massive reduction of unneeded files

1 files changed, 0 insertions, 1256 deletions

diff --git a/nx-X11/util/memleak/fmalloc.c b/nx-X11/util/memleak/fmalloc.c
deleted file mode 100644
index bce5c4388..000000000
--- a/nx-X11/util/memleak/fmalloc.c
+++ /dev/null
@@ -1,1256 +0,0 @@
-/*
- * $Xorg: fmalloc.c,v 1.5 2001/02/09 02:06:19 xorgcvs Exp $
- *
-Copyright 1992, 1998  The Open Group
-
-Permission to use, copy, modify, distribute, and sell this software and its
-documentation for any purpose is hereby granted without fee, provided that
-the above copyright notice appear in all copies and that both that
-copyright notice and this permission notice appear in supporting
-documentation.
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
-OPEN GROUP  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
-CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of The Open Group shall not be
-used in advertising or otherwise to promote the sale, use or other dealings
-in this Software without prior written authorization from The Open Group.
- *
- * Author:  Keith Packard, MIT X Consortium
- */
-
-/* $XFree86: xc/util/memleak/fmalloc.c,v 3.12 2001/02/16 13:24:10 eich Exp $ */
-
-
-/*
- * Leak tracing allocator -- using C lib malloc/free, tracks
- * all allocations.  When requested, performs a garbage-collection
- * style mark/sweep on static memory (data and stack), locating
- * objects referenced therein.  Recursively marks objects.
- * Sweeps through all allocations, warning of possible violations
- * (unreferenced allocated, referenced freed etc).
- */
-
-#include    <stdio.h>
-
-extern char **environ;
-extern xf86DriverList;
-extern etext;
-extern _etext;
-extern __data_start;
-extern _end;
-
-#ifndef TOP_OF_DATA
-#define TOP_OF_DATA 0
-#endif
-
-#ifndef FALSE
-#define FALSE 0
-#endif
-#ifndef TRUE
-#define TRUE 1
-#endif
-
-#ifdef X_NOT_POSIX
-#define NO_ATEXIT
-#endif
-
-typedef unsigned long mem;
-typedef unsigned int  magic;
-
-#ifdef HAS_GET_RETURN_ADDRESS
-#define MAX_RETURN_STACK    16
-#endif
-
-#define MAX_FREED_MEMORY    (1*1024*1024)
-
-#define ACTIVE_HEAD_MAGIC   0xff1111ff
-#define ACTIVE_TAIL_MAGIC   0xee2222ee
-#define ACTIVE_DATA_MAGIC   0xdd3333dd
-#define FREED_HEAD_MAGIC    0xcc4444cc
-#define FREED_TAIL_MAGIC    0xbb5555bb
-#define FREED_DATA_MAGIC    0xcc6666cc
-
-/*
- * the marked fields in each head have two bits - one indicating
- * references to the head of the block, and one indicating references
- * to the middle of the block
- */
-#define UNREFERENCED	    0
-#define REFERENCED_HEAD	    1
-#define REFERENCED_MIDDLE   2
-
-typedef struct _head {
-    struct _head    *left, *right;
-    struct _head    *next;
-    int		    balance;
-#ifdef HAS_GET_RETURN_ADDRESS
-    mem		    returnStack[MAX_RETURN_STACK];
-#endif
-    mem		    *from;
-    mem             *fromReturnStack;
-    unsigned long   allocTime;
-    unsigned long   freeTime;
-    int		    size;
-    int		    desiredsize;
-    int		    actualSize;
-    int		    marked;
-    magic    	    headMagic;
-} HeadRec, *HeadPtr;
-
-typedef struct _tail {
-    magic    	    tailMagic;
-    magic    	    tailPad;
-} TailRec, *TailPtr;
-
-#define Header(p)	((HeadPtr) (((char *) (p)) - sizeof (HeadRec)))
-#define DataForHead(h)	((mem *) ((h) + 1))
-#define Tailer(p)	((TailPtr) (((char *) (p)) + Header(p)->size))
-#define TailForHead(h)	(Tailer(DataForHead(h)))
-#define RoundSize	(sizeof (mem))
-#define RoundUp(s)	(((s) + RoundSize - 1) & ~(RoundSize - 1))
-#define TotalSize(s)	((s) + sizeof (HeadRec) + sizeof (TailRec))
-#define CheckInit()	if (!endOfStaticMemory) endOfStaticMemory = sbrk(0)
-#define BlockContains(h,p)  (DataForHead(h) <= (p) && (p) < (mem *) TailForHead(h))
-
-typedef HeadRec		tree;
-typedef mem		*tree_data;
-
-#define COMPARE_ADDR(a,b,op)	(((mem) (a)) op ((mem) (b)))
-#define COMPARE(a,b,op,s)	((!s) ? \
-			 COMPARE_ADDR(a,b,op) :\
-			(((a)->actualSize op (b)->actualSize) || \
-			 ((a)->actualSize == (b)->actualSize && \
-			  COMPARE_ADDR(a,b,op))))
-				
-
-#define LESS_THAN(a,b,s)    COMPARE(a,b,<,s)
-#define GREATER_THAN(a,b,s) COMPARE(a,b,>,s)
-
-#define SEARCH(top,result,p) for (result = top; result;) {\
-    if ((mem *) (p) < DataForHead(result)) \
-	result = result->left; \
-    else if ((mem *) TailForHead(result) < (mem *) (p)) \
-	result = result->right; \
-    else \
-	break; \
-}
-    
-
-static tree	*activeMemory, *freedMemory, *deadMemory;
-
-static mem	*endOfStaticMemory = (mem *) TOP_OF_DATA;
-static mem	*highestAllocatedMemory;
-
-static int	freedMemoryTotal;
-static int	freedMemoryCount;
-static int	activeMemoryTotal;
-static int	activeMemoryCount;
-static int	deadMemoryTotal;
-static int	unreferencedAllocatedTotal;
-static int	unreferencedAllocatedCount;
-
-int		FindLeakWarnMiddlePointers = 0;
-unsigned long	FindLeakAllocBreakpoint = ~0;
-unsigned long	FindLeakFreeBreakpoint = ~0;
-unsigned long	FindLeakTime;
-int		FindLeakCheckAlways = 0;
-int		FindLeakValidateAlways = 0;
-int		FindPrintAllocations = 0;
-
-static void MarkActiveBlock ();
-static int  tree_insert (), tree_delete ();
-void	    CheckMemory ();
-char	    *malloc (), *realloc (), *calloc ();
-void	    free ();
-extern char *sbrk ();
-
-#ifdef HAS_GET_RETURN_ADDRESS
-static void
-PrintReturnStack (m, ra)
-    char    *m;
-    mem	    *ra;
-{
-    int	    i;
-
-    fprintf (stderr, "   %s:", m);
-    for (i = 0; i < MAX_RETURN_STACK && ra[i]; i++)
-	fprintf (stderr, " 0x%lx", ra[i]);
-    fprintf (stderr, "\n");
-}
-#endif
-
-static void
-MemError (s, h, ourRet)
-    char	*s;
-    HeadPtr	h;
-    int		ourRet;
-{
-    mem *ra;
-    int	i;
-
-    if (h)
-    {
-	fprintf (stderr, "%s 0x%08lx (size %d) (from 0x%lx) ",
-	     s, DataForHead(h), h->desiredsize, h->from);
-#ifdef HAS_GET_RETURN_ADDRESS
-	if (h->fromReturnStack)
-	    PrintReturnStack ("\nallocated at", h->fromReturnStack);
-	else
-	  fprintf(stderr,"\n");
-	PrintReturnStack ("Saved return stack", h->returnStack);
-#else
-	fprintf(stderr,"\n");
-#endif
-    }
-    else 
-	fprintf (stderr, "%s\n", s);
-#ifdef HAS_GET_RETURN_ADDRESS
-    if (ourRet)
-    {
-	mem	returnStack[MAX_RETURN_STACK];
-
-	getStackTrace (returnStack, MAX_RETURN_STACK);
-	PrintReturnStack ("Current return stack", returnStack);
-    }
-#endif
-}
-
-static void
-MarkMemoryRegion (low, high)
-    mem	*low, *high;
-{
-    mem	**start = (mem **) low, **end = (mem **) high;
-    mem	*p;
-
-    while (start < end) {
-	p = *start;
-	if (endOfStaticMemory <= p && p < highestAllocatedMemory)
-	    MarkActiveBlock (p, (mem *) start);
-	start++;
-    }
-}
-
-static void
-MarkActiveBlock (p, from)
-    mem   *p, *from;
-{
-    HeadPtr	h, hh;
-    int		marked;
-    int		oldMarked;
-
-    SEARCH(activeMemory, h, p)
-    if (h) {
-	marked = REFERENCED_HEAD;
-        if (p != DataForHead(h))
-	    marked = REFERENCED_MIDDLE;
-	oldMarked = h->marked;
-	if (!(oldMarked & marked))
-	{
-	    h->marked |= marked;
-	    h->from = from;
-#ifdef HAS_GET_RETURN_ADDRESS
-	    SEARCH(activeMemory, hh, h->from)
-	      if (hh) 
-		h->fromReturnStack = hh->returnStack;
-#endif
-	    if (!oldMarked)
-		MarkMemoryRegion (DataForHead(h), (mem *) TailForHead(h));
-	}
-	return;
-    }
-    SEARCH(freedMemory, h, p)
-    if (h)
-    {
-	marked = REFERENCED_HEAD;
-        if (p != DataForHead(h))
-	    marked = REFERENCED_MIDDLE;
-	if (!(h->marked & marked))
-	{
-	    h->marked |= marked;
-	    h->from = from;
-#ifdef HAS_GET_RETURN_ADDRESS
-	    SEARCH(activeMemory, hh, h->from)
-            if (hh) 
-		h->fromReturnStack = hh->returnStack;
-#endif
-	}
-	return;
-    }
-}
-
-static void
-ClearTree (t)
-    tree    *t;
-{
-    if (!t)
-	return;
-    ClearTree (t->left);
-    t->marked = 0;
-    t->from = 0;
-    ClearTree (t->right);
-}
-
-static void
-SweepActiveTree (t)
-    tree    *t;
-{
-    if (!t)
-	return;
-    SweepActiveTree (t->left);
-    if (!t->marked) {
-	unreferencedAllocatedTotal += t->desiredsize;
-	unreferencedAllocatedCount++;
-	MemError ("Unreferenced allocated", t, FALSE);
-    }
-    else if (!(t->marked & REFERENCED_HEAD))
-	MemError ("Referenced allocated middle", t, FALSE);
-    SweepActiveTree (t->right);
-}
-
-/*
- * run a thread through the tree at the same time
- * - the thread runs 
- *
- * root -> left_child ... -> right_child ... -> null
- */
-
-static tree *
-SweepFreedTree (t)
-    tree    *t;
-{
-    tree    *left_last, *right_last;
-
-    if (!t)
-	return 0;
-
-    left_last = SweepFreedTree (t->left);
-    if (t->marked)
-    {
-	if (t->marked & REFERENCED_HEAD)
-	    MemError ("Referenced freed base", t, FALSE);
-	else if (FindLeakWarnMiddlePointers)
-	    MemError ("Referenced freed middle", t, FALSE);
-    }
-    right_last = SweepFreedTree (t->right);
-
-    if (t->left)
-	t->next = t->left;
-    else
-	t->next = t->right;
-    if (left_last)
-	left_last->next = t->right;
-    if (!right_last)
-	right_last = left_last;
-    if (!right_last)
-	right_last = t;
-    return right_last;
-}
-
-static void
-SweepFreedMemory ()
-{
-    tree    *t, *n;
-    int	    count, shouldCount;
-
-    (void) SweepFreedTree (freedMemory);
-    count = 0;
-    shouldCount = freedMemoryCount;
-    for (t = freedMemory; t; t = n) {
-	n = t->next;
-	count++;
-	if (!t->marked) 
-	{
-	    (void) tree_delete (&freedMemory, t, FALSE);
-	    freedMemoryTotal -= t->desiredsize;
-	    freedMemoryCount--;
-	    tree_insert (&deadMemory, t, TRUE);
-	}
-    }
-    if (count != shouldCount)
-	abort ();
-}
-
-static void
-ValidateTree (head, headMagic, tailMagic, bodyMagic, mesg)
-    tree    *head;
-    mem	    headMagic, tailMagic, bodyMagic;
-    char    *mesg;
-{
-    TailPtr	tail;
-    magic    	*p;
-    int		i;
-
-    if (!head)
-	return;
-    ValidateTree (head->left, headMagic, tailMagic, bodyMagic, mesg);
-    tail = TailForHead (head);
-    if (head->headMagic != headMagic)
-	MemError (mesg, head, FALSE);
-    if (tail->tailMagic != tailMagic)
-	MemError (mesg, head, FALSE);
-    if (bodyMagic) {
-	i = head->size / sizeof (magic);
-	p = (magic *) DataForHead(head);
-	while (i--) {
-	    if (*p++ != bodyMagic)
-	    {
-		MemError (mesg, head, FALSE);
-		break;
-	    }
-	}
-    }
-    ValidateTree (head->right, headMagic, tailMagic, bodyMagic, mesg);
-}
-
-static void
-ValidateActiveMemory ()
-{
-    ValidateTree (activeMemory, ACTIVE_HEAD_MAGIC, ACTIVE_TAIL_MAGIC,
-		  0, "Store outside of active memory");
-}
-
-static void
-ValidateFreedMemory ()
-{
-    ValidateTree (freedMemory, FREED_HEAD_MAGIC, FREED_TAIL_MAGIC,
-		  FREED_DATA_MAGIC, "Store into freed memory");
-}
-
-static void
-AddActiveBlock (h)
-    HeadPtr	h;
-{
-    TailPtr	t = TailForHead(h);
-    magic    	*p;
-    int		i;
-
-    tree_insert (&activeMemory, h, FALSE);
-    if ((mem *) t > highestAllocatedMemory)
-	highestAllocatedMemory = (mem *) t;
-
-    /*
-     * Breakpoint position - assign FindLeakAllocBreakpoint with
-     * debugger and set a breakpoint in the conditional clause below
-     */
-    if (FindLeakTime == FindLeakAllocBreakpoint)
-	h->headMagic = ACTIVE_HEAD_MAGIC;	    /* set breakpoint here */
-
-    h->allocTime = FindLeakTime++;
-
-    h->headMagic = ACTIVE_HEAD_MAGIC;
-    t->tailMagic = ACTIVE_TAIL_MAGIC;
-    i = h->size / sizeof (magic);
-    p = (magic *) DataForHead(h);
-    while (i--)
-	*p++ = ACTIVE_DATA_MAGIC;
-    activeMemoryTotal += h->desiredsize;
-    activeMemoryCount++;
-}
-
-static void
-RemoveActiveBlock (h)
-    HeadPtr	h;
-{
-    activeMemoryTotal -= h->desiredsize;
-    activeMemoryCount--;
-    tree_delete (&activeMemory, h, FALSE);
-}
-
-static void
-AddFreedBlock (h)
-    HeadPtr	h;
-{
-    TailPtr	t = TailForHead(h);
-    int		i;
-    magic    	*p;
-
-    tree_insert (&freedMemory, h, FALSE);
-
-    /*
-     * Breakpoint position - assign FindLeakFreeBreakpoint with
-     * debugger and set a breakpoint in the conditional clause below
-     */
-    if (FindLeakTime == FindLeakFreeBreakpoint)
-	h->headMagic = FREED_HEAD_MAGIC;	    /* set breakpoint here */
-
-    h->freeTime = FindLeakTime++;
-
-    h->headMagic = FREED_HEAD_MAGIC;
-    t->tailMagic = FREED_TAIL_MAGIC;
-    i = h->size / sizeof (magic);
-    p = (magic *) DataForHead(h);
-    while (i--)
-	*p++ = FREED_DATA_MAGIC;
-    freedMemoryTotal += h->desiredsize;
-    freedMemoryCount++;
-    /* GC if we've got piles of unused memory */
-    if (freedMemoryTotal - deadMemoryTotal >= MAX_FREED_MEMORY)
-	CheckMemory ();
-}
-#if 0
-static void
-WarnReferencedRange(rangeStart,rangeEnd,from,to)
-     mem *rangeStart;
-     mem *rangeEnd;
-     mem *from;
-     mem *to;
-{
-  mem *range = rangeStart;
-
-  while ( range < rangeEnd) {
-    if ((mem *)*range >= from && (mem *)*range <= to)
-      fprintf(stderr, "0x%lx still points into newly allocated range\n",
-	      (unsigned long) range);
-    range++;
-  }
-}
-
-static void
-WarnReferencedTree(head, from, to)
-     tree *head;
-     char *from;
-     char *to;
-{
-  if (!head) return;
-  WarnReferencedTree(head->right,from,to);
-  WarnReferencedRange(DataForHead(head),TailForHead(head),from,to);
-  WarnReferencedTree(head->left,from,to);
-}
-
-static void
-WarnReferenced(from, to)
-     char *from;
-     char *to;
-{
-    mem	foo;
-
-    foo = 1;
-    WarnReferencedTree(activeMemory,from,to);
-    WarnReferencedRange(BOTTOM_OF_DATA, endOfStaticMemory,from,to);
-    WarnReferencedRange(&foo, TOP_OF_STACK,from,to);
-}  
-#endif
-/*
- * Entry points:
- *
- *  CheckMemory ()		--	Verifies heap
- *  malloc (size)		--	Allocates memory
- *  free (old)			--	Deallocates memory
- *  realloc (old, size)		--	Allocate, copy, free
- *  calloc (num, size_per)	--	Allocate and zero
- */
-
-void
-CheckMemory ()
-{
-#if 0
-    mem	foo;
-
-    unreferencedAllocatedTotal = 0;
-    unreferencedAllocatedCount = 0;
-    foo = 1;
-    fprintf (stderr, "\nCheckMemory\n");
-    fprintf (stderr, "Static Memory Area: 0x%lx to 0x%lx\n",
-               BOTTOM_OF_DATA, endOfStaticMemory);
-    fprintf (stderr, "%d bytes active memory in %d allocations\n",
-	     activeMemoryTotal, activeMemoryCount);
-    fprintf (stderr, "%d bytes freed memory held from %d allocations\n",
-	    freedMemoryTotal, freedMemoryCount);
-    ValidateActiveMemory ();
-    ValidateFreedMemory ();
-    ClearTree (activeMemory);
-    ClearTree (freedMemory);
-    MarkMemoryRegion (BOTTOM_OF_DATA, endOfStaticMemory);
-    MarkMemoryRegion (&foo, TOP_OF_STACK);
-    SweepActiveTree (activeMemory);
-    SweepFreedMemory ();
-    fprintf (stderr, "%d bytes freed memory still held from %d allocations\n",
-	     freedMemoryTotal, freedMemoryCount);
-    fprintf (stderr, 
-	   "%d bytes of allocated memory not referenced from %d allocations\n",
-	     unreferencedAllocatedTotal,unreferencedAllocatedCount);
-    deadMemoryTotal = freedMemoryTotal;
-    fprintf (stderr, "CheckMemory done\n");
-#endif
-}
-
-/*
- * Allocator interface -- malloc and free (others in separate files)
- */
-
-#define CORE_CHUNK  16384
-
-static char	*core;
-static unsigned	core_left;
-static unsigned	total_core_used;
-
-static char *
-morecore (size)
-    unsigned	size;
-{
-    unsigned	alloc_size;
-    char	*alloc, *newcore;
-
-    if (core_left < size)
-    {
-	alloc_size = (size + CORE_CHUNK - 1) & ~(CORE_CHUNK-1);
-    	newcore = sbrk (alloc_size);
-    	if (((long) newcore) == -1)
-	    return 0;
-	core = newcore;
-	core_left = alloc_size;
-	total_core_used += alloc_size;
-    }
-    alloc = core;
-    core += size;
-    core_left -= size;
-    return alloc;
-}
-
-char *
-malloc (desiredsize)
-    unsigned	desiredsize;
-{
-    char	*ret;
-    unsigned	size;
-    unsigned	totalsize;
-    HeadPtr	h;
-
-    if (!endOfStaticMemory)
-	endOfStaticMemory = (mem *) sbrk(0);
-    if (FindLeakCheckAlways)
-	CheckMemory ();
-    else if (FindLeakValidateAlways)
-    {
-	ValidateActiveMemory ();
-	ValidateFreedMemory ();
-    }
-    size = RoundUp(desiredsize);
-    totalsize = TotalSize (size);
-
-    h = deadMemory;
-    while (h)
-    {
-	if (h->actualSize == size)
-	    break;
-	else if (h->actualSize < size)
-	    h = h->right;
-	else {
-	    if (!h->left)
-		break;
-	    h = h->left;
-	}
-    }
-    if (h) 
-    {
-	tree_delete (&deadMemory, h, TRUE);
-    }
-    else
-    {
-	h = (HeadPtr) morecore (totalsize);
-	if (!h)
-	    return NULL;
-	h->actualSize = size;
-    }
-    h->desiredsize = desiredsize;
-    h->size = size;
-#ifdef HAS_GET_RETURN_ADDRESS
-    getStackTrace (h->returnStack, MAX_RETURN_STACK);
-#endif
-    AddActiveBlock (h);
-    ret =  (char *) DataForHead(h);
-    if (FindPrintAllocations) {
-	fprintf(stderr,"Allocated %i bytes at 0x%lx\n",desiredsize,ret);
-#ifdef HAS_GET_RETURN_ADDRESS
-	PrintReturnStack ("at",h->returnStack);
-#endif
-    }
-    return ret;
-}
-
-void
-free (p)
-    char    *p;
-{
-    HeadPtr	h;
-    static int	beenHere;
-    
-#ifndef NO_ATEXIT
-    /* do it at free instead of malloc to avoid recursion? */
-    if (!beenHere)
-    {
-	beenHere = TRUE;
-	atexit (CheckMemory);
-    }
-#endif
-    if (!p)
-    {
-	MemError ("Freeing NULL", (HeadPtr) 0, TRUE);
-	return;
-    }
-    SEARCH (activeMemory, h, p);
-    if (!h)
-    {
-	SEARCH(freedMemory, h, p);
-	if (h)
-	    MemError ("Freeing something twice", h, TRUE);
-	else
-	    MemError ("Freeing something never allocated", h, TRUE);
-	return;
-    }
-    if (DataForHead(h) != (mem *) p)
-    {
-	MemError ("Freeing pointer to middle of allocated block", h, TRUE);
-	return;
-    }
-    if (h->headMagic != ACTIVE_HEAD_MAGIC ||
-	TailForHead(h)->tailMagic != ACTIVE_TAIL_MAGIC)
-	MemError ("Freeing corrupted data", h, TRUE);
-    RemoveActiveBlock (h);
-#ifdef HAS_GET_RETURN_ADDRESS
-    getStackTrace (h->returnStack, MAX_RETURN_STACK);
-#endif
-    AddFreedBlock (h);
-    if (FindLeakCheckAlways)
-	CheckMemory ();
-    else if (FindLeakValidateAlways)
-    {
-	ValidateActiveMemory ();
-	ValidateFreedMemory ();
-    }
-    if (FindPrintAllocations) {
-	fprintf(stderr,"Freed at:  0x%lx\n",p);
-	PrintReturnStack ("at",h->returnStack);
-    }
-
-}
-
-char *
-realloc (old, desiredsize)
-    char	*old;
-    unsigned	desiredsize;
-{
-    char    *new;
-    HeadPtr  h, fh;
-    int	    copysize;
-
-    new = malloc (desiredsize);
-    if (!new)
-	return NULL;
-    if (!old)
-	return new;
-    SEARCH(activeMemory, h, old);
-    if (!h)
-    {
-	SEARCH(freedMemory, fh, old);
-	if (fh)
-	    MemError ("Reallocing from freed data", fh, TRUE);
-	else
-	    MemError ("Reallocing from something not allocated", h, TRUE);
-    }
-    else
-    {
-	if (DataForHead(h) != (mem *) old)
-	{
-	    MemError ("Reallocing from pointer to middle of allocated block", h, TRUE);
-	}
-	else
-	{
-	    if (h->headMagic != ACTIVE_HEAD_MAGIC ||
-		TailForHead(h)->tailMagic != ACTIVE_TAIL_MAGIC)
-		MemError ("Reallocing corrupted data", h, TRUE);
-	    copysize = desiredsize;
-	    if (h->desiredsize < desiredsize)
-		copysize = h->desiredsize;
-#ifdef SVR4
-	    memmove (new, old, copysize);
-#else
-	    bcopy (old, new, copysize);
-#endif
-	    RemoveActiveBlock (h);
-#ifdef HAS_GET_RETURN_ADDRESS
-	    getStackTrace (h->returnStack, MAX_RETURN_STACK);
-#endif
-	    AddFreedBlock (h);
-	}
-    }
-    if (FindPrintAllocations) {
-	fprintf(stderr,"Freed at: 0x%lx\n",old);
-	fprintf(stderr,"Reallocated: %i bytes at:  0x%lx\n",desiredsize,new);
-#ifdef HAS_GET_RETURN_ADDRESS
-        PrintReturnStack ("at", h->returnStack);
-#endif
-    }
-    return new;
-}
-
-char *
-calloc (num, size)
-    unsigned	num, size;
-{
-    char *ret;
-
-    size *= num;
-    ret = malloc (size);
-    if (!ret)
-	return NULL;
-#ifdef SVR4
-    memset (ret, 0, size);
-#else
-    bzero (ret, size);
-#endif
-    return ret;
-}
-
-/*
- * Semi-Balanced trees (avl).  This only contains two
- * routines - insert and delete.  Searching is
- * reserved for the client to write.
- */
-
-static	rebalance_right (), rebalance_left ();
-
-/*
- * insert a new node
- *
- * this routine returns non-zero if the tree has grown
- * taller
- */
-
-static int
-tree_insert (treep, new, bySize)
-tree	**treep;
-tree	*new;
-int	bySize;
-{
-	if (!(*treep)) {
-		(*treep) = new;
-		(*treep)->left = 0;
-		(*treep)->right = 0;
-		(*treep)->balance = 0;
-		return 1;
-	} else {
-		if (LESS_THAN (*treep, new, bySize)) {
-			if (tree_insert (&((*treep)->right), new, bySize))
-				switch (++(*treep)->balance) {
-				case 0:
-					return 0;
-				case 1:
-					return 1;
-				case 2:
-					(void) rebalance_right (treep);
-				}
-			return 0;
-		} else if (GREATER_THAN(*treep, new, bySize)) {
-			if (tree_insert (&((*treep)->left), new, bySize))
-				switch (--(*treep)->balance) {
-				case 0:
-					return 0;
-				case -1:
-					return 1;
-				case -2:
-					(void) rebalance_left (treep);
-				}
-			return 0;
-		} else {
-			return 0;
-		}
-	}
-	/*NOTREACHED*/
-}
-					
-/*
- * delete a node from a tree
- *
- * this routine return non-zero if the tree has been shortened
- */
-
-static int
-tree_delete (treep, old, bySize)
-tree	**treep;
-tree	*old;
-int	bySize;
-{
-	tree	*to_be_deleted;
-	tree	*replacement;
-	tree	*replacement_parent;
-	int	replacement_direction;
-	int	delete_direction;
-	tree	*swap_temp;
-	int	balance_temp;
-
-	if (!*treep)
-		/* node not found */
-		return 0;
-	if (LESS_THAN(*treep, old, bySize)) {
-		if (tree_delete (&(*treep)->right, old, bySize))
-			/*
-			 * check the balance factors
-			 * Note that the conditions are
-			 * inverted from the insertion case
-			 */
-			switch (--(*treep)->balance) {
-			case 0:
-				return 1;
-			case -1:
-				return 0;
-			case -2:
-				return rebalance_left (treep);
-			}
-		return 0;
-	} else if (GREATER_THAN(*treep, old, bySize)) {
-		if (tree_delete (&(*treep)->left, old, bySize))
-			switch (++(*treep)->balance) {
-			case 0:
-				return 1;
-			case 1:
-				return 0;
-			case 2:
-				return rebalance_right (treep);
-			}
-		return 0;
-	} else {
-		to_be_deleted = *treep;
-		/*
-		 * find an empty down pointer (if any)
-		 * and rehook the tree
-		 */
-		if (!to_be_deleted->right) {
-			(*treep) = to_be_deleted->left;
-			return 1;
-		} else if (!to_be_deleted->left) {
-			(*treep) = to_be_deleted->right;
-			return 1;
-		} else {
-		/* 
-		 * if both down pointers are full, then
-		 * move a node from the bottom of the tree up here.
-		 *
-		 * This builds an incorrect tree -- the replacement
-		 * node and the to_be_deleted node will not
-		 * be in correct order.  This doesn't matter as
-		 * the to_be_deleted node will obviously not leave
-		 * this routine alive.
-		 */
-			/*
-			 * if the tree is left heavy, then go left
-			 * else go right
-			 */
-			replacement_parent = to_be_deleted;
-			if (to_be_deleted->balance == -1) {
-				delete_direction = -1;
-				replacement_direction = -1;
-				replacement = to_be_deleted->left;
-				while (replacement->right) {
-					replacement_parent = replacement;
-					replacement_direction = 1;
-					replacement = replacement->right;
-				}
-			} else {
-				delete_direction = 1;
-				replacement_direction = 1;
-				replacement = to_be_deleted->right;
-				while (replacement->left) {
-					replacement_parent = replacement;
-					replacement_direction = -1;
-					replacement = replacement->left;
-				}
-			}
-			/*
-			 * swap the replacement node into
-			 * the tree where the node is to be removed
-			 * 
-			 * this would be faster if only the data
-			 * element was swapped -- but that
-			 * won't work for findleak.  The alternate
-			 * code would be:
-			   data_temp = to_be_deleted->data;
-			   to _be_deleted->data = replacement->data;
-			   replacement->data = data_temp;
-			 */
-			swap_temp = to_be_deleted->left;
-			to_be_deleted->left = replacement->left;
-			replacement->left = swap_temp;
-			swap_temp = to_be_deleted->right;
-			to_be_deleted->right = replacement->right;
-			replacement->right = swap_temp;
-			balance_temp = to_be_deleted->balance;
-			to_be_deleted->balance = replacement->balance;
-			replacement->balance = balance_temp;
-			/*
-			 * if the replacement node is directly below
-			 * the to-be-removed node, hook the to_be_deleted
-			 * node below it (instead of below itself!)
-			 */
-			if (replacement_parent == to_be_deleted)
-				replacement_parent = replacement;
-			if (replacement_direction == -1)
-				replacement_parent->left = to_be_deleted;
-			else
-				replacement_parent->right = to_be_deleted;
-			(*treep) = replacement;
-			/*
-			 * delete the node from the sub-tree
-			 */
-			if (delete_direction == -1) {
-				if (tree_delete (&(*treep)->left, old, bySize)) {
-					switch (++(*treep)->balance) {
-					case 2:
-						abort ();
-					case 1:
-						return 0;
-					case 0:
-						return 1;
-					}
-				}
-				return 0;
-			} else {
-				if (tree_delete (&(*treep)->right, old, bySize)) {
-					switch (--(*treep)->balance) {
-					case -2:
-						abort ();
-					case -1:
-						return 0;
-					case 0:
-						return 1;
-					}
-				}
-				return 0;
-			}
-		}
-	}
-	/*NOTREACHED*/
-}
-
-/*
- * two routines to rebalance the tree.
- *
- * rebalance_right -- the right sub-tree is too long
- * rebalance_left --  the left sub-tree is too long
- *
- * These routines are the heart of avl trees, I've tried
- * to make their operation reasonably clear with comments,
- * but some study will be necessary to understand the
- * algorithm.
- *
- * these routines return non-zero if the resultant
- * tree is shorter than the un-balanced version.  This
- * is only of interest to the delete routine as the
- * balance after insertion can never actually shorten
- * the tree.
- */
- 
-static
-rebalance_right (treep)
-tree	**treep;
-{
-	tree	*temp;
-	/*
-	 * rebalance the tree
-	 */
-	if ((*treep)->right->balance == -1) {
-		/* 
-		 * double whammy -- the inner sub-sub tree
-		 * is longer than the outer sub-sub tree
-		 *
-		 * this is the "double rotation" from
-		 * knuth.  Scheme:  replace the tree top node
-		 * with the inner sub-tree top node and
-		 * adjust the maze of pointers and balance
-		 * factors accordingly.
-		 */
-		temp = (*treep)->right->left;
-		(*treep)->right->left = temp->right;
-		temp->right = (*treep)->right;
-		switch (temp->balance) {
-		case -1:
-			temp->right->balance = 1;
-			(*treep)->balance = 0;
-			break;
-		case 0:
-			temp->right->balance = 0;
-			(*treep)->balance = 0;
-			break;
-		case 1:
-			temp->right->balance = 0;
-			(*treep)->balance = -1;
-			break;
-		}
-		temp->balance = 0;
-		(*treep)->right = temp->left;
-		temp->left = (*treep);
-		(*treep) = temp;
-		return 1;
-	} else {
-		/*
-		 * a simple single rotation
-		 *
-		 * Scheme:  replace the tree top node
-		 * with the sub-tree top node 
-		 */
-		temp = (*treep)->right->left;
-		(*treep)->right->left = (*treep);
-		(*treep) = (*treep)->right;
-		(*treep)->left->right = temp;
-		/*
-		 * only two possible configurations --
-		 * if the right sub-tree was balanced, then
-		 * *both* sides of it were longer than the
-		 * left side, so the resultant tree will
-		 * have a long leg (the left inner leg being
-		 * the same length as the right leg)
-		 */
-		if ((*treep)->balance == 0) {
-			(*treep)->balance = -1;
-			(*treep)->left->balance = 1;
-			return 0;
-		} else {
-			(*treep)->balance = 0;
-			(*treep)->left->balance = 0;
-			return 1;
-		}
-	}
-}
-
-static
-rebalance_left (treep)
-tree	**treep;
-{
-	tree	*temp;
-	/*
-	 * rebalance the tree
-	 */
-	if ((*treep)->left->balance == 1) {
-		/* 
-		 * double whammy -- the inner sub-sub tree
-		 * is longer than the outer sub-sub tree
-		 *
-		 * this is the "double rotation" from
-		 * knuth.  Scheme:  replace the tree top node
-		 * with the inner sub-tree top node and
-		 * adjust the maze of pointers and balance
-		 * factors accordingly.
-		 */
-		temp = (*treep)->left->right;
-		(*treep)->left->right = temp->left;
-		temp->left = (*treep)->left;
-		switch (temp->balance) {
-		case 1:
-			temp->left->balance = -1;
-			(*treep)->balance = 0;
-			break;
-		case 0:
-			temp->left->balance = 0;
-			(*treep)->balance = 0;
-			break;
-		case -1:
-			temp->left->balance = 0;
-			(*treep)->balance = 1;
-			break;
-		}
-		temp->balance = 0;
-		(*treep)->left = temp->right;
-		temp->right = (*treep);
-		(*treep) = temp;
-		return 1;
-	} else {
-		/*
-		 * a simple single rotation
-		 *
-		 * Scheme:  replace the tree top node
-		 * with the sub-tree top node 
-		 */
-		temp = (*treep)->left->right;
-		(*treep)->left->right = (*treep);
-		(*treep) = (*treep)->left;
-		(*treep)->right->left = temp;
-		/*
-		 * only two possible configurations --
-		 * if the left sub-tree was balanced, then
-		 * *both* sides of it were longer than the
-		 * right side, so the resultant tree will
-		 * have a long leg (the right inner leg being
-		 * the same length as the left leg)
-		 */
-		if ((*treep)->balance == 0) {
-			(*treep)->balance = 1;
-			(*treep)->right->balance = -1;
-			return 0;
-		} else {
-			(*treep)->balance = 0;
-			(*treep)->right->balance = 0;
-			return 1;
-		}
-	}
-}
-
-#ifdef DEBUG
-
-static 
-depth (treep)
-tree	*treep;
-{
-	int	ldepth, rdepth;
-
-	if (!treep)
-		return 0;
-	ldepth = depth (treep->left);
-	rdepth = depth (treep->right);
-	if (ldepth > rdepth)
-		return ldepth + 1;
-	return rdepth + 1;
-}
-
-static tree *
-left_most (treep)
-tree	*treep;
-{
-	while (treep && treep->left)
-		treep = treep->left;
-	return treep;
-}
-
-static tree *
-right_most (treep)
-tree	*treep;
-{
-	while (treep && treep->right)
-		treep = treep->right;
-	return treep;
-}
-
-tree_verify (treep)
-tree	*treep;
-{
-	tree_data	left_data, right_data;
-
-	if (!treep)
-		return 1;
-	if (treep->left)
-		left_data = right_most (treep->left)->data;
-	else
-		left_data = treep->data - 1;
-	if (treep->right)
-		right_data = left_most (treep->right)->data;
-	else
-		right_data = treep->data + 1;
-	if (treep->data < left_data || treep->data > right_data) {
-		abort ();
-		return 0;
-	}
-	if (treep->balance != depth (treep->right) - depth (treep->left)) {
-		abort ();
-		return 0;
-	}
-	return tree_verify (treep->left) && tree_verify (treep->right);
-}
-
-#endif