/*
* Copyright 2000, International Business Machines Corporation and others.
* All Rights Reserved.
- *
+ *
* This software has been released under the terms of the IBM Public
* License. For details, see the LICENSE file in the top-level source
* directory or online at http://www.openafs.org/dl/license10.html
#include <afsconfig.h>
#include <afs/param.h>
+#include <afs/stds.h>
-RCSID
- ("$Header$");
+#include <roken.h>
-#ifdef AFS_NT40_ENV
-#include <winsock2.h>
-#else
-#include <netinet/in.h>
-#endif
-#ifdef HAVE_STRING_H
-#include <string.h>
-#else
-#ifdef HAVE_STRINGS_H
-#include <strings.h>
-#endif
-#endif
-#include <sys/types.h>
-#include <afs/stds.h>
#include <ubik.h>
-#include <afs/auth.h>
#include <afs/bubasics.h>
+
#include "budb_errs.h"
#include "database.h"
+#include "budb_internal.h"
#include "error_macros.h"
int sizeFunctions[HT_MAX_FUNCTION + 1];
int nHTBuckets = NhtBucketS; /* testing: we need small HT blocks */
+int ht_minHBlocks(struct memoryHashTable *mht);
+
/* ht_TableSize - return the size of table necessary to represent a hashtable
* of given length in memory. It basically rounds the length up by the number
* of buckets per block. */
int
-ht_TableSize(length)
- int length;
+ht_TableSize(int length)
{
int n;
if (length == 0)
* It also resets the global variable nHTBuckets. */
static void
-ht_ResetT(blocksP, sizeP, length)
- struct memoryHTBlock ***blocksP;
- int *sizeP;
- int length;
+ht_ResetT(struct memoryHTBlock ***blocksP, int *sizeP, int length)
{
struct memoryHTBlock **b = *blocksP;
int newsize;
}
/* ht_Reset
- * reinitialize a memory hash table.
+ * reinitialize a memory hash table.
* Calls ht_ResetT to invalidate the two block arrays.
*/
void
-ht_Reset(mht)
- struct memoryHashTable *mht;
+ht_Reset(struct memoryHashTable *mht)
{
- struct hashTable *ht;
+ struct hashTable *ht = NULL;
if (!(mht && (ht = mht->ht)))
db_panic("some ht called with bad mht");
test - initialization parameters: bit 4 is small ht. */
afs_int32
-InitDBhash()
+InitDBhash(void)
{
sizeFunctions[0] = 0;
/* ht_DBInit - When rebuilding database, this sets up the hash tables. */
void
-ht_DBInit()
+ht_DBInit(void)
{
db.h.nHTBuckets = htonl(nHTBuckets);
}
afs_int32
-ht_AllocTable(ut, mht)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
+ht_AllocTable(struct ubik_trans *ut, struct memoryHashTable *mht)
{
- struct hashTable *ht;
+ struct hashTable *ht = NULL;
afs_int32 code;
int len;
int nb, mnb; /* number of blocks for hashTable */
int i;
struct memoryHTBlock **b;
+ afs_int32 *plen;
if (!(mht && (ht = mht->ht)))
db_panic("some ht called with bad mht");
len = nb * nHTBuckets; /* new hash table length */
mht->size = nb * sizeof(struct memoryHTBlock *);
- b = mht->blocks = (struct memoryHTBlock **)malloc(mht->size);
- memset(b, 0, mht->size);
+ b = mht->blocks = calloc(1, mht->size);
for (i = 0; i < nb; i++) {
- b[i] = (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
+ b[i] = malloc(sizeof(struct memoryHTBlock));
code = AllocBlock(ut, (struct block *)&b[i]->b, &b[i]->a);
if (code)
return code;
if (code)
return code;
}
- if (code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a)))
+ if ((code = set_word_addr(ut, 0, &db.h, &ht->table, htonl(b[0]->a))))
return code;
- if (code = set_word_addr(ut, 0, &db.h, &ht->length, htonl(len)))
+ plen = &ht->length;
+ if ((code = set_word_addr(ut, 0, &db.h, plen, htonl(len))))
return code;
mht->length = len;
return 0;
}
afs_int32
-ht_FreeTable(ut, mht)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
+ht_FreeTable(struct ubik_trans *ut, struct memoryHashTable *mht)
{
- struct hashTable *ht;
+ struct hashTable *ht = NULL;
afs_int32 code;
struct blockHeader bh;
dbadr a, na;
+ afs_int32 *plen, *pprog;
if (!(mht && (ht = mht->ht)))
db_panic("some ht called with bad mht");
return BUDB_IO;
}
na = ntohl(bh.next);
- if (code = FreeBlock(ut, &bh, a))
+ if ((code = FreeBlock(ut, &bh, a)))
return code;
}
+ plen = &ht->oldLength;
+ pprog = &ht->progress;
if (set_word_addr(ut, 0, &db.h, &ht->oldTable, 0)
- || set_word_addr(ut, 0, &db.h, &ht->oldLength, 0)
- || set_word_addr(ut, 0, &db.h, &ht->progress, 0))
+ || set_word_addr(ut, 0, &db.h, plen, 0)
+ || set_word_addr(ut, 0, &db.h, pprog, 0))
return BUDB_IO;
mht->oldLength = mht->progress = 0;
return 0;
}
afs_int32
-ht_GetTableBlock(ut, mht, hash, old, blockP, boP)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- afs_uint32 hash;
- int old;
- struct memoryHTBlock **blockP;
- int *boP;
+ht_GetTableBlock(struct ubik_trans *ut, struct memoryHashTable *mht,
+ afs_uint32 hash, int old, struct memoryHTBlock **blockP,
+ int *boP)
{
- struct hashTable *ht;
+ struct hashTable *ht = NULL;
struct memoryHTBlock **b;
int hi, bi;
struct memoryHTBlock ***blocksP;
int n;
int i;
int length;
- dbadr ta;
+ dbadr ta = 0;
if ((mht == 0)
|| ((ht = mht->ht) == 0)
if (*blocksP == 0) {
*sizeP = ht_TableSize(length);
- *blocksP = (struct memoryHTBlock **)malloc(*sizeP);
- memset(*blocksP, 0, *sizeP);
+ *blocksP = calloc(1, *sizeP);
}
n = *sizeP / sizeof(struct memoryHTBlock *);
if (bi >= n)
db_panic("non-zero length, but no table");
}
/* else ta is set from last time around loop */
- b[i] =
- (struct memoryHTBlock *)malloc(sizeof(struct memoryHTBlock));
+ b[i] = malloc(sizeof(struct memoryHTBlock));
b[i]->a = ta;
b[i]->valid = 0;
}
*/
static afs_int32
-ht_MaybeAdjust(ut, mht)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
+ht_MaybeAdjust(struct ubik_trans *ut, struct memoryHashTable *mht)
{
struct hashTable *ht = mht->ht;
int numberEntries = ntohl(ht->entries);
}
dbadr
-ht_LookupBucket(ut, mht, hash, old)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- afs_uint32 hash;
- int old;
+ht_LookupBucket(struct ubik_trans *ut, struct memoryHashTable *mht,
+ afs_uint32 hash, int old)
{
struct memoryHTBlock *block;
int bo;
* from insufficient mixing of the hash information. */
afs_uint32
-Old2StringHashFunction(str)
- unsigned char *str;
+Old2StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* problem is that the hash needs to be mixed up not the incoming character. */
afs_uint32
-Old3StringHashFunction(str)
- unsigned char *str;
+Old3StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* It behaves especially badly for hash tables whose size is a power of two. */
afs_uint32
-Old4StringHashFunction(str)
- unsigned char *str;
+Old4StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* #3 with a hash table as big as 8200. */
afs_uint32
-Old5StringHashFunction(str)
- unsigned char *str;
+Old5StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* better than the random hash function. */
afs_uint32
-Old6StringHashFunction(str)
- unsigned char *str;
+Old6StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* well. All these differences are fairly small, however. */
afs_uint32
-Old7StringHashFunction(str)
- unsigned char *str;
+Old7StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* multiplies, which may be faster on some architectures. */
afs_uint32
-Old8StringHashFunction(str)
- unsigned char *str;
+Old8StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
while (*str)
* odd. It behaves beeter than the random hash function. */
afs_uint32
-StringHashFunction(str)
- unsigned char *str;
+StringHashFunction(unsigned char *str)
{
afs_uint32 hash = 1000003; /* big prime to make "" hash nicely */
/* The multiplicative constant should be odd and have a goodly number of
}
afs_uint32
-IdHashFunction(id)
- afs_uint32 id;
+IdHashFunction(afs_uint32 id)
{
afs_uint32 l, r;
id *= 81847;
* twice the number of buckets.
*/
int
-ht_minHBlocks(mht)
- struct memoryHashTable *mht;
+ht_minHBlocks(struct memoryHashTable *mht)
{
int retval;
default:
db_panic("Illegal hash function type");
+ retval = -1; /* not reached */
}
return (retval);
}
afs_uint32
-ht_HashEntry(mht, e)
- struct memoryHashTable *mht;
- char *e; /* entry's address (in b) */
+ht_HashEntry(struct memoryHashTable *mht,
+ char *e) /* entry's address (in b) */
{
int type = ntohl(mht->ht->functionType);
afs_uint32 retval;
switch (type) {
case HT_dumpIden_FUNCTION:
retval = IdHashFunction(ntohl(((struct dump *)e)->id));
- LogDebug(5, "HashEntry: dumpid returns %d\n", retval);
+ LogDebug(5, "HashEntry: dumpid returns %u\n", retval);
break;
case HT_dumpName_FUNCTION:
- retval = StringHashFunction(((struct dump *)e)->dumpName);
- LogDebug(5, "HashEntry: dumpname returns %d\n", retval);
+ retval = StringHashFunction((unsigned char *)((struct dump *)e)->dumpName);
+ LogDebug(5, "HashEntry: dumpname returns %u\n", retval);
break;
case HT_tapeName_FUNCTION:
- retval = StringHashFunction(((struct tape *)e)->name);
- LogDebug(5, "HashEntry: tapename returns %d\n", retval);
+ retval = StringHashFunction((unsigned char *)((struct tape *)e)->name);
+ LogDebug(5, "HashEntry: tapename returns %u\n", retval);
break;
case HT_volName_FUNCTION:
- retval = StringHashFunction(((struct volInfo *)e)->name);
- LogDebug(5, "HashEntry: volname returns %d\n", retval);
+ retval = StringHashFunction((unsigned char *)((struct volInfo *)e)->name);
+ LogDebug(5, "HashEntry: volname returns %u\n", retval);
break;
default:
db_panic("illegal hash function");
+ retval = -1; /* not reached */
}
return (retval);
*/
struct memoryHashTable *
-ht_GetType(type, e_sizeP)
- int type;
- int *e_sizeP;
+ht_GetType(int type, int *e_sizeP)
{
struct memoryHashTable *mht;
}
static int
-ht_KeyMatch(type, key, e)
- int type;
- char *key;
- char *e;
+ht_KeyMatch(int type, char *key, char *e)
{
switch (type) {
case HT_dumpIden_FUNCTION:
default:
db_panic("illegal hash function");
}
+ /* not reached */
+ return 0;
}
/* ht_LookupEntry
*/
afs_int32
-ht_LookupEntry(ut, mht, key, eaP, e)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- char *key; /* pointer to lookup key to match */
- dbadr *eaP; /* db addr of entry found or zero */
- char *e; /* contents of located entry */
+ht_LookupEntry(struct ubik_trans *ut,
+ struct memoryHashTable *mht,
+ void *key, /* pointer to lookup key to match */
+ dbadr *eaP, /* db addr of entry found or zero */
+ void *e) /* contents of located entry */
{
- struct hashTable *ht;
+ struct hashTable *ht = NULL;
int type;
int e_size;
int old;
*eaP = a;
return 0;
}
- a = ntohl(*(dbadr *) (e + mht->threadOffset));
+ a = ntohl(*(dbadr *) ((char *)e + mht->threadOffset));
}
if (old)
return 0;
*/
static afs_int32
-ht_HashInList(ut, mht, opQuota, block, blockOffset)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- int *opQuota;
- struct memoryHTBlock *block;
- int blockOffset;
+ht_HashInList(struct ubik_trans *ut, struct memoryHashTable *mht,
+ int *opQuota, struct memoryHTBlock *block, int blockOffset)
{
struct hashTable *ht = mht->ht;
afs_int32 code;
int e_size = sizeFunctions[ntohl(ht->functionType)];
if (mht->length == 0) {
- if (code = ht_AllocTable(ut, mht)) {
+ if ((code = ht_AllocTable(ut, mht))) {
Log("ht_HashInList: ht_AllocTable failed\n");
return code;
}
for (ea = listA; ea; ea = next_ea) { /*f */
- LogDebug(3, "ht_HashInList: move entry at %d, type %d\n", ea,
+ LogDebug(3, "ht_HashInList: move entry at %u, type %d\n", ea,
ntohl(mht->ht->functionType));
if (dbread(ut, ea, e, e_size))
/* get the hash value */
hash = ht_HashEntry(mht, e) % mht->length;
- LogDebug(4, "ht_HashInList: moved to %d\n", hash);
+ LogDebug(4, "ht_HashInList: moved to %u\n", hash);
/* get the new hash table block */
code = ht_GetTableBlock(ut, mht, hash, 0 /*old */ , &block, &bo);
*/
static afs_int32
-ht_MoveEntries(ut, mht)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
+ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
{
struct memoryHTBlock *block;
afs_uint32 hash;
int count;
int bo;
afs_int32 code;
+ afs_int32 *pprog;
if (mht->oldLength == 0)
return 0;
if (mht->progress >= mht->oldLength)
return (ht_FreeTable(ut, mht));
- if (set_word_addr(ut, 0, &db.h, &mht->ht->progress, htonl(mht->progress))) {
+ pprog = &mht->ht->progress;
+ if (set_word_addr(ut, 0, &db.h, pprog, htonl(mht->progress))) {
Log("ht_MoveEntries: progress set failed\n");
return BUDB_IO;
}
#ifdef notdef
static afs_int32
-ht_MoveEntries(ut, mht)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
+ht_MoveEntries(struct ubik_trans *ut, struct memoryHashTable *mht)
{
afs_uint32 hash;
int bo;
#endif /* notdef */
afs_int32
-ht_HashIn(ut, mht, ea, e)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- dbadr ea; /* block db address */
- char *e; /* entry's address (in b) */
+ht_HashIn(struct ubik_trans *ut,
+ struct memoryHashTable *mht,
+ dbadr ea, /* block db address */
+ void *e) /* entry's address (in b) */
{
- struct hashTable *ht;
+ struct hashTable *ht = NULL;
afs_uint32 hash;
struct memoryHTBlock *block;
int bo;
afs_int32 code;
+ afs_int32 *pentries;
if (!(mht && (ht = mht->ht)))
db_panic("some ht called with bad mht");
- if (code = ht_MaybeAdjust(ut, mht))
+ if ((code = ht_MaybeAdjust(ut, mht)))
return code;
if (mht->length == 0)
- if (code = ht_AllocTable(ut, mht))
+ if ((code = ht_AllocTable(ut, mht)))
return code;
hash = ht_HashEntry(mht, e);
code = set_word_offset(ut, ea, e, mht->threadOffset, block->b.bucket[bo]);
if (code)
return BUDB_IO;
- LogDebug(5, "Hashin: set %d to %d\n", mht->threadOffset,
+ LogDebug(5, "Hashin: set %d to %u\n", mht->threadOffset,
block->b.bucket[bo]);
code =
htonl(ea));
if (code)
return BUDB_IO;
- LogDebug(5, "Hashin: set %d to %d\n", &block->b.bucket[bo], htonl(ea));
+ LogDebug(5, "Hashin: set %"AFS_PTR_FMT" to %d\n",
+ &block->b.bucket[bo], htonl(ea));
+ pentries = &ht->entries;
code =
- set_word_addr(ut, 0, &db.h, &ht->entries,
+ set_word_addr(ut, 0, &db.h, pentries,
htonl(ntohl(ht->entries) + 1));
if (code)
return BUDB_IO;
* but is not otherwise used. */
afs_int32
-RemoveFromList(ut, ea, e, head, ta, t, thread)
- struct ubik_trans *ut;
- dbadr ea; /* db addr of head structure */
- char *e; /* head structure */
- dbadr *head; /* address of head pointer */
- dbadr ta; /* db addr of strucure to be removed */
- char *t; /* structure being removed */
- dbadr *thread; /* pointer to thread pointer */
+RemoveFromList(struct ubik_trans *ut,
+ dbadr ea, /* db addr of head structure */
+ void *e, /* head structure */
+ dbadr *head, /* address of head pointer */
+ dbadr ta, /* db addr of strucure to be removed */
+ void *t, /* structure being removed */
+ dbadr *thread) /* pointer to thread pointer */
{
afs_int32 code;
- int threadOffset = ((char *)thread - t);
+ int threadOffset = ((char *)thread - (char *)t);
dbadr next_a; /* db addr of next element in list */
dbadr loop_a; /* db addr of current list element */
}
afs_int32
-ht_HashOutT(ut, mht, hash, ea, e, old)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- afs_uint32 hash;
- dbadr ea;
- char *e;
- int old;
+ht_HashOutT(struct ubik_trans *ut, struct memoryHashTable *mht,
+ afs_uint32 hash, dbadr ea, char *e, int old)
{
struct memoryHTBlock *block;
int bo;
afs_int32 code;
+ afs_int32 *pentries;
if ((old ? mht->oldLength : mht->length) == 0)
return -1;
}
done:
#endif
+ pentries = &mht->ht->entries;
if (set_word_addr
- (ut, 0, &db.h, &mht->ht->entries, htonl(ntohl(mht->ht->entries) - 1)))
+ (ut, 0, &db.h, pentries, htonl(ntohl(mht->ht->entries) - 1)))
return BUDB_IO;
return 0;
}
afs_int32
-ht_HashOut(ut, mht, ea, e)
- struct ubik_trans *ut;
- struct memoryHashTable *mht;
- dbadr ea;
- char *e;
+ht_HashOut(struct ubik_trans *ut, struct memoryHashTable *mht, dbadr ea,
+ void *e)
{
afs_uint32 hash;
afs_int32 code;
afs_int32
-scanHashTableBlock(ut, mhtPtr, htBlockPtr, old, length, index, selectFn,
- operationFn, rockPtr)
- struct ubik_trans *ut;
- struct memoryHashTable *mhtPtr;
- struct htBlock *htBlockPtr;
- int old;
- afs_int32 length; /* size of whole hash table */
- int index; /* base index of this block */
- int (*selectFn) ();
- int (*operationFn) ();
- char *rockPtr;
+scanHashTableBlock(struct ubik_trans *ut,
+ struct memoryHashTable *mhtPtr,
+ struct htBlock *htBlockPtr,
+ int old,
+ afs_int32 length, /* size of whole hash table */
+ int index, /* base index of this block */
+ int (*selectFn) (dbadr, void *, void *),
+ int (*operationFn) (dbadr, void *, void *),
+ void *rockPtr)
{
int type; /* hash table type */
int entrySize; /* hashed entry size */
- afs_uint32 *mapEntryPtr = 0; /* for status checks */
-
char entry[sizeof(struct block)];
- dbadr entryAddr, nextEntryAddr;
+ dbadr entryAddr;
int i;
- afs_int32 code = 0;
type = ntohl(mhtPtr->ht->functionType);
entrySize = sizeFunctions[type];
*/
for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) { /*f */
- entryAddr = 0;
- nextEntryAddr = ntohl(htBlockPtr->bucket[i]);
+ entryAddr = ntohl(htBlockPtr->bucket[i]);
/* if this is the old hash table, all entries below the progress mark
* should have been moved to the new hash table
*/
- if (old && (index < mhtPtr->progress) && nextEntryAddr)
+ if (old && (index < mhtPtr->progress) && entryAddr)
return BUDB_INTERNALERROR;
/* now walk down the chain of each bucket */
- while (nextEntryAddr) { /*w */
+ while (entryAddr) { /*w */
- entryAddr = nextEntryAddr;
if (dbread(ut, entryAddr, &entry[0], entrySize))
return (BUDB_INTERNALERROR);
(*operationFn) (entryAddr, &entry[0], rockPtr);
}
- nextEntryAddr =
+ entryAddr =
ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
} /*w */
}
afs_int32
-scanHashTable(ut, mhtPtr, selectFn, operationFn, rockPtr)
- struct ubik_trans *ut;
- struct memoryHashTable *mhtPtr;
- int (*selectFn) ();
- int (*operationFn) ();
- char *rockPtr;
+scanHashTable(struct ubik_trans *ut, struct memoryHashTable *mhtPtr,
+ int (*selectFn) (dbadr, void *, void *),
+ int (*operationFn) (dbadr, void *, void *),
+ void *rockPtr)
{
struct htBlock hashTableBlock;
dbadr tableAddr; /* disk addr of hash block */
int tableLength; /* # entries */
int blockLength; /* # blocks */
int hashIndex;
- int blockIndex, entryIndex;
int old;
int i;
afs_int32 code = 0;