Home | History | Annotate | Line # | Download | only in gcc
hash-set.h revision 1.1.1.2 
      1 /* A type-safe hash set.
      2    Copyright (C) 2014-2016 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 hash_set_h
     22 #define hash_set_h
     23 
     24 template<typename KeyId, typename Traits = default_hash_traits<KeyId> >
     25 class hash_set
     26 {
     27 public:
     28   typedef typename Traits::value_type Key;
     29   explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
     30     : m_table (n, ggc, GATHER_STATISTICS, HASH_SET_ORIGIN PASS_MEM_STAT) {}
     31 
     32   /* Create a hash_set in gc memory with space for at least n elements.  */
     33 
     34   static hash_set *
     35     create_ggc (size_t n)
     36       {
     37 	hash_set *set = ggc_alloc<hash_set> ();
     38 	new (set) hash_set (n, true);
     39 	return set;
     40       }
     41 
     42   /* If key k isn't already in the map add it to the map, and
     43      return false.  Otherwise return true.  */
     44 
     45   bool add (const Key &k)
     46     {
     47       Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
     48       bool existed = !Traits::is_empty (*e);
     49       if (!existed)
     50 	*e = k;
     51 
     52       return existed;
     53     }
     54 
     55   /* if the passed in key is in the map return its value otherwise NULL.  */
     56 
     57   bool contains (const Key &k)
     58     {
     59       Key &e = m_table.find_with_hash (k, Traits::hash (k));
     60       return !Traits::is_empty (e);
     61     }
     62 
     63   void remove (const Key &k)
     64     {
     65       m_table.remove_elt_with_hash (k, Traits::hash (k));
     66     }
     67 
     68   /* Call the call back on each pair of key and value with the passed in
     69      arg.  */
     70 
     71   template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)>
     72   void traverse (Arg a) const
     73     {
     74       for (typename hash_table<Traits>::iterator iter = m_table.begin ();
     75 	   iter != m_table.end (); ++iter)
     76 	f (*iter, a);
     77     }
     78 
     79   /* Return the number of elements in the set.  */
     80 
     81   size_t elements () const { return m_table.elements (); }
     82 
     83   class iterator
     84   {
     85   public:
     86     explicit iterator (const typename hash_table<Traits>::iterator &iter) :
     87       m_iter (iter) {}
     88 
     89     iterator &operator++ ()
     90       {
     91 	++m_iter;
     92 	return *this;
     93       }
     94 
     95     Key
     96     operator* ()
     97       {
     98 	return *m_iter;
     99       }
    100 
    101     bool
    102     operator != (const iterator &other) const
    103       {
    104 	return m_iter != other.m_iter;
    105       }
    106 
    107   private:
    108     typename hash_table<Traits>::iterator m_iter;
    109   };
    110 
    111   /* Standard iterator retrieval methods.  */
    112 
    113   iterator begin () const { return iterator (m_table.begin ()); }
    114   iterator end () const { return iterator (m_table.end ()); }
    115 
    116 
    117 private:
    118 
    119   template<typename T, typename U> friend void gt_ggc_mx (hash_set<T, U> *);
    120   template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *);
    121       template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, gt_pointer_operator, void *);
    122 
    123   hash_table<Traits> m_table;
    124 };
    125 
    126 /* ggc marking routines.  */
    127 
    128 template<typename K, typename H>
    129 static inline void
    130 gt_ggc_mx (hash_set<K, H> *h)
    131 {
    132   gt_ggc_mx (&h->m_table);
    133 }
    134 
    135 template<typename K, typename H>
    136 static inline void
    137 gt_pch_nx (hash_set<K, H> *h)
    138 {
    139   gt_pch_nx (&h->m_table);
    140 }
    141 
    142 template<typename K, typename H>
    143 static inline void
    144 gt_pch_nx (hash_set<K, H> *h, gt_pointer_operator op, void *cookie)
    145 {
    146   op (&h->m_table.m_entries, cookie);
    147 }
    148 
    149 #endif
    150