Branch data Line data Source code
1 : : /* A type-safe hash map that retains the insertion order of keys.
2 : : Copyright (C) 2019-2024 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 : 45972 : 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 : 471178 : bool put (const Key &k, const Value &v)
57 : : {
58 : 471178 : bool existed = m_map.put (k, v);
59 : 471178 : if (!existed)
60 : : {
61 : : bool key_present;
62 : 471178 : int &slot = m_key_index.get_or_insert (k, &key_present);
63 : 471178 : if (!key_present)
64 : : {
65 : 471174 : slot = m_keys.length ();
66 : 471174 : m_keys.safe_push (k);
67 : : }
68 : : }
69 : 471178 : return existed;
70 : : }
71 : :
72 : : /* If the passed in key is in the map return its value otherwise NULL. */
73 : :
74 : 3171546 : Value *get (const Key &k)
75 : : {
76 : 2710612 : 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 : 624 : size_t elements () const { return m_map.elements (); }
114 : :
115 : : class iterator
116 : : {
117 : : public:
118 : 155375 : explicit iterator (const ordered_hash_map &map, unsigned idx) :
119 : 32134 : m_ordered_hash_map (map), m_idx (idx) {}
120 : :
121 : 187191 : 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 : 187191 : ++m_idx;
128 : 187191 : if (valid_index_p ())
129 : : break;
130 : : }
131 : 187191 : 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 : 273743 : 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 : 273743 : reference_pair operator* ()
149 : : {
150 : 273743 : const Key &k = m_ordered_hash_map.m_keys[m_idx];
151 : : Value *slot
152 : 273743 : = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
153 : 273743 : gcc_assert (slot);
154 : 273743 : return reference_pair (k, *slot);
155 : : }
156 : :
157 : : bool
158 : 219325 : operator != (const iterator &other) const
159 : : {
160 : 219321 : return m_idx != other.m_idx;
161 : : }
162 : :
163 : : /* Treat one-beyond-the-end as valid, for handling the "end" case. */
164 : :
165 : 219329 : bool valid_index_p () const
166 : : {
167 : 424762 : if (m_idx > m_ordered_hash_map.m_keys.length ())
168 : : return false;
169 : 219329 : if (m_idx == m_ordered_hash_map.m_keys.length ())
170 : : return true;
171 : 187191 : const Key &k = m_ordered_hash_map.m_keys[m_idx];
172 : : Value *slot
173 : 187191 : = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
174 : 187191 : 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 : 32134 : iterator begin () const
184 : : {
185 : 32134 : iterator i = iterator (*this, 0);
186 : 32138 : while (!i.valid_index_p () && i != end ())
187 : 4 : ++i;
188 : 32134 : return i;
189 : : }
190 : 232586 : 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 */
|
