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

   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	8.1	12/31/84)
   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: }

Defined functions

Defined macros