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