![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to findbest.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil|
Return to findbest.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.