Mercurial > projects > ldc

comparison dmd/root/stringtable.c @ 1194:1853dcd9b944

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved some DMDFE files into a seperate dmd/root subdir to closer match the DMD file structure since 1.041.
author Tomas Lindquist Olsen <tomas.l.olsen gmail.com>
date Fri, 03 Apr 2009 17:02:52 +0200
parents dmd/stringtable.c@b30fe7e1dbb9
children
comparison
equal deleted inserted replaced
1193:c271eca933fb 1194:1853dcd9b944
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 "rmem.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