avl.c File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <time.h>
#include <string.h>
#include "avl.h"
#include "assert.h"
#include "list.h"

Go to the source code of this file.

Functions
static int	avl_max (int x, int y)
static int	avl_min (int x, int y)
static struct avl_node *	avl_find_rec (struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result)
static void	avl_insert_before (struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
static void	avl_insert_after (struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
static void	post_insert (struct avl_tree *tree, struct avl_node *node)
static void	avl_delete_worker (struct avl_tree *tree, struct avl_node *node)
static void	avl_remove (struct avl_tree *tree, struct avl_node *node)
void	avl_init (struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
static struct avl_node *	avl_next (struct avl_node *node)
struct avl_node *	avl_find (const struct avl_tree *tree, const void *key)
struct avl_node *	avl_find_lessequal (const struct avl_tree *tree, const void *key)
struct avl_node *	avl_find_greaterequal (const struct avl_tree *tree, const void *key)
int	avl_insert (struct avl_tree *tree, struct avl_node *new)
void	avl_delete (struct avl_tree *tree, struct avl_node *node)
static void	avl_rotate_right (struct avl_tree *tree, struct avl_node *node)
static void	avl_rotate_left (struct avl_tree *tree, struct avl_node *node)
static void	avl_post_delete (struct avl_tree *tree, struct avl_node *node)
static struct avl_node *	avl_local_min (struct avl_node *node)

Function Documentation

avl_delete()

void avl_delete	(	struct avl_tree *	tree,
		struct avl_node *	node
	)

Remove a node from an avl tree

Parameters

tree	pointer to tree
node	pointer to node

Definition at line 307 of file avl.c.

{
  struct avl_node *next;
  struct avl_node *parent;
  struct avl_node *left;
  struct avl_node *right;
  if (node->leader) {
    if (tree->allow_dups
        && !list_is_last(&node->list, &tree->list_head)
        && !(next = avl_next(node))->leader) {
      next->leader = true;
      next->balance = node->balance;
 
      parent = node->parent;
      left = node->left;
      right = node->right;
 
      next->parent = parent;
      next->left = left;
      next->right = right;
 
      if (parent == NULL)
        tree->root = next;
 
      else {
        if (node == parent->left)
          parent->left = next;
 
        else
          parent->right = next;
      }
 
      if (left != NULL)
        left->parent = next;
 
      if (right != NULL)
        right->parent = next;
    }
 
    else
      avl_delete_worker(tree, node);
  }
 
  avl_remove(tree, node);
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_delete_worker()

static void avl_delete_worker ( struct avl_tree *  tree, struct avl_node *  node  )

static

Definition at line 594 of file avl.c.

{
  struct avl_node *parent, *min;
 
  parent = node->parent;
 
  if (node->left == NULL && node->right == NULL) {
    if (parent == NULL) {
      tree->root = NULL;
      return;
    }
 
    if (parent->left == node) {
      parent->left = NULL;
      parent->balance++;
 
      if (parent->balance == 1)
        return;
 
      if (parent->balance == 0) {
        avl_post_delete(tree, parent);
        return;
      }
 
      if (parent->right->balance == 0) {
        avl_rotate_left(tree, parent);
        return;
      }
 
      if (parent->right->balance == 1) {
        avl_rotate_left(tree, parent);
        avl_post_delete(tree, parent->parent);
        return;
      }
 
      avl_rotate_right(tree, parent->right);
      avl_rotate_left(tree, parent);
      avl_post_delete(tree, parent->parent);
      return;
    }
 
    if (parent->right == node) {
      parent->right = NULL;
      parent->balance--;
 
      if (parent->balance == -1)
        return;
 
      if (parent->balance == 0) {
        avl_post_delete(tree, parent);
        return;
      }
 
      if (parent->left->balance == 0) {
        avl_rotate_right(tree, parent);
        return;
      }
 
      if (parent->left->balance == -1) {
        avl_rotate_right(tree, parent);
        avl_post_delete(tree, parent->parent);
        return;
      }
 
      avl_rotate_left(tree, parent->left);
      avl_rotate_right(tree, parent);
      avl_post_delete(tree, parent->parent);
      return;
    }
  }
 
  if (node->left == NULL) {
    if (parent == NULL) {
      tree->root = node->right;
      node->right->parent = NULL;
      return;
    }
 
    assert(node->right);
    node->right->parent = parent;
 
    if (parent->left == node)
      parent->left = node->right;
 
    else
      parent->right = node->right;
 
    avl_post_delete(tree, node->right);
    return;
  }
 
  if (node->right == NULL) {
    if (parent == NULL) {
      tree->root = node->left;
      node->left->parent = NULL;
      return;
    }
 
    node->left->parent = parent;
 
    if (parent->left == node)
      parent->left = node->left;
 
    else
      parent->right = node->left;
 
    avl_post_delete(tree, node->left);
    return;
  }
 
  min = avl_local_min(node->right);
  avl_delete_worker(tree, min);
  parent = node->parent;
 
  min->balance = node->balance;
  min->parent = parent;
  min->left = node->left;
  min->right = node->right;
 
  if (min->left != NULL)
    min->left->parent = min;
 
  if (min->right != NULL)
    min->right->parent = min;
 
  if (parent == NULL) {
    tree->root = min;
    return;
  }
 
  if (parent->left == node) {
    parent->left = min;
    return;
  }
 
  parent->right = min;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_find()

struct avl_node* avl_find	(	const struct avl_tree *	tree,
		const void *	key
	)

Finds a node in an avl-tree with a certain key

Parameters

tree	pointer to avl-tree
key	pointer to key

Returns

pointer to avl-node with key, NULL if no node with this key exists.

Definition at line 115 of file avl.c.

{
  struct avl_node *node;
  int diff;
 
  if (tree->root == NULL)
    return NULL;
 
  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
 
  return diff == 0 ? node : NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_find_greaterequal()

struct avl_node* avl_find_greaterequal	(	const struct avl_tree *	tree,
		const void *	key
	)

Finds the first node in an avl-tree with a key greater or equal than the specified key

Parameters

tree	pointer to avl-tree
key	pointer to specified key

Returns

pointer to avl-node, NULL if no node with key greater or equal specified key exists.

Definition at line 179 of file avl.c.

                                                                    {
  struct avl_node *node, *next;
  int diff;
 
  if (tree->root == NULL)
    return NULL;
 
  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
 
  /* go right as long as key>node.key */
  while (diff > 0) {
    if (list_is_last(&node->list, &tree->list_head)) {
      return NULL;
    }
 
    node = (struct avl_node *)node->list.next;
    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
  }
 
  /* go left as long as key<=next_node.key */
  next = node;
  while (diff <= 0) {
    node = next;
    if (list_is_first(&node->list, &tree->list_head)) {
      break;
    }
 
    next = (struct avl_node *)node->list.prev;
    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
  }
  return node;
}

Here is the call graph for this function:

avl_find_lessequal()

struct avl_node* avl_find_lessequal	(	const struct avl_tree *	tree,
		const void *	key
	)

Finds the last node in an avl-tree with a key less or equal than the specified key

Parameters

tree	pointer to avl-tree
key	pointer to specified key

Returns

pointer to avl-node, NULL if no node with key less or equal specified key exists.

Definition at line 137 of file avl.c.

                                                                 {
  struct avl_node *node, *next;
  int diff;
 
  if (tree->root == NULL)
    return NULL;
 
  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
 
  /* go left as long as key<node.key */
  while (diff < 0) {
    if (list_is_first(&node->list, &tree->list_head)) {
      return NULL;
    }
 
    node = (struct avl_node *)node->list.prev;
    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
  }
 
  /* go right as long as key>=next_node.key */
  next = node;
  while (diff >= 0) {
    node = next;
    if (list_is_last(&node->list, &tree->list_head)) {
      break;
    }
 
    next = (struct avl_node *)node->list.next;
    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
  }
  return node;
}

Here is the call graph for this function:

avl_find_rec()

static struct avl_node * avl_find_rec ( struct avl_node *  node, const void *  key, avl_tree_comp  comp, void *  ptr, int *  cmp_result  )

static

Definition at line 354 of file avl.c.

{
  int diff;
 
  diff = (*comp) (key, node->key, cmp_ptr);
  *cmp_result = diff;
 
  if (diff < 0) {
    if (node->left != NULL)
      return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
 
    return node;
  }
 
  if (diff > 0) {
    if (node->right != NULL)
      return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
 
    return node;
  }
 
  return node;
}

Here is the caller graph for this function:

avl_init()

void avl_init	(	struct avl_tree *	tree,
		avl_tree_comp	comp,
		bool	allow_dups,
		void *	ptr
	)

Initialize a new avl_tree struct

Parameters

tree	pointer to avl-tree
comp	pointer to comparator for the tree
allow_dups	true if the tree allows multiple elements with the same
ptr	custom parameter for comparator

Definition at line 92 of file avl.c.

{
  INIT_LIST_HEAD(&tree->list_head);
  tree->root = NULL;
  tree->count = 0;
  tree->comp = comp;
  tree->allow_dups = allow_dups;
  tree->cmp_ptr = ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_insert()

int avl_insert	(	struct avl_tree *	tree,
		struct avl_node *	new
	)

Inserts an avl_node into a tree

Parameters

tree	pointer to tree
new	pointer to node

Returns

0 if node was inserted successfully, -1 if it was not inserted because of a key collision

Definition at line 220 of file avl.c.

{
  struct avl_node *node, *next, *last;
  int diff;
 
  new->parent = NULL;
 
  new->left = NULL;
  new->right = NULL;
 
  new->balance = 0;
  new->leader = true;
 
  if (tree->root == NULL) {
    list_add(&new->list, &tree->list_head);
    tree->root = new;
    tree->count = 1;
    return 0;
  }
 
  node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
 
  last = node;
 
  while (!list_is_last(&last->list, &tree->list_head)) {
    next = avl_next(last);
    if (next->leader) {
      break;
    }
    last = next;
  }
 
  diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
 
  if (diff == 0) {
    if (!tree->allow_dups)
      return -1;
 
    new->leader = 0;
 
    avl_insert_after(tree, last, new);
    return 0;
  }
 
  if (node->balance == 1) {
    avl_insert_before(tree, node, new);
 
    node->balance = 0;
    new->parent = node;
    node->left = new;
    return 0;
  }
 
  if (node->balance == -1) {
    avl_insert_after(tree, last, new);
 
    node->balance = 0;
    new->parent = node;
    node->right = new;
    return 0;
  }
 
  if (diff < 0) {
    avl_insert_before(tree, node, new);
 
    node->balance = -1;
    new->parent = node;
    node->left = new;
    post_insert(tree, node);
    return 0;
  }
 
  avl_insert_after(tree, last, new);
 
  node->balance = 1;
  new->parent = node;
  node->right = new;
  post_insert(tree, node);
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_insert_after()

static void avl_insert_after ( struct avl_tree *  tree, struct avl_node *  pos_node, struct avl_node *  node  )

static

Definition at line 498 of file avl.c.

{
  list_add(&node->list, &pos_node->list);
  tree->count++;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_insert_before()

static void avl_insert_before ( struct avl_tree *  tree, struct avl_node *  pos_node, struct avl_node *  node  )

static

Definition at line 491 of file avl.c.

{
  list_add_tail(&node->list, &pos_node->list);
  tree->count++;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_local_min()

static struct avl_node* avl_local_min ( struct avl_node *  node )

static

Definition at line 574 of file avl.c.

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

Here is the caller graph for this function:

avl_max()

static int avl_max ( int  x, int  y  )

inlinestatic

internal type save inline function to calculate the maximum of to integers without macro implementation.

Parameters

x	first parameter of maximum function
y	second parameter of maximum function

Returns

largest integer of both parameters

Definition at line 59 of file avl.c.

                                        {
  return x > y ? x : y;
}

Here is the caller graph for this function:

avl_min()

static int avl_min ( int  x, int  y  )

inlinestatic

internal type save inline function to calculate the minimum of to integers without macro implementation.

Parameters

x	first parameter of minimum function
y	second parameter of minimum function

Returns

smallest integer of both parameters

Definition at line 71 of file avl.c.

                                        {
  return x < y ? x : y;
}

Here is the caller graph for this function:

avl_next()

static struct avl_node* avl_next ( struct avl_node *  node )

inlinestatic

Definition at line 102 of file avl.c.

{
    return list_entry(node->list.next, struct avl_node, list);
}

Here is the caller graph for this function:

avl_post_delete()

static void avl_post_delete ( struct avl_tree *  tree, struct avl_node *  node  )

static

Definition at line 512 of file avl.c.

{
  struct avl_node *parent;
 
  if ((parent = node->parent) == NULL)
    return;
 
  if (node == parent->left) {
    parent->balance++;
 
    if (parent->balance == 0) {
      avl_post_delete(tree, parent);
      return;
    }
 
    if (parent->balance == 1)
      return;
 
    if (parent->right->balance == 0) {
      avl_rotate_left(tree, parent);
      return;
    }
 
    if (parent->right->balance == 1) {
      avl_rotate_left(tree, parent);
      avl_post_delete(tree, parent->parent);
      return;
    }
 
    avl_rotate_right(tree, parent->right);
    avl_rotate_left(tree, parent);
    avl_post_delete(tree, parent->parent);
    return;
  }
 
  parent->balance--;
 
  if (parent->balance == 0) {
    avl_post_delete(tree, parent);
    return;
  }
 
  if (parent->balance == -1)
    return;
 
  if (parent->left->balance == 0) {
    avl_rotate_right(tree, parent);
    return;
  }
 
  if (parent->left->balance == -1) {
    avl_rotate_right(tree, parent);
    avl_post_delete(tree, parent->parent);
    return;
  }
 
  avl_rotate_left(tree, parent->left);
  avl_rotate_right(tree, parent);
  avl_post_delete(tree, parent->parent);
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_remove()

static void avl_remove ( struct avl_tree *  tree, struct avl_node *  node  )

static

Definition at line 505 of file avl.c.

{
  list_del(&node->list);
  tree->count--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_rotate_left()

static void avl_rotate_left ( struct avl_tree *  tree, struct avl_node *  node  )

static

Definition at line 411 of file avl.c.

{
  struct avl_node *right, *parent;
 
  right = node->right;
  parent = node->parent;
 
  right->parent = parent;
  node->parent = right;
 
  if (parent == NULL)
    tree->root = right;
 
  else {
    if (parent->left == node)
      parent->left = right;
 
    else
      parent->right = right;
  }
 
  node->right = right->left;
  right->left = node;
 
  if (node->right != NULL)
    node->right->parent = node;
 
  node->balance -= 1 + avl_max(right->balance, 0);
  right->balance -= 1 - avl_min(node->balance, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

avl_rotate_right()

static void avl_rotate_right ( struct avl_tree *  tree, struct avl_node *  node  )

static

Definition at line 379 of file avl.c.

{
  struct avl_node *left, *parent;
 
  left = node->left;
  parent = node->parent;
 
  left->parent = parent;
  node->parent = left;
 
  if (parent == NULL)
    tree->root = left;
 
  else {
    if (parent->left == node)
      parent->left = left;
 
    else
      parent->right = left;
  }
 
  node->left = left->right;
  left->right = node;
 
  if (node->left != NULL)
    node->left->parent = node;
 
  node->balance += 1 - avl_min(left->balance, 0);
  left->balance += 1 + avl_max(node->balance, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

post_insert()

static void post_insert ( struct avl_tree *  tree, struct avl_node *  node  )

static

Definition at line 443 of file avl.c.

{
  struct avl_node *parent = node->parent;
 
  if (parent == NULL)
    return;
 
  if (node == parent->left) {
    parent->balance--;
 
    if (parent->balance == 0)
      return;
 
    if (parent->balance == -1) {
      post_insert(tree, parent);
      return;
    }
 
    if (node->balance == -1) {
      avl_rotate_right(tree, parent);
      return;
    }
 
    avl_rotate_left(tree, node);
    avl_rotate_right(tree, node->parent->parent);
    return;
  }
 
  parent->balance++;
 
  if (parent->balance == 0)
    return;
 
  if (parent->balance == 1) {
    post_insert(tree, parent);
    return;
  }
 
  if (node->balance == 1) {
    avl_rotate_left(tree, parent);
    return;
  }
 
  avl_rotate_right(tree, node);
  avl_rotate_left(tree, node->parent->parent);
}

Here is the call graph for this function:

Here is the caller graph for this function: