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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors