source: src/Common/PersistentMap.h @ d318a18

new-env
Last change on this file since d318a18 was d318a18, checked in by Aaron Moss <a3moss@…>, 6 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.