]>
git.ipfire.org Git - thirdparty/squid.git/blob - test-suite/hash.c
3 * DEBUG: section 00 Hash Tables
4 * AUTHOR: Harvest Derived
6 * SQUID Web Proxy Cache http://www.squid-cache.org/
7 * ----------------------------------------------------------
9 * Squid is the result of efforts by numerous individuals from
10 * the Internet community; see the CONTRIBUTORS file for full
11 * details. Many organizations have provided support for Squid's
12 * development; see the SPONSORS file for full details. Squid is
13 * Copyrighted (C) 2001 by the Regents of the University of
14 * California; see the COPYRIGHT file for full details. Squid
15 * incorporates software developed and/or copyrighted by other
16 * sources; see the CREDITS file for full details.
18 * This program is free software; you can redistribute it and/or modify
19 * it under the terms of the GNU General Public License as published by
20 * the Free Software Foundation; either version 2 of the License, or
21 * (at your option) any later version.
23 * This program is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * GNU General Public License for more details.
28 * You should have received a copy of the GNU General Public License
29 * along with this program; if not, write to the Free Software
30 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
54 extern void my_free(char *, int, void *);
56 #define free(a) my_free(__FILE__, __LINE__, a)
58 extern void print_stats();
60 * hash_url() - Returns a well-distributed hash function for URLs.
61 * The best way is to sum up the last half of the string.
62 * Adapted from code written by Mic Bowman. -Darren
63 * Generates a standard deviation = 15.73
66 hash_url(const void *data
, unsigned int size
)
71 for (i
= j
/ 2, n
= 0; i
< j
; i
++)
72 n
^= 271 * (unsigned) s
[i
];
78 hash_string(const void *data
, unsigned int size
)
86 n
^= 271 * (unsigned) *s
++;
92 /* the following 4 functions were adapted from
93 * usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
98 * Assume that we've already split the bucket to which this key hashes,
99 * calculate that bucket, and check that in fact we did already split it.
101 * This came from ejb's hsearch.
105 #define PRIME2 1048583
107 /* Hash function from Chris Torek. */
109 hash4(const void *data
, unsigned int size
)
111 const char *key
= data
;
116 #define HASH4a h = (h << 5) - h + *key++;
117 #define HASH4b h = (h << 5) + h + *key++;
122 loop
= (len
+ 8 - 1) >> 3;
123 switch (len
& (8 - 1)) {
154 * hash_create - creates a new hash table, uses the cmp_func
155 * to compare keys. Returns the identification for the hash table;
156 * otherwise returns a negative number on error.
159 hash_create(HASHCMP
* cmp_func
, int hash_sz
, HASHHASH
* hash_func
)
161 hash_table
*hid
= calloc(1, sizeof(hash_table
));
163 hid
->size
= (unsigned int) DEFAULT_HASH_SIZE
;
165 hid
->size
= (unsigned int) hash_sz
;
166 /* allocate and null the buckets */
167 hid
->buckets
= calloc(hid
->size
, sizeof(hash_link
*));
169 hid
->hash
= hash_func
;
170 hid
->current_ptr
= NULL
;
171 hid
->current_slot
= 0;
176 * hash_insert - inserts the given item 'item' under the given key 'k'
177 * into the hash table 'hid'. Returns non-zero on error; otherwise,
178 * returns 0 and inserts the item.
180 * It does not copy any data into the hash table, only pointers.
183 hash_insert(hash_table
* hid
, const char *k
, void *item
)
188 /* Add to the given hash table 'hid' */
189 new = calloc(1, sizeof(hash_link
));
191 fprintf(stderr
, "calloc failed!\n");
196 new->key
= (char *) k
;
197 i
= hid
->hash(k
, hid
->size
);
198 new->next
= hid
->buckets
[i
];
199 hid
->buckets
[i
] = new;
203 * hash_join - joins a hash_link under its key lnk->key
204 * into the hash table 'hid'.
206 * It does not copy any data into the hash table, only links pointers.
209 hash_join(hash_table
* hid
, hash_link
* lnk
)
212 i
= hid
->hash(lnk
->key
, hid
->size
);
213 lnk
->next
= hid
->buckets
[i
];
214 hid
->buckets
[i
] = lnk
;
218 * hash_lookup - locates the item under the key 'k' in the hash table
219 * 'hid'. Returns a pointer to the hash bucket on success; otherwise
223 hash_lookup(hash_table
* hid
, const void *k
)
228 b
= hid
->hash(k
, hid
->size
);
229 for (walker
= hid
->buckets
[b
]; walker
!= NULL
; walker
= walker
->next
) {
230 if ((hid
->cmp
) (k
, walker
->key
) == 0)
232 assert(walker
!= walker
->next
);
238 * hash_first - returns the first item in the hash table 'hid'.
239 * Otherwise, returns NULL on error.
242 hash_first(hash_table
* hid
)
246 for (i
= 0; i
< hid
->size
; i
++) {
247 hid
->current_slot
= i
;
248 if (hid
->buckets
[i
] != NULL
)
249 return (hid
->current_ptr
= hid
->buckets
[i
]);
255 * hash_next - returns the next item in the hash table 'hid'.
256 * Otherwise, returns NULL on error or end of list.
258 * MUST call hash_first() before hash_next().
261 hash_next(hash_table
* hid
)
265 if (hid
->current_ptr
!= NULL
) {
266 hid
->current_ptr
= hid
->current_ptr
->next
;
267 if (hid
->current_ptr
!= NULL
)
268 return (hid
->current_ptr
); /* next item */
270 /* find next bucket */
271 for (i
= hid
->current_slot
+ 1; i
< hid
->size
; i
++) {
272 hid
->current_slot
= i
;
273 if (hid
->buckets
[i
] != NULL
)
274 return (hid
->current_ptr
= hid
->buckets
[i
]);
276 return NULL
; /* end of list */
280 hash_delete(hash_table
* hid
, const char *key
)
282 return hash_delete_link(hid
, hash_lookup(hid
, key
));
286 * hash_delete_link - deletes the given hash_link node from the
287 * hash table 'hid'. If FreeLink then free the given hash_link.
289 * On success, it returns 0 and deletes the link; otherwise,
290 * returns non-zero on error.
293 hash_unlink(hash_table
* hid
, hash_link
* hl
, int FreeLink
)
295 hash_link
*walker
, *prev
;
299 i
= hid
->hash(hl
->key
, hid
->size
);
300 for (prev
= NULL
, walker
= hid
->buckets
[i
];
301 walker
!= NULL
; prev
= walker
, walker
= walker
->next
) {
303 if (prev
== NULL
) { /* it's the head */
304 hid
->buckets
[i
] = walker
->next
;
306 prev
->next
= walker
->next
; /* skip it */
308 /* fix walker state if needed */
309 if (walker
== hid
->current_ptr
)
310 hid
->current_ptr
= walker
->next
;
322 /* take link off and free link node */
324 hash_delete_link(hash_table
* hid
, hash_link
* hl
)
326 return (hash_unlink(hid
, hl
, 1));
329 /* take link off only */
331 hash_remove_link(hash_table
* hid
, hash_link
* hl
)
333 return (hash_unlink(hid
, hl
, 0));
337 * hash_get_bucket - returns the head item of the bucket
338 * in the hash table 'hid'. Otherwise, returns NULL on error.
341 hash_get_bucket(hash_table
* hid
, unsigned int bucket
)
343 if (bucket
>= hid
->size
)
345 return (hid
->buckets
[bucket
]);
349 hashFreeMemory(hash_table
* hid
)
359 * hash-driver - Run with a big file as stdin to insert each line into the
360 * hash table, then prints the whole hash table, then deletes a random item,
361 * and prints the table again...
368 LOCAL_ARRAY(char, buf
, BUFSIZ
);
369 LOCAL_ARRAY(char, todelete
, BUFSIZ
);
370 hash_link
*walker
= NULL
;
375 printf("creating hash table\n");
376 if ((hid
= hash_create(strcmp
, 229, hash_string
)) < 0) {
377 printf("hash_create error.\n");
380 printf("done creating hash table: %d\n", hid
);
382 while (fgets(buf
, BUFSIZ
, stdin
)) {
383 buf
[strlen(buf
) - 1] = '\0';
384 printf("Inserting '%s' for item %p to hash table: %d\n",
386 hash_insert(hid
, xstrdup(buf
), (void *) 0x12345678);
387 if (random() % 17 == 0)
388 strcpy(todelete
, buf
);
391 printf("walking hash table...\n");
392 for (i
= 0, walker
= hash_first(hid
); walker
; walker
= hash_next(hid
)) {
393 printf("item %5d: key: '%s' item: %p\n", i
++, walker
->key
,
396 printf("done walking hash table...\n");
399 printf("deleting %s from %d\n", todelete
, hid
);
400 if (hash_delete(hid
, todelete
))
401 printf("hash_delete error\n");
403 printf("walking hash table...\n");
404 for (i
= 0, walker
= hash_first(hid
); walker
; walker
= hash_next(hid
)) {
405 printf("item %5d: key: '%s' item: %p\n", i
++, walker
->key
,
408 printf("done walking hash table...\n");
410 printf("driver finished.\n");