src/lstring.c

   1 /*
   2 ** $Id: lstring.c,v 1.13 1998/06/19 16:14:09 roberto Exp $
   3 ** String table (keeps all strings handled by Lua)
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7
   8 #include <string.h>
   9
  10 #include "lmem.h"
  11 #include "lobject.h"
  12 #include "lstate.h"
  13 #include "lstring.h"
  14 #include "lua.h"
  15
  16
  17 #define NUM_HASHS  61
  18
  19
  20 #define gcsizestring(l) (1+(l/64))  /* "weight" for a string with length 'l' */
  21
  22
  23
  24 static TaggedString EMPTY = {{NULL, 2}, 0L, 0,
  25                             {{{LUA_T_NIL, {NULL}}, 0L}}, {0}};
  26
  27
  28 void luaS_init (void)
  29 {
  30   int i;
  31   L->string_root = luaM_newvector(NUM_HASHS, stringtable);
  32   for (i=0; i<NUM_HASHS; i++) {
  33     L->string_root[i].size = 0;
  34     L->string_root[i].nuse = 0;
  35     L->string_root[i].hash = NULL;
  36   }
  37 }
  38
  39
  40 static unsigned long hash_s (char *s, long l)
  41 {
  42   unsigned long h = 0;
  43   while (l--)
  44     h = ((h<<5)-h)^(unsigned char)*(s++);
  45   return h;
  46 }
  47
  48 static int newsize (stringtable *tb)
  49 {
  50   int size = tb->size;
  51   int realuse = 0;
  52   int i;
  53   /* count how many entries are really in use */
  54   for (i=0; i<size; i++)
  55     if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY)
  56       realuse++;
  57   if (2*(realuse+1) <= size)  /* +1 is the new element */
  58     return size;  /* don't need to grow, just rehash to clear EMPTYs */
  59   else
  60     return luaO_redimension(size);
  61 }
  62
  63
  64 static void grow (stringtable *tb)
  65 {
  66
  67   int ns = newsize(tb);
  68   TaggedString **newhash = luaM_newvector(ns, TaggedString *);
  69   int i;
  70   for (i=0; i<ns; i++)
  71     newhash[i] = NULL;
  72   /* rehash */
  73   tb->nuse = 0;
  74   for (i=0; i<tb->size; i++) {
  75     if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY) {
  76       int h = tb->hash[i]->hash%ns;
  77       while (newhash[h])
  78         h = (h+1)%ns;
  79       newhash[h] = tb->hash[i];
  80       tb->nuse++;
  81     }
  82   }
  83   luaM_free(tb->hash);
  84   tb->size = ns;
  85   tb->hash = newhash;
  86 }
  87
  88
  89 static TaggedString *newone_s (char *str, long l, unsigned long h)
  90 {
  91   TaggedString *ts = (TaggedString *)luaM_malloc(sizeof(TaggedString)+l);
  92   memcpy(ts->str, str, l);
  93   ts->str[l] = 0;  /* ending 0 */
  94   ts->u.s.globalval.ttype = LUA_T_NIL;  /* initialize global value */
  95   ts->u.s.len = l;
  96   ts->constindex = 0;
  97   L->nblocks += gcsizestring(l);
  98   ts->head.marked = 0;
  99   ts->head.next = (GCnode *)ts;  /* signal it is in no list */
 100   ts->hash = h;
 101   return ts;
 102 }
 103
 104 static TaggedString *newone_u (char *buff, int tag, unsigned long h)
 105 {
 106   TaggedString *ts = luaM_new(TaggedString);
 107   ts->u.d.v = buff;
 108   ts->u.d.tag = (tag == LUA_ANYTAG) ? 0 : tag;
 109   ts->constindex = -1;  /* tag -> this is a userdata */
 110   L->nblocks++;
 111   ts->head.marked = 0;
 112   ts->head.next = (GCnode *)ts;  /* signal it is in no list */
 113   ts->hash = h;
 114   return ts;
 115 }
 116
 117 static TaggedString *insert_s (char *str, long l, stringtable *tb)
 118 {
 119   TaggedString *ts;
 120   unsigned long h = hash_s(str, l);
 121   int size = tb->size;
 122   int i;
 123   int j = -1;
 124   if ((long)tb->nuse*3 >= (long)size*2) {
 125     grow(tb);
 126     size = tb->size;
 127   }
 128   for (i = h%size; (ts = tb->hash[i]) != NULL; ) {
 129     if (ts == &EMPTY)
 130       j = i;
 131     else if (ts->constindex >= 0 &&
 132              ts->u.s.len == l &&
 133              (memcmp(str, ts->str, l) == 0))
 134       return ts;
 135     if (++i == size) i=0;
 136   }
 137   /* not found */
 138   if (j != -1)  /* is there an EMPTY space? */
 139     i = j;
 140   else
 141     tb->nuse++;
 142   ts = tb->hash[i] = newone_s(str, l, h);
 143   return ts;
 144 }
 145
 146 static TaggedString *insert_u (void *buff, int tag, stringtable *tb)
 147 {
 148   TaggedString *ts;
 149   unsigned long h = (unsigned long)buff;
 150   int size = tb->size;
 151   int i;
 152   int j = -1;
 153   if ((long)tb->nuse*3 >= (long)size*2) {
 154     grow(tb);
 155     size = tb->size;
 156   }
 157   for (i = h%size; (ts = tb->hash[i]) != NULL; ) {
 158     if (ts == &EMPTY)
 159       j = i;
 160     else if (ts->constindex < 0 &&  /* is a udata? */
 161              (tag == ts->u.d.tag || tag == LUA_ANYTAG) &&
 162              buff == ts->u.d.v)
 163       return ts;
 164     if (++i == size) i=0;
 165   }
 166   /* not found */
 167   if (j != -1)  /* is there an EMPTY space? */
 168     i = j;
 169   else
 170     tb->nuse++;
 171   ts = tb->hash[i] = newone_u(buff, tag, h);
 172   return ts;
 173 }
 174
 175 TaggedString *luaS_createudata (void *udata, int tag)
 176 {
 177   return insert_u(udata, tag, &L->string_root[(unsigned)udata%NUM_HASHS]);
 178 }
 179
 180 TaggedString *luaS_newlstr (char *str, long l)
 181 {
 182   int i = (l==0)?0:(unsigned char)str[0];
 183   return insert_s(str, l, &L->string_root[i%NUM_HASHS]);
 184 }
 185
 186 TaggedString *luaS_new (char *str)
 187 {
 188   return luaS_newlstr(str, strlen(str));
 189 }
 190
 191 TaggedString *luaS_newfixedstring (char *str)
 192 {
 193   TaggedString *ts = luaS_new(str);
 194   if (ts->head.marked == 0)
 195     ts->head.marked = 2;  /* avoid GC */
 196   return ts;
 197 }
 198
 199
 200 void luaS_free (TaggedString *l)
 201 {
 202   while (l) {
 203     TaggedString *next = (TaggedString *)l->head.next;
 204     L->nblocks -= (l->constindex == -1) ? 1 : gcsizestring(l->u.s.len);
 205     luaM_free(l);
 206     l = next;
 207   }
 208 }
 209
 210
 211 /*
 212 ** Garbage collection functions.
 213 */
 214
 215 static void remove_from_list (GCnode *l)
 216 {
 217   while (l) {
 218     GCnode *next = l->next;
 219     while (next && !next->marked)
 220       next = l->next = next->next;
 221     l = next;
 222   }
 223 }
 224
 225
 226 TaggedString *luaS_collector (void)
 227 {
 228   TaggedString *frees = NULL;
 229   int i;
 230   remove_from_list(&(L->rootglobal));
 231   for (i=0; i<NUM_HASHS; i++) {
 232     stringtable *tb = &L->string_root[i];
 233     int j;
 234     for (j=0; j<tb->size; j++) {
 235       TaggedString *t = tb->hash[j];
 236       if (t == NULL) continue;
 237       if (t->head.marked == 1)
 238         t->head.marked = 0;
 239       else if (!t->head.marked) {
 240         t->head.next = (GCnode *)frees;
 241         frees = t;
 242         tb->hash[j] = &EMPTY;
 243       }
 244     }
 245   }
 246   return frees;
 247 }
 248
 249
 250 TaggedString *luaS_collectudata (void)
 251 {
 252   TaggedString *frees = NULL;
 253   int i;
 254   L->rootglobal.next = NULL;  /* empty list of globals */
 255   for (i=0; i<NUM_HASHS; i++) {
 256     stringtable *tb = &L->string_root[i];
 257     int j;
 258     for (j=0; j<tb->size; j++) {
 259       TaggedString *t = tb->hash[j];
 260       if (t == NULL || t == &EMPTY || t->constindex != -1)
 261         continue;  /* get only user data */
 262       t->head.next = (GCnode *)frees;
 263       frees = t;
 264       tb->hash[j] = &EMPTY;
 265     }
 266   }
 267   return frees;
 268 }
 269
 270
 271 void luaS_freeall (void)
 272 {
 273   int i;
 274   for (i=0; i<NUM_HASHS; i++) {
 275     stringtable *tb = &L->string_root[i];
 276     int j;
 277     for (j=0; j<tb->size; j++) {
 278       TaggedString *t = tb->hash[j];
 279       if (t == &EMPTY) continue;
 280       luaM_free(t);
 281     }
 282     luaM_free(tb->hash);
 283   }
 284   luaM_free(L->string_root);
 285 }
 286
 287
 288 void luaS_rawsetglobal (TaggedString *ts, TObject *newval)
 289 {
 290   ts->u.s.globalval = *newval;
 291   if (ts->head.next == (GCnode *)ts) {  /* is not in list? */
 292     ts->head.next = L->rootglobal.next;
 293     L->rootglobal.next = (GCnode *)ts;
 294   }
 295 }
 296
 297
 298 char *luaS_travsymbol (int (*fn)(TObject *))
 299 {
 300   TaggedString *g;
 301   for (g=(TaggedString *)L->rootglobal.next; g; g=(TaggedString *)g->head.next)
 302     if (fn(&g->u.s.globalval))
 303       return g->str;
 304   return NULL;
 305 }
 306
 307
 308 int luaS_globaldefined (char *name)
 309 {
 310   TaggedString *ts = luaS_new(name);
 311   return ts->u.s.globalval.ttype != LUA_T_NIL;
 312 }
 313