gcc/hash-map-traits.h

   1 /* A hash map traits.
   2    Copyright (C) 2015 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 #ifndef HASH_MAP_TRAITS_H
  21 #define HASH_MAP_TRAITS_H
  22
  23 /* Bacause mem-stats.h uses default hashmap traits, we have to
  24    put the class to this separate header file.  */
  25
  26 #include "hash-traits.h"
  27
  28 /* implement default behavior for traits when types allow it.  */
  29
  30 struct default_hashmap_traits
  31 {
  32   /* Hashes the passed in key.  */
  33
  34   template<typename T>
  35   static hashval_t
  36   hash (T *p)
  37     {
  38       return uintptr_t (p) >> 3;
  39     }
  40
  41   /* If the value converts to hashval_t just use it.  */
  42
  43   template<typename T> static hashval_t hash (T v) { return v; }
  44
  45   /* Return true if the two keys passed as arguments are equal.  */
  46
  47   template<typename T>
  48   static bool
  49   equal_keys (const T &a, const T &b)
  50     {
  51       return a == b;
  52     }
  53
  54   /* Called to dispose of the key and value before marking the entry as
  55      deleted.  */
  56
  57   template<typename T> static void remove (T &v) { v.~T (); }
  58
  59   /* Mark the passed in entry as being deleted.  */
  60
  61   template<typename T>
  62   static void
  63   mark_deleted (T &e)
  64     {
  65       mark_key_deleted (e.m_key);
  66     }
  67
  68   /* Mark the passed in entry as being empty.  */
  69
  70   template<typename T>
  71   static void
  72   mark_empty (T &e)
  73     {
  74       mark_key_empty (e.m_key);
  75     }
  76
  77   /* Return true if the passed in entry is marked as deleted.  */
  78
  79   template<typename T>
  80   static bool
  81   is_deleted (T &e)
  82     {
  83       return e.m_key == (void *)1;
  84     }
  85
  86   /* Return true if the passed in entry is marked as empty.  */
  87
  88   template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
  89
  90 private:
  91   template<typename T>
  92   static void
  93   mark_key_deleted (T *&k)
  94     {
  95       k = reinterpret_cast<T *> (1);
  96     }
  97
  98   template<typename T>
  99   static void
 100   mark_key_empty (T *&k)
 101     {
 102       k = static_cast<T *> (0);
 103     }
 104 };
 105
 106 /* Implement hash_map traits for a key with hash traits H.  Empty and
 107    deleted map entries are represented as empty and deleted keys.  */
 108
 109 template <typename H>
 110 struct simple_hashmap_traits
 111 {
 112   static inline hashval_t hash (const typename H::value_type &);
 113   static inline bool equal_keys (const typename H::value_type &,
 114                                  const typename H::value_type &);
 115   template <typename T> static inline void remove (T &);
 116   template <typename T> static inline bool is_empty (const T &);
 117   template <typename T> static inline bool is_deleted (const T &);
 118   template <typename T> static inline void mark_empty (T &);
 119   template <typename T> static inline void mark_deleted (T &);
 120 };
 121
 122 template <typename H>
 123 inline hashval_t
 124 simple_hashmap_traits <H>::hash (const typename H::value_type &h)
 125 {
 126   return H::hash (h);
 127 }
 128
 129 template <typename H>
 130 inline bool
 131 simple_hashmap_traits <H>::equal_keys (const typename H::value_type &k1,
 132                                        const typename H::value_type &k2)
 133 {
 134   return H::equal (k1, k2);
 135 }
 136
 137 template <typename H>
 138 template <typename T>
 139 inline void
 140 simple_hashmap_traits <H>::remove (T &entry)
 141 {
 142   H::remove (entry.m_key);
 143 }
 144
 145 template <typename H>
 146 template <typename T>
 147 inline bool
 148 simple_hashmap_traits <H>::is_empty (const T &entry)
 149 {
 150   return H::is_empty (entry.m_key);
 151 }
 152
 153 template <typename H>
 154 template <typename T>
 155 inline bool
 156 simple_hashmap_traits <H>::is_deleted (const T &entry)
 157 {
 158   return H::is_deleted (entry.m_key);
 159 }
 160
 161 template <typename H>
 162 template <typename T>
 163 inline void
 164 simple_hashmap_traits <H>::mark_empty (T &entry)
 165 {
 166   H::mark_empty (entry.m_key);
 167 }
 168
 169 template <typename H>
 170 template <typename T>
 171 inline void
 172 simple_hashmap_traits <H>::mark_deleted (T &entry)
 173 {
 174   H::mark_deleted (entry.m_key);
 175 }
 176
 177 #endif // HASH_MAP_TRAITS_H