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

##### Functions

    ndxsearch         X

##### Macros

    SEARCHFUDGE       X

       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

ndxsearch defined in line 47; used 2 times

- in /usr/ingres/source/access/find.c line 122, 134

#### Defined macros

SEARCHFUDGE defined in line 45; used 1 times

- in line 102

Last modified: 1995-02-12 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 561 |