4.3BSD - /usr/ingres/source/iutil/bndxsearch.c

   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: }

Defined functions

Defined macros