hash.c (173412) | hash.c (201227) |
---|---|
1/* $FreeBSD: head/sbin/rcorder/hash.c 173412 2007-11-07 10:53:41Z kevlo $ */ | 1/* $FreeBSD: head/sbin/rcorder/hash.c 201227 2009-12-29 22:53:27Z ed $ */ |
2/* $NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $ */ 3 4/* 5 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 6 * Copyright (c) 1988, 1989 by Adam de Boor 7 * Copyright (c) 1989 by Berkeley Softworks 8 * All rights reserved. 9 * --- 88 unchanged lines hidden (view full) --- 98 * 99 * Side Effects: 100 * Memory is allocated for the initial bucket area. 101 * 102 *--------------------------------------------------------- 103 */ 104 105void | 2/* $NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $ */ 3 4/* 5 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 6 * Copyright (c) 1988, 1989 by Adam de Boor 7 * Copyright (c) 1989 by Berkeley Softworks 8 * All rights reserved. 9 * --- 88 unchanged lines hidden (view full) --- 98 * 99 * Side Effects: 100 * Memory is allocated for the initial bucket area. 101 * 102 *--------------------------------------------------------- 103 */ 104 105void |
106Hash_InitTable(t, numBuckets) 107 register Hash_Table *t; /* Structure to use to hold table. */ 108 int numBuckets; /* How many buckets to create for starters. | 106Hash_InitTable( 107 register Hash_Table *t, /* Structure to use to hold table. */ 108 int numBuckets) /* How many buckets to create for starters. |
109 * This number is rounded up to a power of 110 * two. If <= 0, a reasonable default is 111 * chosen. The table will grow in size later 112 * as needed. */ 113{ 114 register int i; 115 register struct Hash_Entry **hp; 116 --- 28 unchanged lines hidden (view full) --- 145 * 146 * Side Effects: 147 * Lots of memory is freed up. 148 * 149 *--------------------------------------------------------- 150 */ 151 152void | 109 * This number is rounded up to a power of 110 * two. If <= 0, a reasonable default is 111 * chosen. The table will grow in size later 112 * as needed. */ 113{ 114 register int i; 115 register struct Hash_Entry **hp; 116 --- 28 unchanged lines hidden (view full) --- 145 * 146 * Side Effects: 147 * Lots of memory is freed up. 148 * 149 *--------------------------------------------------------- 150 */ 151 152void |
153Hash_DeleteTable(t) 154 Hash_Table *t; | 153Hash_DeleteTable(Hash_Table *t) |
155{ 156 register struct Hash_Entry **hp, *h, *nexth = NULL; 157 register int i; 158 159 for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 160 for (h = *hp++; h != NULL; h = nexth) { 161 nexth = h->next; 162 free((char *)h); --- 22 unchanged lines hidden (view full) --- 185 * 186 * Side Effects: 187 * None. 188 * 189 *--------------------------------------------------------- 190 */ 191 192Hash_Entry * | 154{ 155 register struct Hash_Entry **hp, *h, *nexth = NULL; 156 register int i; 157 158 for (hp = t->bucketPtr, i = t->size; --i >= 0;) { 159 for (h = *hp++; h != NULL; h = nexth) { 160 nexth = h->next; 161 free((char *)h); --- 22 unchanged lines hidden (view full) --- 184 * 185 * Side Effects: 186 * None. 187 * 188 *--------------------------------------------------------- 189 */ 190 191Hash_Entry * |
193Hash_FindEntry(t, key) 194 Hash_Table *t; /* Hash table to search. */ 195 char *key; /* A hash key. */ | 192Hash_FindEntry( 193 Hash_Table *t, /* Hash table to search. */ 194 char *key) /* A hash key. */ |
196{ 197 register Hash_Entry *e; 198 register unsigned h; 199 register char *p; 200 201 for (h = 0, p = key; *p;) 202 h = (h << 5) - h + *p++; 203 p = key; --- 18 unchanged lines hidden (view full) --- 222 * with the given key. 223 * 224 * Side Effects: 225 * Memory may be allocated, and the hash buckets may be modified. 226 *--------------------------------------------------------- 227 */ 228 229Hash_Entry * | 195{ 196 register Hash_Entry *e; 197 register unsigned h; 198 register char *p; 199 200 for (h = 0, p = key; *p;) 201 h = (h << 5) - h + *p++; 202 p = key; --- 18 unchanged lines hidden (view full) --- 221 * with the given key. 222 * 223 * Side Effects: 224 * Memory may be allocated, and the hash buckets may be modified. 225 *--------------------------------------------------------- 226 */ 227 228Hash_Entry * |
230Hash_CreateEntry(t, key, newPtr) 231 register Hash_Table *t; /* Hash table to search. */ 232 char *key; /* A hash key. */ 233 Boolean *newPtr; /* Filled in with TRUE if new entry created, | 229Hash_CreateEntry( 230 register Hash_Table *t, /* Hash table to search. */ 231 char *key, /* A hash key. */ 232 Boolean *newPtr) /* Filled in with TRUE if new entry created, |
234 * FALSE otherwise. */ 235{ 236 register Hash_Entry *e; 237 register unsigned h; 238 register char *p; 239 int keylen; 240 struct Hash_Entry **hp; 241 --- 47 unchanged lines hidden (view full) --- 289 * 290 * Side Effects: 291 * Hash chain that entry lives in is modified and memory is freed. 292 * 293 *--------------------------------------------------------- 294 */ 295 296void | 233 * FALSE otherwise. */ 234{ 235 register Hash_Entry *e; 236 register unsigned h; 237 register char *p; 238 int keylen; 239 struct Hash_Entry **hp; 240 --- 47 unchanged lines hidden (view full) --- 288 * 289 * Side Effects: 290 * Hash chain that entry lives in is modified and memory is freed. 291 * 292 *--------------------------------------------------------- 293 */ 294 295void |
297Hash_DeleteEntry(t, e) 298 Hash_Table *t; 299 Hash_Entry *e; | 296Hash_DeleteEntry(Hash_Table *t, Hash_Entry *e) |
300{ 301 register Hash_Entry **hp, *p; 302 303 if (e == NULL) 304 return; 305 for (hp = &t->bucketPtr[e->namehash & t->mask]; 306 (p = *hp) != NULL; hp = &p->next) { 307 if (p == e) { --- 22 unchanged lines hidden (view full) --- 330 * The information in searchPtr is initialized so that successive 331 * calls to Hash_Next will return successive HashEntry's 332 * from the table. 333 * 334 *--------------------------------------------------------- 335 */ 336 337Hash_Entry * | 297{ 298 register Hash_Entry **hp, *p; 299 300 if (e == NULL) 301 return; 302 for (hp = &t->bucketPtr[e->namehash & t->mask]; 303 (p = *hp) != NULL; hp = &p->next) { 304 if (p == e) { --- 22 unchanged lines hidden (view full) --- 327 * The information in searchPtr is initialized so that successive 328 * calls to Hash_Next will return successive HashEntry's 329 * from the table. 330 * 331 *--------------------------------------------------------- 332 */ 333 334Hash_Entry * |
338Hash_EnumFirst(t, searchPtr) 339 Hash_Table *t; /* Table to be searched. */ 340 register Hash_Search *searchPtr;/* Area in which to keep state | 335Hash_EnumFirst( 336 Hash_Table *t, /* Table to be searched. */ 337 register Hash_Search *searchPtr)/* Area in which to keep state |
341 * about search.*/ 342{ 343 searchPtr->tablePtr = t; 344 searchPtr->nextIndex = 0; 345 searchPtr->hashEntryPtr = NULL; 346 return Hash_EnumNext(searchPtr); 347} 348 --- 11 unchanged lines hidden (view full) --- 360 * Side Effects: 361 * The information in searchPtr is modified to advance to the 362 * next entry. 363 * 364 *--------------------------------------------------------- 365 */ 366 367Hash_Entry * | 338 * about search.*/ 339{ 340 searchPtr->tablePtr = t; 341 searchPtr->nextIndex = 0; 342 searchPtr->hashEntryPtr = NULL; 343 return Hash_EnumNext(searchPtr); 344} 345 --- 11 unchanged lines hidden (view full) --- 357 * Side Effects: 358 * The information in searchPtr is modified to advance to the 359 * next entry. 360 * 361 *--------------------------------------------------------- 362 */ 363 364Hash_Entry * |
368Hash_EnumNext(searchPtr) 369 register Hash_Search *searchPtr; /* Area used to keep state about | 365Hash_EnumNext( 366 register Hash_Search *searchPtr) /* Area used to keep state about |
370 search. */ 371{ 372 register Hash_Entry *e; 373 Hash_Table *t = searchPtr->tablePtr; 374 375 /* 376 * The hashEntryPtr field points to the most recently returned 377 * entry, or is nil if we are starting up. If not nil, we have --- 28 unchanged lines hidden (view full) --- 406 * Side Effects: 407 * The entire hash table is moved, so any bucket numbers 408 * from the old table are invalid. 409 * 410 *--------------------------------------------------------- 411 */ 412 413static void | 367 search. */ 368{ 369 register Hash_Entry *e; 370 Hash_Table *t = searchPtr->tablePtr; 371 372 /* 373 * The hashEntryPtr field points to the most recently returned 374 * entry, or is nil if we are starting up. If not nil, we have --- 28 unchanged lines hidden (view full) --- 403 * Side Effects: 404 * The entire hash table is moved, so any bucket numbers 405 * from the old table are invalid. 406 * 407 *--------------------------------------------------------- 408 */ 409 410static void |
414RebuildTable(t) 415 register Hash_Table *t; | 411RebuildTable(register Hash_Table *t) |
416{ 417 register Hash_Entry *e, *next = NULL, **hp, **xp; 418 register int i, mask; 419 register Hash_Entry **oldhp; 420 int oldsize; 421 422 oldhp = t->bucketPtr; 423 oldsize = i = t->size; --- 16 unchanged lines hidden --- | 412{ 413 register Hash_Entry *e, *next = NULL, **hp, **xp; 414 register int i, mask; 415 register Hash_Entry **oldhp; 416 int oldsize; 417 418 oldhp = t->bucketPtr; 419 oldsize = i = t->size; --- 16 unchanged lines hidden --- |