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-2024 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
116 {
117 public:
118 explicit iterator (const ordered_hash_map &map, unsigned idx) :
119 m_ordered_hash_map (map), m_idx (idx) {}
120
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. */
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
149 {
151 Value *slot
152 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
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;
172 Value *slot
173 = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
174 return slot != NULL;
175 }
176
178 unsigned m_idx;
179 };
180
181 /* Standard iterator retrieval methods. */
182
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. */
196
197 /* The underlying map. */
199
200 /* The ordering of the keys. */
202
203 /* For each key that's ever been in the map, its index within m_keys. */
205};
206
207/* Two-argument form. */
208
209template<typename Key, typename Value,
211 Value> >
212class ordered_hash_map;
213
214#endif /* GCC_ORDERED_HASH_MAP_H */
Definition vec.h:1656
Definition hash-map.h:40
Value & get_or_insert(const Key &k, bool *existed=NULL)
Definition hash-map.h:199
Definition ordered-hash-map.h:116
unsigned m_idx
Definition ordered-hash-map.h:178
bool valid_index_p() const
Definition ordered-hash-map.h:165
bool operator!=(const iterator &other) const
Definition ordered-hash-map.h:158
iterator & operator++()
Definition ordered-hash-map.h:121
iterator(const ordered_hash_map &map, unsigned idx)
Definition ordered-hash-map.h:118
reference_pair operator*()
Definition ordered-hash-map.h:148
const ordered_hash_map & m_ordered_hash_map
Definition ordered-hash-map.h:177
Definition ordered-hash-map.h:35
bool put(const Key &k, const Value &v)
Definition ordered-hash-map.h:56
hash_map< KeyId, int > m_key_index
Definition ordered-hash-map.h:204
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< KeyId, Value, Traits > m_map
Definition ordered-hash-map.h:198
ordered_hash_map()
Definition ordered-hash-map.h:39
auto_vec< Key > m_keys
Definition ordered-hash-map.h:201
iterator begin() const
Definition ordered-hash-map.h:183
iterator end() const
Definition ordered-hash-map.h:190
size_t elements() const
Definition ordered-hash-map.h:113
void remove(const Key &k)
Definition ordered-hash-map.h:108
Traits::key_type Key
Definition ordered-hash-map.h:36
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:137
Value & second
Definition ordered-hash-map.h:139
const Key & first
Definition ordered-hash-map.h:138
reference_pair(const Key &key, Value &value)
Definition ordered-hash-map.h:141
Definition hash-map-traits.h:33
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821
#define FOR_EACH_VEC_ELT(V, I, P)
Definition vec.h:1884