1
2 /* Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
3 * http://www.digitalmars.com
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
6 * https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c
7 */
8
9 #include "dsystem.h" // uint{8|16|32}_t, memcpy()
10 #include "root.h"
11 #include "rmem.h" // mem
12 #include "stringtable.h"
13 #include "hash.h"
14
15 #define POOL_BITS 12
16 #define POOL_SIZE (1U << POOL_BITS)
17
18 struct StringEntry
19 {
20 uint32_t hash;
21 uint32_t vptr;
22 };
23
allocValue(const char * s,size_t length,void * ptrvalue)24 uint32_t StringTable::allocValue(const char *s, size_t length, void *ptrvalue)
25 {
26 const size_t nbytes = sizeof(StringValue) + length + 1;
27
28 if (!npools || nfill + nbytes > POOL_SIZE)
29 {
30 pools = (uint8_t **)mem.xrealloc(pools, ++npools * sizeof(pools[0]));
31 pools[npools - 1] = (uint8_t *)mem.xmalloc(nbytes > POOL_SIZE ? nbytes : POOL_SIZE);
32 nfill = 0;
33 }
34
35 StringValue *sv = (StringValue *)&pools[npools - 1][nfill];
36 sv->ptrvalue = ptrvalue;
37 sv->length = length;
38 ::memcpy(sv->lstring(), s, length);
39 sv->lstring()[length] = 0;
40
41 const uint32_t vptr = (uint32_t)(npools << POOL_BITS | nfill);
42 nfill += nbytes + (-nbytes & 7); // align to 8 bytes
43 return vptr;
44 }
45
getValue(uint32_t vptr)46 StringValue *StringTable::getValue(uint32_t vptr)
47 {
48 if (!vptr) return NULL;
49
50 const size_t idx = (vptr >> POOL_BITS) - 1;
51 const size_t off = vptr & (POOL_SIZE - 1);
52 return (StringValue *)&pools[idx][off];
53 }
54
nextpow2(size_t val)55 static size_t nextpow2(size_t val)
56 {
57 size_t res = 1;
58 while (res < val)
59 res <<= 1;
60 return res;
61 }
62
63 static const double loadFactor = 0.8;
64
_init(size_t size)65 void StringTable::_init(size_t size)
66 {
67 size = nextpow2((size_t)(size / loadFactor));
68 if (size < 32) size = 32;
69 table = (StringEntry *)mem.xcalloc(size, sizeof(table[0]));
70 tabledim = size;
71 pools = NULL;
72 npools = nfill = 0;
73 count = 0;
74 }
75
reset(size_t size)76 void StringTable::reset(size_t size)
77 {
78 for (size_t i = 0; i < npools; ++i)
79 mem.xfree(pools[i]);
80
81 mem.xfree(table);
82 mem.xfree(pools);
83 table = NULL;
84 pools = NULL;
85 _init(size);
86 }
87
~StringTable()88 StringTable::~StringTable()
89 {
90 for (size_t i = 0; i < npools; ++i)
91 mem.xfree(pools[i]);
92
93 mem.xfree(table);
94 mem.xfree(pools);
95 table = NULL;
96 pools = NULL;
97 }
98
findSlot(hash_t hash,const char * s,size_t length)99 size_t StringTable::findSlot(hash_t hash, const char *s, size_t length)
100 {
101 // quadratic probing using triangular numbers
102 // http://stackoverflow.com/questions/2348187/moving-from-linear-probing-to-quadratic-probing-hash-collisons/2349774#2349774
103 for (size_t i = hash & (tabledim - 1), j = 1; ;++j)
104 {
105 StringValue *sv;
106 if (!table[i].vptr ||
107 (table[i].hash == hash &&
108 (sv = getValue(table[i].vptr))->length == length &&
109 ::memcmp(s, sv->lstring(), length) == 0))
110 return i;
111 i = (i + j) & (tabledim - 1);
112 }
113 }
114
lookup(const char * s,size_t length)115 StringValue *StringTable::lookup(const char *s, size_t length)
116 {
117 const hash_t hash = calcHash(s, length);
118 const size_t i = findSlot(hash, s, length);
119 // printf("lookup %.*s %p\n", (int)length, s, table[i].value ?: NULL);
120 return getValue(table[i].vptr);
121 }
122
update(const char * s,size_t length)123 StringValue *StringTable::update(const char *s, size_t length)
124 {
125 const hash_t hash = calcHash(s, length);
126 size_t i = findSlot(hash, s, length);
127 if (!table[i].vptr)
128 {
129 if (++count > tabledim * loadFactor)
130 {
131 grow();
132 i = findSlot(hash, s, length);
133 }
134 table[i].hash = hash;
135 table[i].vptr = allocValue(s, length, NULL);
136 }
137 // printf("update %.*s %p\n", (int)length, s, table[i].value ?: NULL);
138 return getValue(table[i].vptr);
139 }
140
insert(const char * s,size_t length,void * ptrvalue)141 StringValue *StringTable::insert(const char *s, size_t length, void *ptrvalue)
142 {
143 const hash_t hash = calcHash(s, length);
144 size_t i = findSlot(hash, s, length);
145 if (table[i].vptr)
146 return NULL; // already in table
147 if (++count > tabledim * loadFactor)
148 {
149 grow();
150 i = findSlot(hash, s, length);
151 }
152 table[i].hash = hash;
153 table[i].vptr = allocValue(s, length, ptrvalue);
154 // printf("insert %.*s %p\n", (int)length, s, table[i].value ?: NULL);
155 return getValue(table[i].vptr);
156 }
157
grow()158 void StringTable::grow()
159 {
160 const size_t odim = tabledim;
161 StringEntry *otab = table;
162 tabledim *= 2;
163 table = (StringEntry *)mem.xcalloc(tabledim, sizeof(table[0]));
164
165 for (size_t i = 0; i < odim; ++i)
166 {
167 StringEntry *se = &otab[i];
168 if (!se->vptr) continue;
169 StringValue *sv = getValue(se->vptr);
170 table[findSlot(se->hash, sv->lstring(), sv->length)] = *se;
171 }
172 mem.xfree(otab);
173 }
174
175 /********************************
176 * Walk the contents of the string table,
177 * calling fp for each entry.
178 * Params:
179 * fp = function to call. Returns !=0 to stop
180 * Returns:
181 * last return value of fp call
182 */
apply(int (* fp)(StringValue *))183 int StringTable::apply(int (*fp)(StringValue *))
184 {
185 for (size_t i = 0; i < tabledim; ++i)
186 {
187 StringEntry *se = &table[i];
188 if (!se->vptr) continue;
189 StringValue *sv = getValue(se->vptr);
190 int result = (*fp)(sv);
191 if (result)
192 return result;
193 }
194 return 0;
195 }
196
197