null+****@clear*****
null+****@clear*****
2011年 6月 22日 (水) 14:41:06 JST
Susumu Yata 2011-06-22 05:41:06 +0000 (Wed, 22 Jun 2011)
New Revision: e3508789b012344bf6922bddaa012c9266dddb1e
Log:
replaced #defines with const objects, updated grn::dat::IdCursor, and fixed grn::dat::CommonPrefixSearchCursor.
Modified files:
lib/dat/common-prefix-search-cursor.cpp
lib/dat/common-prefix-search-cursor.hpp
lib/dat/dat.hpp
lib/dat/header.hpp
lib/dat/id-cursor.cpp
lib/dat/id-cursor.hpp
lib/dat/trie.hpp
Modified: lib/dat/common-prefix-search-cursor.cpp (+9 -2)
===================================================================
--- lib/dat/common-prefix-search-cursor.cpp 2011-06-22 00:41:03 +0000 (64dc032)
+++ lib/dat/common-prefix-search-cursor.cpp 2011-06-22 05:41:06 +0000 (b453639)
@@ -10,7 +10,8 @@ void CommonPrefixSearchCursor::open(const Trie &trie,
UInt32 min_length,
UInt32 max_length,
UInt32 offset,
- UInt32 limit) {
+ UInt32 limit,
+ bool is_ascending) {
GRN_DAT_PARAM_ERROR_IF((ptr == NULL) && (max_length != 0));
GRN_DAT_PARAM_ERROR_IF(min_length > max_length);
@@ -19,6 +20,7 @@ void CommonPrefixSearchCursor::open(const Trie &trie,
trie_ = ≜
buf_.clear();
count_ = 0;
+ is_ascending_ = is_ascending;
if ((limit == 0) || (offset > (max_length - min_length))) {
return;
}
@@ -85,13 +87,18 @@ void CommonPrefixSearchCursor::close() {
trie_ = NULL;
buf_.clear();
count_ = 0;
+ is_ascending_ = false;
}
bool CommonPrefixSearchCursor::next(Key *key) {
if (count_ >= buf_.size()) {
return false;
}
- trie_->ith_key(buf_[count_++], key);
+ if (is_ascending_) {
+ trie_->ith_key(buf_[count_++], key);
+ } else {
+ trie_->ith_key(buf_[buf_.size() - ++count_], key);
+ }
return true;
}
Modified: lib/dat/common-prefix-search-cursor.hpp (+5 -2)
===================================================================
--- lib/dat/common-prefix-search-cursor.hpp 2011-06-22 00:41:03 +0000 (59c0291)
+++ lib/dat/common-prefix-search-cursor.hpp 2011-06-22 05:41:06 +0000 (eaf3b32)
@@ -14,7 +14,8 @@ class CommonPrefixSearchCursor : public Cursor {
CommonPrefixSearchCursor()
: trie_(NULL),
buf_(),
- count_(0) {}
+ count_(0),
+ is_ascending_(false) {}
~CommonPrefixSearchCursor() {}
void open(const Trie &trie,
@@ -22,7 +23,8 @@ class CommonPrefixSearchCursor : public Cursor {
UInt32 min_length,
UInt32 max_length,
UInt32 offset,
- UInt32 limit);
+ UInt32 limit,
+ bool is_ascending = false);
void close();
@@ -32,6 +34,7 @@ class CommonPrefixSearchCursor : public Cursor {
const Trie *trie_;
std::vector<UInt32> buf_;
UInt32 count_;
+ bool is_ascending_;
// Disallows copy and assignment.
CommonPrefixSearchCursor(const CommonPrefixSearchCursor &);
Modified: lib/dat/dat.hpp (+56 -33)
===================================================================
--- lib/dat/dat.hpp 2011-06-22 00:41:03 +0000 (753ecd8)
+++ lib/dat/dat.hpp 2011-06-22 05:41:06 +0000 (75520b4)
@@ -27,39 +27,62 @@ typedef ::uint32_t UInt32;
typedef ::uint64_t UInt64;
#endif // _MSC_VER
-enum {
- // The special label attached to a terminal node.
- TERMINAL_LABEL = 0x100,
-
- LABEL_MASK = 0x1FF,
- BLOCK_MASK = 0x1FF,
-
- // The number of nodes in each block.
- BLOCK_SIZE = 0x200,
-
- ROOT_NODE_ID = 0,
- KEY_ID_OFFSET = 1,
-
- MAX_LABEL = TERMINAL_LABEL,
- MAX_NODE_ID = 0x7FFFFFFF,
- MAX_BLOCK_ID = MAX_NODE_ID / BLOCK_SIZE,
- MAX_OFFSET = MAX_NODE_ID,
- MAX_KEY_ID = MAX_NODE_ID,
- MAX_KEY_LENGTH = 0x7FFF,
- // The level of a block is incremented when find_offset() has failed to find
- // a good offset in that block MAX_FAIL_COUNT times.
- MAX_FAIL_COUNT = 4,
- // The maximum number of blocks tested in each call of find_offset().
- MAX_BLOCK_COUNT = 16,
- // A higher level block has less phantom nodes.
- MAX_BLOCK_LEVEL = 5,
-
- INVALID_LABEL = 0x1FF,
- INVALID_OFFSET = 0,
- INVALID_ENTRY = 0x7FFFFFFF,
-
- SORT_THRESHOLD = 10
-};
+#ifndef UINT8_MAX
+const UInt8 UINT8_MAX = static_cast<UInt8>(0xFFU);
+#endif // UINT8_MAX
+
+#ifndef UINT8_MAX
+const UInt16 UINT16_MAX = static_cast<UInt16>(0xFFFFU);
+#endif // UINT16_MAX
+
+#ifndef UINT8_MAX
+const UInt32 UINT32_MAX = static_cast<UInt32>(0xFFFFFFFFU);
+#endif // UINT32_MAX
+
+#ifndef UINT8_MAX
+const UInt64 UINT64_MAX = static_cast<UInt64>(0xFFFFFFFFFFFFFFFFULL);
+#endif // UINT64_MAX
+
+// The special label attached to a terminal node.
+const UInt16 TERMINAL_LABEL = 0x100;
+const UInt32 LABEL_MASK = 0x1FF;
+const UInt32 BLOCK_MASK = 0x1FF;
+
+const UInt32 BLOCK_SIZE = 0x200;
+
+const UInt32 ROOT_NODE_ID = 0;
+const UInt32 KEY_ID_OFFSET = 1;
+
+const UInt16 MAX_LABEL = TERMINAL_LABEL;
+const UInt32 MAX_NODE_ID = 0x7FFFFFFF;
+const UInt32 MAX_BLOCK_ID = MAX_NODE_ID / BLOCK_SIZE;
+const UInt32 MAX_OFFSET = MAX_NODE_ID;
+const UInt32 MAX_KEY_ID = MAX_NODE_ID;
+const UInt32 MAX_KEY_LENGTH = 0x7FFF;
+
+// The level of a block is incremented when find_offset() has failed to find
+// a good offset in that block MAX_FAIL_COUNT times.
+const UInt32 MAX_FAIL_COUNT = 4;
+
+// The maximum number of blocks tested in each call of find_offset().
+const UInt32 MAX_BLOCK_COUNT = 16;
+// A higher level block has less phantom nodes.
+const UInt32 MAX_BLOCK_LEVEL = 5;
+
+const UInt32 INVALID_LABEL = 0x1FF;
+const UInt32 INVALID_OFFSET = 0;
+const UInt32 INVALID_ENTRY = 0x7FFFFFFF;
+const UInt32 INVALID_NODE_ID = MAX_NODE_ID + 1;
+const UInt32 INVALID_KEY_ID = 0;
+
+const UInt32 DEFAULT_FILE_SIZE = 1U << 20;
+const double DEFAULT_NUM_NODES_PER_KEY = 4.0;
+const double DEFAULT_AVERAGE_KEY_LENGTH = 16.0;
+
+const UInt32 MAX_NUM_NODES = MAX_NODE_ID + 1;
+const UInt32 MAX_NUM_BLOCKS = MAX_BLOCK_ID + 1;
+const UInt32 MAX_NUM_KEYS = MAX_KEY_ID + 1;
+const UInt32 MAX_KEY_BUF_SIZE = 0xFFFFFFFFU;
class Exception : public std::exception {
public:
Modified: lib/dat/header.hpp (+1 -1)
===================================================================
--- lib/dat/header.hpp 2011-06-22 00:41:03 +0000 (e7905a5)
+++ lib/dat/header.hpp 2011-06-22 05:41:06 +0000 (9afce29)
@@ -18,7 +18,7 @@ class Header {
max_num_blocks_(0),
key_buf_size_(0),
entries_() {
- for (int i = 0; i <= MAX_BLOCK_LEVEL; ++i) {
+ for (UInt32 i = 0; i <= MAX_BLOCK_LEVEL; ++i) {
entries_[i] = INVALID_ENTRY;
}
}
Modified: lib/dat/id-cursor.cpp (+14 -6)
===================================================================
--- lib/dat/id-cursor.cpp 2011-06-22 00:41:03 +0000 (c9869bc)
+++ lib/dat/id-cursor.cpp 2011-06-22 05:41:06 +0000 (e5c086d)
@@ -43,8 +43,8 @@ bool IdCursor::next(Key *key) {
if (cur_ == end_) {
return false;
}
- cur_ += step_;
trie_->ith_key(cur_, key);
+ cur_ += step_;
return true;
}
@@ -68,19 +68,27 @@ void IdCursor::open(const Trie &trie,
--max_id;
}
- // Overflow and underflow...
+ if (max_id < min_id) {
+ return;
+ }
+ const UInt32 diff = max_id - min_id;
+ if (diff < offset) {
+ return;
+ }
+ if (limit > (diff - offset)) {
+ limit = diff - offset + 1;
+ }
+
if (is_ascending) {
min_id += offset;
- max_id -= limit;
- ++max_id;
+ max_id = min_id + limit;
if (min_id < max_id) {
cur_ = min_id;
end_ = max_id;
}
} else {
- min_id += limit;
max_id -= offset;
- --min_id;
+ min_id = max_id - limit;
if (min_id < max_id) {
cur_ = max_id;
end_ = min_id;
Modified: lib/dat/id-cursor.hpp (+0 -2)
===================================================================
--- lib/dat/id-cursor.hpp 2011-06-22 00:41:03 +0000 (4697c36)
+++ lib/dat/id-cursor.hpp 2011-06-22 05:41:06 +0000 (6239780)
@@ -44,8 +44,6 @@ class IdCursor : public Cursor {
bool ignores_min = false,
bool ignores_max = false);
- static const UInt32 INVALID_KEY_ID = 0;
-
// Disallows copy and assignment.
IdCursor(const IdCursor &);
IdCursor &operator=(const IdCursor &);
Modified: lib/dat/trie.hpp (+0 -9)
===================================================================
--- lib/dat/trie.hpp 2011-06-22 00:41:03 +0000 (ce2f945)
+++ lib/dat/trie.hpp 2011-06-22 05:41:06 +0000 (89ed399)
@@ -13,15 +13,6 @@ namespace dat {
class Trie {
public:
- static const UInt32 DEFAULT_FILE_SIZE = 1U << 20;
- static const double DEFAULT_NUM_NODES_PER_KEY = 4.0;
- static const double DEFAULT_AVERAGE_KEY_LENGTH = 16.0;
-
- static const UInt32 MAX_NUM_NODES = (UInt32)MAX_NODE_ID + 1;
- static const UInt32 MAX_NUM_BLOCKS = (UInt32)MAX_BLOCK_ID + 1;
- static const UInt32 MAX_NUM_KEYS = (UInt32)MAX_KEY_ID + 1;
- static const UInt32 MAX_KEY_BUF_SIZE = 0xFFFFFFFFU;
-
Trie();
~Trie();