| // |
| // ACBTree.m |
| // ST4 |
| // |
| // Created by Alan Condit on 4/18/11. |
| // Copyright 2011 Alan Condit. All rights reserved. |
| // |
| |
| #import <Cocoa/Cocoa.h> |
| #import "ACBTree.h" |
| #import "AMutableDictionary.h" |
| #import "ANTLRRuntimeException.h" |
| |
| @class AMutableDictionary; |
| |
| @implementation ACBKey |
| |
| static NSInteger RECNUM = 0; |
| |
| @synthesize recnum; |
| @synthesize key; |
| |
| + (ACBKey *)newKey |
| { |
| return [[ACBKey alloc] init]; |
| } |
| |
| + (ACBKey *)newKeyWithKStr:(NSString *)aKey |
| { |
| return [[ACBKey alloc] initWithKStr:(NSString *)aKey]; |
| } |
| |
| - (id) init |
| { |
| self =[super init]; |
| if ( self != nil ) { |
| recnum = RECNUM++; |
| } |
| return self; |
| } |
| |
| - (id) initWithKStr:(NSString *)aKey |
| { |
| self =[super init]; |
| if ( self != nil ) { |
| NSInteger len; |
| recnum = RECNUM++; |
| key = aKey; |
| len = [aKey length]; |
| if ( len >= BTKeySize ) { |
| len = BTKeySize - 1; |
| } |
| strncpy( kstr, [aKey cStringUsingEncoding:NSASCIIStringEncoding], len); |
| kstr[len] = '\0'; |
| } |
| return self; |
| } |
| |
| @end |
| |
| @implementation ACBTree |
| |
| @synthesize dict; |
| @synthesize lnode; |
| @synthesize rnode; |
| @synthesize keys; |
| @synthesize btNodes; |
| @synthesize lnodeid; |
| @synthesize rnodeid; |
| @synthesize nodeid; |
| @synthesize nodeType; |
| @synthesize numkeys; |
| @synthesize numrecs; |
| @synthesize updtd; |
| @synthesize keylen; |
| @synthesize kidx; |
| |
| + (ACBTree *) newNodeWithDictionary:(AMutableDictionary *)theDict |
| { |
| return [[ACBTree alloc] initWithDictionary:theDict]; |
| } |
| |
| - (id)initWithDictionary:(AMutableDictionary *)theDict |
| { |
| self = [super init]; |
| if (self) { |
| // Initialization code here. |
| dict = theDict; |
| nodeid = theDict.nxt_nodeid++; |
| keys = keyArray; |
| btNodes = btNodeArray; |
| if ( nodeid == 0 ) { |
| numkeys = 0; |
| } |
| } |
| |
| return self; |
| } |
| |
| - (ACBTree *)createnode:(ACBKey *)kp |
| { |
| ACBTree *tmp; |
| |
| tmp = [ACBTree newNodeWithDictionary:dict]; |
| tmp.nodeType = nodeType; |
| tmp.lnode = self; |
| tmp.rnode = self.rnode; |
| self.rnode = tmp; |
| //tmp.btNodes[0] = self; |
| //tmp.keys[0] = kp; |
| tmp.updtd = YES; |
| tmp.numrecs = ((nodeType == LEAF)?1:numrecs); |
| updtd = YES; |
| tmp.numkeys = 1; |
| [tmp retain]; |
| return(tmp); |
| } |
| |
| - (ACBTree *)deletekey:(NSString *)dkey |
| { |
| ACBKey /* *del, */ *dkp; |
| ACBTree *told, *sNode; |
| BOOL mustRelease = NO; |
| |
| if ( [dkey isKindOfClass:[NSString class]] ) { |
| dkp = [ACBKey newKeyWithKStr:dkey]; |
| mustRelease = YES; |
| } |
| else if ( [dkey isKindOfClass:[ACBKey class]] ) |
| dkp = (ACBKey *)dkey; |
| else |
| @throw [ANTLRIllegalArgumentException newException:[NSString stringWithFormat:@"Don't understand this key:\"%@\"", dkey]]; |
| sNode = [self search:dkp.key]; |
| if ( sNode == nil || [sNode searchnode:dkp.key match:YES] == FAILURE ) { |
| if ( mustRelease ) [dkp release]; |
| return(self); |
| } |
| told = dict.root; |
| /* del = */[self internaldelete:dkp]; |
| |
| /* check for shrink at the root */ |
| if ( numkeys == 1 && nodeType != LEAF ) { |
| told = btNodes[0]; |
| told.nodeid = 1; |
| told.updtd = YES; |
| dict.root = told; |
| } |
| #ifdef DONTUSENOMO |
| if (debug == 'd') [self printtree]; |
| #endif |
| if ( mustRelease ) [dkp release]; |
| return(told); |
| } |
| |
| /** insertKey is the insertion entry point |
| * It determines if the key exists in the tree already |
| * it calls internalInsert to determine if the key already exists in the tree, |
| * and returns the node to be updated |
| */ |
| - (ACBTree *)insertkey:(ACBKey *)kp value:(id)value |
| { |
| ACBTree *tnew, *q; |
| NSInteger h, nodeNum; |
| |
| tnew = self; |
| q = [self internalinsert:kp value:value split:&h]; |
| /* check for growth at the root */ |
| if ( q != nil ) { |
| tnew = [[ACBTree newNodeWithDictionary:dict] retain]; |
| tnew.nodeType = BTNODE; |
| nodeNum = tnew.nodeid; |
| tnew.nodeid = 0; |
| self.nodeid = nodeNum; |
| [tnew insert:self.keys[numkeys-1] value:self index:0 split:&h]; |
| [tnew insert:q.keys[q.numkeys-1] value:q index:1 split:&h]; |
| tnew.numrecs = self.numrecs + q.numrecs; |
| tnew.lnodeid = self.nodeid; |
| tnew.rnodeid = self.rnodeid; |
| self.rnodeid = tnew.nodeid; |
| tnew.lnode = self; |
| tnew.rnode = self.rnode; |
| self.rnode = tnew; |
| /* affected by nodeid swap */ |
| // newnode.lnodeid = tnew.btNodes[0].nodeid; |
| } |
| //dict.root = t; |
| //l.reccnt++; |
| return(tnew); |
| } |
| |
| - (ACBTree *)search:(NSString *)kstr |
| { |
| NSInteger i, ret; |
| NSInteger srchlvl = 0; |
| ACBTree *t; |
| |
| t = self; |
| if ( self.numkeys == 0 && self.nodeType == LEAF ) |
| return nil; |
| while (t != nil) { |
| for (i = 0; i < t.numkeys; i++) { |
| ret = [t.keys[i].key compare:kstr]; |
| if ( ret >= 0 ) { |
| if ( t.nodeType == LEAF ) { |
| if ( ret == 0 ) return (t); /* node containing keyentry found */ |
| else return nil; |
| } |
| else { |
| break; |
| } |
| } |
| } |
| srchlvl++; |
| if ( t.nodeType == BTNODE ) t = t.btNodes[i]; |
| else { |
| t = nil; |
| } |
| } |
| return(nil); /* entry not found */ |
| } |
| |
| /** SEARCHNODE |
| * calling parameters -- |
| * BKEY PTR for key to search for. |
| * TYPE for exact match(YES) or position(NO) |
| * returns -- i |
| * i == FAILURE when match required but does not exist. |
| * i == t.numkeys if no existing insertion branch found. |
| * otherwise i == insertion branch. |
| */ |
| - (NSInteger)searchnode:(NSString *)kstr match:(BOOL)match |
| { |
| NSInteger i, ret; |
| for ( i = 0; i < numkeys; i++ ) { |
| ret = [keys[i].key compare:kstr]; |
| if ( ret >= 0 ) { /* key node found */ |
| if ( ret == 0 && match == NO ) { |
| return FAILURE; |
| } |
| else if ( ret > 0 && match == YES ) { |
| return FAILURE; |
| } |
| break; |
| } |
| } |
| if ( i == numkeys && match == YES ) { |
| i = FAILURE; |
| } |
| return(i); |
| } |
| |
| - (ACBKey *)internaldelete:(ACBKey *)dkp |
| { |
| NSInteger i, nkey; |
| __strong ACBKey *del = nil; |
| ACBTree *tsb; |
| NSInteger srchlvl = 0; |
| |
| /* find deletion branch */ |
| if ( self.nodeType != LEAF ) { |
| srchlvl++; |
| /* search for end of tree */ |
| i = [self searchnode:dkp.key match:NO]; |
| del = [btNodes[i] internaldelete:dkp]; |
| srchlvl--; |
| /* if not LEAF propagate back high key */ |
| tsb = btNodes[i]; |
| nkey = tsb.numkeys - 1; |
| } |
| /*** the bottom of the tree has been reached ***/ |
| else { /* set up deletion ptrs */ |
| if ( [self delfrmnode:dkp] == SUCCESS ) { |
| if ( numkeys < BTHNODESIZE+1 ) { |
| del = dkp; |
| } |
| else { |
| del = nil; |
| } |
| dkp.recnum = nodeid; |
| return(del); |
| } |
| } |
| /*** indicate deletion to be done ***/ |
| if ( del != nil ) { |
| /*** the key in "del" has to be deleted from in present node ***/ |
| if ( btNodes[i].numkeys >= BTHNODESIZE+1 ) { |
| /* node does not need balancing */ |
| del = nil; |
| self.keys[i] = tsb.keys[nkey]; |
| } |
| else { /* node requires balancing */ |
| if ( i == 0 ) { |
| [self rotateright:0]; |
| self.btNodes[0] = tsb; |
| } else if ( i < numkeys-1 ) { /* look to the right first */ |
| if ( self.btNodes[i+1].numkeys > BTHNODESIZE+1 ) { /* carry from right */ |
| [self borrowright:i]; |
| } |
| else { /* merge present node with right node */ |
| [self mergenode:i]; |
| } |
| } |
| else { /* look to the left */ |
| if ( i > 0 ) { /* carry or merge with left node */ |
| if ( self.btNodes[i-1].numkeys > BTHNODESIZE+1 ) { /* carry from left */ |
| [self borrowleft:i]; |
| } |
| else { /*** merge present node with left node ***/ |
| i--; |
| [self mergenode:i]; |
| tsb = self.btNodes[i]; |
| } |
| } |
| } |
| self.keys[i] = tsb.keys[nkey]; |
| } |
| } |
| numrecs--; |
| updtd = TRUE; |
| return(del); |
| } |
| |
| /** Search key kp on B-tree with root t; if found increment counter. |
| * otherwise insert an item with key kp in tree. If an ACBKey |
| * emerges to be passed to a lower level, then assign it to kp; |
| * h = "tree t has become higher" |
| */ |
| - (ACBTree *) internalinsert:(ACBKey *)kp value:(id)value split:(NSInteger *)h |
| { |
| /* search key ins on node t^; h = false */ |
| NSInteger i, ret; |
| ACBTree *q, *tmp; |
| |
| for (i = 0; i < numkeys; i++) { |
| ret = [keys[i].key compare:kp.key]; |
| if ( ret >= 0 ) { |
| if ( nodeType == LEAF && ret == 0 ) return (self); /* node containing keyentry found */ |
| break; |
| } |
| } |
| if ( nodeType == LEAF ) { /* key goes in this node */ |
| q = [self insert:kp value:value index:i split:h]; |
| } |
| else { /* nodeType == BTNODE */ |
| /* key is not on this node */ |
| q = [self.btNodes[i] internalinsert:kp value:value split:h]; |
| if ( *h ) { |
| [self insert:kp value:q index:i split:h]; |
| } |
| else { |
| self.numrecs++; |
| } |
| tmp = self.btNodes[numkeys-1]; |
| keys[numkeys-1] = tmp.keys[tmp.numkeys-1]; |
| if ( i != numkeys-1 ) { |
| tmp = self.btNodes[i]; |
| keys[i] = tmp.keys[tmp.numkeys-1]; |
| } |
| updtd = YES; |
| } /* search */ |
| return q; |
| } |
| |
| /** Do the actual insertion or split and insert |
| * insert key to the right of t.keys[hi] |
| */ |
| - (ACBTree *) insert:(ACBKey *)kp value:(id)value index:(NSInteger)hi split:(NSInteger *)h |
| { |
| ACBTree *b; |
| |
| if ( numkeys < BTNODESIZE ) { |
| *h = NO; |
| [self rotateright:hi]; |
| keys[hi] = kp; |
| btNodes[hi] = value; |
| numrecs++; |
| numkeys++; |
| updtd = YES; |
| //[kp retain]; |
| return nil; |
| } |
| else { /* node t is full; split it and assign the emerging ACBKey to olditem */ |
| b = [self splitnode:hi]; |
| if ( hi <= BTHNODESIZE ) { /* insert key in left page */ |
| [self rotateright:hi]; |
| keys[hi] = kp; |
| btNodes[hi] = value; |
| numrecs++; |
| numkeys++; |
| } |
| else { /* insert key in right page */ |
| hi -= BTHNODESIZE; |
| if ( b.rnode == nil ) hi--; |
| [b rotateright:hi]; |
| b.keys[hi] = kp; |
| b.btNodes[hi] = value; |
| b.numrecs++; |
| b.numkeys++; |
| } |
| numkeys = b.numkeys = BTHNODESIZE+1; |
| b.updtd = updtd = YES; |
| } |
| return b; |
| } /* insert */ |
| |
| - (void)borrowleft:(NSInteger)i |
| { |
| ACBTree *t0, *t1; |
| NSInteger nkey; |
| |
| t0 = btNodes[i]; |
| t1 = btNodes[i-1]; |
| nkey = t1.numkeys-1; |
| [t0 insinnode:t1.keys[nkey] value:t1.btNodes[nkey]]; |
| [t1 delfrmnode:t1.keys[nkey]]; |
| nkey--; |
| keys[i-1] = t1.keys[nkey]; |
| keys[i-1].recnum = t1.nodeid; |
| } |
| |
| - (void)borrowright:(NSInteger)i |
| { |
| ACBTree *t0, *t1; |
| NSInteger nkey; |
| |
| t0 = btNodes[i]; |
| t1 = btNodes[i+1]; |
| [t0 insinnode:t1.keys[0] value:t1.btNodes[0]]; |
| [t1 delfrmnode:t1.keys[0]]; |
| nkey = t0.numkeys - 1; |
| keys[i] = t0.keys[nkey]; |
| keys[i].recnum = t0.nodeid; |
| } |
| |
| - (NSInteger)delfrmnode:(ACBKey *)ikp |
| { |
| NSInteger j; |
| |
| j = [self searchnode:ikp.key match:YES]; |
| if (j == FAILURE) { |
| return(FAILURE); |
| } |
| ACBKey *k0 = nil; |
| ACBTree *n0 = nil; |
| if ( self.nodeType == LEAF ) { |
| k0 = self.keys[j]; |
| n0 = self.btNodes[j]; |
| } |
| [self rotateleft:j]; |
| self.numkeys--; |
| numrecs -= ((self.nodeType == LEAF)?1:btNodes[j].numrecs); |
| if ( k0 ) [k0 release]; |
| if ( n0 ) [n0 release]; |
| updtd = TRUE; |
| return(SUCCESS); |
| } |
| |
| - (NSInteger)insinnode:(ACBKey *)ikp value:(id)value |
| { |
| NSInteger j; |
| |
| j = [self searchnode:ikp.key match:NO]; |
| [self rotateright:j]; |
| keys[j] = ikp; |
| btNodes[j] = value; |
| numkeys++; |
| if ( nodeType == LEAF ) { |
| numrecs++; |
| } |
| else { |
| numrecs += btNodes[j].numrecs; |
| } |
| updtd = TRUE; |
| return(j); |
| } |
| |
| - (void)mergenode:(NSInteger)i |
| { |
| ACBTree *t0, *t1, *tr; |
| NSInteger j, k, nkeys; |
| |
| t0 = btNodes[i]; |
| t1 = btNodes[i+1]; |
| /*** move keys and pointers from |
| t1 node to t0 node ***/ |
| for (j=t0.numkeys, k=0; j < BTNODESIZE && k < t1.numkeys; j++, k++) { |
| t0.keys[j] = t1.keys[k]; |
| t0.btNodes[j] = t1.btNodes[k]; |
| t0.numkeys++; |
| } |
| t0.numrecs += t1.numrecs; |
| t0.rnode = t1.rnode; |
| t0.rnodeid = t1.rnodeid; |
| t0.updtd = YES; |
| nkeys = t0.numkeys - 1; |
| keys[i] = t0.keys[nkeys]; /* update key to point to new high key */ |
| [self rotateleft:i+1]; /* copy over the keys and nodes */ |
| |
| t1.nodeType = -1; |
| if (t1.rnodeid != 0xffff && i < numkeys - 2) { |
| tr = btNodes[i+1]; |
| tr.lnodeid = t0.nodeid; |
| tr.lnode = t0; |
| tr.updtd = YES; |
| } |
| self.numkeys--; |
| updtd = YES; |
| } |
| |
| - (ACBTree *)splitnode:(NSInteger)idx |
| { |
| ACBTree *t1; |
| NSInteger j, k; |
| |
| k = (idx <= BTHNODESIZE) ? BTHNODESIZE : BTHNODESIZE+1; |
| /*** create new node ***/ |
| // checknode(l, t, k); |
| t1 = [ACBTree newNodeWithDictionary:dict]; |
| t1.nodeType = nodeType; |
| t1.rnode = self.rnode; |
| self.rnode = t1; |
| t1.lnode = self; |
| self.updtd = t1.updtd = YES; |
| /*** move keys and pointers ***/ |
| NSInteger i = 0; |
| for (j = k; j < BTNODESIZE; j++, i++ ) { |
| t1.keys[i] = keys[j]; |
| t1.btNodes[i] = btNodes[j]; |
| t1.numrecs += ((nodeType == LEAF) ? 1 : btNodes[j].numrecs); |
| numrecs -= ((nodeType == LEAF) ? 1 : btNodes[j].numrecs); |
| keys[j] = nil; |
| btNodes[j] = nil; |
| } |
| t1.numkeys = BTNODESIZE-k; |
| self.numkeys = k; |
| return(t1); |
| } |
| |
| #ifdef DONTUSENOMO |
| freetree(l, t) |
| FIDB *l; |
| ACBTree *t; |
| { |
| ACBTree *tmp; |
| NSInteger i; |
| |
| if (dict.root == nil) return(SUCCESS); |
| if (t.nodeid == 1) { |
| srchlvl = 0; |
| } |
| else srchlvl++; |
| for (i = 0; i < t.numkeys; i++) { |
| tmp = t.btNodes[i]; |
| if (tmp != nil) { |
| if (tmp.nodeType == LEAF) { |
| free(tmp); /* free the leaf */ |
| if (tmp == l.rrnode) { |
| l.rrnode = nil; |
| } |
| t.btNodes[i] = nil; |
| l.chknode.nods_inuse--; |
| /* putpage(l, l.chknode, 0); |
| */ |
| } |
| else { |
| freetree(l, tmp); /* continue up the tree */ |
| srchlvl--; /* decrement the srchlvl on return */ |
| } |
| } |
| } |
| free(t); /* free the node entered with */ |
| if (t == l.rrnode) { |
| l.rrnode = nil; |
| } |
| l.chknode.nods_inuse--; |
| /* putpage(l, l.chknode, 0); |
| */ |
| t = nil; |
| } |
| |
| - (void) notfound:(ACBKey *)kp |
| { |
| /* error routine to perform if entry was expected and not found */ |
| } |
| |
| - (void)printtree:(ACBTree *)t |
| { |
| BYTE *str; |
| NSInteger i, j; |
| NSUInteger *pdate, *ptime; |
| |
| syslst = stdprn; |
| if ( t.nodeid == 1 ) { |
| srchlvl = 0; |
| } |
| else srchlvl++; |
| for (j = 0; j < t.numkeys; j++) { |
| checknode(l, t, j); |
| if ( t.btNodes[j] != nil ) [self printtree:t.btNodes[j]]; |
| } |
| NSLog(@"Nodeid = %d, nodeType = %s, numkeys = %d, numrecs = %d\n", |
| t.nodeid, (t.nodeType == BTNODE)?@"NODE":@"LEAF", t.numkeys, t.numrecs); |
| NSLog(@"Left nodeid = %d, Right nodeid = %d\n", t.lnodeid, t.rnodeid); |
| for (i = 0; i < t.numkeys; i++) { |
| NSLog(@" t.keys[%d] recnum = %d, keyval = %@", |
| i, t.keys[i].recnum, t.keys[i]); |
| str = t.keys[i].kstr; |
| pdate = (NSUInteger *) (str + 6); |
| ptime = (NSUInteger *) (str + 8); |
| NSLog(@" date = %04.4x, time = %04.4x\n", |
| *pdate, *ptime); |
| } |
| } |
| |
| - (BOOL)puttree:(ACBTree *)t |
| { |
| NSInteger i; |
| if (t.nodeType != LEAF) { |
| for (i = 0; i < t.numkeys; i++) { |
| if ( t.btNodes[i] != nil ) puttree(l, t.btNodes[i]); |
| } |
| } |
| if ( t.updtd ) { |
| putnode(l, t, t.nodeid); |
| return(YES); |
| } |
| return(NO); |
| } |
| |
| #endif |
| |
| /** ROTATELEFT -- rotate keys from right to the left |
| * starting at position j |
| */ |
| - (void)rotateleft:(NSInteger)j |
| { |
| while ( j+1 < numkeys ) { |
| keys[j] = keys[j+1]; |
| btNodes[j] = btNodes[j+1]; |
| j++; |
| } |
| } |
| |
| /** ROTATERIGHT -- rotate keys to the right by 1 position |
| * starting at the last key down to position j. |
| */ |
| - (void)rotateright:(NSInteger)j |
| { |
| NSInteger k; |
| |
| for ( k = numkeys; k > j; k-- ) { |
| keys[k] = keys[k-1]; |
| btNodes[k] = btNodes[k-1]; |
| } |
| keys[j] = nil; |
| btNodes[j] = nil; |
| } |
| |
| - (NSInteger) keyWalkLeaves |
| { |
| NSInteger i, idx = 0; |
| NSInteger keycnt; |
| ACBTree *t; |
| |
| if ( self != dict.root ) { |
| return 0; // maybe I need to throw an exception here |
| } |
| t = self; |
| self.dict.data = [[NSMutableData dataWithLength:(numkeys * sizeof(id))] retain]; |
| self.dict.ptrBuffer = [self.dict.data mutableBytes]; |
| while ( t != nil && t.nodeType != LEAF ) { |
| t = t.btNodes[0]; |
| } |
| do { |
| keycnt = t.numkeys; |
| for ( i = 0; i < keycnt; i++ ) { |
| if ( t.btNodes[i] != nil ) { |
| dict.ptrBuffer[idx++] = (id) t.keys[i].key; |
| } |
| } |
| t = t.rnode; |
| } while ( t != nil ); |
| return( idx ); |
| } |
| |
| - (NSInteger) objectWalkLeaves |
| { |
| NSInteger i, idx = 0; |
| NSInteger keycnt; |
| ACBTree *t; |
| |
| if ( self != dict.root ) { |
| return 0; // maybe I need to throw an exception here |
| } |
| t = self; |
| self.dict.data = [[NSMutableData dataWithLength:(numrecs * sizeof(id))] retain]; |
| self.dict.ptrBuffer = [self.dict.data mutableBytes]; |
| while ( t != nil && t.nodeType != LEAF ) { |
| t = t.btNodes[0]; |
| } |
| do { |
| keycnt = t.numkeys; |
| for ( i = 0; i < keycnt; i++ ) { |
| if ( t.btNodes[i] != nil ) { |
| dict.ptrBuffer[idx++] = (id) t.btNodes[i]; |
| } |
| } |
| t = t.rnode; |
| } while ( t != nil ); |
| return( idx ); |
| } |
| |
| - (void)dealloc |
| { |
| #ifdef DEBUG_DEALLOC |
| NSLog( @"called dealloc in ACBTree" ); |
| #endif |
| [super dealloc]; |
| } |
| |
| @end |
