24 RCSID(
"$Id: a94d2f630d9dc8356150a9729c6dc6c686a9bedd $")
26 #include <freeradius-devel/util/rb.h>
27 #include <freeradius-devel/util/strerror.h>
33 # define RB_MAGIC (0x5ad09c42)
128 talloc_free_children(tree);
152 if (
unlikely(offset >= UINT16_MAX)) {
154 "Expected <= %u, got %zd", UINT16_MAX, offset);
163 .node_ctx = node_ctx,
164 .offset = offset < 0 ? 0 : (
uint16_t)offset,
167 .data_free = data_free,
231 if (
y->left !=
NIL)
y->left->parent = x;
259 if (
y->right !=
NIL)
y->right->parent = x;
288 if (
y->colour ==
RED) {
310 if (
y->colour ==
RED) {
351 #ifndef TALLOC_GET_TYPE_ABORT_NOOP
352 if (tree->
type) (void)_talloc_get_type_abort(
data, tree->
type, __location__);
366 if (existing) *existing =
current;
477 if (!z || z ==
NIL)
return;
485 while (
y->left !=
NIL)
y =
y->left;
489 if (
y->left !=
NIL) {
510 void *y_data =
y->data;
521 memcpy(
y, z,
sizeof(*
y));
524 if (
y->parent ==
NIL) {
527 if (
y->parent->left == z)
y->parent->left =
y;
528 if (
y->parent->right == z)
y->parent->right =
y;
530 if (
y->left->parent == z)
y->left->parent =
y;
531 if (
y->right->parent == z)
y->right->parent =
y;
558 if (result == 0)
return current;
603 if (found) *found = existing->
data;
607 if (found) *found = NULL;
611 if (found) *found = NULL;
651 void *old_data = node->
data;
674 if (old) *old = NULL;
678 if (old) *old = NULL;
698 if (!node)
return NULL;
702 node_data = node->
data;
723 node_data = node->
data;
742 if (!node)
return false;
784 if (x ==
NIL)
return NULL;
799 if (x ==
NIL)
return NULL;
822 if (x ==
NIL)
return NULL;
915 if (x ==
NIL)
return NULL;
965 if (
y->right !=
NIL &&
y->right != x) {
992 if (x ==
NIL)
return NULL;
1046 if (
y->right ==
NIL ||
y->right == x) {
1065 #define DEF_RB_FLATTEN_FUNC(_order) \
1066 int fr_rb_flatten_##_order(TALLOC_CTX *ctx, void **out[], fr_rb_tree_t *tree) \
1068 uint32_t num = fr_rb_num_elements(tree), i; \
1069 fr_rb_iter_##_order##_t iter; \
1070 void *item, **list; \
1071 if (unlikely(!(list = talloc_array(ctx, void *, num)))) return -1; \
1072 for (item = fr_rb_iter_init_##_order(&iter, tree), i = 0; \
1074 item = fr_rb_iter_next_##_order(&iter), i++) list[i] = item; \
#define UNCONST(_type, _ptr)
Remove const qualification from a pointer.
int8_t(* fr_cmp_t)(void const *a, void const *b)
void(* fr_free_t)(void *)
static rc_request_t * current
void * fr_rb_iter_init_preorder(fr_rb_iter_preorder_t *iter, fr_rb_tree_t *tree)
Initialise a pre-order iterator.
uint32_t fr_rb_num_elements(fr_rb_tree_t *tree)
Return how many nodes there are in a tree.
void * fr_rb_first(fr_rb_tree_t *tree)
static fr_rb_node_t sentinel
void * fr_rb_iter_init_postorder(fr_rb_iter_postorder_t *iter, fr_rb_tree_t *tree)
Initialise a post-order iterator.
int fr_rb_find_or_insert(void **found, fr_rb_tree_t *tree, void const *data)
Attempt to find current data in the tree, if it does not exist insert it.
void fr_rb_iter_delete_inorder(fr_rb_iter_inorder_t *iter)
Remove the current node from the tree.
#define DEF_RB_FLATTEN_FUNC(_order)
static fr_rb_node_t * find_node(fr_rb_tree_t const *tree, void const *data)
static int insert_node(fr_rb_node_t **existing, fr_rb_tree_t *tree, void *data))
Insert an element into the tree.
static void delete_fixup(fr_rb_tree_t *tree, fr_rb_node_t *x, fr_rb_node_t *parent)
Maintain RED-BLACK tree balance after deleting node x.
static void delete_internal(fr_rb_tree_t *tree, fr_rb_node_t *z, bool free_data)
Delete an element (z) from the tree.
int fr_rb_replace(void **old, fr_rb_tree_t *tree, void const *data)
Replace old data with new data, OR insert if there is no old.
void * fr_rb_iter_next_inorder(fr_rb_iter_inorder_t *iter)
Return the next node.
static fr_rb_node_t * _node_inline_alloc(fr_rb_tree_t const *tree, void *data)
Return the fr_rb_node_t that was allocated as part of the data structure.
static fr_rb_node_t * _node_heap_alloc(fr_rb_tree_t const *tree, UNUSED void *data)
Allocate a new fr_rb_node_t on the heap.
void * fr_rb_iter_next_preorder(fr_rb_iter_preorder_t *iter)
Return the next node.
static void free_walker(fr_rb_tree_t *tree, fr_rb_node_t *x)
Walks the tree to delete all nodes Does NOT re-balance it!
static void node_data_free(fr_rb_tree_t const *tree, fr_rb_node_t *node)
static int _tree_free(fr_rb_tree_t *tree)
Free the rbtree cleaning up any nodes.
void * fr_rb_remove(fr_rb_tree_t *tree, void const *data)
Remove an entry from the tree, without freeing the data.
bool fr_rb_delete_by_inline_node(fr_rb_tree_t *tree, fr_rb_node_t *node)
Remove node and free data (if a free function was specified)
int _fr_rb_init(fr_rb_tree_t *tree, TALLOC_CTX *node_ctx, ssize_t offset, char const *type, fr_cmp_t data_cmp, fr_free_t data_free)
Initialise a new RED-BLACK tree.
fr_rb_tree_t * _fr_rb_alloc(TALLOC_CTX *ctx, ssize_t offset, char const *type, fr_cmp_t data_cmp, fr_free_t data_free)
Alloc a new RED-BLACK tree.
void * fr_rb_remove_by_inline_node(fr_rb_tree_t *tree, fr_rb_node_t *node)
Remove an entry from the tree, using the node structure, without freeing the data.
bool fr_rb_insert(fr_rb_tree_t *tree, void const *data)
Insert data into a tree.
void * fr_rb_iter_next_postorder(fr_rb_iter_postorder_t *iter)
Return the next node.
void * fr_rb_last(fr_rb_tree_t *tree)
bool fr_rb_delete(fr_rb_tree_t *tree, void const *data)
Remove node and free data (if a free function was specified)
static void rotate_right(fr_rb_tree_t *tree, fr_rb_node_t *x)
Rotate Node x to right.
static void _node_heap_free(fr_rb_tree_t const *tree, fr_rb_node_t *node, bool free_data)
Clear the fr_rb_node_t that was allocated as part of the data structure.
static void _node_inline_free(fr_rb_tree_t const *tree, fr_rb_node_t *node, bool free_data)
Clear the fr_rb_node_t that was allocated as part of the data structure.
static void rotate_left(fr_rb_tree_t *tree, fr_rb_node_t *x)
Rotate Node x to left.
static void insert_fixup(fr_rb_tree_t *tree, fr_rb_node_t *x)
Maintain red-black tree balance after inserting node x.
void * fr_rb_iter_init_inorder(fr_rb_iter_inorder_t *iter, fr_rb_tree_t *tree)
Initialise an in-order iterator.
void * fr_rb_find(fr_rb_tree_t const *tree, void const *data)
Find an element in the tree, returning the data, not the node.
fr_rb_tree_t * tree
Tree being iterated over.
fr_rb_node_t * node
current node
fr_rb_node_t * parent
Parent.
struct fr_rb_node_s fr_rb_node_t
fr_rb_node_t * left
Left child.
bool being_freed
Disable frees if we're currently calling a free function.
struct fr_rb_tree_s fr_rb_tree_t
fr_rb_node_t * next
if non-NULL, next node cached by fr_rb_iter_delete()
fr_rb_node_t * node
current node
fr_cmp_t data_cmp
Callback to compare node data.
TALLOC_CTX * node_ctx
Talloc ctx to allocate nodes in.
fr_rb_node_t * right
Right child.
char const * type
Talloc type to check elements against.
static bool fr_rb_node_inline_in_tree(fr_rb_node_t const *node)
Check to see if an item is in a tree by examining its inline fr_rb_node_t.
void * data
data stored in node
uint32_t num_elements
How many elements are inside the tree.
fr_free_t data_free
Callback to free node data.
fr_rb_tree_t * tree
Tree being iterated over.
uint16_t offset
Where's the fr_rb_node_t is located in the structure being inserted.
rb_node_free_t node_free
Callback to free a node.
bool being_freed
Prevent double frees in talloc_destructor.
fr_rb_tree_t * tree
Tree being iterated over.
fr_rb_node_t * node
current nodeāset to NULL (not NIL) by fr_rb_iter_delete()
fr_rb_colour_t colour
Node colour (BLACK, RED)
rb_node_alloc_t node_alloc
Callback to allocate a new node.
fr_rb_node_t * root
Root of the rbtree.
Iterator structure for in-order traversal of an rbtree.
Iterator structure for post-order traversal of an rbtree.
Iterator structure for pre-order traversal of an rbtree.
The main red black tree structure.
static int8_t data_cmp(const void *one, const void *two)
fr_aka_sim_id_type_t type
#define fr_strerror_printf(_fmt,...)
Log to thread local error buffer.