gcc 4.5: Sequence point warning fixes
[openafs.git] / src / budb / db_hash.c
1 /*
2  * Copyright 2000, International Business Machines Corporation and others.
3  * All Rights Reserved.
4  * 
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
8  */
9
10 #include <afsconfig.h>
11 #include <afs/param.h>
12
13
14 #ifdef AFS_NT40_ENV
15 #include <winsock2.h>
16 #else
17 #include <netinet/in.h>
18 #endif
19 #include <string.h>
20 #include <sys/types.h>
21 #include <afs/stds.h>
22 #include <ubik.h>
23 #include <afs/bubasics.h>
24 #include "budb_errs.h"
25 #include "database.h"
26 #include "budb_internal.h"
27 #include "error_macros.h"
28
29
30 int sizeFunctions[HT_MAX_FUNCTION + 1];
31 int nHTBuckets = NhtBucketS;    /* testing: we need small HT blocks */
32
33 int ht_minHBlocks(struct memoryHashTable *mht);
34
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. */
38
39 int
40 ht_TableSize(int length)
41 {
42     int n;
43     if (length == 0)
44         return 0;
45     n = (length + nHTBuckets - 1) / nHTBuckets;
46     return n * sizeof(struct memoryHTBlock *);
47 }
48
49 /* ht_ResetT - resets the in-memory representation of a hashtable block array.
50  * It also resets the global variable nHTBuckets. */
51
52 static void
53 ht_ResetT(struct memoryHTBlock ***blocksP, int *sizeP, int length)
54 {
55     struct memoryHTBlock **b = *blocksP;
56     int newsize;
57     int n;
58     int i;
59
60     nHTBuckets = ntohl(db.h.nHTBuckets);
61     if (b) {
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++)
67                 if (b[i])
68                     free(b[i]);
69             free(b);
70             *sizeP = 0;
71             *blocksP = 0;
72         } else {
73             /* invalidate the blocks of the array  */
74             for (i = 0; i < n; i++)
75                 if (b[i])
76                     b[i]->valid = 0;
77         }
78     }
79 }
80
81 /* ht_Reset
82  *      reinitialize a memory hash table. 
83  *      Calls ht_ResetT to invalidate the two block arrays.
84  */
85
86 void
87 ht_Reset(struct memoryHashTable *mht)
88 {
89     struct hashTable *ht = NULL;
90
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);
99 }
100
101 /* InitDBhash - When server starts, do hash table initialization.
102      test - initialization parameters: bit 4 is small ht. */
103
104 afs_int32
105 InitDBhash(void)
106 {
107     sizeFunctions[0] = 0;
108
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);
113
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;
118     return 0;
119 }
120
121 /* ht_DBInit - When rebuilding database, this sets up the hash tables. */
122
123 void
124 ht_DBInit(void)
125 {
126     db.h.nHTBuckets = htonl(nHTBuckets);
127
128     {
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);
133     }
134     {
135         struct tape *s = 0;
136         db.h.tapeName.threadOffset =
137             htonl((char *)&s->nameHashChain - (char *)s);
138         db.h.tapeName.functionType = htonl(HT_tapeName_FUNCTION);
139     }
140     {
141         struct dump *s = 0;
142         db.h.dumpName.threadOffset =
143             htonl((char *)&s->nameHashChain - (char *)s);
144         db.h.dumpName.functionType = htonl(HT_dumpName_FUNCTION);
145
146         db.h.dumpIden.threadOffset =
147             htonl((char *)&s->idHashChain - (char *)s);
148         db.h.dumpIden.functionType = htonl(HT_dumpIden_FUNCTION);
149     }
150     ht_Reset(&db.volName);
151     ht_Reset(&db.tapeName);
152     ht_Reset(&db.dumpName);
153     ht_Reset(&db.dumpIden);
154 }
155
156 afs_int32
157 ht_AllocTable(struct ubik_trans *ut, struct memoryHashTable *mht)
158 {
159     struct hashTable *ht = NULL;
160     afs_int32 code;
161     int len;
162     int nb, mnb;                /* number of blocks for hashTable */
163     int i;
164     struct memoryHTBlock **b;
165     afs_int32 *plen;
166
167     if (!(mht && (ht = mht->ht)))
168         db_panic("some ht called with bad mht");
169     if (ht->length || mht->blocks)
170         db_panic("previous table still allocated");
171
172     len = ntohl(ht->entries) * 2;       /* allow room to grow */
173     nb = (len + nHTBuckets - 1) / nHTBuckets;
174     mnb = ht_minHBlocks(mht);
175     if (nb < mnb)
176         nb = mnb;               /* use minimum */
177     len = nb * nHTBuckets;      /* new hash table length */
178
179     mht->size = nb * sizeof(struct memoryHTBlock *);
180     b = mht->blocks = (struct memoryHTBlock **)malloc(mht->size);
181     memset(b, 0, mht->size);
182
183     for (i = 0; i < nb; i++) {
184         b[i] = (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
185         code = AllocBlock(ut, (struct block *)&b[i]->b, &b[i]->a);
186         if (code)
187             return code;
188         b[i]->valid = 0;
189
190         b[i]->b.h.type = hashTable_BLOCK;
191
192         /* thread the blocks */
193         if (i)
194             b[i - 1]->b.h.next = htonl(b[i]->a);
195     }
196     for (i = 0; i < nb; i++) {
197         code =
198             dbwrite(ut, b[i]->a, (char *)&b[i]->b,
199                     sizeof(struct htBlock) + (nHTBuckets -
200                                               NhtBucketS) * sizeof(dbadr));
201         if (code)
202             return code;
203     }
204     if ((code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a))))
205         return code;
206
207     plen = &ht->length;
208     if ((code = set_word_addr(ut, 0, &db.h, plen, htonl(len))))
209         return code;
210     mht->length = len;
211     return 0;
212 }
213
214 afs_int32
215 ht_FreeTable(struct ubik_trans *ut, struct memoryHashTable *mht)
216 {
217     struct hashTable *ht = NULL;
218     afs_int32 code;
219     struct blockHeader bh;
220     dbadr a, na;
221     afs_int32 *plen, *pprog;
222
223     if (!(mht && (ht = mht->ht)))
224         db_panic("some ht called with bad mht");
225     if (ht->oldLength == 0)
226         db_panic("no table to free");
227
228     ht_ResetT(&mht->oldBlocks, &mht->oldSize, 0);
229
230     for (a = ntohl(ht->oldTable); a; a = na) {
231         if (dbread(ut, a, (char *)&bh, sizeof(bh))) {
232             Log("ht_FreeTable: dbread failed\n");
233             return BUDB_IO;
234         }
235         na = ntohl(bh.next);
236         if ((code = FreeBlock(ut, &bh, a)))
237             return code;
238     }
239     plen = &ht->oldLength;
240     pprog = &ht->progress;
241     if (set_word_addr(ut, 0, &db.h, &ht->oldTable, 0)
242         || set_word_addr(ut, 0, &db.h, plen, 0)
243         || set_word_addr(ut, 0, &db.h, pprog, 0))
244         return BUDB_IO;
245     mht->oldLength = mht->progress = 0;
246     return 0;
247 }
248
249 afs_int32
250 ht_GetTableBlock(struct ubik_trans *ut, struct memoryHashTable *mht, 
251                  afs_uint32 hash, int old, struct memoryHTBlock **blockP, 
252                  int *boP)
253 {
254     struct hashTable *ht = NULL;
255     struct memoryHTBlock **b;
256     int hi, bi;
257     struct memoryHTBlock ***blocksP;
258     int *sizeP;
259     int n;
260     int i;
261     int length;
262     dbadr ta = 0;
263
264     if ((mht == 0)
265         || ((ht = mht->ht) == 0)
266         ) {
267         db_panic("some ht called with bad mht");
268     }
269
270     *blockP = 0;
271
272     if (old) {
273         if ((length = mht->oldLength) == 0)
274             return 0;           /* no entries */
275         hi = hash % length;
276         if (hi < mht->progress)
277             return 0;           /* no such entry */
278         blocksP = &mht->oldBlocks;
279         sizeP = &mht->oldSize;
280     } else {
281         if ((length = mht->length) == 0)
282             return 0;           /* no entries */
283         hi = hash % length;
284         blocksP = &mht->blocks;
285         sizeP = &mht->size;
286     }
287
288     bi = hi / nHTBuckets;       /* block index */
289     *boP = hi - bi * nHTBuckets;        /* block offset ptr */
290
291     if (*blocksP == 0) {
292         *sizeP = ht_TableSize(length);
293         *blocksP = (struct memoryHTBlock **)malloc(*sizeP);
294         memset(*blocksP, 0, *sizeP);
295     }
296     n = *sizeP / sizeof(struct memoryHTBlock *);
297     if (bi >= n)
298         db_panic("table size inconsistent");
299     b = *blocksP;
300
301     /* find an allocated block or the beginning of the block array */
302     for (i = bi; (i > 0) && (b[i] == 0); i--);
303
304     while (1) {
305         if (b[i] == 0) {
306             if (i == 0) {       /* the first block is found from the hashTable */
307                 ta = ntohl(old ? ht->oldTable : ht->table);
308                 if (ta == 0)
309                     db_panic("non-zero length, but no table");
310             }
311             /* else ta is set from last time around loop */
312             b[i] =
313                 (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
314             b[i]->a = ta;
315             b[i]->valid = 0;
316         }
317
318         if (!b[i]->valid) {
319             if (dbread(ut, b[i]->a, (char *)&b[i]->b, sizeof(struct htBlock)))
320                 return BUDB_IO;
321             b[i]->valid = 1;
322         }
323
324         if (i == bi) {
325             *blockP = b[bi];
326             /* printf("ht_GetTableBlock: hash %d block %d offset %d\n",
327              * hash, *blockP, *boP); */
328             return 0;
329         }
330
331         ta = ntohl(b[i++]->b.h.next);   /* get next ptr from current block */
332     }
333 }
334
335 /* ht_MaybeAdjust
336  *      Decide when to push the current hash table to the old hash table.
337  *      The entries in the old hash table are VALID, and are slowly hashed
338  *      into the current table.
339  */
340
341 static afs_int32
342 ht_MaybeAdjust(struct ubik_trans *ut, struct memoryHashTable *mht)
343 {
344     struct hashTable *ht = mht->ht;
345     int numberEntries = ntohl(ht->entries);
346
347     /* old hash table must be empty */
348     if (mht->oldLength != 0)
349         return (0);
350
351     /*
352      * It costs a lot to grow and shrink the hash table. Therefore, we will not
353      * shrink the hash table (only grow it). If the table is more than 2 entries per
354      * chain (average) we need to grow: push the entries to the old hash table.
355      *
356      * Don't shrink it:
357      * || ((mht->length > nHTBuckets) && (numberEntries*8 < mht->length))
358      */
359
360     /* Only grow a hash table if the number of entries is twice the
361      * number of hash length and is less than 20,450 (20 hash blocks). This
362      * means that the volname hash table will not grow (its initial
363      * hashtable size contains 30,600 buckets). Earlier revisions of
364      * the buserver have the initial size at 510 and 5,100 buckets -
365      * in which case we do want to grow it). We don't grow anything larger
366      * than 20,450 entries because it's expensive to re-hash everything.
367      */
368     if ((numberEntries > mht->length * 2) && (numberEntries < 20450)) { /* push current hash table to old hash table */
369         ht->oldLength = ht->length;
370         ht->oldTable = ht->table;
371         ht->progress = 0;
372         ht->length = 0;
373         ht->table = 0;
374         if (dbwrite
375             (ut, ((char *)ht - (char *)&db.h), (char *)ht, sizeof(*ht)))
376             return BUDB_IO;
377
378         ht_Reset(mht);
379         LogDebug(2, "ht_MaybeAdjust: push ht to old\n");
380     }
381     return 0;
382 }
383
384 dbadr
385 ht_LookupBucket(struct ubik_trans *ut, struct memoryHashTable *mht, 
386                 afs_uint32 hash, int old)
387 {
388     struct memoryHTBlock *block;
389     int bo;
390     afs_int32 code;
391
392     if ((old ? mht->oldLength : mht->length) == 0)
393         return 0;
394     code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
395     if (code || (block == 0))
396         return 0;
397     return ntohl(block->b.bucket[bo]);
398 }
399
400 /* This function is not too bad, for small hash tables, but suffers, I think,
401  * from insufficient mixing of the hash information. */
402
403 afs_uint32
404 Old2StringHashFunction(unsigned char *str)
405 {
406     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
407     while (*str)
408         hash = (hash << 1) + (hash >> 31) + *str++;
409     return hash;
410 }
411
412 /* This was actually a coding error, and produces dreadful results.  The
413  * problem is that the hash needs to be mixed up not the incoming character. */
414
415 afs_uint32
416 Old3StringHashFunction(unsigned char *str)
417 {
418     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
419     while (*str)
420         hash += (*str++) * 0x072a51a4;
421     return hash;
422 }
423
424 /* This function is pretty good.  Its main problem is that the low two bits of
425  * the hash multiplier are zero which tends to shift information too far left.
426  * It behaves especially badly for hash tables whose size is a power of two. */
427
428 afs_uint32
429 Old4StringHashFunction(unsigned char *str)
430 {
431     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
432     while (*str)
433         hash = (*str++) + hash * 0x072a51a4;
434     return hash;
435 }
436
437 /* While this is good for a hash table with 500 buckets it is nearly as bad as
438  * #3 with a hash table as big as 8200. */
439
440 afs_uint32
441 Old5StringHashFunction(unsigned char *str)
442 {
443     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
444     while (*str)
445         hash += (*str++);
446     return hash;
447 }
448
449 /* This was an attempt to produce a hash function with the smallest and
450  * simplest mixing multiplier.  This is only a little worse than the real one,
451  * and the difference seems to be smaller with larger hash tables.  It behaves
452  * better than the random hash function. */
453
454 afs_uint32
455 Old6StringHashFunction(unsigned char *str)
456 {
457     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
458     while (*str)
459         hash = hash * 0x81 + (*str++);
460     return hash;
461 }
462
463 /* This actually seems to be little better then the real one.  Having the same
464  * number of bits but only 5 bits apart seems to produce worse results but
465  * having the bits spanning the same range farther apart also doesn't do as
466  * well.  All these differences are fairly small, however. */
467
468 afs_uint32
469 Old7StringHashFunction(unsigned char *str)
470 {
471     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
472     while (*str)
473         hash = hash * 0x42108421 + (*str++);
474     return hash;
475 }
476
477 /* This function tries to provide some non-linearity by providing some feedback
478  * from higher-order bits in the word.  It also uses shifts instead of
479  * multiplies, which may be faster on some architectures. */
480
481 afs_uint32
482 Old8StringHashFunction(unsigned char *str)
483 {
484     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
485     while (*str)
486         hash =
487             hash + (hash << 7) + (hash << 14) + (hash << 21) + (hash << 28) +
488             (hash >> 17) + *str++;
489     return hash;
490 }
491
492 /* This is the result of the above search for good hash functions.  It seems
493  * that the choice of multipliers is somewhat arbitrary but has several
494  * constraints.  It shouldn't have too many or too few one bits and should be
495  * odd.  It behaves beeter than the random hash function. */
496
497 afs_uint32
498 StringHashFunction(unsigned char *str)
499 {
500     afs_uint32 hash = 1000003;  /* big prime to make "" hash nicely */
501     /* The multiplicative constant should be odd and have a goodly number of
502      * one bits. */
503     while (*str)
504         hash = (*str++) + hash * 0x10204081;
505     return hash;
506 }
507
508 afs_uint32
509 IdHashFunction(afs_uint32 id)
510 {
511     afs_uint32 l, r;
512     id *= 81847;
513     l = id | 0xaaaaaaaa;
514     r = id | 0x55555555;
515     return (l * r);
516 }
517
518 /* The minimum hash table blocks to allocate. Each block contains 510
519  * buckets. They hash table grows when the number of entries reaches
520  * twice the number of buckets.
521  */
522 int
523 ht_minHBlocks(struct memoryHashTable *mht)
524 {
525     int retval;
526
527     switch (ntohl(mht->ht->functionType)) {
528     case HT_dumpIden_FUNCTION:
529     case HT_dumpName_FUNCTION:  /* hash table able to handle (befor it grows) ... */
530         retval = 2;             /*     1,020 dump entries */
531         break;
532
533     case HT_tapeName_FUNCTION:
534         retval = 4;             /*      2,040 tape entries */
535         break;
536
537     case HT_volName_FUNCTION:
538         retval = 60;            /*     61,200 volInfo entries (with different names) */
539         break;
540
541     default:
542         db_panic("Illegal hash function type");
543         retval = -1; /* not reached */
544     }
545     return (retval);
546 }
547
548 afs_uint32
549 ht_HashEntry(struct memoryHashTable *mht, 
550              char *e)                           /* entry's address (in b) */
551 {
552     int type = ntohl(mht->ht->functionType);
553     afs_uint32 retval;
554
555     switch (type) {
556     case HT_dumpIden_FUNCTION:
557         retval = IdHashFunction(ntohl(((struct dump *)e)->id));
558         LogDebug(5, "HashEntry: dumpid returns %d\n", retval);
559         break;
560
561     case HT_dumpName_FUNCTION:
562         retval = StringHashFunction((unsigned char *)((struct dump *)e)->dumpName);
563         LogDebug(5, "HashEntry: dumpname returns %d\n", retval);
564         break;
565
566     case HT_tapeName_FUNCTION:
567         retval = StringHashFunction((unsigned char *)((struct tape *)e)->name);
568         LogDebug(5, "HashEntry: tapename returns %d\n", retval);
569         break;
570
571     case HT_volName_FUNCTION:
572         retval = StringHashFunction((unsigned char *)((struct volInfo *)e)->name);
573         LogDebug(5, "HashEntry: volname returns %d\n", retval);
574         break;
575
576     default:
577         db_panic("illegal hash function");
578         retval = -1; /* not reached */
579     }
580
581     return (retval);
582 }
583
584
585 /* ht_GetType
586  *      returns a ptr to the memory hash table for the specified hash
587  *      list.
588  */
589
590 struct memoryHashTable *
591 ht_GetType(int type, int *e_sizeP)
592 {
593     struct memoryHashTable *mht;
594
595     if ((type <= 0) || (type > HT_MAX_FUNCTION))
596         return 0;
597
598     if (e_sizeP)
599         *e_sizeP = sizeFunctions[type];
600     switch (type) {
601     case HT_dumpIden_FUNCTION:
602         mht = &db.dumpIden;
603         break;
604
605     case HT_dumpName_FUNCTION:
606         mht = &db.dumpName;
607         break;
608
609     case HT_tapeName_FUNCTION:
610         mht = &db.tapeName;
611         break;
612
613     case HT_volName_FUNCTION:
614         mht = &db.volName;
615         break;
616
617     default:
618         return 0;
619     }
620     if (ntohl(mht->ht->functionType) != type)
621         db_panic("ht types don't match");
622     return mht;
623 }
624
625 static int
626 ht_KeyMatch(int type, char *key, char *e)
627 {
628     switch (type) {
629     case HT_dumpIden_FUNCTION:
630         return *(dumpId *) key == ntohl(((struct dump *)e)->id);
631     case HT_dumpName_FUNCTION:
632         return strcmp(key, ((struct dump *)e)->dumpName) == 0;
633     case HT_tapeName_FUNCTION:
634         return strcmp(key, ((struct tape *)e)->name) == 0;
635     case HT_volName_FUNCTION:
636         return strcmp(key, ((struct volInfo *)e)->name) == 0;
637
638     default:
639         db_panic("illegal hash function");
640     }
641     /* not reached */
642     return 0;
643 }
644
645 /* ht_LookupEntry
646  * entry:
647  *      ut - ubik transaction
648  *      mht - memory hash table ptr
649  *      key - hash and lookup key
650  * exit:
651  *      eaP - dbaddr of entry found or zero if failed
652   *     e - contents of located entry
653  */
654
655 afs_int32
656 ht_LookupEntry(struct ubik_trans *ut, 
657                struct memoryHashTable *mht, 
658                void *key,       /* pointer to lookup key to match */
659                dbadr *eaP,      /* db addr of entry found or zero */
660                void *e)         /* contents of located entry */
661 {
662     struct hashTable *ht = NULL;
663     int type;
664     int e_size;
665     int old;
666     afs_uint32 hash;
667     dbadr a;
668
669     if (!key || !eaP || !e)
670         db_panic("null ptrs passed to LookupEntry");
671     if (!(mht && (ht = mht->ht)))
672         db_panic("some ht called with bad mht");
673
674     *eaP = 0;                   /* initialize not-found indicator */
675
676     type = ntohl(ht->functionType);
677     e_size = sizeFunctions[type];
678     if (type == HT_dumpIden_FUNCTION)
679         hash = IdHashFunction(*(dumpId *) key);
680     else
681         hash = StringHashFunction(key);
682
683     for (old = 0;; old++) {
684         a = ht_LookupBucket(ut, mht, hash, old);
685         while (a) {
686             if (dbread(ut, a, e, e_size))
687                 return BUDB_IO;
688             if (ht_KeyMatch(type, key, e)) {
689                 *eaP = a;
690                 return 0;
691             }
692             a = ntohl(*(dbadr *) ((char *)e + mht->threadOffset));
693         }
694         if (old)
695             return 0;
696     }
697 }
698
699 /* ht_HashInList
700  * entry:
701  *      opQuota - max # of items to move
702  * exit:
703  *      opQuota - adjusted to reflect # of moves
704  */
705
706 static afs_int32
707 ht_HashInList(struct ubik_trans *ut, struct memoryHashTable *mht, 
708               int *opQuota, struct memoryHTBlock *block, int blockOffset)
709 {
710     struct hashTable *ht = mht->ht;
711     afs_int32 code;
712     dbadr ea, next_ea;
713     dbadr listA;
714     char e[sizeof(struct block)];       /* unnecessarily conservative */
715     int e_size = sizeFunctions[ntohl(ht->functionType)];
716
717     if (mht->length == 0) {
718         if ((code = ht_AllocTable(ut, mht))) {
719             Log("ht_HashInList: ht_AllocTable failed\n");
720             return code;
721         }
722     }
723
724     listA = ntohl(block->b.bucket[blockOffset]);
725
726     if (listA == 0) {
727         Log("ht_HashInList: expecting non-zero bucket\n");
728         return 0;
729     }
730
731     for (ea = listA; ea; ea = next_ea) {        /*f */
732
733         LogDebug(3, "ht_HashInList: move entry at %d, type %d\n", ea,
734                  ntohl(mht->ht->functionType));
735
736         if (dbread(ut, ea, e, e_size))
737             return BUDB_IO;
738
739         /* LogNetDump((struct dump *) e); */
740
741         /* get the address of the next item on the list */
742         next_ea = ntohl(*(dbadr *) (e + mht->threadOffset));
743
744         /* write the link into the bucket */
745         code =
746             set_word_addr(ut, block->a, &block->b,
747                           &block->b.bucket[blockOffset], htonl(next_ea));
748         if (code) {
749             Log("ht_HashInList: bucket update failed\n");
750             return (code);
751         }
752
753         {
754             struct memoryHTBlock *block;
755             int bo;
756             afs_uint32 hash;
757
758             /* get the hash value */
759             hash = ht_HashEntry(mht, e) % mht->length;
760             LogDebug(4, "ht_HashInList: moved to %d\n", hash);
761
762             /* get the new hash table block */
763             code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
764             if (code) {
765                 Log("ht_HashInList: ht_GetTableBlock failed\n");
766                 return code;
767             }
768             if (block == 0) {
769                 Log("ht_HashInList: ht_GetTableBlock returned 0\n");
770                 return BUDB_INTERNALERROR;
771             }
772
773             /* Chain entry at front of bucket;
774              * first threadOffset of entry = bucket
775              * then bucket = addr of entry
776              */
777             if (set_word_offset
778                 (ut, ea, e, mht->threadOffset, block->b.bucket[bo])
779                 || set_word_addr(ut, block->a, &block->b,
780                                  &block->b.bucket[bo], htonl(ea)))
781                 return BUDB_IO;
782         }
783
784         if (--(*opQuota) == 0)
785             break;
786     }                           /*f */
787     return 0;
788 }
789
790
791 /* ht_MoveEntries
792  *      The hash table is needs to be re-sized. Move entries from the old
793  *      to the new.
794  */
795
796 static afs_int32
797 ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
798 {
799     struct memoryHTBlock *block;
800     afs_uint32 hash;
801     int count;
802     int bo;
803     afs_int32 code;
804     afs_int32 *pprog;
805
806     if (mht->oldLength == 0)
807         return 0;
808
809     LogDebug(3, "ht_MoveEntries:\n");
810     /* we assume here that the hash function will map numbers smaller than the
811      * size of the hash table straight through to hash table indexes.
812      */
813     hash = mht->progress;
814
815     /* get hash table block ? */
816     code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
817     if (code)
818         return code;
819
820     if (block == 0)
821         return BUDB_INTERNALERROR;
822
823     count = 10;                 /* max. # entries to move */
824
825     do {
826         if (block->b.bucket[bo]) {
827             code = ht_HashInList(ut, mht, &count, block, bo);
828             if (code) {
829                 Log("ht_MoveEntries: ht_HashInList failed\n");
830                 return (BUDB_IO);
831             }
832         }
833
834         if (block->b.bucket[bo] == 0) {
835             /* this bucket is now empty */
836             mht->progress++;
837         }
838
839         /* don't exceed the quota of items to be moved */
840         if (count == 0)
841             break;
842
843     } while (++bo < nHTBuckets);
844
845     if (mht->progress >= mht->oldLength)
846         return (ht_FreeTable(ut, mht));
847
848     pprog = &mht->ht->progress;
849     if (set_word_addr(ut, 0, &db.h, pprog, htonl(mht->progress))) {
850         Log("ht_MoveEntries: progress set failed\n");
851         return BUDB_IO;
852     }
853     return 0;
854 }
855
856
857 #ifdef notdef
858 static afs_int32
859 ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
860 {
861     afs_uint32 hash;
862     int bo;
863     struct memoryHTBlock *block;
864     afs_int32 code;
865
866     if (mht->oldLength == 0)
867         return 0;
868
869     LogDebug(3, "ht_MoveEntries:\n");
870     /* we assume here that the hash function will map numbers smaller than the
871      * size of the hash table straight through to hash table indexes.
872      */
873     hash = mht->progress;
874
875     /* get hash table block ? */
876     code = ht_GetTableBlock(ut, mht, hash, 1 /*old */ , &block, &bo);
877     if (code)
878         return code;
879
880     if (block == 0)
881         return BUDB_INTERNALERROR;
882
883     do {
884         mht->progress++;
885         if (block->b.bucket[bo]) {
886             code = ht_HashInList(ut, mht, ntohl(block->b.bucket[bo]));
887             if (code) {
888                 Log("ht_MoveEntries: ht_HashInList failed\n");
889                 return (BUDB_IO);
890             }
891             code =
892                 set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
893                               0);
894             if (code) {
895                 Log("ht_MoveEntries: clear old entry failed\n");
896                 return BUDB_IO;
897             }
898             break;
899         }
900     } while (++bo < nHTBuckets);
901
902     if (mht->progress >= mht->oldLength)
903         return (ht_FreeTable(ut, mht));
904
905     if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
906         Log("ht_MoveEntries: progress set failed\n");
907         return BUDB_IO;
908     }
909     return 0;
910 }
911 #endif /* notdef */
912
913 afs_int32
914 ht_HashIn(struct ubik_trans *ut,
915           struct memoryHashTable *mht,
916           dbadr ea,                     /* block db address */
917           void *e)                      /* entry's address (in b) */
918 {
919     struct hashTable *ht = NULL;
920     afs_uint32 hash;
921     struct memoryHTBlock *block;
922     int bo;
923     afs_int32 code;
924     afs_int32 *pentries;
925
926     if (!(mht && (ht = mht->ht)))
927         db_panic("some ht called with bad mht");
928
929     if ((code = ht_MaybeAdjust(ut, mht)))
930         return code;
931     if (mht->length == 0)
932         if ((code = ht_AllocTable(ut, mht)))
933             return code;
934
935     hash = ht_HashEntry(mht, e);
936     code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
937     if (code)
938         return code;
939     if (!block)
940         return BUDB_INTERNALERROR;
941
942     code = set_word_offset(ut, ea, e, mht->threadOffset, block->b.bucket[bo]);
943     if (code)
944         return BUDB_IO;
945     LogDebug(5, "Hashin: set %d to %d\n", mht->threadOffset,
946              block->b.bucket[bo]);
947
948     code =
949         set_word_addr(ut, block->a, &block->b, &block->b.bucket[bo],
950                       htonl(ea));
951     if (code)
952         return BUDB_IO;
953     LogDebug(5, "Hashin: set %"AFS_PTR_FMT" to %d\n",
954              &block->b.bucket[bo], htonl(ea));
955
956     pentries = &ht->entries;
957     code =
958         set_word_addr(ut, 0, &db.h, pentries,
959                       htonl(ntohl(ht->entries) + 1));
960     if (code)
961         return BUDB_IO;
962
963     return ht_MoveEntries(ut, mht);
964 }
965
966 /* RemoveFromList - generic procedure to delete an entry from a list given its
967  * head and thread offset.  Only a single long is modified by this routine.
968  * The head pointer is modified, in place, using set_word_addr if the entry is
969  * at the head of the list, otherwise only the thread of the previous entry is
970  * modified.  The entry pointer is only used to calculate the thread offset,
971  * but is not otherwise used. */
972
973 afs_int32
974 RemoveFromList(struct ubik_trans *ut,
975                dbadr ea,        /* db addr of head structure */
976                void *e,         /* head structure */
977                dbadr *head,     /* address of head pointer */
978                dbadr ta,        /* db addr of strucure to be removed */
979                void *t,         /* structure being removed */
980                dbadr *thread)   /* pointer to thread pointer */
981 {
982     afs_int32 code;
983     int threadOffset = ((char *)thread - (char *)t);
984     dbadr next_a;               /* db addr of next element in list */
985     dbadr loop_a;               /* db addr of current list element */
986
987     if (*head == 0)
988         return -1;              /* empty list: not found */
989     next_a = ntohl(*head);      /* start at head of list */
990     if (next_a == ta) {         /* remove from head of list */
991         code = set_word_addr(ut, ea, e, head, *thread);
992         return code;
993     }
994     do {
995         loop_a = next_a;
996         code =
997             dbread(ut, loop_a + threadOffset, (char *)&next_a, sizeof(dbadr));
998         if (code)
999             return code;
1000         if (next_a == 0)
1001             return -1;          /* end of list: not found */
1002     } while (ta != (next_a = ntohl(next_a)));
1003     code = dbwrite(ut, loop_a + threadOffset, (char *)thread, sizeof(dbadr));
1004     return code;
1005 }
1006
1007 afs_int32
1008 ht_HashOutT(struct ubik_trans *ut, struct memoryHashTable *mht,
1009             afs_uint32 hash, dbadr ea, char *e, int old)
1010 {
1011     struct memoryHTBlock *block;
1012     int bo;
1013     afs_int32 code;
1014     afs_int32 *pentries;
1015
1016     if ((old ? mht->oldLength : mht->length) == 0)
1017         return -1;
1018     code = ht_GetTableBlock(ut, mht, hash, old, &block, &bo);
1019     if (code)
1020         return code;
1021     if ((block == 0) || (block->b.bucket[bo] == 0))
1022         return -1;
1023
1024     code =
1025         RemoveFromList(ut, block->a, (char *)&block->b, &block->b.bucket[bo],
1026                        ea, e, (dbadr *) (e + mht->threadOffset));
1027     if (code)
1028         return code;
1029 #if 0
1030     net_ea = htonl(ea);
1031     unthread_ea = *(afs_int32 *) ((char *)e + mht->threadOffset);
1032     if (block->b.bucket[bo] == net_ea) {
1033         if (set_word_addr
1034             (ut, block->a, &block->b, &block->b.bucket[bo], unthread_ea))
1035             return BUDB_IO;
1036         goto done;
1037     }
1038     loop_a = ntohl(block->b.bucket[bo]);
1039     while (1) {
1040         if (dbread
1041             (ut, loop_a + mht->threadOffset, (char *)&next_loop_a,
1042              sizeof(dbadr)))
1043             return BUDB_IO;
1044         if (next_loop_a == 0)
1045             return -1;          /* not found */
1046         if (net_ea == next_loop_a) {
1047             if (dbwrite
1048                 (ut, loop_a + mht->threadOffset, (char *)&unthread_ea,
1049                  sizeof(dbadr)))
1050                 return BUDB_IO;
1051             goto done;
1052         }
1053         loop_a = ntohl(next_loop_a);
1054     }
1055   done:
1056 #endif
1057     pentries = &mht->ht->entries;
1058     if (set_word_addr
1059         (ut, 0, &db.h, pentries, htonl(ntohl(mht->ht->entries) - 1)))
1060         return BUDB_IO;
1061     return 0;
1062 }
1063
1064 afs_int32
1065 ht_HashOut(struct ubik_trans *ut, struct memoryHashTable *mht, dbadr ea,
1066            void *e) 
1067 {
1068     afs_uint32 hash;
1069     afs_int32 code;
1070
1071     if (!mht)
1072         db_panic("some ht called with bad mht");
1073     hash = ht_HashEntry(mht, e);
1074     if (mht->oldLength) {
1075         code = ht_HashOutT(ut, mht, hash, ea, e, 1 /*old */ );
1076         if (code == 0)
1077             return 0;
1078         else if (code != -1)
1079             ERROR(code);
1080     }
1081     if (mht->length == 0)       /* not found */
1082         ERROR(BUDB_INTERNALERROR);
1083     code = ht_HashOutT(ut, mht, hash, ea, e, 0 /*old */ );
1084     if (code == -1)
1085         ERROR(BUDB_NOENT);
1086     if (code)
1087         ERROR(code);
1088
1089     code = ht_MoveEntries(ut, mht);
1090     if (code)
1091         ERROR(code);
1092     code = ht_MaybeAdjust(ut, mht);
1093     if (code)
1094         ERROR(code);
1095
1096   error_exit:
1097     return (code);
1098 }
1099
1100 /* generic hash table traversal routines */
1101
1102
1103 afs_int32
1104 scanHashTableBlock(struct ubik_trans *ut,
1105                    struct memoryHashTable *mhtPtr,
1106                    struct htBlock *htBlockPtr,
1107                    int old,
1108                    afs_int32 length,    /* size of whole hash table */
1109                    int index,           /* base index of this block */
1110                    int (*selectFn) (dbadr, void *, void *),
1111                    int (*operationFn) (dbadr, void *, void *),
1112                    void *rockPtr)
1113 {
1114     int type;                   /* hash table type */
1115     int entrySize;              /* hashed entry size */
1116
1117     char entry[sizeof(struct block)];
1118     dbadr entryAddr, nextEntryAddr;
1119
1120     int i;
1121
1122     type = ntohl(mhtPtr->ht->functionType);
1123     entrySize = sizeFunctions[type];
1124
1125     /* step through this hash table block, being careful to stop
1126      * before the end of the overall hash table
1127      */
1128
1129     for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) {   /*f */
1130         entryAddr = 0;
1131         nextEntryAddr = ntohl(htBlockPtr->bucket[i]);
1132
1133         /* if this is the old hash table, all entries below the progress mark
1134          * should have been moved to the new hash table
1135          */
1136         if (old && (index < mhtPtr->progress) && nextEntryAddr)
1137             return BUDB_INTERNALERROR;
1138
1139         /* now walk down the chain of each bucket */
1140         while (nextEntryAddr) { /*w */
1141
1142             entryAddr = nextEntryAddr;
1143             if (dbread(ut, entryAddr, &entry[0], entrySize))
1144                 return (BUDB_INTERNALERROR);
1145
1146             if ((*selectFn) (entryAddr, &entry[0], rockPtr)) {
1147                 (*operationFn) (entryAddr, &entry[0], rockPtr);
1148             }
1149
1150             nextEntryAddr =
1151                 ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
1152         }                       /*w */
1153
1154     }                           /*f */
1155
1156     return (0);
1157 }
1158
1159 afs_int32
1160 scanHashTable(struct ubik_trans *ut, struct memoryHashTable *mhtPtr,
1161               int (*selectFn) (dbadr, void *, void *), 
1162               int (*operationFn) (dbadr, void *, void *), 
1163               void *rockPtr)
1164 {
1165     struct htBlock hashTableBlock;
1166     dbadr tableAddr;            /* disk addr of hash block */
1167     int tableLength;            /* # entries */
1168     int blockLength;            /* # blocks */
1169     int hashIndex;
1170     int old;
1171     int i;
1172     afs_int32 code = 0;
1173
1174     extern int nHTBuckets;      /* # buckets in a hash table */
1175
1176     for (old = 0; old <= 1; old++) {    /*fo */
1177         if (old) {
1178             /* check the old hash table */
1179             tableLength = mhtPtr->oldLength;
1180             if (tableLength == 0)
1181                 continue;       /* nothing to do */
1182
1183             tableAddr = ntohl(mhtPtr->ht->oldTable);
1184         } else {
1185             /* check current hash table */
1186             tableLength = mhtPtr->length;
1187             if (tableLength == 0)
1188                 continue;       /* nothing to do */
1189
1190             tableAddr = ntohl(mhtPtr->ht->table);
1191         }
1192
1193         blockLength = (tableLength - 1) / nHTBuckets;
1194         hashIndex = 0;
1195
1196         /* follow the hash chain */
1197         for (i = 0; i <= blockLength; i++) {    /*fi */
1198             /* chain too short */
1199             if (tableAddr == 0)
1200                 ERROR(BUDB_DATABASEINCONSISTENT);
1201
1202             code =
1203                 dbread(ut, tableAddr, &hashTableBlock,
1204                        sizeof(hashTableBlock));
1205             if (code)
1206                 goto error_exit;
1207
1208             code =
1209                 scanHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
1210                                    tableLength, hashIndex, selectFn,
1211                                    operationFn, rockPtr);
1212             if (code)
1213                 goto error_exit;
1214
1215             hashIndex += nHTBuckets;
1216             tableAddr = ntohl(hashTableBlock.h.next);
1217         }                       /*fi */
1218     }                           /*fo */
1219
1220   error_exit:
1221     return (code);
1222 }