aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/test/alloc_SUITE_data/rbtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/test/alloc_SUITE_data/rbtree.c')
-rw-r--r--erts/emulator/test/alloc_SUITE_data/rbtree.c125
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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-26 19:33:11 +0000