1
0
mirror of https://gitlab.xiph.org/xiph/icecast-common.git synced 2024-06-09 06:10:42 +00:00
icecast-common/avl/avl.h
2018-10-12 11:27:17 +00:00

179 lines
4.6 KiB
C

/*
* Copyright (C) 1995 Sam Rushing <rushing@nightmare.com>,
* Copyright (C) 2012-2018 Philipp "ph3-der-loewe" Schafft <lion@lion.leolix.org>
*/
/* $Id: avl.h,v 1.7 2003/07/07 01:10:14 brendan Exp $ */
#ifndef _LIBIGLOO__AVL_H_
#define _LIBIGLOO__AVL_H_
#ifdef __cplusplus
extern "C" {
#endif
#define AVL_KEY_PRINTER_BUFLEN (256)
#ifndef NO_THREAD
#include "thread/thread.h"
#else
#define thread_rwlock_create(x) do{}while(0)
#define igloo_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)
#endif
typedef struct igloo_avl_node_tag {
void * key;
struct igloo_avl_node_tag * left;
struct igloo_avl_node_tag * right;
struct igloo_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 int rank_and_balance;
#if !defined(NO_THREAD) && defined(HAVE_AVL_NODE_LOCK)
igloo_rwlock_t rwlock;
#endif
} igloo_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 igloo__avl_tree;
typedef int (*igloo_avl_key_compare_fun_type) (void * compare_arg, void * a, void * b);
typedef int (*igloo_avl_iter_fun_type) (void * key, void * iter_arg);
typedef int (*igloo_avl_iter_index_fun_type) (unsigned long index, void * key, void * iter_arg);
typedef int (*igloo_avl_free_key_fun_type) (void * key);
typedef int (*igloo_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 igloo__avl_tree {
igloo_avl_node * root;
unsigned int height;
unsigned int length;
igloo_avl_key_compare_fun_type compare_fun;
void * compare_arg;
#ifndef NO_THREAD
igloo_rwlock_t rwlock;
#endif
} igloo_avl_tree;
igloo_avl_tree * igloo_avl_tree_new (igloo_avl_key_compare_fun_type compare_fun, void * compare_arg);
igloo_avl_node * igloo_avl_node_new (void * key, igloo_avl_node * parent);
void igloo_avl_tree_free (
igloo_avl_tree * tree,
igloo_avl_free_key_fun_type free_key_fun
);
int igloo_avl_insert (
igloo_avl_tree * ob,
void * key
);
int igloo_avl_delete (
igloo_avl_tree * tree,
void * key,
igloo_avl_free_key_fun_type free_key_fun
);
int igloo_avl_get_by_index (
igloo_avl_tree * tree,
unsigned long index,
void ** value_address
);
int igloo_avl_get_by_key (
igloo_avl_tree * tree,
void * key,
void ** value_address
);
int igloo_avl_iterate_inorder (
igloo_avl_tree * tree,
igloo_avl_iter_fun_type iter_fun,
void * iter_arg
);
int igloo_avl_iterate_index_range (
igloo_avl_tree * tree,
igloo_avl_iter_index_fun_type iter_fun,
unsigned long low,
unsigned long high,
void * iter_arg
);
int igloo_avl_get_span_by_key (
igloo_avl_tree * tree,
void * key,
unsigned long * low,
unsigned long * high
);
int igloo_avl_get_span_by_two_keys (
igloo_avl_tree * tree,
void * key_a,
void * key_b,
unsigned long * low,
unsigned long * high
);
int igloo_avl_verify (igloo_avl_tree * tree);
void igloo_avl_print_tree (
igloo_avl_tree * tree,
igloo_avl_key_printer_fun_type key_printer
);
igloo_avl_node *igloo_avl_get_first(igloo_avl_tree *tree);
igloo_avl_node *igloo_avl_get_prev(igloo_avl_node * node);
igloo_avl_node *igloo_avl_get_next(igloo_avl_node * node);
/* These two are from David Ascher <david_ascher@brown.edu> */
int igloo_avl_get_item_by_key_most (
igloo_avl_tree * tree,
void * key,
void ** value_address
);
int igloo_avl_get_item_by_key_least (
igloo_avl_tree * tree,
void * key,
void ** value_address
);
/* optional locking stuff */
void igloo_avl_tree_rlock(igloo_avl_tree *tree);
void igloo_avl_tree_wlock(igloo_avl_tree *tree);
void igloo_avl_tree_unlock(igloo_avl_tree *tree);
void avl_node_rlock(igloo_avl_node *node);
void avl_node_wlock(igloo_avl_node *node);
void avl_node_unlock(igloo_avl_node *node);
#ifdef __cplusplus
}
#endif
#endif /* __AVL_H */