1/* A type-safe hash map that retains the insertion order of keys.
2 Copyright (C) 2019-2025 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
32template<typename KeyId, typename Value,
33 typename Traits>
34class ordered_hash_map
35{
36 typedef typename Traits::key_type Key;
37
38public:
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 void empty () { m_map.empty(); }
116
117 class iterator
118 {
119 public:
120 explicit iterator (const ordered_hash_map &map, unsigned idx) :
121 m_ordered_hash_map (map), m_idx (idx) {}
122
123 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 ++m_idx;
130 if (valid_index_p ())
131 break;
132 }
133 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 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 reference_pair operator* ()
151 {
152 const Key &k = m_ordered_hash_map.m_keys[m_idx];
153 Value *slot
154 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
155 gcc_assert (slot);
156 return reference_pair (k, *slot);
157 }
158
159 bool
160 operator != (const iterator &other) const
161 {
162 return m_idx != other.m_idx;
163 }
164
165 /* Treat one-beyond-the-end as valid, for handling the "end" case. */
166
167 bool valid_index_p () const
168 {
169 if (m_idx > m_ordered_hash_map.m_keys.length ())
170 return false;
171 if (m_idx == m_ordered_hash_map.m_keys.length ())
172 return true;
173 const Key &k = m_ordered_hash_map.m_keys[m_idx];
174 Value *slot
175 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
176 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 iterator begin () const
186 {
187 iterator i = iterator (*this, 0);
188 while (!i.valid_index_p () && i != end ())
189 ++i;
190 return i;
191 }
192 iterator end () const { return iterator (*this, m_keys.length ()); }
193
194private:
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
211template<typename Key, typename Value,
212 typename Traits = simple_hashmap_traits<default_hash_traits<Key>,
213 Value> >
214class ordered_hash_map;
215
216#endif /* GCC_ORDERED_HASH_MAP_H */
217

source code of gcc/ordered-hash-map.h