1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- An sparse array (of words) implementation. ---*/ 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- m_sparsewa.c ---*/ 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of Valgrind, a dynamic binary instrumentation 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown framework. 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 11b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Copyright (C) 2008-2011 OpenWorks Ltd 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown info@open-works.co.uk 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_basics.h" 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcassert.h" 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcbase.h" 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_sparsewa.h" /* self */ 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////// 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// // 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// SparseWA: Implementation // 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// // 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////// 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//////// SWA data structures 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// (UInt) `echo "Level Zero Byte Map" | md5sum` 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define Level0_MAGIC 0x458ec222 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// (UInt) `echo "Level N Byte Map" | md5sum` 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define LevelN_MAGIC 0x0a280a1a 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* It's important that the .magic field appears at offset zero in both 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown structs, so that we can reliably distinguish between them. */ 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct { 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord magic; 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord words[256]; 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int nInUse; 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar inUse[256/8]; 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0; 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct { 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord magic; 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* child[256]; /* either LevelN* or Level0* */ 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int nInUse; 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int level; /* 3 .. 1 on 32-bit, 7 .. 1 on 64-bit */ 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN; 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct { 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord partial_key; 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int curr_ix; 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* curr_nd; /* LevelN* or Level0* */ 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int resume_point; /* 1, 2 or 3 */ 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SWAStackElem; 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstruct _SparseWA { 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* (*alloc_nofail)(HChar*,SizeT); 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown HChar* cc; 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*); 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* root; 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SWAStackElem iterStack[8]; 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int isUsed; 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//////// SWA helper functions (bitarray) 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline UWord swa_bitarray_read ( UChar* arr, UWord ix ) { 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord bix = ix >> 3; 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord off = ix & 7; 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (arr[bix] >> off) & 1; 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline UWord swa_bitarray_read_then_set ( UChar* arr, UWord ix ) { 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord bix = ix >> 3; 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord off = ix & 7; 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar old = arr[bix]; 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar nyu = old | (1 << off); 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown arr[bix] = nyu; 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (old >> off) & 1; 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline UWord swa_bitarray_read_then_clear ( UChar* arr, UWord ix ) { 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord bix = ix >> 3; 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord off = ix & 7; 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar old = arr[bix]; 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar nyu = old & ~(1 << off); 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown arr[bix] = nyu; 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (old >> off) & 1; 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//////// SWA helper functions (iteration) 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void swa_PUSH ( SparseWA* swa, UWord partial_key, Int curr_ix, 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* curr_nd, Int resume_point ) 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int sp = swa->isUsed; 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Int _3_or_7 = sizeof(void*) - 1; 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // if (0) VG_(printf)("PUSH, old sp = %d\n", sp); 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(sp >= 0 && sp <= _3_or_7); 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->iterStack[sp].partial_key = partial_key; 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->iterStack[sp].curr_ix = curr_ix; 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->iterStack[sp].curr_nd = curr_nd; 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->iterStack[sp].resume_point = resume_point; 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->isUsed = sp+1; 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void swa_POP ( SparseWA* swa, 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord* partial_key, Int* curr_ix, 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void** curr_nd, Int* resume_point ) 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int sp = swa->isUsed - 1; 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Int _3_or_7 = sizeof(void*) - 1; 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // if (0) VG_(printf)("POP, old sp = %d\n", sp+1); 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(sp >= 0 && sp <= _3_or_7); 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *partial_key = swa->iterStack[sp].partial_key; 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *curr_ix = swa->iterStack[sp].curr_ix; 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *curr_nd = swa->iterStack[sp].curr_nd; 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *resume_point = swa->iterStack[sp].resume_point; 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->isUsed = sp; 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//////// SWA helper functions (allocation) 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic LevelN* swa_new_LevelN ( SparseWA* swa, Int level ) 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN = swa->alloc_nofail( swa->cc, sizeof(LevelN) ); 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(levelN, 0, sizeof(*levelN)); 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN->magic = LevelN_MAGIC; 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN->level = level; 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return levelN; 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Level0* swa_new_Level0 ( SparseWA* swa ) 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0* level0 = swa->alloc_nofail( swa->cc, sizeof(Level0) ); 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(level0, 0, sizeof(*level0)); 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0->magic = Level0_MAGIC; 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return level0; 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//////// SWA public interface 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(initIterSWA) ( SparseWA* swa ) 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->isUsed = 0; 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa->root) swa_PUSH(swa, 0, 0, swa->root, 1/*start_new_node*/); 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(nextIterSWA)( SparseWA* swa, 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* keyP, /*OUT*/UWord* valP ) 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord p_key; 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int curr_ix; 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* curr_nd; 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int resume_point; 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* dispatch whatever's on top of the stack; what that actually 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown means is to return to some previously-saved context. */ 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dispatch: 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa->isUsed == 0) 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa_POP(swa, &p_key, &curr_ix, &curr_nd, &resume_point); 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch (resume_point) { 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: goto start_new_node; 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 2: goto resume_leaf_node; 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 3: goto resume_nonleaf_node; 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: vg_assert(0); 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown start_new_node: 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UWord*)curr_nd == Level0_MAGIC) { 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* curr_nd is a leaf node */ 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0* level0 = (Level0*)curr_nd; 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (curr_ix = 0; curr_ix < 256; curr_ix++) { 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa_bitarray_read(level0->inUse, curr_ix) == 1) { 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa_PUSH(swa, p_key, curr_ix, curr_nd, 2/*resume_leaf_node*/); 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *keyP = (p_key << 8) + (UWord)curr_ix; 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *valP = level0->words[curr_ix]; 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown resume_leaf_node: 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0 = (Level0*)curr_nd; 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* curr_nd is a non-leaf node */ 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN; 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(*(UWord*)curr_nd == LevelN_MAGIC); 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = (LevelN*)curr_nd; 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (curr_ix = 0; curr_ix < 256; curr_ix++) { 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (levelN->child[curr_ix]) { 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa_PUSH(swa, p_key, curr_ix, curr_nd, 3/*resume_nonleaf_node*/); 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p_key = (p_key << 8) + (UWord)curr_ix; 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown curr_nd = levelN->child[curr_ix]; 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown goto start_new_node; 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown resume_nonleaf_node: 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = (LevelN*)curr_nd; 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown goto dispatch; 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSparseWA* VG_(newSWA) ( void*(*alloc_nofail)(HChar* cc, SizeT), 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown HChar* cc, 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void(*dealloc)(void*) ) 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SparseWA* swa; 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(alloc_nofail); 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(cc); 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(dealloc); 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa = alloc_nofail( cc, sizeof(SparseWA) ); 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(swa, 0, sizeof(*swa)); 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->alloc_nofail = alloc_nofail; 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->cc = cc; 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->dealloc = dealloc; 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->root = NULL; 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return swa; 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void swa_deleteSWA_wrk ( void(*dealloc)(void*), void* nd ) 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(nd); 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UWord*)nd == LevelN_MAGIC) { 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN = (LevelN*)nd; 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < 256; i++) { 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (levelN->child[i]) { 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa_deleteSWA_wrk( dealloc, levelN->child[i] ); 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(*(UWord*)nd == Level0_MAGIC); 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dealloc(nd); 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(deleteSWA) ( SparseWA* swa ) 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa->root) 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa_deleteSWA_wrk( swa->dealloc, swa->root ); 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->dealloc(swa); 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(lookupSWA) ( SparseWA* swa, 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* keyP, /*OUT*/UWord* valP, 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key ) 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord ix; 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0* level0; 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN; 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Int _3_or_7 = sizeof(void*) - 1; 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(swa); 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = swa->root; 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* levels 3/7 .. 1 */ 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = _3_or_7; i >= 1; i--) { 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!levelN) return False; 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->level == i); 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->nInUse > 0); 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = (key >> (i*8)) & 0xFF; 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = levelN->child[ix]; 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* level0 */ 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0 = (Level0*)levelN; 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!level0) return False; 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0->magic == Level0_MAGIC); 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0->nInUse > 0); 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = key & 0xFF; 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa_bitarray_read(level0->inUse, ix) == 0) return False; 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *keyP = key; /* this is stupid. only here to make it look like WordFM */ 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *valP = level0->words[ix]; 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(addToSWA) ( SparseWA* swa, UWord key, UWord val ) 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord ix; 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0* level0; 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN; 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool already_present; 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Int _3_or_7 = sizeof(void*) - 1; 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(swa); 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!swa->root) 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->root = swa_new_LevelN(swa, _3_or_7); 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = swa->root; 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* levels 3/7 .. 2 */ 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = _3_or_7; i >= 2; i--) { 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* levelN is the level-i map */ 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN); 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->level == i); 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = (key >> (i*8)) & 0xFF; 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (levelN->child[ix] == NULL) { 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN->child[ix] = swa_new_LevelN(swa, i-1); 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN->nInUse++; 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256); 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = levelN->child[ix]; 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* levelN is the level-1 map */ 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN); 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->level == 1); 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = (key >> (1*8)) & 0xFF; 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (levelN->child[ix] == NULL) { 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN->child[ix] = swa_new_Level0(swa); 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN->nInUse++; 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256); 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0 = levelN->child[ix]; 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* level0 is the level-0 map */ 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0); 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0->magic == Level0_MAGIC); 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = key & 0xFF; 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa_bitarray_read_then_set(level0->inUse, ix) == 0) { 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0->nInUse++; 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown already_present = False; 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown already_present = True; 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0->nInUse >= 1 && level0->nInUse <= 256); 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0->words[ix] = val; 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return already_present; 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(delFromSWA) ( SparseWA* swa, 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key ) 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord ix; 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0* level0; 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN; 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Int _3_or_7 = sizeof(void*) - 1; 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* visited[_3_or_7]; 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord visitedIx[_3_or_7]; 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int nVisited = 0; 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(swa); 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = swa->root; 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* levels 3/7 .. 1 */ 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = _3_or_7; i >= 1; i--) { 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* level i */ 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!levelN) return False; 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->level == i); 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(levelN->nInUse > 0); 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = (key >> (i*8)) & 0xFF; 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown visited[nVisited] = levelN; 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown visitedIx[nVisited++] = ix; 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown levelN = levelN->child[ix]; 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* level 0 */ 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0 = (Level0*)levelN; 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!level0) return False; 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0->magic == Level0_MAGIC); 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(level0->nInUse > 0); 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ix = key & 0xFF; 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa_bitarray_read_then_clear(level0->inUse, ix) == 0) 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *oldK = key; /* this is silly */ 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *oldV = level0->words[ix]; 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0->nInUse--; 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (level0->nInUse > 0) 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 413ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(nVisited == _3_or_7); 414ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->dealloc( level0 ); 415ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 416ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* levels 1 .. 3/7 */ 417ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i <= _3_or_7; i++) { 418ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* level i */ 419ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nVisited--; 420ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(visited[nVisited]->child[ visitedIx[nVisited] ]); 421ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown visited[nVisited]->child[ visitedIx[nVisited] ] = NULL; 422ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown visited[nVisited]->nInUse--; 423ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(visited[nVisited]->nInUse >= 0); 424ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (visited[nVisited]->nInUse > 0) 425ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 426ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->dealloc(visited[nVisited]); 427ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 428ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 429ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(nVisited == 0); 430ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swa->root = NULL; 431ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 432ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 433ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 434ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 435ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UWord swa_sizeSWA_wrk ( void* nd ) 436ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 437ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 438ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord sum = 0; 439ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UWord*)nd == LevelN_MAGIC) { 440ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LevelN* levelN = (LevelN*)nd; 441ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < 256; i++) { 442ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (levelN->child[i]) { 443ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sum += swa_sizeSWA_wrk( levelN->child[i] ); 444ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 445ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 446ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 447ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Level0* level0; 448ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(*(UWord*)nd == Level0_MAGIC); 449ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown level0 = (Level0*)nd; 450ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < 256/8; i += 2) { 451ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord x = level0->inUse[i+0]; /* assume zero-extend */ 452ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord y = level0->inUse[i+1]; /* assume zero-extend */ 453ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* do 'sum += popcount(x) + popcount(y)' for byte-sized x, y */ 454ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* unroll the loop twice so as to expose more ILP */ 455ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown x = (x & 0x55) + ((x >> 1) & 0x55); 456ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown y = (y & 0x55) + ((y >> 1) & 0x55); 457ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown x = (x & 0x33) + ((x >> 2) & 0x33); 458ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown y = (y & 0x33) + ((y >> 2) & 0x33); 459ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown x = (x & 0x0F) + ((x >> 4) & 0x0F); 460ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown y = (y & 0x0F) + ((y >> 4) & 0x0F); 461ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sum += x + y; 462ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 463ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 464ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return sum; 465ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 466ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord VG_(sizeSWA) ( SparseWA* swa ) 467ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 468ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swa->root) 469ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return swa_sizeSWA_wrk ( swa->root ); 470ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 471ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 472ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 473ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 474ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 475ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 476ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 477ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- end m_sparsewa.c ---*/ 478ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 479