/*--------------------------------------------------------------------*/
/*--- An sparse array (of words) implementation. ---*/
/*--- m_sparsewa.c ---*/
/*--------------------------------------------------------------------*/
/*
This file is part of Valgrind, a dynamic binary instrumentation
framework.
Copyright (C) 2008-2013 OpenWorks Ltd
info@open-works.co.uk
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
#include "pub_core_basics.h"
#include "pub_core_libcassert.h"
#include "pub_core_libcbase.h"
#include "pub_core_sparsewa.h" /* self */
/////////////////////////////////////////////////////////
// //
// SparseWA: Implementation //
// //
/////////////////////////////////////////////////////////
//////// SWA data structures
// (UInt) `echo "Level Zero Byte Map" | md5sum`
#define Level0_MAGIC 0x458ec222
// (UInt) `echo "Level N Byte Map" | md5sum`
#define LevelN_MAGIC 0x0a280a1a
/* It's important that the .magic field appears at offset zero in both
structs, so that we can reliably distinguish between them. */
typedef
struct {
UWord magic;
UWord words[256];
Int nInUse;
UChar inUse[256/8];
}
Level0;
typedef
struct {
UWord magic;
void* child[256]; /* either LevelN* or Level0* */
Int nInUse;
Int level; /* 3 .. 1 on 32-bit, 7 .. 1 on 64-bit */
}
LevelN;
typedef
struct {
UWord partial_key;
Int curr_ix;
void* curr_nd; /* LevelN* or Level0* */
Int resume_point; /* 1, 2 or 3 */
}
SWAStackElem;
struct _SparseWA {
void* (*alloc_nofail)(const HChar*,SizeT);
const HChar* cc;
void (*dealloc)(void*);
LevelN* root;
SWAStackElem iterStack[8];
Int isUsed;
};
//////// SWA helper functions (bitarray)
static inline UWord swa_bitarray_read ( const UChar* arr, UWord ix ) {
UWord bix = ix >> 3;
UWord off = ix & 7;
return (arr[bix] >> off) & 1;
}
static inline UWord swa_bitarray_read_then_set ( UChar* arr, UWord ix ) {
UWord bix = ix >> 3;
UWord off = ix & 7;
UChar old = arr[bix];
UChar nyu = old | (1 << off);
arr[bix] = nyu;
return (old >> off) & 1;
}
static inline UWord swa_bitarray_read_then_clear ( UChar* arr, UWord ix ) {
UWord bix = ix >> 3;
UWord off = ix & 7;
UChar old = arr[bix];
UChar nyu = old & ~(1 << off);
arr[bix] = nyu;
return (old >> off) & 1;
}
//////// SWA helper functions (iteration)
static void swa_PUSH ( SparseWA* swa, UWord partial_key, Int curr_ix,
void* curr_nd, Int resume_point )
{
Int sp = swa->isUsed;
const Int _3_or_7 = sizeof(void*) - 1;
// if (0) VG_(printf)("PUSH, old sp = %d\n", sp);
vg_assert(sp >= 0 && sp <= _3_or_7);
swa->iterStack[sp].partial_key = partial_key;
swa->iterStack[sp].curr_ix = curr_ix;
swa->iterStack[sp].curr_nd = curr_nd;
swa->iterStack[sp].resume_point = resume_point;
swa->isUsed = sp+1;
}
static void swa_POP ( SparseWA* swa,
UWord* partial_key, Int* curr_ix,
void** curr_nd, Int* resume_point )
{
Int sp = swa->isUsed - 1;
const Int _3_or_7 = sizeof(void*) - 1;
// if (0) VG_(printf)("POP, old sp = %d\n", sp+1);
vg_assert(sp >= 0 && sp <= _3_or_7);
*partial_key = swa->iterStack[sp].partial_key;
*curr_ix = swa->iterStack[sp].curr_ix;
*curr_nd = swa->iterStack[sp].curr_nd;
*resume_point = swa->iterStack[sp].resume_point;
swa->isUsed = sp;
}
//////// SWA helper functions (allocation)
static LevelN* swa_new_LevelN ( const SparseWA* swa, Int level )
{
LevelN* levelN = swa->alloc_nofail( swa->cc, sizeof(LevelN) );
VG_(memset)(levelN, 0, sizeof(*levelN));
levelN->magic = LevelN_MAGIC;
levelN->level = level;
return levelN;
}
static Level0* swa_new_Level0 ( const SparseWA* swa )
{
Level0* level0 = swa->alloc_nofail( swa->cc, sizeof(Level0) );
VG_(memset)(level0, 0, sizeof(*level0));
level0->magic = Level0_MAGIC;
return level0;
}
//////// SWA public interface
void VG_(initIterSWA) ( SparseWA* swa )
{
swa->isUsed = 0;
if (swa->root) swa_PUSH(swa, 0, 0, swa->root, 1/*start_new_node*/);
}
Bool VG_(nextIterSWA)( SparseWA* swa,
/*OUT*/UWord* keyP, /*OUT*/UWord* valP )
{
UWord p_key;
Int curr_ix;
void* curr_nd;
Int resume_point;
/* dispatch whatever's on top of the stack; what that actually
means is to return to some previously-saved context. */
dispatch:
if (swa->isUsed == 0)
return False;
swa_POP(swa, &p_key, &curr_ix, &curr_nd, &resume_point);
switch (resume_point) {
case 1: goto start_new_node;
case 2: goto resume_leaf_node;
case 3: goto resume_nonleaf_node;
default: vg_assert(0);
}
start_new_node:
if (*(UWord*)curr_nd == Level0_MAGIC) {
/* curr_nd is a leaf node */
Level0* level0 = (Level0*)curr_nd;
for (curr_ix = 0; curr_ix < 256; curr_ix++) {
if (swa_bitarray_read(level0->inUse, curr_ix) == 1) {
swa_PUSH(swa, p_key, curr_ix, curr_nd, 2/*resume_leaf_node*/);
*keyP = (p_key << 8) + (UWord)curr_ix;
*valP = level0->words[curr_ix];
return True;
resume_leaf_node:
level0 = (Level0*)curr_nd;
}
}
} else {
/* curr_nd is a non-leaf node */
LevelN* levelN;
vg_assert(*(UWord*)curr_nd == LevelN_MAGIC);
levelN = (LevelN*)curr_nd;
for (curr_ix = 0; curr_ix < 256; curr_ix++) {
if (levelN->child[curr_ix]) {
swa_PUSH(swa, p_key, curr_ix, curr_nd, 3/*resume_nonleaf_node*/);
p_key = (p_key << 8) + (UWord)curr_ix;
curr_nd = levelN->child[curr_ix];
goto start_new_node;
resume_nonleaf_node:
levelN = (LevelN*)curr_nd;
}
}
}
goto dispatch;
}
SparseWA* VG_(newSWA) ( void*(*alloc_nofail)(const HChar* cc, SizeT),
const HChar* cc,
void(*dealloc)(void*) )
{
SparseWA* swa;
vg_assert(alloc_nofail);
vg_assert(cc);
vg_assert(dealloc);
swa = alloc_nofail( cc, sizeof(SparseWA) );
VG_(memset)(swa, 0, sizeof(*swa));
swa->alloc_nofail = alloc_nofail;
swa->cc = cc;
swa->dealloc = dealloc;
swa->root = NULL;
return swa;
}
static void swa_deleteSWA_wrk ( void(*dealloc)(void*), void* nd )
{
Int i;
vg_assert(nd);
if (*(UWord*)nd == LevelN_MAGIC) {
LevelN* levelN = (LevelN*)nd;
for (i = 0; i < 256; i++) {
if (levelN->child[i]) {
swa_deleteSWA_wrk( dealloc, levelN->child[i] );
}
}
} else {
vg_assert(*(UWord*)nd == Level0_MAGIC);
}
dealloc(nd);
}
void VG_(deleteSWA) ( SparseWA* swa )
{
if (swa->root)
swa_deleteSWA_wrk( swa->dealloc, swa->root );
swa->dealloc(swa);
}
Bool VG_(lookupSWA) ( const SparseWA* swa,
/*OUT*/UWord* valP,
UWord key )
{
Int i;
UWord ix;
Level0* level0;
LevelN* levelN;
const Int _3_or_7 = sizeof(void*) - 1;
vg_assert(swa);
levelN = swa->root;
/* levels 3/7 .. 1 */
for (i = _3_or_7; i >= 1; i--) {
if (!levelN) return False;
vg_assert(levelN->level == i);
vg_assert(levelN->nInUse > 0);
ix = (key >> (i*8)) & 0xFF;
levelN = levelN->child[ix];
}
/* level0 */
level0 = (Level0*)levelN;
if (!level0) return False;
vg_assert(level0->magic == Level0_MAGIC);
vg_assert(level0->nInUse > 0);
ix = key & 0xFF;
if (swa_bitarray_read(level0->inUse, ix) == 0) return False;
*valP = level0->words[ix];
return True;
}
Bool VG_(addToSWA) ( SparseWA* swa, UWord key, UWord val )
{
Int i;
UWord ix;
Level0* level0;
LevelN* levelN;
Bool already_present;
const Int _3_or_7 = sizeof(void*) - 1;
vg_assert(swa);
if (!swa->root)
swa->root = swa_new_LevelN(swa, _3_or_7);
levelN = swa->root;
/* levels 3/7 .. 2 */
for (i = _3_or_7; i >= 2; i--) {
/* levelN is the level-i map */
vg_assert(levelN);
vg_assert(levelN->level == i);
ix = (key >> (i*8)) & 0xFF;
if (levelN->child[ix] == NULL) {
levelN->child[ix] = swa_new_LevelN(swa, i-1);
levelN->nInUse++;
}
vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256);
levelN = levelN->child[ix];
}
/* levelN is the level-1 map */
vg_assert(levelN);
vg_assert(levelN->level == 1);
ix = (key >> (1*8)) & 0xFF;
if (levelN->child[ix] == NULL) {
levelN->child[ix] = swa_new_Level0(swa);
levelN->nInUse++;
}
vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256);
level0 = levelN->child[ix];
/* level0 is the level-0 map */
vg_assert(level0);
vg_assert(level0->magic == Level0_MAGIC);
ix = key & 0xFF;
if (swa_bitarray_read_then_set(level0->inUse, ix) == 0) {
level0->nInUse++;
already_present = False;
} else {
already_present = True;
}
vg_assert(level0->nInUse >= 1 && level0->nInUse <= 256);
level0->words[ix] = val;
return already_present;
}
Bool VG_(delFromSWA) ( SparseWA* swa,
/*OUT*/UWord* oldV, UWord key )
{
Int i;
UWord ix;
Level0* level0;
LevelN* levelN;
const Int _3_or_7 = sizeof(void*) - 1;
LevelN* visited[_3_or_7];
UWord visitedIx[_3_or_7];
Int nVisited = 0;
vg_assert(swa);
levelN = swa->root;
/* levels 3/7 .. 1 */
for (i = _3_or_7; i >= 1; i--) {
/* level i */
if (!levelN) return False;
vg_assert(levelN->level == i);
vg_assert(levelN->nInUse > 0);
ix = (key >> (i*8)) & 0xFF;
visited[nVisited] = levelN;
visitedIx[nVisited++] = ix;
levelN = levelN->child[ix];
}
/* level 0 */
level0 = (Level0*)levelN;
if (!level0) return False;
vg_assert(level0->magic == Level0_MAGIC);
vg_assert(level0->nInUse > 0);
ix = key & 0xFF;
if (swa_bitarray_read_then_clear(level0->inUse, ix) == 0)
return False;
*oldV = level0->words[ix];
level0->nInUse--;
if (level0->nInUse > 0)
return True;
vg_assert(nVisited == _3_or_7);
swa->dealloc( level0 );
/* levels 1 .. 3/7 */
for (i = 1; i <= _3_or_7; i++) {
/* level i */
nVisited--;
vg_assert(visited[nVisited]->child[ visitedIx[nVisited] ]);
visited[nVisited]->child[ visitedIx[nVisited] ] = NULL;
visited[nVisited]->nInUse--;
vg_assert(visited[nVisited]->nInUse >= 0);
if (visited[nVisited]->nInUse > 0)
return True;
swa->dealloc(visited[nVisited]);
}
vg_assert(nVisited == 0);
swa->root = NULL;
return True;
}
static UWord swa_sizeSWA_wrk ( const void* nd )
{
Int i;
if (*(const UWord*)nd == LevelN_MAGIC) {
UWord sum = 0;
const LevelN* levelN = nd;
for (i = 0; i < 256; i++) {
if (levelN->child[i]) {
sum += swa_sizeSWA_wrk( levelN->child[i] );
}
}
return sum;
} else {
const Level0* level0;
vg_assert(*(const UWord*)nd == Level0_MAGIC);
level0 = nd;
return level0->nInUse;
}
}
UWord VG_(sizeSWA) ( const SparseWA* swa )
{
if (swa->root)
return swa_sizeSWA_wrk ( swa->root );
else
return 0;
}
/*--------------------------------------------------------------------*/
/*--- end m_sparsewa.c ---*/
/*--------------------------------------------------------------------*/