dmd2/stringtable.c

   1
   2 // Copyright (c) 1999-2008 by Digital Mars
   3 // All Rights Reserved
   4 // written by Walter Bright
   5 // http://www.digitalmars.com
   6 // License for redistribution is by either the Artistic License
   7 // in artistic.txt, or the GNU General Public License in gnu.txt.
   8 // See the included readme.txt for details.
   9
  10
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include <stdlib.h>
  14
  15 #include "root.h"
  16 #include "mem.h"
  17 #include "dchar.h"
  18 #include "lstring.h"
  19 #include "stringtable.h"
  20
  21 StringTable::StringTable(unsigned size)
  22 {
  23     table = (void **)mem.calloc(size, sizeof(void *));
  24     tabledim = size;
  25     count = 0;
  26 }
  27
  28 StringTable::~StringTable()
  29 {
  30     unsigned i;
  31
  32     // Zero out dangling pointers to help garbage collector.
  33     // Should zero out StringEntry's too.
  34     for (i = 0; i < count; i++)
  35         table[i] = NULL;
  36
  37     mem.free(table);
  38     table = NULL;
  39 }
  40
  41 struct StringEntry
  42 {
  43     StringEntry *left;
  44     StringEntry *right;
  45     hash_t hash;
  46
  47     StringValue value;
  48
  49     static StringEntry *alloc(const dchar *s, unsigned len);
  50 };
  51
  52 StringEntry *StringEntry::alloc(const dchar *s, unsigned len)
  53 {
  54     StringEntry *se;
  55
  56     se = (StringEntry *) mem.calloc(1,sizeof(StringEntry) - sizeof(Lstring) + Lstring::size(len));
  57     se->value.lstring.length = len;
  58     se->hash = Dchar::calcHash(s,len);
  59     memcpy(se->value.lstring.string, s, len * sizeof(dchar));
  60     return se;
  61 }
  62
  63 void **StringTable::search(const dchar *s, unsigned len)
  64 {
  65     hash_t hash;
  66     unsigned u;
  67     int cmp;
  68     StringEntry **se;
  69
  70     //printf("StringTable::search(%p,%d)\n",s,len);
  71     hash = Dchar::calcHash(s,len);
  72     u = hash % tabledim;
  73     se = (StringEntry **)&table[u];
  74     //printf("\thash = %d, u = %d\n",hash,u);
  75     while (*se)
  76     {
  77         cmp = (*se)->hash - hash;
  78         if (cmp == 0)
  79         {
  80             cmp = (*se)->value.lstring.len() - len;
  81             if (cmp == 0)
  82             {
  83                 cmp = Dchar::memcmp(s,(*se)->value.lstring.toDchars(),len);
  84                 if (cmp == 0)
  85                     break;
  86             }
  87         }
  88         if (cmp < 0)
  89             se = &(*se)->left;
  90         else
  91             se = &(*se)->right;
  92     }
  93     //printf("\treturn %p, %p\n",se, (*se));
  94     return (void **)se;
  95 }
  96
  97 StringValue *StringTable::lookup(const dchar *s, unsigned len)
  98 {   StringEntry *se;
  99
 100     se = *(StringEntry **)search(s,len);
 101     if (se)
 102         return &se->value;
 103     else
 104         return NULL;
 105 }
 106
 107 StringValue *StringTable::update(const dchar *s, unsigned len)
 108 {   StringEntry **pse;
 109     StringEntry *se;
 110
 111     pse = (StringEntry **)search(s,len);
 112     se = *pse;
 113     if (!se)                    // not in table: so create new entry
 114     {
 115         se = StringEntry::alloc(s, len);
 116         *pse = se;
 117     }
 118     return &se->value;
 119 }
 120
 121 StringValue *StringTable::insert(const dchar *s, unsigned len)
 122 {   StringEntry **pse;
 123     StringEntry *se;
 124
 125     pse = (StringEntry **)search(s,len);
 126     se = *pse;
 127     if (se)
 128         return NULL;            // error: already in table
 129     else
 130     {
 131         se = StringEntry::alloc(s, len);
 132         *pse = se;
 133     }
 134     return &se->value;
 135 }
 136
 137
 138
 139