source: src/Common/PersistentMap.h@ 184557e

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

First draft of persistent-hash-based TypeEnvironment
  • 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 << entry.first << entry.second;
142 }
143 return;
144 }
145 case REM: {
146 const Rem& self = as<Rem>();
147 gc << self.base << self.key;
148 return;
149 }
150 case INS: case UPD: {
151 const Ins& self = as<Ins>();
152 gc << self.base << self.key << self.val;
153 return;
154 }
155 default: assertf(false, "invalid mode");
156 }
157 }
158
159public:
160 using size_type = std::size_t;
161
162 using iterator = typename Base::const_iterator;
163
164 PersistentMap() : data(), mode(BASE) { init<Base>(); }
165
166 PersistentMap( const Self& o ) = delete;
167
168 Self& operator= ( const Self& o ) = delete;
169
170 ~PersistentMap() { reset(); }
171
172 /// reroot persistent map at current node
173 void reroot() const {
174 // recursive base case
175 if ( mode == BASE ) return;
176
177 // reroot base
178 Self* mut_this = const_cast<Self*>(this);
179 Self* base = ( mode == REM ) ? mut_this->as<Rem>().base : mut_this->as<Ins>().base;
180 base->reroot();
181 assertf(base->mode == BASE, "reroot results in base");
182
183 // take map out of base
184 Base base_map = base->take_as<Base>();
185 base->reset_as_base();
186
187 // switch base to inverse of self and mutate base map
188 switch ( mode ) {
189 case REM: {
190 Rem& self = mut_this->as<Rem>();
191 auto it = base_map.find( self.key );
192 assertf( it != base_map.end(), "removed node must exist in base");
193
194 base->init<Ins>( mut_this, std::move(self.key), std::move(it->second) );
195 base->mode = INS;
196
197 base_map.erase( it );
198 break;
199 }
200 case INS: {
201 Ins& self = mut_this->as<Ins>();
202
203 base->init<Rem>( mut_this, self.key );
204 base->mode = REM;
205
206 base_map.emplace( std::move(self.key), std::move(self.val) );
207 break;
208 }
209 case UPD: {
210 Ins& self = mut_this->as<Ins>();
211 auto it = base_map.find( self.key );
212 assertf( it != base_map.end(), "updated node must exist in base");
213
214 base->init<Ins>( mut_this, std::move(self.key), std::move(it->second) );
215 base->mode = UPD;
216
217 it->second = std::move(self.val);
218 break;
219 }
220 default: assertf(false, "invalid mode");
221 }
222
223 // set base map into self
224 mut_this->reset();
225 mut_this->init<Base>( std::move(base_map) );
226 mode = BASE;
227 }
228
229private:
230 /// Gets the base after rerooting at the current node
231 const Base& rerooted() const {
232 reroot();
233 return as<Base>();
234 }
235
236public:
237 /// true iff the map is empty
238 bool empty() const { return rerooted().empty(); }
239
240 /// Get number of entries in map
241 size_type size() const { return rerooted().size(); }
242
243 /// Get begin iterator for map; may be invalidated by calls to non-iteration functions
244 /// or functions on other maps in the same chain
245 iterator begin() const { return rerooted().begin(); }
246
247 /// Get end iterator for map; may be invalidated by calls to non-iteration functions
248 /// or functions on other maps in the same chain
249 iterator end() const { return rerooted().end(); }
250
251 /// Get underlying map iterator for value
252 iterator find(const Key& k) const { return rerooted().find( k ); }
253
254 /// Check if value is present
255 size_type count(const Key& k) const { return rerooted().count( k ); }
256
257 /// Get value; undefined behavior if not present
258 const Val& get(const Key& k) const {
259 const Base& self = rerooted();
260 auto it = self.find( k );
261 assertf(it != self.end(), "get target not present");
262 return it->second;
263 }
264
265 /// Get value; returns default if not present
266 template<typename V>
267 Val get_or_default(const Key& k, V&& d) const {
268 const Base& self = rerooted();
269 auto it = self.find( k );
270 if ( it == self.end() ) return d;
271 else return it->second;
272 }
273
274 /// Set value, storing new map in output variable
275 template<typename K, typename V>
276 Self* set(K&& k, V&& v) {
277 reroot();
278 assertf(mode == BASE, "reroot results in base");
279
280 // transfer map to new node
281 Self* ret = new Self{ BASE, take_as<Base>() };
282 reset_as_base();
283 Base& base_map = ret->as<Base>();
284
285 // check if this is update or insert
286 auto it = base_map.find( k );
287 if ( it == base_map.end() ) {
288 // set self to REM node and insert into base
289 init<Rem>( ret, k );
290 mode = REM;
291
292 base_map.emplace_hint( it, std::forward<K>(k), std::forward<V>(v) );
293 } else {
294 // set self to UPD node and modify base
295 init<Ins>( ret, std::forward<K>(k), std::move(it->second) );
296 mode = UPD;
297
298 it->second = std::forward<V>(v);
299 }
300
301 return ret;
302 }
303
304 /// Remove value, storing new map in output variable; does nothing if key not in map
305 Self* erase(const Key& k) {
306 reroot();
307 assertf(mode == BASE, "reroot results in base");
308
309 // exit early if key does not exist in map
310 if ( ! as<Base>().count( k ) ) return this;
311
312 // transfer map to new node
313 Self* ret = new Self{ BASE, take_as<Base>() };
314 reset_as_base();
315 Base& base_map = ret->as<Base>();
316
317 // set self to INS node and remove from base
318 init<Ins>( ret, k, base_map[k] );
319 mode = INS;
320
321 base_map.erase( k );
322
323 return ret;
324 }
325
326 /// smart reference for indexing interface
327 class Entry {
328 friend PersistentMap;
329 Self* base;
330 const Key& key;
331
332 public:
333 Entry(Self* b, const Key& k) : base(b), key(k) {}
334
335 /// Gets the underlying map instance
336 Self* get_base() const { return base; }
337
338 /// Gets the key
339 const Key& get_key() const { return key; }
340
341 /// Checks if the key exists in the map
342 bool exists() const { return base->count(key); }
343
344 /// Gets the value for the key (if it exists)
345 const Val& get() const { return base->get(key); }
346
347 /// Cast version of get
348 operator const Val& () const { return base->get(key); }
349
350 /// Sets the value into the key; returns entry pointing to new set
351 template<typename V>
352 Entry& set(V&& v) {
353 base = base->set(key, std::forward<V>(v));
354 return *this;
355 }
356
357 /// Assignment version of set
358 template<typename V>
359 Entry& operator= (V&& v) {
360 base = base->set(key, std::forward<V>(v));
361 return *this;
362 }
363
364 /// Gets value or initializes to new value from args
365 template<typename... Args>
366 Entry& get_or(Args&&... args) {
367 base = base->get_or(key, std::forward<Args>(args)...);
368 return *this;
369 }
370 };
371
372 /// Gets smart reference to slot with given key
373 Entry operator[] (const Key& k) { return { this, k }; }
374
375 /// Gets Entry for key, initializing from args if not present
376 template<typename... Args>
377 Entry get_or_insert(const Key& k, Args&&... args) {
378 Base& base_map = rerooted();
379
380 // check already present
381 if ( base_map.count(k) ) return { this, k };
382
383 // otherwise insert based on parameters
384 base_map.emplace( k, Val{ std::forward<Args>(args)... } );
385 Self* ret = new Self{ BASE, std::move(base_map) };
386
387 // update self to point to new base
388 reset_as_base();
389 init<Rem>( ret, k );
390 mode = REM;
391
392 // return entry for new base
393 return { ret, k };
394 }
395
396 /// Get version node type
397 Mode get_mode() const { return mode; }
398
399 /// Get next version up the revision tree (self if base node)
400 const Self* get_base() const {
401 switch ( mode ) {
402 case BASE: return this;
403 case REM: return as<Rem>().base;
404 case INS: case UPD: return as<Ins>().base;
405 default: assertf(false, "invalid mode");
406 }
407 }
408
409 /// Get key of revision node (undefined if called on base)
410 const Key& get_key() const {
411 switch ( mode ) {
412 case REM: return as<Rem>().key;
413 case INS: case UPD: return as<Ins>().key;
414 default: assertf(false, "invalid mode for get_key()");
415 }
416 }
417
418 /// Get value of insert/update revision node (undefined otherwise)
419 const Val& get_val() const {
420 switch ( mode ) {
421 case INS: case UPD: return as<Ins>().val;
422 default: assertf(false, "invalid mode for get_val()");
423 }
424 }
425
426 /// Applies the function `f` to all elements of the map, returning a pointer to the updated map.
427 /// `f` should take two parameters, `const Key&` and `Val&`, returning option<Val> filled with
428 /// the previous value if mutated, an empty option<Val> otherwise.
429 /// NOTE: when porting to C++17, this should work fine with std::optional
430 template<typename F>
431 Self* apply_to_all(F&& f) {
432 // reset to root and exit early if no change
433 if ( rerooted().empty() ) return this;
434
435 // remove map from self
436 Base base_map = take_as<Base>();
437 reset_as_base();
438
439 // apply all edits
440 Self* next_edit = this;
441 for ( auto& entry : base_map ) {
442 auto res = f( entry.first, entry.second );
443 if ( res ) {
444 // entry has been mutated; reset next_edit node as mutation
445 Self* new_node = new Self{ BASE };
446 next_edit->init<Ins>( new_node, entry.first, *std::move(res) );
447 next_edit->mode = UPD;
448 next_edit = new_node;
449 }
450 }
451
452 // set map into final node and return
453 next_edit->init<Base>( std::move(base_map) );
454 return next_edit;
455 }
456
457 /// Applies the function `f` to all elements of the map.
458 /// `f` should take two parameters, `const Key&` and `const Val&`.
459 template<typename F>
460 void apply_to_all(F&& f) const {
461 for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); }
462 }
463};
464
465// Local Variables: //
466// tab-width: 4 //
467// mode: c++ //
468// compile-command: "make install" //
469// End: //
Note: See TracBrowser for help on using the repository browser.