]>
git.ipfire.org Git - thirdparty/squid.git/blob - lib/hash.cc
f807ae5daaedaaa91d9abe6c6b6d4be0f6289cdd
2 * Copyright (C) 1996-2014 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 00 Hash Tables */
13 #include "profiler/Profiler.h"
23 #include <gnumalloc.h>
28 static void hash_next_bucket(hash_table
* hid
);
31 hash_string(const void *data
, unsigned int size
)
33 const unsigned char *s
= static_cast<const unsigned char *>(data
);
46 /* the following function(s) were adapted from
47 * usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
49 /* Hash function from Chris Torek. */
51 hash4(const void *data
, unsigned int size
)
53 const char *key
= static_cast<const char *>(data
);
58 #define HASH4a h = (h << 5) - h + *key++;
59 #define HASH4b h = (h << 5) + h + *key++;
65 switch (len
& (8 - 1)) {
104 * hash_create - creates a new hash table, uses the cmp_func
105 * to compare keys. Returns the identification for the hash table;
106 * otherwise returns a negative number on error.
109 hash_create(HASHCMP
* cmp_func
, int hash_sz
, HASHHASH
* hash_func
)
111 hash_table
*hid
= (hash_table
*)xcalloc(1, sizeof(hash_table
));
113 hid
->size
= (unsigned int) DEFAULT_HASH_SIZE
;
115 hid
->size
= (unsigned int) hash_sz
;
116 /* allocate and null the buckets */
117 hid
->buckets
= (hash_link
**)xcalloc(hid
->size
, sizeof(hash_link
*));
119 hid
->hash
= hash_func
;
121 hid
->current_slot
= 0;
126 * hash_join - joins a hash_link under its key lnk->key
127 * into the hash table 'hid'.
129 * It does not copy any data into the hash table, only links pointers.
132 hash_join(hash_table
* hid
, hash_link
* lnk
)
135 i
= hid
->hash(lnk
->key
, hid
->size
);
136 lnk
->next
= hid
->buckets
[i
];
137 hid
->buckets
[i
] = lnk
;
142 * hash_lookup - locates the item under the key 'k' in the hash table
143 * 'hid'. Returns a pointer to the hash bucket on success; otherwise
147 hash_lookup(hash_table
* hid
, const void *k
)
150 PROF_start(hash_lookup
);
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) {
155 PROF_stop(hash_lookup
);
158 assert(walker
!= walker
->next
);
160 PROF_stop(hash_lookup
);
165 hash_next_bucket(hash_table
* hid
)
167 while (hid
->next
== NULL
&& ++hid
->current_slot
< hid
->size
)
168 hid
->next
= hid
->buckets
[hid
->current_slot
];
172 * hash_first - initializes the hash table for the hash_next()
176 hash_first(hash_table
* hid
)
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
);
186 * hash_next - returns the next item in the hash table 'hid'.
187 * Otherwise, returns NULL on error or end of list.
189 * MUST call hash_first() before hash_next().
192 hash_next(hash_table
* hid
)
194 hash_link
*p
= hid
->next
;
198 if (NULL
== hid
->next
)
199 hash_next_bucket(hid
);
204 * hash_last - resets hash traversal state to NULL
208 hash_last(hash_table
* hid
)
212 hid
->current_slot
= 0;
216 * hash_remove_link - deletes the given hash_link node from the
217 * hash table 'hid'. Does not free the item, only removes it
220 * An assertion is triggered if the hash_link is not found in the
224 hash_remove_link(hash_table
* hid
, hash_link
* hl
)
227 int i
= hid
->hash(hl
->key
, hid
->size
);
228 for (hash_link
**P
= &hid
->buckets
[i
]; *P
; P
= &(*P
)->next
) {
232 if (hid
->next
== hl
) {
233 hid
->next
= hl
->next
;
234 if (NULL
== hid
->next
)
235 hash_next_bucket(hid
);
244 * hash_get_bucket - returns the head item of the bucket
245 * in the hash table 'hid'. Otherwise, returns NULL on error.
248 hash_get_bucket(hash_table
* hid
, unsigned int bucket
)
250 if (bucket
>= hid
->size
)
252 return (hid
->buckets
[bucket
]);
256 hashFreeItems(hash_table
* hid
, HASHFREE
* free_func
)
260 hash_link
**list
= (hash_link
**)xcalloc(hid
->count
, sizeof(hash_link
*));
262 while ((l
= hash_next(hid
)) && i
< hid
->count
) {
266 for (int j
= 0; j
< i
; ++j
)
267 free_func(*(list
+ j
));
272 hashFreeMemory(hash_table
* hid
)
281 static int hash_primes
[] = {
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]));
303 for (int i
= 0; i
< I
; ++i
) {
304 d
= fabs(log((double) n
) - log((double) hash_primes
[i
]));
308 best_prime
= hash_primes
[i
];
314 * return the key of a hash_link as a const string
317 hashKeyStr(hash_link
* hl
)
319 return (const char *) hl
->key
;
324 * hash-driver - Run with a big file as stdin to insert each line into the
325 * hash table, then prints the whole hash table, then deletes a random item,
326 * and prints the table again...
332 LOCAL_ARRAY(char, buf
, BUFSIZ
);
333 LOCAL_ARRAY(char, todelete
, BUFSIZ
);
334 hash_link
*walker
= NULL
;
339 printf("creating hash table\n");
340 if ((hid
= hash_create((HASHCMP
*) strcmp
, 229, hash4
)) < 0) {
341 printf("hash_create error.\n");
344 printf("done creating hash table: %d\n", hid
);
346 while (fgets(buf
, BUFSIZ
, stdin
)) {
347 buf
[strlen(buf
) - 1] = '\0';
348 printf("Inserting '%s' for item %p to hash table: %d\n",
350 hash_insert(hid
, xstrdup(buf
), (void *) 0x12345678);
351 if (random() % 17 == 0)
352 strcpy(todelete
, buf
);
355 printf("walking hash table...\n");
356 for (int i
= 0, walker
= hash_first(hid
); walker
; walker
= hash_next(hid
)) {
357 printf("item %5d: key: '%s' item: %p\n", i
++, walker
->key
,
360 printf("done walking hash table...\n");
363 printf("deleting %s from %d\n", todelete
, hid
);
364 if (hash_delete(hid
, todelete
))
365 printf("hash_delete error\n");
367 printf("walking hash table...\n");
368 for (int i
= 0, walker
= hash_first(hid
); walker
; walker
= hash_next(hid
)) {
369 printf("item %5d: key: '%s' item: %p\n", i
++, walker
->key
,
372 printf("done walking hash table...\n");
374 printf("driver finished.\n");