source: src/Common/PersistentMap.h@ fdae913

ADT arm-eh ast-experimental cleanup-dtors enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr persistent-indexer pthread-emulation qualifiedEnum stuck-waitfor-destruct
Last change on this file since fdae913 was fdae913, checked in by Aaron Moss <a3moss@…>, 7 years ago

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