1 | /* A type-safe hash map that retains the insertion order of keys. |
2 | Copyright (C) 2019-2023 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 | /* Return a reference to the value for the passed in key, creating the entry |
80 | if it doesn't already exist. If existed is not NULL then it is set to |
81 | false if the key was not previously in the map, and true otherwise. */ |
82 | |
83 | Value &get_or_insert (const Key &k, bool *existed = NULL) |
84 | { |
85 | bool _existed; |
86 | Value &ret = m_map.get_or_insert (k, &_existed); |
87 | |
88 | if (!_existed) |
89 | { |
90 | bool key_present; |
91 | int &slot = m_key_index.get_or_insert (k, &key_present); |
92 | if (!key_present) |
93 | { |
94 | slot = m_keys.length (); |
95 | m_keys.safe_push (k); |
96 | } |
97 | } |
98 | |
99 | if (existed) |
100 | *existed = _existed; |
101 | |
102 | return ret; |
103 | } |
104 | |
105 | /* Removing a key removes it from the map, but retains the insertion |
106 | order. */ |
107 | |
108 | void remove (const Key &k) |
109 | { |
110 | m_map.remove (k); |
111 | } |
112 | |
113 | size_t elements () const { return m_map.elements (); } |
114 | |
115 | class iterator |
116 | { |
117 | public: |
118 | explicit iterator (const ordered_hash_map &map, unsigned idx) : |
119 | m_ordered_hash_map (map), m_idx (idx) {} |
120 | |
121 | iterator &operator++ () |
122 | { |
123 | /* Increment m_idx until we find a non-deleted element, or go beyond |
124 | the end. */ |
125 | while (1) |
126 | { |
127 | ++m_idx; |
128 | if (valid_index_p ()) |
129 | break; |
130 | } |
131 | return *this; |
132 | } |
133 | |
134 | /* Can't use std::pair here, because GCC before 4.3 don't handle |
135 | std::pair where template parameters are references well. |
136 | See PR86739. */ |
137 | struct reference_pair { |
138 | const Key &first; |
139 | Value &second; |
140 | |
141 | reference_pair (const Key &key, Value &value) |
142 | : first (key), second (value) {} |
143 | |
144 | template <typename K, typename V> |
145 | operator std::pair<K, V> () const { return std::pair<K, V> (first, second); } |
146 | }; |
147 | |
148 | reference_pair operator* () |
149 | { |
150 | const Key &k = m_ordered_hash_map.m_keys[m_idx]; |
151 | Value *slot |
152 | = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k); |
153 | gcc_assert (slot); |
154 | return reference_pair (k, *slot); |
155 | } |
156 | |
157 | bool |
158 | operator != (const iterator &other) const |
159 | { |
160 | return m_idx != other.m_idx; |
161 | } |
162 | |
163 | /* Treat one-beyond-the-end as valid, for handling the "end" case. */ |
164 | |
165 | bool valid_index_p () const |
166 | { |
167 | if (m_idx > m_ordered_hash_map.m_keys.length ()) |
168 | return false; |
169 | if (m_idx == m_ordered_hash_map.m_keys.length ()) |
170 | return true; |
171 | const Key &k = m_ordered_hash_map.m_keys[m_idx]; |
172 | Value *slot |
173 | = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k); |
174 | return slot != NULL; |
175 | } |
176 | |
177 | const ordered_hash_map &m_ordered_hash_map; |
178 | unsigned m_idx; |
179 | }; |
180 | |
181 | /* Standard iterator retrieval methods. */ |
182 | |
183 | iterator begin () const |
184 | { |
185 | iterator i = iterator (*this, 0); |
186 | while (!i.valid_index_p () && i != end ()) |
187 | ++i; |
188 | return i; |
189 | } |
190 | iterator end () const { return iterator (*this, m_keys.length ()); } |
191 | |
192 | private: |
193 | /* The assignment operator is not yet implemented; prevent erroneous |
194 | usage of unsafe compiler-generated one. */ |
195 | void operator= (const ordered_hash_map &); |
196 | |
197 | /* The underlying map. */ |
198 | hash_map<KeyId, Value, Traits> m_map; |
199 | |
200 | /* The ordering of the keys. */ |
201 | auto_vec<Key> m_keys; |
202 | |
203 | /* For each key that's ever been in the map, its index within m_keys. */ |
204 | hash_map<KeyId, int> m_key_index; |
205 | }; |
206 | |
207 | /* Two-argument form. */ |
208 | |
209 | template<typename Key, typename Value, |
210 | typename Traits = simple_hashmap_traits<default_hash_traits<Key>, |
211 | Value> > |
212 | class ordered_hash_map; |
213 | |
214 | #endif /* GCC_ORDERED_HASH_MAP_H */ |
215 | |