compilers/linux86-0.16.17/cpp/hash.c

   1
   2 #include <stdio.h>
   3 #ifdef __STDC__
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #else
   7 #include <malloc.h>
   8 #endif
   9 #include "cc.h"
  10
  11 /*
  12  * Two functions:
  13  * char * set_entry(int namespace, char * name, void * value);
  14  *        returns a pointer to the copy of the name;
  15  *
  16  * void * read_entry(int namespace, char * name);
  17  *        returns the value;
  18  */
  19
  20 struct hashentry
  21 {
  22    struct hashentry * next;
  23    void * value;
  24    int    namespace;
  25    char   word[1];
  26 };
  27
  28 struct hashentry ** hashtable;
  29 int  hashsize  = 0xFF;  /* 2^X -1 */
  30 int  hashcount = 0;
  31 static int hashvalue P((int namespace, char * word));
  32
  33 void *
  34 read_entry(namespace, word)
  35 int namespace;
  36 char * word;
  37 {
  38    int hash_val;
  39    struct hashentry * hashline;
  40    if( hashtable == 0 ) return 0;
  41    hash_val = hashvalue(namespace, word);
  42
  43    hashline = hashtable[hash_val];
  44
  45    for(; hashline; hashline = hashline->next)
  46    {
  47       if(namespace != hashline->namespace) continue;
  48       if(word[0] != hashline->word[0])     continue;
  49       if(strcmp(word, hashline->word) )    continue;
  50       return hashline->value;
  51    }
  52    return 0;
  53 }
  54
  55 char *
  56 set_entry(namespace, word, value)
  57 int namespace;
  58 char * word;
  59 void * value;
  60 {
  61    int hash_val, i;
  62    struct hashentry * hashline, *prev;
  63    hash_val = hashvalue(namespace, word);
  64
  65    if( hashtable )
  66    {
  67       hashline = hashtable[hash_val];
  68
  69       for(prev=0; hashline; prev=hashline, hashline = hashline->next)
  70       {
  71          if(namespace != hashline->namespace) continue;
  72          if(word[0] != hashline->word[0])     continue;
  73          if(strcmp(word, hashline->word) )    continue;
  74          if( value ) hashline->value = value;
  75          else
  76          {
  77             if( prev == 0 ) hashtable[hash_val] = hashline->next;
  78             else            prev->next = hashline->next;
  79             free(hashline);
  80             return 0;
  81          }
  82          return hashline->word;
  83       }
  84    }
  85    if( value == 0 ) return 0;
  86    if( hashtable == 0 )
  87    {
  88       hashtable = malloc((hashsize+1)*sizeof(char*));
  89       if( hashtable == 0 ) cfatal("Out of memory");
  90       for(i=0; i<=hashsize; i++) hashtable[i] = 0;
  91    }
  92    /* Add record */
  93    hashline = malloc(sizeof(struct hashentry)+strlen(word));
  94    if( hashline == 0 ) cfatal("Out of memory");
  95    else
  96    {
  97       hashline->next  = hashtable[hash_val];
  98       hashline->namespace = namespace;
  99       hashline->value = value;
 100       strcpy(hashline->word, word);
 101       hashtable[hash_val] = hashline;
 102    }
 103    return hashline->word;
 104 }
 105
 106 static int hashvalue(namespace, word)
 107 int namespace;
 108 char * word;
 109 {
 110    int val = namespace;
 111    char *p = word;
 112
 113    while(*p)
 114    {
 115       val = ((val<<4)^((val>>12)&0xF)^((*p++)&0xFF));
 116    }
 117    val &= hashsize;
 118    return val;
 119 }