![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to btree_util.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 btree_util.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil |
1.1 root 1: #include <btree.h>
2: #include <ingres.h>
3: #include <opsys.h>
4: #include <sccs.h>
5:
6: SCCSID(@(#)btree_util.c 8.2 1/31/86)
7:
8: /* Trace up to the root of the BTree, incrementing (or decrementing) all
9: ** key values.
10: **
11: ** Parameters :
12: ** tree - BTree filename (I)
13: ** block - starting node from which path is traced (I)
14: ** inc - either +1 or -1 (I)
15: */
16:
17: tracepath(rootpage, block, inc)
18:
19: long rootpage;
20: register struct locator *block;
21: register int inc;
22: {
23: struct locator p, child;
24:
25: if (block->pageno != rootpage) /* if at root, no need for adjustment */
26: {
27: bmove(block, &child, sizeof(struct locator));
28:
29: /* trace up to root node */
30: do
31: {
32: p.pageno = child.page.parent;
33: parentkey(child.pageno, &p);
34: p.page.node.intnode.key[p.offset] += inc;
35: write_node(p.pageno, &p.page);
36: bmove(&p, &child, sizeof(struct locator));
37: } while (p.pageno != rootpage);
38: }
39: }
40:
41: /* Determines which key/ptr pair is the parent of the given page
42: **
43: ** Parameters :
44: ** tree - BTree filename (I)
45: ** block - page number of child (I)
46: ** prt - information about the parent of the child (I, O)
47: **
48: */
49:
50: parentkey(block, prt)
51:
52: long block;
53: register struct locator *prt;
54: {
55: register int i;
56:
57: get_node(prt->pageno, &prt->page);
58: /* find pointer in parent which references desired block */
59: for (i = 0; prt->page.node.intnode.ptr[i] != block && i < prt->page.nelmts; ++i)
60: continue;
61:
62: if (i == prt->page.nelmts)
63: syserr("parentkey: child = %ld", block);
64: prt->offset = i;
65: return(0);
66: }
67:
68: /* Retrieve a node from the BTree
69: **
70: ** Parameters :
71: ** tree - BTree filename (I)
72: ** pagenum - page number of page to be retrieved (I)
73: ** buffer - buffer into which page is retrieved (O)
74: */
75:
76: get_node(pagenum, buffer)
77:
78: long pagenum;
79: register struct BTreeNode *buffer;
80: {
81: extern int Btree_fd;
82:
83: if ( lseek(Btree_fd, pagenum * PGSIZE, 0) == -1 )
84: syserr("GET_NODE: seek to %ld failed",pagenum);
85: if (read(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
86: syserr("GET_NODE: read btree, page %ld", pagenum);
87: }
88:
89: /* Write a node into the BTree file name
90: **
91: ** Parameters :
92: ** tree - BTree filename (I)
93: ** pagenum - page number of page to be written (I)
94: ** buffer - buffer containing page to be written (I)
95: */
96:
97: write_node(pagenum, buffer)
98:
99: long pagenum;
100: register struct BTreeNode *buffer;
101: {
102: extern int Btree_fd;
103:
104: lseek(Btree_fd, pagenum * PGSIZE, 0);
105: if (write(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
106: syserr("WRITE_NODE: write btree, page %ld", pagenum);
107: }
108:
109: /* Retrieves a new page from the BTree file. If there is an empty page
110: ** in the file, that page is used. Otherwise, a new page is added to
111: ** the end of the file.
112: **
113: ** Parameters :
114: ** tree - BTree filename (I)
115: **
116: ** Returns :
117: ** page number of new page
118: */
119:
120: long
121: new_page(tree)
122:
123: char *tree;
124: {
125: int i;
126: long freepage, newpage;
127: struct BTreeNode page, root, garbage;
128: struct stat fileinfo;
129: extern DESC Btreesec;
130:
131: get_node(RT, &root);
132: freepage = root.parent;
133: if (freepage == 0)
134: /* no free pages in file, add a new page to the end */
135: {
136: /* determine page number of page at very end of file */
137: stat(tree, &fileinfo);
138: newpage = fileinfo.st_size / PGSIZE;
139: write_node(newpage, &page);
140: }
141: else
142: /* use first free page, adjusting free page chain */
143: {
144: newpage = freepage;
145: get_node(newpage, &garbage);
146: root.parent = garbage.parent;
147: write_node(RT, &root);
148: }
149: return(newpage);
150: }
151:
152: /* Returns an empty file to the empty file list. The head of the list
153: ** is indicated through the parent of the root and linked together
154: ** through the parents of the empty pages.
155: **
156: ** Parameters :
157: ** tree - BTree filename (I)
158: ** pagenum - page number of empty page (I)
159: */
160:
161: return_page(pagenum)
162:
163: long pagenum;
164: {
165: struct BTreeNode root, freepage;
166:
167: /* indicate that page is free by inserting its page number at the
168: ** head of the free page list */
169: get_node(RT, &root);
170: get_node(pagenum, &freepage);
171: freepage.parent = root.parent;
172: freepage.depth = 0;
173: write_node(pagenum, &freepage);
174: root.parent = pagenum;
175: write_node(RT, &root);
176: }
177:
178: /*
179: ** Determine the lid that corresponds to a given position in the B-Tree.
180: **
181: ** Parameters :
182: ** tree - BTree name (I)
183: ** tidloc - location in BTree (I)
184: **
185: ** Returns :
186: ** lid value
187: */
188: get_lid(tidloc, lid)
189:
190: TID *tidloc;
191: long lid[];
192: {
193: static struct locator tid;
194: register int i, j;
195: long l, child;
196:
197: do
198: {
199: /* determine where in BTree to search */
200: pluck_page(tidloc, &tid.pageno);
201:
202: get_node(tid.pageno, (char *) &tid.page);
203: tid.offset = tid.page.node.leafnode.back_ptr[tidloc->line_id & I1MASK];
204:
205: if (tid.offset > tid.page.nelmts - 1)
206: syserr("get_lid: bad tid location %ld, tid.offset=%d, tid.page.nelmts=%d", *tidloc, tid.offset,tid.page.nelmts);
207:
208: /* scan through leaf */
209: for (l = 1, i = tid.offset; i > 0; ++l, --i)
210: continue;
211: /* trace up to root, adding keys */
212: while (!tid.page.depth)
213: {
214: child = tid.pageno;
215: tid.pageno = tid.page.parent;
216: parentkey(child, &tid);
217: for (i = tid.offset - 1; i >= 0; l += tid.page.node.intnode.key[i--])
218: continue;
219: }
220: lid[tid.page.depth - 1] = l;
221: # ifdef xATR1
222: if (tTf(24,0))
223: printf("lid=%ld\n", lid[tid.page.depth - 1]);
224: # endif
225: bmove(&tid.page.prttree, tidloc, LIDSIZE);
226: } while (tid.page.depth > 1);
227: }
228:
229: /*
230: ** Uses the secondary btree relation to find the btree tid corresponding
231: ** to a given main relation tid
232: */
233:
234: search_btree(mtid, tidloc)
235:
236: TID mtid;
237: register TID *tidloc;
238: {
239: char key[2 * LIDSIZE], tup[2 * LIDSIZE];
240: TID tid;
241: extern DESC Btreesec;
242:
243: # ifdef xATR1
244: if (tTf(24,0))
245: {
246: printf("In Search_btree: searching for tid %ld\n", mtid);
247: printdesc(&Btreesec);
248: }
249: # endif
250: clearkeys(&Btreesec);
251: setkey(&Btreesec, key, &mtid, 1);
252: if (!getequal(&Btreesec, key, tup, &tid))
253: bmove(tup + LIDSIZE, tidloc, LIDSIZE);
254: else
255: syserr("search_btree:can't find mtid %ld in btree", mtid);
256: # ifdef xATR1
257: if (tTf(24,0))
258: printup(&Btreesec, tup);
259: # endif
260: }
261:
262: /*
263: ** Linearly searches the leaves of the BTree for a desired tid
264: **
265: ** Parameters :
266: ** tree - BTree file name (I)
267: ** tid - desired tid value (I)
268: ** tidloc - location of the desired tid (O)
269: */
270:
271: lin_search(level, tid, tidloc, lid, tupcnt)
272:
273: int level;
274: long tid;
275: TID *tidloc;
276: long lid[];
277: long tupcnt;
278: {
279: struct locator block;
280: register int i;
281: long page, t, next;
282: int found;
283: long nextpage, count;
284: int forward, first;
285:
286: page = RT;
287: for (i = 0; i < level - 1; ++i)
288: {
289: t = get_tid(page, lid[i], &block);
290: page = t;
291: }
292:
293: found = 0;
294: forward = 0;
295: first = 1;
296: do
297: {
298: if (!forward)
299: {
300: get_node(page, &block.page);
301: next = block.page.nexttree;
302: }
303: count = 0;
304:
305: /* start at leftmost leaf */
306: do
307: {
308: get_node(page, &block.page);
309: if (forward)
310: nextpage = block.page.nexttree;
311: else
312: nextpage = block.page.prevtree;
313: get_tid(page, 1, &block);
314: for ( ; ; )
315: {
316: /* search through leaf */
317: for (i = 0; i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] != tid; ++i)
318: {
319: if (!first)
320: ++count;
321: }
322: if (i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] == tid)
323: {
324: found = 1;
325: break; /* tid found */
326: }
327: first = 0;
328: if (!(block.pageno = block.page.node.leafnode.nextleaf) || count >= tupcnt)
329: break; /* all leaves exhausted */
330: else
331: /* try leaf to the right */
332: get_node(block.pageno, &block.page);
333: }
334: if (found || count >= tupcnt)
335: break;
336: } while (page = nextpage);
337: nextpage = next;
338: forward = !forward;
339: } while (forward != 0 && !found);
340: if (!found)
341: syserr("search_btree: tid not found %ld", tid);
342: else
343: {
344: stuff_page(tidloc, &block.pageno);
345: tidloc->line_id = block.page.node.leafnode.tid_loc[i];
346: }
347: }
348:
349: /*
350: ** Determines the value corresponding to the very last lid in the
351: ** BTree.
352: **
353: ** Parameters :
354: ** tree - BTree file name (I)
355: **
356: ** Returns :
357: ** value of last lid
358: */
359: long
360: last_lid(rootpage)
361:
362: long rootpage;
363:
364: {
365: register int i;
366: long lid;
367: struct BTreeNode root;
368:
369: lid = 0;
370: get_node(rootpage, &root);
371: if (root.nodetype == 'L')
372: lid = root.nelmts;
373: else
374: for (i = 0; i < root.nelmts; ++i)
375: lid += root.node.intnode.key[i];
376: ++lid;
377: return(lid);
378: }
379:
380: /*
381: ** Changes the tid value stored in the leaf of a BTree node
382: **
383: ** Parameters :
384: ** tree - BTree file name (I)
385: ** tid - new tid value (I)
386: ** tidloc - location of tid to be replaced (I)
387: */
388:
389: replace_btree(tid, tidloc)
390:
391: long tid;
392: register TID *tidloc;
393:
394: {
395: long pageno;
396: struct BTreeNode p;
397:
398: pluck_page(tidloc, &pageno);
399: get_node(pageno, &p);
400: p.node.leafnode.tid_pos[tidloc->line_id] = tid;
401: write_node(pageno, &p);
402: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.