Return to findbest.c CVS log

Up to [CSRG BSD Unix] / 42BSD / ingres / source / iutil

Annotation of 42BSD/ingres/source/iutil/findbest.c, revision 1.1

1.1     ! root        1: # include      <ingres.h>
        !             2: # include      <aux.h>
        !             3: # include      <access.h>
        !             4: # include      <sccs.h>
        !             5: 
        !             6: SCCSID(@(#)findbest.c  7.1     2/5/81)
        !             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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.