susumu.yata
null+****@clear*****
Wed Dec 3 12:34:16 JST 2014
susumu.yata 2014-12-03 12:34:16 +0900 (Wed, 03 Dec 2014) New Revision: 9bf81273c9e2705a1587eeaaba36bca3d3a58204 https://github.com/groonga/grnxx/commit/9bf81273c9e2705a1587eeaaba36bca3d3a58204 Message: Remove the old implementation of Index. Removed files: lib/grnxx/index.cpp lib/grnxx/tree_index.hpp Modified files: include/grnxx/index.hpp Modified: include/grnxx/index.hpp (+0 -127) =================================================================== --- include/grnxx/index.hpp 2014-12-03 12:27:24 +0900 (013392e) +++ include/grnxx/index.hpp 2014-12-03 12:34:16 +0900 (b86348e) @@ -134,133 +134,6 @@ class Index { virtual ~Index() = default; }; -//class Index { -// public: -// virtual ~Index() = default; - -// // Return the owner column. -// Column *column() const { -// return column_; -// } -// // Return the name. -// StringCRef name() const { -// return name_.ref(); -// } -// // Return the index type. -// IndexType type() const { -// return type_; -// } - -// // Check if "datum" is registered or not. -// // -// // If registered, returns true. -// // Otherwise, returns false. -// virtual bool contains(const Datum &datum) const; - -// // Search the index for "datum". -// // -// // On success, returns the row ID of one of the matched values. -// // On failure, returns NULL_ROW_ID. -// virtual Int find_one(const Datum &datum) const; - -// // Create a cursor to get records. -// // -// // On success, returns a pointer to the cursor. -// // On failure, returns nullptr and stores error information into "*error" if -// // "error" != nullptr. -// virtual unique_ptr<Cursor> find( -// Error *error, -// const Datum &datum, -// const CursorOptions &options = CursorOptions()) const; - -// // Create a cursor to get records. -// // -// // Returns a pointer to the cursor on success. -// // On failure, returns nullptr and stores error information into "*error" if -// // "error" != nullptr. -// virtual unique_ptr<Cursor> find_in_range( -// Error *error, -// const IndexRange &range = IndexRange(), -// const CursorOptions &options = CursorOptions()) const; - -// // Create a cursor to get records. -// // -// // Returns a pointer to the cursor on success. -// // On failure, returns nullptr and stores error information into "*error" if -// // "error" != nullptr. -// virtual unique_ptr<Cursor> find_starts_with( -// Error *error, -// const EndPoint &prefix, -// const CursorOptions &options = CursorOptions()) const; - -// // Create a cursor to get records. -// // -// // Returns a pointer to the cursor on success. -// // On failure, returns nullptr and stores error information into "*error" if -// // "error" != nullptr. -// virtual unique_ptr<Cursor> find_prefixes( -// Error *error, -// const Datum &datum, -// const CursorOptions &options = CursorOptions()) const; - -// // Insert a new entry. -// // -// // On success, returns true. -// // On failure, returns false and stores error information into "*error" if -// // "error" != nullptr. -// virtual bool insert(Error *error, Int row_id, const Datum &value) = 0; -// // Insert an entry. -// // -// // On success, returns true. -// // On failure, returns false and stores error information into "*error" if -// // "error" != nullptr. -// virtual bool remove(Error *error, Int row_id, const Datum &value) = 0; - -// protected: -// Column *column_; -// Name name_; -// IndexType type_; - -// Index(); - -// // Initialize the base members. -// // -// // On success, returns true. -// // On failure, returns false and stores error information into "*error" if -// // "error" != nullptr. -// bool initialize_base(Error *error, -// Column *column, -// const StringCRef &name, -// IndexType type, -// const IndexOptions &options); - -// private: -// // Create a new index. -// // -// // Returns a pointer to the index on success. -// // On failure, returns nullptr and stores error information into "*error" if -// // "error" != nullptr. -// static unique_ptr<Index> create( -// Error *error, -// Column *column, -// const StringCRef &name, -// IndexType type, -// const IndexOptions &options = IndexOptions()); - -// // Change the index name. -// // -// // Returns true on success. -// // On failure, returns false and stores error information into "*error" if -// // "error" != nullptr. -// bool rename(Error *error, const StringCRef &new_name); - -// // Return whether the index is removable or not. -// bool is_removable(); - -// protected: -// Index() = default; -//}; - } // namespace grnxx #endif // GRNXX_INDEX_HPP Deleted: lib/grnxx/index.cpp (+0 -1191) 100644 =================================================================== --- lib/grnxx/index.cpp 2014-12-03 12:27:24 +0900 (7edb446) +++ /dev/null @@ -1,1191 +0,0 @@ -#include "grnxx/index.hpp" - -#include "grnxx/cursor.hpp" -#include "grnxx/impl/column.hpp" -#include "grnxx/table.hpp" -#include "grnxx/tree_index.hpp" - -namespace grnxx { - -// -- Index -- - -Index::~Index() {} - -bool Index::contains(const Datum &datum) const { - return find_one(datum) != NULL_ROW_ID; -} - -Int Index::find_one(const Datum &datum) const { - // TODO: This function should not fail, so Cursor should not be used. - auto cursor = find(nullptr, datum); - if (!cursor) { - return NULL_ROW_ID; - } - Array<Record> records; - auto result = cursor->read(nullptr, 1, &records); - if (!result.is_ok || (result.count == 0)) { - return NULL_ROW_ID; - } - return records[0].row_id; -} - -unique_ptr<Cursor> Index::find( - Error *error, - const Datum &, - const CursorOptions &) const { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; -} - -unique_ptr<Cursor> Index::find_in_range( - Error *error, - const IndexRange &, - const CursorOptions &) const { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; -} - -unique_ptr<Cursor> Index::find_starts_with( - Error *error, - const EndPoint &, - const CursorOptions &) const { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; -} - -unique_ptr<Cursor> Index::find_prefixes( - Error *error, - const Datum &, - const CursorOptions &) const { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; -} - -Index::Index() - : column_(nullptr), - name_(), - type_() {} - -bool Index::initialize_base(Error *error, - Column *column, - const StringCRef &name, - IndexType type, - const IndexOptions &) { - column_ = column; - if (!name_.assign(error, name)) { - return false; - } - type_ = type; - return true; -} - -unique_ptr<Index> Index::create(Error *error, - Column *column, - const StringCRef &name, - IndexType type, - const IndexOptions &options) { - if (type != TREE_INDEX) { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; - } - switch (column->data_type()) { - case BOOL_DATA: { - return TreeIndex<Bool>::create(error, column, name, options); - } - case INT_DATA: { - return TreeIndex<Int>::create(error, column, name, options); - } - case FLOAT_DATA: { - return TreeIndex<Float>::create(error, column, name, options); - } - case GEO_POINT_DATA: { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; - } - case TEXT_DATA: { - return TreeIndex<Text>::create(error, column, name, options); - } - case BOOL_VECTOR_DATA: - case INT_VECTOR_DATA: - case FLOAT_VECTOR_DATA: - case GEO_POINT_VECTOR_DATA: - case TEXT_VECTOR_DATA: - default: { - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; - } - } -} - -bool Index::rename(Error *error, const StringCRef &new_name) { - return name_.assign(error, new_name); -} - -bool Index::is_removable() { - // TODO: Not supported yet. - return true; -} - -// -- EmptyCursor -- - -class EmptyCursor : public Cursor { - public: - EmptyCursor(const Table *table) : Cursor(table) {} - - CursorResult read(Error *error, ArrayRef<Record> records); -}; - -CursorResult EmptyCursor::read(Error *, ArrayRef<Record>) { - return CursorResult{ true, 0 }; -} - -// Create an empty cursor. -unique_ptr<Cursor> create_empty_cursor(Error *error, const Table *table) { - unique_ptr<Cursor> cursor(new (nothrow) EmptyCursor(table)); - if (!cursor) { - GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); - return nullptr; - } - return cursor; -} - -// -- IteratorCursor -- - -template <typename T> -class IteratorCursor : public Cursor { - public: - using Iterator = T; - - IteratorCursor(const Table *table, - Iterator begin, - Iterator end, - Int offset, - Int limit) - : Cursor(table), - begin_(begin), - it_(begin), - end_(end), - offset_left_(offset), - limit_left_(limit) {} - ~IteratorCursor() {} - - CursorResult read(Error *error, ArrayRef<Record> records); - - private: - Iterator begin_; - Iterator it_; - Iterator end_; - Int offset_left_; - Int limit_left_; -}; - -template <typename T> -CursorResult IteratorCursor<T>::read(Error *, ArrayRef<Record> records) { - Int max_count = records.size(); - if (max_count > limit_left_) { - max_count = limit_left_; - } - if (max_count <= 0) { - return { true, 0 }; - } - Int count = 0; - while ((offset_left_ > 0) && (it_ != end_)) { - ++it_; - --offset_left_; - } - while ((count < max_count) && (it_ != end_)) { - records.set(count, Record(*it_, 0.0)); - ++count; - ++it_; - } - limit_left_ -= count; - return { true, count }; -} - -// Helper function to create an iterator cursor. -template <typename T> -unique_ptr<Cursor> create_iterator_cursor(Error *error, - const Table *table, - T begin, - T end, - Int offset, - Int limit) { - unique_ptr<Cursor> cursor( - new (nothrow) IteratorCursor<T>(table, begin, end, offset, limit)); - if (!cursor) { - GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); - return nullptr; - } - return cursor; -} - -// TODO: It's not clear that a reverse cursor should return row IDs in -// reverse order or not. -// -// Helper function to create a reverse iterator cursor. -template <typename T> -unique_ptr<Cursor> create_reverse_iterator_cursor(Error *error, - const Table *table, - T begin, - T end, - Int offset, - Int limit) { - using ReverseIterator = std::reverse_iterator<T>; - unique_ptr<Cursor> cursor( - new (nothrow) IteratorCursor<ReverseIterator>(table, - ReverseIterator(end), - ReverseIterator(begin), - offset, - limit)); - if (!cursor) { - GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); - return nullptr; - } - return cursor; -} - -// -- MapSetCursor -- - -template <typename T> -class MapSetCursor : public Cursor { - public: - using MapIterator = T; - using SetIterator = typename MapIterator::value_type::second_type::iterator; - - MapSetCursor(const Table *table, - MapIterator begin, - MapIterator end, - Int offset, - Int limit) - : Cursor(table), - map_begin_(begin), - map_it_(begin), - map_end_(end), - set_it_(), - set_end_(), - offset_left_(offset), - limit_left_(limit) { - if (map_it_ != map_end_) { - set_it_ = map_it_->second.begin(); - set_end_ = map_it_->second.end(); - } - } - ~MapSetCursor() {} - - CursorResult read(Error *error, ArrayRef<Record> records); - - private: - MapIterator map_begin_; - MapIterator map_it_; - MapIterator map_end_; - SetIterator set_begin_; - SetIterator set_it_; - SetIterator set_end_; - Int offset_left_; - Int limit_left_; -}; - -template <typename T> -CursorResult MapSetCursor<T>::read(Error *, ArrayRef<Record> records) { - Int max_count = records.size(); - if (max_count > limit_left_) { - max_count = limit_left_; - } - if (max_count <= 0) { - return { true, 0 }; - } - Int count = 0; - while ((count < max_count) && (map_it_ != map_end_)) { - if (set_it_ == set_end_) { - ++map_it_; - if (map_it_ == map_end_) { - break; - } - set_it_ = map_it_->second.begin(); - set_end_ = map_it_->second.end(); - if (set_it_ == set_end_) { - continue; - } - } - - if (offset_left_ > 0) { - --offset_left_; - } else { - records.set(count, Record(*set_it_, 0.0)); - ++count; - } - ++set_it_; - } - limit_left_ -= count; - return { true, count }; -} - -// Helper function to create a map set cursor. -template <typename T> -unique_ptr<Cursor> create_map_set_cursor(Error *error, - const Table *table, - T begin, - T end, - Int offset, - Int limit) { - unique_ptr<Cursor> cursor( - new (nothrow) MapSetCursor<T>(table, begin, end, offset, limit)); - if (!cursor) { - GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); - return nullptr; - } - return cursor; -} - -// TODO: It's not clear that a reverse cursor should return row IDs in -// reverse order or not. -// -// Helper function to create a reverse map set cursor. -template <typename T> -unique_ptr<Cursor> create_reverse_map_set_cursor(Error *error, - const Table *table, - T begin, - T end, - Int offset, - Int limit) { - using ReverseIterator = std::reverse_iterator<T>; - unique_ptr<Cursor> cursor( - new (nothrow) MapSetCursor<ReverseIterator>(table, - ReverseIterator(end), - ReverseIterator(begin), - offset, - limit)); - if (!cursor) { - GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); - return nullptr; - } - return cursor; -} - -// -- ArrayCursor -- - -class ArrayCursor : public Cursor { - public: - using Set = std::set<Int>; - using Map = std::map<String, Set>; - - ArrayCursor(const Table *table, - Array<Map::iterator> &&array, - Int offset, - Int limit) - : Cursor(table), - array_(std::move(array)), - pos_(0), - it_(), - end_(), - offset_left_(offset), - limit_left_(limit) { - if (array_.size() != 0) { - it_ = array_[0]->second.begin(); - end_ = array_[0]->second.end(); - } - } - ~ArrayCursor() {} - - CursorResult read(Error *error, ArrayRef<Record> records); - - private: - Array<Map::iterator> array_; - Int pos_; - Set::iterator it_; - Set::iterator end_; - Int offset_left_; - Int limit_left_; -}; - -CursorResult ArrayCursor::read(Error *, ArrayRef<Record> records) { - Int max_count = records.size(); - if (max_count > limit_left_) { - max_count = limit_left_; - } - if (max_count <= 0) { - return { true, 0 }; - } - Int count = 0; - while ((count < max_count) && (pos_ < array_.size())) { - if (it_ == end_) { - ++pos_; - if (pos_ >= array_.size()) { - break; - } - it_ = array_[pos_]->second.begin(); - end_ = array_[pos_]->second.end(); - if (it_ == end_) { - continue; - } - } - - if (offset_left_ > 0) { - --offset_left_; - } else { - records.set(count, Record(*it_, 0.0)); - ++count; - } - ++it_; - } - limit_left_ -= count; - return { true, count }; -} - -// -- TreeIndex<Bool> -- - -unique_ptr<TreeIndex<Bool>> TreeIndex<Bool>::create( - Error *error, - Column *column, - const StringCRef &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<impl::Column<Bool> *>(column); - Array<Record> records; - for ( ; ; ) { - auto result = cursor->read(error, 1024, &records); - if (!result.is_ok) { - return nullptr; - } else if (result.count == 0) { - break; - } - for (Int i = 0; i < result.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<Bool>::~TreeIndex() {} - -unique_ptr<Cursor> TreeIndex<Bool>::find( - Error *error, - const Datum &datum, - const CursorOptions &options) const { - if (datum.type() != BOOL_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - - auto map_it = map_.find(datum.force_bool()); - if (map_it == map_.end()) { - return create_empty_cursor(error, column_->table()); - } else { - 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<Bool>::find_in_range( - Error *error, - const IndexRange &range, - const CursorOptions &options) const { - Bool lower_bound_value = false; - if (range.has_lower_bound()) { - const EndPoint &lower_bound = range.lower_bound(); - if (lower_bound.value.type() != BOOL_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - lower_bound_value = lower_bound.value.force_bool(); - if (lower_bound.type == EXCLUSIVE_END_POINT) { - if (lower_bound_value) { - return create_empty_cursor(error, column_->table()); - } - lower_bound_value = true; - } - } - - Bool upper_bound_value = true; - if (range.has_upper_bound()) { - const EndPoint &upper_bound = range.upper_bound(); - if (upper_bound.value.type() != BOOL_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - upper_bound_value = upper_bound.value.force_bool(); - if (upper_bound.type == EXCLUSIVE_END_POINT) { - if (!upper_bound_value) { - return create_empty_cursor(error, column_->table()); - } - upper_bound_value = false; - } - } - - if (lower_bound_value > upper_bound_value) { - return create_empty_cursor(error, column_->table()); - } - - 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<Bool>::insert(Error *, Int row_id, const Datum &value) { - auto result = map_[value.force_bool()].insert(row_id); - if (!result.second) { - // Already exists. - return false; - } - return true; -} - -bool TreeIndex<Bool>::remove(Error *, Int row_id, const Datum &value) { - auto map_it = map_.find(value.force_bool()); - 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; -} - -// -- TreeIndex<Int> -- - -unique_ptr<TreeIndex<Int>> TreeIndex<Int>::create( - Error *error, - Column *column, - const StringCRef &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<impl::Column<Int> *>(column); - Array<Record> records; - for ( ; ; ) { - auto result = cursor->read(error, 1024, &records); - if (!result.is_ok) { - return nullptr; - } else if (result.count == 0) { - break; - } - for (Int i = 0; i < result.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<Int>::~TreeIndex() {} - -unique_ptr<Cursor> TreeIndex<Int>::find( - Error *error, - const Datum &datum, - const CursorOptions &options) const { - if (datum.type() != INT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - - auto map_it = map_.find(datum.force_int()); - if (map_it == map_.end()) { - return create_empty_cursor(error, column_->table()); - } else { - 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<Int>::find_in_range( - Error *error, - const IndexRange &range, - const CursorOptions &options) const { - Int lower_bound_value = numeric_limits<Int>::min(); - if (range.has_lower_bound()) { - const EndPoint &lower_bound = range.lower_bound(); - if (lower_bound.value.type() != INT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - lower_bound_value = lower_bound.value.force_int(); - if (lower_bound.type == EXCLUSIVE_END_POINT) { - if (lower_bound_value == numeric_limits<Int>::max()) { - return create_empty_cursor(error, column_->table()); - } - ++lower_bound_value; - } - } - - Int upper_bound_value = numeric_limits<Int>::max(); - if (range.has_upper_bound()) { - const EndPoint &upper_bound = range.upper_bound(); - if (upper_bound.value.type() != INT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - upper_bound_value = upper_bound.value.force_int(); - if (upper_bound.type == EXCLUSIVE_END_POINT) { - if (upper_bound_value == numeric_limits<Int>::min()) { - return create_empty_cursor(error, column_->table()); - } - --upper_bound_value; - } - } - - if (lower_bound_value > upper_bound_value) { - return create_empty_cursor(error, column_->table()); - } - - 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<Int>::insert(Error *, Int row_id, const Datum &value) { - auto result = map_[value.force_int()].insert(row_id); - if (!result.second) { - // Already exists. - return false; - } - return true; -} - -bool TreeIndex<Int>::remove(Error *, Int row_id, const Datum &value) { - auto map_it = map_.find(value.force_int()); - 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; -} - -// -- TreeIndex<Float> -- - -unique_ptr<TreeIndex<Float>> TreeIndex<Float>::create( - Error *error, - Column *column, - const StringCRef &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<impl::Column<Float> *>(column); - Array<Record> records; - for ( ; ; ) { - auto result = cursor->read(error, 1024, &records); - if (!result.is_ok) { - return nullptr; - } else if (result.count == 0) { - break; - } - for (Int i = 0; i < result.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>::find( - 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>::find_in_range( - 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)) { - return create_empty_cursor(error, column_->table()); - } 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()) { - return create_empty_cursor(error, column_->table()); - } 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)) { - return create_empty_cursor(error, column_->table()); - } - - 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; -} - -// -- TreeIndex<Text> -- - -unique_ptr<TreeIndex<Text>> TreeIndex<Text>::create( - Error *error, - Column *column, - const StringCRef &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<impl::Column<Text> *>(column); - Array<Record> records; - for ( ; ; ) { - auto result = cursor->read(error, 1024, &records); - if (!result.is_ok) { - return nullptr; - } else if (result.count == 0) { - break; - } - for (Int i = 0; i < result.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<Text>::~TreeIndex() {} - -unique_ptr<Cursor> TreeIndex<Text>::find( - Error *error, - const Datum &datum, - const CursorOptions &options) const { - if (datum.type() != TEXT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - - String string; - if (!string.assign(error, datum.force_text())) { - return nullptr; - } - auto map_it = map_.find(string); - 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<Text>::find_in_range( - Error *error, - const IndexRange &range, - const CursorOptions &options) const { - String lower_bound_value; - if (range.has_lower_bound()) { - const EndPoint &lower_bound = range.lower_bound(); - if (lower_bound.value.type() != TEXT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - if (!lower_bound_value.assign(error, lower_bound.value.force_text())) { - return nullptr; - } - if (lower_bound.type == EXCLUSIVE_END_POINT) { - if (!lower_bound_value.push_back(error, '\0')) { - return nullptr; - } - } - } - - String upper_bound_value; - if (range.has_upper_bound()) { - const EndPoint &upper_bound = range.upper_bound(); - if (upper_bound.value.type() != TEXT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - if (!upper_bound_value.assign(error, upper_bound.value.force_text())) { - return nullptr; - } - if (upper_bound.type == INCLUSIVE_END_POINT) { - if (!upper_bound_value.push_back(error, '\0')) { - return nullptr; - } - } else if (upper_bound_value.size() == 0) { - return create_empty_cursor(error, column_->table()); - } - } - - if (range.has_upper_bound()) { - if (lower_bound_value >= upper_bound_value) { - return create_empty_cursor(error, column_->table()); - } - } - - auto begin = map_.lower_bound(lower_bound_value); - auto end = range.has_upper_bound() ? - map_.lower_bound(upper_bound_value) : map_.end(); - 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); - } -} - -unique_ptr<Cursor> TreeIndex<Text>::find_starts_with( - Error *error, - const EndPoint &prefix, - const CursorOptions &options) const { - String lower_bound_value; - if (prefix.value.type() != TEXT_DATA) { - GRNXX_ERROR_SET(error, INVALID_ARGUMENT, "Data type conflict"); - return nullptr; - } - if (!lower_bound_value.assign(error, prefix.value.force_text())) { - return nullptr; - } - - String upper_bound_value; - if (!upper_bound_value.assign(error, lower_bound_value)) { - return nullptr; - } - while ((upper_bound_value.size() != 0) && - (static_cast<unsigned char>(upper_bound_value.back()) == 0xFF)) { - upper_bound_value.pop_back(); - } - if (upper_bound_value.size() != 0) { - ++upper_bound_value.back(); - } - - if (prefix.type == EXCLUSIVE_END_POINT) { - if (!lower_bound_value.push_back(error, '\0')) { - return nullptr; - } - } - - auto begin = map_.lower_bound(lower_bound_value); - auto end = (upper_bound_value.size() != 0) ? - map_.lower_bound(upper_bound_value) : map_.end(); - 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); - } -} - -unique_ptr<Cursor> TreeIndex<Text>::find_prefixes( - Error *error, - const Datum &prefix, - const CursorOptions &options) const { - String value; - if (!value.assign(error, prefix.force_text())) { - return nullptr; - } - Array<Map::iterator> array; - String substr; - for (Int i = 0; i <= value.size(); ++i) { - if (!substr.assign(error, value.ref(0, i))) { - return nullptr; - } - auto it = map_.find(substr); - if (it != map_.end()) { - if (!array.push_back(error, it)) { - return nullptr; - } - } - } - if (options.order_type == REVERSE_ORDER) { - for (Int i = 0; i < (array.size() / 2); ++i) { - Map::iterator temp = array[i]; - array[i] = array[array.size() - i - 1]; - array[array.size() - i - 1] = temp; - } - } - unique_ptr<Cursor> cursor( - new (nothrow) ArrayCursor(column_->table(), std::move(array), - options.offset, options.limit)); - if (!cursor) { - GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); - return nullptr; - } - return cursor; -} - -bool TreeIndex<Text>::insert(Error *error, Int row_id, const Datum &value) { - String string; - if (!string.assign(error, value.force_text())) { - return false; - } - auto map_pair = map_.insert(std::make_pair(std::move(string), Set())); - auto set_pair = map_pair.first->second.insert(row_id); - if (!set_pair.second) { - // Already exists. - return false; - } -// auto result = map_[string].insert(row_id); -// if (!result.second) { -// // Already exists. -// return false; -// } - return true; -} - -bool TreeIndex<Text>::remove(Error *error, Int row_id, const Datum &value) { - String string; - if (!string.assign(error, value.force_text())) { - return false; - } - auto map_it = map_.find(string); - 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 Deleted: lib/grnxx/tree_index.hpp (+0 -175) 100644 =================================================================== --- lib/grnxx/tree_index.hpp 2014-12-03 12:27:24 +0900 (94a710a) +++ /dev/null @@ -1,175 +0,0 @@ -#ifndef GRNXX_TREE_INDEX_HPP -#define GRNXX_TREE_INDEX_HPP - -#include <cmath> -#include <map> -#include <set> - -#include "grnxx/index.hpp" -#include "grnxx/types.hpp" - -namespace grnxx { - -template <typename T> class TreeIndex; - -// TODO: This is a test implementation. -template <> -class TreeIndex<Bool> : public Index { - public: - using Value = Bool; - using Set = std::set<Int>; - using Map = std::map<Value, Set>; - - static unique_ptr<TreeIndex> create(Error *error, - Column *column, - const StringCRef &name, - const IndexOptions &options); - - ~TreeIndex(); - - unique_ptr<Cursor> find( - Error *error, - const Datum &datum, - const CursorOptions &options = CursorOptions()) const; - - unique_ptr<Cursor> find_in_range( - 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_() {} -}; - -// TODO: This is a test implementation. -template <> -class TreeIndex<Int> : public Index { - public: - using Value = Int; - using Set = std::set<Int>; - using Map = std::map<Value, Set>; - - static unique_ptr<TreeIndex> create(Error *error, - Column *column, - const StringCRef &name, - const IndexOptions &options); - - ~TreeIndex(); - - unique_ptr<Cursor> find( - Error *error, - const Datum &datum, - const CursorOptions &options = CursorOptions()) const; - - unique_ptr<Cursor> find_in_range( - 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_() {} -}; - -// TODO: This is 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, - const StringCRef &name, - const IndexOptions &options); - - ~TreeIndex(); - - unique_ptr<Cursor> find( - Error *error, - const Datum &datum, - const CursorOptions &options = CursorOptions()) const; - - unique_ptr<Cursor> find_in_range( - 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_() {} -}; - -// TODO: This is a test implementation. -template <> -class TreeIndex<Text> : public Index { - public: - using Value = Text; - using Set = std::set<Int>; - using Map = std::map<String, Set>; - - static unique_ptr<TreeIndex> create(Error *error, - Column *column, - const StringCRef &name, - const IndexOptions &options); - - ~TreeIndex(); - - unique_ptr<Cursor> find( - Error *error, - const Datum &datum, - const CursorOptions &options = CursorOptions()) const; - - unique_ptr<Cursor> find_in_range( - Error *error, - const IndexRange &range, - const CursorOptions &options) const; - - unique_ptr<Cursor> find_starts_with( - Error *error, - const EndPoint &prefix, - const CursorOptions &options = CursorOptions()) const; - - unique_ptr<Cursor> find_prefixes( - Error *error, - const Datum &prefix, - const CursorOptions &options = CursorOptions()) 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����������������������������...Descargar
