#include "rbtree.h"Go to the source code of this file.
Classes | |
| struct | rbstack_slice |
| struct | rbstack_ptr |
Defines | |
| #define | STACK_SLICE_SIZE 20 |
| #define | RBSTACK_INIT(rbstack) |
| #define | RBSTACK_PUSH(rbstack, node) |
| #define | RBSTACK_POP(rbstack, node) |
| #define | RBSTACK_POP_IGNORE(rbstack) |
| #define | RBSTACK_UP(rbstack, node) |
| #define | RBSTACK_UP_IGNORE(rbstack) |
| #define | RBSTACK_PEEK(rbstack) ((rbstack).ssp ? (rbstack).slice->stack[(rbstack).ssp - 1] : NULL) |
| #define | RBSTACK_POKE(rbstack, node) |
| #define | RBSTACK_UP_TO_ROOT(rbstack, node) |
| #define | RBSTACK_FREE(rbstack) |
| #define | RBSTACK_FREE_SET_ROOT(rbstack, node) |
| #define | LOW_RB_TRAVERSE(label, rbstack, node, push, p_leaf, p_sub, between, n_leaf, n_sub, pop) |
| #define | LOW_RB_DEBUG_TRAVERSE(label, rbstack, node, push, p_leaf, p_sub, between, n_leaf, n_sub, pop) |
| #define | LOW_RB_FIND(node, cmp, got_lt, got_eq, got_gt) |
| #define | LOW_RB_FIND_NEQ(node, cmp, got_lt, got_gt) |
| #define | LOW_RB_TRACK(rbstack, node, cmp, got_lt, got_eq, got_gt) |
| #define | LOW_RB_TRACK_NEQ(rbstack, node, cmp, got_lt, got_gt) |
| #define | LOW_RB_TRACK_FIRST(rbstack, node) |
| #define | LOW_RB_TRACK_NEXT(rbstack, node) |
| #define | LOW_RB_TRACK_PREV(rbstack, node) |
| #define | LOW_RB_INSERT(tree, node, cmp, insert, replace) |
| #define | LOW_RB_MERGE(label, a, b, res, length, operation,prep_a, prep_b, cmp, copy_a, free_a, copy_b, free_b) |
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_assign (struct rbstack_ptr *target, struct rbstack_ptr *source) |
| void | rbstack_copy (struct rbstack_ptr *target, struct rbstack_ptr *source) |
| void | rbstack_shift (struct rbstack_ptr rbstack, struct rb_node_hdr *oldbase, struct rb_node_hdr *newbase) |
| void | low_rb_init_root (struct rb_node_hdr *new_root) |
| 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) |
| void | low_rb_build_stack (struct rb_node_hdr *root, struct rb_node_hdr *node, struct rbstack_ptr *rbstack) |
|
|
Value: do { \ size_t PIKE_CONCAT (depth_, label) = 0; \ LOW_RB_TRAVERSE( \ label, rbstack, node, \ fprintf (stderr, "%*s%p enter\n", \ PIKE_CONCAT (depth_, label)++, "", node); {push;}, \ fprintf (stderr, "%*s%p prev leaf\n", \ PIKE_CONCAT (depth_, label), "", node); {p_leaf;}, \ fprintf (stderr, "%*s%p prev subtree\n", \ PIKE_CONCAT (depth_, label), "", node); {p_sub;}, \ fprintf (stderr, "%*s%p between\n", \ PIKE_CONCAT (depth_, label) - 1, "", node); {between;}, \ fprintf (stderr, "%*s%p next leaf\n", \ PIKE_CONCAT (depth_, label), "", node); {n_leaf;}, \ fprintf (stderr, "%*s%p next subtree\n", \ PIKE_CONCAT (depth_, label), "", node); {n_sub;}, \ fprintf (stderr, "%*s%p leave\n", \ --PIKE_CONCAT (depth_, label), "", node); {pop;}); \ } while (0) |
|
|
|
|
|
|
|
|
Value: do { \ int rb_ins_type_; \ RBSTACK_INIT (rbstack); \ if (((node) = *(tree))) { \ LOW_RB_TRACK ( \ rbstack, node, cmp, \ { \ rb_ins_type_ = 1; /* Got less - link at next. */ \ }, { \ rb_ins_type_ = 0; /* Got equal - replace. */ \ {replace;} \ RBSTACK_FREE (rbstack); \ }, { \ rb_ins_type_ = 2; /* Got greater - link at prev. */ \ }); \ } \ else rb_ins_type_ = 3; \ if (rb_ins_type_) { \ DO_IF_DEBUG ((node) = 0); \ {insert;} \ switch (rb_ins_type_) { \ case 1: low_rb_link_at_next ((tree), rbstack, (node)); break; \ case 2: low_rb_link_at_prev ((tree), rbstack, (node)); break; \ case 3: low_rb_init_root (*(tree) = (node)); break; \ } \ } \ } while (0) |
|
|
|
|
|
Value: do { \ DO_IF_DEBUG ( \ if (RBSTACK_PEEK (rbstack)) Pike_fatal ("The stack is not empty.\n"); \ ); \ DO_IF_RB_STATS (rb_num_finds--); \ LOW_RB_FIND ( \ node, \ { \ DO_IF_RB_STATS (rb_find_depth--); \ RBSTACK_PUSH (rbstack, node); \ {cmp;} \ }, \ got_lt, \ { \ while ((node) != RBSTACK_PEEK (rbstack)) \ RBSTACK_POP_IGNORE (rbstack); \ {got_eq;} \ }, got_gt); \ } while (0) |
|
|
Value: do { \ DO_IF_DEBUG ( \ if (RBSTACK_PEEK (rbstack)) Pike_fatal ("The stack is not empty.\n"); \ ); \ DO_IF_RB_STATS (rb_num_sidetracks++); \ if (node) { \ struct rb_node_hdr *rb_prev_ = node->prev; \ RBSTACK_PUSH (rbstack, node); \ DO_IF_RB_STATS (rb_num_sidetrack_ops++); \ while (rb_prev_) { \ RBSTACK_PUSH (rbstack, node = rb_prev_); \ DO_IF_RB_STATS (rb_num_sidetrack_ops++); \ rb_prev_ = node->prev; \ } \ } \ } while (0) |
|
|
Value: do { \ DO_IF_DEBUG ( \ if (RBSTACK_PEEK (rbstack)) Pike_fatal ("The stack is not empty.\n"); \ ); \ DO_IF_RB_STATS (rb_num_finds--); \ LOW_RB_FIND_NEQ ( \ node, \ { \ DO_IF_RB_STATS (rb_find_depth--); \ RBSTACK_PUSH (rbstack, node); \ {cmp;} \ }, \ got_lt, got_gt); \ } while (0) |
|
|
Value: do { \ DO_IF_DEBUG ( \ if (node != RBSTACK_PEEK (rbstack)) \ Pike_fatal ("Given node is not on top of stack.\n"); \ ); \ DO_IF_RB_STATS (rb_num_sidetracks++); \ if (node->flags & RB_THREAD_NEXT) { \ struct rb_node_hdr *rb_next_ = node->next; \ while ((node = RBSTACK_PEEK (rbstack)) != rb_next_) { \ RBSTACK_POP_IGNORE (rbstack); \ DO_IF_RB_STATS (rb_num_sidetrack_ops++); \ } \ } \ else { \ node = node->next; \ while (1) { \ RBSTACK_PUSH (rbstack, node); \ DO_IF_RB_STATS (rb_num_sidetrack_ops++); \ if (node->flags & RB_THREAD_PREV) break; \ node = node->prev; \ } \ } \ } while (0) |
|
|
Value: do { \ DO_IF_DEBUG ( \ if (node != RBSTACK_PEEK (rbstack)) \ Pike_fatal ("Given node is not on top of stack.\n"); \ ); \ DO_IF_RB_STATS (rb_num_sidetracks++); \ if (node->flags & RB_THREAD_PREV) { \ struct rb_node_hdr *rb_prev_ = node->prev; \ while ((node = RBSTACK_PEEK (rbstack)) != rb_prev_) { \ RBSTACK_POP_IGNORE (rbstack); \ DO_IF_RB_STATS (rb_num_sidetrack_ops++); \ } \ } \ else { \ node = node->prev; \ while (1) { \ RBSTACK_PUSH (rbstack, node); \ DO_IF_RB_STATS (rb_num_sidetrack_ops++); \ if (node->flags & RB_THREAD_NEXT) break; \ node = node->next; \ } \ } \ } while (0) |
|
|
|
|
|
Value: do { \ if ((rbstack).ssp) { \ if ((rbstack).slice->up) rbstack_free (&(rbstack)); \ (rbstack).ssp = 0; \ } \ DO_IF_RB_STATS ( \ rb_num_tracks++; \ rb_track_depth += (rbstack).slice->maxdepth; \ if ((rbstack).slice->maxdepth > rb_max_depth) \ rb_max_depth = (rbstack).slice->maxdepth; \ (rbstack).slice->depth = (rbstack).slice->maxdepth = 0; \ ); \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp) { \ if ((rbstack).slice->up) rbstack_free (&(rbstack)); \ (rbstack).ssp = 0; \ (node) = (rbstack).slice->stack[0]; \ } \ DO_IF_RB_STATS ( \ rb_num_tracks++; \ rb_track_depth += (rbstack).slice->maxdepth; \ if ((rbstack).slice->maxdepth > rb_max_depth) \ rb_max_depth = (rbstack).slice->maxdepth; \ (rbstack).slice->depth = (rbstack).slice->maxdepth = 0; \ ); \ } while (0) |
|
|
Value: struct rbstack_slice PIKE_CONCAT3 (_, rbstack, _top_) = { \ DO_IF_RB_STATS (0 COMMA 0 COMMA) \ NULL, \ {NULL,} \ }; \ struct rbstack_ptr rbstack = { \ NULL, \ 0 \ }; \ rbstack.slice = &PIKE_CONCAT3 (_, rbstack, _top_) |
|
|
|
|
|
Value: do { \ DO_IF_DEBUG (if (!(rbstack).ssp) Pike_fatal ("Using free stack pointer.\n")); \ (rbstack).slice->stack[(rbstack).ssp - 1] = (node); \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp) { \ (node) = (rbstack).slice->stack[--(rbstack).ssp]; \ DO_IF_RB_STATS ((rbstack).slice->depth--); \ if (!(rbstack).ssp && (rbstack).slice->up) \ rbstack_pop (&(rbstack)); \ } \ else (node) = NULL; \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp && !--(rbstack).ssp) { \ DO_IF_RB_STATS ((rbstack).slice->depth--); \ if ((rbstack).slice->up) \ rbstack_pop (&(rbstack)); \ } \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp < STACK_SLICE_SIZE) { \ (rbstack).slice->stack[(rbstack).ssp++] = (node); \ } \ else rbstack_push (&(rbstack), node); \ DO_IF_RB_STATS ( \ if (++(rbstack).slice->depth > (rbstack).slice->maxdepth) \ (rbstack).slice->maxdepth = (rbstack).slice->depth; \ ); \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp) { \ (node) = (rbstack).slice->stack[--(rbstack).ssp]; \ if (!(rbstack).ssp && (rbstack).slice->up) \ rbstack_up (&(rbstack)); \ } \ else (node) = NULL; \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp && !--(rbstack).ssp && (rbstack).slice->up) \ rbstack_up (&(rbstack)); \ } while (0) |
|
|
Value: do { \ if ((rbstack).ssp) { \ rbstack_up_to_root (&(rbstack)); \ (node) = (rbstack).slice->stack[0]; \ } \ } while (0) |
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
||||||||||||||||
|
|
|
||||||||||||||||
|
|
|
||||||||||||||||||||
|
|
|
||||||||||||||||
|
|
|
||||||||||||
|
|
|
||||||||||||
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
||||||||||||
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
1.3.9.1