/* 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= 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; }