xref: /aosp_15_r20/external/antlr/runtime/ObjC/Framework/ACBTree.m (revision 16467b971bd3e2009fad32dd79016f2c7e421deb)
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