gcc/ordered-hash-map.h

   1 /* A type-safe hash map that retains the insertion order of keys.
   2    Copyright (C) 2019-2023 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   class iterator
 116   {
 117   public:
 118     explicit iterator (const ordered_hash_map &map, unsigned idx) :
 119       m_ordered_hash_map (map), m_idx (idx) {}
 120
 121     iterator &operator++ ()
 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.  */
 137     struct reference_pair {
 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
 148     reference_pair operator* ()
 149     {
 150       const Key &k = m_ordered_hash_map.m_keys[m_idx];
 151       Value *slot
 152         = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
 153       gcc_assert (slot);
 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;
 171       const Key &k = m_ordered_hash_map.m_keys[m_idx];
 172       Value *slot
 173         = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
 174       return slot != NULL;
 175     }
 176
 177     const ordered_hash_map &m_ordered_hash_map;
 178     unsigned m_idx;
 179   };
 180
 181   /* Standard iterator retrieval methods.  */
 182
 183   iterator begin () const
 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
 192 private:
 193   /* The assignment operator is not yet implemented; prevent erroneous
 194      usage of unsafe compiler-generated one.  */
 195   void operator= (const ordered_hash_map &);
 196
 197   /* The underlying map.  */
 198   hash_map<KeyId, Value, Traits> m_map;
 199
 200   /* The ordering of the keys.  */
 201   auto_vec<Key> m_keys;
 202
 203   /* For each key that's ever been in the map, its index within m_keys.  */
 204   hash_map<KeyId, int> m_key_index;
 205 };
 206
 207 /* Two-argument form.  */
 208
 209 template<typename Key, typename Value,
 210          typename Traits = simple_hashmap_traits<default_hash_traits<Key>,
 211                                                  Value> >
 212 class ordered_hash_map;
 213
 214 #endif /* GCC_ORDERED_HASH_MAP_H */