diff options
Diffstat (limited to 'deps/jemalloc/include/jemalloc/internal/rb.h')
| -rw-r--r-- | deps/jemalloc/include/jemalloc/internal/rb.h | 208 |
1 files changed, 93 insertions, 115 deletions
diff --git a/deps/jemalloc/include/jemalloc/internal/rb.h b/deps/jemalloc/include/jemalloc/internal/rb.h index 3770342f8..2ca8e5933 100644 --- a/deps/jemalloc/include/jemalloc/internal/rb.h +++ b/deps/jemalloc/include/jemalloc/internal/rb.h @@ -42,6 +42,7 @@ struct { \ #define rb_tree(a_type) \ struct { \ a_type *rbt_root; \ + a_type rbt_nil; \ } /* Left accessors. */ @@ -78,15 +79,6 @@ struct { \ (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \ (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \ } while (0) - -/* Node initializer. */ -#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ - /* Bookkeeping bit cannot be used by node pointer. */ \ - assert(((uintptr_t)(a_node) & 0x1) == 0); \ - rbtn_left_set(a_type, a_field, (a_node), NULL); \ - rbtn_right_set(a_type, a_field, (a_node), NULL); \ - rbtn_red_set(a_type, a_field, (a_node)); \ -} while (0) #else /* Right accessors. */ #define rbtn_right_get(a_type, a_field, a_node) \ @@ -107,26 +99,28 @@ struct { \ #define rbtn_black_set(a_type, a_field, a_node) do { \ (a_node)->a_field.rbn_red = false; \ } while (0) +#endif /* Node initializer. */ #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ - rbtn_left_set(a_type, a_field, (a_node), NULL); \ - rbtn_right_set(a_type, a_field, (a_node), NULL); \ + rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ + rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ rbtn_red_set(a_type, a_field, (a_node)); \ } while (0) -#endif /* Tree initializer. */ #define rb_new(a_type, a_field, a_rbt) do { \ - (a_rbt)->rbt_root = NULL; \ + (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \ + rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \ + rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \ } while (0) /* Internal utility macros. */ #define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \ (r_node) = (a_root); \ - if ((r_node) != NULL) { \ + if ((r_node) != &(a_rbt)->rbt_nil) { \ for (; \ - rbtn_left_get(a_type, a_field, (r_node)) != NULL; \ + rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\ (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \ } \ } \ @@ -134,9 +128,10 @@ struct { \ #define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \ (r_node) = (a_root); \ - if ((r_node) != NULL) { \ - for (; rbtn_right_get(a_type, a_field, (r_node)) != NULL; \ - (r_node) = rbtn_right_get(a_type, a_field, (r_node))) { \ + if ((r_node) != &(a_rbt)->rbt_nil) { \ + for (; rbtn_right_get(a_type, a_field, (r_node)) != \ + &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \ + (r_node))) { \ } \ } \ } while (0) @@ -174,11 +169,11 @@ a_prefix##next(a_rbt_type *rbtree, a_type *node); \ a_attr a_type * \ a_prefix##prev(a_rbt_type *rbtree, a_type *node); \ a_attr a_type * \ -a_prefix##search(a_rbt_type *rbtree, const a_type *key); \ +a_prefix##search(a_rbt_type *rbtree, a_type *key); \ a_attr a_type * \ -a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key); \ +a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \ a_attr a_type * \ -a_prefix##psearch(a_rbt_type *rbtree, const a_type *key); \ +a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \ a_attr void \ a_prefix##insert(a_rbt_type *rbtree, a_type *node); \ a_attr void \ @@ -188,10 +183,7 @@ a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ a_rbt_type *, a_type *, void *), void *arg); \ a_attr a_type * \ a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ - a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); \ -a_attr void \ -a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ - void *arg); + a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); /* * The rb_gen() macro generates a type-specific red-black tree implementation, @@ -262,7 +254,7 @@ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ * last/first. * * static ex_node_t * - * ex_search(ex_t *tree, const ex_node_t *key); + * ex_search(ex_t *tree, ex_node_t *key); * Description: Search for node that matches key. * Args: * tree: Pointer to an initialized red-black tree object. @@ -270,9 +262,9 @@ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ * Ret: Node in tree that matches key, or NULL if no match. * * static ex_node_t * - * ex_nsearch(ex_t *tree, const ex_node_t *key); + * ex_nsearch(ex_t *tree, ex_node_t *key); * static ex_node_t * - * ex_psearch(ex_t *tree, const ex_node_t *key); + * ex_psearch(ex_t *tree, ex_node_t *key); * Description: Search for node that matches key. If no match is found, * return what would be key's successor/predecessor, were * key in tree. @@ -320,20 +312,6 @@ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ * arg : Opaque pointer passed to cb(). * Ret: NULL if iteration completed, or the non-NULL callback return value * that caused termination of the iteration. - * - * static void - * ex_destroy(ex_t *tree, void (*cb)(ex_node_t *, void *), void *arg); - * Description: Iterate over the tree with post-order traversal, remove - * each node, and run the callback if non-null. This is - * used for destroying a tree without paying the cost to - * rebalance it. The tree must not be otherwise altered - * during traversal. - * Args: - * tree: Pointer to an initialized red-black tree object. - * cb : Callback function, which, if non-null, is called for each node - * during iteration. There is no way to stop iteration once it - * has begun. - * arg : Opaque pointer passed to cb(). */ #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \ a_attr void \ @@ -342,30 +320,36 @@ a_prefix##new(a_rbt_type *rbtree) { \ } \ a_attr bool \ a_prefix##empty(a_rbt_type *rbtree) { \ - return (rbtree->rbt_root == NULL); \ + return (rbtree->rbt_root == &rbtree->rbt_nil); \ } \ a_attr a_type * \ a_prefix##first(a_rbt_type *rbtree) { \ a_type *ret; \ rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ + if (ret == &rbtree->rbt_nil) { \ + ret = NULL; \ + } \ return (ret); \ } \ a_attr a_type * \ a_prefix##last(a_rbt_type *rbtree) { \ a_type *ret; \ rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ + if (ret == &rbtree->rbt_nil) { \ + ret = NULL; \ + } \ return (ret); \ } \ a_attr a_type * \ a_prefix##next(a_rbt_type *rbtree, a_type *node) { \ a_type *ret; \ - if (rbtn_right_get(a_type, a_field, node) != NULL) { \ + if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \ a_field, node), ret); \ } else { \ a_type *tnode = rbtree->rbt_root; \ - assert(tnode != NULL); \ - ret = NULL; \ + assert(tnode != &rbtree->rbt_nil); \ + ret = &rbtree->rbt_nil; \ while (true) { \ int cmp = (a_cmp)(node, tnode); \ if (cmp < 0) { \ @@ -376,21 +360,24 @@ a_prefix##next(a_rbt_type *rbtree, a_type *node) { \ } else { \ break; \ } \ - assert(tnode != NULL); \ + assert(tnode != &rbtree->rbt_nil); \ } \ } \ + if (ret == &rbtree->rbt_nil) { \ + ret = (NULL); \ + } \ return (ret); \ } \ a_attr a_type * \ a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \ a_type *ret; \ - if (rbtn_left_get(a_type, a_field, node) != NULL) { \ + if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \ a_field, node), ret); \ } else { \ a_type *tnode = rbtree->rbt_root; \ - assert(tnode != NULL); \ - ret = NULL; \ + assert(tnode != &rbtree->rbt_nil); \ + ret = &rbtree->rbt_nil; \ while (true) { \ int cmp = (a_cmp)(node, tnode); \ if (cmp < 0) { \ @@ -401,17 +388,20 @@ a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \ } else { \ break; \ } \ - assert(tnode != NULL); \ + assert(tnode != &rbtree->rbt_nil); \ } \ } \ + if (ret == &rbtree->rbt_nil) { \ + ret = (NULL); \ + } \ return (ret); \ } \ a_attr a_type * \ -a_prefix##search(a_rbt_type *rbtree, const a_type *key) { \ +a_prefix##search(a_rbt_type *rbtree, a_type *key) { \ a_type *ret; \ int cmp; \ ret = rbtree->rbt_root; \ - while (ret != NULL \ + while (ret != &rbtree->rbt_nil \ && (cmp = (a_cmp)(key, ret)) != 0) { \ if (cmp < 0) { \ ret = rbtn_left_get(a_type, a_field, ret); \ @@ -419,14 +409,17 @@ a_prefix##search(a_rbt_type *rbtree, const a_type *key) { \ ret = rbtn_right_get(a_type, a_field, ret); \ } \ } \ + if (ret == &rbtree->rbt_nil) { \ + ret = (NULL); \ + } \ return (ret); \ } \ a_attr a_type * \ -a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) { \ +a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \ a_type *ret; \ a_type *tnode = rbtree->rbt_root; \ - ret = NULL; \ - while (tnode != NULL) { \ + ret = &rbtree->rbt_nil; \ + while (tnode != &rbtree->rbt_nil) { \ int cmp = (a_cmp)(key, tnode); \ if (cmp < 0) { \ ret = tnode; \ @@ -438,14 +431,17 @@ a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) { \ break; \ } \ } \ + if (ret == &rbtree->rbt_nil) { \ + ret = (NULL); \ + } \ return (ret); \ } \ a_attr a_type * \ -a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) { \ +a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \ a_type *ret; \ a_type *tnode = rbtree->rbt_root; \ - ret = NULL; \ - while (tnode != NULL) { \ + ret = &rbtree->rbt_nil; \ + while (tnode != &rbtree->rbt_nil) { \ int cmp = (a_cmp)(key, tnode); \ if (cmp < 0) { \ tnode = rbtn_left_get(a_type, a_field, tnode); \ @@ -457,6 +453,9 @@ a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) { \ break; \ } \ } \ + if (ret == &rbtree->rbt_nil) { \ + ret = (NULL); \ + } \ return (ret); \ } \ a_attr void \ @@ -468,7 +467,7 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ rbt_node_new(a_type, a_field, rbtree, node); \ /* Wind. */ \ path->node = rbtree->rbt_root; \ - for (pathp = path; pathp->node != NULL; pathp++) { \ + for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ int cmp = pathp->cmp = a_cmp(node, pathp->node); \ assert(cmp != 0); \ if (cmp < 0) { \ @@ -488,8 +487,7 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ rbtn_left_set(a_type, a_field, cnode, left); \ if (rbtn_red_get(a_type, a_field, left)) { \ a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ - if (leftleft != NULL && rbtn_red_get(a_type, a_field, \ - leftleft)) { \ + if (rbtn_red_get(a_type, a_field, leftleft)) { \ /* Fix up 4-node. */ \ a_type *tnode; \ rbtn_black_set(a_type, a_field, leftleft); \ @@ -504,8 +502,7 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, cnode, right); \ if (rbtn_red_get(a_type, a_field, right)) { \ a_type *left = rbtn_left_get(a_type, a_field, cnode); \ - if (left != NULL && rbtn_red_get(a_type, a_field, \ - left)) { \ + if (rbtn_red_get(a_type, a_field, left)) { \ /* Split 4-node. */ \ rbtn_black_set(a_type, a_field, left); \ rbtn_black_set(a_type, a_field, right); \ @@ -538,7 +535,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ /* Wind. */ \ nodep = NULL; /* Silence compiler warning. */ \ path->node = rbtree->rbt_root; \ - for (pathp = path; pathp->node != NULL; pathp++) { \ + for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ int cmp = pathp->cmp = a_cmp(node, pathp->node); \ if (cmp < 0) { \ pathp[1].node = rbtn_left_get(a_type, a_field, \ @@ -550,7 +547,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ /* Find node's successor, in preparation for swap. */ \ pathp->cmp = 1; \ nodep = pathp; \ - for (pathp++; pathp->node != NULL; \ + for (pathp++; pathp->node != &rbtree->rbt_nil; \ pathp++) { \ pathp->cmp = -1; \ pathp[1].node = rbtn_left_get(a_type, a_field, \ @@ -593,7 +590,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ } \ } else { \ a_type *left = rbtn_left_get(a_type, a_field, node); \ - if (left != NULL) { \ + if (left != &rbtree->rbt_nil) { \ /* node has no successor, but it has a left child. */\ /* Splice node out, without losing the left child. */\ assert(!rbtn_red_get(a_type, a_field, node)); \ @@ -613,32 +610,33 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ return; \ } else if (pathp == path) { \ /* The tree only contained one node. */ \ - rbtree->rbt_root = NULL; \ + rbtree->rbt_root = &rbtree->rbt_nil; \ return; \ } \ } \ if (rbtn_red_get(a_type, a_field, pathp->node)) { \ /* Prune red node, which requires no fixup. */ \ assert(pathp[-1].cmp < 0); \ - rbtn_left_set(a_type, a_field, pathp[-1].node, NULL); \ + rbtn_left_set(a_type, a_field, pathp[-1].node, \ + &rbtree->rbt_nil); \ return; \ } \ /* The node to be pruned is black, so unwind until balance is */\ /* restored. */\ - pathp->node = NULL; \ + pathp->node = &rbtree->rbt_nil; \ for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ assert(pathp->cmp != 0); \ if (pathp->cmp < 0) { \ rbtn_left_set(a_type, a_field, pathp->node, \ pathp[1].node); \ + assert(!rbtn_red_get(a_type, a_field, pathp[1].node)); \ if (rbtn_red_get(a_type, a_field, pathp->node)) { \ a_type *right = rbtn_right_get(a_type, a_field, \ pathp->node); \ a_type *rightleft = rbtn_left_get(a_type, a_field, \ right); \ a_type *tnode; \ - if (rightleft != NULL && rbtn_red_get(a_type, a_field, \ - rightleft)) { \ + if (rbtn_red_get(a_type, a_field, rightleft)) { \ /* In the following diagrams, ||, //, and \\ */\ /* indicate the path to the removed node. */\ /* */\ @@ -681,8 +679,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ pathp->node); \ a_type *rightleft = rbtn_left_get(a_type, a_field, \ right); \ - if (rightleft != NULL && rbtn_red_get(a_type, a_field, \ - rightleft)) { \ + if (rbtn_red_get(a_type, a_field, rightleft)) { \ /* || */\ /* pathp(b) */\ /* // \ */\ @@ -736,8 +733,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ left); \ a_type *leftrightleft = rbtn_left_get(a_type, a_field, \ leftright); \ - if (leftrightleft != NULL && rbtn_red_get(a_type, \ - a_field, leftrightleft)) { \ + if (rbtn_red_get(a_type, a_field, leftrightleft)) { \ /* || */\ /* pathp(b) */\ /* / \\ */\ @@ -763,7 +759,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ /* (b) */\ /* / */\ /* (b) */\ - assert(leftright != NULL); \ + assert(leftright != &rbtree->rbt_nil); \ rbtn_red_set(a_type, a_field, leftright); \ rbtn_rotate_right(a_type, a_field, pathp->node, \ tnode); \ @@ -786,8 +782,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ return; \ } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \ a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ - if (leftleft != NULL && rbtn_red_get(a_type, a_field, \ - leftleft)) { \ + if (rbtn_red_get(a_type, a_field, leftleft)) { \ /* || */\ /* pathp(r) */\ /* / \\ */\ @@ -825,8 +820,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ } \ } else { \ a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ - if (leftleft != NULL && rbtn_red_get(a_type, a_field, \ - leftleft)) { \ + if (rbtn_red_get(a_type, a_field, leftleft)) { \ /* || */\ /* pathp(b) */\ /* / \\ */\ @@ -872,13 +866,13 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ a_attr a_type * \ a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \ a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ - if (node == NULL) { \ - return (NULL); \ + if (node == &rbtree->rbt_nil) { \ + return (&rbtree->rbt_nil); \ } else { \ a_type *ret; \ if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \ - a_field, node), cb, arg)) != NULL || (ret = cb(rbtree, node, \ - arg)) != NULL) { \ + a_field, node), cb, arg)) != &rbtree->rbt_nil \ + || (ret = cb(rbtree, node, arg)) != NULL) { \ return (ret); \ } \ return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ @@ -892,8 +886,8 @@ a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \ if (cmp < 0) { \ a_type *ret; \ if ((ret = a_prefix##iter_start(rbtree, start, \ - rbtn_left_get(a_type, a_field, node), cb, arg)) != NULL || \ - (ret = cb(rbtree, node, arg)) != NULL) { \ + rbtn_left_get(a_type, a_field, node), cb, arg)) != \ + &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ return (ret); \ } \ return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ @@ -920,18 +914,21 @@ a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ } else { \ ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\ } \ + if (ret == &rbtree->rbt_nil) { \ + ret = NULL; \ + } \ return (ret); \ } \ a_attr a_type * \ a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \ a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ - if (node == NULL) { \ - return (NULL); \ + if (node == &rbtree->rbt_nil) { \ + return (&rbtree->rbt_nil); \ } else { \ a_type *ret; \ if ((ret = a_prefix##reverse_iter_recurse(rbtree, \ - rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \ - (ret = cb(rbtree, node, arg)) != NULL) { \ + rbtn_right_get(a_type, a_field, node), cb, arg)) != \ + &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ return (ret); \ } \ return (a_prefix##reverse_iter_recurse(rbtree, \ @@ -946,8 +943,8 @@ a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \ if (cmp > 0) { \ a_type *ret; \ if ((ret = a_prefix##reverse_iter_start(rbtree, start, \ - rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \ - (ret = cb(rbtree, node, arg)) != NULL) { \ + rbtn_right_get(a_type, a_field, node), cb, arg)) != \ + &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ return (ret); \ } \ return (a_prefix##reverse_iter_recurse(rbtree, \ @@ -975,29 +972,10 @@ a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \ cb, arg); \ } \ - return (ret); \ -} \ -a_attr void \ -a_prefix##destroy_recurse(a_rbt_type *rbtree, a_type *node, void (*cb)( \ - a_type *, void *), void *arg) { \ - if (node == NULL) { \ - return; \ - } \ - a_prefix##destroy_recurse(rbtree, rbtn_left_get(a_type, a_field, \ - node), cb, arg); \ - rbtn_left_set(a_type, a_field, (node), NULL); \ - a_prefix##destroy_recurse(rbtree, rbtn_right_get(a_type, a_field, \ - node), cb, arg); \ - rbtn_right_set(a_type, a_field, (node), NULL); \ - if (cb) { \ - cb(node, arg); \ + if (ret == &rbtree->rbt_nil) { \ + ret = NULL; \ } \ -} \ -a_attr void \ -a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ - void *arg) { \ - a_prefix##destroy_recurse(rbtree, rbtree->rbt_root, cb, arg); \ - rbtree->rbt_root = NULL; \ + return (ret); \ } #endif /* RB_H_ */ |