rbt.h File Reference

#include <libk/serial.h>
#include <str.h>
#include <type.h>

Go to the source code of this file.

Data Structures
struct	__rbt_type
struct	rbt_node

Macros
#define	RBT_TYPE   struct __rbt_type
#define	RBT_ID_NAME   id
#define	FIELD_ACCESS(data_ptr, field)

Typedefs
typedef struct rbt_node	rbt_node

Enumerations
enum	rbt_node_color { RBT_RED , RBT_BLACK }

Functions
static void	rbt_rotate_left (rbt_node **root, rbt_node *x, rbt_node *NIL)
static void	rbt_rotate_right (rbt_node **root, rbt_node *y, rbt_node *NIL)
static void	rbt_fix_insert (rbt_node **root, rbt_node *y, rbt_node *NIL)
static int	rbt_insert_node (rbt_node **root, rbt_node *z, struct __rbt_type *data, rbt_node *NIL)
static rbt_node *	rbt_search_node (rbt_node *root, uint64_t id, rbt_node *NIL)
static void	rbt_fix_delete (rbt_node **root, rbt_node *x, rbt_node *NIL)
static void	rbt_remove_node (rbt_node **root, rbt_node *z, rbt_node *NIL)

Macro Definition Documentation

FIELD_ACCESS

#define FIELD_ACCESS	(		data_ptr,
			field )

Value:

((data_ptr)->field)

Definition at line 17 of file rbt.h.

Referenced by rbt_insert_node(), and rbt_search_node().

RBT_ID_NAME

#define RBT_ID_NAME   id

Definition at line 13 of file rbt.h.

Referenced by rbt_insert_node(), and rbt_search_node().

RBT_TYPE

#define RBT_TYPE   struct __rbt_type

Definition at line 8 of file rbt.h.

Referenced by rbt_insert_node().

Typedef Documentation

rbt_node

typedef struct rbt_node rbt_node

Definition at line 25 of file rbt.h.

Enumeration Type Documentation

rbt_node_color

enum rbt_node_color

Enumerator
RBT_RED
RBT_BLACK

Definition at line 23 of file rbt.h.

Function Documentation

rbt_fix_delete()

static void rbt_fix_delete ( rbt_node ** root, rbt_node * x, rbt_node * NIL )

inlinestatic

Definition at line 178 of file rbt.h.

References rbt_node::color, rbt_node::left, NIL, RBT_BLACK, RBT_RED, rbt_rotate_left(), rbt_rotate_right(), rbt_node::right, root, and x.

Referenced by rbt_remove_node().

rbt_fix_insert()

static void rbt_fix_insert ( rbt_node ** root, rbt_node * y, rbt_node * NIL )

inlinestatic

Definition at line 77 of file rbt.h.

References NIL, RBT_BLACK, RBT_RED, rbt_rotate_left(), rbt_rotate_right(), root, x, and y.

Referenced by rbt_insert_node().

rbt_insert_node()

static int rbt_insert_node ( rbt_node ** root, rbt_node * z, struct __rbt_type * data, rbt_node * NIL )

inlinestatic

Definition at line 123 of file rbt.h.

References rbt_node::color, data, rbt_node::data, FIELD_ACCESS, rbt_node::left, memset(), NIL, parent, rbt_node::parent, RBT_BLACK, rbt_fix_insert(), RBT_ID_NAME, RBT_RED, RBT_TYPE, rbt_node::right, and root.

Referenced by __attribute__(), and vma_register().

rbt_remove_node()

static void rbt_remove_node ( rbt_node ** root, rbt_node * z, rbt_node * NIL )

inlinestatic

Definition at line 238 of file rbt.h.

References rbt_node::color, rbt_node::left, NIL, rbt_node::parent, RBT_BLACK, rbt_fix_delete(), rbt_node::right, root, x, and y.

Referenced by vma_unregister().

rbt_rotate_left()

static void rbt_rotate_left ( rbt_node ** root, rbt_node * x, rbt_node * NIL )

inlinestatic

Definition at line 35 of file rbt.h.

References NIL, root, x, and y.

Referenced by rbt_fix_delete(), and rbt_fix_insert().

rbt_rotate_right()

static void rbt_rotate_right ( rbt_node ** root, rbt_node * y, rbt_node * NIL )

inlinestatic

Definition at line 56 of file rbt.h.

References NIL, root, x, and y.

Referenced by rbt_fix_delete(), and rbt_fix_insert().

rbt_search_node()

static rbt_node * rbt_search_node ( rbt_node * root, uint64_t id, rbt_node * NIL )

inlinestatic

Definition at line 168 of file rbt.h.

References FIELD_ACCESS, NIL, RBT_ID_NAME, rbt_search_node(), and root.

Referenced by rbt_search_node(), vma_find(), and vma_unregister().