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

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

Defined functions