m_sparsewa.c revision 8f943afc22a6a683b78271836c8ddc462b4824a9 
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-2011 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
54typedef
55   struct {
56      UWord magic;
57      UWord words[256];
58      Int   nInUse;
59      UChar inUse[256/8];
60   }
61   Level0;
62
63typedef
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
72typedef
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
81struct _SparseWA {
82   void*        (*alloc_nofail)(HChar*,SizeT);
83   HChar*       cc;
84   void         (*dealloc)(void*);
85   LevelN*      root;
86   SWAStackElem iterStack[8];
87   Int          isUsed;
88};
89
90//////// SWA helper functions (bitarray)
91
92static inline UWord swa_bitarray_read ( UChar* arr, UWord ix ) {
93   UWord bix = ix >> 3;
94   UWord off = ix & 7;
95   return (arr[bix] >> off) & 1;
96}
97
98static 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
107static 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
118static 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
132static 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
149static LevelN* swa_new_LevelN ( 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
158static Level0* swa_new_Level0 ( 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
169void 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
176Bool 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
234SparseWA* VG_(newSWA) ( void*(*alloc_nofail)(HChar* cc, SizeT),
235                        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
252static 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}
268void VG_(deleteSWA) ( SparseWA* swa )
269{
270   if (swa->root)
271      swa_deleteSWA_wrk( swa->dealloc, swa->root );
272   swa->dealloc(swa);
273}
274
275
276Bool VG_(lookupSWA) ( SparseWA* swa,
277                      /*OUT*/UWord* keyP, /*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   *keyP = key; /* this is stupid.  only here to make it look like WordFM */
306   *valP = level0->words[ix];
307   return True;
308}
309
310
311Bool VG_(addToSWA) ( SparseWA* swa, UWord key, UWord val )
312{
313   Int     i;
314   UWord   ix;
315   Level0* level0;
316   LevelN* levelN;
317   Bool    already_present;
318   const Int _3_or_7 = sizeof(void*) - 1;
319
320   vg_assert(swa);
321
322   if (!swa->root)
323      swa->root = swa_new_LevelN(swa, _3_or_7);
324   levelN = swa->root;
325
326   /* levels 3/7 .. 2 */
327   for (i = _3_or_7; i >= 2; i--) {
328      /* levelN is the level-i map */
329      vg_assert(levelN);
330      vg_assert(levelN->level == i);
331      ix = (key >> (i*8)) & 0xFF;
332      if (levelN->child[ix] == NULL) {
333         levelN->child[ix] = swa_new_LevelN(swa, i-1);
334         levelN->nInUse++;
335      }
336      vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256);
337      levelN = levelN->child[ix];
338   }
339
340   /* levelN is the level-1 map */
341   vg_assert(levelN);
342   vg_assert(levelN->level == 1);
343   ix = (key >> (1*8)) & 0xFF;
344   if (levelN->child[ix] == NULL) {
345      levelN->child[ix] = swa_new_Level0(swa);
346      levelN->nInUse++;
347   }
348   vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256);
349   level0 = levelN->child[ix];
350
351   /* level0 is the level-0 map */
352   vg_assert(level0);
353   vg_assert(level0->magic == Level0_MAGIC);
354   ix = key & 0xFF;
355   if (swa_bitarray_read_then_set(level0->inUse, ix) == 0) {
356      level0->nInUse++;
357      already_present = False;
358   } else {
359      already_present = True;
360   }
361   vg_assert(level0->nInUse >= 1 && level0->nInUse <= 256);
362   level0->words[ix] = val;
363
364   return already_present;
365}
366
367
368Bool VG_(delFromSWA) ( SparseWA* swa,
369                       /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key )
370{
371   Int     i;
372   UWord   ix;
373   Level0* level0;
374   LevelN* levelN;
375   const Int _3_or_7 = sizeof(void*) - 1;
376
377   LevelN* visited[_3_or_7];
378   UWord   visitedIx[_3_or_7];
379   Int     nVisited = 0;
380
381   vg_assert(swa);
382   levelN = swa->root;
383
384   /* levels 3/7 .. 1 */
385   for (i = _3_or_7; i >= 1; i--) {
386      /* level i */
387      if (!levelN) return False;
388      vg_assert(levelN->level == i);
389      vg_assert(levelN->nInUse > 0);
390      ix = (key >> (i*8)) & 0xFF;
391      visited[nVisited]     = levelN;
392      visitedIx[nVisited++] = ix;
393      levelN = levelN->child[ix];
394   }
395
396   /* level 0 */
397   level0 = (Level0*)levelN;
398   if (!level0) return False;
399   vg_assert(level0->magic == Level0_MAGIC);
400   vg_assert(level0->nInUse > 0);
401   ix = key & 0xFF;
402
403   if (swa_bitarray_read_then_clear(level0->inUse, ix) == 0)
404      return False;
405
406   *oldK = key; /* this is silly */
407   *oldV = level0->words[ix];
408
409   level0->nInUse--;
410   if (level0->nInUse > 0)
411      return True;
412
413   vg_assert(nVisited == _3_or_7);
414   swa->dealloc( level0 );
415
416   /* levels 1 .. 3/7 */
417   for (i = 1; i <= _3_or_7; i++) {
418      /* level i */
419      nVisited--;
420      vg_assert(visited[nVisited]->child[ visitedIx[nVisited] ]);
421      visited[nVisited]->child[ visitedIx[nVisited] ] = NULL;
422      visited[nVisited]->nInUse--;
423      vg_assert(visited[nVisited]->nInUse >= 0);
424      if (visited[nVisited]->nInUse > 0)
425         return True;
426      swa->dealloc(visited[nVisited]);
427   }
428
429   vg_assert(nVisited == 0);
430   swa->root = NULL;
431   return True;
432}
433
434
435static UWord swa_sizeSWA_wrk ( void* nd )
436{
437   Int   i;
438   UWord sum = 0;
439   if (*(UWord*)nd == LevelN_MAGIC) {
440      LevelN* levelN = (LevelN*)nd;
441      for (i = 0; i < 256; i++) {
442         if (levelN->child[i]) {
443            sum += swa_sizeSWA_wrk( levelN->child[i] );
444         }
445      }
446   } else {
447      Level0* level0;
448      vg_assert(*(UWord*)nd == Level0_MAGIC);
449      level0 = (Level0*)nd;
450      for (i = 0; i < 256/8; i += 2) {
451         UWord x = level0->inUse[i+0]; /* assume zero-extend */
452         UWord y = level0->inUse[i+1]; /* assume zero-extend */
453         /* do 'sum += popcount(x) + popcount(y)' for byte-sized x, y */
454         /* unroll the loop twice so as to expose more ILP */
455         x = (x & 0x55) + ((x >> 1) & 0x55);
456         y = (y & 0x55) + ((y >> 1) & 0x55);
457         x = (x & 0x33) + ((x >> 2) & 0x33);
458         y = (y & 0x33) + ((y >> 2) & 0x33);
459         x = (x & 0x0F) + ((x >> 4) & 0x0F);
460         y = (y & 0x0F) + ((y >> 4) & 0x0F);
461         sum += x + y;
462      }
463   }
464   return sum;
465}
466UWord VG_(sizeSWA) ( SparseWA* swa )
467{
468   if (swa->root)
469      return swa_sizeSWA_wrk ( swa->root );
470   else
471      return 0;
472}
473
474
475
476/*--------------------------------------------------------------------*/
477/*--- end                                             m_sparsewa.c ---*/
478/*--------------------------------------------------------------------*/
479