m_hashtable.c revision 81c00df9ac724e898179dd90e52b2e15deb11fd8 
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) 2000-2005 Julian Seward
11      jseward@acm.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 "core.h"
32#include "pub_core_hashtable.h"
33
34/*--------------------------------------------------------------------*/
35/*--- Declarations                                                 ---*/
36/*--------------------------------------------------------------------*/
37
38/* Holds malloc'd but not freed blocks.  Static, so zero-inited by default. */
39
40#define VG_N_CHAINS 4999 /* a prime number */
41
42#define VG_CHAIN_NO(aa) (((UWord)(aa)) % VG_N_CHAINS)
43
44/*--------------------------------------------------------------------*/
45/*--- Functions                                                    ---*/
46/*--------------------------------------------------------------------*/
47
48VgHashTable VG_(HT_construct)(void)
49{
50   /* Initialises to zero, ie. all entries NULL */
51   return VG_(calloc)(VG_N_CHAINS, sizeof(VgHashNode*));
52}
53
54Int VG_(HT_count_nodes) ( VgHashTable table )
55{
56   VgHashNode* node;
57   UInt      chain;
58   Int       n = 0;
59
60   for (chain = 0; chain < VG_N_CHAINS; chain++)
61      for (node = table[chain]; node != NULL; node = node->next)
62         n++;
63   return n;
64}
65
66/* Puts a new, heap allocated VgHashNode, into the malloclist. */
67void VG_(HT_add_node) ( VgHashTable table, VgHashNode* node )
68{
69   UInt chain   = VG_CHAIN_NO(node->key);
70   node->next   = table[chain];
71   table[chain] = node;
72}
73
74/* Looks up a VgHashNode in the table.  Also returns the address of
75   the previous node's `next' pointer which allows it to be removed from the
76   list later without having to look it up again.  */
77VgHashNode* VG_(HT_get_node) ( VgHashTable table, UWord key,
78                             /*OUT*/VgHashNode*** next_ptr )
79{
80   VgHashNode *prev, *curr;
81   Int       chain;
82
83   chain = VG_CHAIN_NO(key);
84
85   prev = NULL;
86   curr = table[chain];
87   while (True) {
88      if (curr == NULL)
89         break;
90      if (key == curr->key)
91         break;
92      prev = curr;
93      curr = curr->next;
94   }
95
96   if (NULL == prev)
97      *next_ptr = & table[chain];
98   else
99      *next_ptr = & prev->next;
100
101   return curr;
102}
103
104/* Allocates a suitably-sized array, copies all the malloc'd block
105   shadows into it, then returns both the array and the size of it.  This is
106   used by the memory-leak detector.
107*/
108VgHashNode** VG_(HT_to_array) ( VgHashTable table, /*OUT*/ UInt* n_shadows )
109{
110   UInt       i, j;
111   VgHashNode** arr;
112   VgHashNode*  node;
113
114   *n_shadows = 0;
115   for (i = 0; i < VG_N_CHAINS; i++) {
116      for (node = table[i]; node != NULL; node = node->next) {
117         (*n_shadows)++;
118      }
119   }
120   if (*n_shadows == 0)
121      return NULL;
122
123   arr = VG_(malloc)( *n_shadows * sizeof(VgHashNode*) );
124
125   j = 0;
126   for (i = 0; i < VG_N_CHAINS; i++) {
127      for (node = table[i]; node != NULL; node = node->next) {
128         arr[j++] = node;
129      }
130   }
131   vg_assert(j == *n_shadows);
132
133   return arr;
134}
135
136/* Return the first VgHashNode satisfying the predicate p. */
137VgHashNode* VG_(HT_first_match) ( VgHashTable table,
138                                  Bool (*p) ( VgHashNode*, void* ),
139                                  void* d )
140{
141   UInt      i;
142   VgHashNode* node;
143
144   for (i = 0; i < VG_N_CHAINS; i++)
145      for (node = table[i]; node != NULL; node = node->next)
146         if ( p(node, d) )
147            return node;
148
149   return NULL;
150}
151
152void VG_(HT_apply_to_all_nodes)( VgHashTable table,
153                                 void (*f)(VgHashNode*, void*),
154                                 void* d )
155{
156   UInt      i;
157   VgHashNode* node;
158
159   for (i = 0; i < VG_N_CHAINS; i++) {
160      for (node = table[i]; node != NULL; node = node->next) {
161         f(node, d);
162      }
163   }
164}
165
166void VG_(HT_destruct)(VgHashTable table)
167{
168   UInt      i;
169   VgHashNode* node;
170
171   for (i = 0; i < VG_N_CHAINS; i++) {
172      for (node = table[i]; node != NULL; node = node->next) {
173         VG_(free)(node);
174      }
175   }
176   VG_(free)(table);
177}
178
179/*--------------------------------------------------------------------*/
180/*--- end                                                          ---*/
181/*--------------------------------------------------------------------*/
182