monotone

monotone Mtn Source Tree

Root/src/cow_trie.hh

1// Copyright 2010 Timothy Brownawell <tbrownaw@prjek.net>
2// You may use, copy, modify, distribute, etc, this file with no other
3// restriction than that this notice not be removed.
4
5#include <boost/shared_ptr.hpp>
6#include <vector>
7
8// This is *NOT* a normal STL-compatible container! It pretends well enough
9// to work with parallel_iter and such, but it does not have find(),
10// insert(), erase().
11//
12// Because this is copy-on-write, and the copying is per-node instead of for
13// the whole object, the nodes can not have parent pointers (also, having
14// parent pointers would I think make the size 2^n+4 instead of 2^n, which
15// AIUI would waste almost equal space with common memory allocators).
16// This lack of parent pointers means that iterators are expensive, so they're
17// not used except for, well, iteration.
18
19template<typename _Key, typename _Value, int _Bits>
20class cow_trie
21{
22public:
23 typedef _Key key_type;
24 //typedef _Value value_type;
25 typedef std::pair<_Key, _Value> value_type;
26private:
27 enum { mask = (1<<_Bits)-1 };
28 enum { levels = (sizeof(_Key) * 8 + _Bits - 1) / _Bits };
29
30 struct middle_node_type
31 {
32 boost::shared_ptr<void> contents[(1<<_Bits)];
33 };
34 struct leaf_node_type
35 {
36 _Value contents[1<<_Bits];
37 };
38
39 _Value _empty_value;
40 unsigned _count;
41 boost::shared_ptr<void> _data;
42
43 bool walk(boost::shared_ptr<void> & d, _Key key, int level, _Value **ret)
44 {
45 if (!d)
46 {
47if (level > 0)
48 d.reset(new middle_node_type());
49else
50 d.reset(new leaf_node_type());
51 }
52 if (!d.unique())
53 {
54if (level > 0)
55 d.reset(new middle_node_type(*boost::static_pointer_cast<middle_node_type>(d)));
56else
57 d.reset(new leaf_node_type(*boost::static_pointer_cast<leaf_node_type>(d)));
58 }
59 unsigned idx = (key >> (_Bits * level)) & mask;
60 if (level > 0)
61 return walk(boost::static_pointer_cast<middle_node_type>(d)->contents[idx],
62 key, level-1, ret);
63 else
64 {
65*ret = &boost::static_pointer_cast<leaf_node_type>(d)->contents[idx];
66return true;
67 }
68 }
69
70 bool walk(boost::shared_ptr<void> const & d, _Key key, int level, _Value **ret) const
71 {
72 if (!d)
73 {
74return false;
75 }
76 unsigned idx = (key >> (_Bits * level)) & mask;
77 if (level > 0)
78 return walk(boost::static_pointer_cast<middle_node_type>(d)->contents[idx],
79 key, level-1, ret);
80 else
81 {
82*ret = &boost::static_pointer_cast<leaf_node_type>(d)->contents[idx];
83return true;
84 }
85 }
86public:
87 cow_trie() : _count(0) { }
88 unsigned size() const { return _count; }
89 bool empty() const { return _count == 0; }
90 void clear()
91 {
92 _count = 0;
93 _data.reset();
94 }
95 _Value const & set(_Key key, _Value const & value) {
96 _Value *p;
97 walk(_data, key, levels-1, &p);
98 bool b = (*p != _empty_value);
99 bool a = (value != _empty_value);
100 if (b && !a)
101 --_count;
102 else if (a && !b)
103 ++_count;
104 *p = value;
105 return *p;
106 }
107 bool set_if_missing(_Key key, _Value const & value)
108 {
109 _Value *p;
110 walk(_data, key, levels-1, &p);
111 if (*p != _empty_value)
112 return false;
113 if (value != _empty_value)
114 {
115++_count;
116*p = value;
117 }
118 return true;
119 }
120 void unset(_Key key) {
121 set(key, _empty_value);
122 }
123 _Value const &get_if_present(_Key key) const {
124 _Value *p;
125 if (walk(_data, key, levels-1, &p))
126 return *p;
127 else
128 return _empty_value;
129 }
130 // This is actually not the same as above.
131 // It's non-const, so it calls the other walk().
132 _Value const &get_unshared_if_present(_Key key)
133 {
134 _Value *p;
135 if (walk(_data, key, levels-1, &p))
136 return *p;
137 else
138 return _empty_value;
139 }
140
141 class const_iterator
142 {
143 struct stack_item
144 {
145 boost::shared_ptr<void> ptr;
146 unsigned idx;
147 bool operator==(stack_item const & other) const
148 {
149return ptr == other.ptr && idx == other.idx;
150 }
151 };
152 std::vector<stack_item> stack;
153 friend class cow_trie;
154 explicit const_iterator(cow_trie const & t)
155 {
156 if (t._data)
157{
158 stack_item item;
159 item.ptr = t._data;
160 item.idx = (unsigned)-1;
161 stack.push_back(item);
162 ++(*this);
163}
164 }
165 _Value _empty_value;
166 private:
167 value_type _ret;
168 public:
169 bool operator==(const_iterator const & other)
170 {
171 return stack == other.stack;
172 }
173 bool operator!=(const_iterator const & other)
174 {
175 return stack != other.stack;
176 }
177 const_iterator() { }
178 const_iterator const & operator++()
179 {
180 while (!stack.empty())
181{
182 stack_item & item = stack.back();
183 boost::shared_ptr<middle_node_type> middle
184 = boost::static_pointer_cast<middle_node_type>(item.ptr);
185 boost::shared_ptr<leaf_node_type> leaf
186 = boost::static_pointer_cast<leaf_node_type>(item.ptr);
187 for (++item.idx; item.idx < (1<<_Bits); ++item.idx)
188 {
189 if (stack.size() == levels)
190{
191 if (leaf->contents[item.idx] != _empty_value)
192 {
193 _ret.first = (_ret.first & ~mask) | item.idx;
194 _ret.second = leaf->contents[item.idx];
195 return *this;
196 }
197}
198 else
199{
200 if (middle->contents[item.idx])
201 {
202 int shifts = levels - stack.size();
203 int bits = shifts * _Bits;
204 _ret.first = (_ret.first & ~(mask<<bits)) | (item.idx<<bits);
205 stack_item i;
206 i.ptr = middle->contents[item.idx];
207 i.idx = (unsigned)-1;
208 stack.push_back(i);
209 break;
210 }
211}
212 }
213 if (item.idx == (1 << _Bits))
214 stack.pop_back();
215}
216 return *this;
217 }
218 value_type const & operator*() const
219 {
220 return _ret;
221 }
222 value_type const * operator->() const
223 {
224 return &_ret;
225 }
226 };
227 friend class const_iterator;
228
229 const_iterator begin() const { return const_iterator(*this); }
230 const_iterator end() const { return const_iterator(); }
231};
232
233
234// Local Variables:
235// mode: C++
236// fill-column: 76
237// c-file-style: "gnu"
238// indent-tabs-mode: nil
239// End:
240// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status