source: src/GenPoly/ErasableScopedMap.h@ 6b6597c

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since 6b6597c was bfae637, checked in by Aaron Moss <a3moss@…>, 10 years ago

Initial compiling build with TyVarMap as ErasableScopedMap
  • Property mode set to 100644
File size: 9.5 KB
RevLine 
[bfae637]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// ScopedMap.h --
8//
9// Author : Aaron B. Moss
10// Created On : Wed Dec 2 11:37:00 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Wed Dec 2 11:37:00 2015
13// Update Count : 1
14//
15
16#ifndef _ERASABLESCOPEDMAP_H
17#define _ERASABLESCOPEDMAP_H
18
19#include <cassert>
20#include <iterator>
21#include <map>
22#include <utility>
23#include <vector>
24
25namespace GenPoly {
26 /// A map where the items are placed into nested scopes;
27 /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward;
28 /// erasing a key means that find() will no longer report any instance of the key in a scope further
29 /// out, but the erasure itself is scoped. Key erasure works by inserting a sentinal value into the
30 /// value field, and thus only works for Value types where a meaningful sentinal can be chosen.
31 template<typename Key, typename Value>
32 class ErasableScopedMap {
33 typedef std::map< Key, Value > Scope;
34 typedef std::vector< Scope > ScopeList;
35
36 ScopeList scopes; ///< scoped list of maps
37 Value erased; ///< sentinal value for erased keys
38 public:
39 typedef typename Scope::key_type key_type;
40 typedef typename Scope::mapped_type mapped_type;
41 typedef typename Scope::value_type value_type;
42 typedef typename ScopeList::size_type size_type;
43 typedef typename ScopeList::difference_type difference_type;
44 typedef typename Scope::reference reference;
45 typedef typename Scope::const_reference const_reference;
46 typedef typename Scope::pointer pointer;
47 typedef typename Scope::const_pointer const_pointer;
48
49 class iterator : public std::iterator< std::bidirectional_iterator_tag,
50 value_type > {
51 friend class ErasableScopedMap;
52 friend class const_iterator;
53 typedef typename std::map< Key, Value >::iterator wrapped_iterator;
54 typedef typename std::vector< std::map< Key, Value > > scope_list;
55 typedef typename scope_list::size_type size_type;
56
57 /// Checks if this iterator points to a valid item
58 bool is_valid() const {
59 return it != map->scopes[i].end() && it->second != map->erased;
60 }
61
62 /// Increments on invalid
63 iterator& next_valid() {
64 if ( ! is_valid() ) { ++(*this); }
65 return *this;
66 }
67
68 /// Decrements on invalid
69 iterator& prev_valid() {
70 if ( ! is_valid() ) { --(*this); }
71 return *this;
72 }
73
74 iterator(ErasableScopedMap< Key, Value > const &_map, const wrapped_iterator &_it, size_type _i)
75 : map(&_map), it(_it), i(_i) {}
76
77 public:
78 iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {}
79 iterator& operator= (const iterator &that) {
80 map = that.map; i = that.i; it = that.it;
81 return *this;
82 }
83
84 reference operator* () { return *it; }
85 pointer operator-> () { return it.operator->(); }
86
87 iterator& operator++ () {
88 if ( it == map->scopes[i].end() ) {
89 if ( i == 0 ) return *this;
90 --i;
91 it = map->scopes[i].begin();
92 } else {
93 ++it;
94 }
95 return next_valid();
96 }
97 iterator& operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
98
99 iterator& operator-- () {
100 // may fail if this is the begin iterator; allowed by STL spec
101 if ( it == map->scopes[i].begin() ) {
102 ++i;
103 it = map->scopes[i].end();
104 }
105 --it;
106 return prev_valid();
107 }
108 iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
109
110 bool operator== (const iterator &that) {
111 return map == that.map && i == that.i && it == that.it;
112 }
113 bool operator!= (const iterator &that) { return !( *this == that ); }
114
115 private:
116 ErasableScopedMap< Key, Value > const *map;
117 wrapped_iterator it;
118 size_type i;
119 };
120
121 class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
122 value_type > {
123 friend class ErasableScopedMap;
124 typedef typename std::map< Key, Value >::iterator wrapped_iterator;
125 typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator;
126 typedef typename std::vector< std::map< Key, Value > > scope_list;
127 typedef typename scope_list::size_type size_type;
128
129 /// Checks if this iterator points to a valid item
130 bool is_valid() const {
131 return it != map->scopes[i].end() && it->second != map->erased;
132 }
133
134 /// Increments on invalid
135 const_iterator& next_valid() {
136 if ( ! is_valid() ) { ++(*this); }
137 return *this;
138 }
139
140 /// Decrements on invalid
141 const_iterator& prev_valid() {
142 if ( ! is_valid() ) { --(*this); }
143 return *this;
144 }
145
146 const_iterator(ErasableScopedMap< Key, Value > const &_map, const wrapped_const_iterator &_it, size_type _i)
147 : map(&_map), it(_it), i(_i) {}
148 public:
149 const_iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {}
150 const_iterator(const const_iterator &that) : map(that.map), it(that.it), i(that.i) {}
151 const_iterator& operator= (const iterator &that) {
152 map = that.map; i = that.i; it = that.it;
153 return *this;
154 }
155 const_iterator& operator= (const const_iterator &that) {
156 map = that.map; i = that.i; it = that.it;
157 return *this;
158 }
159
160 const_reference operator* () { return *it; }
161 const_pointer operator-> () { return it.operator->(); }
162
163 const_iterator& operator++ () {
164 if ( it == map->scopes[i].end() ) {
165 if ( i == 0 ) return *this;
166 --i;
167 it = map->scopes[i].begin();
168 } else {
169 ++it;
170 }
171 return next_valid();
172 }
173 const_iterator& operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
174
175 const_iterator& operator-- () {
176 // may fail if this is the begin iterator; allowed by STL spec
177 if ( it == map->scopes[i].begin() ) {
178 ++i;
179 it = map->scopes[i].end();
180 }
181 --it;
182 return prev_valid();
183 }
184 const_iterator& operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
185
186 bool operator== (const const_iterator &that) {
187 return map == that.map && i == that.i && it == that.it;
188 }
189 bool operator!= (const const_iterator &that) { return !( *this == that ); }
190
191 private:
192 ErasableScopedMap< Key, Value > const *map;
193 wrapped_const_iterator it;
194 size_type i;
195 };
196
197 /// Starts a new scope
198 void beginScope() {
199 Scope scope;
200 scopes.push_back(scope);
201 }
202
203 /// Ends a scope; invalidates any iterators pointing to elements of that scope
204 void endScope() {
205 scopes.pop_back();
206 assert( ! scopes.empty() );
207 }
208
209 /// Default constructor initializes with one scope
210 ErasableScopedMap( const Value &erased_ ) : erased( erased_ ) { beginScope(); }
211
212 iterator begin() { return iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); }
213 const_iterator begin() const { return const_iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); }
214 const_iterator cbegin() const { return const_iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); }
215 iterator end() { return iterator(*this, scopes[0].end(), 0); }
216 const_iterator end() const { return const_iterator(*this, scopes[0].end(), 0); }
217 const_iterator cend() const { return const_iterator(*this, scopes[0].end(), 0); }
218
219 /// Gets the index of the current scope (counted from 1)
220 size_type currentScope() const { return scopes.size(); }
221
222 /// Finds the given key in the outermost scope it occurs; returns end() for none such
223 iterator find( const Key &key ) {
224 for ( size_type i = scopes.size() - 1; ; --i ) {
225 typename Scope::iterator val = scopes[i].find( key );
226 if ( val != scopes[i].end() ) {
227 return val->second == erased ? end() : iterator( *this, val, i );
228 }
229 if ( i == 0 ) break;
230 }
231 return end();
232 }
233 const_iterator find( const Key &key ) const {
234 return const_iterator( const_cast< ErasableScopedMap< Key, Value >* >(this)->find( key ) );
235 }
236
237 /// Finds the given key in the outermost scope inside the given scope where it occurs
238 iterator findNext( const_iterator &it, const Key &key ) {
239 if ( it.i == 0 ) return end();
240 for ( size_type i = it.i - 1; ; --i ) {
241 typename Scope::iterator val = scopes[i].find( key );
242 if ( val != scopes[i].end() ) {
243 return val->second == erased ? end() : iterator( *this, val, i );
244 }
245 if ( i == 0 ) break;
246 }
247 return end();
248 }
249 const_iterator findNext( const_iterator &it, const Key &key ) const {
250 return const_iterator( const_cast< ErasableScopedMap< Key, Value >* >(this)->findNext( it, key ) );
251 }
252
253 /// Inserts the given key-value pair into the outermost scope
254 std::pair< iterator, bool > insert( const value_type &value ) {
255 std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
256 return std::make_pair( iterator(*this, res.first, scopes.size()-1), res.second );
257 }
258 std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
259
260 /// Marks the given element as erased from this scope inward; returns 1 for erased an element, 0 otherwise
261 size_type erase( const Key &key ) {
262 typename Scope::iterator val = scopes.back().find( key );
263 if ( val != scopes.back().end() ) {
264 val->second = erased;
265 return 1;
266 } else {
267 scopes.back().insert( val, std::make_pair( key, erased ) );
268 return 0;
269 }
270 }
271
272 Value& operator[] ( const Key &key ) {
273 iterator slot = find( key );
274 if ( slot != end() ) return slot->second;
275 return insert( key, Value() ).first->second;
276 }
277 };
278} // namespace GenPoly
279
280#endif // _ERASABLESCOPEDMAP_H
281
282// Local Variables: //
283// tab-width: 4 //
284// mode: c++ //
285// compile-command: "make install" //
286// End: //
Note: See TracBrowser for help on using the repository browser.