susumu.yata
null+****@clear*****
Thu Jun 6 18:32:24 JST 2013
susumu.yata 2013-06-06 18:32:24 +0900 (Thu, 06 Jun 2013) New Revision: 5d30b5d906e1cf53747127334a6e364ac8df134e https://github.com/groonga/grnxx/commit/5d30b5d906e1cf53747127334a6e364ac8df134e Message: Add components of grnxx::map::DoubleArray. Added files: lib/grnxx/map/double_array/block.hpp lib/grnxx/map/double_array/entry.hpp lib/grnxx/map/double_array/node.hpp Modified files: lib/grnxx/map/double_array/Makefile.am lib/grnxx/map/double_array/dummy.cpp lib/grnxx/map/double_array/header.cpp lib/grnxx/map/double_array/header.hpp Modified: lib/grnxx/map/double_array/Makefile.am (+4 -1) =================================================================== --- lib/grnxx/map/double_array/Makefile.am 2013-06-06 18:25:53 +0900 (5e79c12) +++ lib/grnxx/map/double_array/Makefile.am 2013-06-06 18:32:24 +0900 (9539683) @@ -8,5 +8,8 @@ libgrnxx_map_double_array_la_SOURCES = \ libgrnxx_map_double_array_includedir = ${includedir}/grnxx/map/double_array libgrnxx_map_double_array_include_HEADERS = \ + block.hpp \ dummy.hpp \ - header.hpp + entry.hpp \ + header.hpp \ + node.hpp Added: lib/grnxx/map/double_array/block.hpp (+122 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/double_array/block.hpp 2013-06-06 18:32:24 +0900 (5da7c82) @@ -0,0 +1,122 @@ +/* + Copyright (C) 2012-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_MAP_DOUBLE_ARRAY_BLOCK_HPP +#define GRNXX_MAP_DOUBLE_ARRAY_BLOCK_HPP + +#include "grnxx/features.hpp" + +#include "grnxx/types.hpp" + +namespace grnxx { +namespace map { +namespace double_array { + +constexpr uint64_t BLOCK_MAX_FAILURE_COUNT = 4; +constexpr uint64_t BLOCK_MAX_LEVEL = 5; +constexpr uint64_t BLOCK_INVALID_ID = (1ULL << 40) - 1; + +// The internal structure is as follows: +// - values_[0] +// 0-15 (16): first_phantom +// 16-23 ( 8): level +// 24-63 (40): next +// - values_[1] +// 0-15 (16): num_phantoms +// 16-23 ( 8): failure_count +// 24-63 (40): prev +// where 0 is the LSB and 63 is the MSB. + +class Block { + // For values_[0]. + static constexpr uint64_t FIRST_PHANTOM_MASK = (1ULL << 16) - 1; + static constexpr uint8_t FIRST_PHANTOM_SHIFT = 0; + static constexpr uint64_t LEVEL_MASK = (1ULL << 8) - 1; + static constexpr uint8_t LEVEL_SHIFT = 16; + static constexpr uint64_t NEXT_MASK = (1ULL << 40) - 1; + static constexpr uint8_t NEXT_SHIFT = 24; + + // For values_[1]. + static constexpr uint64_t NUM_PHANTOMS_MASK = (1ULL << 16) - 1; + static constexpr uint8_t NUM_PHANTOMS_SHIFT = 0; + static constexpr uint64_t FAILURE_COUNT_MASK = (1ULL << 8) - 1; + static constexpr uint8_t FAILURE_COUNT_SHIFT = 16; + static constexpr uint64_t PREV_MASK = (1ULL << 40) - 1; + static constexpr uint8_t PREV_SHIFT = 24; + + public: + // Return the first phantom node. + uint64_t first_phantom() const { + return (values_[0] >> FIRST_PHANTOM_SHIFT) & FIRST_PHANTOM_MASK; + } + // Return the level. + uint64_t level() const { + return (values_[0] >> LEVEL_SHIFT) & LEVEL_MASK; + } + // Return the next block ID of the same level. + uint64_t next() const { + return (values_[0] >> NEXT_SHIFT) & NEXT_MASK; + } + + // Return the number of phantom nodes. + uint64_t num_phantoms() const { + return (values_[1] >> NUM_PHANTOMS_SHIFT) & NUM_PHANTOMS_MASK; + } + // Return the failure count. + uint64_t failure_count() const { + return (values_[1] >> FAILURE_COUNT_SHIFT) & FAILURE_COUNT_MASK; + } + // Return the previous block ID of the same level. + uint64_t prev() const { + return (values_[1] >> PREV_SHIFT) & PREV_MASK; + } + + void set_first_phantom(uint64_t first_phantom) { + values_[0] = (values_[0] & ~(FIRST_PHANTOM_MASK << FIRST_PHANTOM_SHIFT)) | + ((first_phantom & FIRST_PHANTOM_MASK) << FIRST_PHANTOM_SHIFT); + } + void set_level(uint64_t level) { + values_[0] = (values_[0] & ~(LEVEL_MASK << LEVEL_SHIFT)) | + ((level & LEVEL_MASK) << LEVEL_SHIFT); + } + void set_next(uint64_t next) { + values_[0] = (values_[0] & ~(NEXT_MASK << NEXT_SHIFT)) | + ((next & NEXT_MASK) << NEXT_SHIFT); + } + + void set_num_phantoms(uint64_t num_phantoms) { + values_[1] = (values_[1] & ~(NUM_PHANTOMS_MASK << NUM_PHANTOMS_SHIFT)) | + ((num_phantoms & NUM_PHANTOMS_MASK) << NUM_PHANTOMS_SHIFT); + } + void set_failure_count(uint64_t failure_count) { + values_[1] = (values_[1] & ~(FAILURE_COUNT_MASK << FAILURE_COUNT_SHIFT)) | + ((failure_count & FAILURE_COUNT_MASK) << FAILURE_COUNT_SHIFT); + } + void set_prev(uint64_t prev) { + values_[1] = (values_[1] & ~(PREV_MASK << PREV_SHIFT)) | + ((prev & PREV_MASK) << PREV_SHIFT); + } + + private: + uint64_t values_[2]; +}; + +} // namespace double_array +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DOUBLE_ARRAY_BLOCK_HPP Modified: lib/grnxx/map/double_array/dummy.cpp (+3 -0) =================================================================== --- lib/grnxx/map/double_array/dummy.cpp 2013-06-06 18:25:53 +0900 (852d43d) +++ lib/grnxx/map/double_array/dummy.cpp 2013-06-06 18:32:24 +0900 (efc0711) @@ -17,7 +17,10 @@ */ #include "grnxx/map/double_array/dummy.hpp" +#include "grnxx/map/double_array/block.hpp" +#include "grnxx/map/double_array/entry.hpp" #include "grnxx/map/double_array/header.hpp" +#include "grnxx/map/double_array/node.hpp" namespace grnxx { namespace map { Added: lib/grnxx/map/double_array/entry.hpp (+73 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/double_array/entry.hpp 2013-06-06 18:32:24 +0900 (9307a94) @@ -0,0 +1,73 @@ +/* + Copyright (C) 2012-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_MAP_DOUBLE_ARRAY_ENTRY_HPP +#define GRNXX_MAP_DOUBLE_ARRAY_ENTRY_HPP + +#include "grnxx/features.hpp" + +#include "grnxx/types.hpp" + +namespace grnxx { +namespace map { +namespace double_array { + +// The internal structure is as follows: +// - Common +// 63 ( 1): is_valid +// - Valid: is_valid +// 0-62 (63): bytes_id +// - Invalid: !is_valid +// 0-62 (63): next +// where 0 is the LSB and 63 is the MSB. + +class Entry { + static constexpr uint64_t IS_VALID_FLAG = 1ULL << 63; + + public: + static Entry valid_entry(uint64_t bytes_id) { + return Entry(IS_VALID_FLAG | bytes_id); + } + static Entry invalid_entry(uint64_t next) { + return Entry(next); + } + + // Return true iff the entry is associated with a key. + explicit operator bool() const { + return value_ & IS_VALID_FLAG; + } + + // Return the ID of the associated byte sequence. + uint64_t bytes_id() const { + return value_ & ~IS_VALID_FLAG; + } + // Return the next invalid entry. + uint64_t next() const { + return value_; + } + + private: + uint64_t value_; + + explicit Entry(uint64_t value) : value_(value) {} +}; + +} // namespace double_array +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DOUBLE_ARRAY_ENTRY_HPP Modified: lib/grnxx/map/double_array/header.cpp (+15 -1) =================================================================== --- lib/grnxx/map/double_array/header.cpp 2013-06-06 18:25:53 +0900 (274581b) +++ lib/grnxx/map/double_array/header.cpp 2013-06-06 18:32:24 +0900 (d33d436) @@ -26,7 +26,21 @@ namespace double_array { Header::Header() : map_type(MAP_ARRAY), max_key_id(MAP_MIN_KEY_ID - 1), - num_keys(0) {} + num_keys(0), + nodes_storage_node_id(STORAGE_INVALID_NODE_ID), + siblings_storage_node_id(STORAGE_INVALID_NODE_ID), + blocks_storage_node_id(STORAGE_INVALID_NODE_ID), + entries_storage_node_id(STORAGE_INVALID_NODE_ID), + store_storage_node_id(STORAGE_INVALID_NODE_ID), + next_key_id(MAP_INVALID_KEY_ID), + num_blocks(0), + num_phantoms(0), + num_zombies(0), + latest_blocks() { + for (uint64_t i = 0; i <= BLOCK_MAX_LEVEL; ++i) { + latest_blocks[i] = BLOCK_INVALID_ID; + } +} } // namespace double_array } // namespace map Modified: lib/grnxx/map/double_array/header.hpp (+11 -0) =================================================================== --- lib/grnxx/map/double_array/header.hpp 2013-06-06 18:25:53 +0900 (b3b035a) +++ lib/grnxx/map/double_array/header.hpp 2013-06-06 18:32:24 +0900 (ddf57f9) @@ -20,6 +20,7 @@ #include "grnxx/features.hpp" +#include "grnxx/map/double_array/block.hpp" #include "grnxx/map.hpp" #include "grnxx/types.hpp" @@ -31,6 +32,16 @@ struct Header { MapType map_type; int64_t max_key_id; uint64_t num_keys; + uint32_t nodes_storage_node_id; + uint32_t siblings_storage_node_id; + uint32_t blocks_storage_node_id; + uint32_t entries_storage_node_id; + uint32_t store_storage_node_id; + uint64_t next_key_id; + uint64_t num_blocks; + uint64_t num_phantoms; + uint64_t num_zombies; + uint64_t latest_blocks[BLOCK_MAX_LEVEL + 1]; Header(); }; Added: lib/grnxx/map/double_array/node.hpp (+197 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/double_array/node.hpp 2013-06-06 18:32:24 +0900 (ed0ec73) @@ -0,0 +1,197 @@ +/* + Copyright (C) 2012-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_MAP_DOUBLE_ARRAY_NODE_HPP +#define GRNXX_MAP_DOUBLE_ARRAY_NODE_HPP + +#include "grnxx/features.hpp" + +#include "grnxx/types.hpp" + +namespace grnxx { +namespace map { +namespace double_array { + +constexpr uint64_t NODE_TERMINAL_LABEL = 0x100; +constexpr uint64_t NODE_MAX_LABEL = NODE_TERMINAL_LABEL; +constexpr uint64_t NODE_INVALID_LABEL = NODE_MAX_LABEL + 1; + +constexpr uint64_t NODE_INVALID_OFFSET = 0; + +// The internal structure is as follows: +// - Common +// 62 ( 1): is_phantom +// 63 ( 1): is_origin +// - Phantom: is_phantom +// 0- 8 ( 9): next +// 9-17 ( 9): prev +// 18-61 (44): reserved +// - NonPhantom: !is_phantom +// 0- 8 ( 9): label +// 60 ( 1): has_sibling +// 61 ( 1): is_leaf +// - Leaf: !is_phantom && is_leaf +// 9-48 (40): key_id +// 49-59 (11): reserved +// - NonLeaf: !is_phantom && !is_leaf +// 9-17 ( 9): child +// 18-59 (42): offset +// where 0 is the LSB and 63 is the MSB. + +class Node { + static constexpr uint64_t IS_PHANTOM_FLAG = 1ULL << 62; + static constexpr uint64_t IS_ORIGIN_FLAG = 1ULL << 63; + + static constexpr uint64_t NEXT_MASK = (1ULL << 9) - 1; + static constexpr uint8_t NEXT_SHIFT = 0; + static constexpr uint64_t PREV_MASK = (1ULL << 9) - 1; + static constexpr uint8_t PREV_SHIFT = 9; + + static constexpr uint64_t LABEL_MASK = (1ULL << 9) - 1; + static constexpr uint8_t LABEL_SHIFT = 0; + static constexpr uint64_t HAS_SIBLING_FLAG = 1ULL << 60; + static constexpr uint64_t IS_LEAF_FLAG = 1ULL << 61; + + static constexpr uint64_t KEY_ID_MASK = (1ULL << 40) - 1; + static constexpr uint8_t KEY_ID_SHIFT = 9; + + static constexpr uint64_t CHILD_MASK = (1ULL << 9) - 1; + static constexpr uint8_t CHILD_SHIFT = 9; + static constexpr uint64_t OFFSET_MASK = (1ULL << 42) - 1; + static constexpr uint8_t OFFSET_SHIFT = 18; + + public: + // Create a phantom node. + static Node phantom_node(uint64_t next, uint64_t prev) { + return Node(IS_PHANTOM_FLAG | ((next & NEXT_MASK) << NEXT_SHIFT) | + ((prev & PREV_MASK) << PREV_SHIFT)); + } + + // Return true iff this node is a phantom node. + bool is_phantom() const { + return value_ & IS_PHANTOM_FLAG; + } + // Return true iff the ID of this node is used as an offset. + bool is_origin() const { + return value_ & IS_ORIGIN_FLAG; + } + + // Return the ID of the next phantom node in the same block. + uint64_t next() const { + return (value_ >> NEXT_SHIFT) & NEXT_MASK; + } + // Return the ID of the prev phantom node in the same block. + uint64_t prev() const { + return (value_ >> PREV_SHIFT) & PREV_MASK; + } + + // Return the label. + // Note that a phantom node returns an invalid label. + uint64_t label() const { + return (value_ >> LABEL_SHIFT) & + ((IS_PHANTOM_FLAG >> LABEL_SHIFT) | LABEL_MASK); + } + // Return true iff this node has a sibling with a greater label. + bool has_sibling() const { + return value_ & HAS_SIBLING_FLAG; + } + // Return true iff this node is a leaf node. + bool is_leaf() const { + return value_ & IS_LEAF_FLAG; + } + + // Return the associated key ID. + uint64_t key_id() const { + return (value_ >> KEY_ID_SHIFT) & KEY_ID_MASK; + } + + // Return the ID of the child node with the least label. + uint64_t child() const { + return (value_ >> CHILD_SHIFT) & CHILD_MASK; + } + // Return the offset to child nodes. + uint64_t offset() const { + return (value_ >> OFFSET_SHIFT) & OFFSET_MASK; + } + + void unset_is_phantom() { + value_ = (value_ & IS_ORIGIN_FLAG) | + (NODE_INVALID_LABEL << LABEL_SHIFT) | + (NODE_INVALID_LABEL << CHILD_SHIFT) | + (NODE_INVALID_OFFSET << OFFSET_SHIFT); + } + void set_is_origin() { + value_ |= IS_ORIGIN_FLAG; + } + + void set_next(uint64_t next) { + value_ = (value_ & ~(NEXT_MASK << NEXT_SHIFT)) | + ((next & NEXT_MASK) << NEXT_SHIFT); + } + void set_prev(uint64_t prev) { + value_ = (value_ & ~(PREV_MASK << PREV_SHIFT)) | + ((prev & PREV_MASK) << PREV_SHIFT); + } + void set_next_and_prev(uint64_t next, uint64_t prev) { + constexpr uint64_t NEXT_AND_PREV_MASK = + (NEXT_MASK << NEXT_SHIFT) | (PREV_MASK << PREV_SHIFT); + value_ = (value_ & ~NEXT_AND_PREV_MASK) | + ((next & NEXT_MASK) << NEXT_SHIFT) | + ((prev & PREV_MASK) << PREV_SHIFT); + } + + void set_label(uint64_t label) { + value_ = (value_ & ~(LABEL_MASK << LABEL_SHIFT)) | + ((label & LABEL_MASK) << LABEL_SHIFT); + } + void set_has_sibling() { + value_ |= HAS_SIBLING_FLAG; + } + // set_is_leaf() is not provided because set_key_id() sets IS_LEAF_FLAG. + + void set_key_id(uint64_t key_id) { + value_ = (value_ & ~(KEY_ID_MASK << KEY_ID_SHIFT)) | IS_LEAF_FLAG | + ((key_id & KEY_ID_MASK) << KEY_ID_SHIFT); + } + + void set_child(uint64_t child) { + value_ = (value_ & ~(CHILD_MASK << CHILD_SHIFT)) | + ((child & CHILD_MASK) << CHILD_SHIFT); + } + // Use unset_offset() iff "offset" == INVALID_OFFSET. + void set_offset(uint64_t offset) { + value_ = (value_ & ~(OFFSET_MASK << OFFSET_SHIFT)) | + ((offset & OFFSET_MASK) << OFFSET_SHIFT); + } + void unset_offset() { + value_ = (value_ & (IS_ORIGIN_FLAG | (LABEL_MASK << LABEL_SHIFT) | + IS_LEAF_FLAG)) | + (NODE_INVALID_LABEL << CHILD_SHIFT) | + (NODE_INVALID_OFFSET << OFFSET_SHIFT); + } + + private: + uint64_t value_; + + explicit Node(uint64_t value) : value_(value) {} +}; + +} // namespace double_array +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DOUBLE_ARRAY_NODE_HPP -------------- next part -------------- HTML����������������������������...Download