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