home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / HASH.ZIP / HASH.C next >
Encoding:
C/C++ Source or Header  |  1988-10-07  |  10.1 KB  |  372 lines
  1. /********************************************************************
  2.    HASH.C - general hash table functions - (c) 1988 Howard Lowndes
  3.             This program is from The C Gazette, March 1988, Volume
  4.             2, No.4, page 14
  5. Function:   Provides a set of generic hash table functions. Two types
  6.             of hash tables are provided. These may be selected by the
  7.             COMPILE TIME switches as follows:
  8.  
  9.  HASH.EXE - Compiled with MSC switch and CHAINED switch with Quick C:
  10.             C>qcl /c /DMSC /DCHAINED hash.c
  11.  
  12.          FIXED  - The table contains a fixed # of slots. Hash collision is
  13.                   resolved by looking for the next available slot. (default,
  14.                   no command line switch needed.)
  15.  
  16.          CHAINED- The table consists of pointers to linked lists that con-
  17.                   tain the data elements. Collisions are resolved by simply
  18.                   adding the "colliding" entry to the linked list for that
  19.                   hash value. The linked list is kept in most-recently-used
  20.                   order. This switch disables FIXED.
  21.  
  22.          other switches:
  23.  
  24.                   DEBUG -causes a test driver to be included (default,
  25.                         no need for command line switch)
  26.  
  27.                   MSC -  compile for Microsoft C, Quick C, or Power C.
  28.                         (default is DeSmet - no command line switch needed)
  29.                                            
  30.  
  31.          functions usage:
  32.  
  33.          unsigned size;
  34.          TABLE *tab;
  35.          ENTRY *ent;
  36.          TABLE *htabcreate(size)-creates a hash table with size entries
  37.          ENTRY *do_entry(ent, func, tab)-performs func on the given table.
  38.                   func may be FIND, ADD, or DELETE (defined below)
  39.          void memory_error()-called when we run out of memory--replace if 
  40.          desired.
  41.  
  42.    Source code may be freely used if copyright is stated.
  43.    Object code may be freely used.
  44. *********************************************************************/
  45. #define DEBUG
  46. #define FIXED     /* see below remark to define CHAINED */
  47.  
  48. /* standard header files */
  49. #include <stdio.h>
  50.  
  51. #if defined(MSC)  /* will compile for MSC, QUICK C, or POWER C  */
  52. #include <stdlib.h>
  53. #include <string.h>
  54. #include <malloc.h>
  55.  
  56. #else       /* DeDmet */
  57. void *malloc(), *calloc(), free();
  58. #endif
  59.  
  60.       /* define the tables and table elements */
  61.       /* must be one or the other */
  62. #ifdef CHAINED
  63.    #undef FIXED
  64. #endif
  65.  
  66. #ifndef FIXED     /* to define CHAINED, define CHAINED on command line */
  67.    #define CHAINED      /*    with /DCHAINED  (for MSC & QUICKC)       */
  68.                         /* or with /dCHAINED  (for POWER C)            */
  69. #endif
  70.  
  71. #ifdef CHAINED 
  72. typedef struct entry {  /* we manage the data as a linked list of these */
  73.    char *data;
  74.    struct entry *next;
  75. } ENTRY;
  76. #endif
  77.  
  78. #ifdef FIXED
  79. typedef struct entry {  /* we manage the data as an array of these */
  80.    char *data;
  81. } ENTRY;
  82. #endif
  83.  
  84. typedef struct table {  /* the table itself */
  85.    ENTRY **tbase;
  86.    unsigned tsize;
  87. } TABLE;
  88.  
  89. /* the functions that manipulate a table */
  90. TABLE *htabcreate();    /* make a table */
  91. ENTRY *do_entry();      /* find, add, or delete an entry */
  92.  
  93. /* codes for do_entry() */
  94. #define FIND 1       /* just check to see if it's there */
  95. #define ADD 2        /* add if not already in table */
  96. #define DELETE 3     /* delete if found */
  97.  
  98. /* memory error management */
  99. #define NO_MEM() memory_error()
  100. void memory_error();
  101.  
  102. #ifdef DEBUG
  103.  
  104. int search_count;    /* # of times to try before finding an entry */
  105.  
  106. void main()    /* a sample driver for the hash table */
  107. {              /* user to enter list of item to display.    */
  108.    char inline[80], *s;
  109.    ENTRY trial;
  110.    int func;
  111.    TABLE *trial_table;
  112.    void show_all();
  113.  
  114.    puts ("How big do you want the table to be? ");
  115.    gets (inline);
  116.  
  117.    trial_table = htabcreate( (unsigned) atoi(inline));
  118.  
  119.    for (;;) {
  120.       printf ("(? - Lists all data,  *item - Deletes item,  RETURN - quits)");
  121.       printf ("\nSupply an item:  ");
  122.       gets(inline);
  123.       if (strlen (inline) == 0)
  124.          break;
  125.  
  126.       func = ADD;
  127.       s = inline;
  128.       if (*s == '?') {     /* print out a list of stored data */
  129.          show_all(trial_table);
  130.          continue;
  131.       }
  132.       else if (*s == '*') {      /* delete flag */
  133.          s++;
  134.          func = DELETE;
  135.       }
  136.  
  137.       search_count = 0;
  138.       trial.data = s;
  139.       if (func == ADD) {
  140.          if (do_entry (&trial, FIND, trial_table) == NULL) {
  141.             printf("\nIt took %d tests to learn %s was not in the table",
  142.                search_count, inline);
  143.             printf(" - will add.\n");
  144.             if (do_entry (&trial, ADD, trial_table) == NULL)
  145.                printf("Couldn't add %s - table full\n", inline);
  146.          }
  147.          else
  148.             printf("\n%s found - it took %d tests to find it.\n",
  149.                inline, search_count);
  150.       }
  151.       else {      /* delete */
  152.          if (do_entry (&trial, FIND, trial_table) != NULL) {
  153.             do_entry (&trial, DELETE, trial_table);
  154.             printf("%s deleted.\n", trial.data);
  155.          }
  156.          else
  157.             printf("\n%s not in table.", trial.data);
  158.       }     /* else */
  159.    }     /* for */
  160. }     /* main() */
  161.  
  162. void show_all(tab)         /* print out data in hash table */
  163. TABLE *tab;
  164. {
  165.  
  166.    unsigned u;
  167.    ENTRY *temp;
  168.  
  169.    for (u = 0; u < tab->tsize; u++) {
  170.       printf("%u: ", u);
  171.       #ifdef CHAINED
  172.          for (temp = tab->tbase[u]; temp != NULL; temp = temp->next)
  173.             printf("[%s] ", temp->data);
  174.       #endif
  175.       #ifdef FIXED
  176.          if (tab->tbase[u] != NULL)
  177.             printf("[%s]", tab->tbase[u]->data);
  178.       #endif
  179.          printf("\n");
  180.    }  /* for */
  181. }
  182. #endif
  183.  
  184. static unsigned hash_entry(ent, tab)
  185. ENTRY *ent;
  186. TABLE *tab;
  187. {
  188.  
  189.    unsigned sum;
  190.    char *s;
  191.  
  192.    /* just sum the ASCII value of the data entry */
  193.    sum = 0;
  194.    for (s = ent->data; *s != '\0'; s++)
  195.       sum += *s;
  196.    sum = sum % tab->tsize;       /* make sure it fits */
  197.    return (sum);
  198. }
  199.  
  200. /* make a comparison between two entries */
  201. static int compare_entry (e1, e2)
  202. ENTRY *e1, *e2;
  203. {
  204.       /* very simple version for this model */
  205.    return (strcmp(e1->data, e2->data));
  206. }
  207.  
  208. /* return a pointer to a permanent copy of the entry */
  209. static ENTRY *make_element (ent)
  210. ENTRY *ent;
  211. {
  212.  
  213.    ENTRY *temp;
  214.    char *s;
  215.  
  216.    if ( (temp = (ENTRY *) malloc(sizeof(ENTRY))) == NULL)  NO_MEM();
  217.    if ( (s = malloc (strlen (ent->data) + 1)) == NULL)  NO_MEM();
  218.    strcpy(s, ent->data);
  219.    temp->data = s;
  220.  
  221.    #ifdef CHAINED 
  222.       temp->next = NULL;
  223.    #endif
  224.  
  225.    return (temp);
  226. }
  227.  
  228. TABLE *htabcreate (size)      /* make a table */
  229. unsigned size;
  230. {
  231.  
  232.    TABLE *temp;
  233.    unsigned u;
  234.    ENTRY **ptr;
  235.  
  236.    if (size == 0) {
  237.       printf("\nInvalid table size\n");
  238.       exit (1);
  239.    }
  240.  
  241.    if ( (temp = (TABLE *) malloc(sizeof(TABLE))) == NULL)
  242.       NO_MEM();
  243.    temp->tsize = size;
  244.    if ( (temp->tbase = (ENTRY **) calloc(size, sizeof(ENTRY *))) == NULL)
  245.       NO_MEM();
  246.  
  247.    /* clear the table */
  248.    ptr = temp->tbase;
  249.    for (u = 0; u!= size; u++)
  250.       *ptr++ = NULL;
  251.    return (temp);
  252. }
  253.  
  254. void memory_error()
  255. {
  256.  
  257.    printf("\nOut of memory\n");
  258.    exit(1);
  259. }
  260.  
  261. #ifdef CHAINED
  262. ENTRY *do_entry(ent, func, tab)
  263. ENTRY *ent;
  264. int func;      /* ADD, FIND, or DELETE */
  265. TABLE *tab;
  266. {
  267.  
  268.    unsigned hash;
  269.    ENTRY *trial, *last;
  270.  
  271.    /* see if we can find ent in the table */
  272.    hash = hash_entry(ent, tab);
  273.    for (last = NULL, trial = tab->tbase[hash];
  274.          trial != NULL;
  275.          last = trial, trial = trial->next) {
  276.       #ifdef DEBUG
  277.          search_count++;
  278.       #endif
  279.          if (compare_entry(ent, trial) == 0)
  280.             break;
  281.    }  /* for */
  282.  
  283.    /* DELETE if desired */
  284.    if (func == DELETE) {
  285.       if (trial != NULL) {
  286.          if (last == NULL)    /* first entry in list */
  287.             tab->tbase[hash] = trial->next;
  288.          else
  289.             last->next = trial->next;
  290.          free (trial->data);
  291.          free (trial);
  292.          trial = NULL;
  293.       }
  294.    }
  295.          /* if func is FIND, just reorder list & return a pointer */
  296.    else if (func == FIND) {
  297.       if (trial != NULL)   /* move found entry to top of list */
  298.          if (last != NULL) {  /* not already at top of list */
  299.             last->next = trial->next;  /* take self out of list */
  300.             trial->next = tab->tbase[hash];     /* pick up whole list...*/
  301.             tab->tbase[hash] = trial;  /*   ... and put self at start */
  302.          }
  303.    }
  304.  
  305.          /* ADD if not already present */
  306.    else if (trial == NULL) {
  307.       trial = make_element(ent); /* get a permanent copy of ent */
  308.       trial->next = tab->tbase[hash];  /* put self at head of list */
  309.       tab->tbase[hash] = trial;
  310.    }
  311.    return (trial);
  312. }
  313. #endif
  314.  
  315. #ifdef FIXED
  316. ENTRY *do_entry(ent, func, tab)
  317. ENTRY *ent;
  318. int func;      /* ADD, FIND, or DELETE */
  319. TABLE *tab;
  320. {
  321.  
  322.    unsigned hash, start;
  323.    ENTRY *trial;
  324.  
  325.    /* see if we can find ent in the table */
  326.    start = hash = hash_entry(ent, tab);
  327.    trial = NULL;
  328.    while (tab->tbase[hash] != NULL) {
  329.       #ifdef DEBUG
  330.          search_count++;
  331.       #endif
  332.       if (compare_entry(ent, tab->tbase[hash]) == 0) {
  333.          trial = tab->tbase[hash];
  334.          break;
  335.       }
  336.       hash++;
  337.       if (hash == start)
  338.          break;         /* have come full circle */
  339.       if (hash >= tab->tsize) {
  340.          hash = 0;      /* loop around */
  341.          if (hash == start)
  342.             break;
  343.       }
  344.    }     /* while */
  345.  
  346.          /* DELETE if desired */
  347.    if (func == DELETE) {
  348.       if (trial != NULL) {
  349.          tab->tbase[hash] = NULL;   /* delete from array */
  350.          free (trial->data);
  351.          free (trial);
  352.          trial = NULL;
  353.       }
  354.    }
  355.  
  356.          /* if func is FIND, just return a pointer */
  357.    else if (func == FIND)
  358.       ;
  359.  
  360.          /* ADD if not already present */
  361.    else if (trial == NULL) {
  362.       trial = make_element(ent);
  363.       if (tab->tbase[hash] != NULL)    /* out of slots ! */
  364.          trial = NULL;
  365.       else
  366.          tab->tbase[hash] = trial;
  367.    }
  368.    return (trial);
  369. }
  370. #endif
  371.  
  372.