fsHashTable is the structure of a HashTable block. It functions much like the
hash table found in FFS user directory blocks, except that it is stored in a seperate
block. This block contains a number of hash-chains (about 120 for a 512 byte block). Each
hash-chain is a chain of Nodes. Each Node has a pointer to an Object and a pointer to the
next entry in the hash-chain. Using such a hash-chain you can locate an object
quickly by only knowing its name.
| Field |
Type |
Description |
| bheader |
struct fsBlockHeader |
Standard block header. |
| parent |
NODE |
The node number of the directory Object this HashTable block belongs to. |
| hashentry |
NODE |
An array of Nodes. Each Node represents the start of a hash-chain
(singly linked). A hash-value is calculated using the name of a file or directory,
and this value determines in which chain the Object is linked. If there are no
entries in a hash-chain then the hashentry value is zero. |
struct fsHashTable {
struct fsBlockHeader bheader;
NODE parent;
NODE hashentry[0];
};
To calculate the hash-value using a name of an Object as input use these routines:
UWORD calchash(UBYTE *name) {
UWORD hash=0;
/* Calculates a hash value over the passed in string.
The end of the string can be either a NUL byte or a
slash. The hash function is the same as the one
used in FastFileSystem set to international mode. */
while(name[hash]!=0 && name[hash]!='/') {
hash++;
}
while(*name!=0 && *name!='/') {
hash=hash*13+upperchar(*name++);
}
return((UWORD)(hash % (UWORD)((blocksize-sizeof(struct fsHashTable))>>2)));
}
UBYTE upperchar(UBYTE c) {
if((c>=224 && c<=254 && c!=247) || (c>='a' && c<='z')) {
c-=32;
}
return(c);
}
| 