![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bndxsearch.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / ingres / source / iutil|
Return to bndxsearch.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ingres / source / iutil |
1.1 root 1: #
2: # include <sccs.h>
3:
4: SCCSID(@(#)bndxsearch.c 7.1 2/5/81)
5: /*
6: ** BNDXSEARCH -- search an BTREE directory
7: **
8: ** Looks for an available page, if this would force out a page from
9: ** the relation it adds its own. Searches each level of the dirctory
10: ** for the lowest (highest) page on which the key could occur if mode
11: ** is < (>) 0. At each level the number of keys on the page is checked
12: ** if it is <= SEARCHFUDGE a linear sharch is done, otherwize a binary
13: ** search is preformed. If the full key matches exactly the seach
14: ** can stop. Note that the keys tell the minimum value on that page.
15: **
16: ** Parameters:
17: ** d - pointer to descriptor of open relation
18: ** tid - returns tid of page to start (end) looking
19: ** key - to look for
20: ** mode - < 0 lowkey, > 0 hikey
21: ** keyok - true if all keys are assumed to be set
22: ** path - if non-null, is set to the tids of the access path
23: **
24: ** Returns:
25: ** -2 - pageflush failure
26: ** -1 - get_page failure
27: ** 0 - success
28: **
29: ** Side Effects:
30: ** causes I/O
31: **
32: ** Requires:
33: ** getpage, icompare, paramd, pageflush, top_acc, resetacc, etc.
34: **
35: ** Called By:
36: ** find
37: **
38: ** History:
39: ** Stolen from ndxsearch 7/26/80 (jiw)
40: */
41:
42: # include <ingres.h>
43: # include <aux.h>
44: # include <symbol.h>
45: # include <access.h>
46: # include <lock.h>
47:
48: # define SEARCHFUDGE 6 /* # of linenos to do a binary search */
49:
50: bndxsearch(d, tidx, tuple, mode, keyok, path)
51: struct descriptor *d;
52: struct tup_id *tidx;
53: char tuple[];
54: int mode;
55: int keyok;
56: struct tup_id *path;
57: {
58: register struct tup_id *tid;
59: register int i;
60: long pageid;
61: int j, keylen, dno, partialkey;
62: char *p;
63: int pagerr;
64: struct accessparam relparm;
65: int top;
66: register bottom;
67: extern char *get_addr();
68:
69: tid = tidx;
70: pagerr = 0;
71: paramd(d, &relparm); /* get domains in key order */
72:
73: /* assume fullkey is given */
74: partialkey = FALSE;
75:
76: /* remove any key domains not given by the user */
77: if (!keyok)
78: {
79: for (i = 0; dno = relparm.keydno[i]; i++)
80: {
81: if (d->relgiven[dno])
82: continue;
83: relparm.keydno[i] = 0;
84: partialkey = TRUE;
85: printf("partial key true\n");
86: break;
87: }
88: }
89:
90: /* if the first key isn't given, just return else search directory */
91: if (relparm.keydno[0] != 0)
92: {
93: /* The actual BTREE directory search must be performed */
94: pageid = 0; /* BTREE root is page 0 */
95: stuff_page(tid, &pageid);
96:
97: Acclock = FALSE;
98:
99: do
100: {
101: if (path)
102: {
103: bmove(tid, path++, sizeof(struct tup_id));
104: }
105:
106: if (pagerr = get_page(d, tid))
107: break; /* fatal error */
108: Acc_head->bufstatus |= BUF_DIRECT; /* don't get confused */
109: bottom = -1;
110: top = Acc_head->nxtlino - 1;
111: if (top >= SEARCHFUDGE) /* we are past breakeven */
112: {
113: printf("doing binary search\n");
114: while (top != bottom) /* binary search */
115: {
116: tid->line_id = ((1 + top - bottom) >> 1) + bottom; /* get to half way point */
117: p = get_addr(tid) + PGPTRSIZ;
118: for (j = 0; dno = relparm.keydno[j]; j++)
119: {
120: keylen = d->relfrml[dno] & I1MASK;
121: printf("data: ");
122: printatt(d->relfrmt[dno], keylen, p);
123: printf("| compared with: ");
124: printatt(d->relfrmt[dno], keylen, &tuple[d->reloff[dno]]);
125: printf("|\n");
126: if (i = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
127: break;
128: p += keylen;
129: }
130: /* if key is below directory, then we are in the bottom half */
131: printf("i = %d, mode %d, partialkey %d, top %d, bottom %d\n", i, mode, partialkey, top, bottom);
132: if (i < 0 || (i == 0 && partialkey && mode < 0))
133: top = tid->line_id - 1;
134:
135: else if (i == 0 && !partialkey)
136: {
137: bottom = tid->line_id;
138: break;
139: }
140: else
141: bottom = tid->line_id;
142: }
143: }
144: else /* do a linear search */
145: {
146: printf("doing linear search\n");
147: for (tid->line_id = 0; (tid->line_id & I1MASK) < Acc_head->nxtlino; tid->line_id++)
148: {
149: printf("inside loop: tid\n");
150: dumptid(tid);
151: p = get_addr(tid) + PGPTRSIZ;
152: for (i = 0; dno = relparm.keydno[i]; i++)
153: {
154: keylen = d->relfrml[dno] & I1MASK;
155: printf("data: ");
156: printatt(d->relfrmt[dno], keylen, p);
157: printf("| compared with: ");
158: printatt(d->relfrmt[dno], keylen, &tuple[d->reloff[dno]]);
159: printf("|\n");
160: if (j = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
161: break;
162: printf("after break in tuple comp\n");
163: p += keylen;
164: }
165: /* if key is below directory, then we have passed the position */
166:
167: printf("j = %d, mode %d, partialkey %d\n", j, mode, partialkey);
168: if (j < 0)
169: break;
170:
171: /* if lowkey search on partial key matches, then done */
172: if (j == 0 && partialkey && mode < 0)
173: break;
174: if (j == 0 && mode < 0)
175: {
176: break;
177: }
178: }
179: }
180: if (bottom < 0)
181: p = Acc_head->firstup;
182: else
183: {
184: tid->line_id = bottom;
185: p = get_addr(tid);
186: }
187: printf("result: ");
188: dumptid(tid);
189: bmove(p, tid, PGPTRSIZ);
190: printf("and next tid: ");
191: dumptid(tid);
192: } while (Acc_head->mainpg); /* if at level zero then done */
193: Acclock = TRUE;
194:
195: }
196: tid->line_id = -1;
197:
198: if (path)
199: {
200: bmove(tid, path++, sizeof(struct tup_id));
201: path->line_id = -2; /* impossible value */
202: }
203:
204: printf("final: ");
205: dumptid(tid);
206: return (pagerr);
207: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.