hash.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 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
27static void hash_next_bucket(hash_table * hid);
28
29unsigned int
30hash_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. */
49unsigned int
50hash4(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
108hash_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 = nullptr;
120 hid->current_slot = 0;
121 return hid;
122}
123
130void
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
145hash_link *
146hash_lookup(hash_table * hid, const void *k)
147{
148 int b;
149 assert(k != nullptr);
150 b = hid->hash(k, hid->size);
151 for (hash_link *walker = hid->buckets[b]; walker != nullptr; walker = walker->next) {
152 if ((hid->cmp) (k, walker->key) == 0) {
153 return (walker);
154 }
155 assert(walker != walker->next);
156 }
157 return nullptr;
158}
159
160static void
162{
163 while (hid->next == nullptr && ++hid->current_slot < hid->size)
164 hid->next = hid->buckets[hid->current_slot];
165}
166
171void
173{
174 assert(nullptr == hid->next);
175 hid->current_slot = 0;
176 hid->next = hid->buckets[hid->current_slot];
177 if (nullptr == hid->next)
178 hash_next_bucket(hid);
179}
180
187hash_link *
189{
190 hash_link *p = hid->next;
191 if (nullptr == p)
192 return nullptr;
193 hid->next = p->next;
194 if (nullptr == hid->next)
195 hash_next_bucket(hid);
196 return p;
197}
198
203void
205{
206 assert(hid != nullptr);
207 hid->next = nullptr;
208 hid->current_slot = 0;
209}
210
219void
221{
222 assert(hl != nullptr);
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 (nullptr == hid->next)
231 hash_next_bucket(hid);
232 }
233 --hid->count;
234 return;
235 }
236 assert(0);
237}
238
243hash_link *
244hash_get_bucket(hash_table * hid, unsigned int bucket)
245{
246 if (bucket >= hid->size)
247 return nullptr;
248 return (hid->buckets[bucket]);
249}
250
251void
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
267void
269{
270 if (hid == nullptr)
271 return;
272 if (hid->buckets)
273 xfree(hid->buckets);
274 xfree(hid);
275}
276
277static 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
292int
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
312const char *
314{
315 return (const char *) hl->key;
316}
317
318#if USE_HASH_DRIVER
324int
325main(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
int size
Definition: ModDevPoll.cc:75
void log(char *format,...)
#define assert(EX)
Definition: assert.h:19
unsigned int size
Definition: hash.h:28
int count
Definition: hash.h:31
unsigned int current_slot
Definition: hash.h:29
hash_link ** buckets
Definition: hash.h:25
hash_link * next
Definition: hash.h:30
HASHCMP * cmp
Definition: hash.h:26
HASHHASH * hash
Definition: hash.h:27
A const & min(A const &lhs, A const &rhs)
#define BUFSIZ
Definition: defines.h:20
hash_link * hash_lookup(hash_table *hid, const void *k)
Definition: hash.cc:146
void hashFreeMemory(hash_table *hid)
Definition: hash.cc:268
static int hash_primes[]
Definition: hash.cc:277
const char * hashKeyStr(const hash_link *hl)
Definition: hash.cc:313
#define HASH4
hash_link * hash_next(hash_table *hid)
Definition: hash.cc:188
void hash_remove_link(hash_table *hid, hash_link *hl)
Definition: hash.cc:220
static void hash_next_bucket(hash_table *hid)
Definition: hash.cc:161
hash_table * hash_create(HASHCMP *cmp_func, int hash_sz, HASHHASH *hash_func)
Definition: hash.cc:108
hash_link * hash_get_bucket(hash_table *hid, unsigned int bucket)
Definition: hash.cc:244
unsigned int hash4(const void *data, unsigned int size)
Definition: hash.cc:50
void hashFreeItems(hash_table *hid, HASHFREE *free_func)
Definition: hash.cc:252
void hash_first(hash_table *hid)
Definition: hash.cc:172
int hashPrime(int n)
Definition: hash.cc:293
void hash_join(hash_table *hid, hash_link *lnk)
Definition: hash.cc:131
void hash_last(hash_table *hid)
Definition: hash.cc:204
unsigned int hash_string(const void *data, unsigned int size)
Definition: hash.cc:30
void HASHFREE(void *)
Definition: hash.h:12
int HASHCMP(const void *, const void *)
Definition: hash.h:13
unsigned int HASHHASH(const void *, unsigned int)
Definition: hash.h:14
#define DEFAULT_HASH_SIZE
Definition: hash.h:66
#define xfree
#define xstrdup
#define LOCAL_ARRAY(type, name, size)
Definition: squid.h:68
int unsigned int
Definition: stub_fd.cc:19
#define NULL
Definition: types.h:166
int main(int, char *[])
Definition: unitTestMain.h:25
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors