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