![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to delete_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 delete_btree.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil |
1.1 root 1: # include <stdio.h>
2: # include <btree.h>
3: # include <ingres.h>
4: # include <batch.h>
5: # include <sccs.h>
6:
7: SCCSID(@(#)delete_btree.c 8.1 12/31/84)
8:
9: /* DELETE_BTREE -- BTree deletion routine
10: **
11: ** Deletes a tid from a leaf node and adjusts all values up the tree
12: **
13: ** Parameters :
14: ** tree - BTree filename (I)
15: ** lid - lid to be deleted (I)
16: **
17: ** Returns :
18: ** > 0 success
19: ** < 0 bad lid
20: */
21:
22: delete_btree(lid, level)
23: long lid[];
24: register int level;
25:
26: {
27: register int i, j;
28: struct locator tid[MAXLID];
29: register int save;
30: int num[MAXLID];
31: int del[MAXLID];
32: long page[MAXLID + 1], t;
33: struct BTreeNode temp;
34:
35: # ifdef xATR1
36: if(tTf(24,0))
37: printf("deleting lid %ld from tree ", lid);
38: # endif
39:
40: page[0] = RT;
41: for (i = 0; i < level; ++i)
42: {
43: if ((t = get_tid(page[i], lid[i], &tid[i])) < 0)
44: return(-1);
45: del[i] = 0;
46: num[i] = tid[i].page.nelmts;
47: page[i+1] = t;
48: }
49:
50: del[level-1] = 1;
51: for (i = level - 2; i >= 0; --i)
52: {
53: if (num[i + 1] == 1 && del[i + 1] == 1)
54: del[i] = 1;
55: }
56:
57: for (i = 0; i < level; ++i)
58: {
59: if (del[i])
60: {
61: ++Repl_cnt[i];
62: for (j = i - 1; j >= 0; --j)
63: Prev_lid[j] = lid[j];
64: /* remove tid from leaf */
65: if (tid[i].offset != tid[i].page.nelmts - 1)
66: {
67: save = tid[i].page.node.leafnode.tid_loc[tid[i].offset];
68: for (j = tid[i].offset; j < tid[i].page.nelmts; ++j)
69: {
70: tid[i].page.node.leafnode.tid_loc[j] =
71: tid[i].page.node.leafnode.tid_loc[j + 1];
72: tid[i].page.node.leafnode.back_ptr[tid[i].page.node.leafnode.tid_loc[j]] = j;
73: }
74: tid[i].page.node.leafnode.tid_loc[tid[i].page.nelmts - 1] = save;
75: tid[i].page.node.leafnode.back_ptr[save] = tid[i].page.nelmts - 1;
76: }
77: --tid[i].page.nelmts;
78:
79: if (tid[i].page.nelmts != 0)
80: {
81: write_node(tid[i].pageno, &tid[i].page);
82: /* leaf is now empty as a result of deletion, decrement keys
83: ** up tree */
84: tracepath(page[i], &tid[i], -1);
85: }
86:
87: else if (tid[i].pageno != page[i])
88: {
89: /* key/ptr pair corresponding to empty leaf must be removed */
90: delete_key(page[i], &tid[i]);
91: }
92: else if (lid[i] == 1 && page[i] != RT)
93: {
94: if (tid[i].page.prevtree)
95: {
96: get_node(tid[i].page.prevtree, &temp);
97: temp.nexttree = tid[i].page.nexttree;
98: write_node(tid[i].page.prevtree, &temp);
99: }
100: if (tid[i].page.nexttree)
101: {
102: get_node(tid[i].page.nexttree, &temp);
103: temp.prevtree = tid[i].page.prevtree;
104: write_node(tid[i].page.nexttree, &temp);
105: }
106: return_page(page[i]);
107: }
108: else
109: write_node(page[i], &tid[i].page);
110: }
111: }
112: return(0);
113: }
114:
115: /* Returns an empty page to the empty file space list. Removes key/ptr
116: ** pair corresponding to empty node from tree. Combines and distributes
117: ** pairs if a node has less than the minimum number of values. Adjusts
118: ** all values up the tree.
119: **
120: ** Parameters :
121: ** tree - BTree filename (I)
122: ** empty - empty node (I)
123: */
124:
125: delete_key(rootpage, empty)
126:
127: long rootpage;
128: register struct locator *empty;
129: {
130: struct locator prt, gprt, sibling;
131: register int i;
132: struct BTreeNode new, temp;
133: long pkey, skey;
134: extern char *Fileset;
135: char replbatch[MAXNAME + 4];
136: FILE *fp;
137: long count, page;
138: TID oldtid, newtid;
139:
140: /* find parent corresponding to empty node, and remove ptr/key pair
141: ** from parent */
142: prt.pageno = empty->page.parent;
143: parentkey(empty->pageno, &prt);
144: if (prt.offset != prt.page.nelmts - 1)
145: {
146: for (i = prt.offset; i < prt.page.nelmts; ++i)
147: {
148: prt.page.node.intnode.ptr[i] =
149: prt.page.node.intnode.ptr[i + 1];
150: prt.page.node.intnode.key[i] =
151: prt.page.node.intnode.key[i + 1];
152: }
153: }
154: --prt.page.nelmts;
155:
156: if (empty->page.nodetype == 'L')
157: /* adjust previous and next fields of leaves */
158: {
159: if (empty->page.node.leafnode.nextleaf != 0)
160: {
161: get_node(empty->page.node.leafnode.nextleaf, &temp);
162: temp.node.leafnode.prevleaf = empty->page.node.leafnode.prevleaf;
163: write_node(empty->page.node.leafnode.nextleaf, &temp);
164: }
165: if (empty->page.node.leafnode.prevleaf != 0)
166: {
167: get_node(empty->page.node.leafnode.prevleaf, &temp);
168: temp.node.leafnode.nextleaf = empty->page.node.leafnode.nextleaf;
169: write_node(empty->page.node.leafnode.prevleaf, &temp);
170: }
171: }
172:
173: /* return empty node to empty file space */
174: return_page(empty->pageno);
175:
176: if (prt.page.nelmts >= (int) ((float) MAXPTRS / 2 + 0.5))
177: {
178: write_node(prt.pageno, &prt.page);
179: /* node still has proper number of elements, decrement key
180: ** values up the tree */
181: tracepath(rootpage, &prt, -1);
182: }
183:
184: else if (prt.pageno == rootpage && prt.page.nelmts < 2)
185: /* root has only one child, a leaf; root becomes leaf node */
186: {
187: /* move leaf values into root; root's position always remains
188: ** the same */
189: get_node(prt.page.node.intnode.ptr[0], &new);
190: new.parent = prt.page.parent;
191: write_node(rootpage, &new);
192: return_page(prt.page.node.intnode.ptr[0]);
193: if (new.nodetype == 'I')
194: {
195: for (i = 0; i < new.nelmts; ++i)
196: {
197: get_node(new.node.intnode.ptr[i], &temp);
198: temp.parent = rootpage;
199: write_node(new.node.intnode.ptr[i], &temp);
200: }
201: }
202: else
203: {
204: /* btree tid is being changed, must be reflected in
205: ** secondary btree relation
206: */
207: concat(REPL_IN, Fileset, replbatch);
208: if ((fp = fopen(replbatch, "w")) == NULL)
209: syserr("can't open replbatch in delete_btree");
210: count = 0;
211: page = 0l;
212: stuff_page(&newtid, &page);
213: stuff_page(&oldtid, &prt.page.node.intnode.ptr[0]);
214: for (i = 0; i < new.nelmts; ++i)
215: {
216: oldtid.line_id = newtid.line_id = new.node.leafnode.tid_loc[i];
217: if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
218: syserr("write error in delete_btree");
219: if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
220: syserr("write error in delete_btree");
221: ++count;
222: }
223: fclose(fp);
224: repl_btree(replbatch, count);
225: unlink(replbatch);
226: unlink(ztack(REPL_OUT, Fileset));
227: }
228: }
229:
230: else if (prt.pageno != rootpage)
231: {
232: /* find the grandparent of the empty node */
233: gprt.pageno = prt.page.parent;
234: parentkey(prt.pageno, &gprt);
235: if (gprt.page.nelmts - 1 != gprt.offset)
236: {
237: /* determine the right sibling of the parent node */
238: sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
239: get_node(sibling.pageno, &sibling.page);
240:
241: if (sibling.page.nelmts > MAXPTRS / 2 + 1)
242: /* distribute key/ptr pairs of parent and right sibling
243: ** between the two nodes (since there are sufficient
244: ** pairs to guarantee that both will have at the least
245: ** the minimum number of required children) */
246: {
247: distribute(&prt, &sibling, &pkey, &skey);
248: /* adjust key values in grandparent */
249: gprt.page.node.intnode.key[gprt.offset] = pkey;
250: gprt.page.node.intnode.key[gprt.offset + 1] = skey;
251: write_node(gprt.pageno, &gprt.page);
252: tracepath(rootpage, &gprt, -1);
253: return;
254: }
255: }
256: if (gprt.offset != 0)
257: {
258: /* determine the left sibling of the parent node */
259: sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset - 1];
260: get_node(sibling.pageno, &sibling.page);
261:
262: if (sibling.page.nelmts > MAXPTRS / 2 + 1)
263: /* distribute key/ptr pairs of parent and left sibling
264: ** between the two nodes */
265: {
266: distribute(&sibling, &prt, &skey, &pkey);
267: gprt.page.node.intnode.key[gprt.offset - 1] = skey;
268: gprt.page.node.intnode.key[gprt.offset] = pkey;
269: write_node(gprt.pageno, &gprt.page);
270: tracepath(rootpage, &gprt, -1);
271: return;
272: }
273: }
274:
275: if (gprt.page.nelmts - 1 != gprt.offset)
276: /* combine parent node with its right sibling */
277: {
278: sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
279: get_node(sibling.pageno, &sibling.page);
280: combine(&prt, &sibling);
281: }
282: else
283: /* combine parent node with its left sibling */
284: {
285: sibling.pageno = gprt.page.node.intnode.ptr[gprt.offset - 1];
286: get_node(sibling.pageno, &sibling.page);
287: combine(&sibling, &prt);
288: /* grandparent should point to newly combined block,
289: ** the left sibling */
290: --gprt.offset;
291: }
292:
293: get_node(gprt.page.node.intnode.ptr[gprt.offset], &new);
294: if (gprt.pageno == rootpage && gprt.page.nelmts == 2)
295: /* root has only one child, reduce B-Tree level */
296: {
297: /* only child becomes root */
298: new.parent = gprt.page.parent;
299: write_node(rootpage, &new);
300:
301: /* make sure "new's" children's parent is the root */
302: for (i = 0; i < new.nelmts; ++i)
303: {
304: get_node(new.node.intnode.ptr[i], &temp);
305: temp.parent = rootpage;
306: write_node(new.node.intnode.ptr[i], &temp);
307: }
308: /* both of root's children empty */
309: return_page(gprt.page.node.intnode.ptr[gprt.offset + 1]);
310: return_page(gprt.page.node.intnode.ptr[gprt.offset]);
311: }
312:
313: else
314: {
315: /* adjust key value in grandparent node */
316: pkey = 0;
317: for (i = 0; i < new.nelmts; ++i)
318: pkey += new.node.intnode.key[i];
319: gprt.page.node.intnode.key[gprt.offset] = pkey;
320: write_node(gprt.pageno, &gprt.page);
321:
322: /* remove ptr/key pair corresponding to empty node */
323: gprt.pageno = gprt.page.node.intnode.ptr[gprt.offset + 1];
324: get_node(gprt.pageno, &gprt.page);
325: delete_key(rootpage, &gprt);
326: }
327:
328: }
329: }
330:
331: /* Divides key/ptr pairs between the left and right nodes, so both will
332: ** have the proper number of elements.
333: **
334: ** Parameters :
335: ** tree - BTree filename (I)
336: ** left - left node (I, O)
337: ** right - "left's" right sibling (I, O)
338: ** lkey - key value of the parent of left node (O)
339: ** rkey - key value of the parent of right node (O)
340: */
341:
342: distribute(left, right, lkey, rkey)
343:
344: register struct locator *left, *right;
345: int *lkey, *rkey;
346: {
347: register int i, move;
348: struct BTreeNode temp;
349:
350: if (right->page.nelmts > left->page.nelmts)
351: /* move elements from the right node to the left node */
352: {
353: move = MAXPTRS / 2 - left->page.nelmts;
354:
355: for (i = 1; i <= move; ++i)
356: /* move first part of right node into the end of the left node */
357: {
358: left->page.node.intnode.ptr[i + left->page.nelmts] =
359: right->page.node.intnode.ptr[i - 1];
360: left->page.node.intnode.key[i + left->page.nelmts] =
361: right->page.node.intnode.key[i - 1];
362: /* adjust parents of children whose parents have been
363: ** moved */
364: get_node(left->page.node.intnode.ptr[i + left->page.nelmts], &temp);
365: temp.parent = left->pageno;
366: write_node(left->page.node.intnode.ptr[i + left->page.nelmts], &temp);
367: }
368: left->page.nelmts += move;
369:
370: for (i = move; i < right->page.nelmts; ++i)
371: /* flush right node values to the left */
372: {
373: right->page.node.intnode.ptr[i - move] =
374: right->page.node.intnode.ptr[i];
375: right->page.node.intnode.key[i - move] =
376: right->page.node.intnode.key[i];
377: }
378: right->page.nelmts -= move;
379: }
380:
381: else
382: /* move left node values to the right node */
383: {
384: move = MAXPTRS / 2 - right->page.nelmts + 1;
385:
386: /* move right node values to the right to make room for left
387: ** node values */
388: for (i = right->page.nelmts - 1; i >= 0; --i)
389: {
390: right->page.node.intnode.ptr[i + move] =
391: right->page.node.intnode.ptr[i];
392: right->page.node.intnode.key[i + move] =
393: right->page.node.intnode.key[i];
394: }
395:
396: /* move latter part of left node into the now free space at the
397: ** beginning of the right node */
398: for (i = 0; i < move; ++i)
399: {
400: right->page.node.intnode.ptr[i] =
401: left->page.node.intnode.ptr[left->page.nelmts - move + i];
402: right->page.node.intnode.key[i] =
403: left->page.node.intnode.key[left->page.nelmts - move + i];
404: /* adjust parents of children whose parents have been
405: ** moved */
406: get_node(right->page.node.intnode.ptr[i], &temp);
407: temp.parent = right->pageno;
408: write_node(right->page.node.intnode.ptr[i], &temp);
409: }
410: left->page.nelmts -= move;
411: right->page.nelmts += move;
412: }
413:
414: /* calculate key values for parents of the left and right nodes */
415: *lkey = 0;
416: for (i = 0; i < left->page.nelmts; ++i)
417: *lkey += left->page.node.intnode.key[i];
418: *rkey = 0;
419: for (i = 0; i < right->page.nelmts; ++i)
420: *rkey += right->page.node.intnode.key[i];
421: write_node(left->pageno, &left->page);
422: write_node(right->pageno, &right->page);
423: }
424:
425: /* Combines left and right nodes together to form one node.
426: **
427: ** Parameters :
428: ** tree - BTree filename (I)
429: ** left - left node (I, O)
430: ** right - "left's" right sibling (I)
431: */
432:
433: combine(left, right)
434:
435: register struct locator *left, *right;
436: {
437: register int i;
438: struct BTreeNode temp;
439:
440: /* move all ptr/key values in the right node to the end of the left node */
441: for (i = 0; i < right->page.nelmts; ++i)
442: {
443: left->page.node.intnode.ptr[left->page.nelmts + i] =
444: right->page.node.intnode.ptr[i];
445: left->page.node.intnode.key[left->page.nelmts + i] =
446: right->page.node.intnode.key[i];
447: /* adjust parents of children whose parents have been moved */
448: get_node(left->page.node.intnode.ptr[left->page.nelmts + i], &temp);
449: temp.parent = left->pageno;
450: write_node(left->page.node.intnode.ptr[left->page.nelmts + i], &temp);
451: }
452: left->page.nelmts += right->page.nelmts;
453: write_node(left->pageno, &left->page);
454: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.