Return to ndxsearch.c CVS log

Up to [CSRG BSD Unix] / 42BSD / ingres / source / iutil

Annotation of 42BSD/ingres/source/iutil/ndxsearch.c, revision 1.1

1.1     ! root        1: # include      <ingres.h>
        !             2: # include      <aux.h>
        !             3: # include      <symbol.h>
        !             4: # include      <access.h>
        !             5: # include      <lock.h>
        !             6: # include      <sccs.h>
        !             7: 
        !             8: SCCSID(@(#)ndxsearch.c 7.2     2/17/81)
        !             9: 
        !            10: 
        !            11: /*
        !            12: **  NDXSEARCH -- search an ISAM directory
        !            13: **     
        !            14: **     Looks for an available page, if this would force out a page from
        !            15: **     the relation it adds its own.  Searches each level of the dirctory
        !            16: **     for the lowest (highest) page on which the key could occur if mode
        !            17: **     is < (>) 0.  At each level the number of keys on the page is checked
        !            18: **     if it is <= SEARCHFUDGE a linear sharch is done, otherwize a binary
        !            19: **     search is preformed.  If the full key matches exactly the seach
        !            20: **     can stop.  Note that the keys tell the minimum value on that page.
        !            21: **
        !            22: **     Parameters:
        !            23: **             d       - pointer to descriptor of open relation
        !            24: **             tid     - returns tid of page to start (end) looking
        !            25: **             key     - to look for
        !            26: **             mode    - < 0 lowkey, > 0 hikey
        !            27: **             keyok   - true if all keys are assumed to be set
        !            28: **
        !            29: **     Returns:
        !            30: **             -2      - pageflush failure
        !            31: **             -1      - get_page failure
        !            32: **             0       - success
        !            33: **
        !            34: **     Side Effects:
        !            35: **             causes I/O
        !            36: */
        !            37: 
        !            38: # define       SEARCHFUDGE     6       /* # of linenos to do a binary search */
        !            39: 
        !            40: ndxsearch(d, tid, tuple, mode, keyok)
        !            41: DESC           *d;             
        !            42: register TID   *tid;           
        !            43: char           tuple[];        
        !            44: int            mode;   
        !            45: int            keyok;
        !            46: {
        !            47:        register int            i;
        !            48:        long                    pageid;
        !            49:        int                     j, keylen, dno, partialkey;
        !            50:        char                    *p;
        !            51:        int                     pagerr;
        !            52:        struct accessparam      relparm;
        !            53:        int                     top;
        !            54:        register                bottom;
        !            55:        extern char             *get_addr();
        !            56: 
        !            57:        pagerr = 0;
        !            58:        paramd(d, &relparm);    /* get domains in key order */
        !            59: 
        !            60:        /* assume fullkey is given */
        !            61:        partialkey = FALSE;
        !            62: 
        !            63:        /* remove any key domains not given by the user */
        !            64:        if (!keyok)
        !            65:        {
        !            66:                for (i = 0; dno = relparm.keydno[i]; i++)
        !            67:                {
        !            68:                        if (d->relgiven[dno])
        !            69:                                continue;
        !            70:                        relparm.keydno[i] = 0;
        !            71:                        partialkey = TRUE;
        !            72:                        break;
        !            73:                }
        !            74:        }
        !            75: 
        !            76:        /* if the first key isn't given, just return else search directory */
        !            77:        if (relparm.keydno[0] != 0)
        !            78:        {
        !            79:                /* The actual ISAM directory search must be performed */
        !            80:                pageid = d->reldum.relprim;
        !            81:                stuff_page(tid, &pageid);
        !            82: 
        !            83:                Acclock = FALSE;
        !            84: 
        !            85:                do
        !            86:                {
        !            87:                        if (pagerr = get_page(d, tid))
        !            88:                                break;  /* fatal error */
        !            89:                        Acc_head->bufstatus |= BUF_DIRECT;  /* don't get confused */
        !            90:                        bottom = 0;
        !            91:                        top = Acc_head->nxtlino - 1;
        !            92: 
        !            93:                        if (top >= SEARCHFUDGE)  /* we are past breakeven */
        !            94:                        {
        !            95:                                while (top != bottom)   /* binary search */
        !            96:                                {
        !            97:                                        tid->line_id = ((1 + top - bottom) >> 1) + bottom;      /* get to half way point */
        !            98:                                        p = get_addr(tid);
        !            99:                                        for (j = 0; dno = relparm.keydno[j]; j++)
        !           100:                                        {
        !           101:                                                keylen = d->relfrml[dno] & I1MASK;
        !           102:                                                if (i = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
        !           103:                                                        break;
        !           104:                                                p += keylen;
        !           105:                                        }
        !           106:                                        /* if key is below directory, then we are in the bottom half */
        !           107:                                        if (i < 0 || (i == 0 && partialkey && mode < 0))
        !           108:                                                top = (tid->line_id & I1MASK) - 1;
        !           109: 
        !           110:                                        else if (i == 0 && !partialkey)
        !           111:                                        {
        !           112:                                                bottom = (tid->line_id & I1MASK);
        !           113:                                                break;
        !           114:                                        }
        !           115:                                        else
        !           116:                                                bottom = (tid->line_id & I1MASK);
        !           117:                                }
        !           118:                        }
        !           119:                        else    /* do a linar search */
        !           120:                        {
        !           121:                                for (tid->line_id = 0; (tid->line_id & I1MASK) < Acc_head->nxtlino; tid->line_id++)
        !           122:                                {
        !           123:                                        p = get_addr(tid);
        !           124:                                        for (i = 0; dno = relparm.keydno[i]; i++)
        !           125:                                        {
        !           126:                                                keylen = d->relfrml[dno] & I1MASK;
        !           127:                                                if (j = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
        !           128:                                                        break;
        !           129:                                                p += keylen;
        !           130:                                        }
        !           131:                                        /* if key is below directory, then we have passed the position */
        !           132:                                        if (j < 0)
        !           133:                                                break;
        !           134: 
        !           135:                                        /* if lowkey search on partial key matches, then done */
        !           136:                                        if (j == 0 && partialkey && mode < 0)
        !           137:                                                break;
        !           138:                                        bottom = tid->line_id;
        !           139:                                        if (j == 0 && mode < 0)
        !           140:                                                break;
        !           141:                                }
        !           142:                        }
        !           143:                        pageid = Acc_head->ovflopg + bottom;
        !           144:                        stuff_page(tid, &pageid);
        !           145:                } while (Acc_head->mainpg);  /* if at level zero then done */
        !           146:                Acclock = TRUE;
        !           147:        
        !           148:        }
        !           149:        tid->line_id = -1;
        !           150:        return (pagerr);
        !           151: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.