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

rbtree.c File Reference

#include "global.h"
#include "interpret.h"
#include "pike_error.h"
#include "rbtree_low.h"
#include <assert.h>
#include <stdlib.h>

Defines

#define SET_PTR_TO_CHILD(PARENT, CHILD, PREV_VAL, NEXT_VAL)
#define DO_SIMPLE_UNLINK(UNLINK, PARENT, NODE)
#define ADJUST_STACK_TO_NEXT(RBSTACK, NEXT)

Functions

void rbstack_push (struct rbstack_ptr *rbstack, struct rb_node_hdr *node)
void rbstack_pop (struct rbstack_ptr *rbstack)
void rbstack_up (struct rbstack_ptr *rbstack)
void rbstack_up_to_root (struct rbstack_ptr *rbstack)
void rbstack_free (struct rbstack_ptr *rbstack)
void rbstack_insert (struct rbstack_ptr *top, struct rbstack_ptr *pos, struct rb_node_hdr *node)
void rbstack_shift (struct rbstack_ptr rbstack, struct rb_node_hdr *oldbase, struct rb_node_hdr *newbase)
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)
void low_rb_init_root (struct rb_node_hdr *node)
void low_rb_link_at_prev (struct rb_node_hdr **root, struct rbstack_ptr rbstack, struct rb_node_hdr *new)
void low_rb_link_at_next (struct rb_node_hdr **root, struct rbstack_ptr rbstack, struct rb_node_hdr *new)
rb_node_hdr * low_rb_unlink_with_move (struct rb_node_hdr **root, struct rbstack_ptr *rbstack_ptr, int keep_rbstack, size_t node_size)
void low_rb_unlink_without_move (struct rb_node_hdr **root, struct rbstack_ptr *rbstack_ptr, int keep_rbstack)
rb_node_hdr * rb_get_nth (struct rb_node_hdr *root, size_t n)
size_t rb_sizeof (struct rb_node_hdr *root)
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)

Define Documentation

#define ADJUST_STACK_TO_NEXT (  RBSTACK,
NEXT   ) 
 

Value:

do {                    \
    struct rb_node_hdr *node = RBSTACK_PEEK (RBSTACK);                  \
    if (NEXT && (!node ||                                               \
                 (!(node->flags & RB_THREAD_PREV) && node->prev == NEXT) || \
                 (!(node->flags & RB_THREAD_NEXT) && node->next == NEXT))) { \
      RBSTACK_PUSH (RBSTACK, NEXT);                                     \
      while (!(NEXT->flags & RB_THREAD_PREV))                           \
        RBSTACK_PUSH (RBSTACK, NEXT = NEXT->prev);                      \
    }                                                                   \
    else                                                                \
      while (node != NEXT) {                                            \
        RBSTACK_POP (RBSTACK, node);                                    \
        assert (!NEXT || node != NULL);                                 \
        node = RBSTACK_PEEK (RBSTACK);                                  \
      }                                                                 \
  } while (0)

#define DO_SIMPLE_UNLINK (  UNLINK,
PARENT,
NODE   ) 
 

#define SET_PTR_TO_CHILD (  PARENT,
CHILD,
PREV_VAL,
NEXT_VAL   ) 
 

Value:

do {    \
    if (CHILD == PARENT->prev)                                          \
      PARENT->prev = PREV_VAL;                                          \
    else {                                                              \
      DO_IF_DEBUG(                                                      \
        if (CHILD != PARENT->next)                                      \
          rb_fatal (PARENT, "Got invalid parent to %p "                 \
                    "(stack probably wrong).\n", CHILD);                \
      );                                                                \
      PARENT->next = NEXT_VAL;                                          \
    }                                                                   \
  } while (0)

Function Documentation

void low_rb_init_root (  struct rb_node_hdr *  node  ) 
 

void low_rb_link_at_next (  struct rb_node_hdr **  root,
struct rbstack_ptr  rbstack,
struct rb_node_hdr *  new
) 
 

void low_rb_link_at_prev (  struct rb_node_hdr **  root,
struct rbstack_ptr  rbstack,
struct rb_node_hdr *  new
) 
 

struct rb_node_hdr* low_rb_unlink_with_move (  struct rb_node_hdr **  root,
struct rbstack_ptr *  rbstack_ptr,
int  keep_rbstack,
size_t  node_size
) 
 

void low_rb_unlink_without_move (  struct rb_node_hdr **  root,
struct rbstack_ptr *  rbstack_ptr,
int  keep_rbstack
) 
 

PMOD_EXPORT struct rb_node_hdr* rb_first (  struct rb_node_hdr *  root  ) 
 

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

PMOD_EXPORT struct rb_node_hdr* rb_last (  struct rb_node_hdr *  root  ) 
 

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
) 
 

size_t rb_sizeof (  struct rb_node_hdr *  root  ) 
 

void rbstack_free (  struct rbstack_ptr *  rbstack  ) 
 

void rbstack_insert (  struct rbstack_ptr *  top,
struct rbstack_ptr *  pos,
struct rb_node_hdr *  node
) 
 

void rbstack_pop (  struct rbstack_ptr *  rbstack  ) 
 

void rbstack_push (  struct rbstack_ptr *  rbstack,
struct rb_node_hdr *  node
) 
 

void rbstack_shift (  struct rbstack_ptr  rbstack,
struct rb_node_hdr *  oldbase,
struct rb_node_hdr *  newbase
) 
 

void rbstack_up (  struct rbstack_ptr *  rbstack  ) 
 

void rbstack_up_to_root (  struct rbstack_ptr *  rbstack  ) 
 

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