|
145
|
1 /* A type-safe hash map that retains the insertion order of keys.
|
|
|
2 Copyright (C) 2019-2020 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 */
|
