GCC Middle and Back End API Reference
ordered-hash-map.h
Go to the documentation of this file.
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>
35{
36 typedef typename Traits::key_type Key;
37
38public:
40
42 : m_map (other.m_map),
43 m_keys (other.m_keys.length ()),
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
118 {
119 public:
120 explicit iterator (const ordered_hash_map &map, unsigned idx) :
121 m_ordered_hash_map (map), m_idx (idx) {}
122
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. */
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
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);
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
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. */
198
199 /* The underlying map. */
201
202 /* The ordering of the keys. */
204
205 /* For each key that's ever been in the map, its index within m_keys. */
207};
208
209/* Two-argument form. */
210
211template<typename Key, typename Value,
213 Value> >
214class ordered_hash_map;
215
216#endif /* GCC_ORDERED_HASH_MAP_H */
Definition vec.h:1667
Definition hash-map.h:40
unsigned m_idx
Definition ordered-hash-map.h:180
bool valid_index_p() const
Definition ordered-hash-map.h:167
bool operator!=(const iterator &other) const
Definition ordered-hash-map.h:160
iterator & operator++()
Definition ordered-hash-map.h:123
iterator(const ordered_hash_map &map, unsigned idx)
Definition ordered-hash-map.h:120
reference_pair operator*()
Definition ordered-hash-map.h:150
const ordered_hash_map & m_ordered_hash_map
Definition ordered-hash-map.h:179
Definition ordered-hash-map.h:35
bool put(const Key &k, const Value &v)
Definition ordered-hash-map.h:56
sinfo_hashmap_traits::key_type Key
Definition ordered-hash-map.h:36
hash_map< void *, int > m_key_index
Definition ordered-hash-map.h:206
Value & get_or_insert(const Key &k, bool *existed=NULL)
Definition ordered-hash-map.h:83
ordered_hash_map(const ordered_hash_map &other)
Definition ordered-hash-map.h:41
Value * get(const Key &k)
Definition ordered-hash-map.h:74
void operator=(const ordered_hash_map &)
hash_map< void *, sinfo *, sinfo_hashmap_traits > m_map
Definition ordered-hash-map.h:200
ordered_hash_map()
Definition ordered-hash-map.h:39
auto_vec< Key > m_keys
Definition ordered-hash-map.h:203
iterator begin() const
Definition ordered-hash-map.h:185
iterator end() const
Definition ordered-hash-map.h:192
size_t elements() const
Definition ordered-hash-map.h:113
void remove(const Key &k)
Definition ordered-hash-map.h:108
void empty()
Definition ordered-hash-map.h:115
Definition lra-spills.cc:101
static struct string2counter_map map[debug_counter_number_of_counters]
Definition dbgcnt.cc:39
i
Definition poly-int.h:776
Definition ordered-hash-map.h:139
Value & second
Definition ordered-hash-map.h:141
const Key & first
Definition ordered-hash-map.h:140
reference_pair(const Key &key, Value &value)
Definition ordered-hash-map.h:143
Definition hash-map-traits.h:33
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:814
#define FOR_EACH_VEC_ELT(V, I, P)
Definition vec.h:1895