coregrind/m_sparsewa.c

   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-2013 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
  92 static 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
  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
 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
 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
 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
 149 static 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
 158 static 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
 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
 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
 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
 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 }
 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
 276 Bool 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
 311 Bool 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
 368 Bool 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
 435 static UWord swa_sizeSWA_wrk ( void* nd )
 436 {
 437    Int   i;
 438    if (*(UWord*)nd == LevelN_MAGIC) {
 439       UWord sum = 0;
 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       return sum;
 447    } else {
 448       Level0* level0;
 449       vg_assert(*(UWord*)nd == Level0_MAGIC);
 450       level0 = (Level0*)nd;
 451       return level0->nInUse;
 452    }
 453 }
 454 UWord VG_(sizeSWA) ( SparseWA* swa )
 455 {
 456    if (swa->root)
 457       return swa_sizeSWA_wrk ( swa->root );
 458    else
 459       return 0;
 460 }
 461
 462
 463
 464 /*--------------------------------------------------------------------*/
 465 /*--- end                                             m_sparsewa.c ---*/
 466 /*--------------------------------------------------------------------*/