Splay tree

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

Structs

splay_node

struct splay_node (3 fields) source

§ struct splay_node *left

§ struct splay_node *right

§ struct splay_node *parent

splay_node_ops

struct splay_node_ops (2 fields) source

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

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

splay_tree

struct splay_tree (2 fields) source

§ struct splay_node *root

§ const struct splay_node_ops *ops

Functions

splay_init_node

void splay_init_node(struct splay_node *n)

source

splay_tree_empty

bool splay_tree_empty(const struct splay_tree *tree)

source

splay_tree_init

void splay_tree_init(
    struct splay_tree *tree,
    const struct splay_node_ops *ops
)

source

splay

void splay(struct splay_tree *tree, struct splay_node *node)

source

splay_insert

void splay_insert(struct splay_tree *tree, struct splay_node *node)

source

splay_remove

void splay_remove(struct splay_tree *tree, struct splay_node *node)

source

splay_find

struct splay_node * splay_find(
    struct splay_tree *tree,
    const void *key
)

source

splay_first

struct splay_node * splay_first(const struct splay_tree *tree)

source

splay_last

struct splay_node * splay_last(const struct splay_tree *tree)

source

splay_next

struct splay_node * splay_next(const struct splay_node *node)

source

splay_prev

struct splay_node * splay_prev(const struct splay_node *node)

source

Macros

SPLAY_NODE_INIT

#define SPLAY_NODE_INIT

source

Expansion

#define SPLAY_NODE_INIT \
    (struct splay_node) { \
        .left = NULL, .right = NULL, .parent = NULL \
    }

splay_entry

#define splay_entry(ptr, type, member)

source

Expansion

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

splay_for_each

#define splay_for_each(pos, tree)

source

Expansion

#define splay_for_each(pos, tree) \
    for ((pos) = splay_first(tree); (pos); (pos) = splay_next(pos))

splay_for_each_safe

#define splay_for_each_safe(pos, n, tree)

source

Expansion

#define splay_for_each_safe(pos, n, tree) \
    for ((pos) = splay_first(tree), (n) = (pos) ? splay_next(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? splay_next(pos) : NULL)

splay_for_each_entry

#define splay_for_each_entry(pos, tree, member)

source

Expansion

#define splay_for_each_entry(pos, tree, member) \
    for (typeof(splay_first(tree)) __n = splay_first(tree); \
         __n != NULL && \
         (((pos) = splay_entry(__n, typeof(*(pos)), member)), true); \
         __n = splay_next(__n))

splay_for_each_entry_safe

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

source

Expansion

#define splay_for_each_entry_safe(pos, tmp, tree, member) \
    for (typeof(splay_first(tree)) __n = splay_first(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = splay_entry(__n, typeof(*(pos)), member)), \
          (__nx = splay_next(__n)), \
          ((tmp) = __nx ? splay_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

splay_for_each_reverse

#define splay_for_each_reverse(pos, tree)

source

Expansion

#define splay_for_each_reverse(pos, tree) \
    for ((pos) = splay_last(tree); (pos); (pos) = splay_prev(pos))

splay_for_each_safe_reverse

#define splay_for_each_safe_reverse(pos, n, tree)

source

Expansion

#define splay_for_each_safe_reverse(pos, n, tree) \
    for ((pos) = splay_last(tree), (n) = (pos) ? splay_prev(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? splay_prev(pos) : NULL)

splay_for_each_entry_reverse

#define splay_for_each_entry_reverse(pos, tree, member)

source

Expansion

#define splay_for_each_entry_reverse(pos, tree, member) \
    for (typeof(splay_last(tree)) __n = splay_last(tree); \
         __n != NULL && \
         (((pos) = splay_entry(__n, typeof(*(pos)), member)), true); \
         __n = splay_prev(__n))

splay_for_each_entry_safe_reverse

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

source

Expansion

#define splay_for_each_entry_safe_reverse(pos, tmp, tree, member) \
    for (typeof(splay_last(tree)) __n = splay_last(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = splay_entry(__n, typeof(*(pos)), member)), \
          (__nx = splay_prev(__n)), \
          ((tmp) = __nx ? splay_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)