source: src/Common/PersistentMap.h @ 42f1279c

arm-ehcleanup-dtorsenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 42f1279c was 42f1279c, checked in by Aaron Moss <a3moss@…>, 4 years ago

Eagerly remove over-ridden generated functions

  • Property mode set to 100644
File size: 8.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       : 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
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
27/// Data Structure"
28
29template<typename Key, typename Val,
30         typename Hash = std::hash<Key>, typename Eq = std::equal_to<Key>>
31class PersistentMap 
32        : public std::enable_shared_from_this<PersistentMap<Key, Val, Hash, Eq>> {
33public:
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
40        enum Mode { 
41                BASE,  ///< Root node of version tree
42                REM,   ///< Key removal node
43                INS,   ///< Key update node
44                UPD    ///< Key update node
45        };
46
47private:
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
65               
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        /// check if this is the only reference to itself
117        /// NOTE: optimizations employing this function are not thread-safe
118        bool is_shared(long local_ptrs = 0) const {
119                // 2 accounts for both the pointer which owns "this" and the one created for its use_count
120                return (this->shared_from_this().use_count() - local_ptrs) > 2;
121        }
122
123public:
124        using key_type = typename Base::key_type;
125        using mapped_type = typename Base::mapped_type;
126        using value_type = typename Base::value_type;
127        using size_type = typename Base::size_type;
128        using difference_type = typename Base::difference_type;
129        using iterator = typename Base::const_iterator;
130
131        PersistentMap() : data(), mode(BASE) { init<Base>(); }
132
133        PersistentMap( Base&& b ) : data(), mode(BASE) { init<Base>(std::move(b)); }
134
135        PersistentMap( const Self& o ) = delete;
136
137        Self& operator= ( const Self& o ) = delete;
138
139        ~PersistentMap() { reset(); }
140
141        /// Create a pointer to a new, empty persistent map
142        static Ptr new_ptr() { return std::make_shared<Self>(); }
143
144        /// reroot persistent map at current node
145        void reroot() const {
146                // recursive base case
147                if ( mode == BASE ) return;
148
149                // reroot base
150                Self* mut_this = const_cast<Self*>(this);
151                Ptr base = ( mode == REM ) ? mut_this->as<Rem>().base : mut_this->as<Ins>().base;
152                base->reroot();
153
154                // remove map from base
155                Base base_map = base->take_as<Base>();
156
157                // switch base to inverse of self and mutate base map
158                switch ( mode ) {
159                        case REM: {
160                                Rem& self = mut_this->as<Rem>();
161                                auto it = base_map.find( self.key );
162
163                                if ( base->is_shared( 1 ) ) {
164                                        base->reset_as_base();
165                                        base->init<Ins>( 
166                                                mut_this->shared_from_this(), std::move(self.key), std::move(it->second) );
167                                        base->mode = INS;
168                                }
169
170                                base_map.erase( it );
171                                break;
172                        }
173                        case INS: {
174                                Ins& self = mut_this->as<Ins>();
175
176                                if ( base->is_shared( 1 ) ) {
177                                        base->reset_as_base();
178                                        base->init<Rem>( mut_this->shared_from_this(), self.key );
179                                        base->mode = REM;
180                                }
181
182                                base_map.emplace( std::move(self.key), std::move(self.val) );
183                                break;
184                        }
185                        case UPD: {
186                                Ins& self = mut_this->as<Ins>();
187                                auto it = base_map.find( self.key );
188
189                                if ( base->is_shared( 1 ) ) {
190                                        base->reset_as_base();
191                                        base->init<Ins>( 
192                                                mut_this->shared_from_this(), std::move(self.key), std::move(it->second) );
193                                        base->mode = UPD;
194                                }
195
196                                it->second = std::move(self.val);
197                                break;
198                        }
199                        case BASE: assertf(false, "unreachable"); break;
200                }
201
202                // set base map into self
203                mut_this->reset();
204                mut_this->init<Base>( std::move(base_map) );
205                mode = BASE;
206        }
207
208private:
209        /// the base after rerooting at the current node
210        const Base& rerooted() const {
211                reroot();
212                return as<Base>();
213        }
214
215public:
216        /// true iff the map is empty
217        bool empty() const { return rerooted().empty(); }
218
219        /// number of entries in map
220        size_type size() const { return rerooted().size(); }
221
222        /// begin iterator for map; may be invalidated by calls to non-iteration functions
223        /// or functions on other maps in the same tree
224        iterator begin() const { return rerooted().begin(); }
225
226        /// end iterator for map; may be invalidated by calls to non-iteration functions
227        /// or functions on other maps in the same tree
228        iterator end() const { return rerooted().end(); }
229
230        /// underlying map iterator for value
231        iterator find(const Key& k) const { return rerooted().find( k ); }
232
233        /// check if value is present
234        size_type count(const Key& k) const { return rerooted().count( k ); }
235
236        /// get value; undefined behaviour if not present
237        const Val& get(const Key& k) const {
238                const Base& self = rerooted();
239                auto it = self.find( k );
240                return it->second;
241        }
242
243        /// get value; returns default if not present
244        template<typename V>
245        Val get_or_default(const Key& k, V&& d) const {
246                const Base& self = rerooted();
247                auto it = self.find( k );
248                if ( it == self.end() ) return d;
249                else return it->second;
250        }
251
252        /// set value, storing new map in output variable
253        template<typename K, typename V>
254        Ptr set(K&& k, V&& v) {
255                reroot();
256
257                // transfer map to new node
258                Ptr ret = std::make_shared<Self>( take_as<Base>() );
259                Base& base_map = ret->as<Base>();
260
261                // check if this is update or insert
262                auto it = base_map.find( k );
263                if ( it == base_map.end() ) {
264                        if ( is_shared() ) {
265                                // set self to REM node and insert into base
266                                reset_as_base();
267                                init<Rem>( ret, k );
268                                mode = REM;
269                        }
270
271                        base_map.emplace_hint( it, std::forward<K>(k), std::forward<V>(v) );
272                } else {
273                        if ( is_shared() ) {
274                                // set self to UPD node and modify base
275                                reset_as_base();
276                                init<Ins>( ret, std::forward<K>(k), std::move(it->second) );
277                                mode = UPD;
278                        }
279
280                        it->second = std::forward<V>(v);
281                }
282
283                return ret;
284        }
285
286        /// remove value, storing new map in output variable; does nothing if key not in map
287        Ptr erase(const Key& k) {
288                reroot();
289               
290                // exit early if key does not exist in map
291                if ( ! as<Base>().count( k ) ) return this->shared_from_this();
292
293                // transfer map to new node
294                Ptr ret = std::make_shared<Self>( take_as<Base>() );
295                Base& base_map = ret->as<Base>();
296
297                if ( is_shared() ) {
298                        // set self to INS node and remove from base
299                        reset_as_base();
300                        init<Ins>( ret, k, base_map[k] );
301                        mode = INS;
302                }
303
304                base_map.erase( k );
305
306                return ret;
307        }
308};
309
310// Local Variables: //
311// tab-width: 4 //
312// mode: c++ //
313// compile-command: "make install" //
314// End: //
Note: See TracBrowser for help on using the repository browser.