1/* Copyright (C) 2012-2013 2 Free Software Foundation 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 Under Section 7 of GPL version 3, you are granted additional 17 permissions described in the GCC Runtime Library Exception, version 18 3.1, as published by the Free Software Foundation. 19 20 You should have received a copy of the GNU General Public License and 21 a copy of the GCC Runtime Library Exception along with this program; 22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 <http://www.gnu.org/licenses/>. */ 24 25#ifndef _VTV_MAP_H 26#define _VTV_MAP_H 1 27 28#include <string.h> 29 30#ifdef __MINGW32__ 31#include <stdint.h> 32#include "vtv_utils.h" 33#else 34#include <vtv_utils.h> 35#endif 36 37inline uint64_t 38load8bytes (const void *p) 39{ 40 uint64_t result; 41 memcpy (&result, p, 8); 42 return result; 43} 44 45/* Insert_only_hash_map maps keys to values. The implementation is a 46 basic hash table with open addressing. The keys are not "owned" by 47 the table; it only stores pointers to keys. The key type is 48 specified below (see insert_only_hash_map::key_type) and is, 49 roughly speaking, a string of any length with the string length and 50 a hash code stored at the front. The code here does not compute 51 any hash codes, but rather uses what's given. */ 52 53template<typename T, typename Alloc> 54class insert_only_hash_map 55 { 56 public: 57 typedef size_t size_type; 58 typedef T value_type; 59 typedef Alloc alloc_type; 60 enum { min_capacity = 4 }; 61#if HASHMAP_STATS 62 enum { stats = true }; 63#else 64 enum { stats = false }; 65#endif 66 67 /* Keys are a byte string (up to 2^32 - 1 long) plus a uint32_t 68 that's used as a hash code. The latter can encode arbitrary 69 information at the client's discretion, so, e.g., multiple keys 70 that are the same string still "differ" if the hash codes differ. 71 Keys are equal if the first 8 bytes are equal and the next n 72 bytes are equal. */ 73 struct key_type 74 { 75 uint32_t n; 76 uint32_t hash; 77 char bytes[0]; 78 79 bool 80 equals (const key_type *k) const; 81 }; 82 83 /* Create an empty map with a reasonable number of buckets for the 84 expected size. Returns NULL if the allocator fails. */ 85 86 static insert_only_hash_map * 87 create (size_type expected_size); 88 89 /* The opposite of create(). Free the memory for the given map. */ 90 91 static void 92 destroy (insert_only_hash_map *m) 93 { Alloc().dealloc (m, m->size_in_bytes_); } 94 95 /* Return a map identical to this except that *k is mapped to v. 96 Typcially it's done by modifying this in place, but if a resize 97 is necessary then this is deallocated and a new map is returned. 98 Requires k to be non-NULL. Does nothing and returns NULL if the 99 allocator fails. */ 100 101 insert_only_hash_map* 102 put (const key_type *k, const value_type &v) 103 { return this->put_internal (k, v, false); } 104 105 /* If *k is a key in this then set *v to point to the corresponding 106 value. Otherwise, do the equivalent of insert(k, value_type()) 107 and, if that succeeds, set *v to point to the inserted value. 108 Requires k to be non-NULL. Does nothing and returns NULL if the 109 allocator fails. Typically returns this, but will return a new 110 insert_only_hash_map if a resize occurs. If the return value is 111 non-NULL, *v is set and it's valid until a resize of the map that 112 is the return value. */ 113 114 insert_only_hash_map * 115 find_or_add_key (const key_type *k, value_type **v); 116 117 /* Get the value corresponding to *k. Returns NULL if there is 118 none. Requires k to be non-NULL. The return value is valid 119 until any resize. */ 120 const value_type *get (const key_type *k) const; 121 122 size_type 123 size () const 124 { return num_entries_; } 125 126 bool 127 empty () const 128 { return this->size () == 0; } 129 130 size_type 131 bucket_count () const 132 { return num_buckets_; } 133 134 private: 135 typedef std::pair <const key_type *, value_type> bucket_type; 136 137 insert_only_hash_map *put_internal (const key_type *, const value_type &, 138 bool); 139 140 /* This function determines when to resize the table. */ 141 bool 142 is_too_full (size_type entries) const 143 { return entries > (this->bucket_count () * 0.7); } 144 145 /* Return a copy with double the number of buckets. Returns NULL if 146 the allocator fails. Otherwise, calls destroy (this). */ 147 insert_only_hash_map *destructive_copy (); 148 149 /* Must be a power of 2 not less than min_capacity. */ 150 size_type num_buckets_; 151 size_type num_entries_; 152 size_type size_in_bytes_; 153 bucket_type buckets[0]; /* Actual array size is num_buckets. */ 154}; 155 156template <typename T, typename Alloc> 157insert_only_hash_map <T, Alloc> * 158insert_only_hash_map <T, Alloc>::create (size_type expected_size) 159{ 160 size_t cap = min_capacity; 161 while (expected_size >= cap) 162 { 163 cap *= 2; 164 } 165 size_t size_in_bytes = sizeof (insert_only_hash_map <T, Alloc>) 166 + cap * sizeof (bucket_type); 167 insert_only_hash_map <T, Alloc>* result = 168 static_cast <insert_only_hash_map <T, Alloc>*> (Alloc () 169 .alloc (size_in_bytes)); 170 if (result != NULL) 171 { 172 result->size_in_bytes_ = size_in_bytes; 173 result->num_buckets_ = cap; 174 result->num_entries_ = 0; 175 memset (result->buckets, 0, cap * sizeof (bucket_type)); 176 } 177 return result; 178} 179 180template <typename T, typename Alloc> 181insert_only_hash_map <T, Alloc>* 182insert_only_hash_map <T, Alloc>::destructive_copy () 183{ 184 insert_only_hash_map* copy = create (this->bucket_count ()); 185 if (copy == NULL) 186 return NULL; 187 VTV_DEBUG_ASSERT (copy->bucket_count () == 2 * this->bucket_count ()); 188 for (size_type i = 0; i < this->bucket_count (); i++) 189 if (this->buckets[i].first != NULL) 190 copy->put_internal (this->buckets[i].first, this->buckets[i].second, 191 true); 192 VTV_DEBUG_ASSERT (copy->size () == this->size ()); 193 destroy (this); 194 return copy; 195} 196 197template <typename T, typename Alloc> 198insert_only_hash_map <T, Alloc>* 199insert_only_hash_map <T, Alloc>::find_or_add_key (const key_type *k, 200 value_type **v) 201{ 202 /* Table size is always a power of 2. */ 203 const size_type mask = this->bucket_count () - 1; 204 size_type bucket_index = k->hash & mask; 205 size_type step = 1; 206 for (;;) 207 { 208 bucket_type &bucket = this->buckets[bucket_index]; 209 if (bucket.first == NULL) 210 { 211 /* Key was not present. */ 212 if (this->is_too_full (this->size () + 1)) 213 { 214 insert_only_hash_map <T, Alloc>* result = 215 this->destructive_copy (); 216 return result == NULL 217 ? NULL 218 : result->find_or_add_key (k, v); 219 } 220 else 221 { 222 bucket.first = k; 223 bucket.second = T (); 224 this->num_entries_++; 225 *v = &bucket.second; 226 return this; 227 } 228 } 229 else if (bucket.first->equals (k)) 230 { 231 /* Key was present. */ 232 *v = &bucket.second; 233 return this; 234 } 235 else 236 bucket_index = (bucket_index + step++) & mask; 237 } 238} 239 240template <typename T, typename Alloc> 241insert_only_hash_map <T, Alloc>* 242insert_only_hash_map <T, Alloc>::put_internal ( 243 const insert_only_hash_map::key_type *k, 244 const insert_only_hash_map::value_type &v, 245 bool unique_key_and_resize_not_needed) 246{ 247 /* Table size is always a power of 2. */ 248 const size_type mask = this->bucket_count () - 1; 249 size_type bucket_index = k->hash & mask; 250 size_type step = 1; 251 for (;;) 252 { 253 bucket_type &bucket = this->buckets[bucket_index]; 254 if (bucket.first == NULL) 255 { 256 /* Key was not present. */ 257 if (!unique_key_and_resize_not_needed 258 && this->is_too_full (this->size () + 1)) 259 { 260 insert_only_hash_map <T, Alloc>* result = 261 this->destructive_copy (); 262 return result == NULL 263 ? NULL 264 : result->put_internal (k, v, true); 265 } 266 else 267 { 268 bucket.first = k; 269 bucket.second = v; 270 this->num_entries_++; 271 return this; 272 } 273 } 274 else if (!unique_key_and_resize_not_needed && bucket.first->equals (k)) 275 { 276 /* Key was present. Just change the value. */ 277 bucket.second = v; 278 return this; 279 } 280 else 281 bucket_index = (bucket_index + step++) & mask; 282 } 283} 284 285template <typename T, typename Alloc> 286inline const typename insert_only_hash_map <T, Alloc>::value_type* 287insert_only_hash_map <T, Alloc>::get (const insert_only_hash_map::key_type *k) 288 const 289{ 290 /* Table size is always a power of 2. */ 291 const size_type mask = this->bucket_count () - 1; 292 size_type bucket_index = k->hash & mask; 293 size_type step = 1; 294 for (;;) 295 { 296 const bucket_type &bucket = this->buckets[bucket_index]; 297 if (bucket.first == NULL) 298 return NULL; 299 else if (bucket.first->equals (k)) 300 return &bucket.second; 301 else 302 bucket_index = (bucket_index + step++) & mask; 303 } 304} 305 306template <typename T, typename Alloc> 307inline bool 308insert_only_hash_map <T, Alloc>::key_type::equals ( 309 const typename insert_only_hash_map <T, Alloc>::key_type *k) const 310{ 311 const char* x = reinterpret_cast <const char *> (k); 312 const char* y = reinterpret_cast <const char *> (this); 313 return (load8bytes (x) == load8bytes (y) 314 && memcmp (x + 8, y + 8, this->n) == 0); 315} 316 317#endif /* _VTV_MAP_H */ 318