#ifndef _SYS_RBTREE_H_
#define _SYS_RBTREE_H_
#include <Availability.h>
#include <sys/types.h>
#include <stdbool.h>
#include <inttypes.h>
#include <sys/queue.h>
__BEGIN_DECLS
#define RB_DIR_LEFT 0
#define RB_DIR_RIGHT 1
#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
#define RB_TREE_FOREACH(N, T) \
for ((N) = RB_TREE_MIN(T); (N); \
(N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
#define RB_TREE_FOREACH_SAFE(N, T, TVAR) \
for ((N) = RB_TREE_MIN(T); (N) && ((TVAR) = rb_tree_iterate((T), (N), RB_DIR_RIGHT)); \
(N) = (TVAR))
#define RB_TREE_FOREACH_REVERSE(N, T) \
for ((N) = RB_TREE_MAX(T); (N); \
(N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
#define RB_TREE_FOREACH_REVERSE_SAFE(N, T, TVAR) \
for ((N) = RB_TREE_MAX(T); (N) && ((TVAR) = rb_tree_iterate((T), (N), RB_DIR_LEFT)); \
(N) = (TVAR))
typedef signed int (*rbto_compare_nodes_fn)(void *, const void *, const void *);
typedef signed int (*rbto_compare_key_fn)(void *, const void *, const void *);
typedef struct {
rbto_compare_nodes_fn rbto_compare_nodes;
rbto_compare_key_fn rbto_compare_key;
size_t rbto_node_offset;
void *rbto_context;
} rb_tree_ops_t;
#ifdef _RBTREE_NO_OPAQUE_STRUCTS_
typedef struct rb_node rb_node_t;
typedef struct rb_tree rb_tree_t;
#else
typedef struct rb_node { void * opaque[3]; } rb_node_t;
typedef struct rb_tree { void *opaque[8]; } rb_tree_t;
#endif
#define _rb_availability __OSX_AVAILABLE_STARTING(__MAC_10_9,__IPHONE_7_0);
void rb_tree_init(rb_tree_t *, const rb_tree_ops_t *) _rb_availability;
void * rb_tree_insert_node(rb_tree_t *, void *) _rb_availability;
void * rb_tree_find_node(rb_tree_t *, const void *) _rb_availability;
void * rb_tree_find_node_geq(rb_tree_t *, const void *) _rb_availability;
void * rb_tree_find_node_leq(rb_tree_t *, const void *) _rb_availability;
void rb_tree_remove_node(rb_tree_t *, void *) _rb_availability;
void * rb_tree_iterate(rb_tree_t *, void *, const unsigned int) _rb_availability;
size_t rb_tree_count(rb_tree_t *) _rb_availability;
#undef _rb_availability
__END_DECLS
#endif