Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx at d134110 [master] Add TreeIndex<Float>. (#56)

susumu.yata null+****@clear*****
Tue Sep 16 11:30:04 JST 2014

• Previous message: [Groonga-commit] groonga/grnxx at 3c59b28 [master] Add a test for Cursor with offset and limit.
• Next message: [Groonga-commit] groonga/grnxx at b1a77f6 [master] Add tests for TreeIndex<Float>. (#56)
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2014-09-16 11:30:04 +0900 (Tue, 16 Sep 2014)

  New Revision: d13411002e670274dba73b34f780db38ef4d2bf4
  https://github.com/groonga/grnxx/commit/d13411002e670274dba73b34f780db38ef4d2bf4

  Message:
    Add TreeIndex<Float>. (#56)

  Modified files:
    lib/grnxx/column.cpp
    lib/grnxx/index.cpp
    lib/grnxx/tree_index.hpp

  Modified: lib/grnxx/column.cpp (+32 -5)
===================================================================
--- lib/grnxx/column.cpp    2014-09-16 10:15:32 +0900 (fc2f5f9)
+++ lib/grnxx/column.cpp    2014-09-16 11:30:04 +0900 (d94736e)
@@ -238,9 +238,24 @@ bool ColumnImpl<T>::set(Error *error, Int row_id, const Datum &datum) {
     return false;
   }
   // Note that a Bool object does not have its own address.
-  T value;
-  datum.force(&value);
-  values_.set(row_id, value);
+  T old_value = get(row_id);
+  T new_value;
+  datum.force(&new_value);
+  // TODO: Note that NaN != NaN.
+  if (new_value != old_value) {
+    for (Int i = 0; i < num_indexes(); ++i) {
+      if (!indexes_[i]->insert(error, row_id, datum)) {
+        for (Int j = 0; j < i; ++i) {
+          indexes_[j]->remove(nullptr, row_id, datum);
+        }
+        return false;
+      }
+    }
+    for (Int i = 0; i < num_indexes(); ++i) {
+      indexes_[i]->remove(nullptr, row_id, old_value);
+    }
+  }
+  values_.set(row_id, new_value);
   return true;
 }
 
@@ -284,12 +299,24 @@ bool ColumnImpl<T>::set_default_value(Error *error, Int row_id) {
       return false;
     }
   }
-  values_.set(row_id, TypeTraits<T>::default_value());
+  T value = TypeTraits<T>::default_value();
+  for (Int i = 0; i < num_indexes(); ++i) {
+    if (!indexes_[i]->insert(error, row_id, value)) {
+      for (Int j = 0; j < i; ++j) {
+        indexes_[j]->remove(nullptr, row_id, value);
+      }
+      return false;
+    }
+  }
+  values_.set(row_id, value);
   return true;
 }
 
 template <typename T>
 void ColumnImpl<T>::unset(Int row_id) {
+  for (Int i = 0; i < num_indexes(); ++i) {
+    indexes_[i]->remove(nullptr, row_id, get(row_id));
+  }
   values_.set(row_id, TypeTraits<T>::default_value());
 }
 
@@ -327,7 +354,7 @@ bool ColumnImpl<Int>::set(Error *error, Int row_id, const Datum &datum) {
       indexes_[i]->remove(nullptr, row_id, old_value);
     }
   }
-  values_.set(row_id, datum.force_int());
+  values_.set(row_id, new_value);
   return true;
 }
 

  Modified: lib/grnxx/index.cpp (+175 -1)
===================================================================
--- lib/grnxx/index.cpp    2014-09-16 10:15:32 +0900 (7b4cde7)
+++ lib/grnxx/index.cpp    2014-09-16 11:30:04 +0900 (42d5a2b)
@@ -63,7 +63,9 @@ unique_ptr<Index> Index::create(Error *error,
     case INT_DATA: {
       return TreeIndex<Int>::create(error, column, name, options);
     }
-    case FLOAT_DATA:
+    case FLOAT_DATA: {
+      return TreeIndex<Float>::create(error, column, name, options);
+    }
     case GEO_POINT_DATA:
     case TEXT_DATA:
     case BOOL_VECTOR_DATA:
@@ -498,4 +500,176 @@ bool TreeIndex<Int>::remove(Error *, Int row_id, const Datum &value) {
   return true;
 }
 
+// -- TreeIndex<Float> --
+
+unique_ptr<TreeIndex<Float>> TreeIndex<Float>::create(
+    Error *error,
+    Column *column,
+    String name,
+    const IndexOptions &options) {
+  unique_ptr<TreeIndex> index(new (nothrow) TreeIndex);
+  if (!index) {
+    GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed");
+    return nullptr;
+  }
+  if (!index->initialize_base(error, column, name, TREE_INDEX, options)) {
+    return nullptr;
+  }
+  auto cursor = column->table()->create_cursor(error);
+  if (!cursor) {
+    return nullptr;
+  }
+  auto typed_column = static_cast<ColumnImpl<Float> *>(column);
+  Array<Record> records;
+  for ( ; ; ) {
+    Int count = cursor->read(error, 1024, &records);
+    if (count < 0) {
+      return nullptr;
+    } else if (count == 0) {
+      break;
+    }
+    for (Int i = 0; i < count; ++i) {
+      Int row_id = records.get_row_id(i);
+      if (!index->insert(error, row_id, typed_column->get(row_id))) {
+        return nullptr;
+      }
+    }
+    records.clear();
+  }
+  return index;
+}
+
+TreeIndex<Float>::~TreeIndex() {}
+
+unique_ptr<Cursor> TreeIndex<Float>::create_cursor(
+    Error *error,
+    const Datum &datum,
+    const CursorOptions &options) const {
+  if (datum.type() != FLOAT_DATA) {
+    GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict");
+    return nullptr;
+  }
+
+  auto map_it = map_.find(datum.force_float());
+  if (map_it == map_.end()) {
+    return create_empty_cursor(error, column_->table());
+  }
+  auto set_begin = map_it->second.begin();
+  auto set_end = map_it->second.end();
+  if (options.order_type == REGULAR_ORDER) {
+    return create_iterator_cursor(error,
+                                  column_->table(),
+                                  set_begin,
+                                  set_end,
+                                  options.offset,
+                                  options.limit);
+  } else {
+    return create_reverse_iterator_cursor(error,
+                                          column_->table(),
+                                          set_begin,
+                                          set_end,
+                                          options.offset,
+                                          options.limit);
+  }
+}
+
+unique_ptr<Cursor> TreeIndex<Float>::create_cursor(
+    Error *error,
+    const IndexRange &range,
+    const CursorOptions &options) const {
+  Float lower_bound_value = numeric_limits<Float>::min();
+  if (range.has_lower_bound()) {
+    const EndPoint &lower_bound = range.lower_bound();
+    if (lower_bound.value.type() != FLOAT_DATA) {
+      GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict");
+      return nullptr;
+    }
+    lower_bound_value = lower_bound.value.force_float();
+    if (lower_bound.type == EXCLUSIVE_END_POINT) {
+      if (lower_bound_value == -numeric_limits<Float>::infinity()) {
+        lower_bound_value = numeric_limits<Float>::min();
+      } else if (lower_bound_value == numeric_limits<Float>::max()) {
+        lower_bound_value = numeric_limits<Float>::infinity();
+      } else if (std::isnan(lower_bound_value)) {
+        // TODO: Invalid range.
+        return nullptr;
+      } else {
+        lower_bound_value = std::nextafter(lower_bound_value,
+                                           numeric_limits<Float>::max());
+      }
+    }
+  }
+
+  Float upper_bound_value = numeric_limits<Float>::max();
+  if (range.has_upper_bound()) {
+    const EndPoint &upper_bound = range.upper_bound();
+    if (upper_bound.value.type() != FLOAT_DATA) {
+      GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict");
+      return nullptr;
+    }
+    upper_bound_value = upper_bound.value.force_float();
+    if (upper_bound.type == EXCLUSIVE_END_POINT) {
+      if (upper_bound_value == -numeric_limits<Float>::infinity()) {
+        // TODO: Invalid range.
+        return nullptr;
+      } else if (upper_bound_value == numeric_limits<Float>::min()) {
+        upper_bound_value = -numeric_limits<Float>::infinity();
+      } else if (std::isnan(upper_bound_value)) {
+        upper_bound_value = numeric_limits<Float>::infinity();
+      } else {
+        upper_bound_value = std::nextafter(upper_bound_value,
+                                           numeric_limits<Float>::min());
+      }
+    }
+  }
+
+  if (Less()(upper_bound_value, lower_bound_value)) {
+    // TODO: Invalid range.
+    return nullptr;
+  }
+
+  auto begin = map_.lower_bound(lower_bound_value);
+  auto end = map_.upper_bound(upper_bound_value);
+  if (options.order_type == REGULAR_ORDER) {
+    return create_map_set_cursor(error,
+                                 column_->table(),
+                                 begin,
+                                 end,
+                                 options.offset,
+                                 options.limit);
+  } else {
+    return create_reverse_map_set_cursor(error,
+                                         column_->table(),
+                                         begin,
+                                         end,
+                                         options.offset,
+                                         options.limit);
+  }
+}
+
+bool TreeIndex<Float>::insert(Error *, Int row_id, const Datum &value) {
+  auto result = map_[value.force_float()].insert(row_id);
+  if (!result.second) {
+    // Already exists.
+    return false;
+  }
+  return true;
+}
+
+bool TreeIndex<Float>::remove(Error *, Int row_id, const Datum &value) {
+  auto map_it = map_.find(value.force_float());
+  if (map_it == map_.end()) {
+    return false;
+  }
+  auto set_it = map_it->second.find(row_id);
+  if (set_it == map_it->second.end()) {
+    return false;
+  }
+  map_it->second.erase(set_it);
+  if (map_it->second.size() == 0) {
+    map_.erase(map_it);
+  }
+  return true;
+}
+
 }  // namespace grnxx

  Modified: lib/grnxx/tree_index.hpp (+47 -0)
===================================================================
--- lib/grnxx/tree_index.hpp    2014-09-16 10:15:32 +0900 (fb87673)
+++ lib/grnxx/tree_index.hpp    2014-09-16 11:30:04 +0900 (f665232)
@@ -1,6 +1,7 @@
 #ifndef GRNXX_TREE_INDEX_HPP
 #define GRNXX_TREE_INDEX_HPP
 
+#include <cmath>
 #include <map>
 #include <set>
 
@@ -45,6 +46,52 @@ class TreeIndex<Int> : public Index {
   TreeIndex() : Index(), map_() {}
 };
 
+// TODO: This is just a test implementation.
+template <>
+class TreeIndex<Float> : public Index {
+ public:
+  struct Less {
+    bool operator()(Float lhs, Float rhs) const {
+      // Numbers are prior to NaN.
+      if (std::isnan(lhs)) {
+        return false;
+      } else if (std::isnan(rhs)) {
+        return true;
+      }
+      return lhs < rhs;
+    }
+  };
+
+  using Value = Float;
+  using Set = std::set<Int>;
+  using Map = std::map<Value, Set, Less>;
+
+  static unique_ptr<TreeIndex> create(Error *error,
+                                      Column *column,
+                                      String name,
+                                      const IndexOptions &options);
+
+  ~TreeIndex();
+
+  unique_ptr<Cursor> create_cursor(
+      Error *error,
+      const Datum &datum,
+      const CursorOptions &options = CursorOptions()) const;
+
+  unique_ptr<Cursor> create_cursor(
+      Error *error,
+      const IndexRange &range,
+      const CursorOptions &options) const;
+
+  bool insert(Error *error, Int row_id, const Datum &value);
+  bool remove(Error *error, Int row_id, const Datum &value);
+
+ private:
+  mutable Map map_;
+
+  TreeIndex() : Index(), map_() {}
+};
+
 }  // namespace grnxx
 
 #endif  // GRNXX_TREE_INDEX_HPP
-------------- next part --------------
HTML����������������������������...
Download 

• Previous message: [Groonga-commit] groonga/grnxx at 3c59b28 [master] Add a test for Cursor with offset and limit.
• Next message: [Groonga-commit] groonga/grnxx at b1a77f6 [master] Add tests for TreeIndex<Float>. (#56)
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]