|
145
|
1
|
|
|
2 /* Copyright (C) 1999-2019 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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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 */
|
|
|
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
|
