geany  1.38
About: Geany is a text editor (using GTK2) with basic features of an integrated development environment (syntax highlighting, code folding, symbol name auto-completion, ...). F: office T: editor programming GTK+ IDE
  Fossies Dox: geany-1.38.tar.bz2  ("unofficial" and yet experimental doxygen-generated source code documentation)  
Classes | Macros | Typedefs | Functions
rbtree.h File Reference
#include "general.h"
#include "inline.h"
#include "gcc-attr.h"
#include <stdint.h>
Include dependency graph for rbtree.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  rb_node
 
struct  rb_root
 

Macros

#define container_of(ptr, type, member)    ((type *)( (char *)ptr - offsetof(type,member)))
 
#define offsetof(TYPE, MEMBER)   ((size_t) &((TYPE *)0)->MEMBER)
 
#define NULL   ((void *)0)
 
#define RB_RED   0
 
#define RB_BLACK   1
 
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
 
#define rb_color(r)   ((r)->rb_parent_color & 1)
 
#define rb_is_red(r)   (!rb_color(r))
 
#define rb_is_black(r)   rb_color(r)
 
#define rb_set_red(r)   do { (r)->rb_parent_color &= ~1; } while (0)
 
#define rb_set_black(r)   do { (r)->rb_parent_color |= 1; } while (0)
 
#define RB_ROOT   (struct rb_root) { NULL, }
 
#define rb_entry(ptr, type, member)   container_of(ptr, type, member)
 
#define RB_EMPTY_ROOT(root)   ((root)->rb_node == NULL)
 
#define RB_EMPTY_NODE(node)   (rb_parent(node) == node)
 
#define RB_CLEAR_NODE(node)   (rb_set_parent(node, node))
 

Typedefs

typedef void(* rb_augment_f) (struct rb_node *node, void *data)
 

Functions

static void rb_set_parent (struct rb_node *rb, struct rb_node *p)
 
static void rb_set_color (struct rb_node *rb, int color)
 
static void rb_init_node (struct rb_node *rb)
 
void rb_insert_color (struct rb_node *, struct rb_root *)
 
void rb_erase (struct rb_node *, struct rb_root *)
 
void rb_augment_insert (struct rb_node *node, rb_augment_f func, void *data)
 
struct rb_node * rb_augment_erase_begin (struct rb_node *node)
 
void rb_augment_erase_end (struct rb_node *node, rb_augment_f func, void *data)
 
struct rb_node * rb_next (const struct rb_node *)
 
struct rb_node * rb_prev (const struct rb_node *)
 
struct rb_node * rb_first (const struct rb_root *)
 
struct rb_node * rb_last (const struct rb_root *)
 
void rb_replace_node (struct rb_node *victim, struct rb_node *new, struct rb_root *root)
 
static void rb_link_node (struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
 

Macro Definition Documentation

◆ container_of

#define container_of (   ptr,
  type,
  member 
)     ((type *)( (char *)ptr - offsetof(type,member)))

Definition at line 134 of file rbtree.h.

◆ NULL

#define NULL   ((void *)0)

Definition at line 150 of file rbtree.h.

◆ offsetof

#define offsetof (   TYPE,
  MEMBER 
)    ((size_t) &((TYPE *)0)->MEMBER)

Definition at line 143 of file rbtree.h.

◆ RB_BLACK

#define RB_BLACK   1

Definition at line 157 of file rbtree.h.

◆ RB_CLEAR_NODE

#define RB_CLEAR_NODE (   node)    (rb_set_parent(node, node))

Definition at line 190 of file rbtree.h.

◆ rb_color

#define rb_color (   r)    ((r)->rb_parent_color & 1)

Definition at line 170 of file rbtree.h.

◆ RB_EMPTY_NODE

#define RB_EMPTY_NODE (   node)    (rb_parent(node) == node)

Definition at line 189 of file rbtree.h.

◆ RB_EMPTY_ROOT

#define RB_EMPTY_ROOT (   root)    ((root)->rb_node == NULL)

Definition at line 188 of file rbtree.h.

◆ rb_entry

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

Definition at line 186 of file rbtree.h.

◆ rb_is_black

#define rb_is_black (   r)    rb_color(r)

Definition at line 172 of file rbtree.h.

◆ rb_is_red

#define rb_is_red (   r)    (!rb_color(r))

Definition at line 171 of file rbtree.h.

◆ rb_parent

#define rb_parent (   r)    ((struct rb_node *)((r)->rb_parent_color & ~3))

Definition at line 169 of file rbtree.h.

◆ RB_RED

#define RB_RED   0

Definition at line 156 of file rbtree.h.

◆ RB_ROOT

#define RB_ROOT   (struct rb_root) { NULL, }

Definition at line 185 of file rbtree.h.

◆ rb_set_black

#define rb_set_black (   r)    do { (r)->rb_parent_color |= 1; } while (0)

Definition at line 174 of file rbtree.h.

◆ rb_set_red

#define rb_set_red (   r)    do { (r)->rb_parent_color &= ~1; } while (0)

Definition at line 173 of file rbtree.h.

Typedef Documentation

◆ rb_augment_f

typedef void(* rb_augment_f) (struct rb_node *node, void *data)

Definition at line 203 of file rbtree.h.

Function Documentation

◆ rb_augment_erase_begin()

struct rb_node * rb_augment_erase_begin ( struct rb_node *  node)

Definition at line 337 of file rbtree.c.

References rb_node::rb_left, rb_next(), rb_parent, and rb_node::rb_right.

◆ rb_augment_erase_end()

void rb_augment_erase_end ( struct rb_node *  node,
rb_augment_f  func,
void *  data 
)

Definition at line 362 of file rbtree.c.

References rb_augment_path().

◆ rb_augment_insert()

void rb_augment_insert ( struct rb_node *  node,
rb_augment_f  func,
void *  data 
)

Definition at line 323 of file rbtree.c.

References rb_augment_path(), rb_node::rb_left, and rb_node::rb_right.

◆ rb_erase()

void rb_erase ( struct rb_node *  node,
struct rb_root *  root 
)

Definition at line 233 of file rbtree.c.

References __rb_erase_color(), color, NULL, RB_BLACK, rb_color, rb_node::rb_left, rb_root::rb_node, rb_parent, rb_node::rb_parent_color, rb_node::rb_right, and rb_set_parent().

◆ rb_first()

struct rb_node * rb_first ( const struct rb_root *  root)

Definition at line 371 of file rbtree.c.

References NULL, rb_node::rb_left, and rb_root::rb_node.

◆ rb_init_node()

static void rb_init_node ( struct rb_node *  rb)
static

Definition at line 192 of file rbtree.h.

References NULL, RB_CLEAR_NODE, rb_node::rb_left, rb_node::rb_parent_color, and rb_node::rb_right.

◆ rb_insert_color()

void rb_insert_color ( struct rb_node *  node,
struct rb_root *  root 
)

Definition at line 88 of file rbtree.c.

References __rb_rotate_left(), __rb_rotate_right(), rb_is_red, rb_node::rb_left, rb_root::rb_node, rb_parent, rb_node::rb_right, rb_set_black, and rb_set_red.

Referenced by corkSymtabPut().

◆ rb_last()

struct rb_node * rb_last ( const struct rb_root *  root)

Definition at line 383 of file rbtree.c.

References NULL, rb_root::rb_node, and rb_node::rb_right.

Referenced by foreachEntriesInScope().

◆ rb_link_node()

static void rb_link_node ( struct rb_node *  node,
struct rb_node *  parent,
struct rb_node **  rb_link 
)
static

Definition at line 221 of file rbtree.h.

References NULL, rb_node::rb_left, rb_node::rb_parent_color, and rb_node::rb_right.

Referenced by corkSymtabPut().

◆ rb_next()

struct rb_node * rb_next ( const struct rb_node *  node)

Definition at line 395 of file rbtree.c.

References NULL, rb_node::rb_left, rb_parent, and rb_node::rb_right.

Referenced by foreachEntriesInScope(), and rb_augment_erase_begin().

◆ rb_prev()

struct rb_node * rb_prev ( const struct rb_node *  node)

Definition at line 423 of file rbtree.c.

References NULL, rb_node::rb_left, rb_parent, and rb_node::rb_right.

Referenced by foreachEntriesInScope().

◆ rb_replace_node()

void rb_replace_node ( struct rb_node *  victim,
struct rb_node *  new,
struct rb_root *  root 
)

Definition at line 447 of file rbtree.c.

References rb_node::rb_left, rb_root::rb_node, rb_parent, rb_node::rb_right, and rb_set_parent().

◆ rb_set_color()

static void rb_set_color ( struct rb_node *  rb,
int  color 
)
static

Definition at line 180 of file rbtree.h.

References color, and rb_node::rb_parent_color.

Referenced by __rb_erase_color().

◆ rb_set_parent()

static void rb_set_parent ( struct rb_node *  rb,
struct rb_node *  p 
)
static

Definition at line 176 of file rbtree.h.

References rb_node::rb_parent_color.

Referenced by __rb_rotate_left(), __rb_rotate_right(), rb_erase(), and rb_replace_node().