2 * Copyright 2000, International Business Machines Corporation and others.
5 * This software has been released under the terms of the IBM Public
6 * License. For details, see the LICENSE file in the top-level source
7 * directory or online at http://www.openafs.org/dl/license10.html
10 #include <afsconfig.h>
11 #include <afs/param.h>
17 #include <netinet/in.h>
20 #include <sys/types.h>
23 #include <afs/bubasics.h>
24 #include "budb_errs.h"
26 #include "budb_internal.h"
27 #include "error_macros.h"
30 int sizeFunctions[HT_MAX_FUNCTION + 1];
31 int nHTBuckets = NhtBucketS; /* testing: we need small HT blocks */
33 int ht_minHBlocks(struct memoryHashTable *mht);
35 /* ht_TableSize - return the size of table necessary to represent a hashtable
36 * of given length in memory. It basically rounds the length up by the number
37 * of buckets per block. */
40 ht_TableSize(int length)
45 n = (length + nHTBuckets - 1) / nHTBuckets;
46 return n * sizeof(struct memoryHTBlock *);
49 /* ht_ResetT - resets the in-memory representation of a hashtable block array.
50 * It also resets the global variable nHTBuckets. */
53 ht_ResetT(struct memoryHTBlock ***blocksP, int *sizeP, int length)
55 struct memoryHTBlock **b = *blocksP;
60 nHTBuckets = ntohl(db.h.nHTBuckets);
62 n = *sizeP / sizeof(b[0]);
63 newsize = ht_TableSize(length);
64 if (*sizeP != newsize) {
65 /* free all blocks in the old array */
66 for (i = 0; i < n; i++)
73 /* invalidate the blocks of the array */
74 for (i = 0; i < n; i++)
82 * reinitialize a memory hash table.
83 * Calls ht_ResetT to invalidate the two block arrays.
87 ht_Reset(struct memoryHashTable *mht)
89 struct hashTable *ht = NULL;
91 if (!(mht && (ht = mht->ht)))
92 db_panic("some ht called with bad mht");
93 mht->threadOffset = ntohl(ht->threadOffset);
94 mht->length = ntohl(ht->length);
95 mht->oldLength = ntohl(ht->oldLength);
96 mht->progress = ntohl(ht->progress);
97 ht_ResetT(&mht->blocks, &mht->size, mht->length);
98 ht_ResetT(&mht->oldBlocks, &mht->oldSize, mht->oldLength);
101 /* InitDBhash - When server starts, do hash table initialization.
102 test - initialization parameters: bit 4 is small ht. */
107 sizeFunctions[0] = 0;
109 sizeFunctions[HT_dumpIden_FUNCTION] = sizeof(struct dump);
110 sizeFunctions[HT_dumpName_FUNCTION] = sizeof(struct dump);
111 sizeFunctions[HT_volName_FUNCTION] = sizeof(struct volInfo);
112 sizeFunctions[HT_tapeName_FUNCTION] = sizeof(struct tape);
114 db.volName.ht = &db.h.volName;
115 db.tapeName.ht = &db.h.tapeName;
116 db.dumpName.ht = &db.h.dumpName;
117 db.dumpIden.ht = &db.h.dumpIden;
121 /* ht_DBInit - When rebuilding database, this sets up the hash tables. */
126 db.h.nHTBuckets = htonl(nHTBuckets);
129 struct volInfo *s = 0;
130 db.h.volName.threadOffset =
131 htonl((char *)&s->nameHashChain - (char *)s);
132 db.h.volName.functionType = htonl(HT_volName_FUNCTION);
136 db.h.tapeName.threadOffset =
137 htonl((char *)&s->nameHashChain - (char *)s);
138 db.h.tapeName.functionType = htonl(HT_tapeName_FUNCTION);
142 db.h.dumpName.threadOffset =
143 htonl((char *)&s->nameHashChain - (char *)s);
144 db.h.dumpName.functionType = htonl(HT_dumpName_FUNCTION);
146 db.h.dumpIden.threadOffset =
147 htonl((char *)&s->idHashChain - (char *)s);
148 db.h.dumpIden.functionType = htonl(HT_dumpIden_FUNCTION);
150 ht_Reset(&db.volName);
151 ht_Reset(&db.tapeName);
152 ht_Reset(&db.dumpName);
153 ht_Reset(&db.dumpIden);
157 ht_AllocTable(struct ubik_trans *ut, struct memoryHashTable *mht)
159 struct hashTable *ht = NULL;
162 int nb, mnb; /* number of blocks for hashTable */
164 struct memoryHTBlock **b;
166 if (!(mht && (ht = mht->ht)))
167 db_panic("some ht called with bad mht");
168 if (ht->length || mht->blocks)
169 db_panic("previous table still allocated");
171 len = ntohl(ht->entries) * 2; /* allow room to grow */
172 nb = (len + nHTBuckets - 1) / nHTBuckets;
173 mnb = ht_minHBlocks(mht);
175 nb = mnb; /* use minimum */
176 len = nb * nHTBuckets; /* new hash table length */
178 mht->size = nb * sizeof(struct memoryHTBlock *);
179 b = mht->blocks = (struct memoryHTBlock **)malloc(mht->size);
180 memset(b, 0, mht->size);
182 for (i = 0; i < nb; i++) {
183 b[i] = (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
184 code = AllocBlock(ut, (struct block *)&b[i]->b, &b[i]->a);
189 b[i]->b.h.type = hashTable_BLOCK;
191 /* thread the blocks */
193 b[i - 1]->b.h.next = htonl(b[i]->a);
195 for (i = 0; i < nb; i++) {
197 dbwrite(ut, b[i]->a, (char *)&b[i]->b,
198 sizeof(struct htBlock) + (nHTBuckets -
199 NhtBucketS) * sizeof(dbadr));
203 if ((code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a))))
206 if ((code = set_word_addr(ut, 0, &db.h, &ht->length, htonl(len))))
213 ht_FreeTable(struct ubik_trans *ut, struct memoryHashTable *mht)
215 struct hashTable *ht = NULL;
217 struct blockHeader bh;
220 if (!(mht && (ht = mht->ht)))
221 db_panic("some ht called with bad mht");
222 if (ht->oldLength == 0)
223 db_panic("no table to free");
225 ht_ResetT(&mht->oldBlocks, &mht->oldSize, 0);
227 for (a = ntohl(ht->oldTable); a; a = na) {
228 if (dbread(ut, a, (char *)&bh, sizeof(bh))) {
229 Log("ht_FreeTable: dbread failed\n");
233 if ((code = FreeBlock(ut, &bh, a)))
236 if (set_word_addr(ut, 0, &db.h, &ht->oldTable, 0)
237 || set_word_addr(ut, 0, &db.h, &ht->oldLength, 0)
238 || set_word_addr(ut, 0, &db.h, &ht->progress, 0))
240 mht->oldLength = mht->progress = 0;
245 ht_GetTableBlock(struct ubik_trans *ut, struct memoryHashTable *mht,
246 afs_uint32 hash, int old, struct memoryHTBlock **blockP,
249 struct hashTable *ht = NULL;
250 struct memoryHTBlock **b;
252 struct memoryHTBlock ***blocksP;
260 || ((ht = mht->ht) == 0)
262 db_panic("some ht called with bad mht");
268 if ((length = mht->oldLength) == 0)
269 return 0; /* no entries */
271 if (hi < mht->progress)
272 return 0; /* no such entry */
273 blocksP = &mht->oldBlocks;
274 sizeP = &mht->oldSize;
276 if ((length = mht->length) == 0)
277 return 0; /* no entries */
279 blocksP = &mht->blocks;
283 bi = hi / nHTBuckets; /* block index */
284 *boP = hi - bi * nHTBuckets; /* block offset ptr */
287 *sizeP = ht_TableSize(length);
288 *blocksP = (struct memoryHTBlock **)malloc(*sizeP);
289 memset(*blocksP, 0, *sizeP);
291 n = *sizeP / sizeof(struct memoryHTBlock *);
293 db_panic("table size inconsistent");
296 /* find an allocated block or the beginning of the block array */
297 for (i = bi; (i > 0) && (b[i] == 0); i--);
301 if (i == 0) { /* the first block is found from the hashTable */
302 ta = ntohl(old ? ht->oldTable : ht->table);
304 db_panic("non-zero length, but no table");
306 /* else ta is set from last time around loop */
308 (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
314 if (dbread(ut, b[i]->a, (char *)&b[i]->b, sizeof(struct htBlock)))
321 /* printf("ht_GetTableBlock: hash %d block %d offset %d\n",
322 * hash, *blockP, *boP); */
326 ta = ntohl(b[i++]->b.h.next); /* get next ptr from current block */
331 * Decide when to push the current hash table to the old hash table.
332 * The entries in the old hash table are VALID, and are slowly hashed
333 * into the current table.
337 ht_MaybeAdjust(struct ubik_trans *ut, struct memoryHashTable *mht)
339 struct hashTable *ht = mht->ht;
340 int numberEntries = ntohl(ht->entries);
342 /* old hash table must be empty */
343 if (mht->oldLength != 0)
347 * It costs a lot to grow and shrink the hash table. Therefore, we will not
348 * shrink the hash table (only grow it). If the table is more than 2 entries per
349 * chain (average) we need to grow: push the entries to the old hash table.
352 * || ((mht->length > nHTBuckets) && (numberEntries*8 < mht->length))
355 /* Only grow a hash table if the number of entries is twice the
356 * number of hash length and is less than 20,450 (20 hash blocks). This
357 * means that the volname hash table will not grow (its initial
358 * hashtable size contains 30,600 buckets). Earlier revisions of
359 * the buserver have the initial size at 510 and 5,100 buckets -
360 * in which case we do want to grow it). We don't grow anything larger
361 * than 20,450 entries because it's expensive to re-hash everything.
363 if ((numberEntries > mht->length * 2) && (numberEntries < 20450)) { /* push current hash table to old hash table */
364 ht->oldLength = ht->length;
365 ht->oldTable = ht->table;
370 (ut, ((char *)ht - (char *)&db.h), (char *)ht, sizeof(*ht)))
374 LogDebug(2, "ht_MaybeAdjust: push ht to old\n");
380 ht_LookupBucket(struct ubik_trans *ut, struct memoryHashTable *mht,
381 afs_uint32 hash, int old)
383 struct memoryHTBlock *block;
387 if ((old ? mht->oldLength : mht->length) == 0)
389 code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
390 if (code || (block == 0))
392 return ntohl(block->b.bucket[bo]);
395 /* This function is not too bad, for small hash tables, but suffers, I think,
396 * from insufficient mixing of the hash information. */
399 Old2StringHashFunction(unsigned char *str)
401 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
403 hash = (hash << 1) + (hash >> 31) + *str++;
407 /* This was actually a coding error, and produces dreadful results. The
408 * problem is that the hash needs to be mixed up not the incoming character. */
411 Old3StringHashFunction(unsigned char *str)
413 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
415 hash += (*str++) * 0x072a51a4;
419 /* This function is pretty good. Its main problem is that the low two bits of
420 * the hash multiplier are zero which tends to shift information too far left.
421 * It behaves especially badly for hash tables whose size is a power of two. */
424 Old4StringHashFunction(unsigned char *str)
426 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
428 hash = (*str++) + hash * 0x072a51a4;
432 /* While this is good for a hash table with 500 buckets it is nearly as bad as
433 * #3 with a hash table as big as 8200. */
436 Old5StringHashFunction(unsigned char *str)
438 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
444 /* This was an attempt to produce a hash function with the smallest and
445 * simplest mixing multiplier. This is only a little worse than the real one,
446 * and the difference seems to be smaller with larger hash tables. It behaves
447 * better than the random hash function. */
450 Old6StringHashFunction(unsigned char *str)
452 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
454 hash = hash * 0x81 + (*str++);
458 /* This actually seems to be little better then the real one. Having the same
459 * number of bits but only 5 bits apart seems to produce worse results but
460 * having the bits spanning the same range farther apart also doesn't do as
461 * well. All these differences are fairly small, however. */
464 Old7StringHashFunction(unsigned char *str)
466 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
468 hash = hash * 0x42108421 + (*str++);
472 /* This function tries to provide some non-linearity by providing some feedback
473 * from higher-order bits in the word. It also uses shifts instead of
474 * multiplies, which may be faster on some architectures. */
477 Old8StringHashFunction(unsigned char *str)
479 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
482 hash + (hash << 7) + (hash << 14) + (hash << 21) + (hash << 28) +
483 (hash >> 17) + *str++;
487 /* This is the result of the above search for good hash functions. It seems
488 * that the choice of multipliers is somewhat arbitrary but has several
489 * constraints. It shouldn't have too many or too few one bits and should be
490 * odd. It behaves beeter than the random hash function. */
493 StringHashFunction(unsigned char *str)
495 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
496 /* The multiplicative constant should be odd and have a goodly number of
499 hash = (*str++) + hash * 0x10204081;
504 IdHashFunction(afs_uint32 id)
513 /* The minimum hash table blocks to allocate. Each block contains 510
514 * buckets. They hash table grows when the number of entries reaches
515 * twice the number of buckets.
518 ht_minHBlocks(struct memoryHashTable *mht)
522 switch (ntohl(mht->ht->functionType)) {
523 case HT_dumpIden_FUNCTION:
524 case HT_dumpName_FUNCTION: /* hash table able to handle (befor it grows) ... */
525 retval = 2; /* 1,020 dump entries */
528 case HT_tapeName_FUNCTION:
529 retval = 4; /* 2,040 tape entries */
532 case HT_volName_FUNCTION:
533 retval = 60; /* 61,200 volInfo entries (with different names) */
537 db_panic("Illegal hash function type");
538 retval = -1; /* not reached */
544 ht_HashEntry(struct memoryHashTable *mht,
545 char *e) /* entry's address (in b) */
547 int type = ntohl(mht->ht->functionType);
551 case HT_dumpIden_FUNCTION:
552 retval = IdHashFunction(ntohl(((struct dump *)e)->id));
553 LogDebug(5, "HashEntry: dumpid returns %d\n", retval);
556 case HT_dumpName_FUNCTION:
557 retval = StringHashFunction((unsigned char *)((struct dump *)e)->dumpName);
558 LogDebug(5, "HashEntry: dumpname returns %d\n", retval);
561 case HT_tapeName_FUNCTION:
562 retval = StringHashFunction((unsigned char *)((struct tape *)e)->name);
563 LogDebug(5, "HashEntry: tapename returns %d\n", retval);
566 case HT_volName_FUNCTION:
567 retval = StringHashFunction((unsigned char *)((struct volInfo *)e)->name);
568 LogDebug(5, "HashEntry: volname returns %d\n", retval);
572 db_panic("illegal hash function");
573 retval = -1; /* not reached */
581 * returns a ptr to the memory hash table for the specified hash
585 struct memoryHashTable *
586 ht_GetType(int type, int *e_sizeP)
588 struct memoryHashTable *mht;
590 if ((type <= 0) || (type > HT_MAX_FUNCTION))
594 *e_sizeP = sizeFunctions[type];
596 case HT_dumpIden_FUNCTION:
600 case HT_dumpName_FUNCTION:
604 case HT_tapeName_FUNCTION:
608 case HT_volName_FUNCTION:
615 if (ntohl(mht->ht->functionType) != type)
616 db_panic("ht types don't match");
621 ht_KeyMatch(int type, char *key, char *e)
624 case HT_dumpIden_FUNCTION:
625 return *(dumpId *) key == ntohl(((struct dump *)e)->id);
626 case HT_dumpName_FUNCTION:
627 return strcmp(key, ((struct dump *)e)->dumpName) == 0;
628 case HT_tapeName_FUNCTION:
629 return strcmp(key, ((struct tape *)e)->name) == 0;
630 case HT_volName_FUNCTION:
631 return strcmp(key, ((struct volInfo *)e)->name) == 0;
634 db_panic("illegal hash function");
642 * ut - ubik transaction
643 * mht - memory hash table ptr
644 * key - hash and lookup key
646 * eaP - dbaddr of entry found or zero if failed
647 * e - contents of located entry
651 ht_LookupEntry(struct ubik_trans *ut,
652 struct memoryHashTable *mht,
653 void *key, /* pointer to lookup key to match */
654 dbadr *eaP, /* db addr of entry found or zero */
655 void *e) /* contents of located entry */
657 struct hashTable *ht = NULL;
664 if (!key || !eaP || !e)
665 db_panic("null ptrs passed to LookupEntry");
666 if (!(mht && (ht = mht->ht)))
667 db_panic("some ht called with bad mht");
669 *eaP = 0; /* initialize not-found indicator */
671 type = ntohl(ht->functionType);
672 e_size = sizeFunctions[type];
673 if (type == HT_dumpIden_FUNCTION)
674 hash = IdHashFunction(*(dumpId *) key);
676 hash = StringHashFunction(key);
678 for (old = 0;; old++) {
679 a = ht_LookupBucket(ut, mht, hash, old);
681 if (dbread(ut, a, e, e_size))
683 if (ht_KeyMatch(type, key, e)) {
687 a = ntohl(*(dbadr *) ((char *)e + mht->threadOffset));
696 * opQuota - max # of items to move
698 * opQuota - adjusted to reflect # of moves
702 ht_HashInList(struct ubik_trans *ut, struct memoryHashTable *mht,
703 int *opQuota, struct memoryHTBlock *block, int blockOffset)
705 struct hashTable *ht = mht->ht;
709 char e[sizeof(struct block)]; /* unnecessarily conservative */
710 int e_size = sizeFunctions[ntohl(ht->functionType)];
712 if (mht->length == 0) {
713 if ((code = ht_AllocTable(ut, mht))) {
714 Log("ht_HashInList: ht_AllocTable failed\n");
719 listA = ntohl(block->b.bucket[blockOffset]);
722 Log("ht_HashInList: expecting non-zero bucket\n");
726 for (ea = listA; ea; ea = next_ea) { /*f */
728 LogDebug(3, "ht_HashInList: move entry at %d, type %d\n", ea,
729 ntohl(mht->ht->functionType));
731 if (dbread(ut, ea, e, e_size))
734 /* LogNetDump((struct dump *) e); */
736 /* get the address of the next item on the list */
737 next_ea = ntohl(*(dbadr *) (e + mht->threadOffset));
739 /* write the link into the bucket */
741 set_word_addr(ut, block->a, &block->b,
742 &block->b.bucket[blockOffset], htonl(next_ea));
744 Log("ht_HashInList: bucket update failed\n");
749 struct memoryHTBlock *block;
753 /* get the hash value */
754 hash = ht_HashEntry(mht, e) % mht->length;
755 LogDebug(4, "ht_HashInList: moved to %d\n", hash);
757 /* get the new hash table block */
758 code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
760 Log("ht_HashInList: ht_GetTableBlock failed\n");
764 Log("ht_HashInList: ht_GetTableBlock returned 0\n");
765 return BUDB_INTERNALERROR;
768 /* Chain entry at front of bucket;
769 * first threadOffset of entry = bucket
770 * then bucket = addr of entry
773 (ut, ea, e, mht->threadOffset, block->b.bucket[bo])
774 || set_word_addr(ut, block->a, &block->b,
775 &block->b.bucket[bo], htonl(ea)))
779 if (--(*opQuota) == 0)
787 * The hash table is needs to be re-sized. Move entries from the old
792 ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
794 struct memoryHTBlock *block;
800 if (mht->oldLength == 0)
803 LogDebug(3, "ht_MoveEntries:\n");
804 /* we assume here that the hash function will map numbers smaller than the
805 * size of the hash table straight through to hash table indexes.
807 hash = mht->progress;
809 /* get hash table block ? */
810 code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
815 return BUDB_INTERNALERROR;
817 count = 10; /* max. # entries to move */
820 if (block->b.bucket[bo]) {
821 code = ht_HashInList(ut, mht, &count, block, bo);
823 Log("ht_MoveEntries: ht_HashInList failed\n");
828 if (block->b.bucket[bo] == 0) {
829 /* this bucket is now empty */
833 /* don't exceed the quota of items to be moved */
837 } while (++bo < nHTBuckets);
839 if (mht->progress >= mht->oldLength)
840 return (ht_FreeTable(ut, mht));
842 if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
843 Log("ht_MoveEntries: progress set failed\n");
852 ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
856 struct memoryHTBlock *block;
859 if (mht->oldLength == 0)
862 LogDebug(3, "ht_MoveEntries:\n");
863 /* we assume here that the hash function will map numbers smaller than the
864 * size of the hash table straight through to hash table indexes.
866 hash = mht->progress;
868 /* get hash table block ? */
869 code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
874 return BUDB_INTERNALERROR;
878 if (block->b.bucket[bo]) {
879 code = ht_HashInList(ut, mht, ntohl(block->b.bucket[bo]));
881 Log("ht_MoveEntries: ht_HashInList failed\n");
885 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
888 Log("ht_MoveEntries: clear old entry failed\n");
893 } while (++bo < nHTBuckets);
895 if (mht->progress >= mht->oldLength)
896 return (ht_FreeTable(ut, mht));
898 if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
899 Log("ht_MoveEntries: progress set failed\n");
907 ht_HashIn(struct ubik_trans *ut,
908 struct memoryHashTable *mht,
909 dbadr ea, /* block db address */
910 void *e) /* entry's address (in b) */
912 struct hashTable *ht = NULL;
914 struct memoryHTBlock *block;
918 if (!(mht && (ht = mht->ht)))
919 db_panic("some ht called with bad mht");
921 if ((code = ht_MaybeAdjust(ut, mht)))
923 if (mht->length == 0)
924 if ((code = ht_AllocTable(ut, mht)))
927 hash = ht_HashEntry(mht, e);
928 code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
932 return BUDB_INTERNALERROR;
934 code = set_word_offset(ut, ea, e, mht->threadOffset, block->b.bucket[bo]);
937 LogDebug(5, "Hashin: set %d to %d\n", mht->threadOffset,
938 block->b.bucket[bo]);
941 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
945 LogDebug(5, "Hashin: set %"AFS_PTR_FMT" to %d\n",
946 &block->b.bucket[bo], htonl(ea));
949 set_word_addr(ut, 0, &db.h, &ht->entries,
950 htonl(ntohl(ht->entries) + 1));
954 return ht_MoveEntries(ut, mht);
957 /* RemoveFromList - generic procedure to delete an entry from a list given its
958 * head and thread offset. Only a single long is modified by this routine.
959 * The head pointer is modified, in place, using set_word_addr if the entry is
960 * at the head of the list, otherwise only the thread of the previous entry is
961 * modified. The entry pointer is only used to calculate the thread offset,
962 * but is not otherwise used. */
965 RemoveFromList(struct ubik_trans *ut,
966 dbadr ea, /* db addr of head structure */
967 void *e, /* head structure */
968 dbadr *head, /* address of head pointer */
969 dbadr ta, /* db addr of strucure to be removed */
970 void *t, /* structure being removed */
971 dbadr *thread) /* pointer to thread pointer */
974 int threadOffset = ((char *)thread - (char *)t);
975 dbadr next_a; /* db addr of next element in list */
976 dbadr loop_a; /* db addr of current list element */
979 return -1; /* empty list: not found */
980 next_a = ntohl(*head); /* start at head of list */
981 if (next_a == ta) { /* remove from head of list */
982 code = set_word_addr(ut, ea, e, head, *thread);
988 dbread(ut, loop_a + threadOffset, (char *)&next_a, sizeof(dbadr));
992 return -1; /* end of list: not found */
993 } while (ta != (next_a = ntohl(next_a)));
994 code = dbwrite(ut, loop_a + threadOffset, (char *)thread, sizeof(dbadr));
999 ht_HashOutT(struct ubik_trans *ut, struct memoryHashTable *mht,
1000 afs_uint32 hash, dbadr ea, char *e, int old)
1002 struct memoryHTBlock *block;
1006 if ((old ? mht->oldLength : mht->length) == 0)
1008 code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
1011 if ((block == 0) || (block->b.bucket[bo] == 0))
1015 RemoveFromList(ut, block->a, (char *)&block->b, &block->b.bucket[bo],
1016 ea, e, (dbadr *) (e + mht->threadOffset));
1021 unthread_ea = *(afs_int32 *) ((char *)e + mht->threadOffset);
1022 if (block->b.bucket[bo] == net_ea) {
1024 (ut, block->a, &block->b, &block->b.bucket[bo], unthread_ea))
1028 loop_a = ntohl(block->b.bucket[bo]);
1031 (ut, loop_a + mht->threadOffset, (char *)&next_loop_a,
1034 if (next_loop_a == 0)
1035 return -1; /* not found */
1036 if (net_ea == next_loop_a) {
1038 (ut, loop_a + mht->threadOffset, (char *)&unthread_ea,
1043 loop_a = ntohl(next_loop_a);
1048 (ut, 0, &db.h, &mht->ht->entries, htonl(ntohl(mht->ht->entries) - 1)))
1054 ht_HashOut(struct ubik_trans *ut, struct memoryHashTable *mht, dbadr ea,
1061 db_panic("some ht called with bad mht");
1062 hash = ht_HashEntry(mht, e);
1063 if (mht->oldLength) {
1064 code = ht_HashOutT(ut, mht, hash, ea, e, 1 /*old */ );
1067 else if (code != -1)
1070 if (mht->length == 0) /* not found */
1071 ERROR(BUDB_INTERNALERROR);
1072 code = ht_HashOutT(ut, mht, hash, ea, e, 0 /*old */ );
1078 code = ht_MoveEntries(ut, mht);
1081 code = ht_MaybeAdjust(ut, mht);
1089 /* generic hash table traversal routines */
1093 scanHashTableBlock(struct ubik_trans *ut,
1094 struct memoryHashTable *mhtPtr,
1095 struct htBlock *htBlockPtr,
1097 afs_int32 length, /* size of whole hash table */
1098 int index, /* base index of this block */
1099 int (*selectFn) (dbadr, void *, void *),
1100 int (*operationFn) (dbadr, void *, void *),
1103 int type; /* hash table type */
1104 int entrySize; /* hashed entry size */
1106 char entry[sizeof(struct block)];
1107 dbadr entryAddr, nextEntryAddr;
1111 type = ntohl(mhtPtr->ht->functionType);
1112 entrySize = sizeFunctions[type];
1114 /* step through this hash table block, being careful to stop
1115 * before the end of the overall hash table
1118 for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) { /*f */
1120 nextEntryAddr = ntohl(htBlockPtr->bucket[i]);
1122 /* if this is the old hash table, all entries below the progress mark
1123 * should have been moved to the new hash table
1125 if (old && (index < mhtPtr->progress) && nextEntryAddr)
1126 return BUDB_INTERNALERROR;
1128 /* now walk down the chain of each bucket */
1129 while (nextEntryAddr) { /*w */
1131 entryAddr = nextEntryAddr;
1132 if (dbread(ut, entryAddr, &entry[0], entrySize))
1133 return (BUDB_INTERNALERROR);
1135 if ((*selectFn) (entryAddr, &entry[0], rockPtr)) {
1136 (*operationFn) (entryAddr, &entry[0], rockPtr);
1140 ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
1149 scanHashTable(struct ubik_trans *ut, struct memoryHashTable *mhtPtr,
1150 int (*selectFn) (dbadr, void *, void *),
1151 int (*operationFn) (dbadr, void *, void *),
1154 struct htBlock hashTableBlock;
1155 dbadr tableAddr; /* disk addr of hash block */
1156 int tableLength; /* # entries */
1157 int blockLength; /* # blocks */
1163 extern int nHTBuckets; /* # buckets in a hash table */
1165 for (old = 0; old <= 1; old++) { /*fo */
1167 /* check the old hash table */
1168 tableLength = mhtPtr->oldLength;
1169 if (tableLength == 0)
1170 continue; /* nothing to do */
1172 tableAddr = ntohl(mhtPtr->ht->oldTable);
1174 /* check current hash table */
1175 tableLength = mhtPtr->length;
1176 if (tableLength == 0)
1177 continue; /* nothing to do */
1179 tableAddr = ntohl(mhtPtr->ht->table);
1182 blockLength = (tableLength - 1) / nHTBuckets;
1185 /* follow the hash chain */
1186 for (i = 0; i <= blockLength; i++) { /*fi */
1187 /* chain too short */
1189 ERROR(BUDB_DATABASEINCONSISTENT);
1192 dbread(ut, tableAddr, &hashTableBlock,
1193 sizeof(hashTableBlock));
1198 scanHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
1199 tableLength, hashIndex, selectFn,
1200 operationFn, rockPtr);
1204 hashIndex += nHTBuckets;
1205 tableAddr = ntohl(hashTableBlock.h.next);