![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to insert_btree.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 insert_btree.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 <batch.h>
4: # include <symbol.h>
5: # include <sccs.h>
6:
7: SCCSID(@(#)insert_btree.c 8.1 12/31/84)
8:
9: /* INSERT_BTREE -- BTree insertion routine
10: **
11: ** Insert a tid into the BTree at the position corresponding to its lid.
12: ** Split the leaf if necessary and adjust all values up the tree.
13: **
14: ** Parameters :
15: ** tree - BTree filename (I)
16: ** lid - given lid (I)
17: ** tid - tid to be inserted into BTree leaf (I)
18: ** tidpos - location where tid was inserted (O)
19: **
20: ** Returns :
21: ** -1 lid position does not exist
22: ** 0 successful insertion
23: */
24:
25: insert_btree(tree, rootpage, lid, tid, tidpos, create)
26:
27: char *tree;
28: long rootpage;
29: long lid;
30: long *tid;
31: register TID *tidpos;
32: char create;
33: {
34: register int i, j, start;
35: struct locator block, p;
36: struct BTreeNode newblock, temp, newroot;
37: short rblock, tline;
38: long newpage, tpage;
39: long get_tid(), new_page();
40: int save;
41: char replbatch[MAXNAME + 4];
42: FILE *fp;
43: TID oldtid, newtid;
44: long count, page, childpage;
45: extern char *Fileset;
46: extern DESC Btreesec;
47:
48: # ifdef xATR1
49: if (tTf(24,0))
50: printf("inserting lid %ld into btree at rootpage %d", lid, rootpage);
51: # endif
52:
53: /* find location of desired lid in B-Tree */
54: if (get_tid(rootpage, lid, &block) < -1)
55: return(-1);
56:
57: if (newroot.depth = create)
58: {
59: if (save = block.offset)
60: newroot.prevtree = block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[save -1]];
61: else
62: {
63: if (!block.page.prevtree)
64: newroot.prevtree = 0;
65: else
66: {
67: get_node(block.page.prevtree, &temp);
68: newroot.prevtree = temp.node.leafnode.tid_pos[temp.node.leafnode.tid_loc[temp.nelmts - 1]];
69: }
70: }
71: if (save <= block.page.nelmts - 1 && block.page.nelmts)
72: newroot.nexttree = block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[save]];
73: else
74: {
75: if (!block.page.nexttree)
76: newroot.nexttree = 0;
77: else
78: {
79: get_node(block.page.nexttree, &temp);
80: newroot.nexttree = temp.node.leafnode.tid_pos[temp.node.leafnode.tid_loc[0]];
81: }
82: }
83: *tid = new_page(tree);
84: if (block.pageno == RT)
85: get_node(RT, &block.page);
86: if (newroot.prevtree)
87: {
88: get_node(newroot.prevtree, &temp);
89: temp.nexttree = *tid;
90: write_node(newroot.prevtree, &temp);
91: }
92: if (newroot.nexttree)
93: {
94: get_node(newroot.nexttree, &temp);
95: temp.prevtree = *tid;
96: write_node(newroot.nexttree, &temp);
97: }
98: stuff_page(&newroot.prttree, &block.pageno);
99: newroot.nodetype = 'L';
100: newroot.nelmts = 0;
101: newroot.parent = 0;
102: newroot.node.leafnode.prevleaf = 0;
103: newroot.node.leafnode.nextleaf = 0;
104: for (i = 0; i < MAXLEAVES; ++i)
105: newroot.node.leafnode.tid_loc[i] = newroot.node.leafnode.back_ptr[i] = i;
106: }
107:
108: if (block.page.nelmts != MAXLEAVES)
109: /* insert tid into its proper position in leaf */
110: {
111: save = block.page.node.leafnode.tid_loc[block.page.nelmts];
112: /* move other tids down to make room for new tid */
113: for (i = block.page.nelmts - 1; i >= block.offset; --i)
114: {
115: block.page.node.leafnode.tid_loc[i + 1] =
116: block.page.node.leafnode.tid_loc[i];
117: block.page.node.leafnode.back_ptr[block.page.node.leafnode.tid_loc[i]] = i + 1;
118: }
119: block.page.node.leafnode.tid_loc[block.offset] = save;
120: block.page.node.leafnode.tid_pos[save] = *tid;
121: block.page.node.leafnode.back_ptr[save] = block.offset;
122: ++block.page.nelmts;
123: write_node(block.pageno, &block.page);
124: if (create)
125: newroot.prttree.line_id = save;
126:
127: /* trace up B-Tree, incrementing key values */
128: tracepath(rootpage, &block, 1);
129:
130: tpage = block.pageno;
131: tline = save;
132: }
133:
134: else
135: /* leaf is full, must be split */
136: {
137: /* determine where to split leaf */
138: start = MAXLEAVES / 2;
139: rblock = 0;
140:
141: if (block.offset > start)
142: /* new tid will be inserted in the new leaf */
143: {
144: ++start;
145: rblock = 1;
146: }
147:
148: /* readjust all values in the old leaf and assign them for
149: ** the new leaf */
150:
151: block.page.nelmts = start; /* assume new tid will be
152: ** inserted into new leaf */
153: newpage = new_page(tree);
154: newblock.nodetype = 'L';
155: for (i = 0; i < MAXLEAVES; ++i)
156: newblock.node.leafnode.tid_loc[i] = newblock.node.leafnode.back_ptr[i] = i;
157: newblock.nelmts = MAXLEAVES + 1 - start;
158: newblock.parent = block.page.parent;
159: newblock.depth = 0;
160:
161: if (newblock.node.leafnode.nextleaf = block.page.node.leafnode.nextleaf)
162: {
163: get_node(newblock.node.leafnode.nextleaf, &temp);
164: temp.node.leafnode.prevleaf = newpage;
165: write_node(newblock.node.leafnode.nextleaf, &temp);
166: }
167: block.page.node.leafnode.nextleaf = newpage;
168: newblock.node.leafnode.prevleaf = block.pageno;
169:
170: /* create file for storing tids that must be replaced in btree
171: ** secondary relation
172: */
173: if (!bequal("_SYS", tree, 4) && !create)
174: {
175: concat(REPL_IN, Fileset, replbatch);
176: if ((fp = fopen(replbatch, "w")) == NULL)
177: syserr("can't open batch file in insert_btree");
178: count = 0;
179: stuff_page(&oldtid, &block.pageno);
180: stuff_page(&newtid, &newpage);
181: }
182:
183: /* copy the right half of the old leaf onto the new leaf */
184: for (i = 0, j = start; j < MAXLEAVES || rblock == 1; ++i)
185: {
186: if (j == block.offset && rblock == 1)
187: /* current position in new leaf corresponds to position
188: ** of new tid */
189: {
190: newblock.node.leafnode.tid_pos[newblock.node.leafnode.tid_loc[i]] = *tid;
191: tline = newblock.node.leafnode.tid_loc[i];
192: /* indicate that tid has been inserted */
193: rblock = -1;
194: }
195: else
196: {
197: childpage = newblock.node.leafnode.tid_pos[newblock.node.leafnode.tid_loc[i]] =
198: block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[j]];
199: if (create)
200: {
201: get_node(childpage, &temp);
202: stuff_page(&temp.prttree, &newpage);
203: temp.prttree.line_id = newblock.node.leafnode.tid_loc[i];
204: write_node(childpage, &temp);
205: }
206: if (!bequal("_SYS", tree, 4) && !create)
207: {
208: oldtid.line_id = block.page.node.leafnode.tid_loc[j];
209: newtid.line_id = newblock.node.leafnode.tid_loc[i];
210: if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
211: syserr("write error in insert_btree");
212: if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
213: syserr("write error in insert_btree");
214: ++count;
215: }
216: ++j;
217: }
218: }
219: if (!bequal("_SYS", tree, 4) && !create)
220: {
221: fclose(fp);
222: repl_btree(replbatch, count);
223: }
224:
225: if (!rblock)
226: /* new tid belongs in old leaf, insert it into its proper
227: ** position */
228: {
229: save = block.page.node.leafnode.tid_loc[block.page.nelmts];
230: for (i = block.page.nelmts - 1; i >= block.offset; --i)
231: {
232: block.page.node.leafnode.tid_loc[i + 1] =
233: block.page.node.leafnode.tid_loc[i];
234: block.page.node.leafnode.back_ptr[block.page.node.leafnode.tid_loc[i]] = i + 1;
235: }
236: block.page.node.leafnode.tid_loc[block.offset] = save;
237: block.page.node.leafnode.tid_pos[save] = *tid;
238: block.page.node.leafnode.back_ptr[save] = block.offset;
239: tline = save;
240: /* readjust element counts to reflect that tid has been
241: ** placed in the old leaf */
242: ++block.page.nelmts;
243: --newblock.nelmts;
244: }
245:
246: if (block.pageno == rootpage)
247: {
248: /* split leaf was the root, a new level to the B-Tree
249: ** must be added */
250: rootsplit(tree, rootpage, &block, newpage, block.page.nelmts, newblock.nelmts);
251: newblock.parent = rootpage;
252: write_node(block.pageno, &block.page);
253: newblock.node.leafnode.prevleaf = block.pageno;
254: write_node(newpage, &newblock);
255:
256: if (create)
257: {
258: for (i = 0; i < block.page.nelmts; ++ i)
259: {
260: get_node(block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]], &temp);
261: stuff_page(&temp.prttree, &block.pageno);
262: write_node(block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]], &temp);
263: }
264: }
265: /* btree page has changed */
266: if (!bequal("_SYS", tree, 4) && !create)
267: {
268: concat(REPL_IN, Fileset, replbatch);
269: if ((fp = fopen(replbatch, "w")) == NULL)
270: syserr("can't open batch file in insert_btree");
271: count = 0;
272: page = 0l;
273: stuff_page(&oldtid, &page);
274: stuff_page(&newtid, &block.pageno);
275: for (i = 0; i < block.page.nelmts; ++i)
276: {
277: if (rblock || block.page.node.leafnode.tid_loc[i] != tline)
278: {
279: oldtid.line_id = newtid.line_id = block.page.node.leafnode.tid_loc[i];
280: if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
281: syserr("write error in insert_btree");
282: if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
283: syserr("write error in insert_btree");
284: ++count;
285: }
286: }
287: fclose(fp);
288: repl_btree(replbatch, count);
289: }
290: }
291: else
292: /* insert the pointer and key associated with new leaf into the
293: ** parent of the old leaf */
294: {
295: write_node(block.pageno, &block.page);
296: write_node(newpage, &newblock);
297: p.pageno = block.page.parent;
298: parentkey(block.pageno, &p);
299: p.page.node.intnode.key[p.offset] = block.page.nelmts;
300: insert_key(tree, rootpage, newpage, newblock.nelmts, &p);
301: }
302: tpage = (rblock) ? newpage : block.pageno;
303: }
304: stuff_page(tidpos, &tpage);
305: tidpos->line_id = tline;
306:
307: if (create)
308: write_node(*tid, &newroot);
309:
310: }
311:
312: /*
313: ** Takes a pair of tids from a file and sequentially replaces the
314: ** old tid with the new tid in the secondary btree relation
315: */
316:
317: repl_btree(replbatch, count)
318: register char *replbatch;
319: long count;
320: {
321: register int i, j;
322: TID uptid;
323: DESC d;
324: char tids[2 * LIDSIZE], key[2 * LIDSIZE], newkey[2 * LIDSIZE];
325: extern DESC Btreesec;
326:
327: if (count > 0)
328: {
329: /* set up descriptor for sort */
330: d.reloff[1] = 0;
331: d.reloff[2] = LIDSIZE;
332: d.relfrmt[1] = d.relfrmt[2] = INT;
333: d.relfrml[1] = d.relfrml[2] = LIDSIZE;
334: d.relgiven[1] = 1;
335: d.relgiven[2] = 2;
336: d.reldum.relspec = M_ORDER;
337: d.reldum.relatts = 2;
338: d.reldum.relwid = 2 * LIDSIZE;
339: sortfile(replbatch, &d, FALSE);
340: if ((Repl_outfp = fopen(ztack(REPL_OUT, Fileset), "r")) == NULL)
341: syserr("can't open replace file after sort in insertbtreee\n");
342: clearkeys(&Btreesec);
343: for (i = 0; i < count; ++i)
344: {
345: if (fread(tids, 1, 2 * LIDSIZE, Repl_outfp) != 2 * LIDSIZE)
346: syserr("read error in insert_btree");
347: setkey(&Btreesec, key, tids, 2);
348: if (getequal(&Btreesec, key, newkey, &uptid))
349: {
350: printup(&Btreesec, key);
351: syserr("getequal error in insert_btree");
352: }
353: /* place new tid in place */
354: setkey(&Btreesec, newkey, tids + LIDSIZE, 2);
355: if (j = replace(&Btreesec, &uptid, newkey, TRUE))
356: if (j == 1)
357: continue;
358: else
359: syserr("bad replace in insert_btree");
360: }
361: fclose(Repl_outfp);
362: unlink(replbatch);
363: unlink(ztack(REPL_OUT, Fileset));
364: }
365: }
366:
367: /* Insert a key/ptr pair into a node, splitting nodes if necessary and
368: ** adjusting values up the tree.
369: **
370: ** Parameters :
371: ** tree - BTree filename (I)
372: ** p - page number of newly formed node (I)
373: ** k - key value of newly formed node (I)
374: ** pkey - information about the node whose ptr/key pair is to
375: ** be inserted (I, O)
376: */
377:
378: insert_key(tree, rootpage, p, k, pkey)
379:
380: char *tree;
381: long rootpage;
382: long p, k;
383: register struct locator *pkey;
384: {
385: register int i, j, start;
386: struct BTreeNode newblock, temp;
387: long newpage, oldkey, newkey;
388: struct locator prt;
389: short rblock;
390: long new_page();
391:
392: if (pkey->page.nelmts != MAXPTRS)
393: /* insert pointer/key pair into proper position in node by moving
394: ** other pairs down node */
395: {
396: for (i = pkey->page.nelmts - 1; i >= pkey->offset + 1; --i)
397: {
398: pkey->page.node.intnode.ptr[i + 1] =
399: pkey->page.node.intnode.ptr[i];
400: pkey->page.node.intnode.key[i + 1] =
401: pkey->page.node.intnode.key[i];
402: }
403: ++pkey->page.nelmts;
404: pkey->page.node.intnode.ptr[pkey->offset + 1] = p;
405: pkey->page.node.intnode.key[pkey->offset + 1] = k;
406:
407: write_node(pkey->pageno, &pkey->page);
408:
409: /* trace up B-Tree incrementing keys */
410: tracepath(rootpage, pkey, 1);
411: }
412:
413: else
414: /* node is full, must be split */
415: {
416: /* determine where split will be made */
417: start = MAXPTRS / 2;
418: rblock = 0;
419:
420: if (pkey->offset + 1 > start)
421: /* ptr/key pair will be inserted in new node */
422: {
423: ++start;
424: rblock = 1;
425: }
426:
427: /* readjust old node values and create new node values */
428: pkey->page.nelmts = start;
429: newpage = new_page(tree);
430: newblock.nodetype = 'I';
431: newblock.nelmts = MAXPTRS + 1 - start;
432: newblock.parent = pkey->page.parent;
433: newblock.depth = 0;
434:
435: /* copy right side of old node into new node */
436:
437: for (i = 0, j = start; j < MAXPTRS || rblock == 1; ++i)
438: {
439: if (j == pkey->offset + 1 && rblock == 1)
440: /* node position corresponds to that of new ptr/key pair */
441: {
442: newblock.node.intnode.ptr[i] = p;
443: newblock.node.intnode.key[i] = k;
444: /* make sure children of newblock have proper
445: ** parent */
446: get_node(p, &temp);
447: temp.parent = newpage;
448: write_node(p, &temp);
449:
450: rblock = -1;
451: }
452: else
453: {
454: newblock.node.intnode.ptr[i] =
455: pkey->page.node.intnode.ptr[j];
456: newblock.node.intnode.key[i] =
457: pkey->page.node.intnode.key[j];
458: /* make sure children of newblock have proper
459: ** parent */
460: get_node(newblock.node.intnode.ptr[i], &temp);
461: temp.parent = newpage;
462: write_node(newblock.node.intnode.ptr[i], &temp);
463: ++j;
464: }
465: }
466:
467: if (!rblock)
468: /* insert new ptr/key pair into proper position in old node */
469: {
470: for (i = pkey->page.nelmts - 1; i >= pkey->offset + 1; --i)
471: {
472: pkey->page.node.intnode.ptr[i + 1] =
473: pkey->page.node.intnode.ptr[i];
474: pkey->page.node.intnode.key[i + 1] =
475: pkey->page.node.intnode.key[i];
476: }
477: pkey->page.node.intnode.ptr[pkey->offset + 1] = p;
478: pkey->page.node.intnode.key[pkey->offset + 1] = k;
479: ++pkey->page.nelmts;
480: --newblock.nelmts;
481: }
482:
483: /* calculate the key values of the old and new nodes */
484: oldkey = 0;
485: for (i = 0; i < pkey->page.nelmts; ++i)
486: oldkey += pkey->page.node.intnode.key[i];
487: newkey = 0;
488: for (i = 0; i < newblock.nelmts; ++i)
489: newkey += newblock.node.intnode.key[i];
490:
491: if (pkey->pageno == rootpage)
492: {
493: /* split node was root, add a new level to B-Tree */
494: rootsplit(tree, rootpage, pkey, newpage, oldkey, newkey);
495: newblock.parent = rootpage;
496: write_node(pkey->pageno, &pkey->page);
497: write_node(newpage, &newblock);
498: }
499:
500: else
501: /* recursively add ptr/key pair corresponding to new node into
502: ** the parent of the old node */
503: {
504: write_node(pkey->pageno, &pkey->page);
505: write_node(newpage, &newblock);
506: prt.pageno = pkey->page.parent;
507: parentkey(pkey->pageno, &prt);
508: prt.page.node.intnode.key[prt.offset] = oldkey;
509: insert_key(tree, rootpage, newpage, newkey, &prt);
510: }
511: }
512: }
513:
514: /* Form a new root with two children since the old root was split.
515: **
516: ** Parameters :
517: ** tree - BTree filename (I)
518: ** oldroot - split root (I, O)
519: ** rpageno - page number of new root's right child (I)
520: ** rkey - key of new root's right child (I)
521: */
522:
523: rootsplit(tree, rootpage, oldroot, rpageno, lkey, rkey)
524:
525: char *tree;
526: long rootpage;
527: register struct locator *oldroot;
528: long rpageno, lkey, rkey;
529: {
530: struct BTreeNode newroot, temp;
531: long i;
532:
533: /* get a new page for the former root */
534: oldroot->pageno = new_page(tree);
535:
536: newroot.depth = oldroot->page.depth;
537: newroot.prevtree = oldroot->page.prevtree;
538: newroot.nexttree = oldroot->page.nexttree;
539: bmove(&oldroot->page.prttree, &newroot.prttree, LIDSIZE);
540: newroot.nodetype = 'I';
541: newroot.nelmts = 2;
542: newroot.parent = oldroot->page.parent;
543: oldroot->page.parent = rootpage;
544: oldroot->page.depth = 0;
545: newroot.node.intnode.key[0] = lkey;
546: newroot.node.intnode.ptr[0] = oldroot->pageno;
547: newroot.node.intnode.key[1] = rkey;
548: newroot.node.intnode.ptr[1] = rpageno;
549:
550: write_node(rootpage, &newroot);
551:
552: if (oldroot->page.nodetype == 'I')
553: /* make sure the children of the oldroot have the correct parent */
554: for (i = 0; i < oldroot->page.nelmts; ++i)
555: {
556: get_node(oldroot->page.node.intnode.ptr[i], &temp);
557: temp.parent = oldroot->pageno;
558: write_node(oldroot->page.node.intnode.ptr[i], &temp);
559: }
560: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.