Logo Search packages:      
Sourcecode: fair version File versions  Download package

avlr.c

/*****************************************************************************

    avlr.c - Extra functions for the AVL-tree library.

    Copyright (C) 1998  Michael H. Buselli <cosine@cosine.org>
    Copyright (C) 2000-2005  Wessel Dankers <wsl@nl.linux.org>

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA

    Augmented AVL-tree. Original by Michael H. Buselli <cosine@cosine.org>.

    Modified by Wessel Dankers <wsl@nl.linux.org> to add a bunch of bloat to
    the sourcecode, change the interface and squash a few bugs.
    Mail him if you find new bugs.

*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

#include "avlr.h"

static const avl_node_t *avl_search_leftmost_equal(const avl_tree_t *tree, const avl_node_t *node, const void *item) {
      avl_compare_t cmp = tree->cmp;
      const avl_node_t *r = node;

      for(;;) {
            for(;;) {
                  node = node->left;
                  if(!node)
                        return r;
                  if(cmp(item, node->item))
                        break;
                  r = node;
            }
            for(;;) {
                  node = node->right;
                  if(!node)
                        return r;
                  if(!cmp(item, node->item))
                        break;
            }
            r = node;
      }
}

static const avl_node_t *avl_search_rightmost_equal(const avl_tree_t *tree, const avl_node_t *node, const void *item) {
      avl_compare_t cmp = tree->cmp;
      const avl_node_t *r = node;

      for(;;) {
            for(;;) {
                  node = node->right;
                  if(!node)
                        return r;
                  if(cmp(item, node->item))
                        break;
                  r = node;
            }
            for(;;) {
                  node = node->left;
                  if(!node)
                        return r;
                  if(!cmp(item, node->item))
                        break;
            }
            r = node;
      }
}

avl_node_t *avl_search_rightish(const avl_tree_t *tree, const void *item, int *exact) {
      avl_node_t *node;
      avl_compare_t cmp;
      int c;

      if(!exact)
            exact = &c;

      if(!tree)
            return *exact = 0, NULL;

      node = tree->top;

      if(!node)
            return *exact = 0, NULL;

      cmp = tree->cmp;

      for(;;) {
            c = cmp(item, node->item);

            if(c < 0) {
                  if(node->left)
                        node = node->left;
                  else
                        return *exact = 0, node->prev;
            } else if(c > 0) {
                  if(node->right)
                        node = node->right;
                  else
                        return *exact = 0, node;
            } else {
                  return *exact = 1, node;
            }
      }
}

avl_node_t *avl_search_left(const avl_tree_t *tree, const void *item, int *exact) {
      avl_node_t *node;
      int c;

      if(!exact)
            exact = &c;

      if(!tree)
            return *exact = 0, NULL;

      node = avl_search_rightish(tree, item, exact);

      if(*exact)
            return (avl_node_t *)avl_search_leftmost_equal(tree, node, item);

      if(node)
            return node->next;

      return tree->head;
}

avl_node_t *avl_search_right(const avl_tree_t *tree, const void *item, int *exact) {
      const avl_node_t *node;
      int c;

      if(!exact)
            exact = &c;

      node = avl_search_rightish(tree, item, exact);
      if(*exact)
            node = avl_search_rightmost_equal(tree, node, item);

      return (avl_node_t *)node;
}

avl_node_t *avl_insert_left(avl_tree_t *avltree, avl_node_t *newnode) {
      return avl_insert_before(avltree, avl_search_left(avltree, newnode->item, NULL), newnode);
}

avl_node_t *avl_insert_right(avl_tree_t *avltree, avl_node_t *newnode) {
      return avl_insert_after(avltree, avl_search_right(avltree, newnode->item, NULL), newnode);
}

avl_node_t *avl_insert_somewhere(avl_tree_t *avltree, avl_node_t *newnode) {
      return avl_insert_after(avltree, avl_search_rightish(avltree, newnode->item, NULL), newnode);
}

avl_node_t *avl_item_insert_somewhere(avl_tree_t *avltree, void *item) {
      avl_node_t *newnode;

      if(!avltree)
            return errno = EFAULT, NULL;

      newnode = avl_init_node(malloc(sizeof(avl_node_t)), item);
      if(newnode)
            return avl_insert_somewhere(avltree, newnode);
      return NULL;
}

avl_node_t *avl_item_insert_left(avl_tree_t *avltree, void *item) {
      avl_node_t *newnode;

      if(!avltree)
            return errno = EFAULT, NULL;

      newnode = avl_init_node(malloc(sizeof(avl_node_t)), item);
      if(newnode)
            return avl_insert_left(avltree, newnode);
      return NULL;
}

avl_node_t *avl_item_insert_right(avl_tree_t *avltree, void *item) {
      avl_node_t *newnode;

      if(!avltree)
            return errno = EFAULT, NULL;

      newnode = avl_init_node(malloc(sizeof(avl_node_t)), item);
      if(newnode)
            return avl_insert_right(avltree, newnode);
      return NULL;
}

Generated by  Doxygen 1.6.0   Back to index