hash.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 /* DEBUG: section 00 Hash Tables */
10 
11 #include "squid.h"
12 #include "hash.h"
13 #include "profiler/Profiler.h"
14 
15 #include <cassert>
16 #include <cmath>
17 #include <cstdlib>
18 #include <cstring>
19 #if HAVE_UNISTD_H
20 #include <unistd.h>
21 #endif
22 #if HAVE_GNUMALLLOC_H
23 #include <gnumalloc.h>
24 #elif HAVE_MALLOC_H
25 #include <malloc.h>
26 #endif
27 
28 static void hash_next_bucket(hash_table * hid);
29 
30 unsigned int
31 hash_string(const void *data, unsigned int size)
32 {
33  const unsigned char *s = static_cast<const unsigned char *>(data);
34  unsigned int n = 0;
35  unsigned int j = 0;
36  unsigned int i = 0;
37  while (*s) {
38  ++j;
39  n ^= 271 * *s;
40  ++s;
41  }
42  i = n ^ (j * 271);
43  return i % size;
44 }
45 
46 /* the following function(s) were adapted from
47  * usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
48 
49 /* Hash function from Chris Torek. */
50 unsigned int
51 hash4(const void *data, unsigned int size)
52 {
53  const char *key = static_cast<const char *>(data);
54  size_t loop;
55  unsigned int h;
56  size_t len;
57 
58 #define HASH4a h = (h << 5) - h + *key++;
59 #define HASH4b h = (h << 5) + h + *key++;
60 #define HASH4 HASH4b
61 
62  h = 0;
63  len = strlen(key);
64  loop = len >> 3;
65  switch (len & (8 - 1)) {
66  case 0:
67  break;
68  case 7:
69  HASH4;
70  /* FALLTHROUGH */
71  case 6:
72  HASH4;
73  /* FALLTHROUGH */
74  case 5:
75  HASH4;
76  /* FALLTHROUGH */
77  case 4:
78  HASH4;
79  /* FALLTHROUGH */
80  case 3:
81  HASH4;
82  /* FALLTHROUGH */
83  case 2:
84  HASH4;
85  /* FALLTHROUGH */
86  case 1:
87  HASH4;
88  }
89  while (loop) {
90  --loop;
91  HASH4;
92  HASH4;
93  HASH4;
94  HASH4;
95  HASH4;
96  HASH4;
97  HASH4;
98  HASH4;
99  }
100  return h % size;
101 }
102 
108 hash_table *
109 hash_create(HASHCMP * cmp_func, int hash_sz, HASHHASH * hash_func)
110 {
111  hash_table *hid = (hash_table *)xcalloc(1, sizeof(hash_table));
112  if (!hash_sz)
113  hid->size = (unsigned int) DEFAULT_HASH_SIZE;
114  else
115  hid->size = (unsigned int) hash_sz;
116  /* allocate and null the buckets */
117  hid->buckets = (hash_link **)xcalloc(hid->size, sizeof(hash_link *));
118  hid->cmp = cmp_func;
119  hid->hash = hash_func;
120  hid->next = NULL;
121  hid->current_slot = 0;
122  return hid;
123 }
124 
131 void
133 {
134  int i;
135  i = hid->hash(lnk->key, hid->size);
136  lnk->next = hid->buckets[i];
137  hid->buckets[i] = lnk;
138  ++hid->count;
139 }
140 
146 hash_link *
147 hash_lookup(hash_table * hid, const void *k)
148 {
149  int b;
151  assert(k != NULL);
152  b = hid->hash(k, hid->size);
153  for (hash_link *walker = hid->buckets[b]; walker != NULL; walker = walker->next) {
154  if ((hid->cmp) (k, walker->key) == 0) {
156  return (walker);
157  }
158  assert(walker != walker->next);
159  }
161  return NULL;
162 }
163 
164 static void
166 {
167  while (hid->next == NULL && ++hid->current_slot < hid->size)
168  hid->next = hid->buckets[hid->current_slot];
169 }
170 
175 void
177 {
178  assert(NULL == hid->next);
179  hid->current_slot = 0;
180  hid->next = hid->buckets[hid->current_slot];
181  if (NULL == hid->next)
182  hash_next_bucket(hid);
183 }
184 
191 hash_link *
193 {
194  hash_link *p = hid->next;
195  if (NULL == p)
196  return NULL;
197  hid->next = p->next;
198  if (NULL == hid->next)
199  hash_next_bucket(hid);
200  return p;
201 }
202 
207 void
209 {
210  assert(hid != NULL);
211  hid->next = NULL;
212  hid->current_slot = 0;
213 }
214 
223 void
225 {
226  assert(hl != NULL);
227  int i = hid->hash(hl->key, hid->size);
228  for (hash_link **P = &hid->buckets[i]; *P; P = &(*P)->next) {
229  if (*P != hl)
230  continue;
231  *P = hl->next;
232  if (hid->next == hl) {
233  hid->next = hl->next;
234  if (NULL == hid->next)
235  hash_next_bucket(hid);
236  }
237  --hid->count;
238  return;
239  }
240  assert(0);
241 }
242 
247 hash_link *
248 hash_get_bucket(hash_table * hid, unsigned int bucket)
249 {
250  if (bucket >= hid->size)
251  return NULL;
252  return (hid->buckets[bucket]);
253 }
254 
255 void
256 hashFreeItems(hash_table * hid, HASHFREE * free_func)
257 {
258  hash_link *l;
259  int i = 0;
260  hash_link **list = (hash_link **)xcalloc(hid->count, sizeof(hash_link *));
261  hash_first(hid);
262  while ((l = hash_next(hid)) && i < hid->count) {
263  *(list + i) = l;
264  ++i;
265  }
266  for (int j = 0; j < i; ++j)
267  free_func(*(list + j));
268  xfree(list);
269 }
270 
271 void
273 {
274  if (hid == NULL)
275  return;
276  if (hid->buckets)
277  xfree(hid->buckets);
278  xfree(hid);
279 }
280 
281 static int hash_primes[] = {
282  103,
283  229,
284  467,
285  977,
286  1979,
287  4019,
288  6037,
289  7951,
290  12149,
291  16231,
292  33493,
293  65357
294 };
295 
296 int
297 hashPrime(int n)
298 {
299  int I = sizeof(hash_primes) / sizeof(int);
300  int best_prime = hash_primes[0];
301  double min = fabs(log((double) n) - log((double) hash_primes[0]));
302  double d;
303  for (int i = 0; i < I; ++i) {
304  d = fabs(log((double) n) - log((double) hash_primes[i]));
305  if (d > min)
306  continue;
307  min = d;
308  best_prime = hash_primes[i];
309  }
310  return best_prime;
311 }
312 
316 const char *
318 {
319  return (const char *) hl->key;
320 }
321 
322 #if USE_HASH_DRIVER
323 
328 int
329 main(void)
330 {
331  hash_table *hid;
332  LOCAL_ARRAY(char, buf, BUFSIZ);
333  LOCAL_ARRAY(char, todelete, BUFSIZ);
334  hash_link *walker = NULL;
335 
336  todelete[0] = '\0';
337  printf("init\n");
338 
339  printf("creating hash table\n");
340  if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
341  printf("hash_create error.\n");
342  exit(EXIT_FAILURE);
343  }
344  printf("done creating hash table: %d\n", hid);
345 
346  std::mt19937 mt;
347  xuniform_int_distribution<> dist(0,16);
348 
349  while (fgets(buf, BUFSIZ, stdin)) {
350  buf[strlen(buf) - 1] = '\0';
351  printf("Inserting '%s' for item %p to hash table: %d\n",
352  buf, buf, hid);
353  hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
354  if (dist(mt) == 0)
355  strcpy(todelete, buf);
356  }
357 
358  printf("walking hash table...\n");
359  for (int i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
360  printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
361  walker->item);
362  }
363  printf("done walking hash table...\n");
364 
365  if (todelete[0]) {
366  printf("deleting %s from %d\n", todelete, hid);
367  if (hash_delete(hid, todelete))
368  printf("hash_delete error\n");
369  }
370  printf("walking hash table...\n");
371  for (int i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
372  printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
373  walker->item);
374  }
375  printf("done walking hash table...\n");
376 
377  printf("driver finished.\n");
378  return EXIT_SUCCESS;
379 }
380 #endif
381 
static int hash_primes[]
Definition: hash.cc:281
#define assert(EX)
Definition: assert.h:17
int main(int, char *[])
Definition: unitTestMain.h:25
unsigned int HASHHASH(const void *, unsigned int)
Definition: hash.h:14
hash_link * hash_next(hash_table *hid)
Definition: hash.cc:192
HASHCMP * cmp
Definition: hash.h:26
#define xcalloc
Definition: membanger.c:57
void log(char *format,...)
int i
Definition: membanger.c:49
static void hash_next_bucket(hash_table *hid)
Definition: hash.cc:165
#define xstrdup
#define HASH4
unsigned int hash_string(const void *data, unsigned int size)
Definition: hash.cc:31
hash_link * next
Definition: hash.h:30
void hash_last(hash_table *hid)
Definition: hash.cc:208
char * p
Definition: membanger.c:43
void hashFreeMemory(hash_table *hid)
Definition: hash.cc:272
int hashPrime(int n)
Definition: hash.cc:297
void hash_join(hash_table *hid, hash_link *lnk)
Definition: hash.cc:132
void hash_insert(hash_table *hid, const char *k, void *item)
Definition: hash.c:158
void const char HLPCB void * data
Definition: stub_helper.cc:16
void hash_first(hash_table *hid)
Definition: hash.cc:176
unsigned int current_slot
Definition: hash.h:29
hash_link * hash_get_bucket(hash_table *hid, unsigned int bucket)
Definition: hash.cc:248
void hash_remove_link(hash_table *hid, hash_link *hl)
Definition: hash.cc:224
const char * hashKeyStr(hash_link *hl)
Definition: hash.cc:317
hash_link * hash_lookup(hash_table *hid, const void *k)
Definition: hash.cc:147
#define LOCAL_ARRAY(type, name, size)
Definition: leakcheck.h:18
#define BUFSIZ
Definition: defines.h:20
int unsigned int const char *desc STUB void int len
Definition: stub_fd.cc:20
hash_link ** buckets
Definition: hash.h:25
void const char * buf
Definition: stub_helper.cc:16
void HASHFREE(void *)
Definition: hash.h:12
bool SIGHDLR int STUB void int
Definition: stub_tools.cc:68
HASHHASH * hash
Definition: hash.h:27
#define PROF_start(probename)
Definition: Profiler.h:62
void const cache_key * key
hash_table * hash_create(HASHCMP *cmp_func, int hash_sz, HASHHASH *hash_func)
Definition: hash.cc:109
int count
Definition: hash.h:31
#define PROF_stop(probename)
Definition: Profiler.h:63
void hashFreeItems(hash_table *hid, HASHFREE *free_func)
Definition: hash.cc:256
#define xfree
int hash_delete(hash_table *hid, const char *key)
Definition: hash.c:255
#define DEFAULT_HASH_SIZE
Definition: hash.h:66
unsigned int size
Definition: hash.h:28
unsigned int hash4(const void *data, unsigned int size)
Definition: hash.cc:51
#define NULL
Definition: types.h:166
int size
Definition: ModDevPoll.cc:77
A const & min(A const &lhs, A const &rhs)
int HASHCMP(const void *, const void *)
Definition: hash.h:13

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors