1/* A type-safe hash map that retains the insertion order of keys.
2 Copyright (C) 2019-2023 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 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
192private:
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
209template<typename Key, typename Value,
210 typename Traits = simple_hashmap_traits<default_hash_traits<Key>,
211 Value> >
212class ordered_hash_map;
213
214#endif /* GCC_ORDERED_HASH_MAP_H */
215

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