Category : Files from Magazines
Archive   : CGAZ2-4.ZIP
Filename : HASH.C

 
Output of file : HASH.C contained in archive : CGAZ2-4.ZIP
/**************************** HASH.C **********************************
*
* Generalized hash table functions - (c) 1988 Howard Lowndes
*
* Function: Provides a set of generic hash table functions. Two types
* of hash tables are provided. These may be selected by the compile
* time switches as follows:
*
* FIXED - The table contains a fixed # of slots. Hash collision is
* resolved by looking for the next available slot.
*
* CHAINED - The table consists of pointers to linked lists that contain
* the data elements. Collisions are resolved by simply adding
* the "colliding" entry to the linked list for that hash value.
* The linked list is kept in most-recently-used order.
*
*** other switches:
* DEBUG - causes a test driver to be included
* MSC - compile for Microsoft C (default is DeSmet)
*
*** Functions usage:
* unsigned size;
* TABLE *tab;
* ENTRY *ent;
*
* TABLE *htabcreate(size) - creates a hash table with size entries
* ENTRY *do_entry(ent, func, tab) - performs func on the given table.
* func may be FIND, ADD, or DELETE (defined below)
* void memory_error() - called when we run out of memory--replace if desired.
*
* Source code may be freely used if copyright is stated.
* Object code may be freely used.
*************************************************************************/

#define DEBUG
#define FIXED

/* standard header files */
#include

#ifdef MSC
#include
#include
#include

#else /* DeSmet */
void *malloc(), *calloc(), free();
#endif

/* define the tables and table elements */
#ifdef CHAINED /* must be one or the other */
#undef FIXED
#endif
#ifndef FIXED
#define CHAINED
#endif

#ifdef CHAINED
typedef struct entry { /* We manage the data as a linked list of these */
char *data;
struct entry *next;
} ENTRY;
#endif

#ifdef FIXED
typedef struct entry { /* We manage the data as an array of these */
char *data;
} ENTRY;
#endif

typedef struct table { /* the table itself */
ENTRY **tbase;
unsigned tsize;
} TABLE;

/* the functions that manipulate a table */
TABLE *htabcreate(); /* make a table */
ENTRY *do_entry(); /* find, add, or delete an entry */

/* codes for do_entry() */
#define FIND 1 /* just check to see if its there */
#define ADD 2 /* add if not already in table */
#define DELETE 3 /* delete if found */

/* memory error management */
#define NO_MEM() memory_error()
void memory_error();

#ifdef DEBUG

int search_count; /* # of times to try before finding an entry */
void main()
{
char inline[80], *s;
ENTRY trial;
int func;
TABLE *trial_table;
void show_all();

puts("How big do you want the table to be ? ");
gets(inline);

trial_table = htabcreate( (unsigned) atoi(inline));

for (;;) {
printf
("Supply a data item (? lists all data, *item deletes item): ");
gets(inline);
if (strlen(inline) == 0)
break;

func = ADD;
s = inline;
if (*s == '?') { /* print out a list of stored data */
show_all(trial_table);
continue;
}
else if (*s == '*') { /* delete flag */
s++;
func = DELETE;
}

search_count = 0;
trial.data = s;
if (func == ADD) {
if (do_entry(&trial, FIND, trial_table) == NULL) {
printf
("It took %d tests to learn that %s was not in the table - will add\n",
search_count, inline);
if (do_entry(&trial, ADD, trial_table) == NULL)
printf("Couldn't add %s - table full\n", inline);
}
else {
printf
("%s already in table - it tooks %d tests to find it\n",
inline, search_count);
}
}
else { /* delete */
if (do_entry(&trial, FIND, trial_table) != NULL) {
do_entry(&trial, DELETE, trial_table);
printf("%s deleted\n", trial.data);
}
else
printf("%s not in the table\n", trial.data);
}
}
}

void show_all(tab) /* print out data in hash table */
TABLE *tab;
{
unsigned u;
ENTRY *temp;

for (u = 0; u < tab->tsize; u++) {
printf("%u: ", u);
#ifdef CHAINED
for (temp=tab->tbase[u]; temp != NULL; temp = temp->next)
printf("[%s] ", temp->data);
#endif
#ifdef FIXED
if (tab->tbase[u] != NULL)
printf("[%s]", tab->tbase[u]->data);
#endif
printf("\n");
}
}
#endif

static unsigned hash_entry(ent, tab)
ENTRY *ent;
TABLE *tab;
{
unsigned sum;
char *s;

/* just sum the ASCII value of the data entry */
sum = 0;
for (s = ent->data; *s != '\0'; s++)
sum += *s;

sum = sum % tab->tsize; /* make sure it fits */

return (sum);
}

/* make a comparison between two entries */
static int compare_entry(e1, e2)
ENTRY *e1, *e2;
{
/* very simple version for this model */
return (strcmp(e1->data, e2->data));
}

/* return a pointer to a permanent copy of the entry */
static ENTRY *make_element(ent)
ENTRY *ent;
{
ENTRY *temp;
char *s;

if ((temp = (ENTRY *) malloc(sizeof(ENTRY))) == NULL) NO_MEM();
if ((s = malloc(strlen(ent->data) + 1)) == NULL) NO_MEM();
strcpy(s, ent->data);
temp->data = s;

#ifdef CHAINED
temp->next = NULL;
#endif

return (temp);
}

TABLE *htabcreate(size) /*make a table */
unsigned size;
{
TABLE *temp;
unsigned u;
ENTRY **ptr;

if (size == 0) { printf("\nInvalid table size\n"); exit(1); }

if ((temp = (TABLE *) malloc(sizeof(TABLE))) == NULL) NO_MEM();
temp -> tsize = size;
if ((temp->tbase = (ENTRY **) calloc(size, sizeof(ENTRY *))) == NULL)
NO_MEM();

/* clear the table */
ptr = temp->tbase;
for (u = 0; u != size; u++)
*ptr++ = NULL;

return (temp);
}

void memory_error()
{
printf("\nOut of memory\n");
exit(1);
}

#ifdef CHAINED
ENTRY *do_entry(ent, func, tab)
ENTRY *ent;
int func; /* ADD, FIND, or DELETE */
TABLE *tab;
{
unsigned hash;
ENTRY *trial, *last;

/* see if we can find ent in the table */
hash = hash_entry(ent, tab);
for (last = NULL, trial = tab->tbase[hash];
trial != NULL;
last = trial, trial = trial->next) {
#ifdef DEBUG
search_count++;
#endif
if (compare_entry(ent, trial) == 0)
break;
}

/* DELETE if desired */
if (func == DELETE) {
if (trial != NULL) {
if (last == NULL) /* is first entry in list */
tab->tbase[hash] = trial->next;
else
last->next = trial->next;
free(trial->data);
free(trial);
trial = NULL;
}
}

/* if func is FIND, just reorder list and return a pointer */
else if (func == FIND) {
if (trial != NULL) /* move found entry to top of list */
if (last != NULL) { /* not already at top of list */
last -> next = trial -> next; /* take self out of list */
trial -> next = tab->tbase[hash]; /* pick up whole list...*/
tab->tbase[hash] = trial; /* ... and put self at start */
}
}

/* ADD if not already present */
else if (trial == NULL) {
trial = make_element(ent); /* get a permanent copy of ent */
trial->next = tab->tbase[hash]; /* put self at head of list */
tab->tbase[hash] = trial;
}

return (trial);
}
#endif

#ifdef FIXED
ENTRY *do_entry(ent, func, tab)
ENTRY *ent;
int func; /* ADD, FIND, or DELETE */
TABLE *tab;
{
unsigned hash, start;
ENTRY *trial;

/* see if we can find ent in the table */
start = hash = hash_entry(ent, tab);
trial = NULL;
while (tab->tbase[hash] != NULL) {
#ifdef DEBUG
search_count++;
#endif
if (compare_entry(ent, tab->tbase[hash]) == 0) {
trial = tab->tbase[hash];
break;
}
hash++;
if (hash == start)
break; /* have come full circle */
if (hash >= tab ->tsize) {
hash = 0; /* loop around */
if (hash == start)
break;
}
}

/* DELETE if desired */
if (func == DELETE) {
if (trial != NULL) {
tab->tbase[hash] = NULL; /* delete from array */
free(trial->data);
free(trial);
trial = NULL;
}
}

/* if func is FIND, just return a pointer */
else if (func == FIND)
;

/* ADD if not already present */
else if (trial == NULL) {
trial = make_element(ent);
if (tab->tbase[hash] != NULL) /* out of slots! */
trial = NULL;
else
tab->tbase[hash] = trial;
}
return (trial);
}
#endif


  3 Responses to “Category : Files from Magazines
Archive   : CGAZ2-4.ZIP
Filename : HASH.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/