Treap (Randomized Binary Search Tree)

include/structures/treap.h View source View on GitHub

Structs

treap_node

struct treap_node (4 fields) source

§ uint32_t priority

§ struct treap_node *left

§ struct treap_node *right

§ struct treap_node *parent

treap_node_ops

struct treap_node_ops (2 fields) source

§ int (*cmp)(const struct treap_node *a, const struct treap_node *b)

§ int (*cmp_key)(const struct treap_node *node, const void *key)

treap_tree

struct treap_tree (2 fields) source

§ struct treap_node *root

§ const struct treap_node_ops *ops

Functions

treap_init_node

void treap_init_node(struct treap_node *n, uint32_t priority)

source

treap_tree_empty

bool treap_tree_empty(const struct treap_tree *tree)

source

treap_tree_init

void treap_tree_init(
    struct treap_tree *tree,
    const struct treap_node_ops *ops
)

source

treap_insert

void treap_insert(struct treap_tree *tree, struct treap_node *node)

source

treap_remove

void treap_remove(struct treap_tree *tree, struct treap_node *node)

source

treap_find

struct treap_node * treap_find(
    const struct treap_tree *tree,
    const void *key
)

source

treap_first

struct treap_node * treap_first(const struct treap_tree *tree)

source

treap_last

struct treap_node * treap_last(const struct treap_tree *tree)

source

treap_next

struct treap_node * treap_next(const struct treap_node *node)

source

treap_prev

struct treap_node * treap_prev(const struct treap_node *node)

source

Macros

TREAP_NODE_INIT

#define TREAP_NODE_INIT(prio)

source

Expansion

#define TREAP_NODE_INIT(prio) \
    (struct treap_node) { \
        .priority = (prio), .left = NULL, .right = NULL, .parent = NULL \
    }

treap_entry

#define treap_entry(ptr, type, member)

source

Expansion

#define treap_entry(ptr, type, member) container_of(ptr, type, member)

treap_for_each

#define treap_for_each(pos, tree)

source

Expansion

#define treap_for_each(pos, tree) \
    for ((pos) = treap_first(tree); (pos); (pos) = treap_next(pos))

treap_for_each_safe

#define treap_for_each_safe(pos, n, tree)

source

Expansion

#define treap_for_each_safe(pos, n, tree) \
    for ((pos) = treap_first(tree), (n) = (pos) ? treap_next(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? treap_next(pos) : NULL)

treap_for_each_entry

#define treap_for_each_entry(pos, tree, member)

source

Expansion

#define treap_for_each_entry(pos, tree, member) \
    for (typeof(treap_first(tree)) __n = treap_first(tree); \
         __n != NULL && \
         (((pos) = treap_entry(__n, typeof(*(pos)), member)), true); \
         __n = treap_next(__n))

treap_for_each_entry_safe

#define treap_for_each_entry_safe(pos, tmp, tree, member)

source

Expansion

#define treap_for_each_entry_safe(pos, tmp, tree, member) \
    for (typeof(treap_first(tree)) __n = treap_first(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = treap_entry(__n, typeof(*(pos)), member)), \
          (__nx = treap_next(__n)), \
          ((tmp) = __nx ? treap_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

treap_for_each_reverse

#define treap_for_each_reverse(pos, tree)

source

Expansion

#define treap_for_each_reverse(pos, tree) \
    for ((pos) = treap_last(tree); (pos); (pos) = treap_prev(pos))

treap_for_each_safe_reverse

#define treap_for_each_safe_reverse(pos, n, tree)

source

Expansion

#define treap_for_each_safe_reverse(pos, n, tree) \
    for ((pos) = treap_last(tree), (n) = (pos) ? treap_prev(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? treap_prev(pos) : NULL)

treap_for_each_entry_reverse

#define treap_for_each_entry_reverse(pos, tree, member)

source

Expansion

#define treap_for_each_entry_reverse(pos, tree, member) \
    for (typeof(treap_last(tree)) __n = treap_last(tree); \
         __n != NULL && \
         (((pos) = treap_entry(__n, typeof(*(pos)), member)), true); \
         __n = treap_prev(__n))

treap_for_each_entry_safe_reverse

#define treap_for_each_entry_safe_reverse(pos, tmp, tree, member)

source

Expansion

#define treap_for_each_entry_safe_reverse(pos, tmp, tree, member) \
    for (typeof(treap_last(tree)) __n = treap_last(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = treap_entry(__n, typeof(*(pos)), member)), \
          (__nx = treap_prev(__n)), \
          ((tmp) = __nx ? treap_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)