gcc/ordered-hash-map.h

   1 /* A type-safe hash map that retains the insertion order of keys.
   2    Copyright (C) 2019-2024 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   /* 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
 117   class iterator
 118   {
 119   public:
 120     explicit iterator (const ordered_hash_map &map, unsigned idx) :
 121       m_ordered_hash_map (map), m_idx (idx) {}
 122
 123     iterator &operator++ ()
 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.  */
 139     struct reference_pair {
 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
 150     reference_pair operator* ()
 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);
 155       gcc_assert (slot);
 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
 179     const ordered_hash_map &m_ordered_hash_map;
 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
 194 private:
 195   /* The assignment operator is not yet implemented; prevent erroneous
 196      usage of unsafe compiler-generated one.  */
 197   void operator= (const ordered_hash_map &);
 198
 199   /* The underlying map.  */
 200   hash_map<KeyId, Value, Traits> m_map;
 201
 202   /* The ordering of the keys.  */
 203   auto_vec<Key> m_keys;
 204
 205   /* For each key that's ever been in the map, its index within m_keys.  */
 206   hash_map<KeyId, int> m_key_index;
 207 };
 208
 209 /* Two-argument form.  */
 210
 211 template<typename Key, typename Value,
 212          typename Traits = simple_hashmap_traits<default_hash_traits<Key>,
 213                                                  Value> >
 214 class ordered_hash_map;
 215
 216 #endif /* GCC_ORDERED_HASH_MAP_H */