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

   1: # include   "../ingres.h"
   2: # include   "../aux.h"
   3: # include   "../access.h"
   4: 
   5: findbest(dx, tidx, tuple, need, checkdups)
   6: struct descriptor   *dx;
   7: struct tup_id       *tidx;
   8: char            *tuple;
   9: int         need;
  10: int         checkdups;
  11: 
  12: /*
  13: **	Findbest - find the "best" place to put a tuple.
  14: **	Findbest does not actually put the tuple but rather
  15: **	returns and allocates the tid for the tuple.
  16: **
  17: **	The initial part of the algorithm depends on whether
  18: **	the relation is a heap or not.
  19: **
  20: **	If the relation is a heap, if there is a current page
  21: **	with room for the tuple, that page is used. Otherwise
  22: **	the last page of the heap is considered.
  23: **
  24: **	If the relation is hash or isam, then "find" is used
  25: **	to determine the primary page for the tuple.
  26: **
  27: **	If necessary, findbest will allocate an overflow page
  28: **	if there is not sufficient room for the tuple otherwise.
  29: **
  30: **	If checkdups is TRUE and the relation is not a heap,
  31: **	findbest will check for duplicates.
  32: **
  33: **	Returns:
  34: **
  35: **		0 tuple not a duplicate, tid allocated
  36: **		1 tuple a duplicate of the tuple at tid
  37: */
  38: 
  39: {
  40:     register struct descriptor  *d;
  41:     register struct tup_id      *tid;
  42:     register int            i;
  43:     struct tup_id           temptid;
  44: 
  45:     d = dx;
  46:     tid = tidx;
  47: 
  48: 
  49:     if (abs(d->relspec) == M_HEAP)
  50:     {
  51:         checkdups = FALSE;
  52:         /* determine a page to place tuple in heap relation */
  53:         find_page(d, tid, need);
  54: 
  55:     }
  56:     else
  57:     {
  58:         /* find a suitable page for isam or hash */
  59:         /* determine primary page */
  60:         if (i = find(d, FULLKEY, tid, tid, tuple))
  61:         {
  62:             return (i); /* fatal error */
  63:         }
  64: 
  65:         /* If we are not checking for duplicates then take any
  66: 		** convenient page linked to the main page current indicated
  67: 		** in "tid"
  68: 		*/
  69:         if (!checkdups)
  70:             find_page(d, tid, need);
  71:     }
  72: 
  73:     /* search the chain of pages looking for a spot */
  74:     for (;;)
  75:     {
  76:         if (i = get_page(d, tid))
  77:             break;      /* fatal error */
  78: 
  79:         /* if tuple is duplicate, drop out */
  80:         if (checkdups && dup_check(d, tid, tuple))
  81:         {
  82:             i = 1;
  83:             break;
  84:         }
  85: 
  86:         /* is there space on this page */
  87:         if (space_left(Acc_head) >= need)
  88:             break;  /* found a page to use */
  89: 
  90:         /* no space yet. look on next overflow page */
  91:         if (Acc_head->ovflopg)
  92:         {
  93:             stuff_page(tid, &Acc_head->ovflopg);
  94:             continue;
  95:         }
  96: 
  97:         /* no space. allocate new overflow page */
  98:         if (i = add_ovflo(d, tid))
  99:             break;      /* fatal error */
 100:     }
 101: 
 102:     /* check for dups on remaining overflow pages */
 103:     /* check only if there hasn't been a dup or a page error */
 104:     if (i == 0 && checkdups && Acc_head->ovflopg)
 105:     {
 106:         stuff_page(&temptid, &Acc_head->ovflopg);
 107:         if (i = scan_dups(d, &temptid, tuple))
 108:             bmove(&temptid, tid, sizeof(temptid));  /* tid of duplicate */
 109:     }
 110: 
 111:     /* if tuple isn't a duplicate, allocate a line number */
 112:     if (i == 0)
 113:         tid->line_id = newlino(need);
 114: 
 115: #	ifdef xATR1
 116:     if (tTf(88, 2))
 117:     {
 118:         printf("findbest ret %d,", i);
 119:         dumptid(tid);
 120:     }
 121: #	endif
 122:     return (i);
 123: }
 124: 
 125: 
 126: find_page(dx, tid, need)
 127: struct descriptor   *dx;
 128: struct tup_id       *tid;
 129: int         need;
 130: 
 131: /*
 132: **	Find an appropriate page to put a tuple.
 133: **	If HEAP then any page with room will do. If none
 134: **	can be found, then use the last page.
 135: **	If it is a user relation and a page was found but
 136: **	was full, use it anyway. This can happen only on a
 137: **	modify (which has checkdups turned off).
 138: **
 139: **	For ISAM or HASH look for a page on the same mainpage
 140: **	chain. Duplicate checking must not be enforced.
 141: **
 142: **	The first page to use will be returned in tid in either
 143: **	case.
 144: */
 145: 
 146: {
 147:     register struct descriptor  *d;
 148:     register struct accbuf      *b, *maxbf;
 149:     int             heap;
 150:     long                mainpg;
 151: 
 152:     d = dx;
 153:     maxbf = NULL;
 154:     heap = abs(d->relspec) == M_HEAP;
 155:     pluck_page(tid, &mainpg);
 156:     mainpg++; /* mainpage in buffer points to next higher mainpage */
 157: 
 158:     /* scan all current buffers looking for one belonging to this relation */
 159:     for (b = Acc_head; b != NULL; b = b->modf)
 160:     {
 161:         if (d->reltid == b->rel_tupid && !(b->bufstatus & BUF_DIRECT)
 162:             && (heap || (b->mainpg == mainpg)))
 163:         {
 164:             if (space_left(b) >= need)
 165:             {
 166:                 /* use this page */
 167:                 stuff_page(tid, &b->thispage);
 168:                 return;
 169:             }
 170: 
 171:             /* save buffer of largest page */
 172:             if (maxbf == NULL || maxbf->thispage < b->thispage)
 173:                 maxbf = b;
 174:         }
 175:     }
 176: 
 177:     if (heap)
 178:         last_page(d, tid, maxbf);
 179:     else
 180:     {
 181:         /* if we found a full page of a user's relation,use it */
 182:         if (maxbf && (d->relstat & S_CATALOG) == 0)
 183:             stuff_page(tid, &maxbf->thispage);
 184:     }
 185: }

Defined functions