![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to kpvmalloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / dag|
Return to kpvmalloc.c CVS log | Up to [Research Unix] / researchv10dc / cmd / dag |
1.1 ! root 1: /********************************************************************** ! 2: Memory management: malloc(), realloc(), free(). ! 3: ! 4: Kiem-Phong Vo, ulysses!kpv, ! 5: AT&T Bell Laboratories, MH5D102, 201-582-4869. ! 6: ! 7: The following #-parameters may be redefined: ! 8: SEGMENTED: if defined, memory requests are assumed to be ! 9: non-contiguous across calls of GETCORE's. ! 10: GETCORE: a function to get more core memory. If not SEGMENTED, ! 11: GETCORE(0) is assumed to return the next available ! 12: address. Default is 'sbrk'. ! 13: ERRCORE: the error code as returned by GETCORE. ! 14: Default is ((char *)(-1)). ! 15: CORESIZE: a desired unit (measured in bytes) to be used ! 16: with GETCORE. Default is (1024*ALIGN). ! 17: ! 18: This algorithm is based on a best fit strategy with lists of ! 19: free elts maintained in a self-adjusting binary tree. Each list ! 20: contains all elts of the same size. The tree is ordered by size. ! 21: For results on self-adjusting trees, see the paper: ! 22: Self-Adjusting Binary Trees, ! 23: DD Sleator & RE Tarjan, JACM 1985. ! 24: ! 25: The header of a block contains the size of the data part in bytes. ! 26: Since the size of a block is 0%4, the low two bits of the header ! 27: are free and used as follows: ! 28: ! 29: BIT0: 1 for busy (block is in use), 0 for free. ! 30: BIT1: if the block is busy, this bit is 1 if the ! 31: preceding block in contiguous memory is free. ! 32: Otherwise, it is always 0. ! 33: **********************************************************************/ ! 34: ! 35: /* debugging macros */ ! 36: #ifdef DEBUG ! 37: #define ASSERT(p) if(!(p))abort() ! 38: #define COUNT(n) n++ ! 39: static int nmalloc, nrealloc, nfree; ! 40: #else ! 41: #define ASSERT(p) ! 42: #define COUNT(n) ! 43: #endif /*DEBUG*/ ! 44: ! 45: /* function to copy data from one area to another */ ! 46: #ifdef SYSV ! 47: #define memcopy(to,fr,n) memcpy(to,fr,n) ! 48: #endif ! 49: ! 50: #ifdef BSD ! 51: #define memcopy(to,fr,n) bcopy(fr,to,n) ! 52: #endif ! 53: ! 54: #ifndef memcopy ! 55: static memcopy(to,fr,n) ! 56: register char *to, *fr; ! 57: register int n; ! 58: { ! 59: for(; n > 0; --n) ! 60: *to++ = *fr++; ! 61: } ! 62: #endif ! 63: ! 64: /* for conveniences */ ! 65: #define reg register ! 66: #define NULL (0) ! 67: #define WORDSIZE ((int)(sizeof(WORD))) ! 68: #define MINSIZE ((int)(sizeof(TREE)-sizeof(WORD))) ! 69: #define ROUND(s) if(s%WORDSIZE) s += (WORDSIZE - (s%WORDSIZE)) ! 70: ! 71: #ifdef DEBUG32 ! 72: /* The following definitions ease debugging ! 73: ** on a machine in which sizeof(pointer) == sizeof(int) == 4. ! 74: ** These definitions are not portable. ! 75: */ ! 76: #define ALIGN 4 ! 77: typedef int WORD; ! 78: typedef struct _t_ ! 79: { ! 80: unsigned int t_s; ! 81: struct _t_ *t_p; ! 82: struct _t_ *t_l; ! 83: struct _t_ *t_r; ! 84: struct _t_ *t_n; ! 85: struct _t_ *t_d; ! 86: } TREE; ! 87: #define SIZE(b) ((b)->t_s) ! 88: #define AFTER(b) ((b)->t_p) ! 89: #define PARENT(b) ((b)->t_p) ! 90: #define LEFT(b) ((b)->t_l) ! 91: #define RIGHT(b) ((b)->t_r) ! 92: #define LINKFOR(b) ((b)->t_n) ! 93: #define LINKBAK(b) ((b)->t_p) ! 94: ! 95: #else /* !DEBUG32 */ ! 96: /* The following definitions assume that "char *" has the largest size ! 97: ** among all pointer types. If this is not true, PTRSIZE should ! 98: ** be redefined to be the size of the largest pointer type (void * ?). ! 99: ** All of our allocations will be aligned on the least multiple of 4 ! 100: ** that is >= PTRSIZE. ! 101: */ ! 102: #define PTRSIZE ((int)(sizeof(char *))) ! 103: #define ALIGN (PTRSIZE%4 ? PTRSIZE+(4-(PTRSIZE%4)) : PTRSIZE) ! 104: ! 105: /* the proto-word */ ! 106: typedef union _w_ ! 107: { ! 108: unsigned int w_i; /* an int */ ! 109: struct _t_ *w_p; /* a pointer */ ! 110: char w_a[ALIGN]; /* to force alignment */ ! 111: } WORD; ! 112: ! 113: /* structure of a node in the free tree */ ! 114: typedef struct _t_ ! 115: { ! 116: WORD t_s; /* size of this element */ ! 117: WORD t_p; /* parent node */ ! 118: WORD t_l; /* left child */ ! 119: WORD t_r; /* right child */ ! 120: WORD t_n; /* next in link list */ ! 121: WORD t_d; /* dummy to reserve space for self-pointer */ ! 122: } TREE; ! 123: ! 124: /* usable # of bytes in the block */ ! 125: #define SIZE(b) (((b)->t_s).w_i) ! 126: ! 127: /* free tree pointers */ ! 128: #define PARENT(b) (((b)->t_p).w_p) ! 129: #define LEFT(b) (((b)->t_l).w_p) ! 130: #define RIGHT(b) (((b)->t_r).w_p) ! 131: ! 132: /* forward link in lists of small blocks */ ! 133: #define AFTER(b) (((b)->t_p).w_p) ! 134: ! 135: /* forward and backward links for lists in the tree */ ! 136: #define LINKFOR(b) (((b)->t_n).w_p) ! 137: #define LINKBAK(b) (((b)->t_p).w_p) ! 138: ! 139: #endif /* DEBUG32 */ ! 140: ! 141: /* set/test indicator if a block is in the tree or in a list */ ! 142: #define SETNOTREE(b) (LEFT(b) = (TREE *)(-1)) ! 143: #define ISNOTREE(b) (LEFT(b) == (TREE *)(-1)) ! 144: ! 145: /* functions to get information on a block */ ! 146: #define DATA(b) (((char *) (b)) + WORDSIZE) ! 147: #define BLOCK(d) ((TREE *) ((d) - WORDSIZE)) ! 148: #define SELFP(b) ((TREE **) (((char *) (b)) + SIZE(b))) ! 149: #define LAST(b) (*((TREE **) (((char *) (b)) - WORDSIZE))) ! 150: #define NEXT(b) ((TREE *) (((char *) (b)) + SIZE(b) + WORDSIZE)) ! 151: #define BOTTOM(b) ((DATA(b)+SIZE(b)+WORDSIZE) == Baddr) ! 152: ! 153: /* functions to set and test the lowest two bits of a word */ ! 154: #define BIT0 (01) /* ....01 */ ! 155: #define BIT1 (02) /* ...010 */ ! 156: #define BITS01 (03) /* ...011 */ ! 157: #define ISBIT0(w) ((w) & BIT0) ! 158: #define ISBIT1(w) ((w) & BIT1) ! 159: #define SETBIT0(w) ((w) |= BIT0) ! 160: #define SETBIT1(w) ((w) |= BIT1) ! 161: #define CLRBIT0(w) ((w) &= ~BIT0) ! 162: #define CLRBIT1(w) ((w) &= ~BIT1) ! 163: #define SETBITS01(w) ((w) |= BITS01) ! 164: #define CLRBITS01(w) ((w) &= ~BITS01) ! 165: ! 166: /* system call to get more core */ ! 167: #define GETCORE sbrk ! 168: #define ERRCORE ((char *)(-1)) ! 169: #define CORESIZE (1024*ALIGN) ! 170: ! 171: static TREE *Root, /* root of the free tree */ ! 172: *Bottom, /* the last free chunk in the arena */ ! 173: *_morecore(); /* function to get more core */ ! 174: ! 175: static char *Baddr; /* current high address of the arena */ ! 176: ! 177: char *GETCORE(), *malloc(), *realloc(); ! 178: ! 179: ! 180: /* ! 181: ** Allocation of small blocks ! 182: */ ! 183: ! 184: static TREE *List[MINSIZE/WORDSIZE]; /* lists of small blocks */ ! 185: ! 186: static char * _smalloc(size) ! 187: unsigned int size; ! 188: { ! 189: reg TREE *tp, *np; ! 190: reg int i, n; ! 191: ! 192: /* nothing to do */ ! 193: if(size == 0) ! 194: return NULL; ! 195: ! 196: /* list to use */ ! 197: i = size/WORDSIZE - 1; ! 198: ! 199: if(List[i] == NULL) ! 200: { ! 201: /* number of blocks to get at one time */ ! 202: #define NPS (WORDSIZE*8) ! 203: /**/ASSERT((size+WORDSIZE)*NPS >= MINSIZE); ! 204: ! 205: /* get NPS of these block types */ ! 206: if((List[i] = (TREE *) malloc((size+WORDSIZE)*NPS)) == NULL) ! 207: return NULL; ! 208: ! 209: /* make them into a link list */ ! 210: for(n = 0, np = List[i]; n < NPS; ++n) ! 211: { ! 212: tp = np; ! 213: SIZE(tp) = size; ! 214: np = NEXT(tp); ! 215: AFTER(tp) = np; ! 216: } ! 217: AFTER(tp) = NULL; ! 218: } ! 219: ! 220: /* allocate from the head of the queue */ ! 221: tp = List[i]; ! 222: List[i] = AFTER(tp); ! 223: SETBIT0(SIZE(tp)); ! 224: return DATA(tp); ! 225: } ! 226: ! 227: ! 228: ! 229: /* ! 230: ** malloc(). ! 231: */ ! 232: char * malloc(size) ! 233: unsigned int size; ! 234: { ! 235: reg int n; ! 236: reg TREE *tp, *sp; ! 237: ! 238: /**/ COUNT(nmalloc); ! 239: /**/ ASSERT(WORDSIZE == ALIGN); ! 240: ! 241: /* make sure that size is 0 mod ALIGN */ ! 242: ROUND(size); ! 243: ! 244: /* small blocks */ ! 245: if(size < MINSIZE) ! 246: return _smalloc(size); ! 247: ! 248: /* search for an elt of the right size */ ! 249: sp = NULL; ! 250: n = -1; ! 251: if(Root) ! 252: { ! 253: tp = Root; ! 254: while(1) ! 255: { ! 256: /* branch left */ ! 257: if(SIZE(tp) >= size) ! 258: { ! 259: if(n < 0 || n >= SIZE(tp)) ! 260: sp = tp, n = SIZE(tp); ! 261: if(LEFT(tp)) ! 262: tp = LEFT(tp); ! 263: else break; ! 264: } ! 265: else ! 266: { /* branch right */ ! 267: if(RIGHT(tp)) ! 268: tp = RIGHT(tp); ! 269: else break; ! 270: } ! 271: } ! 272: ! 273: if(sp) ! 274: { ! 275: t_delete(sp); ! 276: } ! 277: else if(tp != Root) ! 278: { ! 279: /* make the searched-to element the root */ ! 280: t_splay(tp); ! 281: Root = tp; ! 282: } ! 283: } ! 284: ! 285: /* if found none fitted in the tree */ ! 286: if(!sp) ! 287: { ! 288: if(Bottom && size <= SIZE(Bottom)) ! 289: sp = Bottom; ! 290: else sp = _morecore(size); ! 291: ! 292: /* no more memory */ ! 293: if(!sp) ! 294: return NULL; ! 295: } ! 296: ! 297: /* tell the forward neighbor that we're busy */ ! 298: CLRBIT1(SIZE(NEXT(sp))); /**/ ASSERT(ISBIT0(SIZE(NEXT(sp)))); ! 299: ! 300: /* if the leftover is enough for a new free piece */ ! 301: if((n = (SIZE(sp) - size) - WORDSIZE) >= MINSIZE) ! 302: { ! 303: SIZE(sp) = size; ! 304: tp = NEXT(sp); ! 305: SIZE(tp) = n|BIT0; ! 306: free(DATA(tp)); ! 307: } ! 308: else if(BOTTOM(sp)) ! 309: Bottom = NULL; ! 310: ! 311: /* return the allocated space */ ! 312: SETBIT0(SIZE(sp)); ! 313: return DATA(sp); ! 314: } ! 315: ! 316: ! 317: /* ! 318: ** realloc(). ! 319: ** If the block size is increasing, we try forward merging first. ! 320: ** This is not best-fit but it avoids some data recopying. ! 321: */ ! 322: char * realloc(old,size) ! 323: char *old; ! 324: unsigned int size; ! 325: { ! 326: reg TREE *tp, *np; ! 327: reg int n, ts; ! 328: reg char *new; ! 329: ! 330: /**/ COUNT(nrealloc); ! 331: ! 332: /* make sure that size is 0 mod ALIGN */ ! 333: ROUND(size); ! 334: ! 335: /* pointer to the block */ ! 336: tp = BLOCK(old); ! 337: ts = SIZE(tp); ! 338: ! 339: /* if the block was freed, data has been destroyed. */ ! 340: if(!ISBIT0(ts)) ! 341: return NULL; ! 342: ! 343: /* nothing to do */ ! 344: CLRBITS01(SIZE(tp)); ! 345: if(size == SIZE(tp)) ! 346: { ! 347: SIZE(tp) = ts; ! 348: return old; ! 349: } ! 350: ! 351: /* special cases involving small blocks */ ! 352: if(size < MINSIZE || SIZE(tp) < MINSIZE) ! 353: goto call_malloc; ! 354: ! 355: /* block is increasing in size, try merging the next block */ ! 356: if(size > SIZE(tp)) ! 357: { ! 358: np = NEXT(tp); ! 359: if(!ISBIT0(SIZE(np))) ! 360: { ! 361: /**/ ASSERT(SIZE(np) >= MINSIZE); ! 362: /**/ ASSERT(!ISBIT1(SIZE(np))); ! 363: SIZE(tp) += SIZE(np)+WORDSIZE; ! 364: if(np != Bottom) ! 365: t_delete(np); ! 366: else Bottom = NULL; ! 367: CLRBIT1(SIZE(NEXT(np))); ! 368: } ! 369: ! 370: #ifndef SEGMENTED ! 371: /* not enough & at TRUE end of memory, try extending core */ ! 372: if(size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) ! 373: { ! 374: Bottom = tp; ! 375: _morecore(size); ! 376: } ! 377: #endif /*!SEGMENTED*/ ! 378: } ! 379: ! 380: /* got enough space to use */ ! 381: if(size <= SIZE(tp)) ! 382: { ! 383: if((n = (SIZE(tp) - size) - WORDSIZE) >= MINSIZE) ! 384: { ! 385: SIZE(tp) = size; ! 386: np = NEXT(tp); ! 387: SIZE(np) = n|BIT0; ! 388: free(DATA(np)); ! 389: } ! 390: else if(BOTTOM(tp)) ! 391: Bottom = NULL; ! 392: ! 393: /* the previous block may be free */ ! 394: if(ISBIT1(ts)) ! 395: SETBIT1(SIZE(tp)); ! 396: SETBIT0(SIZE(tp)); ! 397: return old; ! 398: } ! 399: ! 400: /* call malloc to get a new block */ ! 401: call_malloc: ! 402: SETBIT0(SIZE(tp)); ! 403: if(ISBIT1(ts)) ! 404: SETBIT1(SIZE(tp)); ! 405: if((new = malloc(size)) != NULL) ! 406: { ! 407: ts = SIZE(tp); ! 408: CLRBITS01(ts); ! 409: memcopy(new,old,ts < size ? ts : size); ! 410: } ! 411: free(old); ! 412: return new; ! 413: } ! 414: ! 415: ! 416: ! 417: /* ! 418: ** free(). ! 419: ** Coalescing of adjacent free blocks is done first. ! 420: ** Then, the new free block is leaf-inserted into the free tree ! 421: ** without splaying. This strategy does not guarantee the amortized ! 422: ** O(nlogn) behaviour for the insert/delete/find set of operations ! 423: ** on the tree. In practice, however, free is much more infrequent ! 424: ** than malloc/realloc and the tree searches performed by these ! 425: ** functions adequately keep the tree in balance. ! 426: */ ! 427: free(old) ! 428: char *old; ! 429: { ! 430: reg TREE *tp, *sp, *np; ! 431: reg int ts, size; ! 432: ! 433: /**/ COUNT(nfree); ! 434: ! 435: /* pointer to the block */ ! 436: tp = BLOCK(old); ! 437: ts = SIZE(tp); ! 438: if(!ISBIT0(ts)) ! 439: return -1; ! 440: CLRBITS01(SIZE(tp)); ! 441: ! 442: /* small block, put it in the right linked list */ ! 443: if(SIZE(tp) < MINSIZE) ! 444: { ! 445: ts = SIZE(tp)/WORDSIZE - 1; ! 446: AFTER(tp) = List[ts]; ! 447: List[ts] = tp; ! 448: return 0; ! 449: } ! 450: ! 451: /* see if coalescing with next block is warranted */ ! 452: np = NEXT(tp); ! 453: if(!ISBIT0(SIZE(np))) ! 454: { ! 455: if(np != Bottom) ! 456: t_delete(np); ! 457: SIZE(tp) += SIZE(np)+WORDSIZE; ! 458: } ! 459: ! 460: /* the same with the preceding block */ ! 461: if(ISBIT1(ts)) ! 462: { ! 463: np = LAST(tp); /**/ ASSERT(!ISBIT0(SIZE(np))); ! 464: /**/ ASSERT(np != Bottom); ! 465: t_delete(np); ! 466: SIZE(np) += SIZE(tp)+WORDSIZE; ! 467: tp = np; ! 468: } ! 469: ! 470: /* initialize tree info */ ! 471: PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL; ! 472: ! 473: /* the last word of the block contains self's address */ ! 474: *(SELFP(tp)) = tp; ! 475: ! 476: /* set bottom block, or insert in the free tree */ ! 477: if(BOTTOM(tp)) ! 478: Bottom = tp; ! 479: else ! 480: { ! 481: /* search for the place to insert */ ! 482: if(Root) ! 483: { ! 484: size = SIZE(tp); ! 485: np = Root; ! 486: while(1) ! 487: { ! 488: if(SIZE(np) > size) ! 489: { ! 490: if(LEFT(np)) ! 491: np = LEFT(np); ! 492: else ! 493: { ! 494: LEFT(np) = tp; ! 495: PARENT(tp) = np; ! 496: break; ! 497: } ! 498: } ! 499: else if(SIZE(np) < size) ! 500: { ! 501: if(RIGHT(np)) ! 502: np = RIGHT(np); ! 503: else ! 504: { ! 505: RIGHT(np) = tp; ! 506: PARENT(tp) = np; ! 507: break; ! 508: } ! 509: } ! 510: else ! 511: { ! 512: if(sp = PARENT(np)) /* assignment = */ ! 513: { ! 514: if(np == LEFT(sp)) ! 515: LEFT(sp) = tp; ! 516: else RIGHT(sp) = tp; ! 517: PARENT(tp) = sp; ! 518: } ! 519: else Root = tp; ! 520: ! 521: /* insert to head of list */ ! 522: if(sp = LEFT(np)) /* assignment = */ ! 523: PARENT(sp) = tp; ! 524: LEFT(tp) = sp; ! 525: ! 526: if(sp = RIGHT(np)) /* assignment = */ ! 527: PARENT(sp) = tp; ! 528: RIGHT(tp) = sp; ! 529: ! 530: /* doubly link list */ ! 531: LINKFOR(tp) = np; ! 532: LINKBAK(np) = tp; ! 533: SETNOTREE(np); ! 534: ! 535: break; ! 536: } ! 537: } ! 538: } ! 539: else Root = tp; ! 540: } ! 541: ! 542: /* tell next block that this one is free */ ! 543: SETBIT1(SIZE(NEXT(tp))); /**/ ASSERT(ISBIT0(SIZE(NEXT(tp)))); ! 544: ! 545: return 0; ! 546: } ! 547: ! 548: ! 549: ! 550: /* ! 551: ** Get more core. Gaps in memory are noted as busy blocks. ! 552: */ ! 553: static TREE * _morecore(size) ! 554: unsigned int size; ! 555: { ! 556: reg TREE *tp; ! 557: reg int n; ! 558: reg char *addr; ! 559: ! 560: /* compute new amount of memory to get */ ! 561: tp = Bottom; ! 562: n = size + 2*WORDSIZE; ! 563: ! 564: #ifndef SEGMENTED ! 565: /* if not segmented memory, what we need may be smaller */ ! 566: if((addr = GETCORE(0)) == Baddr) ! 567: n = (size - (tp ? SIZE(tp) : 0)) + WORDSIZE; ! 568: #endif /*!SEGMENTED*/ ! 569: ! 570: /* get a multiple of CORESIZE */ ! 571: n = (n/CORESIZE + 1) * CORESIZE; ! 572: if((addr = GETCORE(n)) == ERRCORE) ! 573: return NULL; ! 574: ! 575: /* contiguous memory */ ! 576: if(addr == Baddr) ! 577: { ! 578: if(tp) ! 579: { ! 580: addr = ((char *)tp); ! 581: n += SIZE(tp) + 2*WORDSIZE; ! 582: } ! 583: else ! 584: { ! 585: addr = Baddr-WORDSIZE; ! 586: n += WORDSIZE; ! 587: } ! 588: } ! 589: ! 590: /* new bottom address */ ! 591: Baddr = addr + n; ! 592: ! 593: /* new bottom block */ ! 594: tp = ((TREE *) addr); ! 595: SIZE(tp) = n - 2*WORDSIZE; /**/ASSERT((SIZE(tp)%ALIGN) == 0); ! 596: ! 597: /* reserved the last word to head any noncontiguous memory */ ! 598: SETBIT0(SIZE(NEXT(tp))); ! 599: ! 600: /* non-contiguous memory, free old bottom block */ ! 601: if(Bottom && Bottom != tp) ! 602: { ! 603: SETBIT0(SIZE(Bottom)); ! 604: free(DATA(Bottom)); ! 605: } ! 606: ! 607: return tp; ! 608: } ! 609: ! 610: ! 611: ! 612: /* ! 613: ** Tree rotation functions (BU: bottom-up, TD: top-down) ! 614: */ ! 615: ! 616: #define LEFT1(x,y) if((RIGHT(x) = LEFT(y))) PARENT(RIGHT(x)) = x;\ ! 617: if((PARENT(y) = PARENT(x)))\ ! 618: if(LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\ ! 619: else RIGHT(PARENT(y)) = y;\ ! 620: LEFT(y) = x; PARENT(x) = y ! 621: ! 622: #define RIGHT1(x,y) if((LEFT(x) = RIGHT(y))) PARENT(LEFT(x)) = x;\ ! 623: if((PARENT(y) = PARENT(x)))\ ! 624: if(LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\ ! 625: else RIGHT(PARENT(y)) = y;\ ! 626: RIGHT(y) = x; PARENT(x) = y ! 627: ! 628: #define BULEFT2(x,y,z) if((RIGHT(x) = LEFT(y))) PARENT(RIGHT(x)) = x;\ ! 629: if((RIGHT(y) = LEFT(z))) PARENT(RIGHT(y)) = y;\ ! 630: if((PARENT(z) = PARENT(x)))\ ! 631: if(LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\ ! 632: else RIGHT(PARENT(z)) = z;\ ! 633: LEFT(z) = y; PARENT(y) = z; LEFT(y) = x; PARENT(x) = y ! 634: ! 635: #define BURIGHT2(x,y,z) if((LEFT(x) = RIGHT(y))) PARENT(LEFT(x)) = x;\ ! 636: if((LEFT(y) = RIGHT(z))) PARENT(LEFT(y)) = y;\ ! 637: if((PARENT(z) = PARENT(x)))\ ! 638: if(LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\ ! 639: else RIGHT(PARENT(z)) = z;\ ! 640: RIGHT(z) = y; PARENT(y) = z; RIGHT(y) = x; PARENT(x) = y ! 641: ! 642: #define TDLEFT2(x,y,z) if((RIGHT(y) = LEFT(z))) PARENT(RIGHT(y)) = y;\ ! 643: if((PARENT(z) = PARENT(x)))\ ! 644: if(LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\ ! 645: else RIGHT(PARENT(z)) = z;\ ! 646: PARENT(x) = z; LEFT(z) = x; ! 647: ! 648: #define TDRIGHT2(x,y,z) if((LEFT(y) = RIGHT(z))) PARENT(LEFT(y)) = y;\ ! 649: if((PARENT(z) = PARENT(x)))\ ! 650: if(LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\ ! 651: else RIGHT(PARENT(z)) = z;\ ! 652: PARENT(x) = z; RIGHT(z) = x; ! 653: ! 654: ! 655: ! 656: /* ! 657: ** Delete a tree element ! 658: */ ! 659: static t_delete(op) ! 660: TREE *op; ! 661: { ! 662: reg TREE *tp, *sp, *gp; ! 663: ! 664: /* if this is a non-tree node */ ! 665: if(ISNOTREE(op)) ! 666: { ! 667: tp = LINKBAK(op); ! 668: if(sp = LINKFOR(op)) /* assignment = */ ! 669: LINKBAK(sp) = tp; ! 670: LINKFOR(tp) = sp; ! 671: return; ! 672: } ! 673: ! 674: /* make op the root of the tree */ ! 675: if(PARENT(op)) ! 676: t_splay(op); ! 677: ! 678: /* if this is the start of a list */ ! 679: if(tp = LINKFOR(op)) /* assignment = */ ! 680: { ! 681: PARENT(tp) = NULL; ! 682: if(sp = LEFT(op)) /* assignment = */ ! 683: PARENT(sp) = tp; ! 684: LEFT(tp) = sp; ! 685: ! 686: if(sp = RIGHT(op)) /* assignment = */ ! 687: PARENT(sp) = tp; ! 688: RIGHT(tp) = sp; ! 689: ! 690: Root = tp; ! 691: return; ! 692: } ! 693: ! 694: /* if op has a non-null left subtree */ ! 695: if(tp = LEFT(op)) /* assignment = */ ! 696: { ! 697: PARENT(tp) = NULL; ! 698: ! 699: if(RIGHT(op)) ! 700: { ! 701: /* make the right-end of the left subtree its root */ ! 702: for(sp = RIGHT(tp); sp != NULL; sp = RIGHT(tp)) ! 703: { ! 704: if(gp = RIGHT(sp)) /* assignment = */ ! 705: { ! 706: TDLEFT2(tp,sp,gp); ! 707: tp = gp; ! 708: } ! 709: else ! 710: { ! 711: LEFT1(tp,sp); ! 712: tp = sp; ! 713: } ! 714: } ! 715: ! 716: /* hook the right subtree of op to the above elt */ ! 717: RIGHT(tp) = RIGHT(op); ! 718: PARENT(RIGHT(tp)) = tp; ! 719: } ! 720: } ! 721: ! 722: /* no left subtree */ ! 723: else if(tp = RIGHT(op)) /* assignment = */ ! 724: PARENT(tp) = NULL; ! 725: ! 726: Root = tp; ! 727: } ! 728: ! 729: ! 730: ! 731: /* ! 732: ** Bottom up splaying (simple version). ! 733: ** The basic idea is to roughly cut in half the ! 734: ** path from Root to tp and make tp the new root. ! 735: */ ! 736: static t_splay(tp) ! 737: reg TREE *tp; ! 738: { ! 739: reg TREE *pp, *gp; ! 740: ! 741: /* iterate until tp is the root */ ! 742: for(pp = PARENT(tp); pp != NULL; pp = PARENT(tp)) ! 743: { ! 744: /* grandparent of tp */ ! 745: gp = PARENT(pp); ! 746: ! 747: /* x is a left child */ ! 748: if(LEFT(pp) == tp) ! 749: { ! 750: if(gp && LEFT(gp) == pp) ! 751: { ! 752: BURIGHT2(gp,pp,tp); ! 753: } ! 754: else ! 755: { ! 756: RIGHT1(pp,tp); ! 757: } ! 758: } ! 759: else ! 760: { /**/ ASSERT(RIGHT(pp) == tp); ! 761: if(gp && RIGHT(gp) == pp) ! 762: { ! 763: BULEFT2(gp,pp,tp); ! 764: } ! 765: else ! 766: { ! 767: LEFT1(pp,tp); ! 768: } ! 769: } ! 770: } ! 771: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.