6 /* implementation dependent declarations */
7 typedef int keyType; /* type of key */
9 /* user data stored in hash table */
11 int stuff; /* optional related data */
14 typedef int hashIndexType; /* index into hash table */
16 #define compEQ(a,b) (a == b)
19 /* implementation independent declarations */
26 typedef struct nodeTag {
27 struct nodeTag *next; /* next node */
28 keyType key; /* key */
29 recType rec; /* user data */
35 hashIndexType hash(keyType key) {
37 /***********************************
38 * hash function applied to data *
39 ***********************************/
41 return (key % hashTableSize);
44 statusEnum insert(keyType key, recType *rec) {
48 /************************************************
49 * allocate node for data and insert in table *
50 ************************************************/
52 /* insert node at beginning of list */
54 if ((p = malloc(sizeof(nodeType))) == 0)
55 return STATUS_MEM_EXHAUSTED;
56 p0 = hashTable[bucket];
57 hashTable[bucket] = p;
64 statusEnum delete(keyType key) {
68 /********************************************
69 * delete node containing data from table *
70 ********************************************/
75 p = hashTable[bucket];
76 while (p && !compEQ(p->key, key)) {
80 if (!p) return STATUS_KEY_NOT_FOUND;
82 /* p designates node to delete, remove it from list */
84 /* not first node, p0 points to previous node */
87 /* first node on chain */
88 hashTable[bucket] = p->next;
94 statusEnum find(keyType key, recType *rec) {
97 /*******************************
98 * find node containing data *
99 *******************************/
101 p = hashTable[hash(key)];
102 while (p && !compEQ(p->key, key))
104 if (!p) return STATUS_KEY_NOT_FOUND;
109 int main(int argc, char **argv) {
110 int i, maxnum, random;
117 * has maxnum hashTableSize [random]
120 * processes 2000 records, tablesize=100, sequential numbers
122 * processes 4000 records, tablesize=200, random numbers
125 maxnum = atoi(argv[1]);
126 hashTableSize = atoi(argv[2]);
129 if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
130 fprintf (stderr, "out of memory (rec)\n");
133 if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
134 fprintf (stderr, "out of memory (key)\n");
138 if ((hashTable = calloc(hashTableSize, sizeof(nodeType *))) == 0) {
139 fprintf (stderr, "out of memory (hashTable)\n");
143 if (random) { /* random */
144 /* fill "key" with unique random numbers */
145 for (i = 0; i < maxnum; i++) key[i] = rand();
146 printf ("ran ht, %d items, %d hashTable\n", maxnum, hashTableSize);
148 for (i=0; i<maxnum; i++) key[i] = i;
149 printf ("seq ht, %d items, %d hashTable\n", maxnum, hashTableSize);
153 for (i = 0; i < maxnum; i++) {
154 err = insert(key[i], &rec[i]);
155 if (err) printf("pt1, i=%d\n", i);
158 for (i = maxnum-1; i >= 0; i--) {
159 err = find(key[i], &rec[i]);
160 if (err) printf("pt2, i=%d\n", i);
163 for (i = maxnum-1; i >= 0; i--) {
164 err = delete(key[i]);
165 if (err) printf("pt3, i=%d\n", i);