LCOV - code coverage report
Current view: top level - gcc - ordered-hash-map.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 45 46 97.8 %
Date: 2020-04-04 11:58:09 Functions: 58 58 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       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                 :     755230 :   ordered_hash_map () {}
      40                 :            : 
      41                 :     932588 :   ordered_hash_map (const ordered_hash_map &other)
      42                 :     932588 :   : m_map (other.m_map),
      43                 :            :     m_keys (other.m_keys.length ()),
      44                 :    1425579 :     m_key_index (other.m_key_index)
      45                 :            :   {
      46                 :            :      unsigned i;
      47                 :            :      Key key;
      48                 :    3034466 :      FOR_EACH_VEC_ELT (other.m_keys, i, key)
      49                 :    2101869 :        m_keys.quick_push (key);
      50                 :     932588 :   }
      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                 :    1244566 :   bool put (const Key &k, const Value &v)
      57                 :            :   {
      58                 :    1244566 :     bool existed = m_map.put (k, v);
      59                 :    1244566 :     if (!existed)
      60                 :            :       {
      61                 :            :         bool key_present;
      62                 :    1244566 :         int &slot = m_key_index.get_or_insert (k, &key_present);
      63                 :    1244566 :         if (!key_present)
      64                 :            :           {
      65                 :    1243324 :              slot = m_keys.length ();
      66                 :    1243324 :              m_keys.safe_push (k);
      67                 :            :           }
      68                 :            :       }
      69                 :    1244566 :     return existed;
      70                 :            :   }
      71                 :            : 
      72                 :            :   /* If the passed in key is in the map return its value otherwise NULL.  */
      73                 :            : 
      74                 :   20001034 :   Value *get (const Key &k)
      75                 :            :   {
      76                 :    8411513 :     return m_map.get (k);
      77                 :            :   }
      78                 :            : 
      79                 :            :   /* Removing a key removes it from the map, but retains the insertion
      80                 :            :      order.  */
      81                 :            : 
      82                 :      17824 :   void remove (const Key &k)
      83                 :            :   {
      84                 :      17824 :      m_map.remove (k);
      85                 :            :   }
      86                 :            : 
      87                 :     500845 :   size_t elements () const { return m_map.elements (); }
      88                 :            : 
      89                 :            :   class iterator
      90                 :            :   {
      91                 :            :   public:
      92                 :   13378631 :     explicit iterator (const ordered_hash_map &map, unsigned idx) :
      93                 :    3689286 :       m_ordered_hash_map (map), m_idx (idx) {}
      94                 :            : 
      95                 :    5011194 :     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                 :    8275933 :            ++m_idx;
     102                 :    8275933 :            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                 :    7989866 :       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                 :    7989863 :     reference_pair operator* ()
     123                 :            :     {
     124                 :    7989863 :       const Key &k = m_ordered_hash_map.m_keys[m_idx];
     125                 :    7989863 :       Value *slot
     126                 :    7989863 :         = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
     127                 :          0 :       gcc_assert (slot);
     128                 :    7989863 :       return reference_pair (k, *slot);
     129                 :            :     }
     130                 :            : 
     131                 :            :     bool
     132                 :    9657163 :     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                 :   11997401 :     bool valid_index_p () const
     140                 :            :     {
     141                 :   22194362 :       if (m_idx > m_ordered_hash_map.m_keys.length ())
     142                 :            :         return false;
     143                 :   11997401 :       if (m_idx == m_ordered_hash_map.m_keys.length ())
     144                 :            :         return true;
     145                 :    8355663 :       const Key &k = m_ordered_hash_map.m_keys[m_idx];
     146                 :    8355663 :       Value *slot
     147                 :    8355663 :         = const_cast<ordered_hash_map &> (m_ordered_hash_map).get (k);
     148                 :    8355663 :       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                 :    3689285 :   iterator begin () const
     158                 :            :   {
     159                 :    3721445 :     iterator i = iterator (*this, 0);
     160                 :    3721445 :     while (!i.valid_index_p () && i != end ())
     161                 :    3721445 :       ++i;
     162                 :    3689285 :     return i;
     163                 :            :   }
     164                 :   17573069 :   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 */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.