source: src/Common/ScopedMap.h @ 35df560

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 35df560 was e58dfb9, checked in by Aaron Moss <a3moss@…>, 5 years ago

Fix scoping bug with generic type instantiations (thanks Rob!)

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