Return to bndxsearch.c CVS log

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

Annotation of 43BSD/ingres/source/iutil/bndxsearch.c, revision 1.1

1.1     ! root        1: #
        !             2: # include      <sccs.h>
        !             3: 
        !             4: SCCSID(@(#)bndxsearch.c        8.1     12/31/84)
        !             5: /*
        !             6: **  BNDXSEARCH -- search an BTREE directory
        !             7: **     
        !             8: **     Looks for an available page, if this would force out a page from
        !             9: **     the relation it adds its own.  Searches each level of the dirctory
        !            10: **     for the lowest (highest) page on which the key could occur if mode
        !            11: **     is < (>) 0.  At each level the number of keys on the page is checked
        !            12: **     if it is <= SEARCHFUDGE a linear sharch is done, otherwize a binary
        !            13: **     search is preformed.  If the full key matches exactly the seach
        !            14: **     can stop.  Note that the keys tell the minimum value on that page.
        !            15: **
        !            16: **     Parameters:
        !            17: **             d       - pointer to descriptor of open relation
        !            18: **             tid     - returns tid of page to start (end) looking
        !            19: **             key     - to look for
        !            20: **             mode    - < 0 lowkey, > 0 hikey
        !            21: **             keyok   - true if all keys are assumed to be set
        !            22: **             path    - if non-null, is set to the tids of the access path
        !            23: **
        !            24: **     Returns:
        !            25: **             -2      - pageflush failure
        !            26: **             -1      - get_page failure
        !            27: **             0       - success
        !            28: **
        !            29: **     Side Effects:
        !            30: **             causes I/O
        !            31: **
        !            32: **     Requires:
        !            33: **             getpage, icompare, paramd, pageflush, top_acc, resetacc, etc.
        !            34: **
        !            35: **     Called By:
        !            36: **             find
        !            37: **
        !            38: **     History:
        !            39: **             Stolen from ndxsearch 7/26/80 (jiw)
        !            40: */
        !            41: 
        !            42: # include      <ingres.h>
        !            43: # include      <aux.h>
        !            44: # include      <symbol.h>
        !            45: # include      <access.h>
        !            46: # include      <lock.h>
        !            47: 
        !            48: # define       SEARCHFUDGE     6       /* # of linenos to do a binary search */
        !            49: 
        !            50: bndxsearch(d, tidx, tuple, mode, keyok, path)
        !            51: struct descriptor      *d;             
        !            52: struct tup_id          *tidx;          
        !            53: char                   tuple[];        
        !            54: int                    mode;   
        !            55: int                    keyok;
        !            56: struct tup_id          *path;
        !            57: {
        !            58:        register struct tup_id          *tid;
        !            59:        register int                    i;
        !            60:        long                            pageid;
        !            61:        int                             j, keylen, dno, partialkey;
        !            62:        char                            *p;
        !            63:        int                             pagerr;
        !            64:        struct accessparam              relparm;
        !            65:        int                             top;
        !            66:        register                        bottom;
        !            67:        extern char                     *get_addr();
        !            68: 
        !            69:        tid = tidx;
        !            70:        pagerr = 0;
        !            71:        paramd(d, &relparm);    /* get domains in key order */
        !            72: 
        !            73:        /* assume fullkey is given */
        !            74:        partialkey = FALSE;
        !            75: 
        !            76:        /* remove any key domains not given by the user */
        !            77:        if (!keyok)
        !            78:        {
        !            79:                for (i = 0; dno = relparm.keydno[i]; i++)
        !            80:                {
        !            81:                        if (d->relgiven[dno])
        !            82:                                continue;
        !            83:                        relparm.keydno[i] = 0;
        !            84:                        partialkey = TRUE;
        !            85:                        printf("partial key true\n");
        !            86:                        break;
        !            87:                }
        !            88:        }
        !            89: 
        !            90:        /* if the first key isn't given, just return else search directory */
        !            91:        if (relparm.keydno[0] != 0)
        !            92:        {
        !            93:                /* The actual BTREE directory search must be performed */
        !            94:                pageid = 0;             /* BTREE root is page 0 */
        !            95:                stuff_page(tid, &pageid);
        !            96: 
        !            97:                Acclock = FALSE;
        !            98: 
        !            99:                do
        !           100:                {
        !           101:                        if (path)
        !           102:                        {
        !           103:                                bmove(tid, path++, sizeof(struct tup_id));
        !           104:                        }
        !           105: 
        !           106:                        if (pagerr = get_page(d, tid))
        !           107:                                break;  /* fatal error */
        !           108:                        Acc_head->bufstatus |= BUF_DIRECT;  /* don't get confused */
        !           109:                        bottom = -1;
        !           110:                        top = Acc_head->nxtlino - 1;
        !           111:                        if (top >= SEARCHFUDGE)  /* we are past breakeven */
        !           112:                        {
        !           113:                                printf("doing binary search\n");
        !           114:                                while (top != bottom)   /* binary search */
        !           115:                                {
        !           116:                                        tid->line_id = ((1 + top - bottom) >> 1) + bottom;      /* get to half way point */
        !           117:                                        p = get_addr(tid) + PGPTRSIZ;
        !           118:                                        for (j = 0; dno = relparm.keydno[j]; j++)
        !           119:                                        {
        !           120:                                                keylen = d->relfrml[dno] & I1MASK;
        !           121:                                                printf("data: ");
        !           122:                                                printatt(d->relfrmt[dno], keylen, p);
        !           123:                                                printf("| compared with: ");
        !           124:                                                printatt(d->relfrmt[dno], keylen, &tuple[d->reloff[dno]]);
        !           125:                                                printf("|\n");
        !           126:                                                if (i = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
        !           127:                                                        break;
        !           128:                                                p += keylen;
        !           129:                                        }
        !           130:                                        /* if key is below directory, then we are in the bottom half */
        !           131:                                        printf("i = %d, mode %d, partialkey %d, top %d, bottom %d\n", i, mode, partialkey, top, bottom);
        !           132:                                        if (i < 0 || (i == 0 && partialkey && mode < 0))
        !           133:                                                top = tid->line_id - 1;
        !           134: 
        !           135:                                        else if (i == 0 && !partialkey)
        !           136:                                        {
        !           137:                                                bottom = tid->line_id;
        !           138:                                                break;
        !           139:                                        }
        !           140:                                        else
        !           141:                                                bottom = tid->line_id;
        !           142:                                }
        !           143:                        }
        !           144:                        else    /* do a linear search */
        !           145:                        {
        !           146:                                printf("doing linear search\n");
        !           147:                                for (tid->line_id = 0; (tid->line_id & I1MASK) < Acc_head->nxtlino; tid->line_id++)
        !           148:                                {
        !           149:                                        printf("inside loop: tid\n");
        !           150:                                        dumptid(tid);
        !           151:                                        p = get_addr(tid) + PGPTRSIZ;
        !           152:                                        for (i = 0; dno = relparm.keydno[i]; i++)
        !           153:                                        {
        !           154:                                                keylen = d->relfrml[dno] & I1MASK;
        !           155:                                                printf("data: ");
        !           156:                                                printatt(d->relfrmt[dno], keylen, p);
        !           157:                                                printf("| compared with: ");
        !           158:                                                printatt(d->relfrmt[dno], keylen, &tuple[d->reloff[dno]]);
        !           159:                                                printf("|\n");
        !           160:                                                if (j = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
        !           161:                                                        break;
        !           162:                                                printf("after break in tuple comp\n");
        !           163:                                                p += keylen;
        !           164:                                        }
        !           165:                                        /* if key is below directory, then we have passed the position */
        !           166: 
        !           167:                                        printf("j = %d, mode %d, partialkey %d\n", j, mode, partialkey);
        !           168:                                        if (j < 0)
        !           169:                                                break;
        !           170: 
        !           171:                                        /* if lowkey search on partial key matches, then done */
        !           172:                                        if (j == 0 && partialkey && mode < 0)
        !           173:                                                break;
        !           174:                                        if (j == 0 && mode < 0)
        !           175:                                        {
        !           176:                                                break;
        !           177:                                        }
        !           178:                                }
        !           179:                        }
        !           180:                        if (bottom < 0)
        !           181:                                p = Acc_head->firstup;
        !           182:                        else
        !           183:                        {
        !           184:                                tid->line_id = bottom;
        !           185:                                p = get_addr(tid);
        !           186:                        }
        !           187:                        printf("result: ");
        !           188:                        dumptid(tid);
        !           189:                        bmove(p, tid, PGPTRSIZ);
        !           190:                        printf("and next tid: ");
        !           191:                        dumptid(tid);
        !           192:                } while (Acc_head->mainpg);  /* if at level zero then done */
        !           193:                Acclock = TRUE;
        !           194:        
        !           195:        }
        !           196:        tid->line_id = -1;
        !           197: 
        !           198:        if (path)
        !           199:        {
        !           200:                bmove(tid, path++, sizeof(struct tup_id));
        !           201:                path->line_id = -2;             /* impossible value */
        !           202:        }
        !           203: 
        !           204:        printf("final: ");
        !           205:        dumptid(tid);
        !           206:        return (pagerr);
        !           207: }

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