ptg10805159764 ADatabase Library Chapter 20
262 while (offset != 0) {
263 nextoffset=_db_readidx(db, offset);
264 if (strcmp(db->idxbuf, key) == 0)
265 break; /* found a match */
266 db->ptroff=offset; /* offset of this (unequal) record */
267 offset=nextoffset; /* next one to compare */
268 }
269 /*
270 * offset == 0 on error (record not found).
271 */
272 return(offset == 0? -1 : 0);
273 }
274 /*
275 * Calculate the hash value for a key.
276 */
277 static DBHASH
278 _db_hash(DB *db, const char *key)
279 {
280 DBHASH hval = 0;
281 char c;
282 int i;
283 for (i = 1; (c = *key++) != 0; i++)
284 hval += c * i; /* ascii char times its 1-based index */
285 return(hval%db->nhash);
286 }[262 – 268] In thewhileloop, we go through each index recordonthe hash chain,
comparing keys. We call_db_readidx to read each index record. It
populates the idxbuf field with the key of the current record. If
_db_readidxreturns zero, we’ve reached the last entry in the chain.
[269 – 273] Ifoffsetis zeroafter the loop, we’ve reached the end of a hash chain
without finding a matching key, so we return−1. Otherwise, we found a
match (and exited the loop with thebreakstatement), so we return success
( 0 ).Inthis case, theptrofffield contains the address of the previous index
record, datoff contains the address of the data record, and datlen
contains the size of the data record. As we make our way through the hash
chain, we save the previous index recordthat points to the current index
record. We’ll use this when we delete a record, since we have to modify the
chain pointer of the previous record to delete the current record.
[274 – 286] _db_hashcalculates the hash value for a given key.Itmultiplies each
ASCII character times its 1-based index and divides the result by the number
of hash table entries. The remainder from the division is the hash value for
this key.Recall that the number of hash table entries is 137, which is a prime
number.According to Knuth[ 1998 ],prime hashes generally provide good
distribution characteristics.