2.11BSD#431 - /usr/ingres/source/access/ndxsearch.c

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

Defined functions

Defined macros