susumu.yata
null+****@clear*****
Mon Sep 8 16:57:15 JST 2014
susumu.yata 2014-09-08 16:57:15 +0900 (Mon, 08 Sep 2014) New Revision: 4afdd6bf37c70c1340e697f3e42fb6cb4068fb62 https://github.com/groonga/grnxx/commit/4afdd6bf37c70c1340e697f3e42fb6cb4068fb62 Message: Add Index implementation. Added files: lib/grnxx/tree_index.hpp Modified files: include/grnxx/column.hpp include/grnxx/index.hpp lib/grnxx/column.cpp lib/grnxx/index.cpp Modified: include/grnxx/column.hpp (+2 -2) =================================================================== --- include/grnxx/column.hpp 2014-09-08 11:42:22 +0900 (3f3a10f) +++ include/grnxx/column.hpp 2014-09-08 16:57:15 +0900 (0277fb4) @@ -45,8 +45,8 @@ class Column { virtual Index *create_index( Error *error, String name, - IndexType index_type, - const IndexOptions &index_options = IndexOptions()); + IndexType type, + const IndexOptions &options = IndexOptions()); // Remove an index named "name". // Modified: include/grnxx/index.hpp (+28 -3) =================================================================== --- include/grnxx/index.hpp 2014-09-08 11:42:22 +0900 (7ed194f) +++ include/grnxx/index.hpp 2014-09-08 16:57:15 +0900 (fa73b66) @@ -32,11 +32,38 @@ class Index { Error *error, const CursorOptions &options = CursorOptions()) const; - private: + // 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, + String name, + IndexType type, + const IndexOptions &options = IndexOptions()); + + private: // Create a new index. // // Returns a pointer to the index on success. @@ -49,8 +76,6 @@ class Index { IndexType type, const IndexOptions &options = IndexOptions()); - Index(); - // Change the index name. // // Returns true on success. Modified: lib/grnxx/column.cpp (+46 -6) =================================================================== --- lib/grnxx/column.cpp 2014-09-08 11:42:22 +0900 (e408db7) +++ lib/grnxx/column.cpp 2014-09-08 16:57:15 +0900 (2c6d131) @@ -14,11 +14,24 @@ Column::~Column() {} Index *Column::create_index(Error *error, String name, - IndexType index_type, - const IndexOptions &index_options) { - // TODO: Index is not supported yet. - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not suported yet"); - return nullptr; + IndexType type, + const IndexOptions &options) { + if (find_index(nullptr, name)) { + GRNXX_ERROR_SET(error, ALREADY_EXISTS, + "Index already exists: name = \"%.*s\"", + static_cast<int>(name.size()), name.data()); + return nullptr; + } + if (!indexes_.reserve(error, indexes_.size() + 1)) { + return nullptr; + } + unique_ptr<Index> new_index = + Index::create(error, this, name, type, options); + if (!new_index) { + return nullptr; + } + indexes_.push_back(error, std::move(new_index)); + return indexes_.back().get(); } bool Column::remove_index(Error *error, String name) { @@ -300,6 +313,21 @@ bool ColumnImpl<Int>::set(Error *error, Int row_id, const Datum &datum) { } } // Note that a Bool object does not have its own address. + Int old_value = get(row_id); + Int new_value = datum.force_int(); + 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, datum.force_int()); return true; } @@ -340,11 +368,23 @@ bool ColumnImpl<Int>::set_default_value(Error *error, Int row_id) { return false; } } - values_.set(row_id, TypeTraits<Int>::default_value()); + Int value = TypeTraits<Int>::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; } void ColumnImpl<Int>::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<Int>::default_value()); } Modified: lib/grnxx/index.cpp (+185 -8) =================================================================== --- lib/grnxx/index.cpp 2014-09-08 11:42:22 +0900 (c54edfe) +++ lib/grnxx/index.cpp 2014-09-08 16:57:15 +0900 (7f4471d) @@ -1,27 +1,73 @@ #include "grnxx/index.hpp" +#include "grnxx/column.hpp" +#include "grnxx/column_impl.hpp" #include "grnxx/cursor.hpp" +#include "grnxx/datum.hpp" +#include "grnxx/table.hpp" +#include "grnxx/tree_index.hpp" namespace grnxx { +// -- Index -- + Index::~Index() {} unique_ptr<Cursor> Index::create_cursor( Error *error, const CursorOptions &options) const { - // TODO: Not supported yet. 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, + String name, + IndexType type, + const IndexOptions &options) { + column_ = column; + if (!name_.assign(error, name)) { + return false; + } + type_ = type; + return true; +} + unique_ptr<Index> Index::create(Error *error, Column *column, String name, IndexType type, const IndexOptions &options) { - // TODO: Not supported yet. - GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); - return nullptr; + if (type != TREE_INDEX) { + GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); + return nullptr; + } + switch (column->data_type()) { + case BOOL_DATA: { + GRNXX_ERROR_SET(error, NOT_SUPPORTED_YET, "Not supoprted yet"); + return nullptr; + } + case INT_DATA: { + return TreeIndex<Int>::create(error, column, name, options); + } + case FLOAT_DATA: + case GEO_POINT_DATA: + case TEXT_DATA: + 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, String new_name) { @@ -33,9 +79,140 @@ bool Index::is_removable() { return true; } -Index::Index() - : column_(nullptr), - name_(), - type_() {} +// -- TreeIndexCursor -- + +template <typename T> class TreeIndexCursor; + +template <> +class TreeIndexCursor<Int> : public Cursor { + public: + using Value = Int; + using Set = std::set<Int>; + using Map = std::map<Value, Set>; + + TreeIndexCursor(const Table *table, Map::iterator begin, Map::iterator end) + : Cursor(table), + map_it_(begin), + map_end_(end), + set_it_(), + set_end_() { + if (begin != end) { + set_it_ = begin->second.begin(); + set_end_ = begin->second.end(); + } + } + ~TreeIndexCursor() {} + + Int read(Error *error, Int max_count, Array<Record> *records); + + private: + Map::iterator map_it_; + Map::iterator map_end_; + Set::iterator set_it_; + Set::iterator set_end_; +}; + +Int TreeIndexCursor<Int>::read(Error *error, + Int max_count, + Array<Record> *records) { + if (map_it_ == map_end_) { + return 0; + } + Int count = 0; + for ( ; count < max_count; ++count) { + 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 (!records->push_back(error, Record(*set_it_, 0.0))) { + return -1; + } + ++set_it_; + } + return count; +} + +// -- TreeIndex<Int> -- + +unique_ptr<TreeIndex<Int>> TreeIndex<Int>::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<Int> *>(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<Int>::~TreeIndex() {} + +unique_ptr<Cursor> TreeIndex<Int>::create_cursor( + Error *error, + const CursorOptions &options) const { + unique_ptr<Cursor> cursor( + new (nothrow) TreeIndexCursor<Int>(column_->table(), + map_.begin(), map_.end())); + if (!cursor) { + GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed"); + return nullptr; + } + return cursor; +} + +bool TreeIndex<Int>::insert(Error *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 *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; +} } // namespace grnxx Added: lib/grnxx/tree_index.hpp (+44 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/tree_index.hpp 2014-09-08 16:57:15 +0900 (adb807e) @@ -0,0 +1,44 @@ +#ifndef GRNXX_TREE_INDEX_HPP +#define GRNXX_TREE_INDEX_HPP + +#include <map> +#include <set> + +#include "grnxx/index.hpp" +#include "grnxx/types.hpp" + +namespace grnxx { + +template <typename T> class TreeIndex; + +// TODO: This is just 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, + String name, + const IndexOptions &options); + + ~TreeIndex(); + + unique_ptr<Cursor> create_cursor( + Error *error, + 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����������������������������...Download