Mercurial > hg > CbC > CbC_gcc
comparison gcc/ordered-hash-map.h @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
131:84e7813d76e9 | 145:1830386684a0 |
---|---|
1 /* A type-safe hash map that retains the insertion order of keys. | |
2 Copyright (C) 2019-2020 Free Software Foundation, Inc. | |
3 | |
4 This file is part of GCC. | |
5 | |
6 GCC is free software; you can redistribute it and/or modify it under | |
7 the terms of the GNU General Public License as published by the Free | |
8 Software Foundation; either version 3, or (at your option) any later | |
9 version. | |
10 | |
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 | |
21 #ifndef GCC_ORDERED_HASH_MAP_H | |
22 #define GCC_ORDERED_HASH_MAP_H | |
23 | |
24 /* Notes: | |
25 - The keys must be PODs, since vec<> uses assignment to populate slots | |
26 without properly initializing them. | |
27 - doesn't have GTY support. | |
28 - supports removal, but retains order of original insertion. | |
29 (Removal might be better handled by using a doubly-linked list | |
30 of nodes, holding the values). */ | |
31 | |
32 template<typename KeyId, typename Value, | |
33 typename Traits> | |
34 class ordered_hash_map | |
35 { | |
36 typedef typename Traits::key_type Key; | |
37 | |
38 public: | |
39 ordered_hash_map () {} | |
40 | |
41 ordered_hash_map (const ordered_hash_map &other) | |
42 : m_map (other.m_map), | |
43 m_keys (other.m_keys.length ()), | |
44 m_key_index (other.m_key_index) | |
45 { | |
46 unsigned i; | |
47 Key key; | |
48 FOR_EACH_VEC_ELT (other.m_keys, i, key) | |
49 m_keys.quick_push (key); | |
50 } | |
51 | |
52 /* If key K isn't already in the map add key K with value V to the map, and | |
53 return false. Otherwise set the value of the entry for key K to be V and | |
54 return true. */ | |
55 | |
56 bool put (const Key &k, const Value &v) | |
57 { | |
58 bool existed = m_map.put (k, v); | |
59 if (!existed) | |
60 { | |
61 bool key_present; | |
62 int &slot = m_key_index.get_or_insert (k, &key_present); | |
63 if (!key_present) | |
64 { | |
65 slot = m_keys.length (); | |
66 m_keys.safe_push (k); | |
67 } | |
68 } | |
69 return existed; | |
70 } | |
71 | |
72 /* If the passed in key is in the map return its value otherwise NULL. */ | |
73 | |
74 Value *get (const Key &k) | |
75 { | |
76 return m_map.get (k); | |
77 } | |
78 | |
79 /* Removing a key removes it from the map, but retains the insertion | |
80 order. */ | |
81 | |
82 void remove (const Key &k) | |
83 { | |
84 m_map.remove (k); | |
85 } | |
86 | |
87 size_t elements () const { return m_map.elements (); } | |
88 | |
89 class iterator | |
90 { | |
91 public: | |
92 explicit iterator (const ordered_hash_map &map, unsigned idx) : | |
93 m_ordered_hash_map (map), m_idx (idx) {} | |
94 | |
95 iterator &operator++ () | |
96 { | |
97 /* Increment m_idx until we find a non-deleted element, or go beyond | |
98 the end. */ | |
99 while (1) | |
100 { | |
101 ++m_idx; | |
102 if (valid_index_p ()) | |
103 break; | |
104 } | |
105 return *this; | |
106 } | |
107 | |
108 /* Can't use std::pair here, because GCC before 4.3 don't handle | |
109 std::pair where template parameters are references well. | |
110 See PR86739. */ | |
111 struct reference_pair { | |
112 const Key &first; | |
113 Value &second; | |
114 | |
115 reference_pair (const Key &key, Value &value) | |
116 : first (key), second (value) {} | |
117 | |
118 template <typename K, typename V> | |
119 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); } | |
120 }; | |
121 | |
122 reference_pair operator* () | |
123 { | |
124 const Key &k = m_ordered_hash_map.m_keys[m_idx]; | |
125 Value *slot | |
126 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k); | |
127 gcc_assert (slot); | |
128 return reference_pair (k, *slot); | |
129 } | |
130 | |
131 bool | |
132 operator != (const iterator &other) const | |
133 { | |
134 return m_idx != other.m_idx; | |
135 } | |
136 | |
137 /* Treat one-beyond-the-end as valid, for handling the "end" case. */ | |
138 | |
139 bool valid_index_p () const | |
140 { | |
141 if (m_idx > m_ordered_hash_map.m_keys.length ()) | |
142 return false; | |
143 if (m_idx == m_ordered_hash_map.m_keys.length ()) | |
144 return true; | |
145 const Key &k = m_ordered_hash_map.m_keys[m_idx]; | |
146 Value *slot | |
147 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k); | |
148 return slot != NULL; | |
149 } | |
150 | |
151 const ordered_hash_map &m_ordered_hash_map; | |
152 unsigned m_idx; | |
153 }; | |
154 | |
155 /* Standard iterator retrieval methods. */ | |
156 | |
157 iterator begin () const | |
158 { | |
159 iterator i = iterator (*this, 0); | |
160 while (!i.valid_index_p () && i != end ()) | |
161 ++i; | |
162 return i; | |
163 } | |
164 iterator end () const { return iterator (*this, m_keys.length ()); } | |
165 | |
166 private: | |
167 /* The assignment operator is not yet implemented; prevent erroneous | |
168 usage of unsafe compiler-generated one. */ | |
169 void operator= (const ordered_hash_map &); | |
170 | |
171 /* The underlying map. */ | |
172 hash_map<KeyId, Value, Traits> m_map; | |
173 | |
174 /* The ordering of the keys. */ | |
175 auto_vec<Key> m_keys; | |
176 | |
177 /* For each key that's ever been in the map, its index within m_keys. */ | |
178 hash_map<KeyId, int> m_key_index; | |
179 }; | |
180 | |
181 /* Two-argument form. */ | |
182 | |
183 template<typename Key, typename Value, | |
184 typename Traits = simple_hashmap_traits<default_hash_traits<Key>, | |
185 Value> > | |
186 class ordered_hash_map; | |
187 | |
188 #endif /* GCC_ORDERED_HASH_MAP_H */ |