Line data Source code
1 : /* A type-safe hash map that retains the insertion order of keys.
2 : Copyright (C) 2019-2026 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 21109 : 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 205835 : bool put (const Key &k, const Value &v)
57 : {
58 205835 : bool existed = m_map.put (k, v);
59 205835 : if (!existed)
60 : {
61 : bool key_present;
62 205835 : int &slot = m_key_index.get_or_insert (k, &key_present);
63 205835 : if (!key_present)
64 : {
65 205831 : slot = m_keys.length ();
66 205831 : m_keys.safe_push (k);
67 : }
68 : }
69 205835 : return existed;
70 : }
71 :
72 : /* If the passed in key is in the map return its value otherwise NULL. */
73 :
74 2648469 : Value *get (const Key &k)
75 : {
76 2287061 : 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 473 : size_t elements () const { return m_map.elements (); }
114 :
115 564 : void empty () { m_map.empty(); }
116 :
117 : class iterator
118 : {
119 : public:
120 102763 : explicit iterator (const ordered_hash_map &map, unsigned idx) :
121 18826 : m_ordered_hash_map (map), m_idx (idx) {}
122 :
123 150423 : 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 150441 : ++m_idx;
130 150441 : if (valid_index_p ())
131 : break;
132 : }
133 150423 : 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 210967 : 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 210967 : reference_pair operator* ()
151 : {
152 210967 : const Key &k = m_ordered_hash_map.m_keys[m_idx];
153 : Value *slot
154 210967 : = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
155 210967 : gcc_assert (slot);
156 210967 : return reference_pair (k, *slot);
157 : }
158 :
159 : bool
160 169249 : operator != (const iterator &other) const
161 : {
162 168963 : return m_idx != other.m_idx;
163 : }
164 :
165 : /* Treat one-beyond-the-end as valid, for handling the "end" case. */
166 :
167 169553 : bool valid_index_p () const
168 : {
169 334091 : if (m_idx > m_ordered_hash_map.m_keys.length ())
170 : return false;
171 169553 : if (m_idx == m_ordered_hash_map.m_keys.length ())
172 : return true;
173 150441 : const Key &k = m_ordered_hash_map.m_keys[m_idx];
174 : Value *slot
175 150441 : = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
176 150441 : 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 18826 : iterator begin () const
186 : {
187 18826 : iterator i = iterator (*this, 0);
188 19112 : while (!i.valid_index_p () && i != end ())
189 286 : ++i;
190 18826 : return i;
191 : }
192 162859 : 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 */
|
