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 19 template<typename _Key, typename _Value, int _Bits> 20 class cow_trie 21 { 22 public: 23 typedef _Key key_type; 24 //typedef _Value value_type; 25 typedef std::pair<_Key, _Value> value_type; 26 private: 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 walk(boost::shared_ptr<void> & d,_Key key,int level,_Value ** ret)43 bool walk(boost::shared_ptr<void> & d, _Key key, int level, _Value **ret) 44 { 45 if (!d) 46 { 47 if (level > 0) 48 d.reset(new middle_node_type()); 49 else 50 d.reset(new leaf_node_type()); 51 } 52 if (!d.unique()) 53 { 54 if (level > 0) 55 d.reset(new middle_node_type(*boost::static_pointer_cast<middle_node_type>(d))); 56 else 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]; 66 return true; 67 } 68 } 69 walk(boost::shared_ptr<void> const & d,_Key key,int level,_Value ** ret) const70 bool walk(boost::shared_ptr<void> const & d, _Key key, int level, _Value **ret) const 71 { 72 if (!d) 73 { 74 return 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]; 83 return true; 84 } 85 } 86 public: cow_trie()87 cow_trie() : _count(0) { } size() const88 unsigned size() const { return _count; } empty() const89 bool empty() const { return _count == 0; } clear()90 void clear() 91 { 92 _count = 0; 93 _data.reset(); 94 } set(_Key key,_Value const & value)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 } set_if_missing(_Key key,_Value const & value)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 } unset(_Key key)120 void unset(_Key key) { 121 set(key, _empty_value); 122 } get_if_present(_Key key) const123 _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(). get_unshared_if_present(_Key key)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; operator ==cow_trie::const_iterator::stack_item147 bool operator==(stack_item const & other) const 148 { 149 return ptr == other.ptr && idx == other.idx; 150 } 151 }; 152 std::vector<stack_item> stack; 153 friend class cow_trie; const_iterator(cow_trie const & t)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: operator ==(const_iterator const & other)169 bool operator==(const_iterator const & other) 170 { 171 return stack == other.stack; 172 } operator !=(const_iterator const & other)173 bool operator!=(const_iterator const & other) 174 { 175 return stack != other.stack; 176 } const_iterator()177 const_iterator() { } operator ++()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 } operator *() const218 value_type const & operator*() const 219 { 220 return _ret; 221 } operator ->() const222 value_type const * operator->() const 223 { 224 return &_ret; 225 } 226 }; 227 friend class const_iterator; 228 begin() const229 const_iterator begin() const { return const_iterator(*this); } end() const230 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: 241