source: src/Common/PersistentMap.h@ 6fa409e

new-env
Last change on this file since 6fa409e was d318a18, checked in by Aaron Moss <a3moss@…>, 7 years ago

Fix assorted memory bugs with persistent-array environment
  • Property mode set to 100644
File size: 12.1 KB
Line 
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 : Wed Jun 13 16:31:00 2018
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Wed Jun 13 16:31:00 2018
13// Update Count : 1
14//
15
16#pragma once
17
18#include <cassert>
19#include <cstddef>
20#include <functional>
21#include <unordered_map>
22#include <utility>
23
24#include "GC.h"
25
26/// Wraps a hash table in a persistent data structure, using a technique based
27/// on the persistent array in Conchon & Filliatre "A Persistent Union-Find
28/// Data Structure"
29
30template<typename Key, typename Val,
31 typename Hash = std::hash<Key>, typename Eq = std::equal_to<Key>>
32class PersistentMap : public GC_Object {
33public:
34 /// Type of this class
35 using Self = PersistentMap<Key, Val, Hash, Eq>;
36
37 /// Types of version nodes
38 enum Mode {
39 BASE, ///< Root node of version tree
40 REM, ///< Key removal node
41 INS, ///< Key update node
42 UPD ///< Key update node
43 };
44
45private:
46 /// Type of underlying hash table
47 using Base = std::unordered_map<Key, Val, Hash, Eq>;
48
49 /// Node inserted into underlying map
50 struct Ins {
51 Self* base; ///< Modified map
52 Key key; ///< Key inserted
53 Val val; ///< Value stored
54
55 template<typename K, typename V>
56 Ins(Self* b, K&& k, V&& v) : base(b), key(std::forward<K>(k)), val(std::forward<V>(v)) {}
57 };
58
59 /// Node removed from underlying map
60 struct Rem {
61 Self* base; ///< Modified map
62 Key key; ///< Key removed
63
64 template<typename K>
65 Rem(Self* b, K&& k) : base(b), key(std::forward<K>(k)) {}
66 };
67
68 /// Underlying storage
69 union Data {
70 char def;
71 Base base;
72 Ins ins;
73 Rem rem;
74
75 Data() : def('\0') {}
76 ~Data() {}
77 } data;
78
79 // Mode of node
80 mutable Mode mode;
81
82 /// get mutable reference as T
83 template<typename T>
84 T& as() { return reinterpret_cast<T&>(data); }
85
86 /// get const reference as T
87 template<typename T>
88 const T& as() const { return reinterpret_cast<const T&>(data); }
89
90 /// get rvalue reference as T
91 template<typename T>
92 T&& take_as() { return std::move(as<T>()); }
93
94 /// initialize as T
95 template<typename T, typename... Args>
96 void init( Args&&... args ) {
97 new( &as<T>() ) T { std::forward<Args>(args)... };
98 }
99
100 /// reset as current mode
101 void reset() {
102 switch( mode ) {
103 case BASE: as<Base>().~Base(); break;
104 case REM: as<Rem>().~Rem(); break;
105 case INS: case UPD: as<Ins>().~Ins(); break;
106 default: assertf(false, "invalid mode");
107 }
108 }
109
110 /// reset as base
111 void reset_as_base() {
112 assertf( mode == BASE, "can only reset_as_base() on BASE" );
113 as<Base>().~Base();
114 }
115
116 /// Non-initializing constructor; should call init() before use
117 PersistentMap( Mode m ) : data(), mode(m) {}
118
119 PersistentMap( Mode m, Base&& b ) : data(), mode(m) {
120 assertf(m == BASE, "invalid mode");
121 init<Base>(std::move(b));
122 }
123
124 template<typename K, typename V>
125 PersistentMap( Mode m, const Self* o, K&& k, V&& v ) : data(), mode(m) {
126 assertf(m == INS || m == UPD, "invalid mode");
127 init<Ins>(o, std::forward<K>(k), std::forward<V>(v));
128 }
129
130 template<typename K>
131 PersistentMap( Mode m, const Self* o, K&& k ) : data(), mode(m) {
132 assertf(m == REM, "invalid mode");
133 init<Rem>(o, std::forward<K>(k));
134 }
135
136protected:
137 void trace(const GC& gc) const {
138 switch( mode ) {
139 case BASE: {
140 for (const auto& entry : as<Base>()) {
141 gc.maybe_trace( entry.first, entry.second );
142 }
143 } break;
144 case REM: {
145 const Rem& self = as<Rem>();
146 gc << self.base;
147 gc.maybe_trace( self.key );
148 } break;
149 case INS: case UPD: {
150 const Ins& self = as<Ins>();
151 gc << self.base;
152 gc.maybe_trace( self.key, self.val );
153 } break;
154 default: assertf(false, "invalid mode");
155 }
156 }
157
158public:
159 using size_type = std::size_t;
160
161 using iterator = typename Base::const_iterator;
162
163 PersistentMap() : data(), mode(BASE) { init<Base>(); }
164
165 PersistentMap( const Self& o ) = delete;
166
167 Self& operator= ( const Self& o ) = delete;
168
169 ~PersistentMap() { reset(); }
170
171 /// reroot persistent map at current node
172 void reroot() const {
173 // recursive base case
174 if ( mode == BASE ) return;
175
176 // reroot base
177 Self* mut_this = const_cast<Self*>(this);
178 Self* base = ( mode == REM ) ? mut_this->as<Rem>().base : mut_this->as<Ins>().base;
179 base->reroot();
180 assertf(base->mode == BASE, "reroot results in base");
181
182 // take map out of base
183 Base base_map = base->take_as<Base>();
184 base->reset_as_base();
185
186 // switch base to inverse of self and mutate base map
187 switch ( mode ) {
188 case REM: {
189 Rem& self = mut_this->as<Rem>();
190 auto it = base_map.find( self.key );
191 assertf( it != base_map.end(), "removed node must exist in base");
192
193 base->init<Ins>( mut_this, std::move(self.key), std::move(it->second) );
194 base->mode = INS;
195
196 base_map.erase( it );
197 } break;
198 case INS: {
199 Ins& self = mut_this->as<Ins>();
200
201 base->init<Rem>( mut_this, self.key );
202 base->mode = REM;
203
204 base_map.emplace( std::move(self.key), std::move(self.val) );
205 } break;
206 case UPD: {
207 Ins& self = mut_this->as<Ins>();
208 auto it = base_map.find( self.key );
209 assertf( it != base_map.end(), "updated node must exist in base");
210
211 base->init<Ins>( mut_this, std::move(self.key), std::move(it->second) );
212 base->mode = UPD;
213
214 it->second = std::move(self.val);
215 } break;
216 default: assertf(false, "invalid mode");
217 }
218
219 // set base map into self
220 mut_this->reset();
221 mut_this->init<Base>( std::move(base_map) );
222 mode = BASE;
223 }
224
225private:
226 /// Gets the base after rerooting at the current node
227 const Base& rerooted() const {
228 reroot();
229 return as<Base>();
230 }
231
232public:
233 /// true iff the map is empty
234 bool empty() const { return rerooted().empty(); }
235
236 /// Get number of entries in map
237 size_type size() const { return rerooted().size(); }
238
239 /// Get begin iterator for map; may be invalidated by calls to non-iteration functions
240 /// or functions on other maps in the same chain
241 iterator begin() const { return rerooted().begin(); }
242
243 /// Get end iterator for map; may be invalidated by calls to non-iteration functions
244 /// or functions on other maps in the same chain
245 iterator end() const { return rerooted().end(); }
246
247 /// Get underlying map iterator for value
248 iterator find(const Key& k) const { return rerooted().find( k ); }
249
250 /// Check if value is present
251 size_type count(const Key& k) const { return rerooted().count( k ); }
252
253 /// Get value; undefined behavior if not present
254 const Val& get(const Key& k) const {
255 const Base& self = rerooted();
256 auto it = self.find( k );
257 assertf(it != self.end(), "get target not present");
258 return it->second;
259 }
260
261 /// Get value; returns default if not present
262 template<typename V>
263 Val get_or_default(const Key& k, V&& d) const {
264 const Base& self = rerooted();
265 auto it = self.find( k );
266 if ( it == self.end() ) return d;
267 else return it->second;
268 }
269
270 /// Set value, storing new map in output variable
271 template<typename K, typename V>
272 Self* set(K&& k, V&& v) {
273 reroot();
274 assertf(mode == BASE, "reroot results in base");
275
276 // transfer map to new node
277 Self* ret = new Self{ BASE, take_as<Base>() };
278 reset_as_base();
279 Base& base_map = ret->as<Base>();
280
281 // check if this is update or insert
282 auto it = base_map.find( k );
283 if ( it == base_map.end() ) {
284 // set self to REM node and insert into base
285 init<Rem>( ret, k );
286 mode = REM;
287
288 base_map.emplace_hint( it, std::forward<K>(k), std::forward<V>(v) );
289 } else {
290 // set self to UPD node and modify base
291 init<Ins>( ret, std::forward<K>(k), std::move(it->second) );
292 mode = UPD;
293
294 it->second = std::forward<V>(v);
295 }
296
297 return ret;
298 }
299
300 /// Remove value, storing new map in output variable; does nothing if key not in map
301 Self* erase(const Key& k) {
302 reroot();
303 assertf(mode == BASE, "reroot results in base");
304
305 // exit early if key does not exist in map
306 if ( ! as<Base>().count( k ) ) return this;
307
308 // transfer map to new node
309 Self* ret = new Self{ BASE, take_as<Base>() };
310 reset_as_base();
311 Base& base_map = ret->as<Base>();
312
313 // set self to INS node and remove from base
314 init<Ins>( ret, k, base_map[k] );
315 mode = INS;
316
317 base_map.erase( k );
318
319 return ret;
320 }
321
322 /// smart reference for indexing interface
323 class Entry {
324 friend PersistentMap;
325 Self* base;
326 const Key& key;
327
328 public:
329 Entry(Self* b, const Key& k) : base(b), key(k) {}
330
331 /// Gets the underlying map instance
332 Self* get_base() const { return base; }
333
334 /// Gets the key
335 const Key& get_key() const { return key; }
336
337 /// Checks if the key exists in the map
338 bool exists() const { return base->count(key); }
339
340 /// Gets the value for the key (if it exists)
341 const Val& get() const { return base->get(key); }
342
343 /// Cast version of get
344 operator const Val& () const { return base->get(key); }
345
346 /// Sets the value into the key; returns entry pointing to new set
347 template<typename V>
348 Entry& set(V&& v) {
349 base = base->set(key, std::forward<V>(v));
350 return *this;
351 }
352
353 /// Assignment version of set
354 template<typename V>
355 Entry& operator= (V&& v) {
356 base = base->set(key, std::forward<V>(v));
357 return *this;
358 }
359
360 /// Gets value or initializes to new value from args
361 template<typename... Args>
362 Entry& get_or(Args&&... args) {
363 base = base->get_or(key, std::forward<Args>(args)...);
364 return *this;
365 }
366 };
367
368 /// Gets smart reference to slot with given key
369 Entry operator[] (const Key& k) { return { this, k }; }
370
371 /// Gets Entry for key, initializing from args if not present
372 template<typename... Args>
373 Entry get_or_insert(const Key& k, Args&&... args) {
374 Base& base_map = rerooted();
375
376 // check already present
377 if ( base_map.count(k) ) return { this, k };
378
379 // otherwise insert based on parameters
380 base_map.emplace( k, Val{ std::forward<Args>(args)... } );
381 Self* ret = new Self{ BASE, std::move(base_map) };
382
383 // update self to point to new base
384 reset_as_base();
385 init<Rem>( ret, k );
386 mode = REM;
387
388 // return entry for new base
389 return { ret, k };
390 }
391
392 /// Get version node type
393 Mode get_mode() const { return mode; }
394
395 /// Get next version up the revision tree (self if base node)
396 const Self* get_base() const {
397 switch ( mode ) {
398 case BASE: return this;
399 case REM: return as<Rem>().base;
400 case INS: case UPD: return as<Ins>().base;
401 default: assertf(false, "invalid mode");
402 }
403 }
404
405 /// Get key of revision node (undefined if called on base)
406 const Key& get_key() const {
407 switch ( mode ) {
408 case REM: return as<Rem>().key;
409 case INS: case UPD: return as<Ins>().key;
410 default: assertf(false, "invalid mode for get_key()");
411 }
412 }
413
414 /// Get value of insert/update revision node (undefined otherwise)
415 const Val& get_val() const {
416 switch ( mode ) {
417 case INS: case UPD: return as<Ins>().val;
418 default: assertf(false, "invalid mode for get_val()");
419 }
420 }
421
422 /// Applies the function `f` to all elements of the map.
423 /// `f` should take two parameters, `const Key&` and `const Val&`.
424 template<typename F>
425 void for_each(F&& f) const {
426 for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); }
427 }
428
429 /// Applies the function `f` to all elements of the map, returning a pointer to the updated map.
430 /// `f` should take two parameters, `const Key&` and `Val&`, returning option<Val> filled with
431 /// the previous value if mutated, an empty option<Val> otherwise.
432 /// NOTE: when porting to C++17, this should work fine with std::optional
433 template<typename F>
434 Self* mutate_each(F&& f) {
435 // reset to root and exit early if no change
436 if ( rerooted().empty() ) return this;
437
438 // remove map from self
439 Base base_map = take_as<Base>();
440 reset_as_base();
441
442 // apply all edits
443 Self* next_edit = this;
444 for ( auto& entry : base_map ) {
445 auto res = f( entry.first, entry.second );
446 if ( res ) {
447 // entry has been mutated; reset next_edit node as mutation
448 Self* new_node = new Self{ BASE };
449 next_edit->init<Ins>( new_node, entry.first, *std::move(res) );
450 next_edit->mode = UPD;
451 next_edit = new_node;
452 }
453 }
454
455 // set map into final node and return
456 next_edit->init<Base>( std::move(base_map) );
457 return next_edit;
458 }
459};
460
461// Local Variables: //
462// tab-width: 4 //
463// mode: c++ //
464// compile-command: "make install" //
465// End: //
Note: See TracBrowser for help on using the repository browser.