---

hashTable.c File Reference

#include "lclintMacros.nf"
#include "basic.h"
#include "256_random_numbers.nf"

Go to the source code of this file.

Defines
#define	hbucket_undefined   0
Functions
void	hashTable_free ( hashTable h)
hashTable	hashTable_create (int size)
cstring	hashTable_stats (hashTable h)
void	hashTable_insert (hashTable h, cstring key, int value)
int	hashTable_lookup (hashTable h, cstring key)
void	hashTable_replaceKey (hashTable h, cstring oldkey, cstring newkey)
void	hashTable_remove (hashTable h, cstring key)

---

Define Documentation

#define hbucket_undefined   0

Definition at line 40 of file hashTable.c.

---

Function Documentation

hashTable hashTable_create ( int size )

Definition at line 266 of file hashTable.c. Referenced by fileTable_create(). { int i; hashTable h = (hashTable) dmalloc (sizeof (*h)); h->size = size; h->nentries = 0; h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * size); /*@+loopexec@*/ for (i = 0; i < size; i++) { h->buckets[i] = hbucket_undefined; } /*@-loopexec@*/ return h; }

void hashTable_free ( hashTable h )

Definition at line 183 of file hashTable.c. Referenced by fileTable_free(). { int i; for (i = 0; i < h->size; i++) { hbucket_free (h->buckets[i]); } sfree (h->buckets); sfree (h); }

void hashTable_insert ( hashTable h, cstring key, int value )

Definition at line 338 of file hashTable.c. { unsigned int hindex; hbucket hb; hentry e; h->nentries++; /* ** rehashing based (loosely) on code by Steve Harrison */ if (h->nentries * 162 > h->size * 100) { int i; int oldsize = h->size; int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */ hbucket *oldbuckets = h->buckets; h->size = newsize; h->nentries = 0; h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize); /*@+loopexec@*/ for (i = 0; i < newsize; i++) { h->buckets[i] = hbucket_undefined; } /*@=loopexec@*/ for (i = 0; i < oldsize; i++) { hbucket bucket = oldbuckets[i]; if (!hbucket_isNull (bucket)) { int j; for (j = 0; j < bucket->size; j++) { hashTable_addEntry (h, bucket->entries[j]); } sfree (bucket); } } sfree (oldbuckets); } e = hentry_create (key, value); hindex = hashTable_hashValue (h, key); hb = h->buckets[hindex]; if (hbucket_isNull (hb)) { h->buckets[hindex] = hbucket_single (e); } else { hbucket_add (hb, e); } }

int hashTable_lookup ( hashTable h, cstring key )

Definition at line 407 of file hashTable.c. { hbucket hb = hashTable_hash (h, key); return (hbucket_lookup (hb, key)); }

void hashTable_remove ( hashTable h, cstring key )

Definition at line 443 of file hashTable.c. { hbucket hb = hashTable_hash (h, key); if (!hbucket_isNull (hb)) { int i; for (i = 0; i < hb->size; i++) { if (cstring_equal (hb->entries[i].key, key)) { if (i < hb->size - 1) { hb->entries[i] = hb->entries[hb->size - 1]; } hb->size--; return; } } } llbug (message ("hashTable_removeKey: %s not found", key)); }

void hashTable_replaceKey ( hashTable h, cstring oldkey, cstring newkey )

Definition at line 419 of file hashTable.c. { hbucket hb = hashTable_hash (h, oldkey); llassert (cstring_equal (oldkey, newkey)); if (!hbucket_isNull (hb)) { int i; for (i = 0; i < hb->size; i++) { if (cstring_equal (hb->entries[i].key, oldkey)) { hb->entries[i].key = newkey; return; } } } llbug (message ("hashTable_replaceKey: %s not found", oldkey)); }

cstring hashTable_stats ( hashTable h )

Definition at line 308 of file hashTable.c. { return (message ("size: %d, collisions: %d, empty: %d\n", h->size, hashTable_countCollisions (h), hashTable_countEmpty (h))); }

---