aboutsummaryrefslogtreecommitdiff
path: root/nx-X11/util/memleak/fmalloc.c
diff options
context:
space:
mode:
authorReinhard Tartler <siretart@tauware.de>2011-10-10 17:43:39 +0200
committerReinhard Tartler <siretart@tauware.de>2011-10-10 17:43:39 +0200
commitf4092abdf94af6a99aff944d6264bc1284e8bdd4 (patch)
tree2ac1c9cc16ceb93edb2c4382c088dac5aeafdf0f /nx-X11/util/memleak/fmalloc.c
parenta840692edc9c6d19cd7c057f68e39c7d95eb767d (diff)
downloadnx-libs-f4092abdf94af6a99aff944d6264bc1284e8bdd4.tar.gz
nx-libs-f4092abdf94af6a99aff944d6264bc1284e8bdd4.tar.bz2
nx-libs-f4092abdf94af6a99aff944d6264bc1284e8bdd4.zip
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
Diffstat (limited to 'nx-X11/util/memleak/fmalloc.c')
-rw-r--r--nx-X11/util/memleak/fmalloc.c1256
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