1
2 /*--------------------------------------------------------------------*/
3 /*--- An sparse array (of words) implementation. ---*/
4 /*--- m_sparsewa.c ---*/
5 /*--------------------------------------------------------------------*/
6
7 /*
8 This file is part of Valgrind, a dynamic binary instrumentation
9 framework.
10
11 Copyright (C) 2008-2017 OpenWorks Ltd
12 info@open-works.co.uk
13
14 This program is free software; you can redistribute it and/or
15 modify it under the terms of the GNU General Public License as
16 published by the Free Software Foundation; either version 2 of the
17 License, or (at your option) any later version.
18
19 This program is distributed in the hope that it will be useful, but
20 WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 General Public License for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
27 02111-1307, USA.
28
29 The GNU General Public License is contained in the file COPYING.
30 */
31
32 #include "pub_core_basics.h"
33 #include "pub_core_libcassert.h"
34 #include "pub_core_libcbase.h"
35 #include "pub_core_sparsewa.h" /* self */
36
37 /////////////////////////////////////////////////////////
38 // //
39 // SparseWA: Implementation //
40 // //
41 /////////////////////////////////////////////////////////
42
43 //////// SWA data structures
44
45 // (UInt) `echo "Level Zero Byte Map" | md5sum`
46 #define Level0_MAGIC 0x458ec222
47
48 // (UInt) `echo "Level N Byte Map" | md5sum`
49 #define LevelN_MAGIC 0x0a280a1a
50
51 /* It's important that the .magic field appears at offset zero in both
52 structs, so that we can reliably distinguish between them. */
53
54 typedef
55 struct {
56 UWord magic;
57 UWord words[256];
58 Int nInUse;
59 UChar inUse[256/8];
60 }
61 Level0;
62
63 typedef
64 struct {
65 UWord magic;
66 void* child[256]; /* either LevelN* or Level0* */
67 Int nInUse;
68 Int level; /* 3 .. 1 on 32-bit, 7 .. 1 on 64-bit */
69 }
70 LevelN;
71
72 typedef
73 struct {
74 UWord partial_key;
75 Int curr_ix;
76 void* curr_nd; /* LevelN* or Level0* */
77 Int resume_point; /* 1, 2 or 3 */
78 }
79 SWAStackElem;
80
81 struct _SparseWA {
82 void* (*alloc_nofail)(const HChar*,SizeT);
83 const HChar* cc;
84 void (*dealloc)(void*);
85 LevelN* root;
86 SWAStackElem iterStack[8];
87 Int isUsed;
88 };
89
90 //////// SWA helper functions (bitarray)
91
swa_bitarray_read(const UChar * arr,UWord ix)92 static inline UWord swa_bitarray_read ( const UChar* arr, UWord ix ) {
93 UWord bix = ix >> 3;
94 UWord off = ix & 7;
95 return (arr[bix] >> off) & 1;
96 }
97
swa_bitarray_read_then_set(UChar * arr,UWord ix)98 static inline UWord swa_bitarray_read_then_set ( UChar* arr, UWord ix ) {
99 UWord bix = ix >> 3;
100 UWord off = ix & 7;
101 UChar old = arr[bix];
102 UChar nyu = old | (1 << off);
103 arr[bix] = nyu;
104 return (old >> off) & 1;
105 }
106
swa_bitarray_read_then_clear(UChar * arr,UWord ix)107 static inline UWord swa_bitarray_read_then_clear ( UChar* arr, UWord ix ) {
108 UWord bix = ix >> 3;
109 UWord off = ix & 7;
110 UChar old = arr[bix];
111 UChar nyu = old & ~(1 << off);
112 arr[bix] = nyu;
113 return (old >> off) & 1;
114 }
115
116 //////// SWA helper functions (iteration)
117
swa_PUSH(SparseWA * swa,UWord partial_key,Int curr_ix,void * curr_nd,Int resume_point)118 static void swa_PUSH ( SparseWA* swa, UWord partial_key, Int curr_ix,
119 void* curr_nd, Int resume_point )
120 {
121 Int sp = swa->isUsed;
122 const Int _3_or_7 = sizeof(void*) - 1;
123 // if (0) VG_(printf)("PUSH, old sp = %d\n", sp);
124 vg_assert(sp >= 0 && sp <= _3_or_7);
125 swa->iterStack[sp].partial_key = partial_key;
126 swa->iterStack[sp].curr_ix = curr_ix;
127 swa->iterStack[sp].curr_nd = curr_nd;
128 swa->iterStack[sp].resume_point = resume_point;
129 swa->isUsed = sp+1;
130 }
131
swa_POP(SparseWA * swa,UWord * partial_key,Int * curr_ix,void ** curr_nd,Int * resume_point)132 static void swa_POP ( SparseWA* swa,
133 UWord* partial_key, Int* curr_ix,
134 void** curr_nd, Int* resume_point )
135 {
136 Int sp = swa->isUsed - 1;
137 const Int _3_or_7 = sizeof(void*) - 1;
138 // if (0) VG_(printf)("POP, old sp = %d\n", sp+1);
139 vg_assert(sp >= 0 && sp <= _3_or_7);
140 *partial_key = swa->iterStack[sp].partial_key;
141 *curr_ix = swa->iterStack[sp].curr_ix;
142 *curr_nd = swa->iterStack[sp].curr_nd;
143 *resume_point = swa->iterStack[sp].resume_point;
144 swa->isUsed = sp;
145 }
146
147 //////// SWA helper functions (allocation)
148
swa_new_LevelN(const SparseWA * swa,Int level)149 static LevelN* swa_new_LevelN ( const SparseWA* swa, Int level )
150 {
151 LevelN* levelN = swa->alloc_nofail( swa->cc, sizeof(LevelN) );
152 VG_(memset)(levelN, 0, sizeof(*levelN));
153 levelN->magic = LevelN_MAGIC;
154 levelN->level = level;
155 return levelN;
156 }
157
swa_new_Level0(const SparseWA * swa)158 static Level0* swa_new_Level0 ( const SparseWA* swa )
159 {
160 Level0* level0 = swa->alloc_nofail( swa->cc, sizeof(Level0) );
161 VG_(memset)(level0, 0, sizeof(*level0));
162 level0->magic = Level0_MAGIC;
163 return level0;
164 }
165
166
167 //////// SWA public interface
168
VG_(initIterSWA)169 void VG_(initIterSWA) ( SparseWA* swa )
170 {
171 swa->isUsed = 0;
172 if (swa->root) swa_PUSH(swa, 0, 0, swa->root, 1/*start_new_node*/);
173 }
174
175
VG_(nextIterSWA)176 Bool VG_(nextIterSWA)( SparseWA* swa,
177 /*OUT*/UWord* keyP, /*OUT*/UWord* valP )
178 {
179 UWord p_key;
180 Int curr_ix;
181 void* curr_nd;
182 Int resume_point;
183
184 /* dispatch whatever's on top of the stack; what that actually
185 means is to return to some previously-saved context. */
186 dispatch:
187
188 if (swa->isUsed == 0)
189 return False;
190
191 swa_POP(swa, &p_key, &curr_ix, &curr_nd, &resume_point);
192 switch (resume_point) {
193 case 1: goto start_new_node;
194 case 2: goto resume_leaf_node;
195 case 3: goto resume_nonleaf_node;
196 default: vg_assert(0);
197 }
198
199 start_new_node:
200 if (*(UWord*)curr_nd == Level0_MAGIC) {
201 /* curr_nd is a leaf node */
202 Level0* level0 = (Level0*)curr_nd;
203 for (curr_ix = 0; curr_ix < 256; curr_ix++) {
204 if (swa_bitarray_read(level0->inUse, curr_ix) == 1) {
205 swa_PUSH(swa, p_key, curr_ix, curr_nd, 2/*resume_leaf_node*/);
206 *keyP = (p_key << 8) + (UWord)curr_ix;
207 *valP = level0->words[curr_ix];
208 return True;
209 resume_leaf_node:
210 level0 = (Level0*)curr_nd;
211 }
212 }
213 } else {
214 /* curr_nd is a non-leaf node */
215 LevelN* levelN;
216 vg_assert(*(UWord*)curr_nd == LevelN_MAGIC);
217 levelN = (LevelN*)curr_nd;
218 for (curr_ix = 0; curr_ix < 256; curr_ix++) {
219 if (levelN->child[curr_ix]) {
220 swa_PUSH(swa, p_key, curr_ix, curr_nd, 3/*resume_nonleaf_node*/);
221 p_key = (p_key << 8) + (UWord)curr_ix;
222 curr_nd = levelN->child[curr_ix];
223 goto start_new_node;
224 resume_nonleaf_node:
225 levelN = (LevelN*)curr_nd;
226 }
227 }
228 }
229
230 goto dispatch;
231 }
232
233
VG_(newSWA)234 SparseWA* VG_(newSWA) ( void*(*alloc_nofail)(const HChar* cc, SizeT),
235 const HChar* cc,
236 void(*dealloc)(void*) )
237 {
238 SparseWA* swa;
239 vg_assert(alloc_nofail);
240 vg_assert(cc);
241 vg_assert(dealloc);
242 swa = alloc_nofail( cc, sizeof(SparseWA) );
243 VG_(memset)(swa, 0, sizeof(*swa));
244 swa->alloc_nofail = alloc_nofail;
245 swa->cc = cc;
246 swa->dealloc = dealloc;
247 swa->root = NULL;
248 return swa;
249 }
250
251
swa_deleteSWA_wrk(void (* dealloc)(void *),void * nd)252 static void swa_deleteSWA_wrk ( void(*dealloc)(void*), void* nd )
253 {
254 Int i;
255 vg_assert(nd);
256 if (*(UWord*)nd == LevelN_MAGIC) {
257 LevelN* levelN = (LevelN*)nd;
258 for (i = 0; i < 256; i++) {
259 if (levelN->child[i]) {
260 swa_deleteSWA_wrk( dealloc, levelN->child[i] );
261 }
262 }
263 } else {
264 vg_assert(*(UWord*)nd == Level0_MAGIC);
265 }
266 dealloc(nd);
267 }
VG_(deleteSWA)268 void VG_(deleteSWA) ( SparseWA* swa )
269 {
270 if (swa->root)
271 swa_deleteSWA_wrk( swa->dealloc, swa->root );
272 swa->dealloc(swa);
273 }
274
275
VG_(lookupSWA)276 Bool VG_(lookupSWA) ( const SparseWA* swa,
277 /*OUT*/UWord* valP,
278 UWord key )
279 {
280 Int i;
281 UWord ix;
282 Level0* level0;
283 LevelN* levelN;
284 const Int _3_or_7 = sizeof(void*) - 1;
285
286 vg_assert(swa);
287 levelN = swa->root;
288
289 /* levels 3/7 .. 1 */
290 for (i = _3_or_7; i >= 1; i--) {
291 if (!levelN) return False;
292 vg_assert(levelN->level == i);
293 vg_assert(levelN->nInUse > 0);
294 ix = (key >> (i*8)) & 0xFF;
295 levelN = levelN->child[ix];
296 }
297
298 /* level0 */
299 level0 = (Level0*)levelN;
300 if (!level0) return False;
301 vg_assert(level0->magic == Level0_MAGIC);
302 vg_assert(level0->nInUse > 0);
303 ix = key & 0xFF;
304 if (swa_bitarray_read(level0->inUse, ix) == 0) return False;
305 *valP = level0->words[ix];
306 return True;
307 }
308
309
VG_(addToSWA)310 Bool VG_(addToSWA) ( SparseWA* swa, UWord key, UWord val )
311 {
312 Int i;
313 UWord ix;
314 Level0* level0;
315 LevelN* levelN;
316 Bool already_present;
317 const Int _3_or_7 = sizeof(void*) - 1;
318
319 vg_assert(swa);
320
321 if (!swa->root)
322 swa->root = swa_new_LevelN(swa, _3_or_7);
323 levelN = swa->root;
324
325 /* levels 3/7 .. 2 */
326 for (i = _3_or_7; i >= 2; i--) {
327 /* levelN is the level-i map */
328 vg_assert(levelN);
329 vg_assert(levelN->level == i);
330 ix = (key >> (i*8)) & 0xFF;
331 if (levelN->child[ix] == NULL) {
332 levelN->child[ix] = swa_new_LevelN(swa, i-1);
333 levelN->nInUse++;
334 }
335 vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256);
336 levelN = levelN->child[ix];
337 }
338
339 /* levelN is the level-1 map */
340 vg_assert(levelN);
341 vg_assert(levelN->level == 1);
342 ix = (key >> (1*8)) & 0xFF;
343 if (levelN->child[ix] == NULL) {
344 levelN->child[ix] = swa_new_Level0(swa);
345 levelN->nInUse++;
346 }
347 vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256);
348 level0 = levelN->child[ix];
349
350 /* level0 is the level-0 map */
351 vg_assert(level0);
352 vg_assert(level0->magic == Level0_MAGIC);
353 ix = key & 0xFF;
354 if (swa_bitarray_read_then_set(level0->inUse, ix) == 0) {
355 level0->nInUse++;
356 already_present = False;
357 } else {
358 already_present = True;
359 }
360 vg_assert(level0->nInUse >= 1 && level0->nInUse <= 256);
361 level0->words[ix] = val;
362
363 return already_present;
364 }
365
366
VG_(delFromSWA)367 Bool VG_(delFromSWA) ( SparseWA* swa,
368 /*OUT*/UWord* oldV, UWord key )
369 {
370 Int i;
371 UWord ix;
372 Level0* level0;
373 LevelN* levelN;
374 const Int _3_or_7 = sizeof(void*) - 1;
375
376 LevelN* visited[_3_or_7];
377 UWord visitedIx[_3_or_7];
378 Int nVisited = 0;
379
380 vg_assert(swa);
381 levelN = swa->root;
382
383 /* levels 3/7 .. 1 */
384 for (i = _3_or_7; i >= 1; i--) {
385 /* level i */
386 if (!levelN) return False;
387 vg_assert(levelN->level == i);
388 vg_assert(levelN->nInUse > 0);
389 ix = (key >> (i*8)) & 0xFF;
390 visited[nVisited] = levelN;
391 visitedIx[nVisited++] = ix;
392 levelN = levelN->child[ix];
393 }
394
395 /* level 0 */
396 level0 = (Level0*)levelN;
397 if (!level0) return False;
398 vg_assert(level0->magic == Level0_MAGIC);
399 vg_assert(level0->nInUse > 0);
400 ix = key & 0xFF;
401
402 if (swa_bitarray_read_then_clear(level0->inUse, ix) == 0)
403 return False;
404
405 *oldV = level0->words[ix];
406
407 level0->nInUse--;
408 if (level0->nInUse > 0)
409 return True;
410
411 vg_assert(nVisited == _3_or_7);
412 swa->dealloc( level0 );
413
414 /* levels 1 .. 3/7 */
415 for (i = 1; i <= _3_or_7; i++) {
416 /* level i */
417 nVisited--;
418 vg_assert(visited[nVisited]->child[ visitedIx[nVisited] ]);
419 visited[nVisited]->child[ visitedIx[nVisited] ] = NULL;
420 visited[nVisited]->nInUse--;
421 vg_assert(visited[nVisited]->nInUse >= 0);
422 if (visited[nVisited]->nInUse > 0)
423 return True;
424 swa->dealloc(visited[nVisited]);
425 }
426
427 vg_assert(nVisited == 0);
428 swa->root = NULL;
429 return True;
430 }
431
432
swa_sizeSWA_wrk(const void * nd)433 static UWord swa_sizeSWA_wrk ( const void* nd )
434 {
435 Int i;
436 if (*(const UWord*)nd == LevelN_MAGIC) {
437 UWord sum = 0;
438 const LevelN* levelN = nd;
439 for (i = 0; i < 256; i++) {
440 if (levelN->child[i]) {
441 sum += swa_sizeSWA_wrk( levelN->child[i] );
442 }
443 }
444 return sum;
445 } else {
446 const Level0* level0;
447 vg_assert(*(const UWord*)nd == Level0_MAGIC);
448 level0 = nd;
449 return level0->nInUse;
450 }
451 }
VG_(sizeSWA)452 UWord VG_(sizeSWA) ( const SparseWA* swa )
453 {
454 if (swa->root)
455 return swa_sizeSWA_wrk ( swa->root );
456 else
457 return 0;
458 }
459
460
461
462 /*--------------------------------------------------------------------*/
463 /*--- end m_sparsewa.c ---*/
464 /*--------------------------------------------------------------------*/
465