Main Page | Class List | Directories | File List | Class Members | File Members
src

rbtree.h File Reference

#include "array.h"

Go to the source code of this file.

Classes

struct  rb_node_hdr

Defines

#define RB_RED   0x2000
#define RB_THREAD_PREV   0x4000
#define RB_THREAD_NEXT   0x8000
#define RB_FLAG_MASK   0xe000
#define keep_flags(node, code)
#define rb_prev(node)
#define rb_next(node)
#define rb_node_check(node)   ((struct rb_node_hdr *) (node))
#define PIKE_MERGE_DESTR_A   0x2000
#define PIKE_MERGE_DESTR_B   0x1000
#define DO_IF_RB_STATS(X)

Typedefs

typedef int rb_find_fn (void *key, struct rb_node_hdr *node)
typedef int rb_cmp_fn (struct rb_node_hdr *a, struct rb_node_hdr *b, void *extra)
typedef int rb_equal_fn (struct rb_node_hdr *a, struct rb_node_hdr *b, void *extra)
typedef rb_node_hdr * rb_copy_fn (struct rb_node_hdr *node, void *extra)
typedef void rb_free_fn (struct rb_node_hdr *node, void *extra)
typedef rb_node_hdr * rb_merge_copy_fn (struct rb_node_hdr *node, void *extra, enum rb_merge_trees tree)
typedef void rb_merge_free_fn (struct rb_node_hdr *node, void *extra, enum rb_merge_trees tree)

Enumerations

enum  rb_merge_trees { MERGE_TREE_A, MERGE_TREE_B, MERGE_TREE_RES }

Functions

PMOD_EXPORT struct rb_node_hdr * rb_first (struct rb_node_hdr *root)
PMOD_EXPORT struct rb_node_hdr * rb_last (struct rb_node_hdr *root)
PMOD_EXPORT struct rb_node_hdr * rb_link_prev (struct rb_node_hdr *node)
PMOD_EXPORT struct rb_node_hdr * rb_link_next (struct rb_node_hdr *node)
rb_node_hdr * rb_insert (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key, struct rb_node_hdr *new)
void rb_add (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key, struct rb_node_hdr *new)
void rb_add_after (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key, struct rb_node_hdr *new, struct rb_node_hdr *existing)
rb_node_hdr * rb_remove (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key)
void rb_remove_node (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key, struct rb_node_hdr *node)
rb_node_hdr * rb_remove_with_move (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key, size_t node_size, rb_free_fn *cleanup_fn, void *cleanup_fn_extra)
rb_node_hdr * rb_remove_node_with_move (struct rb_node_hdr **root, rb_find_fn *find_fn, void *key, struct rb_node_hdr *node, size_t node_size)
rb_node_hdr * rb_find_eq (struct rb_node_hdr *root, rb_find_fn *find_fn, void *key)
rb_node_hdr * rb_find_lt (struct rb_node_hdr *root, rb_find_fn *find_fn, void *key)
rb_node_hdr * rb_find_gt (struct rb_node_hdr *root, rb_find_fn *find_fn, void *key)
rb_node_hdr * rb_find_le (struct rb_node_hdr *root, rb_find_fn *find_fn, void *key)
rb_node_hdr * rb_find_ge (struct rb_node_hdr *root, rb_find_fn *find_fn, void *key)
rb_node_hdr * rb_get_nth (struct rb_node_hdr *root, size_t n)
size_t rb_sizeof (struct rb_node_hdr *root)
void rb_free (struct rb_node_hdr *root, rb_free_fn *free_node_fn, void *extra)
int rb_equal (struct rb_node_hdr *a, struct rb_node_hdr *b, rb_equal_fn *node_equal_fn, void *extra)
rb_node_hdr * rb_copy (struct rb_node_hdr *source, rb_copy_fn *copy_node_fn, void *extra)
rb_node_hdr * rb_make_list (struct rb_node_hdr *tree)
rb_node_hdr * rb_make_tree (struct rb_node_hdr *list, size_t length)
rb_node_hdr * rb_linear_merge (struct rb_node_hdr *a, struct rb_node_hdr *b, int operation, rb_cmp_fn *cmp_fn, void *cmp_fn_extra, rb_merge_copy_fn *copy_node_fn, void *copy_fn_extra, rb_merge_free_fn *free_node_fn, void *free_fn_extra, size_t *length)

Define Documentation

#define DO_IF_RB_STATS (  X   ) 
 

#define keep_flags (  node,
code   ) 
 

Value:

do {                                    \
    int kept_flags_ = (node)->flags;                                    \
    {code;}                                                             \
    (node)->flags =                                                     \
      ((node)->flags & ~RB_FLAG_MASK) | (kept_flags_ & RB_FLAG_MASK);   \
  } while (0)

#define PIKE_MERGE_DESTR_A   0x2000
 

#define PIKE_MERGE_DESTR_B   0x1000
 

#define RB_FLAG_MASK   0xe000
 

#define rb_next (  node   ) 
 

Value:

(DO_IF_RB_STATS (rb_num_sidesteps++ COMMA)                              \
   (node)->flags & RB_THREAD_NEXT ?                                     \
   DO_IF_RB_STATS (rb_num_sidestep_ops++ COMMA) (node)->next :          \
   rb_link_next (node))

#define rb_node_check (  node   )     ((struct rb_node_hdr *) (node))
 

#define rb_prev (  node   ) 
 

Value:

(DO_IF_RB_STATS (rb_num_sidesteps++ COMMA)                              \
   (node)->flags & RB_THREAD_PREV ?                                     \
   DO_IF_RB_STATS (rb_num_sidestep_ops++ COMMA) (node)->prev :          \
   rb_link_prev (node))

#define RB_RED   0x2000
 

#define RB_THREAD_NEXT   0x8000
 

#define RB_THREAD_PREV   0x4000
 

Typedef Documentation

typedef int rb_cmp_fn(struct rb_node_hdr *a, struct rb_node_hdr *b, void *extra)
 

typedef struct rb_node_hdr* rb_copy_fn(struct rb_node_hdr *node, void *extra)
 

typedef int rb_equal_fn(struct rb_node_hdr *a, struct rb_node_hdr *b, void *extra)
 

typedef int rb_find_fn(void *key, struct rb_node_hdr *node)
 

typedef void rb_free_fn(struct rb_node_hdr *node, void *extra)
 

typedef struct rb_node_hdr* rb_merge_copy_fn(struct rb_node_hdr *node, void *extra, enum rb_merge_trees tree)
 

typedef void rb_merge_free_fn(struct rb_node_hdr *node, void *extra, enum rb_merge_trees tree)
 

Enumeration Type Documentation

enum rb_merge_trees
 

Enumeration values:
MERGE_TREE_A 
MERGE_TREE_B 
MERGE_TREE_RES 

Function Documentation

void rb_add (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key,
struct rb_node_hdr *  new
) 
 

void rb_add_after (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key,
struct rb_node_hdr *  new,
struct rb_node_hdr *  existing
) 
 

struct rb_node_hdr* rb_copy (  struct rb_node_hdr *  source,
rb_copy_fn *  copy_node_fn,
void *  extra
) 
 

int rb_equal (  struct rb_node_hdr *  a,
struct rb_node_hdr *  b,
rb_equal_fn *  node_equal_fn,
void *  extra
) 
 

struct rb_node_hdr* rb_find_eq (  struct rb_node_hdr *  root,
rb_find_fn *  find_fn,
void *  key
) 
 

struct rb_node_hdr* rb_find_ge (  struct rb_node_hdr *  root,
rb_find_fn *  find_fn,
void *  key
) 
 

struct rb_node_hdr* rb_find_gt (  struct rb_node_hdr *  root,
rb_find_fn *  find_fn,
void *  key
) 
 

struct rb_node_hdr* rb_find_le (  struct rb_node_hdr *  root,
rb_find_fn *  find_fn,
void *  key
) 
 

struct rb_node_hdr* rb_find_lt (  struct rb_node_hdr *  root,
rb_find_fn *  find_fn,
void *  key
) 
 

PMOD_EXPORT struct rb_node_hdr* rb_first (  struct rb_node_hdr *  root  ) 
 

void rb_free (  struct rb_node_hdr *  root,
rb_free_fn *  free_node_fn,
void *  extra
) 
 

struct rb_node_hdr* rb_get_nth (  struct rb_node_hdr *  root,
size_t  n
) 
 

struct rb_node_hdr* rb_insert (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key,
struct rb_node_hdr *  new
) 
 

PMOD_EXPORT struct rb_node_hdr* rb_last (  struct rb_node_hdr *  root  ) 
 

struct rb_node_hdr* rb_linear_merge (  struct rb_node_hdr *  a,
struct rb_node_hdr *  b,
int  operation,
rb_cmp_fn *  cmp_fn,
void *  cmp_fn_extra,
rb_merge_copy_fn *  copy_node_fn,
void *  copy_fn_extra,
rb_merge_free_fn *  free_node_fn,
void *  free_fn_extra,
size_t *  length
) 
 

PMOD_EXPORT struct rb_node_hdr* rb_link_next (  struct rb_node_hdr *  node  ) 
 

PMOD_EXPORT struct rb_node_hdr* rb_link_prev (  struct rb_node_hdr *  node  ) 
 

struct rb_node_hdr* rb_make_list (  struct rb_node_hdr *  tree  ) 
 

struct rb_node_hdr* rb_make_tree (  struct rb_node_hdr *  list,
size_t  length
) 
 

struct rb_node_hdr* rb_remove (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key
) 
 

void rb_remove_node (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key,
struct rb_node_hdr *  node
) 
 

struct rb_node_hdr* rb_remove_node_with_move (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key,
struct rb_node_hdr *  node,
size_t  node_size
) 
 

struct rb_node_hdr* rb_remove_with_move (  struct rb_node_hdr **  root,
rb_find_fn *  find_fn,
void *  key,
size_t  node_size,
rb_free_fn *  cleanup_fn,
void *  cleanup_fn_extra
) 
 

size_t rb_sizeof (  struct rb_node_hdr *  root  ) 
 

Generated on Fri Jul 22 23:44:30 2005 for Pike by  doxygen 1.3.9.1