rumavl.c

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

/*----------------------------------------------------------------------------
 * RumAVL - Threaded AVL Tree Implementation
 * 
 * Copyright (c) 2005-2007 Jesse Long <[e-mail]>
 * All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 *   1. The above copyright notice and this permission notice shall be
 *	included in all copies or substantial portions of the Software.
 *   2. The origin of the Software must not be misrepresented; you must not
 *	claim that you wrote the original Software.
 *   3. Altered source versions of the Software must be plainly marked as
 *	such, and must not be misrepresented as being the original 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
 * AUTHORS OR COPYRIGHT HOLDERS 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.
 *--------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
 * Although not required by the license, I would appreciate it if you would
 * send me a mail notifying me of bugfixes and enhancements you make to this
 * code. My email address is <[e-mail]>
 *--------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
 *			     DEVELOPEMENT NOTES
 *
 * Links
 *    Each node has two links, link[0] is the left child, and link[1] is the
 *    right child. When a link points to a node that is actually below it in
 *    the BST, the respective thread flag is marked 0. When the link is a
 *    thread, the respective thread flag is marked 1, or 2 if the thread is
 *    to the opposite edge of the BST.
 *    
 * Direction
 *    In RumAVL we use the numbers -1 (RUMAVL_DESC) and +1 (RUMAVL_ASC) to 
 *    indicate direction, where -1 (RUMAVL_DESC) means left or descending in
 *    value, and +1 (RUMAVL_ASC) means right or ascending in value.
 *
 * Threads
 *    In RumAVL, the threads (non-bst links of leaves) are implemented in a
 *    sort of circular list. It is important to note that you cannot go
 *    through the entire list by following the same link, as you would when
 *    going through a linked list. Draw an example threaded AVL tree on paper
 *    and see why.
 *
 *--------------------------------------------------------------------------*/

#include <stdlib.h>
#include <string.h>

#include "rumavl.h"

/* For memory allocation debugging
#ifdef USE_MEMBUG
  #define MEMBUG_DEFINES
  #include <membug.h>
#endif */




/*****************************************************************************
 * 
 * MACROS - to make readability better
 * 
 ****************************************************************************/

/* Link numbers */
#define LEFT		(0)
#define RIGHT		(1)

/* Direction to link no, expects RUMAVL_DESC or RUMAVL_ASC */
#define LINK_NO(i)	(((i) + 1) / 2) /* -1 => 0; 1 => 1 */
/* Get opposite link number, expects LEFT or RIGHT */
#define OTHER_LINK(i)	((i) ^ 1)	/* 1 => 0; 0 => 1 */

/* link no to direction, expects LEFT or RIGHT */
#define DIR_NO(i)	(((i) * 2) - 1) /* 0 => -1; 1 => 1 */
/* opposite direction, expects RUMAVL_DESC or RUMAVL_ASC */
#define OTHER_DIR(i)	((i) * -1)	/* -1 => 1; 1 => -1 */

/* Memory allocation functions */
#define mem_alloc(tree, bytes)		mem_mgr((tree), NULL, (bytes))
#define mem_free(tree, ptr)		mem_mgr((tree), (ptr), 0)
#define mem_relloc(tree, ptr, bytes)	mem_mgr((tree), (ptr), (bytes))




/*****************************************************************************
 * 
 * DATA TYPES
 * 
 ****************************************************************************/

/* 
 * RUMAVL - the handle on the tree
 *
 * All settings for a tree are in the RUMAVL object, including memory
 * management, delete and overwrite callback functions, and the record
 * comparison function pointer.
 */
struct rumavl {
    RUMAVL_NODE *root;		    /* root node in tree */
    size_t reclen;		    /* length of records */
    int (*cmp)(const void *,	    /* function to compare records */
	       const void *, 
	       size_t,
	       void *);
    int (*owcb)(RUMAVL *, RUMAVL_NODE *, void *, const void *, void *);
    int (*delcb)(RUMAVL *, RUMAVL_NODE *, void *, void *);
    void *(*alloc)(void *, size_t, void *);
    void *udata;		    /* user data for callbacks */
};

/*
 * RUMAVL_NODE - the node structure
 *
 * RUMAVL_NODE's contain all information about a specific node, including
 * links to the right and left children of the node, and flags (thread) 
 * indicating whether or not the links are threads or not, and the balance
 * factor of the node.
 *
 * The record associated with each node is allocated along with the node,
 * and can be found directly after the node, by using the NODE_REC() macro.
 */
struct rumavl_node {
    RUMAVL_NODE	   *link[2];	/* links to child nodes */
    char	    thread[2];	/* flags for links, normal link or thread? */
    signed char	    balance;	/* balance factor for node */
    void	   *rec;
    #define NODE_REC(node) ((node)->rec)
};

/*
 * RUMAVL_STACK - a stack of nodes forming a path to a node
 *
 * RUMAVL_STACK's are used while deleting and inserting nodes, where effects
 * could be felt by all parents of the node. RUMAVL_STACK's are implemented
 * in a singly linked list. This is a change from the method used by most AVL
 * trees, where a static array node pointers are allocated. Linked lists allow
 * fo an unlimited height in the AVL tree.
 *
 * node is a pointer to the parent node's pointer to the node in question.
 * dir is the direction of the descent from this node.
 */
typedef struct rumavl_stack RUMAVL_STACK;
struct rumavl_stack {
    RUMAVL_STACK *next;
    RUMAVL_NODE **node;
    int dir;
};

/* various other RumAVL specific structs defined in rumavl.h */




/*****************************************************************************
 * 
 * FORWARD DECLERATIONS
 * 
 ****************************************************************************/

static RUMAVL_NODE *seq_next (RUMAVL_NODE *node, int dir);
static RUMAVL_NODE *node_new(RUMAVL *tree, const void *record);
static void node_destroy (RUMAVL *tree, RUMAVL_NODE *node);
static int stack_push (RUMAVL *tree, RUMAVL_STACK **stack, RUMAVL_NODE **node,
						int dir);
static void stack_destroy(RUMAVL *tree, RUMAVL_STACK *stack);
static void stack_update(RUMAVL *tree, RUMAVL_STACK *stack, signed char diff);

static signed char balance (RUMAVL_NODE **node, int dir);
static signed char rotate (RUMAVL_NODE **node, int dir);

static void *mem_mgr (RUMAVL *tree, void *ptr, size_t size);

static int rec_cmp (RUMAVL *tree, const void *reca, const void *recb);
static int my_cmp (const void *a, const void *b, size_t n, void *udata);

static int insert_cb (RUMAVL *t, RUMAVL_NODE *n, void *r1, const void *r2, 
	void *udata);



/*****************************************************************************
 * 
 * PUBLIC FUNCTIONS
 * 
 ****************************************************************************/

/*----------------------------------------------------------------------------
 * rumavl_new - allocates a new RUMAVL object, and initialises it. This is the
 * only time the user gets to set the record length and record comparison
 * function, to avoid data loss.
 *--------------------------------------------------------------------------*/
RUMAVL *rumavl_new (size_t reclen, 
		    int (*cmp)(const void *, const void *, size_t, void *),
		    void *(*alloc)(void *, size_t, void *),
		    void *udata)
{
    RUMAVL *tree;

    if (reclen < 1)
	return NULL;

    if (alloc == NULL)
	tree = malloc(sizeof(RUMAVL));
    else
	tree = alloc(NULL, sizeof(RUMAVL), udata);

    if (tree == NULL)
	return NULL;
	
    tree->root = NULL;
    
    tree->owcb = NULL;
    tree->delcb = NULL;

    tree->alloc = alloc;

    tree->reclen = reclen;
    tree->udata = udata;

    if (cmp == NULL)
	tree->cmp = my_cmp;
    else
	tree->cmp = cmp;
    
    return tree;
}

/*----------------------------------------------------------------------------
 * rumavl_destroy - cleanly frees all memory used by the RUMAVL, as well as 
 * all nodes. All nodes are passed to the delete callback function in case the
 * user has a special way of destroying nodes. The return value of the delete
 * callback function is ignored, because once we start destroying we cant
 * simply undestroy half the nodes.
 *--------------------------------------------------------------------------*/
void rumavl_destroy (RUMAVL *tree)
{
    RUMAVL_NODE *node, *tmp;
    
    if (tree->root != NULL){
	/* walk through tree deleting all */
	node = tree->root;
	while (node->thread[LEFT] == 0) /* move to bottom left most node */
	    node = node->link[LEFT];
	while (node != NULL){
	    tmp = seq_next(node, RUMAVL_ASC);
	    if (tree->delcb != NULL){
		tree->delcb(tree, node, NODE_REC(node), tree->udata);
	    }
	    node_destroy(tree, node);
	    node = tmp;
	}
    }

    if (tree->alloc == NULL)
	free(tree);
    else
	tree->alloc(tree, 0, tree->udata);
}

/*---------------------------------------------------------------------------
 * rumavl_udata - get a pointer to the tree's user pointer
 *-------------------------------------------------------------------------*/
void **rumavl_udata (RUMAVL *tree)
{
    return &tree->udata;
}

int (**rumavl_owcb(RUMAVL *tree))(RUMAVL *, RUMAVL_NODE *, void *, 
	const void *, void *)
{
    return &tree->owcb;
}

int (**rumavl_delcb(RUMAVL *tree))(RUMAVL *, RUMAVL_NODE *, void *, void *)
{
    return &tree->delcb;
}

/*----------------------------------------------------------------------------
 * rumavl_set - set a node, overwriting if necessary, or creating if the node
 * does not exist
 *--------------------------------------------------------------------------*/
int rumavl_set (RUMAVL *tree, const void *record)
{
    RUMAVL_NODE **node, *tmp;
    RUMAVL_STACK *stack;
    int ln;
    
    if (tree->root == NULL){
	/* This is the first node in the tree */
	if ((tree->root = node_new(tree, record)) == NULL)
	    return RUMAVL_ERR_NOMEM;
	tree->root->link[LEFT] = tree->root;
	tree->root->link[RIGHT] = tree->root;
	tree->root->thread[LEFT] = 2;
	tree->root->thread[RIGHT] = 2;
	return 0;
    }

    /* Since the tree is not empty, we must descend towards the nodes ideal
     * possition, and we may even find an existing node with the same record.
     * We keep a list parents for the eventual node position, because these
     * parents may become inbalanced by a new insertion. */

    stack = NULL;
    node = &tree->root;
    for (;;){
	if ((ln = rec_cmp(tree, record, NODE_REC(*node))) == 0){
	    /* OK, we found the exact node we wish to set, and we now
	     * overwrite it. No change happens to the tree structure */
	    stack_destroy(tree, stack);
	    
	    if (tree->owcb != NULL &&
		    (ln = tree->owcb(tree, *node, NODE_REC(*node), 
				      record, tree->udata)) != 0){
		return ln;
	    }
	    
	    memcpy(NODE_REC(*node), record, tree->reclen);
	    return 0;
	}
	
	/* *node is not the node we seek */
	
	if (stack_push(tree, &stack, node, ln)){
	    stack_destroy(tree, stack);
	    return RUMAVL_ERR_NOMEM;
	}
	
	ln = LINK_NO(ln);
	if ((*node)->thread[ln] > 0){
	    /* This is as close to the correct node as we can get. We will
	     * now break and add the new node as a leaf */
	    break;
	}
	
	node = &(*node)->link[ln];
    }
	    
    /* we have reached a leaf, add new node here */
    if ((tmp = node_new(tree, record)) == NULL){
	stack_destroy(tree, stack);
	return RUMAVL_ERR_NOMEM;
    }
    /* new child inherits parent thread */
    tmp->link[ln] = (*node)->link[ln];
    tmp->thread[ln] = (*node)->thread[ln];
    if (tmp->thread[ln] == 2)
	tmp->link[ln]->link[OTHER_LINK(ln)] = tmp;
    
    tmp->link[OTHER_LINK(ln)] = *node;
    tmp->thread[OTHER_LINK(ln)] = 1;
    (*node)->link[ln] = tmp;