home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / program / cpp102 / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-23  |  3.7 KB  |  188 lines
  1.  
  2. #include "global.h"
  3. #include "ztype.h"
  4.  
  5. #define HASH_SIZE 1009
  6.  
  7. extern char *magic_words[];
  8. extern int N_MWORDS;
  9.  
  10. /* a hash object */
  11. typedef struct hash {
  12.   char *id;
  13.   Macro *data;
  14.   struct hash *next;
  15. } Hash;
  16.  
  17. static Hash *H[HASH_SIZE];
  18.  
  19. /*
  20.    hash_id() -- compute a hash value for the identifier pointed to by |s|;
  21.    place a pointer to the first character after the identifier in |*end|.
  22.  
  23. Credit where it's due -- this hash function was originally suggested by Chris
  24.    Torek on comp.lang.c.  As an explanation of the implementation, he
  25.    offered:  "What *does* that 33 do?  I have no idea."
  26. */
  27. unsigned int hash_id(s, end)
  28.   register char *s;
  29.   char **end;
  30. {
  31.   register unsigned int h = 0;
  32.  
  33.   for (; is_ctok(*s); s++)
  34.     h = (h * 33 + *s) % HASH_SIZE;
  35.   if (end)
  36.     *end = s;
  37.   return h;
  38. }
  39.  
  40. /*
  41.    hash_add() -- add to the hash table an entry for the identifier |s|, with
  42.    hash value |hv| and macro value |M|
  43. */
  44. void hash_add(s, hv, M)
  45.   char *s;
  46.   unsigned int hv;
  47.   Macro *M;
  48. {
  49.   Hash *h, *hh;
  50.   h = mallok(sizeof (Hash));
  51.  
  52.   h->data = M;
  53.   h->next = NULL;
  54.   h->id = strdup(s);
  55.   h->next = H[hv];
  56.   H[hv] = h;
  57. }
  58.  
  59. /*
  60.    hash_unlink() -- destroy the hash object pointed to by |h|; return a
  61.    pointer to the hash object following |h|.  Used in hash_remove().
  62. */
  63. static Hash *hash_unlink(h)
  64.   Hash *h;
  65. {
  66.   Hash *hh = h->next;
  67.  
  68.   free(h->id);
  69.   if (h->data->m_text)
  70.     free(h->data->m_text);
  71.   free(h->data);
  72.   free(h);
  73.   return hh;
  74. }
  75.  
  76. /*
  77.    hash_remove() -- remove the hash object for identifier |s|, with hash
  78.    value |hv|
  79. */
  80. void hash_remove(s, hv)
  81.   char *s;
  82.   unsigned int hv;
  83. {
  84.   unsigned int i;
  85.   Hash *h;
  86.  
  87.   if (!H[hv])
  88.     return;
  89.   if (streq(H[hv]->id, s)) {
  90.     H[hv] = hash_unlink(H[hv]);
  91.     return;
  92.   }
  93.   for (h = H[hv]; h->next; h = h->next)
  94.     if (streq(h->next->id, s)) {
  95.       h->next = hash_unlink(h->next);
  96.       return;
  97.     }
  98. }
  99.  
  100. /*
  101.    magic_check() -- determine if the conditionally-active magic preprocessor
  102.    constant in hash object |h| is in fact active
  103. */
  104. static int magic_check(h)
  105.   Hash *h;
  106. {
  107.   if (streq(h->id, "__STDC__") && ansi)
  108.     return 1;
  109.   if (streq(h->id, "defined") && (get_mode() & IF_EXPR))
  110.     return 1;
  111.   return 0;
  112. }
  113.  
  114. /*
  115.    lookup() -- look for the identifier |s| with hash value |hv| in the hash
  116.    table.  Return its associated macro value, or NULL if the identifier is
  117.    not present
  118. */
  119. Macro *lookup(s, hv)
  120.   char *s;
  121.   unsigned int hv;
  122. {
  123.   Hash *h;
  124.  
  125.   for (h = H[hv]; h; h = h->next)
  126.     if (streq(h->id, s)) {
  127.       if (!(h->data->flags & MAGIC2) || magic_check(h)) {
  128.     return h->data;
  129.       } else {
  130.     return NULL;
  131.       }
  132.     }
  133.   return NULL;
  134. }
  135.  
  136. /*
  137.    hash_setup() -- initialize the hash table and add the predefined tokens
  138. */
  139. void hash_setup()
  140. {
  141.   int i;
  142.   Macro *M;
  143.   unsigned int hv;
  144.  
  145.   for (i = 0; i < HASH_SIZE; i++)
  146.     H[i] = NULL;
  147.   for (i = 0; i < N_MWORDS; i++) {
  148.     M = mallok(sizeof (Macro));
  149.  
  150.     M->nargs = 0;
  151.     M->m_text = M->argnames = NULL;
  152.     M->flags = MAGIC;
  153.     if (i < 2)
  154.       M->flags |= MAGIC2;
  155.     hash_add(magic_words[i], hash_id(magic_words[i], NULL), M);
  156.   }
  157. }
  158.  
  159. /*
  160.    hash_clean_undef() -- remove all identifiers that were #undef'ined via -U
  161.    from the hash table
  162. */
  163. void hash_clean_undef()
  164. {
  165.   int i;
  166.   Hash *h;
  167.  
  168.   for (i = 0; i < HASH_SIZE; i++) {
  169.     while (H[i] && H[i]->data->flags & UNDEF)
  170.       H[i] = hash_unlink(H[i]);
  171.     if (H[i]) {
  172.       for (h = H[i]; h->next; h = h->next)
  173.     if (h->next->data->flags & UNDEF)
  174.       h->next = hash_unlink(h->next);
  175.     }
  176.   }
  177. }
  178.  
  179. /* hash_free() -- deallocate all hash objects */
  180. void hash_free()
  181. {
  182.   int i;
  183.   Hash *h;
  184.  
  185.   for (i = 0; i < HASH_SIZE; i++)
  186.     for (h = H[i]; h; h = hash_unlink(h)) ;
  187. }
  188.