Home | History | Annotate | Download | only in coregrind 
      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-2010 OpenWorks Ltd
     12       info (at) 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)(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 
     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)(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 
    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    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 }
    466 UWord 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