gcc/ordered-hash-map.h

   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 */