![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ndxsearch.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 ndxsearch.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 <symbol.h>
4: # include <access.h>
5: # include <lock.h>
6: # include <sccs.h>
7:
8: SCCSID(@(#)ndxsearch.c 8.1 12/31/84)
9:
10:
11: /*
12: ** NDXSEARCH -- search an ISAM directory
13: **
14: ** Looks for an available page, if this would force out a page from
15: ** the relation it adds its own. Searches each level of the dirctory
16: ** for the lowest (highest) page on which the key could occur if mode
17: ** is < (>) 0. At each level the number of keys on the page is checked
18: ** if it is <= SEARCHFUDGE a linear sharch is done, otherwize a binary
19: ** search is preformed. If the full key matches exactly the seach
20: ** can stop. Note that the keys tell the minimum value on that page.
21: **
22: ** Parameters:
23: ** d - pointer to descriptor of open relation
24: ** tid - returns tid of page to start (end) looking
25: ** key - to look for
26: ** mode - < 0 lowkey, > 0 hikey
27: ** keyok - true if all keys are assumed to be set
28: **
29: ** Returns:
30: ** -2 - pageflush failure
31: ** -1 - get_page failure
32: ** 0 - success
33: **
34: ** Side Effects:
35: ** causes I/O
36: */
37:
38: # define SEARCHFUDGE 6 /* # of linenos to do a binary search */
39:
40: ndxsearch(d, tid, tuple, mode, keyok)
41: DESC *d;
42: register TID *tid;
43: char tuple[];
44: int mode;
45: int keyok;
46: {
47: register int i;
48: long pageid;
49: int j, keylen, dno, partialkey;
50: char *p;
51: int pagerr;
52: struct accessparam relparm;
53: int top;
54: register bottom;
55: extern char *get_addr();
56:
57: pagerr = 0;
58: paramd(d, &relparm); /* get domains in key order */
59:
60: /* assume fullkey is given */
61: partialkey = FALSE;
62:
63: /* remove any key domains not given by the user */
64: if (!keyok)
65: {
66: for (i = 0; dno = relparm.keydno[i]; i++)
67: {
68: if (d->relgiven[dno])
69: continue;
70: relparm.keydno[i] = 0;
71: partialkey = TRUE;
72: break;
73: }
74: }
75:
76: /* if the first key isn't given, just return else search directory */
77: if (relparm.keydno[0] != 0)
78: {
79: /* The actual ISAM directory search must be performed */
80: pageid = d->reldum.relprim;
81: stuff_page(tid, &pageid);
82:
83: Acclock = FALSE;
84:
85: do
86: {
87: if (pagerr = get_page(d, tid))
88: break; /* fatal error */
89: Acc_head->bufstatus |= BUF_DIRECT; /* don't get confused */
90: bottom = 0;
91: top = Acc_head->nxtlino - 1;
92:
93: if (top >= SEARCHFUDGE) /* we are past breakeven */
94: {
95: while (top != bottom) /* binary search */
96: {
97: tid->line_id = ((1 + top - bottom) >> 1) + bottom; /* get to half way point */
98: p = get_addr(tid);
99: for (j = 0; dno = relparm.keydno[j]; j++)
100: {
101: keylen = d->relfrml[dno] & I1MASK;
102: if (i = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
103: break;
104: p += keylen;
105: }
106: /* if key is below directory, then we are in the bottom half */
107: if (i < 0 || (i == 0 && partialkey && mode < 0))
108: top = (tid->line_id & I1MASK) - 1;
109:
110: else if (i == 0 && !partialkey)
111: {
112: bottom = (tid->line_id & I1MASK);
113: break;
114: }
115: else
116: bottom = (tid->line_id & I1MASK);
117: }
118: }
119: else /* do a linar search */
120: {
121: for (tid->line_id = 0; (tid->line_id & I1MASK) < Acc_head->nxtlino; tid->line_id++)
122: {
123: p = get_addr(tid);
124: for (i = 0; dno = relparm.keydno[i]; i++)
125: {
126: keylen = d->relfrml[dno] & I1MASK;
127: if (j = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
128: break;
129: p += keylen;
130: }
131: /* if key is below directory, then we have passed the position */
132: if (j < 0)
133: break;
134:
135: /* if lowkey search on partial key matches, then done */
136: if (j == 0 && partialkey && mode < 0)
137: break;
138: bottom = tid->line_id;
139: if (j == 0 && mode < 0)
140: break;
141: }
142: }
143: pageid = Acc_head->ovflopg + bottom;
144: stuff_page(tid, &pageid);
145: } while (Acc_head->mainpg); /* if at level zero then done */
146: Acclock = TRUE;
147:
148: }
149: tid->line_id = -1;
150: return (pagerr);
151: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.