home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1991 / 04 / morrow / table.c < prev    next >
C/C++ Source or Header  |  1989-09-03  |  2KB  |  104 lines
  1. /***
  2. *       GASystem
  3. *       Mike Morrow
  4. *       September 1989
  5. ***/
  6.  
  7.  
  8.  
  9.  
  10. /**
  11. *                       Hash table routines.
  12. **/
  13.  
  14. #include "table.h"
  15.  
  16. #define HASH_TAB_LEN 31
  17.  
  18.  
  19.  
  20. typedef TBLENT *HASHTABLE[HASH_TAB_LEN];
  21.  
  22.  
  23. /***
  24. *    Declare the table.
  25. **/
  26. static HASHTABLE the_table;
  27.  
  28.  
  29. static unsigned int hash();
  30.  
  31. extern void *calloc();
  32.  
  33.  
  34. /* initialize the hash table by having all pointers set to NULL */
  35. void tbl_init()
  36. {
  37.         unsigned int i;
  38.         TBL_PTR *p;
  39.  
  40.         for (i=0, p = the_table; i<HASH_TAB_LEN; i++, p++)
  41.             *p = (TBL_PTR)0;
  42. }
  43.  
  44.  
  45. /**
  46. *    Insert a copy of the record rec_dat into the table.
  47. **/
  48.  
  49. TBL_PTR tbl_ins(rec_dat)
  50. TBL_PTR rec_dat;
  51. {
  52.         register TBL_PTR new_rec;
  53.         register unsigned int index;
  54.  
  55.         new_rec = (TBL_PTR)calloc(1, sizeof(TBLENT));
  56.         if(! new_rec)
  57.             return new_rec;
  58.  
  59.         *new_rec = *rec_dat;
  60.  
  61.         index = hash(new_rec->key);
  62.         new_rec->link = the_table[index];
  63.         the_table[index] = new_rec;
  64.         return new_rec;
  65. }
  66.  
  67. /**
  68. *    find the record whose key is target.
  69. **/
  70. TBL_PTR tbl_find(target)
  71. char *target;
  72. {
  73.         register TBL_PTR rec_ptr;
  74.  
  75.  
  76.         for(rec_ptr = the_table[hash(target)];
  77.             rec_ptr && strcmp(target, rec_ptr->key);
  78.             rec_ptr = rec_ptr->link)
  79.             {
  80.                 /* empty */
  81.             }
  82.  
  83.         return rec_ptr;
  84. }
  85.  
  86.  
  87.  
  88. static unsigned int hash(key)
  89. char *key;
  90. {
  91.    register unsigned int sum;
  92.    register char *ptr;
  93.  
  94.    sum = 1;
  95.    for(ptr = key; *ptr; ptr++)
  96.    {
  97.            sum <<= 1;
  98.            sum ^= *ptr;
  99.    }
  100.  
  101.    return sum % HASH_TAB_LEN;
  102. }
  103.  
  104.