mad.c

来自「具有IDE功能的编辑器」· C语言 代码 · 共 1,555 行 · 第 1/3 页

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void mad_free (void *x)
#else
void free (void *x)
#endif
{
    char *p = (char *) x;
    HeadPtr h;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc) {
	free (p);
	return;
    }
#endif

    if (!p) {
	mem_error ("Freeing NULL", (HeadPtr) 0, TRUE);
	return;
    }
    SEARCH (active_memory, h, p);
    if (!h) {
	SEARCH (freed_memory, h, p);
	if (h)
	    mem_error ("Freeing something twice", h, TRUE);
	else
	    mem_error ("Freeing something never allocated", h, TRUE);
	return;
    }
    if (data_for_head (h) != (mem *) p) {
	mem_error ("Freeing pointer to middle of allocated block", h, TRUE);
	return;
    }
    if (h->head_magic != ACTIVE_HEAD_MAGIC || tail_for_head (h)->tail_magic != ACTIVE_TAIL_MAGIC)
	mem_error ("Freeing corrupted data", h, TRUE);
    remove_active_block (h);
#ifdef HAS_GET_RETURN_ADDRESS
    get_stack_trace (h->return_stack, MAX_RETURN_STACK);
#endif
    add_freed_block (h);
    if (mad_check_always)
	validate_memory ();
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void *mad_realloc (void *x, unsigned desiredsize)
#else
void *realloc (void *x, unsigned desiredsize)
#endif
{
    char *new, *old = (char *) x;
    HeadPtr h, fh;
    int copysize;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc)
	return realloc (old, desiredsize);
#endif

    if (desiredsize == 0) {
	/* JAC: man realloc says realloc(ptr,0) is equivalent to free(ptr),
	   and returns NULL. */
#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
	mad_free (old);
#else
	free (old);
#endif
	return 0;
    }

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    new = mad_malloc (desiredsize);
#else
    new = malloc (desiredsize);
#endif
    if (!new)
	return 0;
    SEARCH (active_memory, h, old);
    if (!h) {
	SEARCH (freed_memory, fh, old);
	if (fh)
	    mem_error ("Reallocing from freed data", fh, TRUE);
	else if (h)
	    mem_error ("Reallocing from something not allocated", h, TRUE);
    } else {
	if (data_for_head (h) != (mem *) old) {
	    mem_error ("Reallocing from pointer to middle of allocated block", h, TRUE);
	} else {
	    if (h->head_magic != ACTIVE_HEAD_MAGIC ||
		tail_for_head (h)->tail_magic != ACTIVE_TAIL_MAGIC)
		    mem_error ("Reallocing corrupted data", h, TRUE);
	    copysize = desiredsize;
	    if (h->desiredsize < desiredsize)
		copysize = h->desiredsize;
	    memmove (new, old, copysize);
	    remove_active_block (h);
#ifdef HAS_GET_RETURN_ADDRESS
	    get_stack_trace (h->return_stack, MAX_RETURN_STACK);
#endif
	    add_freed_block (h);
	}
    }
    return new;
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void *mad_calloc (unsigned num, unsigned size)
#else
void *calloc (unsigned num, unsigned size)
#endif
{
    char *ret;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc)
	return calloc (num, size);
#endif

    size *= num;
#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    ret = mad_malloc (size);
#else
    ret = malloc (size);
#endif
    if (!ret)
	return 0;
    memset (ret, 0, size);
    return ret;
}

/*
 * Semi-Balanced trees (avl).  This only contains two
 * routines - insert and delete.  Searching is
 * reserved for the client to write.
 */

static int rebalance_right (tree ** treep);
static int rebalance_left (tree ** treep);

/*
 * insert a new node
 *
 * this routine returns non-zero if the tree has grown
 * taller
 */

static int tree_insert (tree ** treep, tree * new, int by_size)
{
    if (!(*treep)) {
	(*treep) = new;
	(*treep)->left = 0;
	(*treep)->right = 0;
	(*treep)->balance = 0;
	return 1;
    } else {
	if (LESS_THAN (*treep, new, by_size)) {
	    if (tree_insert (&((*treep)->right), new, by_size))
		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, by_size)) {
	    if (tree_insert (&((*treep)->left), new, by_size))
		switch (--(*treep)->balance) {
		case 0:
		    return 0;
		case -1:
		    return 1;
		case -2:
		    (void) rebalance_left (treep);
		}
	    return 0;
	} else {
	    return 0;
	}
    }
}

/*
 * delete a node from a tree
 *
 * this routine return non-zero if the tree has been shortened
 */

static int tree_delete (tree ** treep, tree * old, int by_size)
{
    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, by_size)) {
	if (tree_delete (&(*treep)->right, old, by_size))
	    /*
	     * 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, by_size)) {
	if (tree_delete (&(*treep)->left, old, by_size))
	    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 Debauch.  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, by_size)) {
		    switch (++(*treep)->balance) {
		    case 2:
			abort ();
		    case 1:
			return 0;
		    case 0:
			return 1;
		    }
		}
		return 0;
	    } else {
		if (tree_delete (&(*treep)->right, old, by_size)) {
		    switch (--(*treep)->balance) {
		    case -2:
			abort ();
		    case -1:
			return 0;
		    case 0:
			return 1;
		    }
		}
		return 0;
	    }
	}
    }
}

/*
 * 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 int rebalance_right (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 int rebalance_left (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;
	}
    }
}

/********* end fmalloc.c **********************/

#include <stdarg.h>

static void output (char *fmt, ...)
{
    char s[1024];
    va_list args;
    va_start (args, fmt);
    memset (s, 0, sizeof (s));
    vsprintf (s, fmt, args);
    write (output_file, s, strlen (s));
    va_end (args);
}

#endif				/* DEBUG_MALLOC */