libutil++  1.9.3
 All Classes Functions Variables
CedarTrie.h
1 /*
2 ** libutil++
3 ** $Id: CedarTrie.h 1652 2016-02-28 19:36:07Z sella $
4 ** Copyright (c) 2011-2016 Digital Genesis, LLC. All Rights Reserved.
5 ** Released under the LGPL Version 2.1 License.
6 ** http://www.digitalgenesis.com
7 */
8 
9 #ifndef __libutilxx__sella__container__CedarTrie_H__
10 #define __libutilxx__sella__container__CedarTrie_H__
11 
12 #include "../../common.h"
13 #include "ContainerException.h"
14 
15 #define SUPPRESS_CEDAR_ASSERT
16 
17 #ifdef USE_PREFIX_TRIE
18  #include "cedarpp.h" /* Prefix Trie */
19 #elif defined USE_REDUCED_TRIE
20  #include "cedar.h"
21 #else
22  #include "cedar.h"
23 #endif
24 
25 #include <stdarg.h>
26 
27 namespace sella {
28  namespace container {
29  template <typename V> /* Cedar requires that V must be 4 bytes (int32_t) or less. */
30  class CedarTrie {
31  public:
32  typedef V value_t;
33 #ifdef USE_ORDERED_TRIE
34  typedef cedar::da<value_t, cedar::NaN<value_t>::N1, cedar::NaN<value_t>::N2, true> trie_t;
35 #else
36  typedef cedar::da<value_t, cedar::NaN<value_t>::N1, cedar::NaN<value_t>::N2, false> trie_t;
37 #endif
38  typedef std::shared_ptr<CedarTrie<value_t>> shared;
39 
40  public:
41  CedarTrie() throw () {
42  static_assert(sizeof(value_t) <= 4, "CedarTrie requires that V must be 4 bytes (int32_t) or less");
43  }
44 
45  void insert(const std::string &key, const value_t &value) throw () {
46  trie.update(key.data(), key.size(), value);
47  }
48 
49  void insert(const char *key, size_t len, const value_t &value) throw () {
50  trie.update(key, len, value);
51  }
52 
53  void insert(const char *key, const value_t &value) throw () {
54  trie.update(key, ::strlen(key), value);
55  }
56 
57  void insert(const uint8_t *key, size_t len, const value_t &value) throw () {
58  trie.update((const char*) key, len, value);
59  }
60 
61  int remove(const std::string &key) throw () {
62  return trie.erase(key.data(), key.size(), 0);
63  }
64 
65  int remove(const char *key) throw () {
66  return trie.erase(key, ::strlen(key), 0);
67  }
68 
69  int remove(const char *key, size_t len) throw () {
70  return trie.erase(key, len, 0);
71  }
72 
73  int remove(const uint8_t *key, size_t len) throw () {
74  return trie.erase((const char*) key, len, 0);
75  }
76 
77  bool lookup(const char *key, size_t len, value_t &value) throw () {
78  typename trie_t::result_triple_type result_triple[1] = { 0, 0, 0 };
79 
80  if (trie.commonPrefixPredict(key, result_triple, 1, len, 0) > 0) {
81  if (result_triple[0].length == 0) { /* Exact match */
82  value = result_triple[0].value;
83 
84  return true;
85  }
86  }
87 
88  return false;
89  }
90 
91  bool lookup(const std::string &key, value_t &value) throw () {
92  return lookup(key.data(), key.size(), value);
93  }
94 
95  bool lookup(const uint8_t *key, size_t len, value_t &value) throw () {
96  return lookup((const char*) key, len, value);
97  }
98 
99  bool lookup(const std::string &prefix, std::vector<std::pair<std::string, value_t>> &values) throw () {
100  typename trie_t::result_triple_type* result_triple = new typename trie_t::result_triple_type[64];
101  size_t count;
102 
103  if ((count = trie.commonPrefixPredict(prefix.data(), result_triple, 64, prefix.size(), 0)) > 0) {
104  if (count > 64) { /* Allocate more room */
105  delete result_triple;
106 
107  result_triple = new typename trie_t::result_triple_type[count];
108 
109  if ((count = trie.commonPrefixPredict(prefix.data(), result_triple, count, prefix.size(), 0)) < 1) {
110  delete result_triple;
111 
112  return false;
113  }
114  }
115 
116  values.reserve(count);
117 
118  for (size_t i = 0; i < count; i++) {
119  char suffix[256];
120 
121  trie.suffix(suffix, result_triple[0].length, result_triple[0].id);
122  values.push_back(std::make_pair(prefix + suffix, result_triple[0].value));
123  }
124 
125  delete result_triple;
126 
127  return true;
128  }
129 
130  return false;
131  }
132 
133  value_t at(const std::string &key) throw (ContainerException) {
134  return at(key.data(), key.size());
135  }
136 
137  value_t at(const char *key) throw (ContainerException) {
138  return at(key, ::strlen(key));
139  }
140 
141  value_t at(const char *key, size_t len) throw (ContainerException) {
142  value_t v;
143 
144  if (!lookup(key, len, v)) {
145  THROW(ContainerException, "key %s not found", std::string(key, len).c_str());
146  }
147 
148  return v;
149  }
150 
151  value_t at(const uint8_t *key, size_t len) throw (ContainerException) {
152  return ((const char*) key, len);
153  }
154 
155  const value_t& operator[](const std::string &key) const throw (ContainerException) {
156  return trie.update(key.data(), key.size());
157  }
158 
159  const value_t& operator[](const char *key) const throw (ContainerException) {
160  return trie.update(key, ::strlen(key));
161  }
162 
163  value_t& operator[](const std::string &key) throw (ContainerException) {
164  return trie.update(key.data(), key.size());
165  }
166 
167  value_t& operator[](const char *key) throw (ContainerException) {
168  return trie.update(key, ::strlen(key));
169  }
170 
171  bool contains(const std::string &key) throw () {
172  value_t v;
173 
174  return lookup(key, v);
175  }
176 
177  bool contains(const char *key) throw () {
178  value_t v;
179 
180  return lookup(key, ::strlen(key), v);
181  }
182 
183  bool contains(const char *key, size_t len) throw () {
184  value_t v;
185 
186  return lookup(key, len, v);
187  }
188 
189  size_t capacity(void) const {
190  return trie.capacity();
191  }
192 
193  size_t size(void) const {
194  return trie.size();
195  }
196 
197  size_t total_size(void) const {
198  return trie.total_size();
199  }
200 
201  size_t unit_size(void) const {
202  return trie.unit_size();
203  }
204 
205  size_t nonzero_size(void) const {
206  return trie.nonzero_size();
207  }
208 
209  size_t num_keys(void) const {
210  return trie.num_keys();
211  }
212 
213  bool empty(void) const throw () {
214  return (trie.num_keys() == 0);
215  }
216 
217  void clear(void) throw () {
218  trie.clear(true);
219  }
220 
221  private:
222  trie_t trie;
223  };
224 
225  }
226 };
227 
228 #endif
229 
230 /*
231 ** vim: noet ts=3 sw=3
232 */
Generated on Sat Sep 2 2017 11:44:21 for libutil++ by   doxygen 1.8.5