Bug Summary

File:budb/db_hash.c
Location:line 1082, column 2
Description:Assigned value is always the same as the existing value

Annotated Source Code

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