]>
git.ipfire.org Git - thirdparty/squid.git/blob - test-suite/hash.c
5 * DEBUG: section 0 Hash Tables
6 * AUTHOR: Harvest Derived
8 * SQUID Web Proxy Cache http://www.squid-cache.org/
9 * ----------------------------------------------------------
11 * Squid is the result of efforts by numerous individuals from
12 * the Internet community; see the CONTRIBUTORS file for full
13 * details. Many organizations have provided support for Squid's
14 * development; see the SPONSORS file for full details. Squid is
15 * Copyrighted (C) 2001 by the Regents of the University of
16 * California; see the COPYRIGHT file for full details. Squid
17 * incorporates software developed and/or copyrighted by other
18 * sources; see the CREDITS file for full details.
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License as published by
22 * the Free Software Foundation; either version 2 of the License, or
23 * (at your option) any later version.
25 * This program is distributed in the hope that it will be useful,
26 * but WITHOUT ANY WARRANTY; without even the implied warranty of
27 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 * GNU General Public License for more details.
30 * You should have received a copy of the GNU General Public License
31 * along with this program; if not, write to the Free Software
32 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
39 #include <sys/types.h>
46 extern void my_free(char *, int, void *);
48 #define free(a) my_free(__FILE__, __LINE__, a)
50 extern void print_stats();
52 * hash_url() - Returns a well-distributed hash function for URLs.
53 * The best way is to sum up the last half of the string.
54 * Adapted from code written by Mic Bowman. -Darren
55 * Generates a standard deviation = 15.73
58 hash_url(const void *data
, unsigned int size
)
63 for (i
= j
/ 2, n
= 0; i
< j
; i
++)
64 n
^= 271 * (unsigned) s
[i
];
70 hash_string(const void *data
, unsigned int size
)
78 n
^= 271 * (unsigned) *s
++;
84 /* the following 4 functions were adapted from
85 * usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
90 * Assume that we've already split the bucket to which this key hashes,
91 * calculate that bucket, and check that in fact we did already split it.
93 * This came from ejb's hsearch.
97 #define PRIME2 1048583
99 /* Hash function from Chris Torek. */
101 hash4(const void *data
, unsigned int size
)
103 const char *key
= data
;
108 #define HASH4a h = (h << 5) - h + *key++;
109 #define HASH4b h = (h << 5) + h + *key++;
114 loop
= (len
+ 8 - 1) >> 3;
115 switch (len
& (8 - 1)) {
146 * hash_create - creates a new hash table, uses the cmp_func
147 * to compare keys. Returns the identification for the hash table;
148 * otherwise returns a negative number on error.
151 hash_create(HASHCMP
* cmp_func
, int hash_sz
, HASHHASH
* hash_func
)
153 hash_table
*hid
= calloc(1, sizeof(hash_table
));
155 hid
->size
= (unsigned int) DEFAULT_HASH_SIZE
;
157 hid
->size
= (unsigned int) hash_sz
;
158 /* allocate and null the buckets */
159 hid
->buckets
= calloc(hid
->size
, sizeof(hash_link
*));
161 hid
->hash
= hash_func
;
162 hid
->current_ptr
= NULL
;
163 hid
->current_slot
= 0;
168 * hash_insert - inserts the given item 'item' under the given key 'k'
169 * into the hash table 'hid'. Returns non-zero on error; otherwise,
170 * returns 0 and inserts the item.
172 * It does not copy any data into the hash table, only pointers.
175 hash_insert(hash_table
* hid
, const char *k
, void *item
)
180 /* Add to the given hash table 'hid' */
181 new = calloc(1, sizeof(hash_link
));
183 fprintf(stderr
, "calloc failed!\n");
188 new->key
= (char *) k
;
189 i
= hid
->hash(k
, hid
->size
);
190 new->next
= hid
->buckets
[i
];
191 hid
->buckets
[i
] = new;
195 * hash_join - joins a hash_link under its key lnk->key
196 * into the hash table 'hid'.
198 * It does not copy any data into the hash table, only links pointers.
201 hash_join(hash_table
* hid
, hash_link
* lnk
)
204 i
= hid
->hash(lnk
->key
, hid
->size
);
205 lnk
->next
= hid
->buckets
[i
];
206 hid
->buckets
[i
] = lnk
;
210 * hash_lookup - locates the item under the key 'k' in the hash table
211 * 'hid'. Returns a pointer to the hash bucket on success; otherwise
215 hash_lookup(hash_table
* hid
, const void *k
)
220 b
= hid
->hash(k
, hid
->size
);
221 for (walker
= hid
->buckets
[b
]; walker
!= NULL
; walker
= walker
->next
) {
222 if ((hid
->cmp
) (k
, walker
->key
) == 0)
224 assert(walker
!= walker
->next
);
230 * hash_first - returns the first item in the hash table 'hid'.
231 * Otherwise, returns NULL on error.
234 hash_first(hash_table
* hid
)
238 for (i
= 0; i
< hid
->size
; i
++) {
239 hid
->current_slot
= i
;
240 if (hid
->buckets
[i
] != NULL
)
241 return (hid
->current_ptr
= hid
->buckets
[i
]);
247 * hash_next - returns the next item in the hash table 'hid'.
248 * Otherwise, returns NULL on error or end of list.
250 * MUST call hash_first() before hash_next().
253 hash_next(hash_table
* hid
)
257 if (hid
->current_ptr
!= NULL
) {
258 hid
->current_ptr
= hid
->current_ptr
->next
;
259 if (hid
->current_ptr
!= NULL
)
260 return (hid
->current_ptr
); /* next item */
262 /* find next bucket */
263 for (i
= hid
->current_slot
+ 1; i
< hid
->size
; i
++) {
264 hid
->current_slot
= i
;
265 if (hid
->buckets
[i
] != NULL
)
266 return (hid
->current_ptr
= hid
->buckets
[i
]);
268 return NULL
; /* end of list */
272 hash_delete(hash_table
* hid
, const char *key
)
274 return hash_delete_link(hid
, hash_lookup(hid
, key
));
278 * hash_delete_link - deletes the given hash_link node from the
279 * hash table 'hid'. If FreeLink then free the given hash_link.
281 * On success, it returns 0 and deletes the link; otherwise,
282 * returns non-zero on error.
285 hash_unlink(hash_table
* hid
, hash_link
* hl
, int FreeLink
)
287 hash_link
*walker
, *prev
;
291 i
= hid
->hash(hl
->key
, hid
->size
);
292 for (prev
= NULL
, walker
= hid
->buckets
[i
];
293 walker
!= NULL
; prev
= walker
, walker
= walker
->next
) {
295 if (prev
== NULL
) { /* it's the head */
296 hid
->buckets
[i
] = walker
->next
;
298 prev
->next
= walker
->next
; /* skip it */
300 /* fix walker state if needed */
301 if (walker
== hid
->current_ptr
)
302 hid
->current_ptr
= walker
->next
;
314 /* take link off and free link node */
316 hash_delete_link(hash_table
* hid
, hash_link
* hl
)
318 return (hash_unlink(hid
, hl
, 1));
321 /* take link off only */
323 hash_remove_link(hash_table
* hid
, hash_link
* hl
)
325 return (hash_unlink(hid
, hl
, 0));
329 * hash_get_bucket - returns the head item of the bucket
330 * in the hash table 'hid'. Otherwise, returns NULL on error.
333 hash_get_bucket(hash_table
* hid
, unsigned int bucket
)
335 if (bucket
>= hid
->size
)
337 return (hid
->buckets
[bucket
]);
342 hashFreeMemory(hash_table
* hid
)
351 #ifdef USE_HASH_DRIVER
353 * hash-driver - Run with a big file as stdin to insert each line into the
354 * hash table, then prints the whole hash table, then deletes a random item,
355 * and prints the table again...
362 LOCAL_ARRAY(char, buf
, BUFSIZ
);
363 LOCAL_ARRAY(char, todelete
, BUFSIZ
);
364 hash_link
*walker
= NULL
;
369 printf("creating hash table\n");
370 if ((hid
= hash_create(strcmp
, 229, hash_string
)) < 0) {
371 printf("hash_create error.\n");
374 printf("done creating hash table: %d\n", hid
);
376 while (fgets(buf
, BUFSIZ
, stdin
)) {
377 buf
[strlen(buf
) - 1] = '\0';
378 printf("Inserting '%s' for item %p to hash table: %d\n",
380 hash_insert(hid
, xstrdup(buf
), (void *) 0x12345678);
381 if (random() % 17 == 0)
382 strcpy(todelete
, buf
);
385 printf("walking hash table...\n");
386 for (i
= 0, walker
= hash_first(hid
); walker
; walker
= hash_next(hid
)) {
387 printf("item %5d: key: '%s' item: %p\n", i
++, walker
->key
,
390 printf("done walking hash table...\n");
393 printf("deleting %s from %d\n", todelete
, hid
);
394 if (hash_delete(hid
, todelete
))
395 printf("hash_delete error\n");
397 printf("walking hash table...\n");
398 for (i
= 0, walker
= hash_first(hid
); walker
; walker
= hash_next(hid
)) {
399 printf("item %5d: key: '%s' item: %p\n", i
++, walker
->key
,
402 printf("done walking hash table...\n");
405 printf("driver finished.\n");