sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame] | 11 | Copyright (C) 2008-2017 OpenWorks Ltd |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 12 | info@open-works.co.uk |
| 13 | |
| 14 | This program is free software; you can redistribute it and/or |
| 15 | modify it under the terms of the GNU General Public License as |
| 16 | published by the Free Software Foundation; either version 2 of the |
| 17 | License, or (at your option) any later version. |
| 18 | |
| 19 | This program is distributed in the hope that it will be useful, but |
| 20 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 21 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 22 | General Public License for more details. |
| 23 | |
| 24 | You should have received a copy of the GNU General Public License |
| 25 | along with this program; if not, 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 { |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 82 | void* (*alloc_nofail)(const HChar*,SizeT); |
| 83 | const HChar* cc; |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 84 | void (*dealloc)(void*); |
| 85 | LevelN* root; |
| 86 | SWAStackElem iterStack[8]; |
| 87 | Int isUsed; |
| 88 | }; |
| 89 | |
| 90 | //////// SWA helper functions (bitarray) |
| 91 | |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 92 | static inline UWord swa_bitarray_read ( const UChar* arr, UWord ix ) { |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 149 | static LevelN* swa_new_LevelN ( const SparseWA* swa, Int level ) |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 158 | static Level0* swa_new_Level0 ( const SparseWA* swa ) |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 166 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 175 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 233 | |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 234 | SparseWA* VG_(newSWA) ( void*(*alloc_nofail)(const HChar* cc, SizeT), |
| 235 | const HChar* cc, |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 251 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | } |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 275 | |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 276 | Bool VG_(lookupSWA) ( const SparseWA* swa, |
philippe | 40648e2 | 2015-04-11 11:42:22 +0000 | [diff] [blame] | 277 | /*OUT*/UWord* valP, |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 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; |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 305 | *valP = level0->words[ix]; |
| 306 | return True; |
| 307 | } |
| 308 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 309 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 310 | Bool VG_(addToSWA) ( SparseWA* swa, UWord key, UWord val ) |
| 311 | { |
| 312 | Int i; |
| 313 | UWord ix; |
| 314 | Level0* level0; |
| 315 | LevelN* levelN; |
| 316 | Bool already_present; |
| 317 | const Int _3_or_7 = sizeof(void*) - 1; |
| 318 | |
| 319 | vg_assert(swa); |
| 320 | |
| 321 | if (!swa->root) |
| 322 | swa->root = swa_new_LevelN(swa, _3_or_7); |
| 323 | levelN = swa->root; |
| 324 | |
| 325 | /* levels 3/7 .. 2 */ |
| 326 | for (i = _3_or_7; i >= 2; i--) { |
| 327 | /* levelN is the level-i map */ |
| 328 | vg_assert(levelN); |
| 329 | vg_assert(levelN->level == i); |
| 330 | ix = (key >> (i*8)) & 0xFF; |
| 331 | if (levelN->child[ix] == NULL) { |
| 332 | levelN->child[ix] = swa_new_LevelN(swa, i-1); |
| 333 | levelN->nInUse++; |
| 334 | } |
| 335 | vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256); |
| 336 | levelN = levelN->child[ix]; |
| 337 | } |
| 338 | |
| 339 | /* levelN is the level-1 map */ |
| 340 | vg_assert(levelN); |
| 341 | vg_assert(levelN->level == 1); |
| 342 | ix = (key >> (1*8)) & 0xFF; |
| 343 | if (levelN->child[ix] == NULL) { |
| 344 | levelN->child[ix] = swa_new_Level0(swa); |
| 345 | levelN->nInUse++; |
| 346 | } |
| 347 | vg_assert(levelN->nInUse >= 1 && levelN->nInUse <= 256); |
| 348 | level0 = levelN->child[ix]; |
| 349 | |
| 350 | /* level0 is the level-0 map */ |
| 351 | vg_assert(level0); |
| 352 | vg_assert(level0->magic == Level0_MAGIC); |
| 353 | ix = key & 0xFF; |
| 354 | if (swa_bitarray_read_then_set(level0->inUse, ix) == 0) { |
| 355 | level0->nInUse++; |
| 356 | already_present = False; |
| 357 | } else { |
| 358 | already_present = True; |
| 359 | } |
| 360 | vg_assert(level0->nInUse >= 1 && level0->nInUse <= 256); |
| 361 | level0->words[ix] = val; |
| 362 | |
| 363 | return already_present; |
| 364 | } |
| 365 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 366 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 367 | Bool VG_(delFromSWA) ( SparseWA* swa, |
philippe | 40648e2 | 2015-04-11 11:42:22 +0000 | [diff] [blame] | 368 | /*OUT*/UWord* oldV, UWord key ) |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 369 | { |
| 370 | Int i; |
| 371 | UWord ix; |
| 372 | Level0* level0; |
| 373 | LevelN* levelN; |
| 374 | const Int _3_or_7 = sizeof(void*) - 1; |
| 375 | |
| 376 | LevelN* visited[_3_or_7]; |
| 377 | UWord visitedIx[_3_or_7]; |
| 378 | Int nVisited = 0; |
| 379 | |
| 380 | vg_assert(swa); |
| 381 | levelN = swa->root; |
| 382 | |
| 383 | /* levels 3/7 .. 1 */ |
| 384 | for (i = _3_or_7; i >= 1; i--) { |
| 385 | /* level i */ |
| 386 | if (!levelN) return False; |
| 387 | vg_assert(levelN->level == i); |
| 388 | vg_assert(levelN->nInUse > 0); |
| 389 | ix = (key >> (i*8)) & 0xFF; |
| 390 | visited[nVisited] = levelN; |
| 391 | visitedIx[nVisited++] = ix; |
| 392 | levelN = levelN->child[ix]; |
| 393 | } |
| 394 | |
| 395 | /* level 0 */ |
| 396 | level0 = (Level0*)levelN; |
| 397 | if (!level0) return False; |
| 398 | vg_assert(level0->magic == Level0_MAGIC); |
| 399 | vg_assert(level0->nInUse > 0); |
| 400 | ix = key & 0xFF; |
| 401 | |
| 402 | if (swa_bitarray_read_then_clear(level0->inUse, ix) == 0) |
| 403 | return False; |
| 404 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 405 | *oldV = level0->words[ix]; |
| 406 | |
| 407 | level0->nInUse--; |
| 408 | if (level0->nInUse > 0) |
| 409 | return True; |
| 410 | |
| 411 | vg_assert(nVisited == _3_or_7); |
| 412 | swa->dealloc( level0 ); |
| 413 | |
| 414 | /* levels 1 .. 3/7 */ |
| 415 | for (i = 1; i <= _3_or_7; i++) { |
| 416 | /* level i */ |
| 417 | nVisited--; |
| 418 | vg_assert(visited[nVisited]->child[ visitedIx[nVisited] ]); |
| 419 | visited[nVisited]->child[ visitedIx[nVisited] ] = NULL; |
| 420 | visited[nVisited]->nInUse--; |
| 421 | vg_assert(visited[nVisited]->nInUse >= 0); |
| 422 | if (visited[nVisited]->nInUse > 0) |
| 423 | return True; |
| 424 | swa->dealloc(visited[nVisited]); |
| 425 | } |
| 426 | |
| 427 | vg_assert(nVisited == 0); |
| 428 | swa->root = NULL; |
| 429 | return True; |
| 430 | } |
| 431 | |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 432 | |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 433 | static UWord swa_sizeSWA_wrk ( const void* nd ) |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 434 | { |
| 435 | Int i; |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 436 | if (*(const UWord*)nd == LevelN_MAGIC) { |
philippe | bcad739 | 2011-11-17 21:57:21 +0000 | [diff] [blame] | 437 | UWord sum = 0; |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 438 | const LevelN* levelN = nd; |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 439 | for (i = 0; i < 256; i++) { |
| 440 | if (levelN->child[i]) { |
| 441 | sum += swa_sizeSWA_wrk( levelN->child[i] ); |
| 442 | } |
philippe | bcad739 | 2011-11-17 21:57:21 +0000 | [diff] [blame] | 443 | } |
| 444 | return sum; |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 445 | } else { |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 446 | const Level0* level0; |
| 447 | vg_assert(*(const UWord*)nd == Level0_MAGIC); |
| 448 | level0 = nd; |
philippe | bcad739 | 2011-11-17 21:57:21 +0000 | [diff] [blame] | 449 | return level0->nInUse; |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 450 | } |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 451 | } |
florian | ee0d0e9 | 2014-10-18 16:17:13 +0000 | [diff] [blame] | 452 | UWord VG_(sizeSWA) ( const SparseWA* swa ) |
sewardj | f35dbb8 | 2008-12-06 23:34:52 +0000 | [diff] [blame] | 453 | { |
| 454 | if (swa->root) |
| 455 | return swa_sizeSWA_wrk ( swa->root ); |
| 456 | else |
| 457 | return 0; |
| 458 | } |
| 459 | |
| 460 | |
| 461 | |
sewardj | 78b7ecf | 2008-12-06 22:07:35 +0000 | [diff] [blame] | 462 | /*--------------------------------------------------------------------*/ |
| 463 | /*--- end m_sparsewa.c ---*/ |
| 464 | /*--------------------------------------------------------------------*/ |