1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- An AVL tree based finite map for word keys and word values. ---*/ 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- Inspired by Haskell's "FiniteMap" library. ---*/ 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- m_wordfm.c ---*/ 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of Valgrind, a dynamic binary instrumentation 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown framework. 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 12436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2007-2013 Julian Seward 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown jseward@acm.org 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This code is based on previous work by Nicholas Nethercote 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (coregrind/m_oset.c) which is 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 18436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2005-2013 Nicholas Nethercote 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown njn@valgrind.org 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown which in turn was derived partially from: 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AVL C library 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Copyright (C) 2000,2002 Daniel Nagy 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown the License, or (at your option) any later version. 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown [...] 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (taken from libavl-0.4/debian/copyright) 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_basics.h" 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcassert.h" 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcbase.h" 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_wordfm.h" /* self */ 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- WordFM ---// 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- Implementation ---// 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* One element of the AVL tree */ 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _AvlNode { 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key; 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord val; 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _AvlNode* child[2]; /* [0] is left subtree, [1] is right */ 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char balance; /* do not make this unsigned */ 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode; 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct { 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord w; 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool b; 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MaybeWord; 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define WFM_STKMAX 32 // At most 2**32 entries can be iterated over 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstruct _WordFM { 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* root; 84436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov void* (*alloc_nofail)( const HChar*, SizeT ); 85436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc; 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*); 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word (*kCmp)(UWord,UWord); 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* nodeStack[WFM_STKMAX]; // Iterator node stack 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int numStack[WFM_STKMAX]; // Iterator num stack 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int stackTop; // Iterator stack pointer, one past end 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* forward */ 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(UWord,UWord)); 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Swing to the left. Warning: no balance maintainance. */ 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void avl_swl ( AvlNode** root ) 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* a = *root; 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* b = a->child[1]; 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *root = b; 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->child[1] = b->child[0]; 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b->child[0] = a; 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Swing to the right. Warning: no balance maintainance. */ 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void avl_swr ( AvlNode** root ) 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* a = *root; 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* b = a->child[0]; 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *root = b; 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->child[0] = b->child[1]; 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b->child[1] = a; 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Balance maintainance after especially nasty swings. */ 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void avl_nasty ( AvlNode* root ) 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch (root->balance) { 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->child[0]->balance = 0; 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->child[1]->balance = 1; 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->child[0]->balance = -1; 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->child[1]->balance = 0; 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->child[0]->balance = 0; 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->child[1]->balance = 0; 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(0); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown root->balance=0; 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Find size of a non-NULL tree. */ 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UWord size_avl_nonNull ( AvlNode* nd ) 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 1 + (nd->child[0] ? size_avl_nonNull(nd->child[0]) : 0) 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown + (nd->child[1] ? size_avl_nonNull(nd->child[1]) : 0); 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Unsignedly compare w1 and w2. If w1 < w2, produce a negative 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown number; if w1 > w2 produce a positive number, and if w1 == w2 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown produce zero. */ 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline Word cmp_unsigned_Words ( UWord w1, UWord w2 ) { 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (w1 < w2) return -1; 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (w1 > w2) return 1; 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Insert element a into the AVL tree t. Returns True if the depth of 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown the tree has grown. If element with that key is already present, 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown just copy a->val to existing node, first returning old ->val field 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown of existing node in *oldV, so that the caller can finalize it 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown however it wants. 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool avl_insert_wrk ( AvlNode** rootp, 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/MaybeWord* oldV, 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* a, 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word (*kCmp)(UWord,UWord) ) 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cmpres; 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* initialize */ 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->child[0] = 0; 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->child[1] = 0; 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->balance = 0; 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown oldV->b = False; 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* insert into an empty tree? */ 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!(*rootp)) { 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp) = a; 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpres = kCmp ? /*boxed*/ kCmp( (*rootp)->key, a->key ) 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : /*unboxed*/ cmp_unsigned_Words( (UWord)(*rootp)->key, 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (UWord)a->key ); 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpres > 0) { 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* insert into the left subtree */ 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->child[0]) { 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* left_subtree = (*rootp)->child[0]; 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (avl_insert_wrk(&left_subtree, oldV, a, kCmp)) { 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch ((*rootp)->balance--) { 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: return False; 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: return True; 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: break; 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: tl_assert(0); 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->child[0]->balance < 0) { 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( rootp ); 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->balance = 0; 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[1]->balance = 0; 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( &((*rootp)->child[0]) ); 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( rootp ); 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_nasty( *rootp ); 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[0] = left_subtree; 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[0] = a; 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->balance--) 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(0);/*NOTREACHED*/ 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpres < 0) { 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* insert into the right subtree */ 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->child[1]) { 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* right_subtree = (*rootp)->child[1]; 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (avl_insert_wrk(&right_subtree, oldV, a, kCmp)) { 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch((*rootp)->balance++){ 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: return False; 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: return True; 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: break; 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: tl_assert(0); 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->child[1]->balance > 0) { 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( rootp ); 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->balance = 0; 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[0]->balance = 0; 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( &((*rootp)->child[1]) ); 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( rootp ); 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_nasty( *rootp ); 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[1] = right_subtree; 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[1] = a; 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->balance++) 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(0);/*NOTREACHED*/ 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else { 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* cmpres == 0, a duplicate - replace the val, but don't 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown incorporate the node in the tree */ 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown oldV->b = True; 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown oldV->w = (*rootp)->val; 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->val = a->val; 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Remove an element a from the AVL tree t. a must be part of 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown the tree. Returns True if the depth of the tree has shrunk. 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool avl_remove_wrk ( AvlNode** rootp, 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* a, 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word(*kCmp)(UWord,UWord) ) 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool ch; 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cmpres; 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpres = kCmp ? /*boxed*/ kCmp( (*rootp)->key, a->key ) 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : /*unboxed*/ cmp_unsigned_Words( (UWord)(*rootp)->key, 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (UWord)a->key ); 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpres > 0){ 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* remove from the left subtree */ 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* left_subtree = (*rootp)->child[0]; 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(left_subtree); 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ch = avl_remove_wrk(&left_subtree, a, kCmp); 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[0]=left_subtree; 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (ch) { 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch ((*rootp)->balance++) { 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: return True; 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: return False; 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: break; 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: tl_assert(0); 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch ((*rootp)->child[1]->balance) { 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( rootp ); 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->balance = -1; 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[0]->balance = 1; 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( rootp ); 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->balance = 0; 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[0]->balance = 0; 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(0); 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( &((*rootp)->child[1]) ); 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( rootp ); 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_nasty( *rootp ); 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpres < 0) { 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* remove from the right subtree */ 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* right_subtree = (*rootp)->child[1]; 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(right_subtree); 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ch = avl_remove_wrk(&right_subtree, a, kCmp); 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[1] = right_subtree; 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (ch) { 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch ((*rootp)->balance--) { 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: return True; 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: return False; 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: break; 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: tl_assert(0); 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch ((*rootp)->child[0]->balance) { 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 0: 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( rootp ); 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->balance = 1; 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[1]->balance = -1; 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case -1: 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( rootp ); 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->balance = 0; 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp)->child[1]->balance = 0; 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(0); 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swl( &((*rootp)->child[0]) ); 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_swr( rootp ); 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_nasty( *rootp ); 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else { 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(cmpres == 0); 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert((*rootp)==a); 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return avl_removeroot_wrk(rootp, kCmp); 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Remove the root of the AVL tree *rootp. 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * Warning: dumps core if *rootp is empty 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool avl_removeroot_wrk ( AvlNode** rootp, 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word(*kCmp)(UWord,UWord) ) 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool ch; 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* a; 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!(*rootp)->child[0]) { 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!(*rootp)->child[1]) { 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp) = 0; 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp) = (*rootp)->child[1]; 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!(*rootp)->child[1]) { 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp) = (*rootp)->child[0]; 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((*rootp)->balance < 0) { 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* remove from the left subtree */ 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = (*rootp)->child[0]; 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (a->child[1]) a = a->child[1]; 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* remove from the right subtree */ 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = (*rootp)->child[1]; 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (a->child[0]) a = a->child[0]; 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ch = avl_remove_wrk(rootp, a, kCmp); 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->child[0] = (*rootp)->child[0]; 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->child[1] = (*rootp)->child[1]; 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a->balance = (*rootp)->balance; 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*rootp) = a; 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if(a->balance == 0) return ch; 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownAvlNode* avl_find_node ( AvlNode* t, Word k, Word(*kCmp)(UWord,UWord) ) 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (kCmp) { 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Boxed comparisons */ 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cmpresS; 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (t == NULL) return NULL; 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresS = kCmp(t->key, k); 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpresS > 0) t = t->child[0]; else 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpresS < 0) t = t->child[1]; else 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return t; 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Unboxed comparisons */ 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cmpresS; /* signed */ 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord cmpresU; /* unsigned */ 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (t == NULL) return NULL; /* unlikely ==> predictable */ 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresS = cmp_unsigned_Words( (UWord)t->key, (UWord)k ); 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpresS == 0) return t; /* unlikely ==> predictable */ 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresU = (UWord)cmpresS; 413ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1); 414ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown t = t->child[cmpresU]; 415ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 416ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 417ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 418ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 419ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 420ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool avl_find_bounds ( AvlNode* t, 421ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP, 422ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP, 423ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord minKey, UWord minVal, 424ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord maxKey, UWord maxVal, 425ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key, 426ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word(*kCmp)(UWord,UWord) ) 427ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 428ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord kLowerBound = minKey; 429ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord vLowerBound = minVal; 430ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord kUpperBound = maxKey; 431ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord vUpperBound = maxVal; 432ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (t) { 433ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cmpresS = kCmp ? kCmp(t->key, key) 434ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : cmp_unsigned_Words(t->key, key); 435ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpresS < 0) { 436ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown kLowerBound = t->key; 437ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vLowerBound = t->val; 438ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown t = t->child[1]; 439ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown continue; 440ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 441ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpresS > 0) { 442ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown kUpperBound = t->key; 443ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vUpperBound = t->val; 444ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown t = t->child[0]; 445ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown continue; 446ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 447ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* We should never get here. If we do, it means the given key 448ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown is actually present in the tree, which means the original 449ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown call was invalid -- an error on the caller's part, and we 450ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cannot give any meaningful values for the bounds. (Well, 451ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown maybe we could, but we're not gonna. Ner!) */ 452ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 453ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 454ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (kMinP) *kMinP = kLowerBound; 455ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vMinP) *vMinP = vLowerBound; 456ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (kMaxP) *kMaxP = kUpperBound; 457ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vMaxP) *vMaxP = vUpperBound; 458ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 459ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 460ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 461ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Clear the iterator stack. 462ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void stackClear(WordFM* fm) 463ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 464ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 465ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm); 466ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < WFM_STKMAX; i++) { 467ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->nodeStack[i] = NULL; 468ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->numStack[i] = 0; 469ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 470ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->stackTop = 0; 471ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 472ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 473ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Push onto the iterator stack. 474ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline void stackPush(WordFM* fm, AvlNode* n, Int i) 475ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 476ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm->stackTop < WFM_STKMAX); 477ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(1 <= i && i <= 3); 478ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->nodeStack[fm->stackTop] = n; 479ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm-> numStack[fm->stackTop] = i; 480ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->stackTop++; 481ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 482ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 483ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Pop from the iterator stack. 484ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline Bool stackPop(WordFM* fm, AvlNode** n, Int* i) 485ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 486ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm->stackTop <= WFM_STKMAX); 487ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 488ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (fm->stackTop > 0) { 489ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->stackTop--; 490ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *n = fm->nodeStack[fm->stackTop]; 491ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *i = fm-> numStack[fm->stackTop]; 492ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(1 <= *i && *i <= 3); 493ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->nodeStack[fm->stackTop] = NULL; 494ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm-> numStack[fm->stackTop] = 0; 495ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 496ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 497ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 498ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 499ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 500ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 501ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic 502ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownAvlNode* avl_dopy ( AvlNode* nd, 503ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord(*dopyK)(UWord), 504ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord(*dopyV)(UWord), 505436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov void*(alloc_nofail)(const HChar*,SizeT), 506436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc ) 507ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 508ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* nyu; 509ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (! nd) 510ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 511ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu = alloc_nofail(cc, sizeof(AvlNode)); 512ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(nyu); 513ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 514ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->child[0] = nd->child[0]; 515ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->child[1] = nd->child[1]; 516ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->balance = nd->balance; 517ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 518ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Copy key */ 519ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (dopyK) { 520ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->key = dopyK( nd->key ); 521ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nd->key != 0 && nyu->key == 0) 522ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; /* oom in key dcopy */ 523ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 524ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* copying assumedly unboxed keys */ 525ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->key = nd->key; 526ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 527ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 528ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Copy val */ 529ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (dopyV) { 530ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->val = dopyV( nd->val ); 531ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nd->val != 0 && nyu->val == 0) 532ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; /* oom in val dcopy */ 533ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 534ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* copying assumedly unboxed vals */ 535ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->val = nd->val; 536ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 537ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 538ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Copy subtrees */ 539ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nyu->child[0]) { 540ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->child[0] = avl_dopy( nyu->child[0], dopyK, dopyV, 541ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown alloc_nofail, cc ); 542ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (! nyu->child[0]) 543ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 544ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 545ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nyu->child[1]) { 546ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->child[1] = avl_dopy( nyu->child[1], dopyK, dopyV, 547ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown alloc_nofail, cc ); 548ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (! nyu->child[1]) 549ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 550ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 551ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 552ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return nyu; 553ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 554ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 555ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Initialise a WordFM. */ 556ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void initFM ( WordFM* fm, 557436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov void* (*alloc_nofail)( const HChar*, SizeT ), 558436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc, 559ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*), 560ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word (*kCmp)(UWord,UWord) ) 561ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 562ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->root = 0; 563ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->kCmp = kCmp; 564ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->alloc_nofail = alloc_nofail; 565ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->cc = cc; 566ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->dealloc = dealloc; 567ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->stackTop = 0; 568ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 569ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 570ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --- Public interface functions --- */ 571ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 572ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Allocate and initialise a WordFM. If kCmp is non-NULL, elements in 573ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown the set are ordered according to the ordering specified by kCmp, 574ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown which becomes obvious if you use VG_(initIterFM), 575ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over 576ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sections of the map, or the whole thing. If kCmp is NULL then the 577ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ordering used is unsigned word ordering (UWord) on the key 578ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown values. */ 579436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovWordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar*, SizeT ), 580436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc, 581ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*), 582ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word (*kCmp)(UWord,UWord) ) 583ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 584ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WordFM* fm = alloc_nofail(cc, sizeof(WordFM)); 585ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm); 586ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown initFM(fm, alloc_nofail, cc, dealloc, kCmp); 587ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return fm; 588ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 589ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 590ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void avl_free ( AvlNode* nd, 591ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void(*kFin)(UWord), 592ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void(*vFin)(UWord), 593ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void(*dealloc)(void*) ) 594ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 595ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!nd) 596ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 597ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nd->child[0]) 598ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_free(nd->child[0], kFin, vFin, dealloc); 599ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nd->child[1]) 600ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_free(nd->child[1], kFin, vFin, dealloc); 601ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (kFin) 602ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown kFin( nd->key ); 603ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (vFin) 604ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vFin( nd->val ); 605ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(nd, 0, sizeof(AvlNode)); 606ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dealloc(nd); 607ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 608ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 609ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Free up the FM. If kFin is non-NULL, it is applied to keys 610ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown before the FM is deleted; ditto with vFin for vals. */ 611ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(deleteFM) ( WordFM* fm, void(*kFin)(UWord), void(*vFin)(UWord) ) 612ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 613ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void(*dealloc)(void*) = fm->dealloc; 614ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_free( fm->root, kFin, vFin, dealloc ); 615ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(fm, 0, sizeof(WordFM) ); 616ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dealloc(fm); 617ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 618ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 619ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Add (k,v) to fm. */ 620ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(addToFM) ( WordFM* fm, UWord k, UWord v ) 621ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 622ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MaybeWord oldV; 623ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* node; 624ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown node = fm->alloc_nofail( fm->cc, sizeof(AvlNode) ); 625ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown node->key = k; 626ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown node->val = v; 627ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown oldV.b = False; 628ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown oldV.w = 0; 629ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_insert_wrk( &fm->root, &oldV, node, fm->kCmp ); 630ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown //if (oldV.b && fm->vFin) 631ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // fm->vFin( oldV.w ); 632ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (oldV.b) 633ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->dealloc(node); 634ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return oldV.b; 635ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 636ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 637ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Delete key from fm, returning associated key and val if found 638ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(delFromFM) ( WordFM* fm, 639ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key ) 640ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 641ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* node = avl_find_node( fm->root, key, fm->kCmp ); 642ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (node) { 643ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown avl_remove_wrk( &fm->root, node, fm->kCmp ); 644ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (oldK) 645ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *oldK = node->key; 646ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (oldV) 647ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *oldV = node->val; 648ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->dealloc(node); 649ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 650ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 651ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 652ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 653ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 654ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 655ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Look up in fm, assigning found key & val at spec'd addresses 656ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(lookupFM) ( WordFM* fm, 657ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key ) 658ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 659ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* node = avl_find_node( fm->root, key, fm->kCmp ); 660ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (node) { 661ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (keyP) 662ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *keyP = node->key; 663ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (valP) 664ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *valP = node->val; 665ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 666ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 667ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 668ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 669ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 670ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 671ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// See comment in pub_tool_wordfm.h for explanation 672ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(findBoundsFM)( WordFM* fm, 673ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP, 674ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP, 675ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord minKey, UWord minVal, 676ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord maxKey, UWord maxVal, 677ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key ) 678ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 679ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* really we should assert that minKey <= key <= maxKey, 680ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown where <= is as defined by fm->kCmp. */ 681ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return avl_find_bounds( fm->root, kMinP, vMinP, 682ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown kMaxP, vMaxP, 683ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown minKey, minVal, 684ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown maxKey, maxVal, 685ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown key, fm->kCmp ); 686ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 687ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 688ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// See comment in pub_tool_wordfm.h for performance warning 689ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord VG_(sizeFM) ( WordFM* fm ) 690ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 691ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Hmm, this is a bad way to do this 692ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return fm->root ? size_avl_nonNull( fm->root ) : 0; 693ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 694ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 695ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// NB UNTESTED! TEST BEFORE USE! 696ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//Bool VG_(isEmptyFM)( WordFM* fm ) 697ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//{ 698ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// return fm->root ? False : True; 699ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//} 700ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 701ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// set up FM for iteration 702ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(initIterFM) ( WordFM* fm ) 703ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 704ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm); 705ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackClear(fm); 706ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (fm->root) 707ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackPush(fm, fm->root, 1); 708ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 709ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 710ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// set up FM for iteration so that the first key subsequently produced 711ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// by VG_(nextIterFM) is the smallest key in the map >= start_at. 712ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Naturally ">=" is defined by the comparison function supplied to 713ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// VG_(newFM), as documented above. 714ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(initIterAtFM) ( WordFM* fm, UWord start_at ) 715ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 716ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 717ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode *n, *t; 718ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cmpresS; /* signed */ 719ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord cmpresU; /* unsigned */ 720ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 721ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm); 722ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackClear(fm); 723ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 724ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!fm->root) 725ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 726ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 727ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = NULL; 728ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // We need to do regular search and fill in the stack. 729ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown t = fm->root; 730ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 731ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 732ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (t == NULL) return; 733ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 734ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresS 735ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown = fm->kCmp ? /*boxed*/ fm->kCmp( t->key, start_at ) 736ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : /*unboxed*/ cmp_unsigned_Words( t->key, start_at ); 737ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 738ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cmpresS == 0) { 739ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // We found the exact key -- we are done. 740ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // The iteration should start with this node. 741ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackPush(fm, t, 2); 742ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // The stack now looks like {2, 2, ... ,2, 2} 743ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 744ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 745ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresU = (UWord)cmpresS; 746ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1); 747ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!cmpresU) { 748ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Push this node only if we go to the left child. 749ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackPush(fm, t, 2); 750ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 751ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown t = t->child[cmpresU]; 752ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 753ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (stackPop(fm, &n, &i)) { 754ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // If we've pushed something to stack and did not find the exact key, 755ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // we must fix the top element of stack. 756ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(i == 2); 757ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackPush(fm, n, 3); 758ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // the stack looks like {2, 2, ..., 2, 3} 759ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 760ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 761ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 762ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// get next key/val pair. Will tl_assert if fm has been modified 763ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// or looked up in since initIter{,At}FM was called. 764ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(nextIterFM) ( WordFM* fm, /*OUT*/UWord* pKey, /*OUT*/UWord* pVal ) 765ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 766ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i = 0; 767ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* n = NULL; 768ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 769ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm); 770ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 771ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // This in-order traversal requires each node to be pushed and popped 772ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // three times. These could be avoided by updating nodes in-situ on the 773ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // top of the stack, but the push/pop cost is so small that it's worth 774ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // keeping this loop in this simpler form. 775ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (stackPop(fm, &n, &i)) { 776ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch (i) { 777ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: case_1: 778ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackPush(fm, n, 2); 779ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* if (n->child[0]) stackPush(fm, n->child[0], 1); */ 780ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n->child[0]) { n = n->child[0]; goto case_1; } 781ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 782ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 2: 783ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown stackPush(fm, n, 3); 784ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (pKey) *pKey = n->key; 785ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (pVal) *pVal = n->val; 786ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 787ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 3: 788ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* if (n->child[1]) stackPush(fm, n->child[1], 1); */ 789ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n->child[1]) { n = n->child[1]; goto case_1; } 790ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 791ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: 792ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(0); 793ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 794ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 795ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 796ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Stack empty, iterator is exhausted, return NULL 797ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 798ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 799ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 800ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// clear the I'm iterating flag 801ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(doneIterFM) ( WordFM* fm ) 802ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 803ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 804ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 805ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordFM* VG_(dopyFM) ( WordFM* fm, UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) ) 806ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 807ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WordFM* nyu; 808ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 809ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* can't clone the fm whilst iterating on it */ 810ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(fm->stackTop == 0); 811ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 812ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu = fm->alloc_nofail( fm->cc, sizeof(WordFM) ); 813ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(nyu); 814ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 815ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *nyu = *fm; 816ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 817ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->stackTop = 0; 818ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(fm->nodeStack, 0, sizeof(fm->nodeStack)); 819ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(fm->numStack, 0, sizeof(fm->numStack)); 820ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 821ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nyu->root) { 822ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->root = avl_dopy( nyu->root, dopyK, dopyV, 823ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fm->alloc_nofail, fm->cc ); 824ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (! nyu->root) 825ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 826ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 827ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 828ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return nyu; 829ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 830ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 831ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// admin: what's the 'common' allocation size (for tree nodes?) 832ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSizeT VG_(getNodeSizeFM)( void ) 833ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 834ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return sizeof(AvlNode); 835ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 836ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 837ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 838ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- end WordFM ---// 839ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- Implementation ---// 840ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 841ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 842ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 843ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- WordBag (unboxed words only) ---// 844ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- Implementation ---// 845ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 846ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 847ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* A trivial container, to make it opaque. */ 848ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstruct _WordBag { 849ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WordFM* fm; 850ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 851ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 852436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovWordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar*, SizeT ), 853436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc, 854ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*) ) 855ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 856ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WordBag* bag = alloc_nofail(cc, sizeof(WordBag)); 857ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bag->fm = VG_(newFM)( alloc_nofail, cc, dealloc, NULL ); 858ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return bag; 859ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 860ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 861ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(deleteBag) ( WordBag* bag ) 862ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 863ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*) = bag->fm->dealloc; 864ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(deleteFM)( bag->fm, NULL, NULL ); 865ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memset)(bag, 0, sizeof(WordBag)); 866ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dealloc(bag); 867ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 868ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 869ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(addToBag)( WordBag* bag, UWord w ) 870ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 871ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key, count; 872ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(lookupFM)(bag->fm, &key, &count, w)) { 873ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(key == w); 874ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(count >= 1); 875ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(addToFM)(bag->fm, w, count+1); 876ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 877ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(addToFM)(bag->fm, w, 1); 878ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 879ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 880ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 881ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord VG_(elemBag) ( WordBag* bag, UWord w ) 882ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 883ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key, count; 884ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(lookupFM)( bag->fm, &key, &count, w)) { 885ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(key == w); 886ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(count >= 1); 887ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 888ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 889ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 890ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 891ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 892ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 893ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord VG_(sizeUniqueBag) ( WordBag* bag ) 894ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 895ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return VG_(sizeFM)( bag->fm ); 896ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 897ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 898ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UWord sizeTotalBag_wrk ( AvlNode* nd ) 899ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 900ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* unchecked pre: nd is non-NULL */ 901ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord w = nd->val; 902ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(w >= 1); 903ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nd->child[0]) 904ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown w += sizeTotalBag_wrk(nd->child[0]); 905ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nd->child[1]) 906ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown w += sizeTotalBag_wrk(nd->child[1]); 907ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return w; 908ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 909ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord VG_(sizeTotalBag)( WordBag* bag ) 910ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 911ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (bag->fm->root) 912ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return sizeTotalBag_wrk(bag->fm->root); 913ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 914ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 915ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 916ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 917ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(delFromBag)( WordBag* bag, UWord w ) 918ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 919ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UWord key, count; 920ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(lookupFM)(bag->fm, &key, &count, w)) { 921ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(key == w); 922ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(count >= 1); 923ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (count > 1) { 924ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(addToFM)(bag->fm, w, count-1); 925ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 926ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(count == 1); 927ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(delFromFM)( bag->fm, NULL, NULL, w ); 928ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 929ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 930ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 931ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 932ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 933ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 934ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 935ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(isEmptyBag)( WordBag* bag ) 936ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 937ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return VG_(sizeFM)(bag->fm) == 0; 938ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 939ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 940ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(isSingletonTotalBag)( WordBag* bag ) 941ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 942ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* nd; 943ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(sizeFM)(bag->fm) != 1) 944ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 945ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nd = bag->fm->root; 946ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(nd); 947ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(!nd->child[0]); 948ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(!nd->child[1]); 949ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return nd->val == 1; 950ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 951ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 952ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord VG_(anyElementOfBag)( WordBag* bag ) 953ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 954ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Return an arbitrarily chosen element in the bag. We might as 955ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown well return the one at the root of the underlying AVL tree. */ 956ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AvlNode* nd = bag->fm->root; 957ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(nd); /* if this fails, 'bag' is empty - caller is in error. */ 958ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tl_assert(nd->val >= 1); 959ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return nd->key; 960ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 961ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 962ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(initIterBag)( WordBag* bag ) 963ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 964ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(initIterFM)(bag->fm); 965ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 966ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 967ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(nextIterBag)( WordBag* bag, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount ) 968ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 969ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return VG_(nextIterFM)( bag->fm, pVal, pCount ); 970ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 971ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 972ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(doneIterBag)( WordBag* bag ) 973ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 974ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(doneIterFM)( bag->fm ); 975ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 976ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 977ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 978ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- end WordBag (unboxed words only) ---// 979ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- Implementation ---// 980ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 981ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 982ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 983ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- end m_wordfm.c ---*/ 984ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 985