jemalloc_rb.h File Reference

Go to the source code of this file.

Defines
#define	rb_node(a_type)
#define	rb_tree(a_type)
#define	rbp_left_get(a_type, a_field, a_node)   ((a_node)->a_field.rbn_left)
#define	rbp_left_set(a_type, a_field, a_node, a_left)
#define	rbp_right_get(a_type, a_field, a_node)
#define	rbp_right_set(a_type, a_field, a_node, a_right)
#define	rbp_red_get(a_type, a_field, a_node)
#define	rbp_color_set(a_type, a_field, a_node, a_red)
#define	rbp_red_set(a_type, a_field, a_node)
#define	rbp_black_set(a_type, a_field, a_node)
#define	rbp_node_new(a_type, a_field, a_tree, a_node)
#define	rb_new(a_type, a_field, a_tree)
#define	rbp_black_height(a_type, a_field, a_tree, r_height)
#define	rbp_first(a_type, a_field, a_tree, a_root, r_node)
#define	rbp_last(a_type, a_field, a_tree, a_root, r_node)
#define	rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node)
#define	rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node)
#define	rb_first(a_type, a_field, a_tree, r_node)
#define	rb_last(a_type, a_field, a_tree, r_node)
#define	rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node)
#define	rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node)
#define	rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node)
#define	rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node)
#define	rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node)
#define	rbp_rotate_left(a_type, a_field, a_node, r_node)
#define	rbp_rotate_right(a_type, a_field, a_node, r_node)
#define	rbp_lean_left(a_type, a_field, a_node, r_node)
#define	rbp_lean_right(a_type, a_field, a_node, r_node)
#define	rbp_move_red_left(a_type, a_field, a_node, r_node)
#define	rbp_move_red_right(a_type, a_field, a_node, r_node)
#define	rb_insert(a_type, a_field, a_cmp, a_tree, a_node)
#define	rb_remove(a_type, a_field, a_cmp, a_tree, a_node)
#define	rb_wrap(a_attr, a_prefix, a_tree_type, a_type, a_field, a_cmp)
#define	rbp_compute_f_height(a_type, a_field, a_tree)
#define	rbp_compute_fr_height(a_type, a_field, a_tree)
#define	rb_foreach_begin(a_type, a_field, a_tree, a_var)
#define	rb_foreach_next(a_type, a_field, a_cmp, a_tree, a_node)
#define	rb_foreach_end(a_type, a_field, a_tree, a_var)
#define	rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var)
#define	rb_foreach_reverse_prev(a_type, a_field, a_cmp, a_tree, a_node)
#define	rb_foreach_reverse_end(a_type, a_field, a_tree, a_var)

---

Define Documentation

#define rb_first	(		a_type,
			a_field,
			a_tree,
			r_node
	)

Value:

do {                    \
    rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node));   \
    if ((r_node) == &(a_tree)->rbt_nil) {                               \
        (r_node) = NULL;                                                \
    }                                                                   \
} while (0)

#define rb_foreach_begin	(		a_type,
			a_field,
			a_tree,
			a_var
	)

Value:

{               \
    rbp_compute_f_height(a_type, a_field, a_tree)                       \
    {                                                                   \
        /* Initialize the path to contain the left spine.             */\
        a_type *rbp_f_path[rbp_f_height];                               \
        a_type *rbp_f_node;                                             \
        bool rbp_f_synced = false;                                      \
        unsigned rbp_f_depth = 0;                                       \
        if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {                 \
            rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;               \
            rbp_f_depth++;                                              \
            while ((rbp_f_node = rbp_left_get(a_type, a_field,          \
              rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {      \
                rbp_f_path[rbp_f_depth] = rbp_f_node;                   \
                rbp_f_depth++;                                          \
            }                                                           \
        }                                                               \
        /* While the path is non-empty, iterate.                      */\
        while (rbp_f_depth > 0) {                                       \
            (a_var) = rbp_f_path[rbp_f_depth-1];

#define rb_foreach_end	(		a_type,
			a_field,
			a_tree,
			a_var
	)

#define rb_foreach_next	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node
	)

Value:

/* Re-initialize the path to contain the path to a_node.  */\
            rbp_f_depth = 0;                                            \
            if (a_node != NULL) {                                       \
                if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {         \
                    rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;       \
                    rbp_f_depth++;                                      \
                    rbp_f_node = rbp_f_path[0];                         \
                    while (true) {                                      \
                        int rbp_f_cmp = (a_cmp)((a_node),               \
                          rbp_f_path[rbp_f_depth-1]);                   \
                        if (rbp_f_cmp < 0) {                            \
                            rbp_f_node = rbp_left_get(a_type, a_field,  \
                              rbp_f_path[rbp_f_depth-1]);               \
                        } else if (rbp_f_cmp > 0) {                     \
                            rbp_f_node = rbp_right_get(a_type, a_field, \
                              rbp_f_path[rbp_f_depth-1]);               \
                        } else {                                        \
                            break;                                      \
                        }                                               \
                        assert(rbp_f_node != &(a_tree)->rbt_nil);       \
                        rbp_f_path[rbp_f_depth] = rbp_f_node;           \
                        rbp_f_depth++;                                  \
                    }                                                   \
                }                                                       \
            }                                                           \
            rbp_f_synced = true;

#define rb_foreach_reverse_begin	(		a_type,
			a_field,
			a_tree,
			a_var
	)

Value:

{       \
    rbp_compute_fr_height(a_type, a_field, a_tree)                      \
    {                                                                   \
        /* Initialize the path to contain the right spine.            */\
        a_type *rbp_fr_path[rbp_fr_height];                             \
        a_type *rbp_fr_node;                                            \
        bool rbp_fr_synced = false;                                     \
        unsigned rbp_fr_depth = 0;                                      \
        if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {                 \
            rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;             \
            rbp_fr_depth++;                                             \
            while ((rbp_fr_node = rbp_right_get(a_type, a_field,        \
              rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {    \
                rbp_fr_path[rbp_fr_depth] = rbp_fr_node;                \
                rbp_fr_depth++;                                         \
            }                                                           \
        }                                                               \
        /* While the path is non-empty, iterate.                      */\
        while (rbp_fr_depth > 0) {                                      \
            (a_var) = rbp_fr_path[rbp_fr_depth-1];

#define rb_foreach_reverse_end	(		a_type,
			a_field,
			a_tree,
			a_var
	)

#define rb_foreach_reverse_prev	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node
	)

Value:

/* Re-initialize the path to contain the path to a_node.  */\
            rbp_fr_depth = 0;                                           \
            if (a_node != NULL) {                                       \
                if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {         \
                    rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;     \
                    rbp_fr_depth++;                                     \
                    rbp_fr_node = rbp_fr_path[0];                       \
                    while (true) {                                      \
                        int rbp_fr_cmp = (a_cmp)((a_node),              \
                          rbp_fr_path[rbp_fr_depth-1]);                 \
                        if (rbp_fr_cmp < 0) {                           \
                            rbp_fr_node = rbp_left_get(a_type, a_field, \
                              rbp_fr_path[rbp_fr_depth-1]);             \
                        } else if (rbp_fr_cmp > 0) {                    \
                            rbp_fr_node = rbp_right_get(a_type, a_field,\
                              rbp_fr_path[rbp_fr_depth-1]);             \
                        } else {                                        \
                            break;                                      \
                        }                                               \
                        assert(rbp_fr_node != &(a_tree)->rbt_nil);      \
                        rbp_fr_path[rbp_fr_depth] = rbp_fr_node;        \
                        rbp_fr_depth++;                                 \
                    }                                                   \
                }                                                       \
            }                                                           \
            rbp_fr_synced = true;

#define rb_insert	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node
	)

#define rb_last	(		a_type,
			a_field,
			a_tree,
			r_node
	)

Value:

do {                    \
    rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node);      \
    if ((r_node) == &(a_tree)->rbt_nil) {                               \
        (r_node) = NULL;                                                \
    }                                                                   \
} while (0)

#define rb_new	(		a_type,
			a_field,
			a_tree
	)

Value:

do {                            \
    (a_tree)->rbt_root = &(a_tree)->rbt_nil;                            \
    rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);          \
    rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);                 \
} while (0)

#define rb_next	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node,
			r_node
	)

Value:

do {    \
    rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));       \
    if ((r_node) == &(a_tree)->rbt_nil) {                               \
        (r_node) = NULL;                                                \
    }                                                                   \
} while (0)

#define rb_node

(

a_type

)

Value:

struct {                                                                \
    a_type *rbn_left;                                                   \
    a_type *rbn_right_red;                                              \
}

Referenced by rb_tree().

#define rb_nsearch	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_key,
			r_node
	)

Value:

do {    \
    a_type *rbp_ns_t = (a_tree)->rbt_root;                              \
    (r_node) = NULL;                                                    \
    while (rbp_ns_t != &(a_tree)->rbt_nil) {                            \
        int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t);                    \
        if (rbp_ns_cmp < 0) {                                           \
            (r_node) = rbp_ns_t;                                        \
            rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t);         \
        } else if (rbp_ns_cmp > 0) {                                    \
            rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t);        \
        } else {                                                        \
            (r_node) = rbp_ns_t;                                        \
            break;                                                      \
        }                                                               \
    }                                                                   \
} while (0)

#define rb_prev	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node,
			r_node
	)

Value:

do {    \
    rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));       \
    if ((r_node) == &(a_tree)->rbt_nil) {                               \
        (r_node) = NULL;                                                \
    }                                                                   \
} while (0)

#define rb_psearch	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_key,
			r_node
	)

Value:

do {    \
    a_type *rbp_ps_t = (a_tree)->rbt_root;                              \
    (r_node) = NULL;                                                    \
    while (rbp_ps_t != &(a_tree)->rbt_nil) {                            \
        int rbp_ps_cmp = (a_cmp)((a_key), rbp_ps_t);                    \
        if (rbp_ps_cmp < 0) {                                           \
            rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t);         \
        } else if (rbp_ps_cmp > 0) {                                    \
            (r_node) = rbp_ps_t;                                        \
            rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t);        \
        } else {                                                        \
            (r_node) = rbp_ps_t;                                        \
            break;                                                      \
        }                                                               \
    }                                                                   \
} while (0)

#define rb_remove	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node
	)

#define rb_search	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_key,
			r_node
	)

Value:

do {    \
    int rbp_se_cmp;                                                     \
    (r_node) = (a_tree)->rbt_root;                                      \
    while ((r_node) != &(a_tree)->rbt_nil                               \
      && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) {              \
        if (rbp_se_cmp < 0) {                                           \
            (r_node) = rbp_left_get(a_type, a_field, (r_node));         \
        } else {                                                        \
            (r_node) = rbp_right_get(a_type, a_field, (r_node));        \
        }                                                               \
    }                                                                   \
    if ((r_node) == &(a_tree)->rbt_nil) {                               \
        (r_node) = NULL;                                                \
    }                                                                   \
} while (0)

#define rb_tree

(

a_type

)

Value:

struct {                                                                \
    a_type *rbt_root;                                                   \
    a_type rbt_nil;                                                     \
}

#define rb_wrap	(		a_attr,
			a_prefix,
			a_tree_type,
			a_type,
			a_field,
			a_cmp
	)

#define rbp_black_height	(		a_type,
			a_field,
			a_tree,
			r_height
	)

Value:

do {    \
    a_type *rbp_bh_t;                                                   \
    for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;                 \
      rbp_bh_t != &(a_tree)->rbt_nil;                                   \
      rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {             \
        if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {          \
            (r_height)++;                                               \
        }                                                               \
    }                                                                   \
} while (0)

#define rbp_black_set	(		a_type,
			a_field,
			a_node
	)

Value:

do {                    \
    (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)           \
      (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));                \
} while (0)

#define rbp_color_set	(		a_type,
			a_field,
			a_node,
			a_red
	)

Value:

do {            \
    (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)          \
      (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))                 \
      | ((ssize_t)a_red));                                              \
} while (0)

#define rbp_compute_f_height	(		a_type,
			a_field,
			a_tree
	)

Value:

/* Compute the maximum possible tree depth (3X the black height). */\
    unsigned rbp_f_height;                                              \
    rbp_black_height(a_type, a_field, a_tree, rbp_f_height);            \
    rbp_f_height *= 3;

#define rbp_compute_fr_height	(		a_type,
			a_field,
			a_tree
	)

Value:

/* Compute the maximum possible tree depth (3X the black height). */\
    unsigned rbp_fr_height;                                             \
    rbp_black_height(a_type, a_field, a_tree, rbp_fr_height);           \
    rbp_fr_height *= 3;

#define rbp_first	(		a_type,
			a_field,
			a_tree,
			a_root,
			r_node
	)

Value:

do {            \
    for ((r_node) = (a_root);                                           \
      rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;    \
      (r_node) = rbp_left_get(a_type, a_field, (r_node))) {             \
    }                                                                   \
} while (0)

#define rbp_last	(		a_type,
			a_field,
			a_tree,
			a_root,
			r_node
	)

Value:

do {            \
    for ((r_node) = (a_root);                                           \
      rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;   \
      (r_node) = rbp_right_get(a_type, a_field, (r_node))) {            \
    }                                                                   \
} while (0)

#define rbp_lean_left	(		a_type,
			a_field,
			a_node,
			r_node
	)

Value:

do {            \
    bool rbp_ll_red;                                                    \
    rbp_rotate_left(a_type, a_field, (a_node), (r_node));               \
    rbp_ll_red = rbp_red_get(a_type, a_field, (a_node));                \
    rbp_color_set(a_type, a_field, (r_node), rbp_ll_red);               \
    rbp_red_set(a_type, a_field, (a_node));                             \
} while (0)

#define rbp_lean_right	(		a_type,
			a_field,
			a_node,
			r_node
	)

Value:

do {            \
    bool rbp_lr_red;                                                    \
    rbp_rotate_right(a_type, a_field, (a_node), (r_node));              \
    rbp_lr_red = rbp_red_get(a_type, a_field, (a_node));                \
    rbp_color_set(a_type, a_field, (r_node), rbp_lr_red);               \
    rbp_red_set(a_type, a_field, (a_node));                             \
} while (0)

#define rbp_left_get	(		a_type,
			a_field,
			a_node
	)		((a_node)->a_field.rbn_left)

#define rbp_left_set	(		a_type,
			a_field,
			a_node,
			a_left
	)

Value:

do {            \
    (a_node)->a_field.rbn_left = a_left;                                \
} while (0)

#define rbp_move_red_left	(		a_type,
			a_field,
			a_node,
			r_node
	)

Value:

do {            \
    a_type *rbp_mrl_t, *rbp_mrl_u;                                      \
    rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node));                \
    rbp_red_set(a_type, a_field, rbp_mrl_t);                            \
    rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));               \
    rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t);               \
    if (rbp_red_get(a_type, a_field, rbp_mrl_u)) {                      \
        rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u);        \
        rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u);            \
        rbp_rotate_left(a_type, a_field, (a_node), (r_node));           \
        rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));           \
        if (rbp_red_get(a_type, a_field, rbp_mrl_t)) {                  \
            rbp_black_set(a_type, a_field, rbp_mrl_t);                  \
            rbp_red_set(a_type, a_field, (a_node));                     \
            rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t);      \
            rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t);         \
        } else {                                                        \
            rbp_black_set(a_type, a_field, (a_node));                   \
        }                                                               \
    } else {                                                            \
        rbp_red_set(a_type, a_field, (a_node));                         \
        rbp_rotate_left(a_type, a_field, (a_node), (r_node));           \
    }                                                                   \
} while (0)

#define rbp_move_red_right	(		a_type,
			a_field,
			a_node,
			r_node
	)

#define rbp_next	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node,
			r_node
	)

Value:

do {    \
    if (rbp_right_get(a_type, a_field, (a_node))                        \
      != &(a_tree)->rbt_nil) {                                          \
        rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type,        \
          a_field, (a_node)), (r_node));                                \
    } else {                                                            \
        a_type *rbp_n_t = (a_tree)->rbt_root;                           \
        assert(rbp_n_t != &(a_tree)->rbt_nil);                          \
        (r_node) = &(a_tree)->rbt_nil;                                  \
        while (true) {                                                  \
            int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t);                 \
            if (rbp_n_cmp < 0) {                                        \
                (r_node) = rbp_n_t;                                     \
                rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t);       \
            } else if (rbp_n_cmp > 0) {                                 \
                rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t);      \
            } else {                                                    \
                break;                                                  \
            }                                                           \
            assert(rbp_n_t != &(a_tree)->rbt_nil);                      \
        }                                                               \
    }                                                                   \
} while (0)

#define rbp_node_new	(		a_type,
			a_field,
			a_tree,
			a_node
	)

Value:

do {            \
    rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);        \
    rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);       \
    rbp_red_set(a_type, a_field, (a_node));                             \
} while (0)

#define rbp_prev	(		a_type,
			a_field,
			a_cmp,
			a_tree,
			a_node,
			r_node
	)

Value:

do {    \
    if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\
        rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type,          \
          a_field, (a_node)), (r_node));                                \
    } else {                                                            \
        a_type *rbp_p_t = (a_tree)->rbt_root;                           \
        assert(rbp_p_t != &(a_tree)->rbt_nil);                          \
        (r_node) = &(a_tree)->rbt_nil;                                  \
        while (true) {                                                  \
            int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t);                 \
            if (rbp_p_cmp < 0) {                                        \
                rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t);       \
            } else if (rbp_p_cmp > 0) {                                 \
                (r_node) = rbp_p_t;                                     \
                rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t);      \
            } else {                                                    \
                break;                                                  \
            }                                                           \
            assert(rbp_p_t != &(a_tree)->rbt_nil);                      \
        }                                                               \
    }                                                                   \
} while (0)

#define rbp_red_get	(		a_type,
			a_field,
			a_node
	)

Value:

((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)          \
      & ((size_t)1)))

#define rbp_red_set	(		a_type,
			a_field,
			a_node
	)

Value:

do {                    \
    (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)          \
      (a_node)->a_field.rbn_right_red) | ((size_t)1));                  \
} while (0)

#define rbp_right_get	(		a_type,
			a_field,
			a_node
	)

Value:

((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)               \
      & ((ssize_t)-2)))

#define rbp_right_set	(		a_type,
			a_field,
			a_node,
			a_right
	)

Value:

do {            \
    (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
      | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
} while (0)

#define rbp_rotate_left	(		a_type,
			a_field,
			a_node,
			r_node
	)

Value:

do {            \
    (r_node) = rbp_right_get(a_type, a_field, (a_node));                \
    rbp_right_set(a_type, a_field, (a_node),                            \
      rbp_left_get(a_type, a_field, (r_node)));                         \
    rbp_left_set(a_type, a_field, (r_node), (a_node));                  \
} while (0)

#define rbp_rotate_right	(		a_type,
			a_field,
			a_node,
			r_node
	)

Value:

do {            \
    (r_node) = rbp_left_get(a_type, a_field, (a_node));                 \
    rbp_left_set(a_type, a_field, (a_node),                             \
      rbp_right_get(a_type, a_field, (r_node)));                        \
    rbp_right_set(a_type, a_field, (r_node), (a_node));                 \
} while (0)