1 /* A type-safe hash map that retains the insertion order of keys.
2 Copyright (C) 2019-2023 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 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 /* Removing a key removes it from the map, but retains the insertion
80 order. */
81
82 void remove (const Key &k)
83 {
84 m_map.remove (k);
85 }
86
87 size_t elements () const { return m_map.elements (); }
88
89 class iterator
90 {
91 public:
92 explicit iterator (const ordered_hash_map &map, unsigned idx) :
93 m_ordered_hash_map (map), m_idx (idx) {}
94
95 iterator &operator++ ()
96 {
97 /* Increment m_idx until we find a non-deleted element, or go beyond
98 the end. */
99 while (1)
100 {
101 ++m_idx;
102 if (valid_index_p ())
103 break;
104 }
105 return *this;
106 }
107
108 /* Can't use std::pair here, because GCC before 4.3 don't handle
109 std::pair where template parameters are references well.
110 See PR86739. */
111 struct reference_pair {
112 const Key &first;
113 Value &second;
114
115 reference_pair (const Key &key, Value &value)
116 : first (key), second (value) {}
117
118 template <typename K, typename V>
119 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
120 };
121
122 reference_pair operator* ()
123 {
124 const Key &k = m_ordered_hash_map.m_keys[m_idx];
125 Value *slot
126 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
127 gcc_assert (slot);
128 return reference_pair (k, *slot);
129 }
130
131 bool
132 operator != (const iterator &other) const
133 {
134 return m_idx != other.m_idx;
135 }
136
137 /* Treat one-beyond-the-end as valid, for handling the "end" case. */
138
139 bool valid_index_p () const
140 {
141 if (m_idx > m_ordered_hash_map.m_keys.length ())
142 return false;
143 if (m_idx == m_ordered_hash_map.m_keys.length ())
144 return true;
145 const Key &k = m_ordered_hash_map.m_keys[m_idx];
146 Value *slot
147 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
148 return slot != NULL;
149 }
150
151 const ordered_hash_map &m_ordered_hash_map;
152 unsigned m_idx;
153 };
154
155 /* Standard iterator retrieval methods. */
156
157 iterator begin () const
158 {
159 iterator i = iterator (*this, 0);
160 while (!i.valid_index_p () && i != end ())
161 ++i;
162 return i;
163 }
164 iterator end () const { return iterator (*this, m_keys.length ()); }
165
166 private:
167 /* The assignment operator is not yet implemented; prevent erroneous
168 usage of unsafe compiler-generated one. */
169 void operator= (const ordered_hash_map &);
170
171 /* The underlying map. */
172 hash_map<KeyId, Value, Traits> m_map;
173
174 /* The ordering of the keys. */
175 auto_vec<Key> m_keys;
176
177 /* For each key that's ever been in the map, its index within m_keys. */
178 hash_map<KeyId, int> m_key_index;
179 };
180
181 /* Two-argument form. */
182
183 template<typename Key, typename Value,
184 typename Traits = simple_hashmap_traits<default_hash_traits<Key>,
185 Value> >
186 class ordered_hash_map;
187
188 #endif /* GCC_ORDERED_HASH_MAP_H */