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: ordered_hash_map()39 ordered_hash_map () {} 40 ordered_hash_map(const ordered_hash_map & other)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 put(const Key & k,const Value & v)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 get(const Key & k)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 remove(const Key & k)82 void remove (const Key &k) 83 { 84 m_map.remove (k); 85 } 86 elements()87 size_t elements () const { return m_map.elements (); } 88 89 class iterator 90 { 91 public: iterator(const ordered_hash_map & map,unsigned idx)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 reference_pairreference_pair115 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 valid_index_p()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 begin()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 } end()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 */ 189