Branch data Line data Source code
1 : : /* A type-safe hash map that retains the insertion order of keys.
2 : : Copyright (C) 2019-2025 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 : 39044 : ordered_hash_map () {}
40 : :
41 : 4 : ordered_hash_map (const ordered_hash_map &other)
42 : 4 : : m_map (other.m_map),
43 : 8 : m_keys (other.m_keys.length ()),
44 : 4 : m_key_index (other.m_key_index)
45 : : {
46 : : unsigned i;
47 : : Key key;
48 : 8 : FOR_EACH_VEC_ELT (other.m_keys, i, key)
49 : 4 : m_keys.quick_push (key);
50 : 4 : }
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 : 395421 : bool put (const Key &k, const Value &v)
57 : : {
58 : 395421 : bool existed = m_map.put (k, v);
59 : 395421 : if (!existed)
60 : : {
61 : : bool key_present;
62 : 395421 : int &slot = m_key_index.get_or_insert (k, &key_present);
63 : 395421 : if (!key_present)
64 : : {
65 : 395417 : slot = m_keys.length ();
66 : 395417 : m_keys.safe_push (k);
67 : : }
68 : : }
69 : 395421 : return existed;
70 : : }
71 : :
72 : : /* If the passed in key is in the map return its value otherwise NULL. */
73 : :
74 : 2680977 : Value *get (const Key &k)
75 : : {
76 : 2292964 : 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 : 16 : Value &get_or_insert (const Key &k, bool *existed = NULL)
84 : : {
85 : : bool _existed;
86 : 16 : Value &ret = m_map.get_or_insert (k, &_existed);
87 : :
88 : 16 : if (!_existed)
89 : : {
90 : : bool key_present;
91 : 8 : int &slot = m_key_index.get_or_insert (k, &key_present);
92 : 8 : if (!key_present)
93 : : {
94 : 8 : slot = m_keys.length ();
95 : 8 : m_keys.safe_push (k);
96 : : }
97 : : }
98 : :
99 : 16 : if (existed)
100 : 16 : *existed = _existed;
101 : :
102 : 16 : return ret;
103 : : }
104 : :
105 : : /* Removing a key removes it from the map, but retains the insertion
106 : : order. */
107 : :
108 : 8 : void remove (const Key &k)
109 : : {
110 : 8 : m_map.remove (k);
111 : : }
112 : :
113 : 508 : size_t elements () const { return m_map.elements (); }
114 : :
115 : 520 : void empty () { m_map.empty(); }
116 : :
117 : : class iterator
118 : : {
119 : : public:
120 : 131729 : explicit iterator (const ordered_hash_map &map, unsigned idx) :
121 : 27612 : m_ordered_hash_map (map), m_idx (idx) {}
122 : :
123 : 157982 : iterator &operator++ ()
124 : : {
125 : : /* Increment m_idx until we find a non-deleted element, or go beyond
126 : : the end. */
127 : : while (1)
128 : : {
129 : 158000 : ++m_idx;
130 : 158000 : if (valid_index_p ())
131 : : break;
132 : : }
133 : 157982 : return *this;
134 : : }
135 : :
136 : : /* Can't use std::pair here, because GCC before 4.3 don't handle
137 : : std::pair where template parameters are references well.
138 : : See PR86739. */
139 : : struct reference_pair {
140 : : const Key &first;
141 : : Value &second;
142 : :
143 : 230013 : reference_pair (const Key &key, Value &value)
144 : : : first (key), second (value) {}
145 : :
146 : : template <typename K, typename V>
147 : : operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
148 : : };
149 : :
150 : 230013 : reference_pair operator* ()
151 : : {
152 : 230013 : const Key &k = m_ordered_hash_map.m_keys[m_idx];
153 : : Value *slot
154 : 230013 : = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
155 : 230013 : gcc_assert (slot);
156 : 230013 : return reference_pair (k, *slot);
157 : : }
158 : :
159 : : bool
160 : 185594 : operator != (const iterator &other) const
161 : : {
162 : 185330 : return m_idx != other.m_idx;
163 : : }
164 : :
165 : : /* Treat one-beyond-the-end as valid, for handling the "end" case. */
166 : :
167 : 185876 : bool valid_index_p () const
168 : : {
169 : 360148 : if (m_idx > m_ordered_hash_map.m_keys.length ())
170 : : return false;
171 : 185876 : if (m_idx == m_ordered_hash_map.m_keys.length ())
172 : : return true;
173 : 158000 : const Key &k = m_ordered_hash_map.m_keys[m_idx];
174 : : Value *slot
175 : 158000 : = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
176 : 158000 : return slot != NULL;
177 : : }
178 : :
179 : : const ordered_hash_map &m_ordered_hash_map;
180 : : unsigned m_idx;
181 : : };
182 : :
183 : : /* Standard iterator retrieval methods. */
184 : :
185 : 27612 : iterator begin () const
186 : : {
187 : 27612 : iterator i = iterator (*this, 0);
188 : 27876 : while (!i.valid_index_p () && i != end ())
189 : 264 : ++i;
190 : 27612 : return i;
191 : : }
192 : 196630 : iterator end () const { return iterator (*this, m_keys.length ()); }
193 : :
194 : : private:
195 : : /* The assignment operator is not yet implemented; prevent erroneous
196 : : usage of unsafe compiler-generated one. */
197 : : void operator= (const ordered_hash_map &);
198 : :
199 : : /* The underlying map. */
200 : : hash_map<KeyId, Value, Traits> m_map;
201 : :
202 : : /* The ordering of the keys. */
203 : : auto_vec<Key> m_keys;
204 : :
205 : : /* For each key that's ever been in the map, its index within m_keys. */
206 : : hash_map<KeyId, int> m_key_index;
207 : : };
208 : :
209 : : /* Two-argument form. */
210 : :
211 : : template<typename Key, typename Value,
212 : : typename Traits = simple_hashmap_traits<default_hash_traits<Key>,
213 : : Value> >
214 : : class ordered_hash_map;
215 : :
216 : : #endif /* GCC_ORDERED_HASH_MAP_H */
|