diff options
Diffstat (limited to 'erts/emulator/beam/erl_rbtree.h')
| -rw-r--r-- | erts/emulator/beam/erl_rbtree.h | 461 |
1 files changed, 337 insertions, 124 deletions
diff --git a/erts/emulator/beam/erl_rbtree.h b/erts/emulator/beam/erl_rbtree.h index e59d6900b0..ce401fa7e7 100644 --- a/erts/emulator/beam/erl_rbtree.h +++ b/erts/emulator/beam/erl_rbtree.h @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2015-2017. All Rights Reserved. + * Copyright Ericsson AB 2015-2018. All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -50,8 +50,14 @@ * - ERTS_RBT_GET_LEFT(T) - Get left child node. * - ERTS_RBT_SET_LEFT(T, L) - Set left child node. * - ERTS_RBT_GET_KEY(T) - Get key of node. - * - ERTS_RBT_IS_LT(KX, KY) - Is key KX less than key KY? - * - ERTS_RBT_IS_EQ(KX, KY) - Is key KX equal to key KY? + * Either: + * - ERTS_RBT_CMP_KEYS(KX, KY) - Compare keys... + * or: + * - ERTS_RBT_IS_LT(KX, KY) - Is key KX less than key KY? + * - ERTS_RBT_IS_EQ(KX, KY) - Is key KX equal to key KY? + * + * If ERTS_RBT_CMP_KEYS is defined ERTS_RBT_IS_LT and + * ERTS_RBT_IS_EQ will be redefined using ERTS_RBT_CMP_KEYS * * Optional defines: * @@ -155,7 +161,7 @@ * * - void <ERTS_RBT_PREFIX>_rbt_foreach( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg); * Operate by calling the operator 'op' on each element. * Order is undefined. @@ -164,7 +170,7 @@ * * - void <ERTS_RBT_PREFIX>_rbt_foreach_destroy( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg); * Operate by calling the operator 'op' on each element. * Order is undefined. Each element should be destroyed @@ -174,39 +180,46 @@ * * - int <ERTS_RBT_PREFIX>_rbt_foreach_yielding( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg, * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate, - * Sint ylimit); + * Sint reds); * Operate by calling the operator 'op' on each element. * Order is undefined. * - * Yield when 'ylimit' elements has been processed. True is - * returned when yielding, and false is returned when - * the whole tree has been processed. The tree should not be - * modified until all of it has been processed. + * Yield when 'reds' reductions has been processed. The 'op' + * function return the number of reductions that each element + * took to process. The number of reductions remaining is returned, + * meaning that if 0 is returned, there are more elements to be + * processed. If a value greater than 0 is returned the foreach has + * ended. The tree should not be modified until all of it has been + * processed. * * 'arg' is passed as argument to 'op'. * * - int <ERTS_RBT_PREFIX>_rbt_foreach_destroy_yielding( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg, * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate, - * Sint ylimit); + * Sint reds); * Operate by calling the operator 'op' on each element. * Order is undefined. Each element should be destroyed * by 'op'. * - * Yield when 'ylimit' elements has been processed. True is - * returned when yielding, and false is returned when - * the whole tree has been processed. + * Yield when 'reds' reductions has been processed. The 'op' + * function return the number of reductions that each element + * took to process. The number of reductions remaining is returned, + * meaning that if 0 is returned, there are more elements to be + * processed. If a value greater than 0 is returned the foreach has + * ended. The tree should not be modified until all of it has been + * processed. * * 'arg' is passed as argument to 'op'. * * - void <ERTS_RBT_PREFIX>_rbt_foreach_small( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg); * Operate by calling the operator 'op' on each element from * smallest towards larger elements. @@ -215,7 +228,7 @@ * * - void <ERTS_RBT_PREFIX>_rbt_foreach_large( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg); * Operate by calling the operator 'op' on each element from * largest towards smaller elements. @@ -224,40 +237,46 @@ * * - int <ERTS_RBT_PREFIX>_rbt_foreach_small_yielding( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg, * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate, - * Sint ylimit); + * Sint reds); * Operate by calling the operator 'op' on each element from * smallest towards larger elements. * - * Yield when 'ylimit' elements has been processed. True is - * returned when yielding, and false is returned when - * the whole tree has been processed. The tree should not be - * modified until all of it has been processed. + * Yield when 'reds' reductions has been processed. The 'op' + * function return the number of reductions that each element + * took to process. The number of reductions remaining is returned, + * meaning that if 0 is returned, there are more elements to be + * processed. If a value greater than 0 is returned the foreach has + * ended. The tree should not be modified until all of it has been + * processed. * * 'arg' is passed as argument to 'op'. * * - int <ERTS_RBT_PREFIX>_rbt_foreach_large_yielding( * ERTS_RBT_T *tree, - * void (*op)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), * void *arg, * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate, - * Sint ylimit); + * Sint reds); * Operate by calling the operator 'op' on each element from * largest towards smaller elements. * - * Yield when 'ylimit' elements has been processed. True is - * returned when yielding, and false is returned when - * the whole tree has been processed. The tree should not be - * modified until all of it has been processed. + * Yield when 'reds' reductions has been processed. The 'op' + * function return the number of reductions that each element + * took to process. The number of reductions remaining is returned, + * meaning that if 0 is returned, there are more elements to be + * processed. If a value greater than 0 is returned the foreach has + * ended. The tree should not be modified until all of it has been + * processed. * * 'arg' is passed as argument to 'op'. * * - void <ERTS_RBT_PREFIX>_rbt_foreach_small_destroy( * ERTS_RBT_T **tree, - * void (*op)(ERTS_RBT_T *, void *), - * void (*destr)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), + * int (*destr)(ERTS_RBT_T *, void *), * void *arg); * Operate by calling the operator 'op' on each element from * smallest towards larger elements. @@ -271,8 +290,8 @@ * * - void <ERTS_RBT_PREFIX>_rbt_foreach_large_destroy( * ERTS_RBT_T **tree, - * void (*op)(ERTS_RBT_T *, void *), - * void (*destr)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), + * int (*destr)(ERTS_RBT_T *, void *), * void *arg); * Operate by calling the operator 'op' on each element from * largest towards smaller elements. @@ -286,11 +305,11 @@ * * - int <ERTS_RBT_PREFIX>_rbt_foreach_small_destroy_yielding( * ERTS_RBT_T **tree, - * void (*op)(ERTS_RBT_T *, void *), - * void (*destr)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), + * int (*destr)(ERTS_RBT_T *, void *), * void *arg, * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate, - * Sint ylimit); + * Sint reds); * Operate by calling the operator 'op' on each element from * smallest towards larger elements. * @@ -299,20 +318,23 @@ * Note that elements are often destroyed in another order * than the order that the elements are operated on. * - * Yield when 'ylimit' elements has been processed. True is - * returned when yielding, and false is returned when - * the whole tree has been processed. The tree should not be - * modified until all of it has been processed. + * Yield when 'reds' reductions has been processed. The 'op' and + * 'destr' functions return the number of reductions that each element + * took to process. The number of reductions remaining is returned, + * meaning that if 0 is returned, there are more elements to be + * processed. If a value greater than 0 is returned the foreach has + * ended. The tree should not be modified until all of it has been + * processed. * * 'arg' is passed as argument to 'op' and 'destroy'. * * - int <ERTS_RBT_PREFIX>_rbt_foreach_large_destroy_yielding( * ERTS_RBT_T **tree, - * void (*op)(ERTS_RBT_T *, void *), - * void (*destr)(ERTS_RBT_T *, void *), + * int (*op)(ERTS_RBT_T *, void *), + * int (*destr)(ERTS_RBT_T *, void *), * void *arg, * <ERTS_RBT_PREFIX>_rbt_yield_state_t *ystate, - * Sint ylimit); + * Sint reds); * Operate by calling the operator 'op' on each element from * largest towards smaller elements. * @@ -321,10 +343,13 @@ * Note that elements are often destroyed in another order * than the order that the elements are operated on. * - * Yield when 'ylimit' elements has been processed. True is - * returned when yielding, and false is returned when - * the whole tree has been processed. The tree should not be - * modified until all of it has been processed. + * Yield when 'reds' reductions has been processed. The 'op' and + * 'destr' functions return the number of reductions that each element + * took to process. The number of reductions remaining is returned, + * meaning that if 0 is returned, there are more elements to be + * processed. If a value greater than 0 is returned the foreach has + * ended. The tree should not be modified until all of it has been + * processed. * * 'arg' is passed as argument to 'op' and 'destroy'. * @@ -337,6 +362,15 @@ * Should only be used for debuging. */ +#ifdef ERTS_RBT_CMP_KEYS + +# undef ERTS_RBT_IS_LT +# define ERTS_RBT_IS_LT(KX, KY) (ERTS_RBT_CMP_KEYS((KX), (KY)) < 0) + +# undef ERTS_RBT_IS_EQ +# define ERTS_RBT_IS_EQ(KX, KY) (ERTS_RBT_CMP_KEYS((KX), (KY)) == 0) + +#endif /* * Check that we have all mandatory defines @@ -396,6 +430,16 @@ # error Missing definition of ERTS_RBT_IS_EQ #endif +#undef ERTS_RBT_IS_GT__ +#ifdef ERTS_RBT_CMP_KEYS +# define ERTS_RBT_IS_GT__(KX, KY) \ + (ERTS_RBT_CMP_KEYS((KX), (KY)) > 0) +#else +# define ERTS_RBT_IS_GT__(KX, KY) \ + (!ERTS_RBT_IS_LT((KX), (KY)) && !ERTS_RBT_IS_EQ((KX), (KY))) + +#endif + #if defined(ERTS_RBT_HARD_DEBUG) || defined(DEBUG) # ifndef ERTS_RBT_DEBUG # define ERTS_RBT_DEBUG 1 @@ -422,17 +466,6 @@ # define ERTS_RBT_API_INLINE__ ERTS_INLINE #endif -#ifndef ERTS_RBT_YIELD_STAT_INITER -# define ERTS_RBT_YIELD_STAT_INITER {NULL, 0} -#endif -#ifndef ERTS_RBT_YIELD_STAT_INIT -# define ERTS_RBT_YIELD_STAT_INIT(YS) \ - do { \ - (YS)->x = NULL; \ - (YS)->up = 0; \ - } while (0) -#endif - #define ERTS_RBT_CONCAT_MACRO_VALUES___(X, Y) \ X ## Y #define ERTS_RBT_CONCAT_MACRO_VALUES__(X, Y) \ @@ -445,8 +478,38 @@ typedef struct { ERTS_RBT_T *x; int up; +#ifdef DEBUG + int debug_red_adj; +#endif } ERTS_RBT_YIELD_STATE_T__; +#define ERTS_RBT_CALLBACK_FOREACH_FUNC(NAME) int (*NAME)(ERTS_RBT_T *, void *, Sint) + +#ifndef ERTS_RBT_YIELD_STAT_INITER +# ifdef DEBUG +# define ERTS_RBT_YIELD_STAT_INITER {NULL, 0, CONTEXT_REDS} +# else +# define ERTS_RBT_YIELD_STAT_INITER {NULL, 0} +# endif +#endif +#ifndef ERTS_RBT_YIELD_STAT_INIT +# define ERTS_RBT_YIELD_STAT_INIT__(YS) \ + do { \ + (YS)->x = NULL; \ + (YS)->up = 0; \ + } while (0) +# ifdef DEBUG +# define ERTS_RBT_YIELD_STAT_INIT(YS) \ + do { \ + ERTS_RBT_YIELD_STAT_INIT__(YS); \ + (YS)->debug_red_adj = CONTEXT_REDS; \ + } while(0) +# else +# define ERTS_RBT_YIELD_STAT_INIT(YS) ERTS_RBT_YIELD_STAT_INIT__(YS) +# endif +#endif + + #define ERTS_RBT_FUNC__(Name) \ ERTS_RBT_CONCAT_MACRO_VALUES__(ERTS_RBT_PREFIX, _rbt_ ## Name) @@ -1007,19 +1070,30 @@ ERTS_RBT_FUNC__(insert_aux__)(ERTS_RBT_T **root, ERTS_RBT_T *n, int lookup) ERTS_RBT_T *p, *x = *root; while (1) { - ERTS_RBT_KEY_T kx; + ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x); ERTS_RBT_T *c; + int kres; +#ifdef ERTS_RBT_CMP_KEYS + int kcmp = ERTS_RBT_CMP_KEYS(kn, kx); + kres = kcmp == 0; +#else + kres = ERTS_RBT_IS_EQ(kn, kx); +#endif - kx = ERTS_RBT_GET_KEY(x); - - if (lookup && ERTS_RBT_IS_EQ(kn, kx)) { + if (lookup && kres) { ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL); return x; } - if (ERTS_RBT_IS_LT(kn, kx)) { +#ifdef ERTS_RBT_CMP_KEYS + kres = kcmp < 0; +#else + kres = ERTS_RBT_IS_LT(kn, kx); +#endif + + if (kres) { c = ERTS_RBT_GET_LEFT(x); if (!c) { ERTS_RBT_SET_PARENT(n, x); @@ -1075,6 +1149,101 @@ ERTS_RBT_FUNC__(insert)(ERTS_RBT_T **root, ERTS_RBT_T *n) #endif /* ERTS_RBT_WANT_INSERT */ +#ifdef ERTS_RBT_WANT_LOOKUP_CREATE +static ERTS_INLINE ERTS_RBT_T * +ERTS_RBT_FUNC__(lookup_create)(ERTS_RBT_T **root, + ERTS_RBT_KEY_T kn, + ERTS_RBT_T *(*create)(ERTS_RBT_KEY_T, void *), + void *arg, + int *created) +{ + ERTS_RBT_T *n; + ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL); + + if (!*root) { + n = (*create)(kn, arg); + ERTS_RBT_INIT_EMPTY_TNODE(n); + ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn)); + ERTS_RBT_SET_BLACK(n); + *root = n; + *created = !0; +#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT + ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(NULL, n); +#endif + } + else { + ERTS_RBT_T *p, *x = *root; + + while (1) { + ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x); + ERTS_RBT_T *c; + int kres; +#ifdef ERTS_RBT_CMP_KEYS + int kcmp = ERTS_RBT_CMP_KEYS(kn, kx); + kres = kcmp == 0; +#else + kres = ERTS_RBT_IS_EQ(kn, kx); +#endif + + if (kres) { + + ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL); + + *created = 0; + return x; + } + +#ifdef ERTS_RBT_CMP_KEYS + kres = kcmp < 0; +#else + kres = ERTS_RBT_IS_LT(kn, kx); +#endif + + if (kres) { + c = ERTS_RBT_GET_LEFT(x); + if (!c) { + n = (*create)(kn, arg); + ERTS_RBT_INIT_EMPTY_TNODE(n); + ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn)); + *created = !0; + ERTS_RBT_SET_PARENT(n, x); + ERTS_RBT_SET_LEFT(x, n); + p = x; + break; + } + } + else { + c = ERTS_RBT_GET_RIGHT(x); + if (!c) { + n = (*create)(kn, arg); + ERTS_RBT_INIT_EMPTY_TNODE(n); + ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn)); + *created = !0; + ERTS_RBT_SET_PARENT(n, x); + ERTS_RBT_SET_RIGHT(x, n); + p = x; + break; + } + } + + x = c; + } + + ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn)); + ERTS_RBT_ASSERT(p); + + ERTS_RBT_SET_RED(n); + if (ERTS_RBT_IS_RED(p)) + ERTS_RBT_FUNC__(insert_fixup__)(root, n); + } + + ERTS_RBT_HDBG_CHECK_TREE__(*root, n); + + return n; +} + +#endif /* ERTS_RBT_WANT_LOOKUP_CREATE */ + #ifdef ERTS_RBT_WANT_LOOKUP static ERTS_RBT_API_INLINE__ ERTS_RBT_T * @@ -1088,11 +1257,24 @@ ERTS_RBT_FUNC__(lookup)(ERTS_RBT_T *root, ERTS_RBT_KEY_T key) while (1) { ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x); ERTS_RBT_T *c; + int kres; +#ifdef ERTS_RBT_CMP_KEYS + int kcmp = ERTS_RBT_CMP_KEYS(key, kx); + kres = kcmp == 0; +#else + kres = ERTS_RBT_IS_EQ(key, kx); +#endif - if (ERTS_RBT_IS_EQ(key, kx)) + if (kres) return x; - if (ERTS_RBT_IS_LT(key, kx)) { +#ifdef ERTS_RBT_CMP_KEYS + kres = kcmp < 0; +#else + kres = ERTS_RBT_IS_LT(key, kx); +#endif + + if (kres) { c = ERTS_RBT_GET_LEFT(x); if (!c) return NULL; @@ -1158,11 +1340,11 @@ ERTS_RBT_FUNC__(largest)(ERTS_RBT_T *root) static ERTS_INLINE int ERTS_RBT_FUNC__(foreach_unordered__)(ERTS_RBT_T **root, int destroying, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg, - int yielding, + int yielding, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { ERTS_RBT_T *c, *p, *x; @@ -1170,13 +1352,17 @@ ERTS_RBT_FUNC__(foreach_unordered__)(ERTS_RBT_T **root, if (yielding && ystate->x) { x = ystate->x; +#ifdef DEBUG + if (ystate->debug_red_adj > 0) + ystate->debug_red_adj -= 100; +#endif ERTS_RBT_ASSERT(ystate->up); goto restart_up; } else { x = *root; if (!x) - return 0; + return reds; if (destroying) *root = NULL; } @@ -1202,10 +1388,10 @@ ERTS_RBT_FUNC__(foreach_unordered__)(ERTS_RBT_T **root, #ifdef ERTS_RBT_DEBUG int cdir; #endif - if (yielding && ylimit-- <= 0) { + if (yielding && reds <= 0) { ystate->x = x; ystate->up = 1; - return 1; + return 0; } restart_up: @@ -1231,14 +1417,20 @@ ERTS_RBT_FUNC__(foreach_unordered__)(ERTS_RBT_T **root, } #endif - (*op)(x, arg); + reds -= (*op)(x, arg, reds); +#ifdef DEBUG + if (yielding) + reds -= ystate->debug_red_adj; +#endif if (!p) { + /* Done */ if (yielding) { ystate->x = NULL; ystate->up = 0; + return reds <= 0 ? 1 : reds; } - return 0; /* Done */ + return 1; } c = ERTS_RBT_GET_RIGHT(p); @@ -1263,20 +1455,26 @@ static ERTS_INLINE int ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root, int from_small, int destroying, - void (*op)(ERTS_RBT_T *, void *), - void (*destroy)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), + ERTS_RBT_CALLBACK_FOREACH_FUNC(destroy), void *arg, - int yielding, + int yielding, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { ERTS_RBT_T *c, *p, *x; ERTS_RBT_ASSERT(!yielding || ystate); ERTS_RBT_ASSERT(!destroying || destroy); + ERTS_RBT_ASSERT(!yielding || yop); + ERTS_RBT_ASSERT(yielding || op); if (yielding && ystate->x) { x = ystate->x; +#ifdef DEBUG + if (ystate->debug_red_adj > 0) + ystate->debug_red_adj -= 100; +#endif if (ystate->up) goto restart_up; else @@ -1285,7 +1483,7 @@ ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root, else { x = *root; if (!x) - return 0; + return reds; if (destroying) *root = NULL; } @@ -1301,12 +1499,16 @@ ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root, x = c; } - (*op)(x, arg); + reds -= (*op)(x, arg, reds); +#ifdef DEBUG + if (yielding) + reds -= ystate->debug_red_adj; +#endif - if (yielding && --ylimit <= 0) { + if (yielding && reds <= 0) { ystate->x = x; ystate->up = 0; - return 1; + return 0; } restart_down: @@ -1328,12 +1530,16 @@ ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root, ? ERTS_RBT_GET_LEFT(p) : ERTS_RBT_GET_RIGHT(p)) == x); - (*op)(p, arg); + reds -= (*op)(p, arg, reds); +#ifdef DEBUG + if (yielding) + reds -= ystate->debug_red_adj; +#endif - if (yielding && --ylimit <= 0) { + if (yielding && reds <= 0) { ystate->x = x; ystate->up = 1; - return 1; + return 0; restart_up: p = ERTS_RBT_GET_PARENT(x); } @@ -1366,15 +1572,20 @@ ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root, } #endif - (*destroy)(x, arg); + reds -= (*destroy)(x, arg, reds); +#ifdef DEBUG + if (yielding) + reds -= ystate->debug_red_adj; +#endif } if (!p) { if (yielding) { ystate->x = NULL; ystate->up = 0; + return reds <= 0 ? 1 : reds; } - return 0; /* Done */ + return 1; /* Done */ } x = p; } @@ -1387,7 +1598,7 @@ ERTS_RBT_FUNC__(foreach_ordered__)(ERTS_RBT_T **root, static ERTS_RBT_API_INLINE__ void ERTS_RBT_FUNC__(foreach)(ERTS_RBT_T *root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg) { (void) ERTS_RBT_FUNC__(foreach_unordered__)(&root, 0, op, arg, @@ -1400,7 +1611,7 @@ ERTS_RBT_FUNC__(foreach)(ERTS_RBT_T *root, static ERTS_RBT_API_INLINE__ void ERTS_RBT_FUNC__(foreach_small)(ERTS_RBT_T *root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg) { (void) ERTS_RBT_FUNC__(foreach_ordered__)(&root, 1, 0, @@ -1414,7 +1625,7 @@ ERTS_RBT_FUNC__(foreach_small)(ERTS_RBT_T *root, static ERTS_RBT_API_INLINE__ void ERTS_RBT_FUNC__(foreach_large)(ERTS_RBT_T *root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg) { (void) ERTS_RBT_FUNC__(foreach_ordered__)(&root, 0, 0, @@ -1426,15 +1637,15 @@ ERTS_RBT_FUNC__(foreach_large)(ERTS_RBT_T *root, #ifdef ERTS_RBT_WANT_FOREACH_YIELDING -static ERTS_RBT_API_INLINE__ void +static ERTS_RBT_API_INLINE__ int ERTS_RBT_FUNC__(foreach_yielding)(ERTS_RBT_T *root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { - (void) ERTS_RBT_FUNC__(foreach_unordered__)(*root, 0, op, arg, - 1, ystate, ylimit); + return ERTS_RBT_FUNC__(foreach_unordered__)(&root, 0, op, arg, + 1, ystate, reds); } #endif /* ERTS_RBT_WANT_FOREACH_YIELDING */ @@ -1443,14 +1654,14 @@ ERTS_RBT_FUNC__(foreach_yielding)(ERTS_RBT_T *root, static ERTS_RBT_API_INLINE__ int ERTS_RBT_FUNC__(foreach_small_yielding)(ERTS_RBT_T *root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { return ERTS_RBT_FUNC__(foreach_ordered__)(&root, 1, 0, op, NULL, arg, - 1, ystate, ylimit); + 1, ystate, reds); } #endif /* ERTS_RBT_WANT_FOREACH_SMALL_YIELDING */ @@ -1459,14 +1670,14 @@ ERTS_RBT_FUNC__(foreach_small_yielding)(ERTS_RBT_T *root, static ERTS_RBT_API_INLINE__ int ERTS_RBT_FUNC__(foreach_large_yielding)(ERTS_RBT_T *root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { return ERTS_RBT_FUNC__(foreach_ordered__)(&root, 0, 0, op, NULL, arg, - 1, ystate, ylimit); + 1, ystate, reds); } #endif /* ERTS_RBT_WANT_FOREACH_LARGE_YIELDING */ @@ -1475,11 +1686,11 @@ ERTS_RBT_FUNC__(foreach_large_yielding)(ERTS_RBT_T *root, static ERTS_RBT_API_INLINE__ void ERTS_RBT_FUNC__(foreach_destroy)(ERTS_RBT_T **root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg) { (void) ERTS_RBT_FUNC__(foreach_unordered__)(root, 1, op, arg, - 0, NULL, 0); + 0, NULL, 0); } #endif /* ERTS_RBT_WANT_FOREACH_DESTROY */ @@ -1488,8 +1699,8 @@ ERTS_RBT_FUNC__(foreach_destroy)(ERTS_RBT_T **root, static ERTS_RBT_API_INLINE__ void ERTS_RBT_FUNC__(foreach_small_destroy)(ERTS_RBT_T **root, - void (*op)(ERTS_RBT_T *, void *), - void (*destr)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), + ERTS_RBT_CALLBACK_FOREACH_FUNC(destr), void *arg) { (void) ERTS_RBT_FUNC__(foreach_ordered__)(root, 1, 1, @@ -1503,8 +1714,8 @@ ERTS_RBT_FUNC__(foreach_small_destroy)(ERTS_RBT_T **root, static ERTS_RBT_API_INLINE__ void ERTS_RBT_FUNC__(foreach_large_destroy)(ERTS_RBT_T **root, - void (*op)(ERTS_RBT_T *, void *), - void (*destr)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), + ERTS_RBT_CALLBACK_FOREACH_FUNC(destr), void *arg) { (void) ERTS_RBT_FUNC__(foreach_ordered__)(root, 0, 1, @@ -1518,13 +1729,13 @@ ERTS_RBT_FUNC__(foreach_large_destroy)(ERTS_RBT_T **root, static ERTS_RBT_API_INLINE__ int ERTS_RBT_FUNC__(foreach_destroy_yielding)(ERTS_RBT_T **root, - void (*op)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), void *arg, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { return ERTS_RBT_FUNC__(foreach_unordered__)(root, 1, op, arg, - 1, ystate, ylimit); + 1, ystate, reds); } #endif /* ERTS_RBT_WANT_FOREACH_DESTROY_YIELDING */ @@ -1533,15 +1744,15 @@ ERTS_RBT_FUNC__(foreach_destroy_yielding)(ERTS_RBT_T **root, static ERTS_RBT_API_INLINE__ int ERTS_RBT_FUNC__(foreach_small_destroy_yielding)(ERTS_RBT_T **root, - void (*op)(ERTS_RBT_T *, void *), - void (*destr)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), + ERTS_RBT_CALLBACK_FOREACH_FUNC(destr), void *arg, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { return ERTS_RBT_FUNC__(foreach_ordered__)(root, 1, 1, op, destr, arg, - 1, ystate, ylimit); + 1, ystate, reds); } #endif /* ERTS_RBT_WANT_FOREACH_SMALL_DESTROY_YIELDING */ @@ -1550,15 +1761,15 @@ ERTS_RBT_FUNC__(foreach_small_destroy_yielding)(ERTS_RBT_T **root, static ERTS_RBT_API_INLINE__ int ERTS_RBT_FUNC__(foreach_large_destroy_yielding)(ERTS_RBT_T **root, - void (*op)(ERTS_RBT_T *, void *), - void (*destr)(ERTS_RBT_T *, void *), + ERTS_RBT_CALLBACK_FOREACH_FUNC(op), + ERTS_RBT_CALLBACK_FOREACH_FUNC(destr), void *arg, ERTS_RBT_YIELD_STATE_T__ *ystate, - Sint ylimit) + Sint reds) { return ERTS_RBT_FUNC__(foreach_ordered__)(root, 0, 1, op, destr, arg, - 1, ystate, ylimit); + 1, ystate, reds); } #endif /* ERTS_RBT_WANT_FOREACH_LARGE_DESTROY_YIELDING */ @@ -1630,8 +1841,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n) kx = ERTS_RBT_GET_KEY(x); kc = ERTS_RBT_GET_KEY(c); - ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kc, kx) - || ERTS_RBT_IS_EQ(kc, kx)); + ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kc, kx)); x = c; } @@ -1649,8 +1859,8 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n) kx = ERTS_RBT_GET_KEY(x); kc = ERTS_RBT_GET_KEY(c); - ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kx, kc) - || ERTS_RBT_IS_EQ(kx, kc)); + ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kx, kc)); + x = c; } @@ -1672,8 +1882,8 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n) kx = ERTS_RBT_GET_KEY(x); kc = ERTS_RBT_GET_KEY(c); - ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kx, kc) - || ERTS_RBT_IS_EQ(kx, kc)); + ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kx, kc)); + /* Go down tree of x's sibling... */ x = c; break; @@ -1707,10 +1917,12 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n) #undef ERTS_RBT_NEED_FOREACH_ORDERED__ #undef ERTS_RBT_NEED_HDBG_CHECK_TREE__ #undef ERTS_RBT_HDBG_CHECK_TREE__ +#undef ERTS_RBT_IS_GT__ #ifdef ERTS_RBT_UNDEF # undef ERTS_RBT_PREFIX # undef ERTS_RBT_T +# undef ERTS_RBT_CALLBACK_FOREACH_FUNC # undef ERTS_RBT_KEY_T # undef ERTS_RBT_FLAGS_T # undef ERTS_RBT_INIT_EMPTY_TNODE @@ -1727,6 +1939,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n) # undef ERTS_RBT_GET_LEFT # undef ERTS_RBT_SET_LEFT # undef ERTS_RBT_GET_KEY +# undef ERTS_RBT_CMP_KEYS # undef ERTS_RBT_IS_LT # undef ERTS_RBT_IS_EQ # undef ERTS_RBT_UNDEF |