WAP For Hashing ..Hash Table Implementataion

/* hash table */

#include
#include

/* implementation dependent declarations */
typedef int keyType; /* type of key */

/* user data stored in hash table */
typedef struct {
int stuff; /* optional related data */
} recType;

typedef int hashIndexType; /* index into hash table */

#define compEQ(a,b) (a == b)


/* implementation independent declarations */
typedef enum {
STATUS_OK,
STATUS_MEM_EXHAUSTED,
STATUS_KEY_NOT_FOUND
} statusEnum;

typedef struct nodeTag {
struct nodeTag *next; /* next node */
keyType key; /* key */
recType rec; /* user data */
} nodeType;

nodeType **hashTable;
int hashTableSize;

hashIndexType hash(keyType key) {

/***********************************
* hash function applied to data *
***********************************/

return (key % hashTableSize);
}

statusEnum insert(keyType key, recType *rec) {
nodeType *p, *p0;
hashIndexType bucket;

/************************************************
* allocate node for data and insert in table *
************************************************/

/* insert node at beginning of list */
bucket = hash(key);
if ((p = malloc(sizeof(nodeType))) == 0)
return STATUS_MEM_EXHAUSTED;
p0 = hashTable[bucket];
hashTable[bucket] = p;
p->next = p0;
p->key = key;
p->rec = *rec;
return STATUS_OK;
}

statusEnum delete(keyType key) {
nodeType *p0, *p;
hashIndexType bucket;

/********************************************
* delete node containing data from table *
********************************************/

/* find node */
p0 = 0;
bucket = hash(key);
p = hashTable[bucket];
while (p && !compEQ(p->key, key)) {
p0 = p;
p = p->next;
}
if (!p) return STATUS_KEY_NOT_FOUND;

/* p designates node to delete, remove it from list */
if (p0)
/* not first node, p0 points to previous node */
p0->next = p->next;
else
/* first node on chain */
hashTable[bucket] = p->next;

free (p);
return STATUS_OK;
}

statusEnum find(keyType key, recType *rec) {
nodeType *p;

/*******************************
* find node containing data *
*******************************/

p = hashTable[hash(key)];
while (p && !compEQ(p->key, key))
p = p->next;
if (!p) return STATUS_KEY_NOT_FOUND;
*rec = p->rec;
return STATUS_OK;
}

int main(int argc, char **argv) {
int i, maxnum, random;
recType *rec;
keyType *key;
statusEnum err;

/* command-line:
*
* has maxnum hashTableSize [random]
*
* has 2000 100
* processes 2000 records, tablesize=100, sequential numbers
* has 4000 200 r
* processes 4000 records, tablesize=200, random numbers
*
*/
maxnum = atoi(argv[1]);
hashTableSize = atoi(argv[2]);
random = argc > 3;

if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
fprintf (stderr, "out of memory (rec)\n");
exit(1);
}
if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
fprintf (stderr, "out of memory (key)\n");
exit(1);
}

if ((hashTable = calloc(hashTableSize, sizeof(nodeType *))) == 0) {
fprintf (stderr, "out of memory (hashTable)\n");
exit(1);
}

if (random) { /* random */
/* fill "key" with unique random numbers */
for (i = 0; i < maxnum; i++) key[i] = rand();
printf ("ran ht, %d items, %d hashTable\n", maxnum, hashTableSize);
} else {
for (i=0; i printf ("seq ht, %d items, %d hashTable\n", maxnum, hashTableSize);
}


for (i = 0; i < maxnum; i++) {
err = insert(key[i], &rec[i]);
if (err) printf("pt1, i=%d\n", i);
}

for (i = maxnum-1; i >= 0; i--) {
err = find(key[i], &rec[i]);
if (err) printf("pt2, i=%d\n", i);
}

for (i = maxnum-1; i >= 0; i--) {
err = delete(key[i]);
if (err) printf("pt3, i=%d\n", i);
}
return 0;
}