cloudy  trunk
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
hash.cpp
Go to the documentation of this file.
1 /* This file is part of Cloudy and is copyright (C)1978-2008 by Gary J. Ferland and
2  * others. For conditions of distribution and use see copyright notice in license.txt */
3 #include "cddefines.h"
4 #include "hash.h"
5 
6 /* Implement sorted linear hash table -- automatically expands to
7  * get uniform bin filling, requires good hash function as 2^n masking is used.
8  *
9  * References
10  *
11  * W. Litwin, Linear hashing: A new tool for file and table addressing,
12  * Proc. 6th Conference on Very Large Databases, pages 212-223, 1980.
13  *
14  * http://www.concentric.net/~Ttwang/tech/sorthash.htm
15  *
16  */
17 
18 /* Function to calculate 4 byte hash index -- must be good for 2^n table */
19 STATIC unsigned long hashfunction(const void *t, const size_t len);
20 
21 /* Internal utility functions for hash table */
22 STATIC entry *lookup_key(const void *key, size_t *lkey, const hashtab *table,
23  unsigned long *hk);
24 STATIC void extend(hashtab *table);
25 STATIC unsigned long getbin(unsigned long hk, const hashtab *table);
26 
27 
28 hashtab *newhash(void (*freedata)(void *))
29 {
30  hashtab *self;
31 
32  DEBUG_ENTRY("newhash()");
33 
34  self = (hashtab *) MALLOC(sizeof(hashtab));
35  self->freedata = freedata;
36  self->nelem = 0;
37  self->size = 0x1;
38  self->fullmask = 0x1;
39  self->frontmask = 0x0;
40  self->space = 128;
41  self->hashfunction = hashfunction;
42  self->tab = (entry **) MALLOC(self->space*sizeof(entry *));
43  self->tab[0] = NULL;
44 
45  return self;
46 }
47 
48 void freehash(hashtab *table)
49 {
50  entry *s, *t;
51  unsigned long i;
52 
53  DEBUG_ENTRY("freehash()");
54 
55  for(i=0;i<table->size;i++)
56  {
57  s = table->tab[i];
58  while (s != NULL)
59  {
60  t = s->next;
61  if(table->freedata != NULL)
62  {
63  table->freedata(s->data.p);
64  }
65  free(s);
66  s = t;
67  }
68  }
69 
70  free(table->tab);
71  free(table);
72 }
73 
74 data_u *addentry(const void *key, size_t lkey, hashtab *table, int *exists)
75 {
76  unsigned long hk, i;
77  entry *s;
78  void *p;
79 
80  DEBUG_ENTRY("addentry()");
81 
82  s = lookup_key(key,&lkey,table,&hk);
83  if(s)
84  {
85  *exists = 1;
86  return &(s->data);
87  }
88 
89  *exists = 0;
90  p = MALLOC(sizeof(entry)+lkey);
91  s = (entry *) p;
92  s->hashval = hk;
93  s->data.lkey = lkey;
94  s->data.key = (void *)(((char *)p)+sizeof(entry));
95  memcpy(s->data.key,key,lkey);
96 
97  i = getbin(hk,table);
98  s->next = table->tab[i];
99  table->tab[i] = s;
100 
101  table->nelem++;
102 
103  extend(table);
104 
105  return &(s->data);
106 }
107 
108 data_u *lookup(const void *key, size_t lkey, const hashtab *table)
109 {
110  unsigned long hk;
111  entry *s;
112 
113  if(table->nelem == 0)
114  return NULL;
115  s = lookup_key(key,&lkey,table,&hk);
116  if(s == NULL)
117  return NULL;
118  return &(s->data);
119 }
120 
121 int maxchain(const hashtab *table)
122 {
123  unsigned long i, l, max=0;
124  entry *s;
125 
126  DEBUG_ENTRY("maxchain()");
127 
128  for(i=0;i<table->size;i++)
129  {
130  l = 0;
131  for(s = table->tab[i];s != NULL;s=s->next)
132  {
133  l++;
134  }
135  if(l > max)
136  max = l;
137  }
138 
139  return max;
140 }
141 
142 /* Internal utility functions */
143 /* Bernstein hash, see:
144  http://www.cse.yorku.ca/~oz/hash.html
145  http://www.burtleburtle.net/bob/hash/doobs.html
146 */
147 enum {HASHINIT=5381,HASHMUL=33}; /* Bernstein */
148 /* enum {HASHINIT=0,HASHMUL=131}; */
149 STATIC unsigned long hashfunction(const void *t, const size_t len)
150 {
151  size_t i;
152  unsigned long h = HASHINIT;
153  unsigned char *s = (unsigned char *)t;
154 
155  DEBUG_ENTRY("hashfunction()");
156 
157  for( i=0; i<len; i++ )
158  h = HASHMUL*h + s[i];
159 
160  return( h );
161 }
162 
163 STATIC entry *lookup_key(const void *key, size_t *lkey, const hashtab *table,
164  unsigned long *hk)
165 {
166  unsigned long i;
167  entry *s;
168 
169  DEBUG_ENTRY("lookup_key()");
170 
171  if(*lkey == 0)
172  *lkey = strlen((char *) key)+1;
173 
174  *hk = table->hashfunction(key,*lkey);
175  i = getbin(*hk,table);
176 
177  /* Look through list within bin */
178  for(s = table->tab[i];s!=NULL;s=s->next)
179  {
180  /* Check for match -- full hash value will likely distinguish */
181  if(*hk == s->hashval &&
182  *lkey == s->data.lkey &&
183  !memcmp(key,s->data.key,*lkey))
184  {
185  return s;
186  }
187  }
188  return NULL;
189 }
190 
191 STATIC void extend(hashtab *table)
192 {
193  unsigned long move, last, i, j;
194  entry *t, *s;
195 
196  DEBUG_ENTRY("extend()");
197  last = table->size;
198  table->size++;
199  if(last > table->fullmask)
200  { /* Extend table when full */
201  table->frontmask = table->fullmask;
202  table->fullmask <<= 1;
203  table->fullmask |= 1;
204  if(table->fullmask+1 > table->space)
205  {
206  table->space = table->fullmask+1;
207  table->tab = (entry **)
208  REALLOC(table->tab,(table->space)*sizeof(entry *));
209  }
210  }
211 
212  /* Split next bin in front part */
213  i = last & table->frontmask;
214  t = table->tab[i];
215  table->tab[last] = table->tab[i] = NULL;
216  move = table->frontmask ^ table->fullmask;
217  while (t)
218  { /* Go through list and sort between [last] and [i] */
219  if(t->hashval & move)
220  {
221  j = last;
222  }
223  else
224  {
225  j = i;
226  }
227  s = t->next;
228  t->next = table->tab[j];
229  table->tab[j] = t;
230  t = s;
231  }
232 }
233 
234 STATIC unsigned long getbin(unsigned long hk, const hashtab *table)
235 {
236  unsigned long i;
237 
238  DEBUG_ENTRY("getbin()");
239  i = hk & table->fullmask;
240  if(i >= table->size)
241  i &= table->frontmask;
242  assert (i < table->size && i < table->space);
243  return i;
244 }
245 
246 /* Copy data from hash into list,
247  optionally selected according to a masking function */
248 unsigned long makelist(const hashtab *table, data_u **list,
249  const unsigned long nlist, int (*maskfun)(data_u *dat))
250 {
251  unsigned long i, n;
252  entry *s;
253 
254  DEBUG_ENTRY("makelist()");
255 
256  n = 0;
257  for(i=0;i<table->size;i++)
258  {
259  for(s = table->tab[i];s != NULL;s = s->next)
260  {
261  if(maskfun == NULL || maskfun(&(s->data)))
262  list[n++] = &(s->data);
263  if(n > nlist)
264  {
265  fprintf(ioQQQ,"Too many list items for array provided in makelist\n");
266  cdEXIT(EXIT_FAILURE);
267  }
268  }
269  }
270  return n;
271 }
272 unsigned long makeplist(const hashtab *table, void **list,
273  const unsigned long nlist, int (*maskfun)(data_u *dat))
274 {
275  unsigned long i, n;
276  entry *s;
277 
278  DEBUG_ENTRY("makeplist()");
279  n = 0;
280  for(i=0;i<table->size;i++)
281  {
282  for(s = table->tab[i];s != NULL;s = s->next)
283  {
284  if(maskfun == NULL || maskfun(&(s->data)))
285  list[n++] = s->data.p;
286  if(n > nlist)
287  {
288  fprintf(ioQQQ,"Too many list items for array provided in makeplist\n");
289  cdEXIT(EXIT_FAILURE);
290  }
291  }
292  }
293  return n;
294 }
295 
296 #ifdef TEST
297 main()
298 {
299  hashtab *table;
300  data_u *data;
301  int i, exists;
302 
303  char strings[][15] = {"Hello","Goodbye","Thirteen","One",
304  "Two","Three","Four","Five","Six",
305  "Seven","Eight"};
306 
307  table = newhash(NULL);
308  for(i=0;i<sizeof(strings)/15;i++)
309  {
310  data = addentry(strings[i],0,table,&exists);
311  data->i = i;
312  }
313 
314  for(i=0;i<sizeof(strings)/15;i++)
315  {
316  data = lookup(strings[i],0,table);
317  if(data)
318  {
319  printf("Found data %d\n",data->i);
320  }
321  else
322  {
323  printf("Couldn't find data\n");
324  }
325  }
326  data = lookup("Banana",0,table);
327  if(data)
328  {
329  printf("Found data %d\n",data->i);
330  }
331  else
332  {
333  printf("Couldn't find data (as expected)\n");
334  }
335  printf("Longest chain is %d\n",maxchain(table));
336 }
337 #endif

Generated for cloudy by doxygen 1.8.4