aboutsummaryrefslogtreecommitdiff
path: root/nx-X11/util/memleak/fmalloc.c
diff options
context:
space:
mode:
authorMike Gabriel <mike.gabriel@das-netzwerkteam.de>2015-02-02 15:02:49 +0100
committerMike Gabriel <mike.gabriel@das-netzwerkteam.de>2015-02-02 15:02:49 +0100
commitb16b9e4656e7199c2aec74a4c8ebc7a875d3ba73 (patch)
tree4361edef0d42d5bf5ac984ef72b4fac35426eae7 /nx-X11/util/memleak/fmalloc.c
parent0d5a83e986f39982c0924652a3662e60b1f23162 (diff)
downloadnx-libs-b16b9e4656e7199c2aec74a4c8ebc7a875d3ba73.tar.gz
nx-libs-b16b9e4656e7199c2aec74a4c8ebc7a875d3ba73.tar.bz2
nx-libs-b16b9e4656e7199c2aec74a4c8ebc7a875d3ba73.zip
massive reduction of unneeded files
Diffstat (limited to 'nx-X11/util/memleak/fmalloc.c')
-rw-r--r--nx-X11/util/memleak/fmalloc.c1256
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