gcc/hash-set.h

   1 /* A type-safe hash set.
   2    Copyright (C) 2014 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 #include "hash-table.h"
  25
  26 /* implement default behavior for traits when types allow it.  */
  27
  28 struct default_hashset_traits
  29 {
  30   /* Hashes the passed in key.  */
  31
  32   template<typename T>
  33   static hashval_t
  34   hash (T *p)
  35     {
  36       return uintptr_t(p) >> 3;
  37     }
  38
  39   template<typename T> static hashval_t hash(const T &v) { return v; }
  40
  41   /* Return true if the two keys passed as arguments are equal.  */
  42
  43   template<typename T>
  44   static bool
  45   equal (const T &a, const T &b)
  46     {
  47       return a == b;
  48     }
  49
  50   /* Called to dispose of the key before marking the entry as deleted.  */
  51
  52   template<typename T> static void remove (T &v) { v.~T (); }
  53
  54   /* Mark the passed in entry as being deleted.  */
  55
  56   template<typename T>
  57   static void
  58   mark_deleted (T *&e)
  59     {
  60       e = reinterpret_cast<void *> (1);
  61     }
  62
  63   /* Mark the passed in entry as being empty.  */
  64
  65   template<typename T>
  66   static void
  67   mark_empty (T *&e)
  68     {
  69       e = NULL;
  70     }
  71
  72   /* Return true if the passed in entry is marked as deleted.  */
  73
  74   template<typename T>
  75   static bool
  76   is_deleted (T *e)
  77     {
  78       return e == reinterpret_cast<void *> (1);
  79     }
  80
  81   /* Return true if the passed in entry is marked as empty.  */
  82
  83   template<typename T> static bool is_empty (T *e) { return e == NULL; }
  84 };
  85
  86 template<typename Key, typename Traits = default_hashset_traits>
  87 class hash_set
  88 {
  89   struct hash_entry
  90   {
  91     Key m_key;
  92
  93     typedef hash_entry value_type;
  94     typedef Key compare_type;
  95     typedef int store_values_directly;
  96
  97     static hashval_t hash (const hash_entry &e)
  98       {
  99         return Traits::hash (e.m_key);
 100       }
 101
 102     static bool equal (const hash_entry &a, const Key &b)
 103         {
 104           return Traits::equal (a.m_key, b);
 105         }
 106
 107     static void remove (hash_entry &e) { Traits::remove (e.m_key); }
 108
 109     static void
 110     mark_deleted (hash_entry &e)
 111       {
 112         Traits::mark_deleted (e.m_key);
 113       }
 114
 115     static bool is_deleted (const hash_entry &e)
 116       {
 117         return Traits::is_deleted (e.m_key);
 118       }
 119
 120     static void
 121     mark_empty (hash_entry &e)
 122       {
 123         Traits::mark_empty (e.m_key);
 124       }
 125
 126     static bool
 127     is_empty (const hash_entry &e)
 128       {
 129         return Traits::is_empty (e.m_key);
 130       }
 131   };
 132
 133 public:
 134   explicit hash_set (size_t n = 13) : m_table (n) {}
 135
 136   /* If key k isn't already in the map add it to the map, and
 137      return false.  Otherwise return true.  */
 138
 139   bool add (const Key &k)
 140     {
 141       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 142                                                    INSERT);
 143       bool existed = !hash_entry::is_empty (*e);
 144       if (!existed)
 145         e->m_key = k;
 146
 147       return existed;
 148     }
 149
 150   /* if the passed in key is in the map return its value otherwise NULL.  */
 151
 152   bool contains (const Key &k)
 153     {
 154       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 155       return !Traits::is_empty (e.m_key);
 156     }
 157
 158   /* Call the call back on each pair of key and value with the passed in
 159      arg.  */
 160
 161   template<typename Arg, bool (*f)(const Key &, Arg)>
 162   void traverse (Arg a) const
 163     {
 164       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 165            iter != m_table.end (); ++iter)
 166         f ((*iter).m_key, a);
 167     }
 168
 169 private:
 170   hash_table<hash_entry> m_table;
 171 };
 172
 173 #endif