Imported nx-X11-3.1.0-1.tar.gznx-X11/3.1.0-1

Summary: Imported nx-X11-3.1.0-1.tar.gz
Keywords:

Imported nx-X11-3.1.0-1.tar.gz
into Git repository

1 files changed, 1256 insertions, 0 deletions

diff --git a/nx-X11/util/memleak/fmalloc.c b/nx-X11/util/memleak/fmalloc.c
new file mode 100644
index 000000000..bce5c4388
--- /dev/null
+++ b/nx-X11/util/memleak/fmalloc.c
@@ -0,0 +1,1256 @@
+/*
+ * $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