[b8665e3] | 1 | // |
---|
| 2 | // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo |
---|
| 3 | // |
---|
| 4 | // The contents of this file are covered under the licence agreement in the |
---|
| 5 | // file "LICENCE" distributed with Cforall. |
---|
| 6 | // |
---|
| 7 | // PersistentMap.h -- |
---|
| 8 | // |
---|
| 9 | // Author : Aaron B. Moss |
---|
| 10 | // Created On : Thu Mar 7 15:50:00 2019 |
---|
| 11 | // Last Modified By : Aaron B. Moss |
---|
| 12 | // Last Modified On : Thu Mar 7 15:50:00 2019 |
---|
| 13 | // Update Count : 1 |
---|
| 14 | // |
---|
| 15 | |
---|
| 16 | #pragma once |
---|
| 17 | |
---|
| 18 | #include <cassert> // for assertf |
---|
| 19 | #include <cstddef> // for size_t |
---|
| 20 | #include <functional> // for hash, equal_to |
---|
| 21 | #include <memory> // for shared_ptr, enable_shared_from_this, make_shared |
---|
| 22 | #include <unordered_map> // for unordered_map |
---|
| 23 | #include <utility> // for forward, move |
---|
| 24 | |
---|
[fc1a3e2] | 25 | /// Wraps a hash table in a persistent data structure, using a technique based |
---|
| 26 | /// on the persistent array in Conchon & Filliatre "A Persistent Union-Find |
---|
[b8665e3] | 27 | /// Data Structure" |
---|
| 28 | |
---|
| 29 | template<typename Key, typename Val, |
---|
[fc1a3e2] | 30 | typename Hash = std::hash<Key>, typename Eq = std::equal_to<Key>> |
---|
| 31 | class PersistentMap |
---|
[b8665e3] | 32 | : public std::enable_shared_from_this<PersistentMap<Key, Val, Hash, Eq>> { |
---|
| 33 | public: |
---|
| 34 | /// Type of this class |
---|
| 35 | using Self = PersistentMap<Key, Val, Hash, Eq>; |
---|
| 36 | /// Type of pointer to this class |
---|
| 37 | using Ptr = std::shared_ptr<Self>; |
---|
| 38 | |
---|
| 39 | /// Types of version nodes |
---|
[fc1a3e2] | 40 | enum Mode { |
---|
[b8665e3] | 41 | BASE, ///< Root node of version tree |
---|
| 42 | REM, ///< Key removal node |
---|
| 43 | INS, ///< Key update node |
---|
| 44 | UPD ///< Key update node |
---|
| 45 | }; |
---|
| 46 | |
---|
| 47 | private: |
---|
| 48 | using Base = std::unordered_map<Key, Val, Hash, Eq>; |
---|
| 49 | |
---|
| 50 | /// Insertion/update node |
---|
| 51 | struct Ins { |
---|
| 52 | Ptr base; ///< Modified map |
---|
| 53 | Key key; ///< Key inserted |
---|
| 54 | Val val; ///< Value stored |
---|
| 55 | |
---|
| 56 | template<typename P, typename K, typename V> |
---|
| 57 | Ins(P&& p, K&& k, V&& v) |
---|
| 58 | : base(std::forward<P>(p)), key(std::forward<K>(k)), val(std::forward<V>(v)) {} |
---|
| 59 | }; |
---|
| 60 | |
---|
| 61 | /// Removal node |
---|
| 62 | struct Rem { |
---|
| 63 | Ptr base; ///< Modified map |
---|
| 64 | Key key; ///< Key removed |
---|
[fc1a3e2] | 65 | |
---|
[b8665e3] | 66 | template<typename P, typename K> |
---|
| 67 | Rem(P&& p, K&& k) : base(std::forward<P>(p)), key(std::forward<K>(k)) {} |
---|
| 68 | }; |
---|
| 69 | |
---|
| 70 | /// Underlying storage |
---|
| 71 | union Data { |
---|
| 72 | char def; |
---|
| 73 | Base base; |
---|
| 74 | Ins ins; |
---|
| 75 | Rem rem; |
---|
| 76 | |
---|
| 77 | Data() : def('\0') {} |
---|
| 78 | ~Data() {} |
---|
| 79 | } data; |
---|
| 80 | |
---|
| 81 | /// Type of node |
---|
| 82 | mutable Mode mode; |
---|
| 83 | |
---|
| 84 | /// get mutable reference as T |
---|
| 85 | template<typename T> |
---|
| 86 | T& as() { return reinterpret_cast<T&>(data); } |
---|
| 87 | |
---|
| 88 | /// get const reference as T |
---|
| 89 | template<typename T> |
---|
| 90 | const T& as() const { return reinterpret_cast<const T&>(data); } |
---|
| 91 | |
---|
| 92 | /// get rvalue reference as T |
---|
| 93 | template<typename T> |
---|
| 94 | T&& take_as() { return std::move(as<T>()); } |
---|
| 95 | |
---|
| 96 | /// initialize as T |
---|
| 97 | template<typename T, typename... Args> |
---|
| 98 | void init( Args&&... args ) { |
---|
| 99 | new( &as<T>() ) T { std::forward<Args>(args)... }; |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | /// reset as current mode |
---|
| 103 | void reset() { |
---|
| 104 | switch( mode ) { |
---|
| 105 | case BASE: as<Base>().~Base(); break; |
---|
| 106 | case REM: as<Rem>().~Rem(); break; |
---|
| 107 | case INS: case UPD: as<Ins>().~Ins(); break; |
---|
| 108 | } |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | /// reset as base |
---|
| 112 | void reset_as_base() { |
---|
| 113 | as<Base>().~Base(); |
---|
| 114 | } |
---|
| 115 | |
---|
| 116 | public: |
---|
[42f1279c] | 117 | using key_type = typename Base::key_type; |
---|
| 118 | using mapped_type = typename Base::mapped_type; |
---|
| 119 | using value_type = typename Base::value_type; |
---|
| 120 | using size_type = typename Base::size_type; |
---|
| 121 | using difference_type = typename Base::difference_type; |
---|
[b8665e3] | 122 | using iterator = typename Base::const_iterator; |
---|
| 123 | |
---|
| 124 | PersistentMap() : data(), mode(BASE) { init<Base>(); } |
---|
| 125 | |
---|
| 126 | PersistentMap( Base&& b ) : data(), mode(BASE) { init<Base>(std::move(b)); } |
---|
| 127 | |
---|
| 128 | PersistentMap( const Self& o ) = delete; |
---|
| 129 | |
---|
| 130 | Self& operator= ( const Self& o ) = delete; |
---|
| 131 | |
---|
| 132 | ~PersistentMap() { reset(); } |
---|
| 133 | |
---|
| 134 | /// Create a pointer to a new, empty persistent map |
---|
| 135 | static Ptr new_ptr() { return std::make_shared<Self>(); } |
---|
| 136 | |
---|
| 137 | /// reroot persistent map at current node |
---|
| 138 | void reroot() const { |
---|
| 139 | // recursive base case |
---|
| 140 | if ( mode == BASE ) return; |
---|
| 141 | |
---|
| 142 | // reroot base |
---|
| 143 | Self* mut_this = const_cast<Self*>(this); |
---|
| 144 | Ptr base = ( mode == REM ) ? mut_this->as<Rem>().base : mut_this->as<Ins>().base; |
---|
| 145 | base->reroot(); |
---|
| 146 | |
---|
| 147 | // remove map from base |
---|
[1febef62] | 148 | Base base_map = base->template take_as<Base>(); |
---|
[181a6af] | 149 | base->reset_as_base(); |
---|
[b8665e3] | 150 | |
---|
| 151 | // switch base to inverse of self and mutate base map |
---|
| 152 | switch ( mode ) { |
---|
| 153 | case REM: { |
---|
| 154 | Rem& self = mut_this->as<Rem>(); |
---|
| 155 | auto it = base_map.find( self.key ); |
---|
| 156 | |
---|
[fc1a3e2] | 157 | base->template init<Ins>( |
---|
[fdae913] | 158 | mut_this->shared_from_this(), std::move(self.key), std::move(it->second) ); |
---|
[181a6af] | 159 | base->mode = INS; |
---|
[b8665e3] | 160 | |
---|
| 161 | base_map.erase( it ); |
---|
| 162 | break; |
---|
| 163 | } |
---|
| 164 | case INS: { |
---|
| 165 | Ins& self = mut_this->as<Ins>(); |
---|
| 166 | |
---|
[1febef62] | 167 | base->template init<Rem>( mut_this->shared_from_this(), self.key ); |
---|
[181a6af] | 168 | base->mode = REM; |
---|
[b8665e3] | 169 | |
---|
| 170 | base_map.emplace( std::move(self.key), std::move(self.val) ); |
---|
| 171 | break; |
---|
| 172 | } |
---|
| 173 | case UPD: { |
---|
| 174 | Ins& self = mut_this->as<Ins>(); |
---|
| 175 | auto it = base_map.find( self.key ); |
---|
| 176 | |
---|
[fc1a3e2] | 177 | base->template init<Ins>( |
---|
[fdae913] | 178 | mut_this->shared_from_this(), std::move(self.key), std::move(it->second) ); |
---|
[181a6af] | 179 | base->mode = UPD; |
---|
[b8665e3] | 180 | |
---|
| 181 | it->second = std::move(self.val); |
---|
| 182 | break; |
---|
| 183 | } |
---|
| 184 | case BASE: assertf(false, "unreachable"); break; |
---|
| 185 | } |
---|
| 186 | |
---|
| 187 | // set base map into self |
---|
| 188 | mut_this->reset(); |
---|
| 189 | mut_this->init<Base>( std::move(base_map) ); |
---|
| 190 | mode = BASE; |
---|
| 191 | } |
---|
| 192 | |
---|
| 193 | private: |
---|
| 194 | /// the base after rerooting at the current node |
---|
| 195 | const Base& rerooted() const { |
---|
| 196 | reroot(); |
---|
| 197 | return as<Base>(); |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | public: |
---|
| 201 | /// true iff the map is empty |
---|
| 202 | bool empty() const { return rerooted().empty(); } |
---|
| 203 | |
---|
| 204 | /// number of entries in map |
---|
| 205 | size_type size() const { return rerooted().size(); } |
---|
| 206 | |
---|
| 207 | /// begin iterator for map; may be invalidated by calls to non-iteration functions |
---|
| 208 | /// or functions on other maps in the same tree |
---|
| 209 | iterator begin() const { return rerooted().begin(); } |
---|
| 210 | |
---|
| 211 | /// end iterator for map; may be invalidated by calls to non-iteration functions |
---|
| 212 | /// or functions on other maps in the same tree |
---|
| 213 | iterator end() const { return rerooted().end(); } |
---|
| 214 | |
---|
| 215 | /// underlying map iterator for value |
---|
| 216 | iterator find(const Key& k) const { return rerooted().find( k ); } |
---|
| 217 | |
---|
| 218 | /// check if value is present |
---|
| 219 | size_type count(const Key& k) const { return rerooted().count( k ); } |
---|
| 220 | |
---|
| 221 | /// get value; undefined behaviour if not present |
---|
| 222 | const Val& get(const Key& k) const { |
---|
| 223 | const Base& self = rerooted(); |
---|
| 224 | auto it = self.find( k ); |
---|
| 225 | return it->second; |
---|
| 226 | } |
---|
| 227 | |
---|
| 228 | /// get value; returns default if not present |
---|
| 229 | template<typename V> |
---|
| 230 | Val get_or_default(const Key& k, V&& d) const { |
---|
| 231 | const Base& self = rerooted(); |
---|
| 232 | auto it = self.find( k ); |
---|
| 233 | if ( it == self.end() ) return d; |
---|
| 234 | else return it->second; |
---|
| 235 | } |
---|
| 236 | |
---|
| 237 | /// set value, storing new map in output variable |
---|
| 238 | template<typename K, typename V> |
---|
| 239 | Ptr set(K&& k, V&& v) { |
---|
| 240 | reroot(); |
---|
| 241 | |
---|
| 242 | // transfer map to new node |
---|
| 243 | Ptr ret = std::make_shared<Self>( take_as<Base>() ); |
---|
[181a6af] | 244 | reset_as_base(); |
---|
[1febef62] | 245 | Base& base_map = ret->template as<Base>(); |
---|
[b8665e3] | 246 | |
---|
| 247 | // check if this is update or insert |
---|
| 248 | auto it = base_map.find( k ); |
---|
| 249 | if ( it == base_map.end() ) { |
---|
[181a6af] | 250 | // set self to REM node and insert into base |
---|
| 251 | init<Rem>( ret, k ); |
---|
| 252 | mode = REM; |
---|
[b8665e3] | 253 | |
---|
| 254 | base_map.emplace_hint( it, std::forward<K>(k), std::forward<V>(v) ); |
---|
| 255 | } else { |
---|
[181a6af] | 256 | // set self to UPD node and modify base |
---|
| 257 | init<Ins>( ret, std::forward<K>(k), std::move(it->second) ); |
---|
| 258 | mode = UPD; |
---|
[b8665e3] | 259 | |
---|
| 260 | it->second = std::forward<V>(v); |
---|
| 261 | } |
---|
| 262 | |
---|
| 263 | return ret; |
---|
| 264 | } |
---|
| 265 | |
---|
| 266 | /// remove value, storing new map in output variable; does nothing if key not in map |
---|
| 267 | Ptr erase(const Key& k) { |
---|
| 268 | reroot(); |
---|
[fc1a3e2] | 269 | |
---|
[b8665e3] | 270 | // exit early if key does not exist in map |
---|
| 271 | if ( ! as<Base>().count( k ) ) return this->shared_from_this(); |
---|
| 272 | |
---|
| 273 | // transfer map to new node |
---|
| 274 | Ptr ret = std::make_shared<Self>( take_as<Base>() ); |
---|
[181a6af] | 275 | reset_as_base(); |
---|
[1febef62] | 276 | Base& base_map = ret->template as<Base>(); |
---|
[b8665e3] | 277 | |
---|
[181a6af] | 278 | // set self to INS node and remove from base |
---|
| 279 | init<Ins>( ret, k, base_map[k] ); |
---|
| 280 | mode = INS; |
---|
[b8665e3] | 281 | |
---|
| 282 | base_map.erase( k ); |
---|
| 283 | |
---|
| 284 | return ret; |
---|
| 285 | } |
---|
| 286 | }; |
---|
| 287 | |
---|
| 288 | // Local Variables: // |
---|
| 289 | // tab-width: 4 // |
---|
| 290 | // mode: c++ // |
---|
| 291 | // compile-command: "make install" // |
---|
| 292 | // End: // |
---|