xref: /aosp_15_r20/external/antlr/runtime/ObjC/Framework/ACBTree.m (revision 16467b971bd3e2009fad32dd79016f2c7e421deb)

//
//  ACBTree.m
//  ST4
//
//  Created by Alan Condit on 4/18/11.
//  Copyright 2011 Alan Condit. All rights reserved.
//

#import <Foundation/Foundation.h>
#import "ACBTree.h"
#import "AMutableDictionary.h"
#import "RuntimeException.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;
}

- (void)dealloc
{
#ifdef DEBUG_DEALLOC
    NSLog( @"called dealloc in ACBKey" );
#endif
    [super dealloc];
}

- (NSString *) description
{
    return [NSString stringWithFormat:@"len =%02d\nrecnum=%04d\nkey=%@\n", [key length], recnum, key];
}

@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;
}

- (void)dealloc
{
#ifdef DEBUG_DEALLOC
    NSLog( @"called dealloc in ACBTree" );
#endif
    [super dealloc];
}

- (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 [IllegalArgumentException 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 );
}

- (NSString *) description
{
    NSMutableString *str = [NSMutableString stringWithCapacity:16];
    NSInteger i;
    for (i = 0; i < numkeys; i++ ) {
        [str appendString:[NSString stringWithFormat:@"key[%d]=%@", i, [keys[i] description]]];
    }
    for (i = 0; i < numkeys; i++ ) {
        [str appendString:[NSString stringWithFormat:@"btnodes[%d]=%@\n", i, [btNodes[i] description]]];
    }
    return str;
}

@end