btree.c

#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include "linklist.h"

#define _bt_empty(bt) ((bt)->root == NULL ? AD_TRUE : AD_FALSE)

struct _BTNODE {
    struct _BTNODE *left, *right;
    void *data;
};

struct _BTREE {
    unsigned count;
    BTNODE *root;                  /*root node of the binary tree*/
    AD_COMPARE_FUNC *compFunc;     /*pointer to comparison function*/
    pthread_mutex_t mutex;
};

#define BTREE_SIZE sizeof(BTREE)
#define BTNODE_SIZE    sizeof(BTNODE)

BTREE *bt_init (AD_COMPARE_FUNC *compare)
{
    BTREE *bt;

    if ((bt = calloc(1, BTREE_SIZE))) {
   bt->root = NULL;
   bt->compFunc = compare;
   
   pthread_mutex_init(&(bt->mutex), NULL);
    }

    return bt;
}

static BTNODE *_new_node(void *newdata)
{
    BTNODE *node;

    if ((node = malloc(BTNODE_SIZE))) {
   node->data = newdata;
   node->left = node->right = NULL;
    }

    return node;
}

static void _free_single_node(BTNODE *node) {
    if (node)
   free(node);
}

static BTNODE *_rotate_right(BTNODE *node)
{
      /* Make the old parent the right child of the new parent */
      /* The new parent is the old left child of the old parent */
    BTNODE *temp;

    temp = node->left;
    node->left = temp->right;
    temp->right = node;

    return temp;
}

static BTNODE *_rotate_left(BTNODE *node)
{
    /* The new parent is the old right child of the old parent */
    /* Make the old parent the left child of the old parent */
    BTNODE *temp;

    temp = node->right;
    node->right = temp->left;
    temp->left = node;

    return temp;
}

/* uses root insertion with rotation */
static BTNODE *_add(BTNODE *currentNode, void *newdata, AD_COMPARE_FUNC *compFunc)
{
    BTNODE *newnode;

    
    if (currentNode == NULL) {
   newnode = _new_node (newdata);
   currentNode = newnode;

   return currentNode;
    }

//    if (compFunc(newdata, currentNode->data) == AD_LESS_THAN) {
    if (compFunc(newdata, currentNode->data) < 0) {
   currentNode->left = _add(currentNode->left, newdata, compFunc);
   currentNode = _rotate_right(currentNode);
    } else {
   currentNode->right = _add(currentNode->right, newdata, compFunc);
   currentNode = _rotate_left (currentNode);
    }

    return currentNode;  /*Don't forget this*/
}

BTREE *bt_add(BTREE *bt, void *newdata)
{
    if (bt != NULL) {
   pthread_mutex_lock(&(bt->mutex));

   if (_bt_empty(bt) == AD_TRUE)
       bt->root = _new_node(newdata);
   else
       bt->root= _add(bt->root, newdata, bt->compFunc);
   
   bt->count++;
   
   pthread_mutex_unlock(&(bt->mutex));
    }
    
    return bt;
}

AD_BOOLEAN bt_empty(BTREE *bt) {
    return _bt_empty(bt);
}

static void *_traverse(BTNODE *currentNode, AD_TRAVERSE_ORDER order, AD_TRAV_FUNC *travFunc, void *param)
{
    void *data = NULL;

    if (!currentNode)  return NULL;

    switch (order) {
   case AD_PRE_ORDER:
       if (travFunc(currentNode->data, param) == AD_FALSE) {
      data = currentNode->data;
      break;
       }
       _traverse(currentNode->left, order, travFunc, param);
       _traverse(currentNode->right, order, travFunc, param);
       break;
   
   case AD_IN_ORDER:
       _traverse(currentNode->left, order, travFunc, param);
       if (travFunc(currentNode->data, param) == AD_FALSE) {
      data = currentNode->data;
      break;
       }
       _traverse(currentNode->right, order, travFunc, param);
       break;
       
   case AD_POST_ORDER:
       _traverse(currentNode->left, order, travFunc, param);
       _traverse(currentNode->right, order, travFunc, param);
       if (travFunc(currentNode->data, param) == AD_FALSE)
      data = currentNode->data;
       break;
   
   case AD_LEVEL_ORDER:
       break;
   
   case AD_OUT_ORDER:
            _traverse(currentNode->right, order, travFunc, param);
            if (travFunc(currentNode->data, param) == AD_FALSE) {
                data = currentNode->data;
      break;
            }
       _traverse(currentNode->left, order, travFunc, param);
            break;
    }
    
    return data;
}

void *bt_traverse(BTREE *bt, AD_LOCK lock_f, AD_TRAVERSE_ORDER order, AD_TRAV_FUNC *travFunc, void *param)
{
    void *data = NULL;

    if (!bt || (_bt_empty(bt) == AD_TRUE)) return NULL;
    
    if (lock_f)
   pthread_mutex_lock(&(bt->mutex));
    
    if (order == AD_LEVEL_ORDER) {
   QUEUE *q = q_init();
   BTNODE *node;

   q_add(q, bt->root);
   while ((node = q_remove(q))) {
       if (travFunc(node->data, param) == AD_FALSE)
      return data;

       if (node->left)
      q_add(q, node->left);
       
       if (node->right)
      q_add (q, node->right);
   }
   q_free (q);
    } else
   data = _traverse(bt->root, order, travFunc, param);
    
    if (lock_f)
   pthread_mutex_unlock(&(bt->mutex));
   
    return data;
}

static BTNODE *_retrieve(BTNODE *currentNode, void *key, AD_COMPARE_FUNC *compFunc)
{
    AD_RELATION relation;

    if (currentNode == NULL)
   return NULL;       /* not found */

    relation = compFunc(key, currentNode->data);
//    if (relation == AD_LESS_THAN)
    if (relation < 0)
   return _retrieve (currentNode->left, key, compFunc); /* go left */
//    else if (relation == AD_GREATER_THAN)
    else if (relation > 0)
   return _retrieve (currentNode->right, key, compFunc); /* go right */
    else
   return currentNode;  /* you found it */
}

void *bt_find(BTREE *bt, void *key, AD_LOCK lock_f)
{
    BTNODE *node;
    void *data = NULL;
    if (!bt)   return NULL;
    
    if (lock_f)
   pthread_mutex_lock(&(bt->mutex));

    if ((node = _retrieve (bt->root, key, bt->compFunc)))
   data = node->data;
   
    if (lock_f)
   pthread_mutex_unlock(&(bt->mutex));
    
    return data;
}

unsigned bt_count(BTREE *bt)
{
    unsigned count = 0;
    
    if (bt != NULL) {
   pthread_mutex_lock(&(bt->mutex));
   
   count = bt->count;
   
   pthread_mutex_unlock(&(bt->mutex));
    }

    return count;
}

static unsigned _height(BTNODE *node)
{
    int leftHeight, rightHeight;

    if (node == NULL)
   return 0;
   
    leftHeight = _height(node->left);
    rightHeight = _height(node->right);

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

unsigned bt_height(BTREE *bt)
{
    unsigned count = 0;
    
    if (bt != NULL) {
   pthread_mutex_lock(&(bt->mutex));
   
   count = _height(bt->root);

   pthread_mutex_unlock(&(bt->mutex));    
    }

    return count;
}

static void _free_nodes(BTNODE *node)
{
    if (node) {
   _free_nodes(node->left);
   _free_nodes(node->right);

   free(node);
    }
}

void bt_free(BTREE *bt)
{
    if (bt != NULL) {
   pthread_mutex_lock(&(bt->mutex));
   
   _free_nodes(bt->root);
   
   pthread_mutex_unlock(&(bt->mutex));
   pthread_mutex_destroy(&(bt->mutex));
   
   free(bt);
    }
}

/* Delete the smallest node in this subtree. an exemption is when the minimum is
   at the top, i,e., the input parameter 'node' in which case we return the node
   without unlinking it */
static BTNODE *_delete_min(BTNODE *node)
{
      /* not yet tested */
    BTNODE *parent;

    if (node == NULL)
   return NULL;   /* node not found */

    parent = NULL;
    while (node->left) {
   parent = node;
   node = node->left;
    }

    if (parent == NULL)
   return node; /* only one node, therefore it is the 'min' */
    else {
   parent->left = node->right;  /* disconnect the minimum node */
   return node; /* the calling function should be the one to free this node */
    }
}

static BTNODE *_delete (BTNODE *currentNode, void *key, AD_COMPARE_FUNC *compFunc, void **data)
{
    BTNODE *tempNode, *child = NULL;
    AD_RELATION rel;


    if (currentNode == NULL) {
   *data = NULL;
   return NULL;   /*node not found*/
    }
    
    rel = compFunc(key, currentNode->data);
//    if (rel == AD_LESS_THAN)
    if (rel < 0)
   currentNode->left = _delete(currentNode->left, key, compFunc, data);
//    else if (rel == AD_GREATER_THAN)
    else if (rel > 0)
   currentNode->right = _delete(currentNode->right, key, compFunc, data);
    else if (currentNode->right && currentNode->left) {
   /* two children */
   *data = currentNode->data;

   if (currentNode->right->left == NULL) { /* only one node in the right subtree */
       /* swap the contents of the current node and right child */
       tempNode = currentNode->right;
       currentNode->data = tempNode->data;
       currentNode->right = currentNode->right->right; /*Unlink*/
   } else {
       tempNode = _delete_min(currentNode->right);
       currentNode->data = tempNode->data;
   }
   _free_single_node(tempNode);
    } else {
   /* zero or one child */
   *data = currentNode->data;
   tempNode = currentNode;
   
   if (currentNode->left == NULL)
       child = currentNode->right;

        if (currentNode->right == NULL)
       child = currentNode->left;

   /* free the temp node */
   _free_single_node(tempNode);

   return child;
    }
    
    return currentNode;
}

void *bt_delete(BTREE *bt, void *key)
{
    void *data = NULL;


    if (!bt)   return NULL;

    pthread_mutex_lock(&(bt->mutex));

    bt->root = _delete(bt->root, key, bt->compFunc, &data);
    
    if (data)  bt->count--;

    pthread_mutex_unlock(&(bt->mutex));

    return data;
}

static BTNODE *_left(BTNODE *preNode, BTNODE *currentNode)
{
    if (currentNode == NULL)
   return preNode;

    return _left(currentNode, currentNode->left);
}

static BTNODE *_right(BTNODE *preNode, BTNODE *currentNode)
{
    if (currentNode == NULL)
   return preNode;

    return _right(currentNode, currentNode->right);
}

static void *_runing_dir(BTREE *bt, BTNODE *(*_dir)(BTNODE *, BTNODE *))
{
    BTNODE *node;
    void *data = NULL;


    if (!bt)   return NULL;
    
    pthread_mutex_lock(&(bt->mutex));
    
    if ((node = _dir(NULL, bt->root)))
   data = node->data;
    
    pthread_mutex_unlock(&(bt->mutex));
    
    return data;
}

void *bt_left(BTREE *bt)
{
    return _runing_dir(bt, _left);
}

void *bt_right(BTREE *bt)
{
    return _runing_dir(bt, _right);
}