susumu.yata
null+****@clear*****
Thu Apr 4 18:22:17 JST 2013
susumu.yata 2013-04-04 18:22:17 +0900 (Thu, 04 Apr 2013) New Revision: 7e64e31e34b7003e85b5333fdb340d6e7d95a9d8 https://github.com/groonga/grnxx/commit/7e64e31e34b7003e85b5333fdb340d6e7d95a9d8 Message: Add grnxx::alpha::Map and its array-based implementation. Added files: lib/grnxx/alpha/map.cpp lib/grnxx/alpha/map.hpp lib/grnxx/alpha/map/Makefile.am lib/grnxx/alpha/map/array.cpp lib/grnxx/alpha/map/array.hpp Modified files: configure.ac lib/grnxx/alpha/Makefile.am Modified: configure.ac (+1 -0) =================================================================== --- configure.ac 2013-03-27 15:13:10 +0900 (43f6b37) +++ configure.ac 2013-04-04 18:22:17 +0900 (cb6c374) @@ -61,6 +61,7 @@ AC_CONFIG_FILES([Makefile lib/Makefile lib/grnxx/Makefile lib/grnxx/alpha/Makefile + lib/grnxx/alpha/map/Makefile lib/grnxx/charset/Makefile lib/grnxx/db/Makefile lib/grnxx/io/Makefile Modified: lib/grnxx/alpha/Makefile.am (+7 -0) =================================================================== --- lib/grnxx/alpha/Makefile.am 2013-03-27 15:13:10 +0900 (2e9a91a) +++ lib/grnxx/alpha/Makefile.am 2013-04-04 18:22:17 +0900 (16f9358) @@ -1,12 +1,19 @@ +SUBDIRS = map + noinst_LTLIBRARIES = libgrnxx_alpha.la +libgrnxx_alpha_la_LIBADD = \ + map/libgrnxx_alpha_map.la + libgrnxx_alpha_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_alpha_la_SOURCES = \ double_array.cpp \ + map.cpp \ sample.cpp libgrnxx_alpha_includedir = ${includedir}/grnxx/alpha libgrnxx_alpha_include_HEADERS = \ double_array.hpp \ + map.hpp \ sample.hpp Added: lib/grnxx/alpha/map.cpp (+176 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map.cpp 2013-04-04 18:22:17 +0900 (c4ee891) @@ -0,0 +1,176 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#include "grnxx/alpha/map.hpp" + +#include "grnxx/alpha/map/array.hpp" +#include "grnxx/slice.hpp" + +namespace grnxx { +namespace alpha { + +template <typename T> +MapCursor<T>::MapCursor() : key_id_(-1), key_() {} + +template <typename T> +MapCursor<T>::~MapCursor() {} + +template <typename T> +bool MapCursor<T>::next() { + // TODO: Not supported!? + return false; +} + +template <typename T> +bool MapCursor<T>::remove() { + // TODO: Not supported. + return false; +} + +template class MapCursor<int8_t>; +template class MapCursor<int16_t>; +template class MapCursor<int32_t>; +template class MapCursor<int64_t>; +template class MapCursor<uint8_t>; +template class MapCursor<uint16_t>; +template class MapCursor<uint32_t>; +template class MapCursor<uint64_t>; +template class MapCursor<double>; +//template class MapCursor<Slice>; + +template <typename T> +Map<T>::Map() {} + +template <typename T> +Map<T>::~Map() {} + +template <typename T> +Map<T> *Map<T>::create(MapType type, io::Pool pool, + const MapOptions &options) { + switch (type) { + case MAP_ARRAY: { + return map::Array<T>::create(pool, options); + } + default: { + // Not supported yet. + return nullptr; + } + } +} + +template <typename T> +Map<T> *Map<T>::open(io::Pool pool, uint32_t block_id) { + const MapHeader *header = static_cast<const MapHeader *>( + pool.get_block_address(block_id)); + switch (header->type) { + case MAP_ARRAY: { + return map::Array<T>::open(pool, block_id); + } + default: { + // Not supported yet. + return nullptr; + } + } +} + +template <typename T> +bool Map<T>::unlink(io::Pool pool, uint32_t block_id) { + const MapHeader *header = static_cast<const MapHeader *>( + pool.get_block_address(block_id)); + switch (header->type) { + case MAP_ARRAY: { + return map::Array<T>::unlink(pool, block_id); + } + default: { + // Not supported yet. + return false; + } + } +} + +template <typename T> +uint32_t Map<T>::block_id() const { + // Not supported. + return 0; +} + +template <typename T> +MapType Map<T>::type() const { + // Not supported. + return MAP_UNKNOWN; +} + +template <typename T> +bool Map<T>::get(int64_t, T *) { + // Not supported. + return false; +} + +template <typename T> +bool Map<T>::unset(int64_t) { + // Not supported. + return false; +} + +template <typename T> +bool Map<T>::reset(int64_t, T) { + // Not supported. + return false; +} + +template <typename T> +bool Map<T>::search(T, int64_t *) { + // Not supported. + return false; +} + +template <typename T> +bool Map<T>::insert(T, int64_t *) { + // Not supported. + return false; +} + +template <typename T> +bool Map<T>::remove(T) { + // Not supported. + return false; +} + +template <typename T> +bool Map<T>::update(T, T, int64_t *) { + // Not supported. + return false; +} + +template <typename T> +void Map<T>::truncate() { + // Not supported. +} + +template class Map<int8_t>; +template class Map<int16_t>; +template class Map<int32_t>; +template class Map<int64_t>; +template class Map<uint8_t>; +template class Map<uint16_t>; +template class Map<uint32_t>; +template class Map<uint64_t>; +template class Map<double>; +//template class Map<Slice>; + +} // namespace alpha +} // namespace grnxx Added: lib/grnxx/alpha/map.hpp (+117 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map.hpp 2013-04-04 18:22:17 +0900 (48ce0c3) @@ -0,0 +1,117 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#ifndef GRNXX_ALPHA_MAP_HPP +#define GRNXX_ALPHA_MAP_HPP + +#include "grnxx/io/pool.hpp" +#include "grnxx/slice.hpp" + +namespace grnxx { +namespace alpha { + +enum MapType : int32_t { + MAP_UNKNOWN = 0, + MAP_ARRAY = 1, // Test implementation. + MAP_DOUBLE_ARRAY = 2, // TODO: Not supported yet. + MAP_PATRICIA = 3, // TODO: Not supported yet. + MAP_HASH_TABLE = 4 // TODO: Not supported yet. +}; + +struct MapOptions { +}; + +struct MapHeader { + MapType type; +}; + +// TODO: Not supported yet. +template <typename T> +class MapCursor { + public: + MapCursor(); + virtual ~MapCursor(); + + // Move the cursor to the next key and return true on success. + virtual bool next(); + + // Remove the current key and return true on success. + virtual bool remove(); + + // Return the ID of the current key. + int64_t key_id() const { + return key_id_; + } + // Return a reference to the current key. + T key() const { + return key_; + } + + private: + int64_t key_id_; + T key_; +}; + +template <typename T> +class Map { + public: + Map(); + virtual ~Map(); + + // Create a map on "pool". + static Map *create(MapType type, io::Pool pool, + const MapOptions &options = MapOptions()); + // Open an existing map. + static Map *open(io::Pool pool, uint32_t block_id); + + // Free blocks allocated to a map. + static bool unlink(io::Pool pool, uint32_t block_id); + + // Return the header block ID of "*this". + virtual uint32_t block_id() const; + // Return the type of "*this". + virtual MapType type() const; + + // Get a key associated with "key_id" and return true on success. + // Assign the found key to "*key" iff "key" != nullptr. + virtual bool get(int64_t key_id, T *key = nullptr); + // Remove a key associated with "key_id" and return true on success. + virtual bool unset(int64_t key_id); + // Replace a key associated with "key_id" with "dest_key" and return true + // on success. + virtual bool reset(int64_t key_id, T dest_key); + + // Search "key" and return true on success. + // Assign the ID to "*key_id" iff "key_id" != nullptr. + virtual bool search(T key, int64_t *key_id = nullptr); + // Insert "key" and return true on success. + // Assign the ID to "*key_id" iff "key_id" != nullptr. + virtual bool insert(T key, int64_t *key_id = nullptr); + // Remove "key" and return true on success. + virtual bool remove(T key); + // Replace "src_key" with "dest_key" and return true on success. + // Assign the ID to "*key_id" iff "key_id" != nullptr. + virtual bool update(T src_key, T dest_key, int64_t *key_id = nullptr); + + // Remove all the keys in "*this". + virtual void truncate(); +}; + +} // namespace alpha +} // namespace grnxx + +#endif // GRNXX_ALPHA_MAP_HPP Added: lib/grnxx/alpha/map/Makefile.am (+10 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map/Makefile.am 2013-04-04 18:22:17 +0900 (8586a95) @@ -0,0 +1,10 @@ +noinst_LTLIBRARIES = libgrnxx_alpha_map.la + +libgrnxx_alpha_map_la_LDFLAGS = @AM_LTLDFLAGS@ + +libgrnxx_alpha_map_la_SOURCES = \ + array.cpp + +libgrnxx_alpha_map_includedir = ${includedir}/grnxx/alpha/map +libgrnxx_alpha_map_include_HEADERS = \ + array.hpp Added: lib/grnxx/alpha/map/array.cpp (+209 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map/array.cpp 2013-04-04 18:22:17 +0900 (876eef5) @@ -0,0 +1,209 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#include "array.hpp" + +namespace grnxx { +namespace alpha { +namespace map { + +ArrayHeader::ArrayHeader() + : map_type(MAP_ARRAY), + bits_block_id(io::BLOCK_INVALID_ID), + keys_block_id(io::BLOCK_INVALID_ID), + max_key_id(-1) {} + +template <typename T> +Array<T>::~Array() {} + +template <typename T> +Array<T> *Array<T>::create(io::Pool pool, const MapOptions &) { + std::unique_ptr<Array<T>> array(new (std::nothrow) Array<T>); + array->pool_ = pool; + array->block_info_ = pool.create_block(sizeof(ArrayHeader)); + array->header_ = static_cast<ArrayHeader *>( + pool.get_block_address(*array->block_info_)); + *array->header_ = ArrayHeader(); + array->bits_.create(pool, 0); + array->header_->bits_block_id = array->bits_.block_id(); + array->keys_.create(pool); + array->header_->keys_block_id = array->keys_.block_id(); + return array.release(); +} + +template <typename T> +Array<T> *Array<T>::open(io::Pool pool, uint32_t block_id) { + std::unique_ptr<Array<T>> array(new (std::nothrow) Array<T>); + array->pool_ = pool; + array->block_info_ = pool.get_block_info(block_id); + array->header_ = static_cast<ArrayHeader *>( + pool.get_block_address(*array->block_info_)); + array->bits_.open(pool, array->header_->bits_block_id); + array->keys_.open(pool, array->header_->keys_block_id); + return array.release(); +} + +template <typename T> +bool Array<T>::unlink(io::Pool pool, uint32_t block_id) { + Array<T> *array = open(pool, block_id); + pool.free_block(array->header_->bits_block_id); + pool.free_block(array->header_->keys_block_id); + pool.free_block(array->block_id()); + return false; +} + +template <typename T> +uint32_t Array<T>::block_id() const { + return block_info_->id(); +} + +template <typename T> +MapType Array<T>::type() const { + return MAP_ARRAY; +} + +template <typename T> +bool Array<T>::get(int64_t key_id, T *key) { + if ((key_id < 0) || (key_id > header_->max_key_id)) { + return false; + } + if (!get_bit(key_id)) { + return false; + } + if (key) { + *key = keys_[key_id]; + } + return true; +} + +template <typename T> +bool Array<T>::unset(int64_t key_id) { + if ((key_id < 0) || (key_id > header_->max_key_id)) { + return false; + } + if (!get_bit(key_id)) { + return false; + } + set_bit(key_id, false); + return true; +} + +template <typename T> +bool Array<T>::reset(int64_t key_id, T dest_key) { + if ((key_id < 0) || (key_id > header_->max_key_id)) { + return false; + } + if (!get_bit(key_id)) { + return false; + } + keys_[key_id] = dest_key; + return true; +} + +template <typename T> +bool Array<T>::search(T key, int64_t *key_id) { + for (int64_t i = 0; i < header_->max_key_id; ++i) { + if (get_bit(i)) { + if (key == keys_[i]) { + if (key_id) { + *key_id = i; + } + return true; + } + } + } + return false; +} + +template <typename T> +bool Array<T>::insert(T key, int64_t *key_id) { + int64_t key_id_candidate = -1; + for (int64_t i = 0; i < header_->max_key_id; ++i) { + if (get_bit(i)) { + if (key == keys_[i]) { + if (key_id) { + *key_id = i; + } + return false; + } + } else if (key_id_candidate != -1) { + // Use the youngest ID if there exist IDs associated with removed keys. + key_id_candidate = i; + } + } + if (key_id_candidate == -1) { + key_id_candidate = ++header_->max_key_id; + } + keys_[key_id_candidate] = key; + if (key_id) { + *key_id = key_id_candidate; + } + return true; +} + +template <typename T> +bool Array<T>::remove(T key) { + int64_t key_id; + if (!search(key, &key_id)) { + return false; + } + set_bit(key_id, false); + return true; +} + +template <typename T> +bool Array<T>::update(T src_key, T dest_key, int64_t *key_id) { + int64_t src_key_id; + if (!search(src_key, &src_key_id)) { + return false; + } + keys_[src_key_id] = dest_key; + if (key_id) { + *key_id = src_key_id; + } + return true; +} + +template <typename T> +void Array<T>::truncate() { + for (int64_t i = 0; i <= header_->max_key_id; ++i) { + set_bit(i, false); + } + header_->max_key_id = -1; +} + +template <typename T> +Array<T>::Array() + : pool_(), + block_info_(nullptr), + header_(nullptr), + bits_(), + keys_() {} + +template class Array<int8_t>; +template class Array<int16_t>; +template class Array<int32_t>; +template class Array<int64_t>; +template class Array<uint8_t>; +template class Array<uint16_t>; +template class Array<uint32_t>; +template class Array<uint64_t>; +template class Array<double>; + +} // namespace map +} // namespace alpha +} // namespace grnxx Added: lib/grnxx/alpha/map/array.hpp (+87 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map/array.hpp 2013-04-04 18:22:17 +0900 (65cf4bb) @@ -0,0 +1,87 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#ifndef GRNXX_ALPHA_MAP_ARRAY_HPP +#define GRNXX_ALPHA_MAP_ARRAY_HPP + +#include "grnxx/alpha/map.hpp" +#include "grnxx/db/vector.hpp" + +namespace grnxx { +namespace alpha { +namespace map { + +struct ArrayHeader { + MapType map_type; + uint32_t bits_block_id; + uint32_t keys_block_id; + int64_t max_key_id; + + ArrayHeader(); +}; + +template <typename T> +class Array : public grnxx::alpha::Map<T> { + public: + ~Array(); + + static Array *create(io::Pool pool, + const MapOptions &options = MapOptions()); + static Array *open(io::Pool pool, uint32_t block_id); + + static bool unlink(io::Pool pool, uint32_t block_id); + + uint32_t block_id() const; + MapType type() const; + + bool get(int64_t key_id, T *key = nullptr); + bool unset(int64_t key_id); + bool reset(int64_t key_id, T dest_key); + + bool search(T key, int64_t *key_id = nullptr); + bool insert(T key, int64_t *key_id = nullptr); + bool remove(T key); + bool update(T src_key, T dest_key, int64_t *key_id = nullptr); + + void truncate(); + + private: + io::Pool pool_; + const io::BlockInfo *block_info_; + ArrayHeader *header_; + db::Vector<uint32_t> bits_; + db::Vector<T> keys_; + + Array(); + + bool get_bit(int64_t key_id) { + return bits_[key_id / 32] & (1U << (key_id % 32)); + } + void set_bit(int64_t key_id, bool bit) { + if (bit) { + bits_[key_id / 32] |= 1U << (key_id % 32); + } else { + bits_[key_id / 32] &= ~(1U << (key_id % 32)); + } + } +}; + +} // namespace map +} // namespace alpha +} // namespace grnxx + +#endif // GRNXX_ALPHA_MAP_ARRAY_HPP -------------- next part -------------- HTML����������������������������...Download