rumavl.c

CRFsuite is a very fast implmentation of the Conditional Random Fields (CRF) algorithm. It handles t

/*----------------------------------------------------------------------------
 * rumavl_strerror - return string description of RumAVL error code
 *--------------------------------------------------------------------------*/
const char *rumavl_strerror (int errno)
{
    switch (errno){
	case 0:
	    return "Operation successful";
	case RUMAVL_ERR_INVAL:
	    return "Invalid argument to function";
	case RUMAVL_ERR_NOMEM:
	    return "Insufficient memory to complete operation";
	case RUMAVL_ERR_NOENT:
	    return "Entry does not exist";
	case RUMAVL_ERR_EORNG:
	    return "No more entries in range";
	case RUMAVL_ERR_EXIST:
	    return "Entry already exists";
    }
    return "UNKNOWN ERROR";
}




/*****************************************************************************
 * 
 * PRIVATE FUNCTIONS
 * 
 ****************************************************************************/

/*----------------------------------------------------------------------------
 * insert_cb - used by rumavl_insert() to disallow any overwriting by
 * rumavl_set()
 *--------------------------------------------------------------------------*/
static int insert_cb (RUMAVL *t, RUMAVL_NODE *n, void *r1, const void *r2, 
	void *udata)
{
    (void) t; (void) r1; (void) r2; (void) udata; (void) n;
    return RUMAVL_ERR_EXIST;
}

/*----------------------------------------------------------------------------
 * seq_next - return a pointer to the next node in sequence
 *--------------------------------------------------------------------------*/
static RUMAVL_NODE *seq_next (RUMAVL_NODE *node, int dir)
{
    int ln;
    
    ln = LINK_NO(dir);
    if (node->thread[ln] == 2){
	return NULL;
    }else if (node->thread[ln] == 1){
	return node->link[ln];
    }
    node = node->link[ln];
    ln = OTHER_LINK(ln);
    while (node->thread[ln] == 0){
	node = node->link[ln];
    }
    return node;
}

/*----------------------------------------------------------------------------
 * node_new - create a new node. MUST update link[] and thread[] after calling
 * this function
 *--------------------------------------------------------------------------*/
static RUMAVL_NODE *node_new(RUMAVL *tree, const void *record)
{
    RUMAVL_NODE *node;

    if ((node = mem_alloc(tree, sizeof(RUMAVL_NODE))) == NULL)
	return NULL;

    if ((node->rec = mem_alloc(tree, tree->reclen)) == NULL){
	mem_free(tree, node);
	return NULL;
    }

    memcpy(node->rec, record, tree->reclen);
    node->balance = 0;
    node->link[0] = NULL;
    node->link[1] = NULL;
    node->thread[0] = 0;
    node->thread[1] = 0;
    return node;
}

/*----------------------------------------------------------------------------
 * node_destroy - cleanly destroy node
 *--------------------------------------------------------------------------*/
static void node_destroy (RUMAVL *tree, RUMAVL_NODE *node)
{
    mem_free(tree, node);
}

/*----------------------------------------------------------------------------
 * stack_push - push a node entry onto stack, for rumavl_set() and 
 * rumavl_delete(). If this is the first entry, *stack should == NULL
 *--------------------------------------------------------------------------*/
static int stack_push(RUMAVL *tree, RUMAVL_STACK **stack, RUMAVL_NODE **node, 
			int dir)
{
    RUMAVL_STACK *tmp;
    
    if ((tmp = mem_alloc(tree, sizeof(RUMAVL_STACK))) == NULL)
	return -1;
    
    tmp->next = *stack;
    *stack = tmp;
    tmp->node = node;
    tmp->dir = dir;

    return 0;
}

/*----------------------------------------------------------------------------
 * stack_destroy - free up a stack
 *--------------------------------------------------------------------------*/
static void stack_destroy(RUMAVL *tree, RUMAVL_STACK *stack)
{
    RUMAVL_STACK *tmp;
    while (stack != NULL){
	tmp = stack;
	stack = stack->next;
	mem_free(tree, tmp);
    }
}

/*----------------------------------------------------------------------------
 * stack_update - goes up stack readjusting balance as needed. This function
 * serves as a testiment to the philosophy of commenting while you code, 'cos
 * hell if I can remember how I got to this. I think is has something to do
 * with the varying effects on tree height, depending on exactly which sub 
 * tree, or sub-sub tree was modified. TODO study and comment
 *--------------------------------------------------------------------------*/
static void stack_update(RUMAVL *tree, RUMAVL_STACK *stack, signed char diff)
{
    RUMAVL_STACK *tmpstack;
    
    /* if diff becomes 0, we quit, because no further change to ancestors
     * can be made */
    while (stack != NULL && diff != 0){
	signed char ob, nb;
	ob = (*stack->node)->balance;
	(*stack->node)->balance += diff * (signed char)stack->dir;
	nb = (*stack->node)->balance;
	if (diff < 0){
	    if (stack->dir == -1 && ob < 0){
		if (nb > 0)
		    nb = 0;
		diff = (nb - ob) * -1;
	    }else if (stack->dir == 1 && ob > 0){
		if (nb < 0)
		    nb = 0;
		diff = nb - ob;
	    }else{
		diff = 0;
	    }
	}else{
	    if (stack->dir == -1 && nb < 0){
		if (ob > 0)
		    ob = 0;
		diff = (nb - ob) * -1;
	    }else if (stack->dir == 1 && nb > 0){
		if (ob < 0)
		    ob = 0;
		diff = nb - ob;
	    }else{
		diff = 0;
	    }
	}
	while ((*stack->node)->balance > 1){
	    diff += balance(stack->node, -1);
	}
	while ((*stack->node)->balance < -1){
	    diff += balance(stack->node, 1);
	}
	tmpstack = stack;
	stack = stack->next;
	mem_free(tree, tmpstack);
    }

    /* we may exit early if diff becomes 0. We still need to free all stack
     * entries */
    while (stack != NULL){
	tmpstack = stack;
	stack = stack->next;
	mem_free(tree, tmpstack);
    }
}

/*----------------------------------------------------------------------------
 * my_cmp - a wrapper around memcmp() for default record comparison function.
 *--------------------------------------------------------------------------*/
static int my_cmp (const void *a, const void *b, size_t n, void *udata)
{
    (void) udata;
    return memcmp(a, b, n);
}

/*----------------------------------------------------------------------------
 * rec_cmp - a wrapper around the record comparison function, that only
 * returns 0, RUMAVL_ASC or RUMAVL_DESC.
 *--------------------------------------------------------------------------*/
static int rec_cmp (RUMAVL *tree, const void *reca, const void *recb)
{
    int retv;
    retv = tree->cmp(reca, recb, tree->reclen, tree->udata);
    if (retv < 0)
	return RUMAVL_DESC;
    if (retv > 0)
	return RUMAVL_ASC;
    return 0;
}

/*----------------------------------------------------------------------------
 * Balance - rotate or double rotate as needed. Sometimes simply rotating a
 * tree is inefficient, as it leaves the tree as inbalanced as it was before
 * the rotate. To rectify this, we first rotate the heavier child so that the
 * heavier grandchild is on the outside, then rotate as per normal.
 *
 * TODO Check all callers, and make sure that they call this function sanely,
 *	and then remove unnecessary checks.
 *--------------------------------------------------------------------------*/
static signed char balance (RUMAVL_NODE **node, int dir)
{
    int ln;
    signed char retv;
    
    if (node == NULL || *node == NULL || (dir * dir) != 1)
	return 0;

    ln = OTHER_LINK(LINK_NO(dir)); /* link number of new root */
    
    /* new root must exist */
    if ((*node)->thread[ln] > 0)
	return 0;

    retv = 0;
    if ((*node)->link[ln]->balance == (char) dir &&
	    (*node)->link[ln]->thread[OTHER_LINK(ln)] == 0){
	/* double rotate if inner grandchild is heaviest */
	retv = rotate (&((*node)->link[ln]), OTHER_DIR(dir));
    }
    
    return retv + rotate (node, dir);
}

/*----------------------------------------------------------------------------
 * rotate
 *
 * rotates a tree rooted at *node. dir determines the direction of the rotate,
 * dir < 0 -> left rotate; dir >= 0 -> right rotate
 *
 * TODO How sure are we that all callers pass decent `dir' values?
 * TODO Restudy the tree height modification and balance factor algorithms,
 *	and document them.
 *--------------------------------------------------------------------------*/
static signed char rotate (RUMAVL_NODE **node, int dir)
{
    RUMAVL_NODE *tmp;
    signed char a, b, ad, bd, retv;
    int ln;

    /* force |dir| to be either -1 or +1 */
    if (node == NULL || *node == NULL || (dir * dir) != 1)
	return 0;

    ln = LINK_NO(dir);
    ln = OTHER_LINK(ln); /* link number of new root */

    /* new root must exist */
    if ((*node)->thread[ln] > 0)
	return 0;

    /* calculate effect on tree height */
    if ((dir == 1 && (*node)->balance < 0 && (*node)->link[0]->balance >= 0)||
       (dir == -1 && (*node)->balance > 0 && (*node)->link[1]->balance <= 0)){
	retv = 0;
    }else{
	if (dir == 1){
	    if ((*node)->balance < -1)
		retv = -1;
	    else if ((*node)->balance == -1)
		retv = 0;
	    else
		retv = +1;
	}else{
	    if ((*node)->balance > 1)
		retv = -1;
	    else if ((*node)->balance == 1)
		retv = 0;
	    else
		retv = +1;
	}
    }
		    

    /* rotate tree */
    tmp = *node;
    *node = tmp->link[ln];
    if ((*node)->thread[OTHER_LINK(ln)] > 0){
	tmp->thread[ln] = 1;
    }else{
	tmp->link[ln] = (*node)->link[OTHER_LINK(ln)];
	tmp->thread[ln] = 0;
    }
    (*node)->link[OTHER_LINK(ln)] = tmp;
    (*node)->thread[OTHER_LINK(ln)] = 0;
    


    /* rebalance factors after rotate matrix */
    a = tmp->balance;
    b = (*node)->balance;

    if (a > 0)
	ad = 1;
    else if (a < 0)
	ad = -1;
    else
	ad = 0;

    if (b > 0)
	bd = 1;
    else if (b < 0)
	bd = -1;
    else
	bd = 0;
    
    if (ad == OTHER_DIR(dir)){
	if (bd == OTHER_DIR(dir)){
	    tmp->balance += (b * -1) + dir;
	    if (tmp->balance * dir > 0)
		(*node)->balance = (tmp->balance - (b * -1)) + dir;
	    else
		(*node)->balance += dir;
	}else{
	    tmp->balance += dir;
	    (*node)->balance += dir;
	}
    }else{
	if (bd == OTHER_DIR(dir)){
	    tmp->balance += (b * -1) + dir;
	    (*node)->balance += dir + tmp->balance; 
	}else{
	    tmp->balance += dir;
	    (*node)->balance += dir + tmp->balance;
	}
    }
    
    return retv;
}

/*----------------------------------------------------------------------------
 * mem_alloc
 *
 * default memory allocation function (malloc wrapper)
 *--------------------------------------------------------------------------*/
static void *mem_mgr (RUMAVL *tree, void *ptr, size_t size)
{
    if (tree->alloc != NULL)
	return tree->alloc(ptr, size, tree->udata);
 
    return realloc(ptr, size);
}