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>
19 #include <netinet/in.h>
28 #include <sys/types.h>
32 #include <afs/bubasics.h>
33 #include "budb_errs.h"
35 #include "error_macros.h"
38 int sizeFunctions[HT_MAX_FUNCTION + 1];
39 int nHTBuckets = NhtBucketS; /* testing: we need small HT blocks */
41 /* ht_TableSize - return the size of table necessary to represent a hashtable
42 * of given length in memory. It basically rounds the length up by the number
43 * of buckets per block. */
52 n = (length + nHTBuckets - 1) / nHTBuckets;
53 return n * sizeof(struct memoryHTBlock *);
56 /* ht_ResetT - resets the in-memory representation of a hashtable block array.
57 * It also resets the global variable nHTBuckets. */
60 ht_ResetT(blocksP, sizeP, length)
61 struct memoryHTBlock ***blocksP;
65 struct memoryHTBlock **b = *blocksP;
70 nHTBuckets = ntohl(db.h.nHTBuckets);
72 n = *sizeP / sizeof(b[0]);
73 newsize = ht_TableSize(length);
74 if (*sizeP != newsize) {
75 /* free all blocks in the old array */
76 for (i = 0; i < n; i++)
83 /* invalidate the blocks of the array */
84 for (i = 0; i < n; i++)
92 * reinitialize a memory hash table.
93 * Calls ht_ResetT to invalidate the two block arrays.
98 struct memoryHashTable *mht;
100 struct hashTable *ht;
102 if (!(mht && (ht = mht->ht)))
103 db_panic("some ht called with bad mht");
104 mht->threadOffset = ntohl(ht->threadOffset);
105 mht->length = ntohl(ht->length);
106 mht->oldLength = ntohl(ht->oldLength);
107 mht->progress = ntohl(ht->progress);
108 ht_ResetT(&mht->blocks, &mht->size, mht->length);
109 ht_ResetT(&mht->oldBlocks, &mht->oldSize, mht->oldLength);
112 /* InitDBhash - When server starts, do hash table initialization.
113 test - initialization parameters: bit 4 is small ht. */
118 sizeFunctions[0] = 0;
120 sizeFunctions[HT_dumpIden_FUNCTION] = sizeof(struct dump);
121 sizeFunctions[HT_dumpName_FUNCTION] = sizeof(struct dump);
122 sizeFunctions[HT_volName_FUNCTION] = sizeof(struct volInfo);
123 sizeFunctions[HT_tapeName_FUNCTION] = sizeof(struct tape);
125 db.volName.ht = &db.h.volName;
126 db.tapeName.ht = &db.h.tapeName;
127 db.dumpName.ht = &db.h.dumpName;
128 db.dumpIden.ht = &db.h.dumpIden;
132 /* ht_DBInit - When rebuilding database, this sets up the hash tables. */
137 db.h.nHTBuckets = htonl(nHTBuckets);
140 struct volInfo *s = 0;
141 db.h.volName.threadOffset =
142 htonl((char *)&s->nameHashChain - (char *)s);
143 db.h.volName.functionType = htonl(HT_volName_FUNCTION);
147 db.h.tapeName.threadOffset =
148 htonl((char *)&s->nameHashChain - (char *)s);
149 db.h.tapeName.functionType = htonl(HT_tapeName_FUNCTION);
153 db.h.dumpName.threadOffset =
154 htonl((char *)&s->nameHashChain - (char *)s);
155 db.h.dumpName.functionType = htonl(HT_dumpName_FUNCTION);
157 db.h.dumpIden.threadOffset =
158 htonl((char *)&s->idHashChain - (char *)s);
159 db.h.dumpIden.functionType = htonl(HT_dumpIden_FUNCTION);
161 ht_Reset(&db.volName);
162 ht_Reset(&db.tapeName);
163 ht_Reset(&db.dumpName);
164 ht_Reset(&db.dumpIden);
168 ht_AllocTable(ut, mht)
169 struct ubik_trans *ut;
170 struct memoryHashTable *mht;
172 struct hashTable *ht;
175 int nb, mnb; /* number of blocks for hashTable */
177 struct memoryHTBlock **b;
179 if (!(mht && (ht = mht->ht)))
180 db_panic("some ht called with bad mht");
181 if (ht->length || mht->blocks)
182 db_panic("previous table still allocated");
184 len = ntohl(ht->entries) * 2; /* allow room to grow */
185 nb = (len + nHTBuckets - 1) / nHTBuckets;
186 mnb = ht_minHBlocks(mht);
188 nb = mnb; /* use minimum */
189 len = nb * nHTBuckets; /* new hash table length */
191 mht->size = nb * sizeof(struct memoryHTBlock *);
192 b = mht->blocks = (struct memoryHTBlock **)malloc(mht->size);
193 memset(b, 0, mht->size);
195 for (i = 0; i < nb; i++) {
196 b[i] = (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
197 code = AllocBlock(ut, (struct block *)&b[i]->b, &b[i]->a);
202 b[i]->b.h.type = hashTable_BLOCK;
204 /* thread the blocks */
206 b[i - 1]->b.h.next = htonl(b[i]->a);
208 for (i = 0; i < nb; i++) {
210 dbwrite(ut, b[i]->a, (char *)&b[i]->b,
211 sizeof(struct htBlock) + (nHTBuckets -
212 NhtBucketS) * sizeof(dbadr));
216 if (code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a)))
219 if (code = set_word_addr(ut, 0, &db.h, &ht->length, htonl(len)))
226 ht_FreeTable(ut, mht)
227 struct ubik_trans *ut;
228 struct memoryHashTable *mht;
230 struct hashTable *ht;
232 struct blockHeader bh;
235 if (!(mht && (ht = mht->ht)))
236 db_panic("some ht called with bad mht");
237 if (ht->oldLength == 0)
238 db_panic("no table to free");
240 ht_ResetT(&mht->oldBlocks, &mht->oldSize, 0);
242 for (a = ntohl(ht->oldTable); a; a = na) {
243 if (dbread(ut, a, (char *)&bh, sizeof(bh))) {
244 Log("ht_FreeTable: dbread failed\n");
248 if (code = FreeBlock(ut, &bh, a))
251 if (set_word_addr(ut, 0, &db.h, &ht->oldTable, 0)
252 || set_word_addr(ut, 0, &db.h, &ht->oldLength, 0)
253 || set_word_addr(ut, 0, &db.h, &ht->progress, 0))
255 mht->oldLength = mht->progress = 0;
260 ht_GetTableBlock(ut, mht, hash, old, blockP, boP)
261 struct ubik_trans *ut;
262 struct memoryHashTable *mht;
265 struct memoryHTBlock **blockP;
268 struct hashTable *ht;
269 struct memoryHTBlock **b;
271 struct memoryHTBlock ***blocksP;
279 || ((ht = mht->ht) == 0)
281 db_panic("some ht called with bad mht");
287 if ((length = mht->oldLength) == 0)
288 return 0; /* no entries */
290 if (hi < mht->progress)
291 return 0; /* no such entry */
292 blocksP = &mht->oldBlocks;
293 sizeP = &mht->oldSize;
295 if ((length = mht->length) == 0)
296 return 0; /* no entries */
298 blocksP = &mht->blocks;
302 bi = hi / nHTBuckets; /* block index */
303 *boP = hi - bi * nHTBuckets; /* block offset ptr */
306 *sizeP = ht_TableSize(length);
307 *blocksP = (struct memoryHTBlock **)malloc(*sizeP);
308 memset(*blocksP, 0, *sizeP);
310 n = *sizeP / sizeof(struct memoryHTBlock *);
312 db_panic("table size inconsistent");
315 /* find an allocated block or the beginning of the block array */
316 for (i = bi; (i > 0) && (b[i] == 0); i--);
320 if (i == 0) { /* the first block is found from the hashTable */
321 ta = ntohl(old ? ht->oldTable : ht->table);
323 db_panic("non-zero length, but no table");
325 /* else ta is set from last time around loop */
327 (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
333 if (dbread(ut, b[i]->a, (char *)&b[i]->b, sizeof(struct htBlock)))
340 /* printf("ht_GetTableBlock: hash %d block %d offset %d\n",
341 * hash, *blockP, *boP); */
345 ta = ntohl(b[i++]->b.h.next); /* get next ptr from current block */
350 * Decide when to push the current hash table to the old hash table.
351 * The entries in the old hash table are VALID, and are slowly hashed
352 * into the current table.
356 ht_MaybeAdjust(ut, mht)
357 struct ubik_trans *ut;
358 struct memoryHashTable *mht;
360 struct hashTable *ht = mht->ht;
361 int numberEntries = ntohl(ht->entries);
363 /* old hash table must be empty */
364 if (mht->oldLength != 0)
368 * It costs a lot to grow and shrink the hash table. Therefore, we will not
369 * shrink the hash table (only grow it). If the table is more than 2 entries per
370 * chain (average) we need to grow: push the entries to the old hash table.
373 * || ((mht->length > nHTBuckets) && (numberEntries*8 < mht->length))
376 /* Only grow a hash table if the number of entries is twice the
377 * number of hash length and is less than 20,450 (20 hash blocks). This
378 * means that the volname hash table will not grow (its initial
379 * hashtable size contains 30,600 buckets). Earlier revisions of
380 * the buserver have the initial size at 510 and 5,100 buckets -
381 * in which case we do want to grow it). We don't grow anything larger
382 * than 20,450 entries because it's expensive to re-hash everything.
384 if ((numberEntries > mht->length * 2) && (numberEntries < 20450)) { /* push current hash table to old hash table */
385 ht->oldLength = ht->length;
386 ht->oldTable = ht->table;
391 (ut, ((char *)ht - (char *)&db.h), (char *)ht, sizeof(*ht)))
395 LogDebug(2, "ht_MaybeAdjust: push ht to old\n");
401 ht_LookupBucket(ut, mht, hash, old)
402 struct ubik_trans *ut;
403 struct memoryHashTable *mht;
407 struct memoryHTBlock *block;
411 if ((old ? mht->oldLength : mht->length) == 0)
413 code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
414 if (code || (block == 0))
416 return ntohl(block->b.bucket[bo]);
419 /* This function is not too bad, for small hash tables, but suffers, I think,
420 * from insufficient mixing of the hash information. */
423 Old2StringHashFunction(str)
426 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
428 hash = (hash << 1) + (hash >> 31) + *str++;
432 /* This was actually a coding error, and produces dreadful results. The
433 * problem is that the hash needs to be mixed up not the incoming character. */
436 Old3StringHashFunction(str)
439 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
441 hash += (*str++) * 0x072a51a4;
445 /* This function is pretty good. Its main problem is that the low two bits of
446 * the hash multiplier are zero which tends to shift information too far left.
447 * It behaves especially badly for hash tables whose size is a power of two. */
450 Old4StringHashFunction(str)
453 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
455 hash = (*str++) + hash * 0x072a51a4;
459 /* While this is good for a hash table with 500 buckets it is nearly as bad as
460 * #3 with a hash table as big as 8200. */
463 Old5StringHashFunction(str)
466 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
472 /* This was an attempt to produce a hash function with the smallest and
473 * simplest mixing multiplier. This is only a little worse than the real one,
474 * and the difference seems to be smaller with larger hash tables. It behaves
475 * better than the random hash function. */
478 Old6StringHashFunction(str)
481 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
483 hash = hash * 0x81 + (*str++);
487 /* This actually seems to be little better then the real one. Having the same
488 * number of bits but only 5 bits apart seems to produce worse results but
489 * having the bits spanning the same range farther apart also doesn't do as
490 * well. All these differences are fairly small, however. */
493 Old7StringHashFunction(str)
496 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
498 hash = hash * 0x42108421 + (*str++);
502 /* This function tries to provide some non-linearity by providing some feedback
503 * from higher-order bits in the word. It also uses shifts instead of
504 * multiplies, which may be faster on some architectures. */
507 Old8StringHashFunction(str)
510 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
513 hash + (hash << 7) + (hash << 14) + (hash << 21) + (hash << 28) +
514 (hash >> 17) + *str++;
518 /* This is the result of the above search for good hash functions. It seems
519 * that the choice of multipliers is somewhat arbitrary but has several
520 * constraints. It shouldn't have too many or too few one bits and should be
521 * odd. It behaves beeter than the random hash function. */
524 StringHashFunction(str)
527 afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
528 /* The multiplicative constant should be odd and have a goodly number of
531 hash = (*str++) + hash * 0x10204081;
546 /* The minimum hash table blocks to allocate. Each block contains 510
547 * buckets. They hash table grows when the number of entries reaches
548 * twice the number of buckets.
552 struct memoryHashTable *mht;
556 switch (ntohl(mht->ht->functionType)) {
557 case HT_dumpIden_FUNCTION:
558 case HT_dumpName_FUNCTION: /* hash table able to handle (befor it grows) ... */
559 retval = 2; /* 1,020 dump entries */
562 case HT_tapeName_FUNCTION:
563 retval = 4; /* 2,040 tape entries */
566 case HT_volName_FUNCTION:
567 retval = 60; /* 61,200 volInfo entries (with different names) */
571 db_panic("Illegal hash function type");
578 struct memoryHashTable *mht;
579 char *e; /* entry's address (in b) */
581 int type = ntohl(mht->ht->functionType);
585 case HT_dumpIden_FUNCTION:
586 retval = IdHashFunction(ntohl(((struct dump *)e)->id));
587 LogDebug(5, "HashEntry: dumpid returns %d\n", retval);
590 case HT_dumpName_FUNCTION:
591 retval = StringHashFunction(((struct dump *)e)->dumpName);
592 LogDebug(5, "HashEntry: dumpname returns %d\n", retval);
595 case HT_tapeName_FUNCTION:
596 retval = StringHashFunction(((struct tape *)e)->name);
597 LogDebug(5, "HashEntry: tapename returns %d\n", retval);
600 case HT_volName_FUNCTION:
601 retval = StringHashFunction(((struct volInfo *)e)->name);
602 LogDebug(5, "HashEntry: volname returns %d\n", retval);
606 db_panic("illegal hash function");
614 * returns a ptr to the memory hash table for the specified hash
618 struct memoryHashTable *
619 ht_GetType(type, e_sizeP)
623 struct memoryHashTable *mht;
625 if ((type <= 0) || (type > HT_MAX_FUNCTION))
629 *e_sizeP = sizeFunctions[type];
631 case HT_dumpIden_FUNCTION:
635 case HT_dumpName_FUNCTION:
639 case HT_tapeName_FUNCTION:
643 case HT_volName_FUNCTION:
650 if (ntohl(mht->ht->functionType) != type)
651 db_panic("ht types don't match");
656 ht_KeyMatch(type, key, e)
662 case HT_dumpIden_FUNCTION:
663 return *(dumpId *) key == ntohl(((struct dump *)e)->id);
664 case HT_dumpName_FUNCTION:
665 return strcmp(key, ((struct dump *)e)->dumpName) == 0;
666 case HT_tapeName_FUNCTION:
667 return strcmp(key, ((struct tape *)e)->name) == 0;
668 case HT_volName_FUNCTION:
669 return strcmp(key, ((struct volInfo *)e)->name) == 0;
672 db_panic("illegal hash function");
678 * ut - ubik transaction
679 * mht - memory hash table ptr
680 * key - hash and lookup key
682 * eaP - dbaddr of entry found or zero if failed
683 * e - contents of located entry
687 ht_LookupEntry(ut, mht, key, eaP, e)
688 struct ubik_trans *ut;
689 struct memoryHashTable *mht;
690 char *key; /* pointer to lookup key to match */
691 dbadr *eaP; /* db addr of entry found or zero */
692 char *e; /* contents of located entry */
694 struct hashTable *ht;
701 if (!key || !eaP || !e)
702 db_panic("null ptrs passed to LookupEntry");
703 if (!(mht && (ht = mht->ht)))
704 db_panic("some ht called with bad mht");
706 *eaP = 0; /* initialize not-found indicator */
708 type = ntohl(ht->functionType);
709 e_size = sizeFunctions[type];
710 if (type == HT_dumpIden_FUNCTION)
711 hash = IdHashFunction(*(dumpId *) key);
713 hash = StringHashFunction(key);
715 for (old = 0;; old++) {
716 a = ht_LookupBucket(ut, mht, hash, old);
718 if (dbread(ut, a, e, e_size))
720 if (ht_KeyMatch(type, key, e)) {
724 a = ntohl(*(dbadr *) (e + mht->threadOffset));
733 * opQuota - max # of items to move
735 * opQuota - adjusted to reflect # of moves
739 ht_HashInList(ut, mht, opQuota, block, blockOffset)
740 struct ubik_trans *ut;
741 struct memoryHashTable *mht;
743 struct memoryHTBlock *block;
746 struct hashTable *ht = mht->ht;
750 char e[sizeof(struct block)]; /* unnecessarily conservative */
751 int e_size = sizeFunctions[ntohl(ht->functionType)];
753 if (mht->length == 0) {
754 if (code = ht_AllocTable(ut, mht)) {
755 Log("ht_HashInList: ht_AllocTable failed\n");
760 listA = ntohl(block->b.bucket[blockOffset]);
763 Log("ht_HashInList: expecting non-zero bucket\n");
767 for (ea = listA; ea; ea = next_ea) { /*f */
769 LogDebug(3, "ht_HashInList: move entry at %d, type %d\n", ea,
770 ntohl(mht->ht->functionType));
772 if (dbread(ut, ea, e, e_size))
775 /* LogNetDump((struct dump *) e); */
777 /* get the address of the next item on the list */
778 next_ea = ntohl(*(dbadr *) (e + mht->threadOffset));
780 /* write the link into the bucket */
782 set_word_addr(ut, block->a, &block->b,
783 &block->b.bucket[blockOffset], htonl(next_ea));
785 Log("ht_HashInList: bucket update failed\n");
790 struct memoryHTBlock *block;
794 /* get the hash value */
795 hash = ht_HashEntry(mht, e) % mht->length;
796 LogDebug(4, "ht_HashInList: moved to %d\n", hash);
798 /* get the new hash table block */
799 code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
801 Log("ht_HashInList: ht_GetTableBlock failed\n");
805 Log("ht_HashInList: ht_GetTableBlock returned 0\n");
806 return BUDB_INTERNALERROR;
809 /* Chain entry at front of bucket;
810 * first threadOffset of entry = bucket
811 * then bucket = addr of entry
814 (ut, ea, e, mht->threadOffset, block->b.bucket[bo])
815 || set_word_addr(ut, block->a, &block->b,
816 &block->b.bucket[bo], htonl(ea)))
820 if (--(*opQuota) == 0)
828 * The hash table is needs to be re-sized. Move entries from the old
833 ht_MoveEntries(ut, mht)
834 struct ubik_trans *ut;
835 struct memoryHashTable *mht;
837 struct memoryHTBlock *block;
843 if (mht->oldLength == 0)
846 LogDebug(3, "ht_MoveEntries:\n");
847 /* we assume here that the hash function will map numbers smaller than the
848 * size of the hash table straight through to hash table indexes.
850 hash = mht->progress;
852 /* get hash table block ? */
853 code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
858 return BUDB_INTERNALERROR;
860 count = 10; /* max. # entries to move */
863 if (block->b.bucket[bo]) {
864 code = ht_HashInList(ut, mht, &count, block, bo);
866 Log("ht_MoveEntries: ht_HashInList failed\n");
871 if (block->b.bucket[bo] == 0) {
872 /* this bucket is now empty */
876 /* don't exceed the quota of items to be moved */
880 } while (++bo < nHTBuckets);
882 if (mht->progress >= mht->oldLength)
883 return (ht_FreeTable(ut, mht));
885 if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
886 Log("ht_MoveEntries: progress set failed\n");
895 ht_MoveEntries(ut, mht)
896 struct ubik_trans *ut;
897 struct memoryHashTable *mht;
901 struct memoryHTBlock *block;
904 if (mht->oldLength == 0)
907 LogDebug(3, "ht_MoveEntries:\n");
908 /* we assume here that the hash function will map numbers smaller than the
909 * size of the hash table straight through to hash table indexes.
911 hash = mht->progress;
913 /* get hash table block ? */
914 code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
919 return BUDB_INTERNALERROR;
923 if (block->b.bucket[bo]) {
924 code = ht_HashInList(ut, mht, ntohl(block->b.bucket[bo]));
926 Log("ht_MoveEntries: ht_HashInList failed\n");
930 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
933 Log("ht_MoveEntries: clear old entry failed\n");
938 } while (++bo < nHTBuckets);
940 if (mht->progress >= mht->oldLength)
941 return (ht_FreeTable(ut, mht));
943 if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
944 Log("ht_MoveEntries: progress set failed\n");
952 ht_HashIn(ut, mht, ea, e)
953 struct ubik_trans *ut;
954 struct memoryHashTable *mht;
955 dbadr ea; /* block db address */
956 char *e; /* entry's address (in b) */
958 struct hashTable *ht;
960 struct memoryHTBlock *block;
964 if (!(mht && (ht = mht->ht)))
965 db_panic("some ht called with bad mht");
967 if (code = ht_MaybeAdjust(ut, mht))
969 if (mht->length == 0)
970 if (code = ht_AllocTable(ut, mht))
973 hash = ht_HashEntry(mht, e);
974 code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
978 return BUDB_INTERNALERROR;
980 code = set_word_offset(ut, ea, e, mht->threadOffset, block->b.bucket[bo]);
983 LogDebug(5, "Hashin: set %d to %d\n", mht->threadOffset,
984 block->b.bucket[bo]);
987 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
991 LogDebug(5, "Hashin: set %d to %d\n", &block->b.bucket[bo], htonl(ea));
994 set_word_addr(ut, 0, &db.h, &ht->entries,
995 htonl(ntohl(ht->entries) + 1));
999 return ht_MoveEntries(ut, mht);
1002 /* RemoveFromList - generic procedure to delete an entry from a list given its
1003 * head and thread offset. Only a single long is modified by this routine.
1004 * The head pointer is modified, in place, using set_word_addr if the entry is
1005 * at the head of the list, otherwise only the thread of the previous entry is
1006 * modified. The entry pointer is only used to calculate the thread offset,
1007 * but is not otherwise used. */
1010 RemoveFromList(ut, ea, e, head, ta, t, thread)
1011 struct ubik_trans *ut;
1012 dbadr ea; /* db addr of head structure */
1013 char *e; /* head structure */
1014 dbadr *head; /* address of head pointer */
1015 dbadr ta; /* db addr of strucure to be removed */
1016 char *t; /* structure being removed */
1017 dbadr *thread; /* pointer to thread pointer */
1020 int threadOffset = ((char *)thread - t);
1021 dbadr next_a; /* db addr of next element in list */
1022 dbadr loop_a; /* db addr of current list element */
1025 return -1; /* empty list: not found */
1026 next_a = ntohl(*head); /* start at head of list */
1027 if (next_a == ta) { /* remove from head of list */
1028 code = set_word_addr(ut, ea, e, head, *thread);
1034 dbread(ut, loop_a + threadOffset, (char *)&next_a, sizeof(dbadr));
1038 return -1; /* end of list: not found */
1039 } while (ta != (next_a = ntohl(next_a)));
1040 code = dbwrite(ut, loop_a + threadOffset, (char *)thread, sizeof(dbadr));
1045 ht_HashOutT(ut, mht, hash, ea, e, old)
1046 struct ubik_trans *ut;
1047 struct memoryHashTable *mht;
1053 struct memoryHTBlock *block;
1057 if ((old ? mht->oldLength : mht->length) == 0)
1059 code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
1062 if ((block == 0) || (block->b.bucket[bo] == 0))
1066 RemoveFromList(ut, block->a, (char *)&block->b, &block->b.bucket[bo],
1067 ea, e, (dbadr *) (e + mht->threadOffset));
1072 unthread_ea = *(afs_int32 *) ((char *)e + mht->threadOffset);
1073 if (block->b.bucket[bo] == net_ea) {
1075 (ut, block->a, &block->b, &block->b.bucket[bo], unthread_ea))
1079 loop_a = ntohl(block->b.bucket[bo]);
1082 (ut, loop_a + mht->threadOffset, (char *)&next_loop_a,
1085 if (next_loop_a == 0)
1086 return -1; /* not found */
1087 if (net_ea == next_loop_a) {
1089 (ut, loop_a + mht->threadOffset, (char *)&unthread_ea,
1094 loop_a = ntohl(next_loop_a);
1099 (ut, 0, &db.h, &mht->ht->entries, htonl(ntohl(mht->ht->entries) - 1)))
1105 ht_HashOut(ut, mht, ea, e)
1106 struct ubik_trans *ut;
1107 struct memoryHashTable *mht;
1115 db_panic("some ht called with bad mht");
1116 hash = ht_HashEntry(mht, e);
1117 if (mht->oldLength) {
1118 code = ht_HashOutT(ut, mht, hash, ea, e, 1 /*old */ );
1121 else if (code != -1)
1124 if (mht->length == 0) /* not found */
1125 ERROR(BUDB_INTERNALERROR);
1126 code = ht_HashOutT(ut, mht, hash, ea, e, 0 /*old */ );
1132 code = ht_MoveEntries(ut, mht);
1135 code = ht_MaybeAdjust(ut, mht);
1143 /* generic hash table traversal routines */
1147 scanHashTableBlock(ut, mhtPtr, htBlockPtr, old, length, index, selectFn,
1148 operationFn, rockPtr)
1149 struct ubik_trans *ut;
1150 struct memoryHashTable *mhtPtr;
1151 struct htBlock *htBlockPtr;
1153 afs_int32 length; /* size of whole hash table */
1154 int index; /* base index of this block */
1156 int (*operationFn) ();
1159 int type; /* hash table type */
1160 int entrySize; /* hashed entry size */
1162 afs_uint32 *mapEntryPtr = 0; /* for status checks */
1164 char entry[sizeof(struct block)];
1165 dbadr entryAddr, nextEntryAddr;
1170 type = ntohl(mhtPtr->ht->functionType);
1171 entrySize = sizeFunctions[type];
1173 /* step through this hash table block, being careful to stop
1174 * before the end of the overall hash table
1177 for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) { /*f */
1179 nextEntryAddr = ntohl(htBlockPtr->bucket[i]);
1181 /* if this is the old hash table, all entries below the progress mark
1182 * should have been moved to the new hash table
1184 if (old && (index < mhtPtr->progress) && nextEntryAddr)
1185 return BUDB_INTERNALERROR;
1187 /* now walk down the chain of each bucket */
1188 while (nextEntryAddr) { /*w */
1190 entryAddr = nextEntryAddr;
1191 if (dbread(ut, entryAddr, &entry[0], entrySize))
1192 return (BUDB_INTERNALERROR);
1194 if ((*selectFn) (entryAddr, &entry[0], rockPtr)) {
1195 (*operationFn) (entryAddr, &entry[0], rockPtr);
1199 ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
1208 scanHashTable(ut, mhtPtr, selectFn, operationFn, rockPtr)
1209 struct ubik_trans *ut;
1210 struct memoryHashTable *mhtPtr;
1212 int (*operationFn) ();
1215 struct htBlock hashTableBlock;
1216 dbadr tableAddr; /* disk addr of hash block */
1217 int tableLength; /* # entries */
1218 int blockLength; /* # blocks */
1220 int blockIndex, entryIndex;
1225 extern int nHTBuckets; /* # buckets in a hash table */
1227 for (old = 0; old <= 1; old++) { /*fo */
1229 /* check the old hash table */
1230 tableLength = mhtPtr->oldLength;
1231 if (tableLength == 0)
1232 continue; /* nothing to do */
1234 tableAddr = ntohl(mhtPtr->ht->oldTable);
1236 /* check current hash table */
1237 tableLength = mhtPtr->length;
1238 if (tableLength == 0)
1239 continue; /* nothing to do */
1241 tableAddr = ntohl(mhtPtr->ht->table);
1244 blockLength = (tableLength - 1) / nHTBuckets;
1247 /* follow the hash chain */
1248 for (i = 0; i <= blockLength; i++) { /*fi */
1249 /* chain too short */
1251 ERROR(BUDB_DATABASEINCONSISTENT);
1254 dbread(ut, tableAddr, &hashTableBlock,
1255 sizeof(hashTableBlock));
1260 scanHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
1261 tableLength, hashIndex, selectFn,
1262 operationFn, rockPtr);
1266 hashIndex += nHTBuckets;
1267 tableAddr = ntohl(hashTableBlock.h.next);