![[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] / researchv10no / cmd / dag|
Return to kpvmalloc.c CVS log | Up to [Research Unix] / researchv10no / 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.