m_sparsewa.c revision 40648e2927dae10d81b1a1b68aad750e810c83e9
178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--------------------------------------------------------------------*/ 378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--- An sparse array (of words) implementation. ---*/ 478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--- m_sparsewa.c ---*/ 578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--------------------------------------------------------------------*/ 678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/* 878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj This file is part of Valgrind, a dynamic binary instrumentation 978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj framework. 1078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 110f157ddb404bcde7815a1c5bf2d7e41c114f3d73sewardj Copyright (C) 2008-2013 OpenWorks Ltd 1278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj info@open-works.co.uk 1378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 1478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj This program is free software; you can redistribute it and/or 1578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj modify it under the terms of the GNU General Public License as 1678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj published by the Free Software Foundation; either version 2 of the 1778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj License, or (at your option) any later version. 1878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 1978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj This program is distributed in the hope that it will be useful, but 2078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj WITHOUT ANY WARRANTY; without even the implied warranty of 2178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 2278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj General Public License for more details. 2378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 2478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj You should have received a copy of the GNU General Public License 2578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj along with this program; if not, write to the Free Software 2678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 2778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 02111-1307, USA. 2878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 2978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj The GNU General Public License is contained in the file COPYING. 3078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj*/ 3178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 3278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj#include "pub_core_basics.h" 3378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj#include "pub_core_libcassert.h" 3478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj#include "pub_core_libcbase.h" 3578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj#include "pub_core_sparsewa.h" /* self */ 3678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 3778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj///////////////////////////////////////////////////////// 3878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj// // 3978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj// SparseWA: Implementation // 4078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj// // 4178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj///////////////////////////////////////////////////////// 4278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 4378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj//////// SWA data structures 4478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 4578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj// (UInt) `echo "Level Zero Byte Map" | md5sum` 4678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj#define Level0_MAGIC 0x458ec222 4778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 4878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj// (UInt) `echo "Level N Byte Map" | md5sum` 4978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj#define LevelN_MAGIC 0x0a280a1a 5078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 5178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/* It's important that the .magic field appears at offset zero in both 5278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj structs, so that we can reliably distinguish between them. */ 5378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 5478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjtypedef 5578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj struct { 5678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord magic; 5778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord words[256]; 5878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int nInUse; 5978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UChar inUse[256/8]; 6078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 6178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Level0; 6278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 6378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjtypedef 6478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj struct { 6578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord magic; 6678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void* child[256]; /* either LevelN* or Level0* */ 6778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int nInUse; 6878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int level; /* 3 .. 1 on 32-bit, 7 .. 1 on 64-bit */ 6978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 7078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN; 7178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 7278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjtypedef 7378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj struct { 7478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord partial_key; 7578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int curr_ix; 7678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void* curr_nd; /* LevelN* or Level0* */ 7778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int resume_point; /* 1, 2 or 3 */ 7878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 7978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj SWAStackElem; 8078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 8178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjstruct _SparseWA { 8254fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorian void* (*alloc_nofail)(const HChar*,SizeT); 8354fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorian const HChar* cc; 8478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void (*dealloc)(void*); 8578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* root; 8678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj SWAStackElem iterStack[8]; 8778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int isUsed; 8878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj}; 8978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 9078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj//////// SWA helper functions (bitarray) 9178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 92ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianstatic inline UWord swa_bitarray_read ( const UChar* arr, UWord ix ) { 9378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord bix = ix >> 3; 9478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord off = ix & 7; 9578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return (arr[bix] >> off) & 1; 9678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 9778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 9878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjstatic inline UWord swa_bitarray_read_then_set ( UChar* arr, UWord ix ) { 9978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord bix = ix >> 3; 10078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord off = ix & 7; 10178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UChar old = arr[bix]; 10278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UChar nyu = old | (1 << off); 10378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj arr[bix] = nyu; 10478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return (old >> off) & 1; 10578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 10678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 10778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjstatic inline UWord swa_bitarray_read_then_clear ( UChar* arr, UWord ix ) { 10878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord bix = ix >> 3; 10978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord off = ix & 7; 11078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UChar old = arr[bix]; 11178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UChar nyu = old & ~(1 << off); 11278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj arr[bix] = nyu; 11378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return (old >> off) & 1; 11478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 11578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 11678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj//////// SWA helper functions (iteration) 11778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 11878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjstatic void swa_PUSH ( SparseWA* swa, UWord partial_key, Int curr_ix, 11978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void* curr_nd, Int resume_point ) 12078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 12178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int sp = swa->isUsed; 12278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj const Int _3_or_7 = sizeof(void*) - 1; 12378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj // if (0) VG_(printf)("PUSH, old sp = %d\n", sp); 12478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(sp >= 0 && sp <= _3_or_7); 12578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->iterStack[sp].partial_key = partial_key; 12678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->iterStack[sp].curr_ix = curr_ix; 12778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->iterStack[sp].curr_nd = curr_nd; 12878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->iterStack[sp].resume_point = resume_point; 12978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->isUsed = sp+1; 13078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 13178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 13278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjstatic void swa_POP ( SparseWA* swa, 13378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord* partial_key, Int* curr_ix, 13478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void** curr_nd, Int* resume_point ) 13578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 13678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int sp = swa->isUsed - 1; 13778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj const Int _3_or_7 = sizeof(void*) - 1; 13878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj // if (0) VG_(printf)("POP, old sp = %d\n", sp+1); 13978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(sp >= 0 && sp <= _3_or_7); 14078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *partial_key = swa->iterStack[sp].partial_key; 14178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *curr_ix = swa->iterStack[sp].curr_ix; 14278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *curr_nd = swa->iterStack[sp].curr_nd; 14378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *resume_point = swa->iterStack[sp].resume_point; 14478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->isUsed = sp; 14578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 14678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 14778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj//////// SWA helper functions (allocation) 14878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 149ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianstatic LevelN* swa_new_LevelN ( const SparseWA* swa, Int level ) 15078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 15178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* levelN = swa->alloc_nofail( swa->cc, sizeof(LevelN) ); 15278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj VG_(memset)(levelN, 0, sizeof(*levelN)); 15378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN->magic = LevelN_MAGIC; 15478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN->level = level; 15578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return levelN; 15678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 15778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 158ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianstatic Level0* swa_new_Level0 ( const SparseWA* swa ) 15978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 16078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Level0* level0 = swa->alloc_nofail( swa->cc, sizeof(Level0) ); 16178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj VG_(memset)(level0, 0, sizeof(*level0)); 16278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0->magic = Level0_MAGIC; 16378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return level0; 16478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 16578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 166f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 16778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj//////// SWA public interface 16878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 16978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjvoid VG_(initIterSWA) ( SparseWA* swa ) 17078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 17178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->isUsed = 0; 17278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa->root) swa_PUSH(swa, 0, 0, swa->root, 1/*start_new_node*/); 17378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 17478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 175f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 17678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjBool VG_(nextIterSWA)( SparseWA* swa, 17778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /*OUT*/UWord* keyP, /*OUT*/UWord* valP ) 17878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 17978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord p_key; 18078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int curr_ix; 18178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void* curr_nd; 18278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int resume_point; 18378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 18478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* dispatch whatever's on top of the stack; what that actually 18578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj means is to return to some previously-saved context. */ 18678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj dispatch: 18778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 18878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa->isUsed == 0) 18978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return False; 19078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 19178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa_POP(swa, &p_key, &curr_ix, &curr_nd, &resume_point); 19278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj switch (resume_point) { 19378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj case 1: goto start_new_node; 19478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj case 2: goto resume_leaf_node; 19578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj case 3: goto resume_nonleaf_node; 19678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj default: vg_assert(0); 19778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 19878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 19978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj start_new_node: 20078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (*(UWord*)curr_nd == Level0_MAGIC) { 20178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* curr_nd is a leaf node */ 20278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Level0* level0 = (Level0*)curr_nd; 20378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (curr_ix = 0; curr_ix < 256; curr_ix++) { 20478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa_bitarray_read(level0->inUse, curr_ix) == 1) { 20578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa_PUSH(swa, p_key, curr_ix, curr_nd, 2/*resume_leaf_node*/); 20678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *keyP = (p_key << 8) + (UWord)curr_ix; 20778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *valP = level0->words[curr_ix]; 20878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return True; 20978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj resume_leaf_node: 21078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0 = (Level0*)curr_nd; 21178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 21278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 21378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } else { 21478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* curr_nd is a non-leaf node */ 21578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* levelN; 21678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(*(UWord*)curr_nd == LevelN_MAGIC); 21778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = (LevelN*)curr_nd; 21878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (curr_ix = 0; curr_ix < 256; curr_ix++) { 21978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (levelN->child[curr_ix]) { 22078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa_PUSH(swa, p_key, curr_ix, curr_nd, 3/*resume_nonleaf_node*/); 22178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj p_key = (p_key << 8) + (UWord)curr_ix; 22278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj curr_nd = levelN->child[curr_ix]; 22378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj goto start_new_node; 22478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj resume_nonleaf_node: 22578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = (LevelN*)curr_nd; 22678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 22778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 22878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 22978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 23078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj goto dispatch; 23178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 23278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 233f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 23454fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorianSparseWA* VG_(newSWA) ( void*(*alloc_nofail)(const HChar* cc, SizeT), 23554fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorian const HChar* cc, 23678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj void(*dealloc)(void*) ) 23778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 23878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj SparseWA* swa; 23978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(alloc_nofail); 24078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(cc); 24178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(dealloc); 24278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa = alloc_nofail( cc, sizeof(SparseWA) ); 24378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj VG_(memset)(swa, 0, sizeof(*swa)); 24478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->alloc_nofail = alloc_nofail; 24578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->cc = cc; 24678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->dealloc = dealloc; 24778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->root = NULL; 24878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return swa; 24978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 25078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 251f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 25278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjstatic void swa_deleteSWA_wrk ( void(*dealloc)(void*), void* nd ) 25378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 25478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int i; 25578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(nd); 25678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (*(UWord*)nd == LevelN_MAGIC) { 25778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* levelN = (LevelN*)nd; 25878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (i = 0; i < 256; i++) { 25978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (levelN->child[i]) { 26078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa_deleteSWA_wrk( dealloc, levelN->child[i] ); 26178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 26278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 26378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } else { 26478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(*(UWord*)nd == Level0_MAGIC); 26578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 26678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj dealloc(nd); 26778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 26878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjvoid VG_(deleteSWA) ( SparseWA* swa ) 26978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 27078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa->root) 27178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa_deleteSWA_wrk( swa->dealloc, swa->root ); 27278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->dealloc(swa); 27378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 27478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 275f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 276ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianBool VG_(lookupSWA) ( const SparseWA* swa, 27740648e2927dae10d81b1a1b68aad750e810c83e9philippe /*OUT*/UWord* valP, 27878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord key ) 27978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 28078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int i; 28178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord ix; 28278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Level0* level0; 28378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* levelN; 28478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj const Int _3_or_7 = sizeof(void*) - 1; 28578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 28678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(swa); 28778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = swa->root; 28878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 28978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* levels 3/7 .. 1 */ 29078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (i = _3_or_7; i >= 1; i--) { 29178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (!levelN) return False; 29278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->level == i); 29378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->nInUse > 0); 29478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = (key >> (i*8)) & 0xFF; 29578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = levelN->child[ix]; 29678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 29778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 29878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* level0 */ 29978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0 = (Level0*)levelN; 30078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (!level0) return False; 30178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0->magic == Level0_MAGIC); 30278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0->nInUse > 0); 30378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = key & 0xFF; 30478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa_bitarray_read(level0->inUse, ix) == 0) return False; 30578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *valP = level0->words[ix]; 30678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return True; 30778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 30878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 309f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 31078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjBool VG_(addToSWA) ( SparseWA* swa, UWord key, UWord val ) 31178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 31278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int i; 31378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord ix; 31478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Level0* level0; 31578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* levelN; 31678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Bool already_present; 31778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj const Int _3_or_7 = sizeof(void*) - 1; 31878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 31978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(swa); 32078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 32178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (!swa->root) 32278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->root = swa_new_LevelN(swa, _3_or_7); 32378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = swa->root; 32478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 32578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* levels 3/7 .. 2 */ 32678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (i = _3_or_7; i >= 2; i--) { 32778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* levelN is the level-i map */ 32878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN); 32978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->level == i); 33078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = (key >> (i*8)) & 0xFF; 33178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (levelN->child[ix] == NULL) { 33278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN->child[ix] = swa_new_LevelN(swa, i-1); 33378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN->nInUse++; 33478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 33578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256); 33678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = levelN->child[ix]; 33778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 33878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 33978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* levelN is the level-1 map */ 34078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN); 34178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->level == 1); 34278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = (key >> (1*8)) & 0xFF; 34378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (levelN->child[ix] == NULL) { 34478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN->child[ix] = swa_new_Level0(swa); 34578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN->nInUse++; 34678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 34778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256); 34878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0 = levelN->child[ix]; 34978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 35078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* level0 is the level-0 map */ 35178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0); 35278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0->magic == Level0_MAGIC); 35378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = key & 0xFF; 35478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa_bitarray_read_then_set(level0->inUse, ix) == 0) { 35578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0->nInUse++; 35678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj already_present = False; 35778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } else { 35878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj already_present = True; 35978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 36078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0->nInUse >= 1 && level0->nInUse <= 256); 36178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0->words[ix] = val; 36278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 36378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return already_present; 36478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 36578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 366f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 36778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardjBool VG_(delFromSWA) ( SparseWA* swa, 36840648e2927dae10d81b1a1b68aad750e810c83e9philippe /*OUT*/UWord* oldV, UWord key ) 36978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj{ 37078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int i; 37178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord ix; 37278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Level0* level0; 37378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* levelN; 37478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj const Int _3_or_7 = sizeof(void*) - 1; 37578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 37678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj LevelN* visited[_3_or_7]; 37778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj UWord visitedIx[_3_or_7]; 37878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj Int nVisited = 0; 37978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 38078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(swa); 38178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = swa->root; 38278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 38378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* levels 3/7 .. 1 */ 38478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (i = _3_or_7; i >= 1; i--) { 38578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* level i */ 38678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (!levelN) return False; 38778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->level == i); 38878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(levelN->nInUse > 0); 38978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = (key >> (i*8)) & 0xFF; 39078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj visited[nVisited] = levelN; 39178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj visitedIx[nVisited++] = ix; 39278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj levelN = levelN->child[ix]; 39378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 39478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 39578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* level 0 */ 39678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0 = (Level0*)levelN; 39778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (!level0) return False; 39878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0->magic == Level0_MAGIC); 39978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(level0->nInUse > 0); 40078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj ix = key & 0xFF; 40178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 40278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (swa_bitarray_read_then_clear(level0->inUse, ix) == 0) 40378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return False; 40478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 40578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj *oldV = level0->words[ix]; 40678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 40778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj level0->nInUse--; 40878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (level0->nInUse > 0) 40978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return True; 41078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 41178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(nVisited == _3_or_7); 41278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->dealloc( level0 ); 41378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 41478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* levels 1 .. 3/7 */ 41578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj for (i = 1; i <= _3_or_7; i++) { 41678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj /* level i */ 41778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj nVisited--; 41878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(visited[nVisited]->child[ visitedIx[nVisited] ]); 41978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj visited[nVisited]->child[ visitedIx[nVisited] ] = NULL; 42078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj visited[nVisited]->nInUse--; 42178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(visited[nVisited]->nInUse >= 0); 42278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj if (visited[nVisited]->nInUse > 0) 42378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return True; 42478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->dealloc(visited[nVisited]); 42578b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj } 42678b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 42778b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj vg_assert(nVisited == 0); 42878b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj swa->root = NULL; 42978b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj return True; 43078b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj} 43178b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj 432f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 433ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianstatic UWord swa_sizeSWA_wrk ( const void* nd ) 434f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj{ 435f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj Int i; 436ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorian if (*(const UWord*)nd == LevelN_MAGIC) { 437bcad7394b3805ace9f8d45010bf50d8591cf15fcphilippe UWord sum = 0; 438ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorian const LevelN* levelN = nd; 439f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj for (i = 0; i < 256; i++) { 440f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj if (levelN->child[i]) { 441f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj sum += swa_sizeSWA_wrk( levelN->child[i] ); 442f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj } 443bcad7394b3805ace9f8d45010bf50d8591cf15fcphilippe } 444bcad7394b3805ace9f8d45010bf50d8591cf15fcphilippe return sum; 445f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj } else { 446ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorian const Level0* level0; 447ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorian vg_assert(*(const UWord*)nd == Level0_MAGIC); 448ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorian level0 = nd; 449bcad7394b3805ace9f8d45010bf50d8591cf15fcphilippe return level0->nInUse; 450f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj } 451f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj} 452ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianUWord VG_(sizeSWA) ( const SparseWA* swa ) 453f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj{ 454f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj if (swa->root) 455f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj return swa_sizeSWA_wrk ( swa->root ); 456f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj else 457f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj return 0; 458f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj} 459f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 460f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 461f35dbb824c543c6b0b9e332f54d8d8d235564e7dsewardj 46278b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--------------------------------------------------------------------*/ 46378b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--- end m_sparsewa.c ---*/ 46478b7ecf61466941e3fdbf7d2e436c0dee59e468csewardj/*--------------------------------------------------------------------*/ 465