rumavl.c

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

    (*node)->thread[ln] = 0;

    /* all parentage is now one level heavier - balance where necessary */
    stack_update(tree, stack, +1);
    
    return 0;
}


/*----------------------------------------------------------------------------
 * rumavl_insert - like rumavl_set, but only works if the node does not
 * exist. Temporarily replaces overwrite callback with a function that
 * always prevents overwrite, and calls rumavl_set()
 *--------------------------------------------------------------------------*/
int rumavl_insert (RUMAVL *tree, const void *record)
{
    int retv;
    int (*tmp)(RUMAVL *, RUMAVL_NODE *, void *, const void *, void *);
    
    tmp = tree->owcb;
    tree->owcb = insert_cb;
    retv = rumavl_set(tree, record);
    tree->owcb = tmp;
    return retv;
}

/*----------------------------------------------------------------------------
 * rumavl_delete - deletes a node. Beware! this function is the worst part of
 * the library. Think (and draw pictures) when you edit this function.
 *--------------------------------------------------------------------------*/
int rumavl_delete (RUMAVL *tree, const void *record)
{
    RUMAVL_NODE **node, *tmpnode;
    RUMAVL_STACK *stack;
    int dir, ln;

    if (tree->root == NULL)	/* tree is empty */
	return RUMAVL_ERR_NOENT;

    stack = NULL;
    node = &tree->root;

    /* Find desired node */
    while ((dir = rec_cmp(tree, record, NODE_REC(*node))) != 0){
	if (stack_push(tree, &stack, node, dir) != 0)
	    goto nomemout;

	if ((*node)->thread[LINK_NO(dir)] > 0){
	    /* desired node does not exist */
	    stack_destroy(tree, stack);
	    return RUMAVL_ERR_NOENT;
	}
	node = &(*node)->link[LINK_NO(dir)];
    }

    /* OK, we got the node to be deleted, now get confirmation from user */
    if (tree->delcb != NULL &&
	    (ln = tree->delcb(tree, *node, NODE_REC(*node), tree->udata)) 
	    != 0){
	stack_destroy(tree, stack);
	return ln;
    }

    if ((*node)->thread[LEFT] > 0){
	if ((*node)->thread[RIGHT] > 0){
	    /* ooh look, we're a leaf */
	    tmpnode = *node;
	    if (stack != NULL){
		/* This node has a parent, which will need to take over a
		 * thread from the node being deleted. First we work out
		 * which (left/right) child we are of parent, then give
		 * parent the respective thread. If the thread destination
		 * points back to us (edge of tree thread), update it to
		 * point to our parent. */
		ln = LINK_NO(stack->dir);
		(*stack->node)->link[ln] = tmpnode->link[ln];
		(*stack->node)->thread[ln] = tmpnode->thread[ln];
		if ((*stack->node)->thread[ln] == 2)
		    (*stack->node)->link[ln]->link[OTHER_LINK(ln)] =
			*stack->node;
	    }else{
		/* 
		 * the only time stack will == NULL is when we are
		 * deleting the root of the tree. We already know that
		 * this is a leaf, so we will be leaving the tree empty.
		 */
		tree->root = NULL;
	    }
	    node_destroy(tree, tmpnode);
	}else{
	    /* *node has only one child, and can be pruned by replacing
	     * *node with its only child. This block of code and the next
	     * should be identical, except that all directions and link
	     * numbers are opposite.
	     *
	     * Let node being deleted = DELNODE for this comment.
	     * DELNODE only has one child (the right child). The left
	     * most descendant of DELNODE will have a thread (left thread)
	     * pointing to DELNODE. This thread must be updated to point
	     * to the node currently pointed to by DELNODE's left thread.
	     *
	     * DELNODE's left thread may point to the opposite edge of the
	     * BST. In this case, the destination of the thread will have
	     * a thread back to DELNODE. This will need to be updated to
	     * point back to the leftmost descendant of DELNODE.
	     */
	    tmpnode = *node;		    /* node being deleted */
	    *node = (*node)->link[RIGHT];   /* right child */
	    /* find left most descendant */
	    while ((*node)->thread[LEFT] == 0) 
		node = &(*node)->link[LEFT];
	    /* inherit thread from node being deleted */
	    (*node)->link[LEFT] = tmpnode->link[LEFT];
	    (*node)->thread[LEFT] = tmpnode->thread[LEFT];
	    /* update reverse thread if necessary */
	    if ((*node)->thread[LEFT] == 2)
		(*node)->link[LEFT]->link[RIGHT] = *node;
	    node_destroy(tree, tmpnode);
	}
    }else if ((*node)->thread[RIGHT] > 0){
	/* see above */
	tmpnode = *node;
	*node = (*node)->link[LEFT];
	while ((*node)->thread[RIGHT] == 0)
	    node = &(*node)->link[RIGHT];
	(*node)->link[RIGHT] = tmpnode->link[RIGHT];
	(*node)->thread[RIGHT] = tmpnode->thread[RIGHT];
	if ((*node)->thread[RIGHT] == 2)
	    (*node)->link[RIGHT]->link[LEFT] = *node;
	node_destroy(tree, tmpnode);
    }else{
	/* Delete a node with children on both sides. We do this by replacing
	 * the node to be deleted (delnode) with its inner most child
	 * on the heavier side (repnode). This in place replacement is quicker
	 * than the previously used method of rotating delnode until it is a
	 * (semi) leaf.
	 *
	 * At this point node points to delnode's parent's link to delnode. */
	RUMAVL_NODE *repnode, *parent;
	int outdir, outln;

	/* find heaviest subtree */
	if ((*node)->balance > 0){
	    outdir = +1;    /* outter direction */
	    dir = -1;	    /* inner direction */
	    outln = 1;	    /* outer link number */
	    ln = 0;	    /* inner link number */
	}else{
	    outdir = -1;    /* same as above, but opposite subtree */
	    dir = +1;
	    outln = 0;
	    ln = 1;
	}
	
	/* Add node to be deleted to the list of nodes to be rebalanced.
	 * Rememer that the replacement node will actually be acted apon,
	 * and that the replacement node should feel the effect of its own
	 * move */
	if (stack_push(tree, &stack, node, outdir) != 0)
	    goto nomemout;
	
	parent = *node;
	repnode = parent->link[outln];

	if (repnode->thread[ln] != 0){
	    /* repnode inherits delnode's lighter tree, and balance, and gets
	     * balance readjusted below */
	    repnode->link[ln] = (*node)->link[ln];
	    repnode->thread[ln] = (*node)->thread[ln];
	    repnode->balance = (*node)->balance;
	}else{
	    /* Now we add delnodes direct child to the list of "to update".
	     * We pass a pointer to delnode's link to its direct child to 
	     * stack_push(), but that pointer is invalid, because when
	     * stack_update() tries to access the link, delnode would have
	     * been destroyed. So, we remember the stack position at which
	     * we passed the faulty pointer to stack_push, and update its
	     * node pointer when we find repnode to point to repnodes 
	     * link on the same side */
	    RUMAVL_STACK *tmpstack;

	    if (stack_push(tree, &stack, &parent->link[outln], dir) != 0)
		goto nomemout;

	    tmpstack = stack;

	    parent = repnode;
	    repnode = repnode->link[ln];

	    /* move towards the innermost child of delnode */		
	    while (repnode->thread[ln] == 0){
		if (stack_push(tree, &stack, &parent->link[ln], dir) != 0)
		    goto nomemout;
		parent = repnode;
		repnode = repnode->link[ln];
	    }

	    if (repnode->thread[outln] == 0){
		/* repnode's parent inherits repnodes only child */
		parent->link[ln] = repnode->link[outln];
	    }else{
		/* parent already has a link to repnode, but it must now be
		 * marked as a thread */
		parent->thread[ln] = 1;
	    }

	    repnode->link[0] = (*node)->link[0];
	    repnode->thread[0] = (*node)->thread[0];
	    repnode->link[1] = (*node)->link[1];
	    repnode->thread[1] = (*node)->thread[1];
	    repnode->balance = (*node)->balance;

	    /* see comment above */
	    tmpstack->node = &repnode->link[outln];
	}
	node_destroy(tree, *node);
	*node = repnode;

	/* innermost child in lighter tree has an invalid thread to delnode,
	 * update it to point to repnode */
	repnode = seq_next(repnode, dir);
	repnode->link[outln] = *node;
    }

    /* update parents' balances */
    stack_update(tree, stack, -1);
    return 0;

nomemout:
    stack_destroy(tree, stack);
    return RUMAVL_ERR_NOMEM;
}

/*----------------------------------------------------------------------------
 * rumavl_find
 *
 * Returns a pointer to the record that matches "record".
 *--------------------------------------------------------------------------*/
void *rumavl_find (RUMAVL *tree, const void *find)
{
    void *record;
    rumavl_node_find(tree, find, &record);
    return record;
}

void *(**rumavl_alloc(RUMAVL *tree))(void *ptr, size_t size, void *udata)
{
    return &tree->alloc;
}

/*----------------------------------------------------------------------------
 * rumavl_record_size - returns size of all records in a tree
 *--------------------------------------------------------------------------*/
size_t rumavl_record_size (RUMAVL *tree)
{
    return tree->reclen;
}

/*----------------------------------------------------------------------------
 * rumavl_node_find
 *
 * Returns a pointer to the node that matches "record".
 *--------------------------------------------------------------------------*/
RUMAVL_NODE *rumavl_node_find (RUMAVL *tree, const void *find, void **record)
{
    RUMAVL_NODE *node;
    int ln;
    
    if (find == NULL || tree->root == NULL)
	goto fail;

    node = tree->root;
    for (;;){
	if ((ln = rec_cmp(tree, find, NODE_REC(node))) == 0){
	    if (record != NULL)
		*record = NODE_REC(node);
	    return node;
	}

	ln = LINK_NO(ln);
	if (node->thread[ln] > 0)
	    break;

	node = node->link[ln];
    }
    /* we didn't find the desired node */

fail:
    if (record != NULL)
	*record = NULL;
    
    return NULL; 
}

/*----------------------------------------------------------------------------
 * rumavl_node_next - find next node 
 *--------------------------------------------------------------------------*/
RUMAVL_NODE *rumavl_node_next (RUMAVL *tree, RUMAVL_NODE *node, int dir,
				    void **record)
{
    /* make sure `dir' is either RUMAVL_ASC or RUMAVL_DESC */
    if (dir == 0)
	goto fail;
    else if (dir > 0)
	dir = RUMAVL_ASC;
    else
	dir = RUMAVL_DESC;

    /* if node is uninitialised, start with first possible node in `dir'
     * direction */
    if (node == NULL){
	/* unless the tree is empty of course */
	if (tree->root == NULL)
	    goto fail;

	dir = OTHER_LINK(LINK_NO(dir));
	node = tree->root;
	while (node->thread[dir] == 0){
	    node = node->link[dir];
	}
	goto found;
    }

    if ((node = seq_next(node, dir)) == NULL)
	goto fail;

    /* fall through */

found:
    if (record != NULL)
	*record = NODE_REC(node);
    return node;

fail:
    if (record != NULL)
	*record = NULL;
    return NULL;
}

/*----------------------------------------------------------------------------
 * rumavl_node_record - returns a pointer to the record stored in a node
 *--------------------------------------------------------------------------*/
void *rumavl_node_record (RUMAVL_NODE *node)
{
    return NODE_REC(node);
}

/*----------------------------------------------------------------------------
 * rumavl_foreach - loop through entire tree, using temporary iterator
 *--------------------------------------------------------------------------*/
extern int rumavl_foreach (RUMAVL *tree, int dir,
	    int (*cbfn)(RUMAVL *, void *, void *), void *udata)
{
    RUMAVL_NODE *node;
    int retv;
    void *record;

    if (cbfn == NULL)
	return RUMAVL_ERR_INVAL;
    
    retv = RUMAVL_ERR_NOENT;
    node = NULL;
    while ((node = rumavl_node_next(tree, node, dir, &record)) != NULL){
	if ((retv = cbfn(tree, record, udata)) != 0)
	    break;
    }

    return retv;
}