![[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.