diff options
Diffstat (limited to 'erts/emulator/test/alloc_SUITE_data/rbtree.c')
-rw-r--r-- | erts/emulator/test/alloc_SUITE_data/rbtree.c | 125 |
1 files changed, 68 insertions, 57 deletions
diff --git a/erts/emulator/test/alloc_SUITE_data/rbtree.c b/erts/emulator/test/alloc_SUITE_data/rbtree.c index 702f075304..38bbbdf90c 100644 --- a/erts/emulator/test/alloc_SUITE_data/rbtree.c +++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c @@ -1,13 +1,14 @@ -/* ``The contents of this file are subject to the Erlang Public License, - * Version 1.1, (the "License"); you may not use this file except in - * compliance with the License. You should have received a copy of the - * Erlang Public License along with this software. If not, it can be - * retrieved via the world wide web at http://www.erlang.org/. - * - * Software distributed under the License is distributed on an "AS IS" - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See - * the License for the specific language governing rights and limitations - * under the License. +/* ``Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. * * The Initial Developer of the Original Code is Ericsson Utvecklings AB. * Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings @@ -19,7 +20,7 @@ #include "testcase_driver.h" #include "allocator_test.h" -#define NO_BLOCKS 100000 +int NO_BLOCKS; #define RIGHT_VISITED (1 << 0) #define LEFT_VISITED (1 << 1) @@ -85,23 +86,21 @@ print_tree(TestCaseState_t *tcs, RBT_t *root) static RBT_t * check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) { - enum { BF, AOBF, AOFF, AOFFCAOBF }type; + enum { BF, AOBF, AOFF } type; int i, max_i; char stk[128]; RBT_t *root, *x, *y, *res; Ulong x_sz, y_sz, is_x_black; long blacks, curr_blacks; + int have_max_sz; res = NULL; - if (IS_BF_ALGO(alc)) { - if (IS_AOBF(alc)) type = AOBF; - else type = BF; - } - else { /* AOFF_ALGO */ - if (IS_CBF(alc)) type = AOFFCAOBF; - else type = AOFF; - } + if (IS_AOBF(alc)) type = AOBF; + else if (IS_BF(alc)) type = BF; + else type = AOFF; + + have_max_sz = !IS_BF_ALGO(alc); root = RBT_ROOT(alc, size); @@ -191,17 +190,10 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) break; case AOFF: ASSERT(tcs, y < x); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); break; - case AOFFCAOBF: - { - void* x_crr = BLK_TO_MBC(x); - void* y_crr = BLK_TO_MBC(y); - ASSERT(tcs, (y < x && (x_crr != y_crr || x_sz == y_sz)) - || (y_sz < x_sz && x_crr == y_crr)); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); - break; - } + } + if (have_max_sz) { + ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); } } @@ -219,27 +211,22 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) break; case AOFF: ASSERT(tcs, y > x); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); break; - case AOFFCAOBF: - { - void* x_crr = BLK_TO_MBC(x); - void* y_crr = BLK_TO_MBC(y); - ASSERT(tcs, (y > x && (x_crr != y_crr || x_sz == y_sz)) - || (y_sz > x_sz && x_crr == y_crr)); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); - break; - } + } + if (have_max_sz) { + ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); } } if (type == BF) { Ulong l_sz; - RBTL_t *l = RBT_NEXT(x); + RBTL_t *l, *prev=x; for (l = RBT_NEXT(x); l; l = RBT_NEXT(l)) { l_sz = BLK_SZ(l); ASSERT(tcs, l_sz == x_sz); ASSERT(tcs, !RBT_IS_TREE(l)); + ASSERT(tcs, RBT_PREV(l) == prev); + prev = l; } } @@ -262,18 +249,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) res = x; } break; - case AOFFCAOBF: - if (BLK_TO_MBC(x) != BLK_TO_MBC(res) || x_sz == y_sz) { - if (x < res) { - res = x; - } - } - else if (x_sz < y_sz) { - res = x; - } - break; } - } } @@ -289,9 +265,10 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) ASSERT(tcs, curr_blacks == 0); ASSERT(tcs, i == -1); + /* testcase_printf(tcs, "Red-Black Tree OK! Max depth = %d; " "Black depth = %d\n", max_i+1, blacks < 0 ? 0 : blacks); - + */ return res; } @@ -310,7 +287,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size, int ignore_null) tmp = ALLOC(a, sz - ABLK_HDR_SZ); ASSERT(tcs, tmp); y = UMEM2BLK(tmp); - if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) { + if (!IS_BF(a)) { ASSERT(tcs, x == y); } else { @@ -488,9 +465,16 @@ testcase_run(TestCaseState_t *tcs) char *argv2[] = {"-tasaobf", NULL}; char *argv3[] = {"-tasaoff", NULL}; char *argv4[] = {"-tasaoffcaobf", NULL}; + char *argv5[] = {"-tasaoffcbf", NULL}; Allctr_t *a; rbtree_test_data *td; + NO_BLOCKS = 100*1000; + if (enif_is_identical(tcs->build_type, + enif_make_atom(tcs->curr_env,"valgrind"))) { + NO_BLOCKS /= 10; + } + /* Best fit... */ testcase_printf(tcs, "Setup...\n"); @@ -511,6 +495,7 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, IS_BF_ALGO(a)); ASSERT(tcs, !IS_AOBF(a)); + ASSERT(tcs, IS_BF(a)); test_it(tcs); @@ -529,6 +514,7 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, IS_BF_ALGO(a)); ASSERT(tcs, IS_AOBF(a)); + ASSERT(tcs, !IS_BF(a)); test_it(tcs); @@ -546,7 +532,8 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, !IS_BF_ALGO(a)); - ASSERT(tcs, !IS_CBF(a)); + ASSERT(tcs, !IS_AOBF(a)); + ASSERT(tcs, !IS_BF(a)); test_it(tcs); test_carrier_migration(tcs); @@ -556,7 +543,7 @@ testcase_run(TestCaseState_t *tcs) testcase_printf(tcs, "Address order first fit test succeeded!\n"); - /* Address order first fit, best fit within carrier */ + /* Address order first fit, aobf within carrier */ testcase_printf(tcs, "Starting test of aoffcaobf...\n"); @@ -565,7 +552,28 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, !IS_BF_ALGO(a)); - ASSERT(tcs, IS_CBF(a)); + ASSERT(tcs, IS_AOBF(a)); + ASSERT(tcs, !IS_BF(a)); + + test_it(tcs); + test_carrier_migration(tcs); + + STOP_ALC(a); + td->allocator = NULL; + + testcase_printf(tcs, "aoffcaobf test succeeded!\n"); + + /* Address order first fit, bf within carrier */ + + testcase_printf(tcs, "Starting test of aoffcbf...\n"); + + current_rbt_type_op_base = AO_FIRSTFIT_OP_BASE; + td->allocator = a = START_ALC("rbtree_aoffcbf_", 0, argv5); + + ASSERT(tcs, a); + ASSERT(tcs, !IS_BF_ALGO(a)); + ASSERT(tcs, !IS_AOBF(a)); + ASSERT(tcs, IS_BF(a)); test_it(tcs); test_carrier_migration(tcs); @@ -576,3 +584,6 @@ testcase_run(TestCaseState_t *tcs) testcase_printf(tcs, "aoffcaobf test succeeded!\n"); } + +ERL_NIF_INIT(rbtree, testcase_nif_funcs, testcase_nif_init, + NULL, NULL, NULL); |