avl.h 3.4 KB
Newer Older
Jack Moffitt's avatar
Jack Moffitt committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 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 71 72 73 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
/*
 * Copyright (C) 1995 by Sam Rushing <rushing@nightmare.com>
 */

/* $Id: avl.h,v 1.1 2001/09/10 02:28:03 jack Exp $ */

#ifndef __AVL_H
#define __AVL_H

#ifdef __cplusplus
extern "C" {
#endif

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;

  rwlock_t rwlock;
} 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;

  rwlock_t rwlock;
} 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 */