source: src/GenPoly/ScopedMap.h@ b542bfb

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since b542bfb was 46f6134, checked in by Thierry Delisle <tdelisle@…>, 9 years ago

Implemented owning scoped map for typedef elimination phase
  • Property mode set to 100644
File size: 9.3 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// 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 _SCOPEDMAP_H
17#define _SCOPEDMAP_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 template<typename Key, typename Value>
29 class ScopedMap {
30 typedef std::map< Key, Value > Scope;
31 typedef std::vector< Scope > ScopeList;
32
33 ScopeList scopes; ///< scoped list of maps
34 public:
35 typedef typename Scope::key_type key_type;
36 typedef typename Scope::mapped_type mapped_type;
37 typedef typename Scope::value_type value_type;
38 typedef typename ScopeList::size_type size_type;
39 typedef typename ScopeList::difference_type difference_type;
40 typedef typename Scope::reference reference;
41 typedef typename Scope::const_reference const_reference;
42 typedef typename Scope::pointer pointer;
43 typedef typename Scope::const_pointer const_pointer;
44
45 class iterator : public std::iterator< std::bidirectional_iterator_tag,
46 value_type > {
47 friend class ScopedMap;
48 friend class const_iterator;
49 typedef typename std::map< Key, Value >::iterator wrapped_iterator;
50 typedef typename std::vector< std::map< Key, Value > > scope_list;
51 typedef typename scope_list::size_type size_type;
52
53 /// Checks if this iterator points to a valid item
54 bool is_valid() const {
55 return it != (*scopes)[i].end();
56 }
57
58 /// Increments on invalid
59 iterator& next_valid() {
60 if ( ! is_valid() ) { ++(*this); }
61 return *this;
62 }
63
64 /// Decrements on invalid
65 iterator& prev_valid() {
66 if ( ! is_valid() ) { --(*this); }
67 return *this;
68 }
69
70 iterator(scope_list &_scopes, const wrapped_iterator &_it, size_type _i)
71 : scopes(&_scopes), it(_it), i(_i) {}
72 public:
73 iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
74 iterator& operator= (const iterator &that) {
75 scopes = that.scopes; i = that.i; it = that.it;
76 return *this;
77 }
78
79 reference operator* () { return *it; }
80 pointer operator-> () { return it.operator->(); }
81
82 iterator& operator++ () {
83 if ( it == (*scopes)[i].end() ) {
84 if ( i == 0 ) return *this;
85 --i;
86 it = (*scopes)[i].begin();
87 } else {
88 ++it;
89 }
90 return next_valid();
91 }
92 iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
93
94 iterator& operator-- () {
95 // may fail if this is the begin iterator; allowed by STL spec
96 if ( it == (*scopes)[i].begin() ) {
97 ++i;
98 it = (*scopes)[i].end();
99 }
100 --it;
101 return prev_valid();
102 }
103 iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
104
105 bool operator== (const iterator &that) {
106 return scopes == that.scopes && i == that.i && it == that.it;
107 }
108 bool operator!= (const iterator &that) { return !( *this == that ); }
109
110 private:
111 scope_list *scopes;
112 wrapped_iterator it;
113 size_type i;
114 };
115
116 class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
117 value_type > {
118 friend class ScopedMap;
119 typedef typename std::map< Key, Value >::iterator wrapped_iterator;
120 typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator;
121 typedef typename std::vector< std::map< Key, Value > > scope_list;
122 typedef typename scope_list::size_type size_type;
123
124 /// Checks if this iterator points to a valid item
125 bool is_valid() const {
126 return it != (*scopes)[i].end();
127 }
128
129 /// Increments on invalid
130 const_iterator& next_valid() {
131 if ( ! is_valid() ) { ++(*this); }
132 return *this;
133 }
134
135 /// Decrements on invalid
136 const_iterator& prev_valid() {
137 if ( ! is_valid() ) { --(*this); }
138 return *this;
139 }
140
141 const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
142 : scopes(&_scopes), it(_it), i(_i) {}
143 public:
144 const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
145 const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
146 const_iterator& operator= (const iterator &that) {
147 scopes = that.scopes; i = that.i; it = that.it;
148 return *this;
149 }
150 const_iterator& operator= (const const_iterator &that) {
151 scopes = that.scopes; i = that.i; it = that.it;
152 return *this;
153 }
154
155 const_reference operator* () { return *it; }
156 const_pointer operator-> () { return it.operator->(); }
157
158 const_iterator& operator++ () {
159 if ( it == (*scopes)[i].end() ) {
160 if ( i == 0 ) return *this;
161 --i;
162 it = (*scopes)[i].begin();
163 } else {
164 ++it;
165 }
166 return next_valid();
167 }
168 const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
169
170 const_iterator& operator-- () {
171 // may fail if this is the begin iterator; allowed by STL spec
172 if ( it == (*scopes)[i].begin() ) {
173 ++i;
174 it = (*scopes)[i].end();
175 }
176 --it;
177 return prev_valid();
178 }
179 const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
180
181 bool operator== (const const_iterator &that) {
182 return scopes == that.scopes && i == that.i && it == that.it;
183 }
184 bool operator!= (const const_iterator &that) { return !( *this == that ); }
185
186 private:
187 scope_list const *scopes;
188 wrapped_const_iterator it;
189 size_type i;
190 };
191
192 /// Starts a new scope
193 void beginScope() {
194 scopes.emplace_back();
195 }
196
197 /// Ends a scope; invalidates any iterators pointing to elements of that scope
198 void endScope() {
199 scopes.pop_back();
200 assert( ! scopes.empty() );
201 }
202
203 /// Default constructor initializes with one scope
204 ScopedMap() { beginScope(); }
205
206 iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
207 const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
208 const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
209 iterator end() { return iterator(scopes, scopes[0].end(), 0); }
210 const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
211 const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
212
213 /// Gets the index of the current scope (counted from 1)
214 size_type currentScope() const { return scopes.size(); }
215
216 /// Finds the given key in the outermost scope it occurs; returns end() for none such
217 iterator find( const Key &key ) {
218 for ( size_type i = scopes.size() - 1; ; --i ) {
219 typename Scope::iterator val = scopes[i].find( key );
220 if ( val != scopes[i].end() ) return iterator( scopes, val, i );
221 if ( i == 0 ) break;
222 }
223 return end();
224 }
225 const_iterator find( const Key &key ) const {
226 return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->find( key ) );
227 }
228
229 /// Finds the given key in the outermost scope inside the given scope where it occurs
230 iterator findNext( const_iterator &it, const Key &key ) {
231 if ( it.i == 0 ) return end();
232 for ( size_type i = it.i - 1; ; --i ) {
233 typename Scope::iterator val = scopes[i].find( key );
234 if ( val != scopes[i].end() ) return iterator( scopes, val, i );
235 if ( i == 0 ) break;
236 }
237 return end();
238 }
239 const_iterator findNext( const_iterator &it, const Key &key ) const {
240 return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->findNext( it, key ) );
241 }
242
243 /// Inserts the given key-value pair into the outermost scope
244 std::pair< iterator, bool > insert( const value_type &value ) {
245 std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
246 return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
247 }
248
249 std::pair< iterator, bool > insert( value_type &&value ) {
250 std::pair< typename Scope::iterator, bool > res = scopes.back().insert( std::move( value ) );
251 return std::make_pair( iterator(scopes, std::move( res.first ), scopes.size()-1), std::move( res.second ) );
252 }
253
254 std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
255 std::pair< iterator, bool > insert( const Key &key, Value &&value ) { return insert( std::make_pair( key, std::move( value ) ) ); }
256
257 Value& operator[] ( const Key &key ) {
258 iterator slot = find( key );
259 if ( slot != end() ) return slot->second;
260 return insert( key, Value() ).first->second;
261 }
262
263 iterator erase( iterator pos ) {
264 Scope& scope = (*pos.scopes) [ pos.i ];
265 const typename iterator::wrapped_iterator& new_it = scope.erase( pos.it );
266 iterator it( *pos.scopes, new_it, pos.i );
267 return it.next_valid();
268 }
269
270 size_type count( const Key &key ) const {
271 size_type c = 0;
272 auto it = find( key );
273 auto end = cend();
274
275 while(it != end) {
276 c++;
277 it = findNext(it, key);
278 }
279
280 return c;
281 }
282
283 };
284} // namespace GenPoly
285
286#endif // _SCOPEDMAP_H
287
288// Local Variables: //
289// tab-width: 4 //
290// mode: c++ //
291// compile-command: "make install" //
292// End: //
Note: See TracBrowser for help on using the repository browser.