avl.h 3.99 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.6 2003/03/15 02:10:18 msmith 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
#ifndef NO_THREAD
15
#include <thread/thread.h>
16
#else
17 18 19 20 21
#define thread_rwlock_create(x) do{}while(0)
#define thread_rwlock_destroy(x) do{}while(0)
#define thread_rwlock_rlock(x) do{}while(0)
#define thread_rwlock_wlock(x) do{}while(0)
#define thread_rwlock_unlock(x) do{}while(0)
22
#endif
Michael Smith's avatar
Michael Smith committed
23

Jack Moffitt's avatar
Jack Moffitt committed
24
typedef struct avl_node_tag {
25 26 27 28
  void *        key;
  struct avl_node_tag *    left;
  struct avl_node_tag *    right;  
  struct avl_node_tag *    parent;
Jack Moffitt's avatar
Jack Moffitt committed
29 30 31 32 33
  /*
   * 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>
   */
34
  unsigned long        rank_and_balance;
35
#ifndef NO_THREAD
Jack Moffitt's avatar
Jack Moffitt committed
36
  rwlock_t rwlock;
37
#endif
Jack Moffitt's avatar
Jack Moffitt committed
38 39
} avl_node;

40
#define AVL_GET_BALANCE(n)    ((int)(((n)->rank_and_balance & 3) - 1))
Jack Moffitt's avatar
Jack Moffitt committed
41

42
#define AVL_GET_RANK(n)    (((n)->rank_and_balance >> 2))
Jack Moffitt's avatar
Jack Moffitt committed
43 44 45 46 47 48 49 50 51 52 53

#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;

54 55 56 57 58
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 *);
Jack Moffitt's avatar
Jack Moffitt committed
59 60 61 62 63 64 65

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

typedef struct _avl_tree {
66 67 68 69 70
  avl_node *            root;
  unsigned long            height;
  unsigned long            length;
  avl_key_compare_fun_type    compare_fun;
  void *             compare_arg;
71
#ifndef NO_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
} 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 (
80 81
  avl_tree *        tree,
  avl_free_key_fun_type    free_key_fun
Jack Moffitt's avatar
Jack Moffitt committed
82 83 84
  );

int avl_insert (
85 86
  avl_tree *        ob,
  void *        key
Jack Moffitt's avatar
Jack Moffitt committed
87 88 89
  );

int avl_delete (
90 91 92
  avl_tree *        tree,
  void *        key,
  avl_free_key_fun_type    free_key_fun
Jack Moffitt's avatar
Jack Moffitt committed
93 94 95
  );

int avl_get_by_index (
96 97 98
  avl_tree *        tree,
  unsigned long        index,
  void **        value_address
Jack Moffitt's avatar
Jack Moffitt committed
99 100 101
  );

int avl_get_by_key (
102 103 104
  avl_tree *        tree,
  void *        key,
  void **        value_address
Jack Moffitt's avatar
Jack Moffitt committed
105 106 107
  );

int avl_iterate_inorder (
108 109 110
  avl_tree *        tree,
  avl_iter_fun_type    iter_fun,
  void *        iter_arg
Jack Moffitt's avatar
Jack Moffitt committed
111 112 113
  );

int avl_iterate_index_range (
114
  avl_tree *        tree,
Jack Moffitt's avatar
Jack Moffitt committed
115
  avl_iter_index_fun_type iter_fun,
116 117 118
  unsigned long        low,
  unsigned long        high,
  void *        iter_arg
Jack Moffitt's avatar
Jack Moffitt committed
119 120 121
  );

int avl_get_span_by_key (
122 123 124 125
  avl_tree *        tree,
  void *        key,
  unsigned long *    low,
  unsigned long *    high
Jack Moffitt's avatar
Jack Moffitt committed
126 127 128
  );

int avl_get_span_by_two_keys (
129 130 131 132 133
  avl_tree *        tree,
  void *        key_a,
  void *        key_b,
  unsigned long *    low,
  unsigned long *    high
Jack Moffitt's avatar
Jack Moffitt committed
134 135 136 137 138
  );

int avl_verify (avl_tree * tree);

void avl_print_tree (
139
  avl_tree *        tree,
Jack Moffitt's avatar
Jack Moffitt committed
140 141 142 143 144 145 146 147 148 149 150 151
  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 (
152 153 154
  avl_tree *        tree,
  void *        key,
  void **        value_address
Jack Moffitt's avatar
Jack Moffitt committed
155 156 157
  );

int avl_get_item_by_key_least (
158 159 160
  avl_tree *        tree,
  void *        key,
  void **        value_address
Jack Moffitt's avatar
Jack Moffitt committed
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
  );

/* 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 */