src/tree.c

   1 /*
   2 ** tree.c
   3 ** TecCGraf - PUC-Rio
   4 */
   5
   6 char *rcs_tree="$Id: tree.c,v 1.28 1997/06/11 14:24:40 roberto Exp $";
   7
   8
   9 #include <string.h>
  10
  11 #include "luamem.h"
  12 #include "lua.h"
  13 #include "tree.h"
  14 #include "lex.h"
  15 #include "hash.h"
  16 #include "table.h"
  17 #include "fallback.h"
  18
  19
  20 #define NUM_HASHS  64
  21
  22 typedef struct {
  23   int size;
  24   int nuse;  /* number of elements (including EMPTYs) */
  25   TaggedString **hash;
  26 } stringtable;
  27
  28 static int initialized = 0;
  29
  30 static stringtable string_root[NUM_HASHS];
  31
  32 static TaggedString EMPTY = {LUA_T_STRING, NULL, {{NOT_USED, NOT_USED}},
  33                              0, 2, {0}};
  34
  35
  36 static unsigned long hash (char *s, int tag)
  37 {
  38   unsigned long h;
  39   if (tag != LUA_T_STRING)
  40     h = (unsigned long)s;
  41   else {
  42     h = 0;
  43     while (*s)
  44       h = ((h<<5)-h)^(unsigned char)*(s++);
  45   }
  46   return h;
  47 }
  48
  49
  50 static void luaI_inittree (void)
  51 {
  52   int i;
  53   for (i=0; i<NUM_HASHS; i++) {
  54     string_root[i].size = 0;
  55     string_root[i].nuse = 0;
  56     string_root[i].hash = NULL;
  57   }
  58 }
  59
  60
  61 static void initialize (void)
  62 {
  63   initialized = 1;
  64   luaI_inittree();
  65   luaI_addReserved();
  66   luaI_initsymbol();
  67   luaI_initconstant();
  68   luaI_initfallbacks();
  69 }
  70
  71
  72 static void grow (stringtable *tb)
  73 {
  74   int newsize = luaI_redimension(tb->size);
  75   TaggedString **newhash = newvector(newsize, TaggedString *);
  76   int i;
  77   for (i=0; i<newsize; i++)
  78     newhash[i] = NULL;
  79   /* rehash */
  80   tb->nuse = 0;
  81   for (i=0; i<tb->size; i++)
  82     if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY) {
  83       int h = tb->hash[i]->hash%newsize;
  84       while (newhash[h])
  85         h = (h+1)%newsize;
  86       newhash[h] = tb->hash[i];
  87       tb->nuse++;
  88     }
  89   luaI_free(tb->hash);
  90   tb->size = newsize;
  91   tb->hash = newhash;
  92 }
  93
  94
  95 static TaggedString *newone(char *buff, int tag, unsigned long h)
  96 {
  97   TaggedString *ts;
  98   if (tag == LUA_T_STRING) {
  99     ts = (TaggedString *)luaI_malloc(sizeof(TaggedString)+strlen(buff));
 100     strcpy(ts->str, buff);
 101     ts->u.s.varindex = ts->u.s.constindex = NOT_USED;
 102     ts->tag = LUA_T_STRING;
 103   }
 104   else {
 105     ts = (TaggedString *)luaI_malloc(sizeof(TaggedString));
 106     ts->u.v = buff;
 107     ts->tag = tag == LUA_ANYTAG ? 0 : tag;
 108   }
 109   ts->marked = 0;
 110   ts->hash = h;
 111   return ts;
 112 }
 113
 114 static TaggedString *insert (char *buff, int tag, stringtable *tb)
 115 {
 116   TaggedString *ts;
 117   unsigned long h = hash(buff, tag);
 118   int i;
 119   int j = -1;
 120   if ((Long)tb->nuse*3 >= (Long)tb->size*2)
 121   {
 122     if (!initialized)
 123       initialize();
 124     grow(tb);
 125   }
 126   i = h%tb->size;
 127   while ((ts = tb->hash[i]) != NULL)
 128   {
 129     if (ts == &EMPTY)
 130       j = i;
 131     else if ((ts->tag == LUA_T_STRING) ?
 132               (tag == LUA_T_STRING && (strcmp(buff, ts->str) == 0)) :
 133               ((tag == ts->tag || tag == LUA_ANYTAG) && buff == ts->u.v))
 134       return ts;
 135     i = (i+1)%tb->size;
 136   }
 137   /* not found */
 138   lua_pack();
 139   if (j != -1)  /* is there an EMPTY space? */
 140     i = j;
 141   else
 142     tb->nuse++;
 143   ts = tb->hash[i] = newone(buff, tag, h);
 144   return ts;
 145 }
 146
 147 TaggedString *luaI_createudata (void *udata, int tag)
 148 {
 149   return insert(udata, tag, &string_root[(unsigned)udata%NUM_HASHS]);
 150 }
 151
 152 TaggedString *lua_createstring (char *str)
 153 {
 154   return insert(str, LUA_T_STRING, &string_root[(unsigned)str[0]%NUM_HASHS]);
 155 }
 156
 157
 158 void luaI_strcallIM (TaggedString *l)
 159 {
 160   TObject o;
 161   ttype(&o) = LUA_T_USERDATA;
 162   for (; l; l=l->next) {
 163     tsvalue(&o) = l;
 164     luaI_gcIM(&o);
 165   }
 166 }
 167
 168
 169 void luaI_strfree (TaggedString *l)
 170 {
 171   while (l) {
 172     TaggedString *next = l->next;
 173     luaI_free(l);
 174     l = next;
 175   }
 176 }
 177
 178
 179 /*
 180 ** Garbage collection function.
 181 */
 182 TaggedString *luaI_strcollector (long *acum)
 183 {
 184   Long counter = 0;
 185   TaggedString *frees = NULL;
 186   int i;
 187   for (i=0; i<NUM_HASHS; i++)
 188   {
 189     stringtable *tb = &string_root[i];
 190     int j;
 191     for (j=0; j<tb->size; j++)
 192     {
 193       TaggedString *t = tb->hash[j];
 194       if (t != NULL && t->marked <= 1)
 195       {
 196         if (t->marked)
 197           t->marked = 0;
 198         else
 199         {
 200           t->next = frees;
 201           frees = t;
 202           tb->hash[j] = &EMPTY;
 203           counter++;
 204         }
 205       }
 206     }
 207   }
 208   *acum += counter;
 209   return frees;
 210 }
 211