avl.h 3.65 KB
Newer Older
Jack Moffitt's avatar
Jack Moffitt committed
1 2 3 4
/*
 * Copyright (C) 1995 by Sam Rushing <rushing@nightmare.com>
 */

5
/* $Id: avl.h,v 1.3 2003/03/06 01:55:20 brendan Exp $ */
Jack Moffitt's avatar
Jack Moffitt committed
6 7 8 9 10 11 12 13

#ifndef __AVL_H
#define __AVL_H

#ifdef __cplusplus
extern "C" {
#endif

14
#ifdef USE_THREAD
Michael Smith's avatar
Michael Smith committed
15
#include "thread.h"
16 17 18 19 20 21 22
#else
#define thread_rwlock_create(x)
#define thread_rwlock_destroy(x)
#define thread_rwlock_rlock(x)
#define thread_rwlock_wlock(x)
#define thread_rwlock_unlock(x)
#endif
Michael Smith's avatar
Michael Smith committed
23

Jack Moffitt's avatar
Jack Moffitt committed
24 25 26 27 28 29 30 31 32 33 34
typedef struct avl_node_tag {
  void *		key;
  struct avl_node_tag *	left;
  struct avl_node_tag *	right;  
  struct avl_node_tag *	parent;
  /*
   * The lower 2 bits of <rank_and_balance> specify the balance
   * factor: 00==-1, 01==0, 10==+1.
   * The rest of the bits are used for <rank>
   */
  unsigned long		rank_and_balance;
35
#ifdef USE_THREAD
Jack Moffitt's avatar
Jack Moffitt committed
36
  rwlock_t rwlock;
37
#endif
Jack Moffitt's avatar
Jack Moffitt committed
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
} avl_node;

#define AVL_GET_BALANCE(n)	((int)(((n)->rank_and_balance & 3) - 1))

#define AVL_GET_RANK(n)	(((n)->rank_and_balance >> 2))

#define AVL_SET_BALANCE(n,b) \
  ((n)->rank_and_balance) = \
    (((n)->rank_and_balance & (~3)) | ((int)((b) + 1)))

#define AVL_SET_RANK(n,r) \
  ((n)->rank_and_balance) = \
    (((n)->rank_and_balance & 3) | (r << 2))

struct _avl_tree;

typedef int (*avl_key_compare_fun_type)	(void * compare_arg, void * a, void * b);
typedef int (*avl_iter_fun_type)	(void * key, void * iter_arg);
typedef int (*avl_iter_index_fun_type)	(unsigned long index, void * key, void * iter_arg);
typedef int (*avl_free_key_fun_type)	(void * key);
typedef int (*avl_key_printer_fun_type)	(char *, void *);

/*
 * <compare_fun> and <compare_arg> let us associate a particular compare
 * function with each tree, separately.
 */

typedef struct _avl_tree {
  avl_node *			root;
  unsigned long			height;
  unsigned long			length;
  avl_key_compare_fun_type	compare_fun;
  void * 			compare_arg;
71
#ifdef USE_THREAD
Jack Moffitt's avatar
Jack Moffitt committed
72
  rwlock_t rwlock;
73
#endif
Jack Moffitt's avatar
Jack Moffitt committed
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
} avl_tree;

avl_tree * avl_tree_new (avl_key_compare_fun_type compare_fun, void * compare_arg);
avl_node * avl_node_new (void * key, avl_node * parent);

void avl_tree_free (
  avl_tree *		tree,
  avl_free_key_fun_type	free_key_fun
  );

int avl_insert (
  avl_tree *		ob,
  void *		key
  );

int avl_delete (
  avl_tree *		tree,
  void *		key,
  avl_free_key_fun_type	free_key_fun
  );

int avl_get_by_index (
  avl_tree *		tree,
  unsigned long		index,
  void **		value_address
  );

int avl_get_by_key (
  avl_tree *		tree,
  void *		key,
  void **		value_address
  );

int avl_iterate_inorder (
  avl_tree *		tree,
  avl_iter_fun_type	iter_fun,
  void *		iter_arg
  );

int avl_iterate_index_range (
  avl_tree *		tree,
  avl_iter_index_fun_type iter_fun,
  unsigned long		low,
  unsigned long		high,
  void *		iter_arg
  );

int avl_get_span_by_key (
  avl_tree *		tree,
  void *		key,
  unsigned long *	low,
  unsigned long *	high
  );

int avl_get_span_by_two_keys (
  avl_tree *		tree,
  void *		key_a,
  void *		key_b,
  unsigned long *	low,
  unsigned long *	high
  );

int avl_verify (avl_tree * tree);

void avl_print_tree (
  avl_tree *		tree,
  avl_key_printer_fun_type key_printer
  );

avl_node *avl_get_first(avl_tree *tree);

avl_node *avl_get_prev(avl_node * node);

avl_node *avl_get_next(avl_node * node);

/* These two are from David Ascher <david_ascher@brown.edu> */

int avl_get_item_by_key_most (
  avl_tree *		tree,
  void *		key,
  void **		value_address
  );

int avl_get_item_by_key_least (
  avl_tree *		tree,
  void *		key,
  void **		value_address
  );

/* optional locking stuff */
void avl_tree_rlock(avl_tree *tree);
void avl_tree_wlock(avl_tree *tree);
void avl_tree_unlock(avl_tree *tree);
void avl_node_rlock(avl_node *node);
void avl_node_wlock(avl_node *node);
void avl_node_unlock(avl_node *node);

#ifdef __cplusplus
}
#endif

#endif /* __AVL_H */