home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume30 / tin / part14 / hashstr.c < prev    next >
C/C++ Source or Header  |  1992-05-20  |  3KB  |  126 lines
  1. /*
  2.  *  Project   : tin - a threaded Netnews reader
  3.  *  Module    : hashstr.c
  4.  *  Author    : I.Lea & R.Skrenta
  5.  *  Created   : 01-04-91
  6.  *  Updated   : 21-03-92
  7.  *  Notes     :
  8.  *  Copyright : (c) Copyright 1991-92 by Iain Lea & Rich Skrenta
  9.  *              You may  freely  copy or  redistribute  this software,
  10.  *              so  long as there is no profit made from its use, sale
  11.  *              trade or  reproduction.  You may not change this copy-
  12.  *              right notice, and it must be included in any copy made
  13.  */
  14.  
  15. #include    "tin.h"
  16.  
  17. /*
  18.  *  Maintain a table of all strings we have seen.
  19.  *  If a new string comes in, add it to the table and return a pointer
  20.  *  to it.  If we've seen it before, just return the pointer to it.
  21.  *
  22.  *  Usage:  hash_str("some string") returns char *
  23.  *
  24.  *  Spillovers are chained on the end
  25.  */
  26.  
  27. /*
  28.  *  Arbitrary table size, but make sure it's prime!
  29.  */
  30.  
  31. #define        HASHNODE_TABLE_SIZE    2411
  32.  
  33. struct hashnode *table[HASHNODE_TABLE_SIZE];
  34.  
  35.  
  36. char *hash_str (s)
  37.     char *s;
  38. {
  39.     long h;                /* result of hash:  index into hash table */
  40.     struct hashnode *p;    /* used to descend the spillover structs */
  41.  
  42.     if (s == (char *) 0) {
  43.         return ((char *) 0);
  44.     }
  45.  
  46.     {
  47.         unsigned char *t = (unsigned char *) s;
  48.  
  49.         h = *t++;
  50.         while (*t)
  51.             h = ((h << 1) ^ *t++) % (long) HASHNODE_TABLE_SIZE;
  52.     }
  53.  
  54.     p = table[h];
  55.  
  56.     if (p == (struct hashnode *) 0) {
  57.         table[h] = add_string (s);
  58.         return table[h]->s;
  59.     }
  60.  
  61.     while (1) {
  62.         if (strcmp (s, p->s) == 0) {
  63.             return (p->s);
  64.         }
  65.  
  66.         if (p->next == (struct hashnode *) 0) {
  67.             p->next = add_string (s);
  68.             return p->next->s;
  69.         } else {
  70.             p = p->next;
  71.         }
  72.     }
  73.     /* NOTREACHED */
  74. }
  75.  
  76.  
  77. struct hashnode *add_string (s)
  78.     char *s;
  79. {
  80.     int *iptr;
  81.     struct hashnode *p;
  82.  
  83.     p = (struct hashnode *) my_malloc ((unsigned) sizeof (struct hashnode));
  84.  
  85.     p->next = (struct hashnode *) 0;
  86.     iptr = (int *) my_malloc ((unsigned) strlen (s) + sizeof (int) + 1);
  87.     *iptr++ = -1;
  88.     p->s = (char *) iptr;
  89.     strcpy (p->s, s);
  90.     return (p);
  91. }
  92.  
  93.  
  94. void hash_init ()
  95. {
  96.     int i;
  97.  
  98.     for (i = 0; i < HASHNODE_TABLE_SIZE; i++) {
  99.         table[i] = (struct hashnode *) 0;
  100.     }
  101. }
  102.  
  103.  
  104. void hash_reclaim ()
  105. {
  106.     int i;
  107.     int *iptr;
  108.     struct hashnode *p, *next;
  109.  
  110.     for (i = 0; i < HASHNODE_TABLE_SIZE; i++)
  111.         if (table[i] != (struct hashnode *) 0) {
  112.             p = table[i];
  113.             while (p != (struct hashnode *) 0) {
  114.                 next = p->next;
  115.                 if (p->s != (char *) 0) {
  116.                     iptr = (int *) p->s;
  117.                     iptr--;
  118.                     free ((char *) iptr);
  119.                 }
  120.                 free ((char *) p);
  121.                 p = next;
  122.             }
  123.             table[i] = (struct hashnode *) 0;
  124.         }
  125. }
  126.