1*16467b97STreehugger Robot// 2*16467b97STreehugger Robot// ACBTree.m 3*16467b97STreehugger Robot// ST4 4*16467b97STreehugger Robot// 5*16467b97STreehugger Robot// Created by Alan Condit on 4/18/11. 6*16467b97STreehugger Robot// Copyright 2011 Alan Condit. All rights reserved. 7*16467b97STreehugger Robot// 8*16467b97STreehugger Robot 9*16467b97STreehugger Robot#import <Foundation/Foundation.h> 10*16467b97STreehugger Robot#import "ACBTree.h" 11*16467b97STreehugger Robot#import "AMutableDictionary.h" 12*16467b97STreehugger Robot#import "RuntimeException.h" 13*16467b97STreehugger Robot 14*16467b97STreehugger Robot@class AMutableDictionary; 15*16467b97STreehugger Robot 16*16467b97STreehugger Robot@implementation ACBKey 17*16467b97STreehugger Robot 18*16467b97STreehugger Robotstatic NSInteger RECNUM = 0; 19*16467b97STreehugger Robot 20*16467b97STreehugger Robot@synthesize recnum; 21*16467b97STreehugger Robot@synthesize key; 22*16467b97STreehugger Robot 23*16467b97STreehugger Robot+ (ACBKey *)newKey 24*16467b97STreehugger Robot{ 25*16467b97STreehugger Robot return [[ACBKey alloc] init]; 26*16467b97STreehugger Robot} 27*16467b97STreehugger Robot 28*16467b97STreehugger Robot+ (ACBKey *)newKeyWithKStr:(NSString *)aKey 29*16467b97STreehugger Robot{ 30*16467b97STreehugger Robot return [[ACBKey alloc] initWithKStr:(NSString *)aKey]; 31*16467b97STreehugger Robot} 32*16467b97STreehugger Robot 33*16467b97STreehugger Robot- (id) init 34*16467b97STreehugger Robot{ 35*16467b97STreehugger Robot self =[super init]; 36*16467b97STreehugger Robot if ( self != nil ) { 37*16467b97STreehugger Robot recnum = RECNUM++; 38*16467b97STreehugger Robot } 39*16467b97STreehugger Robot return self; 40*16467b97STreehugger Robot} 41*16467b97STreehugger Robot 42*16467b97STreehugger Robot- (id) initWithKStr:(NSString *)aKey 43*16467b97STreehugger Robot{ 44*16467b97STreehugger Robot self =[super init]; 45*16467b97STreehugger Robot if ( self != nil ) { 46*16467b97STreehugger Robot NSInteger len; 47*16467b97STreehugger Robot recnum = RECNUM++; 48*16467b97STreehugger Robot key = aKey; 49*16467b97STreehugger Robot len = [aKey length]; 50*16467b97STreehugger Robot if ( len >= BTKeySize ) { 51*16467b97STreehugger Robot len = BTKeySize - 1; 52*16467b97STreehugger Robot } 53*16467b97STreehugger Robot strncpy( kstr, [aKey cStringUsingEncoding:NSASCIIStringEncoding], len); 54*16467b97STreehugger Robot kstr[len] = '\0'; 55*16467b97STreehugger Robot } 56*16467b97STreehugger Robot return self; 57*16467b97STreehugger Robot} 58*16467b97STreehugger Robot 59*16467b97STreehugger Robot- (void)dealloc 60*16467b97STreehugger Robot{ 61*16467b97STreehugger Robot#ifdef DEBUG_DEALLOC 62*16467b97STreehugger Robot NSLog( @"called dealloc in ACBKey" ); 63*16467b97STreehugger Robot#endif 64*16467b97STreehugger Robot [super dealloc]; 65*16467b97STreehugger Robot} 66*16467b97STreehugger Robot 67*16467b97STreehugger Robot- (NSString *) description 68*16467b97STreehugger Robot{ 69*16467b97STreehugger Robot return [NSString stringWithFormat:@"len =%02d\nrecnum=%04d\nkey=%@\n", [key length], recnum, key]; 70*16467b97STreehugger Robot} 71*16467b97STreehugger Robot 72*16467b97STreehugger Robot@end 73*16467b97STreehugger Robot 74*16467b97STreehugger Robot@implementation ACBTree 75*16467b97STreehugger Robot 76*16467b97STreehugger Robot@synthesize dict; 77*16467b97STreehugger Robot@synthesize lnode; 78*16467b97STreehugger Robot@synthesize rnode; 79*16467b97STreehugger Robot@synthesize keys; 80*16467b97STreehugger Robot@synthesize btNodes; 81*16467b97STreehugger Robot@synthesize lnodeid; 82*16467b97STreehugger Robot@synthesize rnodeid; 83*16467b97STreehugger Robot@synthesize nodeid; 84*16467b97STreehugger Robot@synthesize nodeType; 85*16467b97STreehugger Robot@synthesize numkeys; 86*16467b97STreehugger Robot@synthesize numrecs; 87*16467b97STreehugger Robot@synthesize updtd; 88*16467b97STreehugger Robot@synthesize keylen; 89*16467b97STreehugger Robot@synthesize kidx; 90*16467b97STreehugger Robot 91*16467b97STreehugger Robot+ (ACBTree *) newNodeWithDictionary:(AMutableDictionary *)theDict 92*16467b97STreehugger Robot{ 93*16467b97STreehugger Robot return [[ACBTree alloc] initWithDictionary:theDict]; 94*16467b97STreehugger Robot} 95*16467b97STreehugger Robot 96*16467b97STreehugger Robot- (id)initWithDictionary:(AMutableDictionary *)theDict 97*16467b97STreehugger Robot{ 98*16467b97STreehugger Robot self = [super init]; 99*16467b97STreehugger Robot if (self) { 100*16467b97STreehugger Robot // Initialization code here. 101*16467b97STreehugger Robot dict = theDict; 102*16467b97STreehugger Robot nodeid = theDict.nxt_nodeid++; 103*16467b97STreehugger Robot keys = keyArray; 104*16467b97STreehugger Robot btNodes = btNodeArray; 105*16467b97STreehugger Robot if ( nodeid == 0 ) { 106*16467b97STreehugger Robot numkeys = 0; 107*16467b97STreehugger Robot } 108*16467b97STreehugger Robot } 109*16467b97STreehugger Robot 110*16467b97STreehugger Robot return self; 111*16467b97STreehugger Robot} 112*16467b97STreehugger Robot 113*16467b97STreehugger Robot- (void)dealloc 114*16467b97STreehugger Robot{ 115*16467b97STreehugger Robot#ifdef DEBUG_DEALLOC 116*16467b97STreehugger Robot NSLog( @"called dealloc in ACBTree" ); 117*16467b97STreehugger Robot#endif 118*16467b97STreehugger Robot [super dealloc]; 119*16467b97STreehugger Robot} 120*16467b97STreehugger Robot 121*16467b97STreehugger Robot- (ACBTree *)createnode:(ACBKey *)kp 122*16467b97STreehugger Robot{ 123*16467b97STreehugger Robot ACBTree *tmp; 124*16467b97STreehugger Robot 125*16467b97STreehugger Robot tmp = [ACBTree newNodeWithDictionary:dict]; 126*16467b97STreehugger Robot tmp.nodeType = nodeType; 127*16467b97STreehugger Robot tmp.lnode = self; 128*16467b97STreehugger Robot tmp.rnode = self.rnode; 129*16467b97STreehugger Robot self.rnode = tmp; 130*16467b97STreehugger Robot //tmp.btNodes[0] = self; 131*16467b97STreehugger Robot //tmp.keys[0] = kp; 132*16467b97STreehugger Robot tmp.updtd = YES; 133*16467b97STreehugger Robot tmp.numrecs = ((nodeType == LEAF)?1:numrecs); 134*16467b97STreehugger Robot updtd = YES; 135*16467b97STreehugger Robot tmp.numkeys = 1; 136*16467b97STreehugger Robot [tmp retain]; 137*16467b97STreehugger Robot return(tmp); 138*16467b97STreehugger Robot} 139*16467b97STreehugger Robot 140*16467b97STreehugger Robot- (ACBTree *)deletekey:(NSString *)dkey 141*16467b97STreehugger Robot{ 142*16467b97STreehugger Robot ACBKey /* *del, */ *dkp; 143*16467b97STreehugger Robot ACBTree *told, *sNode; 144*16467b97STreehugger Robot BOOL mustRelease = NO; 145*16467b97STreehugger Robot 146*16467b97STreehugger Robot if ( [dkey isKindOfClass:[NSString class]] ) { 147*16467b97STreehugger Robot dkp = [ACBKey newKeyWithKStr:dkey]; 148*16467b97STreehugger Robot mustRelease = YES; 149*16467b97STreehugger Robot } 150*16467b97STreehugger Robot else if ( [dkey isKindOfClass:[ACBKey class]] ) 151*16467b97STreehugger Robot dkp = (ACBKey *)dkey; 152*16467b97STreehugger Robot else 153*16467b97STreehugger Robot @throw [IllegalArgumentException newException:[NSString stringWithFormat:@"Don't understand this key:\"%@\"", dkey]]; 154*16467b97STreehugger Robot sNode = [self search:dkp.key]; 155*16467b97STreehugger Robot if ( sNode == nil || [sNode searchnode:dkp.key match:YES] == FAILURE ) { 156*16467b97STreehugger Robot if ( mustRelease ) [dkp release]; 157*16467b97STreehugger Robot return(self); 158*16467b97STreehugger Robot } 159*16467b97STreehugger Robot told = dict.root; 160*16467b97STreehugger Robot /* del = */[self internaldelete:dkp]; 161*16467b97STreehugger Robot 162*16467b97STreehugger Robot /* check for shrink at the root */ 163*16467b97STreehugger Robot if ( numkeys == 1 && nodeType != LEAF ) { 164*16467b97STreehugger Robot told = btNodes[0]; 165*16467b97STreehugger Robot told.nodeid = 1; 166*16467b97STreehugger Robot told.updtd = YES; 167*16467b97STreehugger Robot dict.root = told; 168*16467b97STreehugger Robot } 169*16467b97STreehugger Robot#ifdef DONTUSENOMO 170*16467b97STreehugger Robot if (debug == 'd') [self printtree]; 171*16467b97STreehugger Robot#endif 172*16467b97STreehugger Robot if ( mustRelease ) [dkp release]; 173*16467b97STreehugger Robot return(told); 174*16467b97STreehugger Robot} 175*16467b97STreehugger Robot 176*16467b97STreehugger Robot/** insertKey is the insertion entry point 177*16467b97STreehugger Robot * It determines if the key exists in the tree already 178*16467b97STreehugger Robot * it calls internalInsert to determine if the key already exists in the tree, 179*16467b97STreehugger Robot * and returns the node to be updated 180*16467b97STreehugger Robot */ 181*16467b97STreehugger Robot- (ACBTree *)insertkey:(ACBKey *)kp value:(id)value 182*16467b97STreehugger Robot{ 183*16467b97STreehugger Robot ACBTree *tnew, *q; 184*16467b97STreehugger Robot NSInteger h, nodeNum; 185*16467b97STreehugger Robot 186*16467b97STreehugger Robot tnew = self; 187*16467b97STreehugger Robot q = [self internalinsert:kp value:value split:&h]; 188*16467b97STreehugger Robot /* check for growth at the root */ 189*16467b97STreehugger Robot if ( q != nil ) { 190*16467b97STreehugger Robot tnew = [[ACBTree newNodeWithDictionary:dict] retain]; 191*16467b97STreehugger Robot tnew.nodeType = BTNODE; 192*16467b97STreehugger Robot nodeNum = tnew.nodeid; 193*16467b97STreehugger Robot tnew.nodeid = 0; 194*16467b97STreehugger Robot self.nodeid = nodeNum; 195*16467b97STreehugger Robot [tnew insert:self.keys[numkeys-1] value:self index:0 split:&h]; 196*16467b97STreehugger Robot [tnew insert:q.keys[q.numkeys-1] value:q index:1 split:&h]; 197*16467b97STreehugger Robot tnew.numrecs = self.numrecs + q.numrecs; 198*16467b97STreehugger Robot tnew.lnodeid = self.nodeid; 199*16467b97STreehugger Robot tnew.rnodeid = self.rnodeid; 200*16467b97STreehugger Robot self.rnodeid = tnew.nodeid; 201*16467b97STreehugger Robot tnew.lnode = self; 202*16467b97STreehugger Robot tnew.rnode = self.rnode; 203*16467b97STreehugger Robot self.rnode = tnew; 204*16467b97STreehugger Robot /* affected by nodeid swap */ 205*16467b97STreehugger Robot // newnode.lnodeid = tnew.btNodes[0].nodeid; 206*16467b97STreehugger Robot } 207*16467b97STreehugger Robot //dict.root = t; 208*16467b97STreehugger Robot //l.reccnt++; 209*16467b97STreehugger Robot return(tnew); 210*16467b97STreehugger Robot} 211*16467b97STreehugger Robot 212*16467b97STreehugger Robot- (ACBTree *)search:(NSString *)kstr 213*16467b97STreehugger Robot{ 214*16467b97STreehugger Robot NSInteger i, ret; 215*16467b97STreehugger Robot NSInteger srchlvl = 0; 216*16467b97STreehugger Robot ACBTree *t; 217*16467b97STreehugger Robot 218*16467b97STreehugger Robot t = self; 219*16467b97STreehugger Robot if ( self.numkeys == 0 && self.nodeType == LEAF ) 220*16467b97STreehugger Robot return nil; 221*16467b97STreehugger Robot while (t != nil) { 222*16467b97STreehugger Robot for (i = 0; i < t.numkeys; i++) { 223*16467b97STreehugger Robot ret = [t.keys[i].key compare:kstr]; 224*16467b97STreehugger Robot if ( ret >= 0 ) { 225*16467b97STreehugger Robot if ( t.nodeType == LEAF ) { 226*16467b97STreehugger Robot if ( ret == 0 ) return (t); /* node containing keyentry found */ 227*16467b97STreehugger Robot else return nil; 228*16467b97STreehugger Robot } 229*16467b97STreehugger Robot else { 230*16467b97STreehugger Robot break; 231*16467b97STreehugger Robot } 232*16467b97STreehugger Robot } 233*16467b97STreehugger Robot } 234*16467b97STreehugger Robot srchlvl++; 235*16467b97STreehugger Robot if ( t.nodeType == BTNODE ) t = t.btNodes[i]; 236*16467b97STreehugger Robot else { 237*16467b97STreehugger Robot t = nil; 238*16467b97STreehugger Robot } 239*16467b97STreehugger Robot } 240*16467b97STreehugger Robot return(nil); /* entry not found */ 241*16467b97STreehugger Robot} 242*16467b97STreehugger Robot 243*16467b97STreehugger Robot/** SEARCHNODE 244*16467b97STreehugger Robot * calling parameters -- 245*16467b97STreehugger Robot * BKEY PTR for key to search for. 246*16467b97STreehugger Robot * TYPE for exact match(YES) or position(NO) 247*16467b97STreehugger Robot * returns -- i 248*16467b97STreehugger Robot * i == FAILURE when match required but does not exist. 249*16467b97STreehugger Robot * i == t.numkeys if no existing insertion branch found. 250*16467b97STreehugger Robot * otherwise i == insertion branch. 251*16467b97STreehugger Robot */ 252*16467b97STreehugger Robot- (NSInteger)searchnode:(NSString *)kstr match:(BOOL)match 253*16467b97STreehugger Robot{ 254*16467b97STreehugger Robot NSInteger i, ret; 255*16467b97STreehugger Robot for ( i = 0; i < numkeys; i++ ) { 256*16467b97STreehugger Robot ret = [keys[i].key compare:kstr]; 257*16467b97STreehugger Robot if ( ret >= 0 ) { /* key node found */ 258*16467b97STreehugger Robot if ( ret == 0 && match == NO ) { 259*16467b97STreehugger Robot return FAILURE; 260*16467b97STreehugger Robot } 261*16467b97STreehugger Robot else if ( ret > 0 && match == YES ) { 262*16467b97STreehugger Robot return FAILURE; 263*16467b97STreehugger Robot } 264*16467b97STreehugger Robot break; 265*16467b97STreehugger Robot } 266*16467b97STreehugger Robot } 267*16467b97STreehugger Robot if ( i == numkeys && match == YES ) { 268*16467b97STreehugger Robot i = FAILURE; 269*16467b97STreehugger Robot } 270*16467b97STreehugger Robot return(i); 271*16467b97STreehugger Robot} 272*16467b97STreehugger Robot 273*16467b97STreehugger Robot- (ACBKey *)internaldelete:(ACBKey *)dkp 274*16467b97STreehugger Robot{ 275*16467b97STreehugger Robot NSInteger i, nkey; 276*16467b97STreehugger Robot __strong ACBKey *del = nil; 277*16467b97STreehugger Robot ACBTree *tsb; 278*16467b97STreehugger Robot NSInteger srchlvl = 0; 279*16467b97STreehugger Robot 280*16467b97STreehugger Robot /* find deletion branch */ 281*16467b97STreehugger Robot if ( self.nodeType != LEAF ) { 282*16467b97STreehugger Robot srchlvl++; 283*16467b97STreehugger Robot /* search for end of tree */ 284*16467b97STreehugger Robot i = [self searchnode:dkp.key match:NO]; 285*16467b97STreehugger Robot del = [btNodes[i] internaldelete:dkp]; 286*16467b97STreehugger Robot srchlvl--; 287*16467b97STreehugger Robot /* if not LEAF propagate back high key */ 288*16467b97STreehugger Robot tsb = btNodes[i]; 289*16467b97STreehugger Robot nkey = tsb.numkeys - 1; 290*16467b97STreehugger Robot } 291*16467b97STreehugger Robot /*** the bottom of the tree has been reached ***/ 292*16467b97STreehugger Robot else { /* set up deletion ptrs */ 293*16467b97STreehugger Robot if ( [self delfrmnode:dkp] == SUCCESS ) { 294*16467b97STreehugger Robot if ( numkeys < BTHNODESIZE+1 ) { 295*16467b97STreehugger Robot del = dkp; 296*16467b97STreehugger Robot } 297*16467b97STreehugger Robot else { 298*16467b97STreehugger Robot del = nil; 299*16467b97STreehugger Robot } 300*16467b97STreehugger Robot dkp.recnum = nodeid; 301*16467b97STreehugger Robot return(del); 302*16467b97STreehugger Robot } 303*16467b97STreehugger Robot } 304*16467b97STreehugger Robot /*** indicate deletion to be done ***/ 305*16467b97STreehugger Robot if ( del != nil ) { 306*16467b97STreehugger Robot /*** the key in "del" has to be deleted from in present node ***/ 307*16467b97STreehugger Robot if ( btNodes[i].numkeys >= BTHNODESIZE+1 ) { 308*16467b97STreehugger Robot /* node does not need balancing */ 309*16467b97STreehugger Robot del = nil; 310*16467b97STreehugger Robot self.keys[i] = tsb.keys[nkey]; 311*16467b97STreehugger Robot } 312*16467b97STreehugger Robot else { /* node requires balancing */ 313*16467b97STreehugger Robot if ( i == 0 ) { 314*16467b97STreehugger Robot [self rotateright:0]; 315*16467b97STreehugger Robot self.btNodes[0] = tsb; 316*16467b97STreehugger Robot } else if ( i < numkeys-1 ) { /* look to the right first */ 317*16467b97STreehugger Robot if ( self.btNodes[i+1].numkeys > BTHNODESIZE+1 ) { /* carry from right */ 318*16467b97STreehugger Robot [self borrowright:i]; 319*16467b97STreehugger Robot } 320*16467b97STreehugger Robot else { /* merge present node with right node */ 321*16467b97STreehugger Robot [self mergenode:i]; 322*16467b97STreehugger Robot } 323*16467b97STreehugger Robot } 324*16467b97STreehugger Robot else { /* look to the left */ 325*16467b97STreehugger Robot if ( i > 0 ) { /* carry or merge with left node */ 326*16467b97STreehugger Robot if ( self.btNodes[i-1].numkeys > BTHNODESIZE+1 ) { /* carry from left */ 327*16467b97STreehugger Robot [self borrowleft:i]; 328*16467b97STreehugger Robot } 329*16467b97STreehugger Robot else { /*** merge present node with left node ***/ 330*16467b97STreehugger Robot i--; 331*16467b97STreehugger Robot [self mergenode:i]; 332*16467b97STreehugger Robot tsb = self.btNodes[i]; 333*16467b97STreehugger Robot } 334*16467b97STreehugger Robot } 335*16467b97STreehugger Robot } 336*16467b97STreehugger Robot self.keys[i] = tsb.keys[nkey]; 337*16467b97STreehugger Robot } 338*16467b97STreehugger Robot } 339*16467b97STreehugger Robot numrecs--; 340*16467b97STreehugger Robot updtd = TRUE; 341*16467b97STreehugger Robot return(del); 342*16467b97STreehugger Robot} 343*16467b97STreehugger Robot 344*16467b97STreehugger Robot/** Search key kp on B-tree with root t; if found increment counter. 345*16467b97STreehugger Robot * otherwise insert an item with key kp in tree. If an ACBKey 346*16467b97STreehugger Robot * emerges to be passed to a lower level, then assign it to kp; 347*16467b97STreehugger Robot * h = "tree t has become higher" 348*16467b97STreehugger Robot */ 349*16467b97STreehugger Robot- (ACBTree *) internalinsert:(ACBKey *)kp value:(id)value split:(NSInteger *)h 350*16467b97STreehugger Robot{ 351*16467b97STreehugger Robot /* search key ins on node t^; h = false */ 352*16467b97STreehugger Robot NSInteger i, ret; 353*16467b97STreehugger Robot ACBTree *q, *tmp; 354*16467b97STreehugger Robot 355*16467b97STreehugger Robot for (i = 0; i < numkeys; i++) { 356*16467b97STreehugger Robot ret = [keys[i].key compare:kp.key]; 357*16467b97STreehugger Robot if ( ret >= 0 ) { 358*16467b97STreehugger Robot if ( nodeType == LEAF && ret == 0 ) return (self); /* node containing keyentry found */ 359*16467b97STreehugger Robot break; 360*16467b97STreehugger Robot } 361*16467b97STreehugger Robot } 362*16467b97STreehugger Robot if ( nodeType == LEAF ) { /* key goes in this node */ 363*16467b97STreehugger Robot q = [self insert:kp value:value index:i split:h]; 364*16467b97STreehugger Robot } 365*16467b97STreehugger Robot else { /* nodeType == BTNODE */ 366*16467b97STreehugger Robot /* key is not on this node */ 367*16467b97STreehugger Robot q = [self.btNodes[i] internalinsert:kp value:value split:h]; 368*16467b97STreehugger Robot if ( *h ) { 369*16467b97STreehugger Robot [self insert:kp value:q index:i split:h]; 370*16467b97STreehugger Robot } 371*16467b97STreehugger Robot else { 372*16467b97STreehugger Robot self.numrecs++; 373*16467b97STreehugger Robot } 374*16467b97STreehugger Robot tmp = self.btNodes[numkeys-1]; 375*16467b97STreehugger Robot keys[numkeys-1] = tmp.keys[tmp.numkeys-1]; 376*16467b97STreehugger Robot if ( i != numkeys-1 ) { 377*16467b97STreehugger Robot tmp = self.btNodes[i]; 378*16467b97STreehugger Robot keys[i] = tmp.keys[tmp.numkeys-1]; 379*16467b97STreehugger Robot } 380*16467b97STreehugger Robot updtd = YES; 381*16467b97STreehugger Robot } /* search */ 382*16467b97STreehugger Robot return q; 383*16467b97STreehugger Robot} 384*16467b97STreehugger Robot 385*16467b97STreehugger Robot/** Do the actual insertion or split and insert 386*16467b97STreehugger Robot * insert key to the right of t.keys[hi] 387*16467b97STreehugger Robot */ 388*16467b97STreehugger Robot- (ACBTree *) insert:(ACBKey *)kp value:(id)value index:(NSInteger)hi split:(NSInteger *)h 389*16467b97STreehugger Robot{ 390*16467b97STreehugger Robot ACBTree *b; 391*16467b97STreehugger Robot 392*16467b97STreehugger Robot if ( numkeys < BTNODESIZE ) { 393*16467b97STreehugger Robot *h = NO; 394*16467b97STreehugger Robot [self rotateright:hi]; 395*16467b97STreehugger Robot keys[hi] = kp; 396*16467b97STreehugger Robot btNodes[hi] = value; 397*16467b97STreehugger Robot numrecs++; 398*16467b97STreehugger Robot numkeys++; 399*16467b97STreehugger Robot updtd = YES; 400*16467b97STreehugger Robot //[kp retain]; 401*16467b97STreehugger Robot return nil; 402*16467b97STreehugger Robot } 403*16467b97STreehugger Robot else { /* node t is full; split it and assign the emerging ACBKey to olditem */ 404*16467b97STreehugger Robot b = [self splitnode:hi]; 405*16467b97STreehugger Robot if ( hi <= BTHNODESIZE ) { /* insert key in left page */ 406*16467b97STreehugger Robot [self rotateright:hi]; 407*16467b97STreehugger Robot keys[hi] = kp; 408*16467b97STreehugger Robot btNodes[hi] = value; 409*16467b97STreehugger Robot numrecs++; 410*16467b97STreehugger Robot numkeys++; 411*16467b97STreehugger Robot } 412*16467b97STreehugger Robot else { /* insert key in right page */ 413*16467b97STreehugger Robot hi -= BTHNODESIZE; 414*16467b97STreehugger Robot if ( b.rnode == nil ) hi--; 415*16467b97STreehugger Robot [b rotateright:hi]; 416*16467b97STreehugger Robot b.keys[hi] = kp; 417*16467b97STreehugger Robot b.btNodes[hi] = value; 418*16467b97STreehugger Robot b.numrecs++; 419*16467b97STreehugger Robot b.numkeys++; 420*16467b97STreehugger Robot } 421*16467b97STreehugger Robot numkeys = b.numkeys = BTHNODESIZE+1; 422*16467b97STreehugger Robot b.updtd = updtd = YES; 423*16467b97STreehugger Robot } 424*16467b97STreehugger Robot return b; 425*16467b97STreehugger Robot} /* insert */ 426*16467b97STreehugger Robot 427*16467b97STreehugger Robot- (void)borrowleft:(NSInteger)i 428*16467b97STreehugger Robot{ 429*16467b97STreehugger Robot ACBTree *t0, *t1; 430*16467b97STreehugger Robot NSInteger nkey; 431*16467b97STreehugger Robot 432*16467b97STreehugger Robot t0 = btNodes[i]; 433*16467b97STreehugger Robot t1 = btNodes[i-1]; 434*16467b97STreehugger Robot nkey = t1.numkeys-1; 435*16467b97STreehugger Robot [t0 insinnode:t1.keys[nkey] value:t1.btNodes[nkey]]; 436*16467b97STreehugger Robot [t1 delfrmnode:t1.keys[nkey]]; 437*16467b97STreehugger Robot nkey--; 438*16467b97STreehugger Robot keys[i-1] = t1.keys[nkey]; 439*16467b97STreehugger Robot keys[i-1].recnum = t1.nodeid; 440*16467b97STreehugger Robot} 441*16467b97STreehugger Robot 442*16467b97STreehugger Robot- (void)borrowright:(NSInteger)i 443*16467b97STreehugger Robot{ 444*16467b97STreehugger Robot ACBTree *t0, *t1; 445*16467b97STreehugger Robot NSInteger nkey; 446*16467b97STreehugger Robot 447*16467b97STreehugger Robot t0 = btNodes[i]; 448*16467b97STreehugger Robot t1 = btNodes[i+1]; 449*16467b97STreehugger Robot [t0 insinnode:t1.keys[0] value:t1.btNodes[0]]; 450*16467b97STreehugger Robot [t1 delfrmnode:t1.keys[0]]; 451*16467b97STreehugger Robot nkey = t0.numkeys - 1; 452*16467b97STreehugger Robot keys[i] = t0.keys[nkey]; 453*16467b97STreehugger Robot keys[i].recnum = t0.nodeid; 454*16467b97STreehugger Robot} 455*16467b97STreehugger Robot 456*16467b97STreehugger Robot- (NSInteger)delfrmnode:(ACBKey *)ikp 457*16467b97STreehugger Robot{ 458*16467b97STreehugger Robot NSInteger j; 459*16467b97STreehugger Robot 460*16467b97STreehugger Robot j = [self searchnode:ikp.key match:YES]; 461*16467b97STreehugger Robot if (j == FAILURE) { 462*16467b97STreehugger Robot return(FAILURE); 463*16467b97STreehugger Robot } 464*16467b97STreehugger Robot ACBKey *k0 = nil; 465*16467b97STreehugger Robot ACBTree *n0 = nil; 466*16467b97STreehugger Robot if ( self.nodeType == LEAF ) { 467*16467b97STreehugger Robot k0 = self.keys[j]; 468*16467b97STreehugger Robot n0 = self.btNodes[j]; 469*16467b97STreehugger Robot } 470*16467b97STreehugger Robot [self rotateleft:j]; 471*16467b97STreehugger Robot self.numkeys--; 472*16467b97STreehugger Robot numrecs -= ((self.nodeType == LEAF)?1:btNodes[j].numrecs); 473*16467b97STreehugger Robot if ( k0 ) [k0 release]; 474*16467b97STreehugger Robot if ( n0 ) [n0 release]; 475*16467b97STreehugger Robot updtd = TRUE; 476*16467b97STreehugger Robot return(SUCCESS); 477*16467b97STreehugger Robot} 478*16467b97STreehugger Robot 479*16467b97STreehugger Robot- (NSInteger)insinnode:(ACBKey *)ikp value:(id)value 480*16467b97STreehugger Robot{ 481*16467b97STreehugger Robot NSInteger j; 482*16467b97STreehugger Robot 483*16467b97STreehugger Robot j = [self searchnode:ikp.key match:NO]; 484*16467b97STreehugger Robot [self rotateright:j]; 485*16467b97STreehugger Robot keys[j] = ikp; 486*16467b97STreehugger Robot btNodes[j] = value; 487*16467b97STreehugger Robot numkeys++; 488*16467b97STreehugger Robot if ( nodeType == LEAF ) { 489*16467b97STreehugger Robot numrecs++; 490*16467b97STreehugger Robot } 491*16467b97STreehugger Robot else { 492*16467b97STreehugger Robot numrecs += btNodes[j].numrecs; 493*16467b97STreehugger Robot } 494*16467b97STreehugger Robot updtd = TRUE; 495*16467b97STreehugger Robot return(j); 496*16467b97STreehugger Robot} 497*16467b97STreehugger Robot 498*16467b97STreehugger Robot- (void)mergenode:(NSInteger)i 499*16467b97STreehugger Robot{ 500*16467b97STreehugger Robot ACBTree *t0, *t1, *tr; 501*16467b97STreehugger Robot NSInteger j, k, nkeys; 502*16467b97STreehugger Robot 503*16467b97STreehugger Robot t0 = btNodes[i]; 504*16467b97STreehugger Robot t1 = btNodes[i+1]; 505*16467b97STreehugger Robot /*** move keys and pointers from 506*16467b97STreehugger Robot t1 node to t0 node ***/ 507*16467b97STreehugger Robot for (j=t0.numkeys, k=0; j < BTNODESIZE && k < t1.numkeys; j++, k++) { 508*16467b97STreehugger Robot t0.keys[j] = t1.keys[k]; 509*16467b97STreehugger Robot t0.btNodes[j] = t1.btNodes[k]; 510*16467b97STreehugger Robot t0.numkeys++; 511*16467b97STreehugger Robot } 512*16467b97STreehugger Robot t0.numrecs += t1.numrecs; 513*16467b97STreehugger Robot t0.rnode = t1.rnode; 514*16467b97STreehugger Robot t0.rnodeid = t1.rnodeid; 515*16467b97STreehugger Robot t0.updtd = YES; 516*16467b97STreehugger Robot nkeys = t0.numkeys - 1; 517*16467b97STreehugger Robot keys[i] = t0.keys[nkeys]; /* update key to point to new high key */ 518*16467b97STreehugger Robot [self rotateleft:i+1]; /* copy over the keys and nodes */ 519*16467b97STreehugger Robot 520*16467b97STreehugger Robot t1.nodeType = -1; 521*16467b97STreehugger Robot if (t1.rnodeid != 0xffff && i < numkeys - 2) { 522*16467b97STreehugger Robot tr = btNodes[i+1]; 523*16467b97STreehugger Robot tr.lnodeid = t0.nodeid; 524*16467b97STreehugger Robot tr.lnode = t0; 525*16467b97STreehugger Robot tr.updtd = YES; 526*16467b97STreehugger Robot } 527*16467b97STreehugger Robot self.numkeys--; 528*16467b97STreehugger Robot updtd = YES; 529*16467b97STreehugger Robot} 530*16467b97STreehugger Robot 531*16467b97STreehugger Robot- (ACBTree *)splitnode:(NSInteger)idx 532*16467b97STreehugger Robot{ 533*16467b97STreehugger Robot ACBTree *t1; 534*16467b97STreehugger Robot NSInteger j, k; 535*16467b97STreehugger Robot 536*16467b97STreehugger Robot k = (idx <= BTHNODESIZE) ? BTHNODESIZE : BTHNODESIZE+1; 537*16467b97STreehugger Robot /*** create new node ***/ 538*16467b97STreehugger Robot // checknode(l, t, k); 539*16467b97STreehugger Robot t1 = [ACBTree newNodeWithDictionary:dict]; 540*16467b97STreehugger Robot t1.nodeType = nodeType; 541*16467b97STreehugger Robot t1.rnode = self.rnode; 542*16467b97STreehugger Robot self.rnode = t1; 543*16467b97STreehugger Robot t1.lnode = self; 544*16467b97STreehugger Robot self.updtd = t1.updtd = YES; 545*16467b97STreehugger Robot /*** move keys and pointers ***/ 546*16467b97STreehugger Robot NSInteger i = 0; 547*16467b97STreehugger Robot for (j = k; j < BTNODESIZE; j++, i++ ) { 548*16467b97STreehugger Robot t1.keys[i] = keys[j]; 549*16467b97STreehugger Robot t1.btNodes[i] = btNodes[j]; 550*16467b97STreehugger Robot t1.numrecs += ((nodeType == LEAF) ? 1 : btNodes[j].numrecs); 551*16467b97STreehugger Robot numrecs -= ((nodeType == LEAF) ? 1 : btNodes[j].numrecs); 552*16467b97STreehugger Robot keys[j] = nil; 553*16467b97STreehugger Robot btNodes[j] = nil; 554*16467b97STreehugger Robot } 555*16467b97STreehugger Robot t1.numkeys = BTNODESIZE-k; 556*16467b97STreehugger Robot self.numkeys = k; 557*16467b97STreehugger Robot return(t1); 558*16467b97STreehugger Robot} 559*16467b97STreehugger Robot 560*16467b97STreehugger Robot#ifdef DONTUSENOMO 561*16467b97STreehugger Robotfreetree(l, t) 562*16467b97STreehugger RobotFIDB *l; 563*16467b97STreehugger RobotACBTree *t; 564*16467b97STreehugger Robot{ 565*16467b97STreehugger Robot ACBTree *tmp; 566*16467b97STreehugger Robot NSInteger i; 567*16467b97STreehugger Robot 568*16467b97STreehugger Robot if (dict.root == nil) return(SUCCESS); 569*16467b97STreehugger Robot if (t.nodeid == 1) { 570*16467b97STreehugger Robot srchlvl = 0; 571*16467b97STreehugger Robot } 572*16467b97STreehugger Robot else srchlvl++; 573*16467b97STreehugger Robot for (i = 0; i < t.numkeys; i++) { 574*16467b97STreehugger Robot tmp = t.btNodes[i]; 575*16467b97STreehugger Robot if (tmp != nil) { 576*16467b97STreehugger Robot if (tmp.nodeType == LEAF) { 577*16467b97STreehugger Robot free(tmp); /* free the leaf */ 578*16467b97STreehugger Robot if (tmp == l.rrnode) { 579*16467b97STreehugger Robot l.rrnode = nil; 580*16467b97STreehugger Robot } 581*16467b97STreehugger Robot t.btNodes[i] = nil; 582*16467b97STreehugger Robot l.chknode.nods_inuse--; 583*16467b97STreehugger Robot /* putpage(l, l.chknode, 0); 584*16467b97STreehugger Robot */ 585*16467b97STreehugger Robot } 586*16467b97STreehugger Robot else { 587*16467b97STreehugger Robot freetree(l, tmp); /* continue up the tree */ 588*16467b97STreehugger Robot srchlvl--; /* decrement the srchlvl on return */ 589*16467b97STreehugger Robot } 590*16467b97STreehugger Robot } 591*16467b97STreehugger Robot } 592*16467b97STreehugger Robot free(t); /* free the node entered with */ 593*16467b97STreehugger Robot if (t == l.rrnode) { 594*16467b97STreehugger Robot l.rrnode = nil; 595*16467b97STreehugger Robot } 596*16467b97STreehugger Robot l.chknode.nods_inuse--; 597*16467b97STreehugger Robot /* putpage(l, l.chknode, 0); 598*16467b97STreehugger Robot */ 599*16467b97STreehugger Robot t = nil; 600*16467b97STreehugger Robot} 601*16467b97STreehugger Robot 602*16467b97STreehugger Robot- (void) notfound:(ACBKey *)kp 603*16467b97STreehugger Robot{ 604*16467b97STreehugger Robot /* error routine to perform if entry was expected and not found */ 605*16467b97STreehugger Robot} 606*16467b97STreehugger Robot 607*16467b97STreehugger Robot- (void)printtree:(ACBTree *)t 608*16467b97STreehugger Robot{ 609*16467b97STreehugger Robot BYTE *str; 610*16467b97STreehugger Robot NSInteger i, j; 611*16467b97STreehugger Robot NSUInteger *pdate, *ptime; 612*16467b97STreehugger Robot 613*16467b97STreehugger Robot syslst = stdprn; 614*16467b97STreehugger Robot if ( t.nodeid == 1 ) { 615*16467b97STreehugger Robot srchlvl = 0; 616*16467b97STreehugger Robot } 617*16467b97STreehugger Robot else srchlvl++; 618*16467b97STreehugger Robot for (j = 0; j < t.numkeys; j++) { 619*16467b97STreehugger Robot checknode(l, t, j); 620*16467b97STreehugger Robot if ( t.btNodes[j] != nil ) [self printtree:t.btNodes[j]]; 621*16467b97STreehugger Robot } 622*16467b97STreehugger Robot NSLog(@"Nodeid = %d, nodeType = %s, numkeys = %d, numrecs = %d\n", 623*16467b97STreehugger Robot t.nodeid, (t.nodeType == BTNODE)?@"NODE":@"LEAF", t.numkeys, t.numrecs); 624*16467b97STreehugger Robot NSLog(@"Left nodeid = %d, Right nodeid = %d\n", t.lnodeid, t.rnodeid); 625*16467b97STreehugger Robot for (i = 0; i < t.numkeys; i++) { 626*16467b97STreehugger Robot NSLog(@" t.keys[%d] recnum = %d, keyval = %@", 627*16467b97STreehugger Robot i, t.keys[i].recnum, t.keys[i]); 628*16467b97STreehugger Robot str = t.keys[i].kstr; 629*16467b97STreehugger Robot pdate = (NSUInteger *) (str + 6); 630*16467b97STreehugger Robot ptime = (NSUInteger *) (str + 8); 631*16467b97STreehugger Robot NSLog(@" date = %04.4x, time = %04.4x\n", 632*16467b97STreehugger Robot *pdate, *ptime); 633*16467b97STreehugger Robot } 634*16467b97STreehugger Robot} 635*16467b97STreehugger Robot 636*16467b97STreehugger Robot- (BOOL)puttree:(ACBTree *)t 637*16467b97STreehugger Robot{ 638*16467b97STreehugger Robot NSInteger i; 639*16467b97STreehugger Robot if (t.nodeType != LEAF) { 640*16467b97STreehugger Robot for (i = 0; i < t.numkeys; i++) { 641*16467b97STreehugger Robot if ( t.btNodes[i] != nil ) puttree(l, t.btNodes[i]); 642*16467b97STreehugger Robot } 643*16467b97STreehugger Robot } 644*16467b97STreehugger Robot if ( t.updtd ) { 645*16467b97STreehugger Robot putnode(l, t, t.nodeid); 646*16467b97STreehugger Robot return(YES); 647*16467b97STreehugger Robot } 648*16467b97STreehugger Robot return(NO); 649*16467b97STreehugger Robot} 650*16467b97STreehugger Robot 651*16467b97STreehugger Robot#endif 652*16467b97STreehugger Robot 653*16467b97STreehugger Robot/** ROTATELEFT -- rotate keys from right to the left 654*16467b97STreehugger Robot * starting at position j 655*16467b97STreehugger Robot */ 656*16467b97STreehugger Robot- (void)rotateleft:(NSInteger)j 657*16467b97STreehugger Robot{ 658*16467b97STreehugger Robot while ( j+1 < numkeys ) { 659*16467b97STreehugger Robot keys[j] = keys[j+1]; 660*16467b97STreehugger Robot btNodes[j] = btNodes[j+1]; 661*16467b97STreehugger Robot j++; 662*16467b97STreehugger Robot } 663*16467b97STreehugger Robot} 664*16467b97STreehugger Robot 665*16467b97STreehugger Robot/** ROTATERIGHT -- rotate keys to the right by 1 position 666*16467b97STreehugger Robot * starting at the last key down to position j. 667*16467b97STreehugger Robot */ 668*16467b97STreehugger Robot- (void)rotateright:(NSInteger)j 669*16467b97STreehugger Robot{ 670*16467b97STreehugger Robot NSInteger k; 671*16467b97STreehugger Robot 672*16467b97STreehugger Robot for ( k = numkeys; k > j; k-- ) { 673*16467b97STreehugger Robot keys[k] = keys[k-1]; 674*16467b97STreehugger Robot btNodes[k] = btNodes[k-1]; 675*16467b97STreehugger Robot } 676*16467b97STreehugger Robot keys[j] = nil; 677*16467b97STreehugger Robot btNodes[j] = nil; 678*16467b97STreehugger Robot} 679*16467b97STreehugger Robot 680*16467b97STreehugger Robot- (NSInteger) keyWalkLeaves 681*16467b97STreehugger Robot{ 682*16467b97STreehugger Robot NSInteger i, idx = 0; 683*16467b97STreehugger Robot NSInteger keycnt; 684*16467b97STreehugger Robot ACBTree *t; 685*16467b97STreehugger Robot 686*16467b97STreehugger Robot if ( self != dict.root ) { 687*16467b97STreehugger Robot return 0; // maybe I need to throw an exception here 688*16467b97STreehugger Robot } 689*16467b97STreehugger Robot t = self; 690*16467b97STreehugger Robot self.dict.data = [[NSMutableData dataWithLength:(numkeys * sizeof(id))] retain]; 691*16467b97STreehugger Robot self.dict.ptrBuffer = [self.dict.data mutableBytes]; 692*16467b97STreehugger Robot while ( t != nil && t.nodeType != LEAF ) { 693*16467b97STreehugger Robot t = t.btNodes[0]; 694*16467b97STreehugger Robot } 695*16467b97STreehugger Robot do { 696*16467b97STreehugger Robot keycnt = t.numkeys; 697*16467b97STreehugger Robot for ( i = 0; i < keycnt; i++ ) { 698*16467b97STreehugger Robot if ( t.btNodes[i] != nil ) { 699*16467b97STreehugger Robot dict.ptrBuffer[idx++] = (id) t.keys[i].key; 700*16467b97STreehugger Robot } 701*16467b97STreehugger Robot } 702*16467b97STreehugger Robot t = t.rnode; 703*16467b97STreehugger Robot } while ( t != nil ); 704*16467b97STreehugger Robot return( idx ); 705*16467b97STreehugger Robot} 706*16467b97STreehugger Robot 707*16467b97STreehugger Robot- (NSInteger) objectWalkLeaves 708*16467b97STreehugger Robot{ 709*16467b97STreehugger Robot NSInteger i, idx = 0; 710*16467b97STreehugger Robot NSInteger keycnt; 711*16467b97STreehugger Robot ACBTree *t; 712*16467b97STreehugger Robot 713*16467b97STreehugger Robot if ( self != dict.root ) { 714*16467b97STreehugger Robot return 0; // maybe I need to throw an exception here 715*16467b97STreehugger Robot } 716*16467b97STreehugger Robot t = self; 717*16467b97STreehugger Robot self.dict.data = [[NSMutableData dataWithLength:(numrecs * sizeof(id))] retain]; 718*16467b97STreehugger Robot self.dict.ptrBuffer = [self.dict.data mutableBytes]; 719*16467b97STreehugger Robot while ( t != nil && t.nodeType != LEAF ) { 720*16467b97STreehugger Robot t = t.btNodes[0]; 721*16467b97STreehugger Robot } 722*16467b97STreehugger Robot do { 723*16467b97STreehugger Robot keycnt = t.numkeys; 724*16467b97STreehugger Robot for ( i = 0; i < keycnt; i++ ) { 725*16467b97STreehugger Robot if ( t.btNodes[i] != nil ) { 726*16467b97STreehugger Robot dict.ptrBuffer[idx++] = (id) t.btNodes[i]; 727*16467b97STreehugger Robot } 728*16467b97STreehugger Robot } 729*16467b97STreehugger Robot t = t.rnode; 730*16467b97STreehugger Robot } while ( t != nil ); 731*16467b97STreehugger Robot return( idx ); 732*16467b97STreehugger Robot} 733*16467b97STreehugger Robot 734*16467b97STreehugger Robot- (NSString *) description 735*16467b97STreehugger Robot{ 736*16467b97STreehugger Robot NSMutableString *str = [NSMutableString stringWithCapacity:16]; 737*16467b97STreehugger Robot NSInteger i; 738*16467b97STreehugger Robot for (i = 0; i < numkeys; i++ ) { 739*16467b97STreehugger Robot [str appendString:[NSString stringWithFormat:@"key[%d]=%@", i, [keys[i] description]]]; 740*16467b97STreehugger Robot } 741*16467b97STreehugger Robot for (i = 0; i < numkeys; i++ ) { 742*16467b97STreehugger Robot [str appendString:[NSString stringWithFormat:@"btnodes[%d]=%@\n", i, [btNodes[i] description]]]; 743*16467b97STreehugger Robot } 744*16467b97STreehugger Robot return str; 745*16467b97STreehugger Robot} 746*16467b97STreehugger Robot 747*16467b97STreehugger Robot@end 748