susumu.yata
null+****@clear*****
Mon Aug 5 16:00:30 JST 2013
susumu.yata 2013-08-05 16:00:30 +0900 (Mon, 05 Aug 2013) New Revision: e96fe8282e922a9514462fa805cd42e73c0cdc45 https://github.com/groonga/grnxx/commit/e96fe8282e922a9514462fa805cd42e73c0cdc45 Message: Move the definition of Patricia::Node. Removed files: lib/grnxx/map/patricia/Makefile.am lib/grnxx/map/patricia/dummy.cpp lib/grnxx/map/patricia/dummy.hpp lib/grnxx/map/patricia/node.hpp Modified files: configure.ac lib/grnxx/map/Makefile.am lib/grnxx/map/patricia.cpp lib/grnxx/map/patricia.hpp Modified: configure.ac (+0 -1) =================================================================== --- configure.ac 2013-08-05 15:53:42 +0900 (4df9e9b) +++ configure.ac 2013-08-05 16:00:30 +0900 (2f71390) @@ -63,7 +63,6 @@ AC_CONFIG_FILES([Makefile lib/grnxx/charset/Makefile lib/grnxx/map/Makefile lib/grnxx/map/double_array/Makefile - lib/grnxx/map/patricia/Makefile lib/grnxx/storage/Makefile src/Makefile test/Makefile]) Modified: lib/grnxx/map/Makefile.am (+2 -4) =================================================================== --- lib/grnxx/map/Makefile.am 2013-08-05 15:53:42 +0900 (6f9f4d6) +++ lib/grnxx/map/Makefile.am 2013-08-05 16:00:30 +0900 (10f354d) @@ -1,12 +1,10 @@ SUBDIRS = \ - double_array \ - patricia + double_array noinst_LTLIBRARIES = libgrnxx_map.la libgrnxx_map_la_LIBADD = \ - double_array/libgrnxx_map_double_array.la \ - patricia/libgrnxx_map_patricia.la + double_array/libgrnxx_map_double_array.la libgrnxx_map_la_LDFLAGS = @AM_LTLDFLAGS@ Modified: lib/grnxx/map/patricia.cpp (+92 -7) =================================================================== --- lib/grnxx/map/patricia.cpp 2013-08-05 15:53:42 +0900 (e590358) +++ lib/grnxx/map/patricia.cpp 2013-08-05 16:00:30 +0900 (cda6a46) @@ -28,7 +28,6 @@ #include "grnxx/map/hash.hpp" #include "grnxx/map/helper.hpp" #include "grnxx/map/key_pool.hpp" -#include "grnxx/map/patricia/node.hpp" #include "grnxx/mutex.hpp" #include "grnxx/storage.hpp" @@ -44,12 +43,12 @@ constexpr uint64_t DUMMY_NODE_ID = ROOT_NODE_ID + 1; constexpr uint64_t NODE_ARRAY_SIZE = 1ULL << 41; constexpr uint64_t CACHE_SIZE = 1ULL << 19; -using patricia::NODE_INVALID_OFFSET; - -using patricia::NODE_DEAD; -using patricia::NODE_LEAF; -using patricia::NODE_BRANCH; -using patricia::NODE_TERMINAL; +enum NodeStatus : uint64_t { + NODE_DEAD = 0, + NODE_LEAF = 1, + NODE_BRANCH = 2, + NODE_TERMINAL = 3 +}; } // namespace @@ -83,6 +82,92 @@ PatriciaHeader::operator bool() const { return common_header.format() == FORMAT_STRING; } +// The internal structure of PatriciaNode is as follows: +// - Common +// 62-63 ( 2): status (DEAD, LEAF, BRANCH, TERMINAL) +// - Leaf: LEAF +// 0-39 (40): key_id +// 40-61 (22): reserved +// - Branch or Terminal: BRANCH || TERMINAL +// 16-57 (42): offset +// 58-61 ( 4): reserved +// - Branch: BRANCH +// 0-15 (16): bit_pos +// - Terminal: TERMINAL +// 0-15 (16): bit_size +// where 0 is the LSB and 63 is the MSB. +class PatriciaNode { + static constexpr uint64_t STATUS_MASK = (1ULL << 2) - 1; + static constexpr uint8_t STATUS_SHIFT = 62; + + static constexpr uint64_t KEY_ID_MASK = (1ULL << 40) - 1; + static constexpr uint8_t KEY_ID_SHIFT = 0; + + static constexpr uint64_t OFFSET_MASK = (1ULL << 42) - 1; + static constexpr uint8_t OFFSET_SHIFT = 16; + + static constexpr uint64_t BIT_POS_MASK = (1ULL << 16) - 1; + static constexpr uint8_t BIT_POS_SHIFT = 0; + + static constexpr uint64_t BIT_SIZE_MASK = (1ULL << 16) - 1; + static constexpr uint8_t BIT_SIZE_SHIFT = 0; + + public: + PatriciaNode() = default; + + // Create a node that has neither descendants nor an associated key. + static PatriciaNode dead_node() { + return PatriciaNode(NODE_DEAD << STATUS_SHIFT); + } + // Create a node that has an associated key that is identified by "key_id". + static PatriciaNode leaf_node(int64_t key_id) { + return PatriciaNode((NODE_LEAF << STATUS_SHIFT) | + ((key_id & KEY_ID_MASK) << KEY_ID_SHIFT)); + } + // Create a node that works as a 0/1 branch. + // If key["bit_pos"] == 0, the next node ID is "offset". + // Otherwise, the next node ID is "offset" + 1. + static PatriciaNode branch_node(uint64_t bit_pos, uint64_t offset) { + return PatriciaNode((NODE_BRANCH << STATUS_SHIFT) | + ((bit_pos & BIT_POS_MASK) << BIT_POS_SHIFT) | + ((offset & OFFSET_MASK) << OFFSET_SHIFT)); + } + // Create a node that works as a short/long branch. + // If key_size <= "bit_size", the next node ID is "offset". + // Otherwise, the next node ID is "offset" + 1. + static PatriciaNode terminal_node(uint64_t bit_size, uint64_t offset) { + return PatriciaNode((NODE_TERMINAL << STATUS_SHIFT) | + ((bit_size & BIT_SIZE_MASK) << BIT_SIZE_SHIFT) | + ((offset & OFFSET_MASK) << OFFSET_SHIFT)); + } + + // Return the node status. + uint64_t status() const { + return (value_ >> STATUS_SHIFT) & STATUS_MASK; + } + // Return the associated key ID. + int64_t key_id() const { + return (value_ >> KEY_ID_SHIFT) & KEY_ID_MASK; + } + // Return the offset to the next nodes. + uint64_t offset() const { + return (value_ >> OFFSET_SHIFT) & OFFSET_MASK; + } + // Return the position of the branch. + uint64_t bit_pos() const { + return (value_ >> BIT_POS_SHIFT) & BIT_POS_MASK; + } + // Return the branch condition. + uint64_t bit_size() const { + return (value_ >> BIT_SIZE_SHIFT) & BIT_SIZE_MASK; + } + + private: + uint64_t value_; + + explicit PatriciaNode(uint64_t value) : value_(value) {} +}; + class PatriciaCacheEntry { public: // Create an unused entry. Modified: lib/grnxx/map/patricia.hpp (+3 -7) =================================================================== --- lib/grnxx/map/patricia.hpp 2013-08-05 15:53:42 +0900 (0a3acb3) +++ lib/grnxx/map/patricia.hpp 2013-08-05 16:00:30 +0900 (8d07738) @@ -32,21 +32,17 @@ namespace grnxx { class Storage; namespace map { -namespace patricia { - -class Node; - -} // namespace patricia template <typename T> class KeyPool; struct PatriciaHeader; +class PatriciaNode; class PatriciaCacheEntry; template <typename T> class Patricia : public Map<T> { using Header = PatriciaHeader; - using Node = patricia::Node; + using Node = PatriciaNode; using NodeArray = Array<Node, 65536, 8192>; public: @@ -96,7 +92,7 @@ class Patricia : public Map<T> { template <> class Patricia<Bytes> : public Map<Bytes> { using Header = PatriciaHeader; - using Node = patricia::Node; + using Node = PatriciaNode; using NodeArray = Array<Node, 65536, 8192>; using CacheEntry = PatriciaCacheEntry; using Cache = Array<CacheEntry>; Deleted: lib/grnxx/map/patricia/Makefile.am (+0 -11) 100644 =================================================================== --- lib/grnxx/map/patricia/Makefile.am 2013-08-05 15:53:42 +0900 (5b2868a) +++ /dev/null @@ -1,11 +0,0 @@ -noinst_LTLIBRARIES = libgrnxx_map_patricia.la - -libgrnxx_map_patricia_la_LDFLAGS = @AM_LTLDFLAGS@ - -libgrnxx_map_patricia_la_SOURCES = \ - dummy.cpp - -libgrnxx_map_patricia_includedir = ${includedir}/grnxx/map/patricia -libgrnxx_map_patricia_include_HEADERS = \ - dummy.hpp \ - node.hpp Deleted: lib/grnxx/map/patricia/dummy.cpp (+0 -28) 100644 =================================================================== --- lib/grnxx/map/patricia/dummy.cpp 2013-08-05 15:53:42 +0900 (0fa7a5d) +++ /dev/null @@ -1,28 +0,0 @@ -/* - 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 -*/ -#include "grnxx/map/patricia/dummy.hpp" - -#include "grnxx/map/patricia/node.hpp" - -namespace grnxx { -namespace map { -namespace patricia { - -} // namespace patricia -} // namespace map -} // namespace grnxx Deleted: lib/grnxx/map/patricia/dummy.hpp (+0 -31) 100644 =================================================================== --- lib/grnxx/map/patricia/dummy.hpp 2013-08-05 15:53:42 +0900 (3195d55) +++ /dev/null @@ -1,31 +0,0 @@ -/* - 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_PATRICIA_DUMMY_HPP -#define GRNXX_MAP_PATRICIA_DUMMY_HPP - -#include "grnxx/features.hpp" - -namespace grnxx { -namespace map { -namespace patricia { - -} // namespace patricia -} // namespace map -} // namespace grnxx - -#endif // GRNXX_MAP_PATRICIA_DUMMY_HPP Deleted: lib/grnxx/map/patricia/node.hpp (+0 -135) 100644 =================================================================== --- lib/grnxx/map/patricia/node.hpp 2013-08-05 15:53:42 +0900 (d3a9b53) +++ /dev/null @@ -1,135 +0,0 @@ -/* - 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_PATRICIA_NODE_HPP -#define GRNXX_MAP_PATRICIA_NODE_HPP - -#include "grnxx/features.hpp" - -#include "grnxx/bytes.hpp" -#include "grnxx/types.hpp" - -namespace grnxx { -namespace map { -namespace patricia { - -constexpr uint64_t NODE_INVALID_OFFSET = 0; - -enum NodeStatus : uint64_t { - NODE_DEAD = 0, - NODE_LEAF = 1, - NODE_BRANCH = 2, - NODE_TERMINAL = 3 -}; - -// The internal structure is as follows: -// - Common -// 62-63 ( 2): status (DEAD, LEAF, BRANCH, TERMINAL) -// - Leaf: LEAF -// 0-39 (40): key_id -// 40-61 (22): reserved -// - Branch or Terminal: BRANCH || TERMINAL -// 16-57 (42): offset -// 58-61 ( 4): reserved -// - Branch: BRANCH -// 0-15 (16): bit_pos -// - Terminal: TERMINAL -// 0-15 (16): bit_size -// where 0 is the LSB and 63 is the MSB. - -class Node { - static constexpr uint64_t STATUS_MASK = (1ULL << 2) - 1; - static constexpr uint8_t STATUS_SHIFT = 62; - - static constexpr uint64_t KEY_ID_MASK = (1ULL << 40) - 1; - static constexpr uint8_t KEY_ID_SHIFT = 0; - - static constexpr uint64_t OFFSET_MASK = (1ULL << 42) - 1; - static constexpr uint8_t OFFSET_SHIFT = 16; - - static constexpr uint64_t BIT_POS_MASK = (1ULL << 16) - 1; - static constexpr uint8_t BIT_POS_SHIFT = 0; - - static constexpr uint64_t BIT_SIZE_MASK = (1ULL << 16) - 1; - static constexpr uint8_t BIT_SIZE_SHIFT = 0; - - public: - - Node() = default; - - // Create a node that has neither descendants nor an associated key. - static Node dead_node() { - return Node((NODE_DEAD << STATUS_SHIFT)); - } - // Create a node that has an associated key that is identified by "key_id". - static Node leaf_node(int64_t key_id) { - return Node((NODE_LEAF << STATUS_SHIFT) | - ((key_id & KEY_ID_MASK) << KEY_ID_SHIFT)); - } - // Create a node that works as a 0/1 branch. - // If key["bit_pos"] == 0, the next node ID is "offset". - // Otherwise, the next node ID is "offset" + 1. - static Node branch_node(uint64_t bit_pos, uint64_t offset) { - return Node((NODE_BRANCH << STATUS_SHIFT) | - ((bit_pos & BIT_POS_MASK) << BIT_POS_SHIFT) | - ((offset & OFFSET_MASK) << OFFSET_SHIFT)); - } - // Create a node that works as a short/long branch. - // If key_size <= "bit_size", the next node ID is "offset". - // Otherwise, the next node ID is "offset" + 1. - static Node terminal_node(uint64_t bit_size, uint64_t offset) { - return Node((NODE_TERMINAL << STATUS_SHIFT) | - ((bit_size & BIT_SIZE_MASK) << BIT_SIZE_SHIFT) | - ((offset & OFFSET_MASK) << OFFSET_SHIFT)); - } - - // Return the node status. - uint64_t status() const { - return (value_ >> STATUS_SHIFT) & STATUS_MASK; - } - - // Return the associated key ID. - int64_t key_id() const { - return (value_ >> KEY_ID_SHIFT) & KEY_ID_MASK; - } - - // Return the offset to the next nodes. - uint64_t offset() const { - return (value_ >> OFFSET_SHIFT) & OFFSET_MASK; - } - - // Return the position of the branch. - uint64_t bit_pos() const { - return (value_ >> BIT_POS_SHIFT) & BIT_POS_MASK; - } - - // Return the branch condition. - uint64_t bit_size() const { - return (value_ >> BIT_SIZE_SHIFT) & BIT_SIZE_MASK; - } - - private: - uint64_t value_; - - explicit Node(uint64_t value) : value_(value) {} -}; - -} // namespace patricia -} // namespace map -} // namespace grnxx - -#endif // GRNXX_MAP_PATRICIA_NODE_HPP -------------- next part -------------- HTML����������������������������...下载
