1
2/*--------------------------------------------------------------------*/
3/*--- A separately-chained hash table.               m_hashtable.c ---*/
4/*--------------------------------------------------------------------*/
5
6/*
7   This file is part of Valgrind, a dynamic binary instrumentation
8   framework.
9
10   Copyright (C) 2005-2013 Nicholas Nethercote
11      njn@valgrind.org
12
13   This program is free software; you can redistribute it and/or
14   modify it under the terms of the GNU General Public License as
15   published by the Free Software Foundation; either version 2 of the
16   License, or (at your option) any later version.
17
18   This program is distributed in the hope that it will be useful, but
19   WITHOUT ANY WARRANTY; without even the implied warranty of
20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21   General Public License for more details.
22
23   You should have received a copy of the GNU General Public License
24   along with this program; if not, write to the Free Software
25   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26   02111-1307, USA.
27
28   The GNU General Public License is contained in the file COPYING.
29*/
30
31#include "pub_core_basics.h"
32#include "pub_core_debuglog.h"
33#include "pub_core_hashtable.h"
34#include "pub_core_libcassert.h"
35#include "pub_core_mallocfree.h"
36
37/*--------------------------------------------------------------------*/
38/*--- Declarations                                                 ---*/
39/*--------------------------------------------------------------------*/
40
41#define CHAIN_NO(key,tbl) (((UWord)(key)) % tbl->n_chains)
42
43struct _VgHashTable {
44   UInt         n_chains;   // should be prime
45   UInt         n_elements;
46   VgHashNode*  iterNode;   // current iterator node
47   UInt         iterChain;  // next chain to be traversed by the iterator
48   VgHashNode** chains;     // expanding array of hash chains
49   Bool         iterOK;     // table safe to iterate over?
50   const HChar* name;       // name of table (for debugging only)
51};
52
53#define N_HASH_PRIMES 20
54
55static SizeT primes[N_HASH_PRIMES] = {
56         769UL,         1543UL,         3079UL,          6151UL,
57       12289UL,        24593UL,        49157UL,         98317UL,
58      196613UL,       393241UL,       786433UL,       1572869UL,
59     3145739UL,      6291469UL,     12582917UL,      25165843UL,
60    50331653UL,    100663319UL,    201326611UL,     402653189UL
61};
62
63/*--------------------------------------------------------------------*/
64/*--- Functions                                                    ---*/
65/*--------------------------------------------------------------------*/
66
67VgHashTable VG_(HT_construct) ( const HChar* name )
68{
69   /* Initialises to zero, ie. all entries NULL */
70   SizeT       n_chains = primes[0];
71   SizeT       sz       = n_chains * sizeof(VgHashNode*);
72   VgHashTable table    = VG_(calloc)("hashtable.Hc.1",
73                                      1, sizeof(struct _VgHashTable));
74   table->chains        = VG_(calloc)("hashtable.Hc.2", 1, sz);
75   table->n_chains      = n_chains;
76   table->n_elements    = 0;
77   table->iterOK        = True;
78   table->name          = name;
79   vg_assert(name);
80   return table;
81}
82
83Int VG_(HT_count_nodes) ( VgHashTable table )
84{
85   return table->n_elements;
86}
87
88static void resize ( VgHashTable table )
89{
90   Int          i;
91   SizeT        sz;
92   SizeT        old_chains = table->n_chains;
93   SizeT        new_chains = old_chains + 1;
94   VgHashNode** chains;
95   VgHashNode * node;
96
97   /* If we've run out of primes, do nothing. */
98   if (old_chains == primes[N_HASH_PRIMES-1])
99      return;
100
101   vg_assert(old_chains >= primes[0]
102             && old_chains < primes[N_HASH_PRIMES-1]);
103
104   for (i = 0; i < N_HASH_PRIMES; i++) {
105      if (primes[i] > new_chains) {
106         new_chains = primes[i];
107         break;
108      }
109   }
110
111   vg_assert(new_chains > old_chains);
112   vg_assert(new_chains > primes[0]
113             && new_chains <= primes[N_HASH_PRIMES-1]);
114
115   VG_(debugLog)(
116      1, "hashtable",
117         "resizing table `%s' from %lu to %lu (total elems %lu)\n",
118         table->name, (UWord)old_chains, (UWord)new_chains,
119         (UWord)table->n_elements );
120
121   table->n_chains = new_chains;
122   sz = new_chains * sizeof(VgHashNode*);
123   chains = VG_(calloc)("hashtable.resize.1", 1, sz);
124
125   for (i = 0; i < old_chains; i++) {
126      node = table->chains[i];
127      while (node != NULL) {
128         VgHashNode* next = node->next;
129         UWord chain = CHAIN_NO(node->key, table);
130         node->next = chains[chain];
131         chains[chain] = node;
132         node = next;
133      }
134   }
135
136   VG_(free)(table->chains);
137   table->chains = chains;
138}
139
140/* Puts a new, heap allocated VgHashNode, into the VgHashTable.  Prepends
141   the node to the appropriate chain.  No duplicate key detection is done. */
142void VG_(HT_add_node) ( VgHashTable table, void* vnode )
143{
144   VgHashNode* node     = (VgHashNode*)vnode;
145   UWord chain          = CHAIN_NO(node->key, table);
146   node->next           = table->chains[chain];
147   table->chains[chain] = node;
148   table->n_elements++;
149   if ( (1 * (ULong)table->n_elements) > (1 * (ULong)table->n_chains) ) {
150      resize(table);
151   }
152
153   /* Table has been modified; hence HT_Next should assert. */
154   table->iterOK = False;
155}
156
157/* Looks up a VgHashNode in the table.  Returns NULL if not found. */
158void* VG_(HT_lookup) ( VgHashTable table, UWord key )
159{
160   VgHashNode* curr = table->chains[ CHAIN_NO(key, table) ];
161
162   while (curr) {
163      if (key == curr->key) {
164         return curr;
165      }
166      curr = curr->next;
167   }
168   return NULL;
169}
170
171/* Removes a VgHashNode from the table.  Returns NULL if not found. */
172void* VG_(HT_remove) ( VgHashTable table, UWord key )
173{
174   UWord        chain         = CHAIN_NO(key, table);
175   VgHashNode*  curr          =   table->chains[chain];
176   VgHashNode** prev_next_ptr = &(table->chains[chain]);
177
178   /* Table has been modified; hence HT_Next should assert. */
179   table->iterOK = False;
180
181   while (curr) {
182      if (key == curr->key) {
183         *prev_next_ptr = curr->next;
184         table->n_elements--;
185         return curr;
186      }
187      prev_next_ptr = &(curr->next);
188      curr = curr->next;
189   }
190   return NULL;
191}
192
193/* Allocates a suitably-sized array, copies pointers to all the hashtable
194   elements into it, then returns both the array and the size of it.  The
195   array must be freed with VG_(free).
196*/
197VgHashNode** VG_(HT_to_array) ( VgHashTable table, /*OUT*/ UInt* n_elems )
198{
199   UInt       i, j;
200   VgHashNode** arr;
201   VgHashNode*  node;
202
203   *n_elems = table->n_elements;
204   if (*n_elems == 0)
205      return NULL;
206
207   arr = VG_(malloc)( "hashtable.Hta.1", *n_elems * sizeof(VgHashNode*) );
208
209   j = 0;
210   for (i = 0; i < table->n_chains; i++) {
211      for (node = table->chains[i]; node != NULL; node = node->next) {
212         arr[j++] = node;
213      }
214   }
215   vg_assert(j == *n_elems);
216
217   return arr;
218}
219
220void VG_(HT_ResetIter)(VgHashTable table)
221{
222   vg_assert(table);
223   table->iterNode  = NULL;
224   table->iterChain = 0;
225   table->iterOK    = True;
226}
227
228void* VG_(HT_Next)(VgHashTable table)
229{
230   Int i;
231   vg_assert(table);
232   /* See long comment on HT_Next prototype in pub_tool_hashtable.h.
233      In short if this fails, it means the caller tried to modify the
234      table whilst iterating over it, which is a bug. */
235   vg_assert(table->iterOK);
236
237   if (table->iterNode && table->iterNode->next) {
238      table->iterNode = table->iterNode->next;
239      return table->iterNode;
240   }
241
242   for (i = table->iterChain; i < table->n_chains; i++) {
243      if (table->chains[i]) {
244         table->iterNode  = table->chains[i];
245         table->iterChain = i + 1;  // Next chain to be traversed
246         return table->iterNode;
247      }
248   }
249   return NULL;
250}
251
252void VG_(HT_destruct)(VgHashTable table, void(*freenode_fn)(void*))
253{
254   UInt       i;
255   VgHashNode *node, *node_next;
256
257   for (i = 0; i < table->n_chains; i++) {
258      for (node = table->chains[i]; node != NULL; node = node_next) {
259         node_next = node->next;
260         freenode_fn(node);
261      }
262   }
263   VG_(free)(table->chains);
264   VG_(free)(table);
265}
266
267/*--------------------------------------------------------------------*/
268/*--- end                                                          ---*/
269/*--------------------------------------------------------------------*/
270