]>
Commit | Line | Data |
---|---|---|
757bf1df | 1 | /* A type-safe hash map that retains the insertion order of keys. |
a945c346 | 2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
757bf1df DM |
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 | ||
3bb0bf06 AT |
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 | ||
757bf1df DM |
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 */ |