[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
master fd3f51b7c3: Fix manual noverlay tests
|
From: |
Basil L. Contovounesios |
|
Subject: |
master fd3f51b7c3: Fix manual noverlay tests |
|
Date: |
Fri, 4 Nov 2022 08:08:08 -0400 (EDT) |
branch: master
commit fd3f51b7c3a6649ee3db12d33b056b1afdbfa7e9
Author: Basil L. Contovounesios <contovob@tcd.ie>
Commit: Basil L. Contovounesios <contovob@tcd.ie>
Fix manual noverlay tests
* test/manual/noverlay/Makefile.in: Add copyright notice.
(LIBS): Rename...
(PACKAGES): ...to this, to avoid confusion with Autoconf's LIBS.
All uses changed.
(CFLAGS): Break out -I flag...
(CPPFLAGS): ...into this new variable.
(LDFLAGS): Rename...
(LDLIBS): ...to this, which is expected to hold -l flags.
(top_builddir): New variable.
(EMACS): Define in terms of it.
(.PHONY): Add clean, distclean, and perf targets.
(have-libcheck): Remove redundant target. All uses updated.
(itree-tests.o): Remove redundant dependency on its source file.
(itree-tests): Remove redundant (and uncompilable) rule.
* test/manual/noverlay/check-sanitize.sh: Use /usr/bin/env. Add
copyright notice. Enable pipefail option, to propagate itree-tests
exit status to caller. Fix typo in usage message. Strip less
information from Check's error messages.
* test/manual/noverlay/emacs-compat.h: Add copyright notice.
Include stdlib.h.
(emacs_abort, eassert): Consistently use EXIT_FAILURE.
(eassume): Define when necessary.
* test/manual/noverlay/itree-tests.c: Add copyright notice. Include
standard headers before third-party ones. Use most narrowly
applicable ck_assert* macro for the types being checked,
e.g. ck_assert_ptr_* macros for pointer values. Replace removed
names and APIs with current ones, e.g. the itree_node field 'color'
is now called 'red'. Ensure preconditions of itree API are
satisfied before use, e.g. itree_node otick being set appropriately
before insertion, or global iterator being initialized
before (implicit) use (bug#58976). Make all functions static.
(DEF_TEST_SETUP): Remove all instances, replacing with...
(test_insert1_setup, test_insert2_setup, test_remove1_setup)
(test_remove2_setup): ...these new test fixtures.
(A, B, C, D, E, N_05, N_10, N_15, N_20, N_30, N_40, N_50, N_70)
(N_80, N_90, N_85, N_95): Define as static variables rather than
macros.
(test_get_tree4): Remove, inlining salient parts.
(shuffle): Move closer to users.
(test_create_tree): Accept itree_nodes as argument instead of
dynamically allocating them. All callers changed.
(FOREACH): Remove unused macro.
(N_BEG, N_END): Define in terms of itree_node_begin and
itree_node_end, respectively.
(test_gap_insert_1, test_gap_insert_2, test_gap_insert_3)
(test_gap_insert_5, test_gap_insert_7, test_gap_insert_11): Use
test_setup_gap_node_noadvance.
(basic_suite): Group unit tests into test cases and fixtures. Run
previously forgotten test_insert_14.
(main): Run suite as CK_ENV to allow specifying desired verbosity in
the environment.
---
test/manual/noverlay/Makefile.in | 41 +-
test/manual/noverlay/check-sanitize.sh | 28 +-
test/manual/noverlay/emacs-compat.h | 36 +-
test/manual/noverlay/itree-tests.c | 1284 +++++++++++++++-----------------
4 files changed, 679 insertions(+), 710 deletions(-)
diff --git a/test/manual/noverlay/Makefile.in b/test/manual/noverlay/Makefile.in
index beef1dbc09..3c8dba1ce1 100644
--- a/test/manual/noverlay/Makefile.in
+++ b/test/manual/noverlay/Makefile.in
@@ -1,26 +1,41 @@
+### @configure_input@
+
+# Copyright (C) 2017-2022 Free Software Foundation, Inc.
+
+# This file is part of GNU Emacs.
+
+# GNU Emacs is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+
+# GNU Emacs is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
+
PROGRAM = itree-tests
-LIBS = check
+PACKAGES = check
top_srcdir = @top_srcdir@
-CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(LIBS)) -I $(top_srcdir)/src
-LDFLAGS += $(shell pkg-config --libs $(LIBS)) -lm
+top_builddir = @top_builddir@
+CPPFLAGS += -I $(top_srcdir)/src
+CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(PACKAGES))
+LDLIBS += $(shell pkg-config --libs $(PACKAGES)) -lm
OBJECTS = itree-tests.o
CC = gcc
-EMACS ?= ../../../src/emacs
+EMACS ?= $(top_builddir)/src/emacs
-.PHONY: all check have-libcheck
+.PHONY: all check clean distclean perf
all: check
-have-libcheck:
- pkg-config --cflags $(LIBS)
-
-check: have-libcheck $(PROGRAM)
+check: $(PROGRAM)
./check-sanitize.sh ./$(PROGRAM)
-itree-tests.o: emacs-compat.h itree-tests.c $(top_srcdir)/src/itree.c
$(top_srcdir)/src/itree.h
-
-$(PROGRAM): $(OBJECTS)
- $(CC) $(CFLAGS) $(LDFLAGS) $(OBJECTS) -o $(PROGRAM)
+itree-tests.o: emacs-compat.h $(top_srcdir)/src/itree.c
$(top_srcdir)/src/itree.h
perf:
-$(EMACS) -Q -l ./overlay-perf.el -f perf-run-batch
diff --git a/test/manual/noverlay/check-sanitize.sh
b/test/manual/noverlay/check-sanitize.sh
index 03eedce8a6..9a67818dc8 100755
--- a/test/manual/noverlay/check-sanitize.sh
+++ b/test/manual/noverlay/check-sanitize.sh
@@ -1,11 +1,33 @@
-#!/bin/bash
+#!/usr/bin/env bash
+### check-sanitize.sh - strip confusing parts of Check error output
+
+## Copyright (C) 2017-2022 Free Software Foundation, Inc.
+
+## This file is part of GNU Emacs.
+
+## GNU Emacs is free software: you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation, either version 3 of the License, or
+## (at your option) any later version.
+
+## GNU Emacs is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+## GNU General Public License for more details.
+
+## You should have received a copy of the GNU General Public License
+## along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
+
+set -o pipefail
prog=$1
shift
[ -z "$prog" ] && {
- echo "usage:$(basename $0) CHECK_PRGOGRAM";
+ echo "usage:$(basename $0) CHECK_PROGRAM";
exit 1;
}
-"$prog" "$@" | sed -e 's/^\([^:]\+\):\([0-9]\+\):[PFE]:[^:]*:\([^:]*\):[^:]*:
*\(.*\)/\1:\2:\3:\4/'
+# FIXME: This would be unnecessary if
+# compilation-error-regexp-alist-alist understood libcheck OOTB.
+"$prog" "$@" | sed -e
's/^\([^:]\+\):\([0-9]\+\):\([PFE]\):\([^:]*\):\([^:]*\):[^:]*:\(.*\)/\1:\2:\3:\4:\5:\6/'
diff --git a/test/manual/noverlay/emacs-compat.h
b/test/manual/noverlay/emacs-compat.h
index 812f8e48a3..d2448b12db 100644
--- a/test/manual/noverlay/emacs-compat.h
+++ b/test/manual/noverlay/emacs-compat.h
@@ -1,8 +1,28 @@
+/* Mock necessary parts of lisp.h.
+
+Copyright (C) 2017-2022 Free Software Foundation, Inc.
+
+This file is part of GNU Emacs.
+
+GNU Emacs is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or (at
+your option) any later version.
+
+GNU Emacs is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
+
#ifndef TEST_COMPAT_H
#define TEST_COMPAT_H
-#include <stdio.h>
#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
typedef int Lisp_Object;
@@ -28,20 +48,24 @@ void
emacs_abort ()
{
fprintf (stderr, "Aborting...\n");
- exit (1);
+ exit (EXIT_FAILURE);
}
#ifndef eassert
#define eassert(cond) \
do { \
if (! (cond)) { \
- fprintf (stderr, "\n%s:%d:eassert condition failed: %s\n", \
- __FILE__, __LINE__ ,#cond); \
- exit (1); \
+ fprintf (stderr, "%s:%d:eassert condition failed: %s\n", \
+ __FILE__, __LINE__ , # cond); \
+ exit (EXIT_FAILURE); \
} \
} while (0)
#endif
+#ifndef eassume
+#define eassume eassert
+#endif
+
#ifndef max
#define max(x,y) ((x) >= (y) ? (x) : (y))
#endif
@@ -49,4 +73,4 @@ emacs_abort ()
#define min(x,y) ((x) <= (y) ? (x) : (y))
#endif
-#endif
+#endif /* TEST_COMPAT_H */
diff --git a/test/manual/noverlay/itree-tests.c
b/test/manual/noverlay/itree-tests.c
index a318389213..278e65f9bf 100644
--- a/test/manual/noverlay/itree-tests.c
+++ b/test/manual/noverlay/itree-tests.c
@@ -1,7 +1,28 @@
+/* Test the interval data-structure in itree.c.
+
+Copyright (c) 2017-2022 Free Software Foundation, Inc.
+
+This file is part of GNU Emacs.
+
+GNU Emacs is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or (at
+your option) any later version.
+
+GNU Emacs is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
+
#include <config.h>
-#include <check.h>
-#include <stdlib.h>
+
#include <stdarg.h>
+#include <stdlib.h>
+
+#include <check.h>
#include "emacs-compat.h"
#define EMACS_LISP_H /* lisp.h inclusion guard */
@@ -9,7 +30,14 @@
#define ITREE_TESTING
#include "itree.c"
-/* Basic tests of the interval_tree data-structure. */
+/* Globals. */
+
+static struct itree_tree tree;
+static struct itree_node A, B, C, D, E;
+static struct itree_node N_05, N_10, N_15, N_20, N_30, N_40;
+static struct itree_node N_50, N_70, N_80, N_90, N_85, N_95;
+
+/* Basic tests of the itree_tree data-structure. */
/*
+===================================================================================+
* | Insert
@@ -17,25 +45,21 @@
/* The graphs below display the trees after each insertion (as they
should be). See the source code for the different cases
- applied. */
-
-#define N_50 (n[0])
-#define N_30 (n[1])
-#define N_20 (n[2])
-#define N_10 (n[3])
-#define N_15 (n[4])
-#define N_05 (n[5])
-
-#define DEF_TEST_SETUP() \
- struct interval_tree tree; \
- struct interval_node n[6]; \
- interval_tree_init (&tree); \
- const int values[] = {50, 30, 20, 10, 15, 5}; \
- for (int i = 0; i < 6; ++i) \
- { \
- n[i].begin = values[i]; \
- n[i].end = values[i]; \
+ applied. */
+
+static void
+test_insert1_setup (void)
+{
+ enum { N = 6 };
+ const int values[N] = {50, 30, 20, 10, 15, 5};
+ struct itree_node *nodes[N] = {&N_50, &N_30, &N_20, &N_10, &N_15, &N_05};
+ interval_tree_init (&tree);
+ for (int i = 0; i < N; ++i)
+ {
+ nodes[i]->begin = nodes[i]->end = values[i];
+ nodes[i]->otick = tree.otick;
}
+}
START_TEST (test_insert_1)
{
@@ -43,10 +67,9 @@ START_TEST (test_insert_1)
* [50]
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (&N_50 == tree.root);
+ ck_assert (! N_50.red);
+ ck_assert_ptr_eq (&N_50, tree.root);
}
END_TEST
@@ -58,17 +81,16 @@ START_TEST (test_insert_2)
* (30)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_30);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_RED);
- ck_assert (&N_50 == tree.root);
- ck_assert (N_30.parent == &N_50);
- ck_assert (N_50.left == &N_30);
- ck_assert (N_50.right == &tree.nil);
- ck_assert (N_30.left == &tree.nil);
- ck_assert (N_30.right == &tree.nil);
+ ck_assert (! N_50.red);
+ ck_assert (N_30.red);
+ ck_assert_ptr_eq (&N_50, tree.root);
+ ck_assert_ptr_eq (N_30.parent, &N_50);
+ ck_assert_ptr_eq (N_50.left, &N_30);
+ ck_assert_ptr_null (N_50.right);
+ ck_assert_ptr_null (N_30.left);
+ ck_assert_ptr_null (N_30.right);
}
END_TEST
@@ -80,20 +102,19 @@ START_TEST (test_insert_3)
* (20) (50)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_30);
interval_tree_insert (&tree, &N_20);
- ck_assert (N_50.color == ITREE_RED);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_20.color == ITREE_RED);
- ck_assert (&N_30 == tree.root);
- ck_assert (N_50.parent == &N_30);
- ck_assert (N_30.right == &N_50);
- ck_assert (N_30.left == &N_20);
- ck_assert (N_20.left == &tree.nil);
- ck_assert (N_20.right == &tree.nil);
- ck_assert (N_20.parent == &N_30);
+ ck_assert (N_50.red);
+ ck_assert (! N_30.red);
+ ck_assert (N_20.red);
+ ck_assert_ptr_eq (&N_30, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_30);
+ ck_assert_ptr_eq (N_30.right, &N_50);
+ ck_assert_ptr_eq (N_30.left, &N_20);
+ ck_assert_ptr_null (N_20.left);
+ ck_assert_ptr_null (N_20.right);
+ ck_assert_ptr_eq (N_20.parent, &N_30);
}
END_TEST
@@ -107,25 +128,24 @@ START_TEST (test_insert_4)
* (10)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_30);
interval_tree_insert (&tree, &N_20);
interval_tree_insert (&tree, &N_10);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_20.color == ITREE_BLACK);
- ck_assert (N_10.color == ITREE_RED);
- ck_assert (&N_30 == tree.root);
- ck_assert (N_50.parent == &N_30);
- ck_assert (N_30.right == &N_50);
- ck_assert (N_30.left == &N_20);
- ck_assert (N_20.left == &N_10);
- ck_assert (N_20.right == &tree.nil);
- ck_assert (N_20.parent == &N_30);
- ck_assert (N_10.parent == &N_20);
- ck_assert (N_20.left == &N_10);
- ck_assert (N_10.right == &tree.nil);
+ ck_assert (! N_50.red);
+ ck_assert (! N_30.red);
+ ck_assert (! N_20.red);
+ ck_assert (N_10.red);
+ ck_assert_ptr_eq (&N_30, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_30);
+ ck_assert_ptr_eq (N_30.right, &N_50);
+ ck_assert_ptr_eq (N_30.left, &N_20);
+ ck_assert_ptr_eq (N_20.left, &N_10);
+ ck_assert_ptr_null (N_20.right);
+ ck_assert_ptr_eq (N_20.parent, &N_30);
+ ck_assert_ptr_eq (N_10.parent, &N_20);
+ ck_assert_ptr_eq (N_20.left, &N_10);
+ ck_assert_ptr_null (N_10.right);
}
END_TEST
@@ -139,31 +159,29 @@ START_TEST (test_insert_5)
* (10) (20)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_30);
interval_tree_insert (&tree, &N_20);
interval_tree_insert (&tree, &N_10);
interval_tree_insert (&tree, &N_15);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_20.color == ITREE_RED);
- ck_assert (N_10.color == ITREE_RED);
- ck_assert (N_15.color == ITREE_BLACK);
- ck_assert (&N_30 == tree.root);
- ck_assert (N_50.parent == &N_30);
- ck_assert (N_30.right == &N_50);
- ck_assert (N_30.left == &N_15);
- ck_assert (N_20.left == &tree.nil);
- ck_assert (N_20.right == &tree.nil);
- ck_assert (N_20.parent == &N_15);
- ck_assert (N_10.parent == &N_15);
- ck_assert (N_20.left == &tree.nil);
- ck_assert (N_10.right == &tree.nil);
- ck_assert (N_15.right == &N_20);
- ck_assert (N_15.left == &N_10);
- ck_assert (N_15.parent == &N_30);
-
+ ck_assert (! N_50.red);
+ ck_assert (! N_30.red);
+ ck_assert (N_20.red);
+ ck_assert (N_10.red);
+ ck_assert (! N_15.red);
+ ck_assert_ptr_eq (&N_30, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_30);
+ ck_assert_ptr_eq (N_30.right, &N_50);
+ ck_assert_ptr_eq (N_30.left, &N_15);
+ ck_assert_ptr_null (N_20.left);
+ ck_assert_ptr_null (N_20.right);
+ ck_assert_ptr_eq (N_20.parent, &N_15);
+ ck_assert_ptr_eq (N_10.parent, &N_15);
+ ck_assert_ptr_null (N_20.left);
+ ck_assert_ptr_null (N_10.right);
+ ck_assert_ptr_eq (N_15.right, &N_20);
+ ck_assert_ptr_eq (N_15.left, &N_10);
+ ck_assert_ptr_eq (N_15.parent, &N_30);
}
END_TEST
@@ -179,67 +197,54 @@ START_TEST (test_insert_6)
* (5)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_30);
interval_tree_insert (&tree, &N_20);
interval_tree_insert (&tree, &N_10);
interval_tree_insert (&tree, &N_15);
interval_tree_insert (&tree, &N_05);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_20.color == ITREE_BLACK);
- ck_assert (N_10.color == ITREE_BLACK);
- ck_assert (N_15.color == ITREE_RED);
- ck_assert (N_05.color == ITREE_RED);
- ck_assert (&N_30 == tree.root);
- ck_assert (N_50.parent == &N_30);
- ck_assert (N_30.right == &N_50);
- ck_assert (N_30.left == &N_15);
- ck_assert (N_20.left == &tree.nil);
- ck_assert (N_20.right == &tree.nil);
- ck_assert (N_20.parent == &N_15);
- ck_assert (N_10.parent == &N_15);
- ck_assert (N_20.left == &tree.nil);
- ck_assert (N_10.right == &tree.nil);
- ck_assert (N_15.right == &N_20);
- ck_assert (N_15.left == &N_10);
- ck_assert (N_15.parent == &N_30);
- ck_assert (N_05.parent == &N_10);
- ck_assert (N_10.left == &N_05);
- ck_assert (N_05.right == &tree.nil);
+ ck_assert (! N_50.red);
+ ck_assert (! N_30.red);
+ ck_assert (! N_20.red);
+ ck_assert (! N_10.red);
+ ck_assert (N_15.red);
+ ck_assert (N_05.red);
+ ck_assert_ptr_eq (&N_30, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_30);
+ ck_assert_ptr_eq (N_30.right, &N_50);
+ ck_assert_ptr_eq (N_30.left, &N_15);
+ ck_assert_ptr_null (N_20.left);
+ ck_assert_ptr_null (N_20.right);
+ ck_assert_ptr_eq (N_20.parent, &N_15);
+ ck_assert_ptr_eq (N_10.parent, &N_15);
+ ck_assert_ptr_null (N_20.left);
+ ck_assert_ptr_null (N_10.right);
+ ck_assert_ptr_eq (N_15.right, &N_20);
+ ck_assert_ptr_eq (N_15.left, &N_10);
+ ck_assert_ptr_eq (N_15.parent, &N_30);
+ ck_assert_ptr_eq (N_05.parent, &N_10);
+ ck_assert_ptr_eq (N_10.left, &N_05);
+ ck_assert_ptr_null (N_05.right);
}
END_TEST
-#undef N_50
-#undef N_30
-#undef N_20
-#undef N_10
-#undef N_15
-#undef N_05
-#undef DEF_TEST_SETUP
-
/* These are the mirror cases to the above ones. */
-#define N_50 (n[0])
-#define N_70 (n[1])
-#define N_80 (n[2])
-#define N_90 (n[3])
-#define N_85 (n[4])
-#define N_95 (n[5])
-
-#define DEF_TEST_SETUP() \
- struct interval_tree tree; \
- struct interval_node n[6]; \
- interval_tree_init (&tree); \
- const int values[] = {50, 70, 80, 90, 85, 95}; \
- for (int i = 0; i < 6; ++i) \
- { \
- n[i].begin = values[i]; \
- n[i].end = values[i]; \
+static void
+test_insert2_setup (void)
+{
+ enum { N = 6 };
+ const int values[] = {50, 70, 80, 90, 85, 95};
+ struct itree_node *nodes[N] = {&N_50, &N_70, &N_80, &N_90, &N_85, &N_95};
+ interval_tree_init (&tree);
+ for (int i = 0; i < N; ++i)
+ {
+ nodes[i]->begin = nodes[i]->end = values[i];
+ nodes[i]->otick = tree.otick;
}
+}
START_TEST (test_insert_7)
{
@@ -247,10 +252,9 @@ START_TEST (test_insert_7)
* [50]
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (&N_50 == tree.root);
+ ck_assert (! N_50.red);
+ ck_assert_ptr_eq (&N_50, tree.root);
}
END_TEST
@@ -262,17 +266,16 @@ START_TEST (test_insert_8)
* (70)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_70);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_70.color == ITREE_RED);
- ck_assert (&N_50 == tree.root);
- ck_assert (N_70.parent == &N_50);
- ck_assert (N_50.right == &N_70);
- ck_assert (N_50.left == &tree.nil);
- ck_assert (N_70.right == &tree.nil);
- ck_assert (N_70.left == &tree.nil);
+ ck_assert (! N_50.red);
+ ck_assert (N_70.red);
+ ck_assert_ptr_eq (&N_50, tree.root);
+ ck_assert_ptr_eq (N_70.parent, &N_50);
+ ck_assert_ptr_eq (N_50.right, &N_70);
+ ck_assert_ptr_null (N_50.left);
+ ck_assert_ptr_null (N_70.right);
+ ck_assert_ptr_null (N_70.left);
}
END_TEST
@@ -284,20 +287,19 @@ START_TEST (test_insert_9)
* (50) (80)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_70);
interval_tree_insert (&tree, &N_80);
- ck_assert (N_50.color == ITREE_RED);
- ck_assert (N_70.color == ITREE_BLACK);
- ck_assert (N_80.color == ITREE_RED);
- ck_assert (&N_70 == tree.root);
- ck_assert (N_50.parent == &N_70);
- ck_assert (N_70.right == &N_80);
- ck_assert (N_70.left == &N_50);
- ck_assert (N_80.right == &tree.nil);
- ck_assert (N_80.left == &tree.nil);
- ck_assert (N_80.parent == &N_70);
+ ck_assert (N_50.red);
+ ck_assert (! N_70.red);
+ ck_assert (N_80.red);
+ ck_assert_ptr_eq (&N_70, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_70);
+ ck_assert_ptr_eq (N_70.right, &N_80);
+ ck_assert_ptr_eq (N_70.left, &N_50);
+ ck_assert_ptr_null (N_80.right);
+ ck_assert_ptr_null (N_80.left);
+ ck_assert_ptr_eq (N_80.parent, &N_70);
}
END_TEST
@@ -311,25 +313,24 @@ START_TEST (test_insert_10)
* (90)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_70);
interval_tree_insert (&tree, &N_80);
interval_tree_insert (&tree, &N_90);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_70.color == ITREE_BLACK);
- ck_assert (N_80.color == ITREE_BLACK);
- ck_assert (N_90.color == ITREE_RED);
- ck_assert (&N_70 == tree.root);
- ck_assert (N_50.parent == &N_70);
- ck_assert (N_70.right == &N_80);
- ck_assert (N_70.left == &N_50);
- ck_assert (N_80.right == &N_90);
- ck_assert (N_80.left == &tree.nil);
- ck_assert (N_80.parent == &N_70);
- ck_assert (N_90.parent == &N_80);
- ck_assert (N_80.right == &N_90);
- ck_assert (N_90.left == &tree.nil);
+ ck_assert (! N_50.red);
+ ck_assert (! N_70.red);
+ ck_assert (! N_80.red);
+ ck_assert (N_90.red);
+ ck_assert_ptr_eq (&N_70, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_70);
+ ck_assert_ptr_eq (N_70.right, &N_80);
+ ck_assert_ptr_eq (N_70.left, &N_50);
+ ck_assert_ptr_eq (N_80.right, &N_90);
+ ck_assert_ptr_null (N_80.left);
+ ck_assert_ptr_eq (N_80.parent, &N_70);
+ ck_assert_ptr_eq (N_90.parent, &N_80);
+ ck_assert_ptr_eq (N_80.right, &N_90);
+ ck_assert_ptr_null (N_90.left);
}
END_TEST
@@ -343,30 +344,29 @@ START_TEST (test_insert_11)
* (80) (90)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_70);
interval_tree_insert (&tree, &N_80);
interval_tree_insert (&tree, &N_90);
interval_tree_insert (&tree, &N_85);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_70.color == ITREE_BLACK);
- ck_assert (N_80.color == ITREE_RED);
- ck_assert (N_90.color == ITREE_RED);
- ck_assert (N_85.color == ITREE_BLACK);
- ck_assert (&N_70 == tree.root);
- ck_assert (N_50.parent == &N_70);
- ck_assert (N_70.right == &N_85);
- ck_assert (N_70.left == &N_50);
- ck_assert (N_80.right == &tree.nil);
- ck_assert (N_80.left == &tree.nil);
- ck_assert (N_80.parent == &N_85);
- ck_assert (N_90.parent == &N_85);
- ck_assert (N_80.right == &tree.nil);
- ck_assert (N_90.left == &tree.nil);
- ck_assert (N_85.right == &N_90);
- ck_assert (N_85.left == &N_80);
- ck_assert (N_85.parent == &N_70);
+ ck_assert (! N_50.red);
+ ck_assert (! N_70.red);
+ ck_assert (N_80.red);
+ ck_assert (N_90.red);
+ ck_assert (! N_85.red);
+ ck_assert_ptr_eq (&N_70, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_70);
+ ck_assert_ptr_eq (N_70.right, &N_85);
+ ck_assert_ptr_eq (N_70.left, &N_50);
+ ck_assert_ptr_null (N_80.right);
+ ck_assert_ptr_null (N_80.left);
+ ck_assert_ptr_eq (N_80.parent, &N_85);
+ ck_assert_ptr_eq (N_90.parent, &N_85);
+ ck_assert_ptr_null (N_80.right);
+ ck_assert_ptr_null (N_90.left);
+ ck_assert_ptr_eq (N_85.right, &N_90);
+ ck_assert_ptr_eq (N_85.left, &N_80);
+ ck_assert_ptr_eq (N_85.parent, &N_70);
}
END_TEST
@@ -383,139 +383,90 @@ START_TEST (test_insert_12)
* (95)
*/
- DEF_TEST_SETUP ();
interval_tree_insert (&tree, &N_50);
interval_tree_insert (&tree, &N_70);
interval_tree_insert (&tree, &N_80);
interval_tree_insert (&tree, &N_90);
interval_tree_insert (&tree, &N_85);
interval_tree_insert (&tree, &N_95);
- ck_assert (N_50.color == ITREE_BLACK);
- ck_assert (N_70.color == ITREE_BLACK);
- ck_assert (N_80.color == ITREE_BLACK);
- ck_assert (N_90.color == ITREE_BLACK);
- ck_assert (N_85.color == ITREE_RED);
- ck_assert (N_95.color == ITREE_RED);
- ck_assert (&N_70 == tree.root);
- ck_assert (N_50.parent == &N_70);
- ck_assert (N_70.right == &N_85);
- ck_assert (N_70.left == &N_50);
- ck_assert (N_80.right == &tree.nil);
- ck_assert (N_80.left == &tree.nil);
- ck_assert (N_80.parent == &N_85);
- ck_assert (N_90.parent == &N_85);
- ck_assert (N_80.right == &tree.nil);
- ck_assert (N_90.left == &tree.nil);
- ck_assert (N_85.right == &N_90);
- ck_assert (N_85.left == &N_80);
- ck_assert (N_85.parent == &N_70);
- ck_assert (N_95.parent == &N_90);
- ck_assert (N_90.right == &N_95);
- ck_assert (N_95.left == &tree.nil);
+ ck_assert (! N_50.red);
+ ck_assert (! N_70.red);
+ ck_assert (! N_80.red);
+ ck_assert (! N_90.red);
+ ck_assert (N_85.red);
+ ck_assert (N_95.red);
+ ck_assert_ptr_eq (&N_70, tree.root);
+ ck_assert_ptr_eq (N_50.parent, &N_70);
+ ck_assert_ptr_eq (N_70.right, &N_85);
+ ck_assert_ptr_eq (N_70.left, &N_50);
+ ck_assert_ptr_null (N_80.right);
+ ck_assert_ptr_null (N_80.left);
+ ck_assert_ptr_eq (N_80.parent, &N_85);
+ ck_assert_ptr_eq (N_90.parent, &N_85);
+ ck_assert_ptr_null (N_80.right);
+ ck_assert_ptr_null (N_90.left);
+ ck_assert_ptr_eq (N_85.right, &N_90);
+ ck_assert_ptr_eq (N_85.left, &N_80);
+ ck_assert_ptr_eq (N_85.parent, &N_70);
+ ck_assert_ptr_eq (N_95.parent, &N_90);
+ ck_assert_ptr_eq (N_90.right, &N_95);
+ ck_assert_ptr_null (N_95.left);
}
END_TEST
-#undef N_50
-#undef N_70
-#undef N_80
-#undef N_90
-#undef N_85
-#undef N_95
-#undef DEF_TEST_SETUP
-
-struct interval_tree*
-test_get_tree4 (struct interval_node **n)
-{
- static struct interval_tree tree;
- static struct interval_node nodes[4];
- memset (&tree, 0, sizeof (struct interval_tree));
- memset (&nodes, 0, 4 * sizeof (struct interval_node));
- interval_tree_init (&tree);
- for (int i = 0; i < 4; ++i)
- {
- nodes[i].begin = 10 * (i + 1);
- nodes[i].end = nodes[i].begin;
- interval_tree_insert (&tree, &nodes[i]);
- }
- *n = nodes;
- return &tree;
-}
-
-static void
-shuffle (int *index, int n)
-{
- for (int i = n - 1; i >= 0; --i)
- {
- int j = random () % (i + 1);
- int h = index[j];
- index[j] = index[i];
- index[i] = h;
- }
-}
-
-#define N_10 (nodes[0])
-#define N_20 (nodes[1])
-#define N_30 (nodes[2])
-#define N_40 (nodes[3])
-
START_TEST (test_insert_13)
{
- struct interval_node *nodes = NULL;
- struct interval_tree *tree = test_get_tree4 (&nodes);
-
-
- ck_assert (tree->root == &N_20);
- ck_assert (N_20.left == &N_10);
- ck_assert (N_20.right == &N_30);
- ck_assert (N_30.right == &N_40);
- ck_assert (N_10.color == ITREE_BLACK);
- ck_assert (N_20.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_40.color == ITREE_RED);
+ enum { N = 4 };
+ const int values[N] = {10, 20, 30, 40};
+ struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
+ interval_tree_init (&tree);
+ for (int i = 0; i < N; ++i)
+ itree_insert (&tree, nodes[i], values[i], values[i]);
+
+ ck_assert_ptr_eq (tree.root, &N_20);
+ ck_assert_ptr_eq (N_20.left, &N_10);
+ ck_assert_ptr_eq (N_20.right, &N_30);
+ ck_assert_ptr_eq (N_30.right, &N_40);
+ ck_assert (! N_10.red);
+ ck_assert (! N_20.red);
+ ck_assert (! N_30.red);
+ ck_assert (N_40.red);
}
END_TEST
START_TEST (test_insert_14)
{
- struct interval_tree tree;
- struct interval_node nodes[3];
-
- nodes[0].begin = nodes[1].begin = nodes[2].begin = 10;
- nodes[0].end = nodes[1].end = nodes[2].end = 10;
+ enum { N = 3 };
+ struct itree_node nodes[N];
+ interval_tree_init (&tree);
- for (int i = 0; i < 3; ++i)
- interval_tree_insert (&tree, &nodes[i]);
- for (int i = 0; i < 3; ++i)
+ for (int i = 0; i < N; ++i)
+ itree_insert (&tree, &nodes[i], 10, 10);
+ for (int i = 0; i < N; ++i)
ck_assert (interval_tree_contains (&tree, &nodes[i]));
}
END_TEST
-
-
/*
+===================================================================================+
* | Remove
*
+===================================================================================+
*/
-#define A (nodes[0])
-#define B (nodes[1])
-#define C (nodes[2])
-#define D (nodes[3])
-#define E (nodes[4])
-
/* Creating proper test trees for the formal tests via insertions is
- way to tedious, so we just fake it and only test the
- fix-routine. */
-#define DEF_TEST_SETUP() \
- struct interval_tree tree; \
- struct interval_node nodes[5]; \
- interval_tree_init (&tree); \
- tree.root = &B; \
- A.parent = &B; B.parent = &tree.nil; C.parent = &D; \
- D.parent = &B; E.parent = &D; \
- A.left = A.right = C.left = C.right = &tree.nil; \
- E.left = E.right = &tree.nil; \
- B.left = &A; B.right = &D; D.left = &C; D.right = &E \
+ way too tedious, so we just fake it and only test the
+ fix-routine. */
+static void
+test_remove1_setup (void)
+{
+ interval_tree_init (&tree);
+ tree.root = &B;
+ A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
+ A.left = A.right = C.left = C.right = E.left = E.right = NULL;
+ B.left = &A; B.right = &D;
+ D.left = &C; D.right = &E;
+ A.offset = B.offset = C.offset = D.offset = E.offset = 0;
+ A.otick = B.otick = C.otick = D.otick = E.otick = tree.otick;
+}
/* 1.a -> 2.a
* [B]
@@ -525,126 +476,106 @@ END_TEST
* [C] [E]
*/
-
START_TEST (test_remove_1)
{
- DEF_TEST_SETUP ();
- B.color = A.color = C.color = E.color = ITREE_BLACK;
- D.color = ITREE_RED;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_RED);
- ck_assert (D.color == ITREE_BLACK);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.left == &A);
- ck_assert (B.right == &C);
- ck_assert (C.parent == &B);
- ck_assert (E.parent == &D);
- ck_assert (D.right == &E);
- ck_assert (D.left == &B);
- ck_assert (tree.root == &D);
+ B.red = A.red = C.red = E.red = false;
+ D.red = true;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (C.red);
+ ck_assert (! D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.left, &A);
+ ck_assert_ptr_eq (B.right, &C);
+ ck_assert_ptr_eq (C.parent, &B);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_eq (D.right, &E);
+ ck_assert_ptr_eq (D.left, &B);
+ ck_assert_ptr_eq (tree.root, &D);
}
END_TEST
/* 2.a */
START_TEST (test_remove_2)
{
- DEF_TEST_SETUP ();
- B.color = D.color = A.color = C.color = E.color = ITREE_BLACK;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_BLACK);
- ck_assert (D.color == ITREE_RED);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.left == &A);
- ck_assert (B.right == &D);
- ck_assert (C.parent == &D);
- ck_assert (E.parent == &D);
- ck_assert (tree.root == &B);
+ B.red = D.red = A.red = C.red = E.red = false;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (! C.red);
+ ck_assert (D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.left, &A);
+ ck_assert_ptr_eq (B.right, &D);
+ ck_assert_ptr_eq (C.parent, &D);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_eq (tree.root, &B);
}
END_TEST
-/* 3.a -> 4.a*/
+/* 3.a -> 4.a */
START_TEST (test_remove_3)
{
- DEF_TEST_SETUP ();
- D.color = A.color = E.color = ITREE_BLACK;
- B.color = C.color = ITREE_RED;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_BLACK);
- ck_assert (D.color == ITREE_BLACK);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.left == &A);
- ck_assert (B.right == &tree.nil);
- ck_assert (&C == tree.root);
- ck_assert (C.left == &B);
- ck_assert (C.right == &D);
- ck_assert (E.parent == &D);
- ck_assert (D.left == &tree.nil);
-
+ D.red = A.red = E.red = false;
+ B.red = C.red = true;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (! C.red);
+ ck_assert (! D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.left, &A);
+ ck_assert_ptr_null (B.right);
+ ck_assert_ptr_eq (&C, tree.root);
+ ck_assert_ptr_eq (C.left, &B);
+ ck_assert_ptr_eq (C.right, &D);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_null (D.left);
}
END_TEST
/* 4.a */
START_TEST (test_remove_4)
{
- DEF_TEST_SETUP ();
- B.color = C.color = E.color = ITREE_RED;
- A.color = D.color = ITREE_BLACK;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_RED);
- ck_assert (D.color == ITREE_BLACK);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.left == &A);
- ck_assert (B.right == &C);
- ck_assert (C.parent == &B);
- ck_assert (E.parent == &D);
- ck_assert (tree.root == &D);
+ B.red = C.red = E.red = true;
+ A.red = D.red = false;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (C.red);
+ ck_assert (! D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.left, &A);
+ ck_assert_ptr_eq (B.right, &C);
+ ck_assert_ptr_eq (C.parent, &B);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_eq (tree.root, &D);
}
END_TEST
-
-#undef A
-#undef B
-#undef C
-#undef D
-#undef E
-#undef DEF_TEST_SETUP
-
-/* These are the mirrored cases. */
-
-#define A (nodes[0])
-#define B (nodes[1])
-#define C (nodes[2])
-#define D (nodes[3])
-#define E (nodes[4])
-
-#define DEF_TEST_SETUP() \
- struct interval_tree tree; \
- struct interval_node nodes[5]; \
- interval_tree_init (&tree); \
- tree.root = &B; \
- A.parent = &B; B.parent = &tree.nil; C.parent = &D; \
- D.parent = &B; E.parent = &D; \
- A.right = A.left = C.right = C.left = &tree.nil; \
- E.right = E.left = &tree.nil; \
- B.right = &A; B.left = &D; D.right = &C; D.left = &E \
+/* These are the mirrored cases. */
+
+static void
+test_remove2_setup (void)
+{
+ interval_tree_init (&tree);
+ tree.root = &B;
+ A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
+ A.right = A.left = C.right = C.left = E.right = E.left = NULL;
+ B.right = &A; B.left = &D;
+ D.right = &C; D.left = &E;
+}
/* 1.b -> 2.b
* [B]
@@ -654,161 +585,159 @@ END_TEST
* [C] [E]
*/
-
START_TEST (test_remove_5)
{
- DEF_TEST_SETUP ();
- B.color = A.color = C.color = E.color = ITREE_BLACK;
- D.color = ITREE_RED;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_RED);
- ck_assert (D.color == ITREE_BLACK);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.right == &A);
- ck_assert (B.left == &C);
- ck_assert (C.parent == &B);
- ck_assert (E.parent == &D);
- ck_assert (D.left == &E);
- ck_assert (D.right == &B);
- ck_assert (tree.root == &D);
+ B.red = A.red = C.red = E.red = false;
+ D.red = true;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (C.red);
+ ck_assert (! D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.right, &A);
+ ck_assert_ptr_eq (B.left, &C);
+ ck_assert_ptr_eq (C.parent, &B);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_eq (D.left, &E);
+ ck_assert_ptr_eq (D.right, &B);
+ ck_assert_ptr_eq (tree.root, &D);
}
END_TEST
/* 2.b */
START_TEST (test_remove_6)
{
- DEF_TEST_SETUP ();
- B.color = D.color = A.color = C.color = E.color = ITREE_BLACK;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_BLACK);
- ck_assert (D.color == ITREE_RED);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.right == &A);
- ck_assert (B.left == &D);
- ck_assert (C.parent == &D);
- ck_assert (E.parent == &D);
- ck_assert (tree.root == &B);
+ B.red = D.red = A.red = C.red = E.red = false;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (! C.red);
+ ck_assert (D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.right, &A);
+ ck_assert_ptr_eq (B.left, &D);
+ ck_assert_ptr_eq (C.parent, &D);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_eq (tree.root, &B);
}
END_TEST
-/* 3.b -> 4.b*/
+/* 3.b -> 4.b */
START_TEST (test_remove_7)
{
- DEF_TEST_SETUP ();
- D.color = A.color = E.color = ITREE_BLACK;
- B.color = C.color = ITREE_RED;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_BLACK);
- ck_assert (D.color == ITREE_BLACK);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.right == &A);
- ck_assert (B.left == &tree.nil);
- ck_assert (&C == tree.root);
- ck_assert (C.right == &B);
- ck_assert (C.left == &D);
- ck_assert (E.parent == &D);
- ck_assert (D.right == &tree.nil);
-
+ D.red = A.red = E.red = false;
+ B.red = C.red = true;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (! C.red);
+ ck_assert (! D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.right, &A);
+ ck_assert_ptr_null (B.left);
+ ck_assert_ptr_eq (&C, tree.root);
+ ck_assert_ptr_eq (C.right, &B);
+ ck_assert_ptr_eq (C.left, &D);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_null (D.right);
}
END_TEST
/* 4.b */
START_TEST (test_remove_8)
{
- DEF_TEST_SETUP ();
- B.color = C.color = E.color = ITREE_RED;
- A.color = D.color = ITREE_BLACK;
- interval_tree_remove_fix (&tree, &A);
-
- ck_assert (A.color == ITREE_BLACK);
- ck_assert (B.color == ITREE_BLACK);
- ck_assert (C.color == ITREE_RED);
- ck_assert (D.color == ITREE_BLACK);
- ck_assert (E.color == ITREE_BLACK);
- ck_assert (A.parent == &B);
- ck_assert (B.right == &A);
- ck_assert (B.left == &C);
- ck_assert (C.parent == &B);
- ck_assert (E.parent == &D);
- ck_assert (tree.root == &D);
+ B.red = C.red = E.red = true;
+ A.red = D.red = false;
+ interval_tree_remove_fix (&tree, &A, &B);
+
+ ck_assert (! A.red);
+ ck_assert (! B.red);
+ ck_assert (C.red);
+ ck_assert (! D.red);
+ ck_assert (! E.red);
+ ck_assert_ptr_eq (A.parent, &B);
+ ck_assert_ptr_eq (B.right, &A);
+ ck_assert_ptr_eq (B.left, &C);
+ ck_assert_ptr_eq (C.parent, &B);
+ ck_assert_ptr_eq (E.parent, &D);
+ ck_assert_ptr_eq (tree.root, &D);
}
END_TEST
-
-#undef A
-#undef B
-#undef C
-#undef D
-#undef E
-#undef DEF_TEST_SETUP
-
-
START_TEST (test_remove_9)
{
- struct interval_node *nodes = NULL;
- struct interval_tree *tree = test_get_tree4 (&nodes);
+ enum { N = 4 };
+ const int values[N] = {10, 20, 30, 40};
+ struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
+ interval_tree_init (&tree);
+ for (int i = 0; i < N; ++i)
+ itree_insert (&tree, nodes[i], values[i], values[i]);
- ck_assert (tree->root == &N_20);
+ ck_assert (tree.root == &N_20);
ck_assert (N_20.left == &N_10);
ck_assert (N_20.right == &N_30);
ck_assert (N_30.right == &N_40);
- ck_assert (N_20.color == ITREE_BLACK);
- ck_assert (N_10.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_40.color == ITREE_RED);
-
- interval_tree_remove (tree, &N_10);
-
- ck_assert (tree->root == &N_30);
- ck_assert (N_30.parent == &tree->nil);
- ck_assert (N_30.left == &N_20);
- ck_assert (N_30.right == &N_40);
- ck_assert (N_20.color == ITREE_BLACK);
- ck_assert (N_30.color == ITREE_BLACK);
- ck_assert (N_40.color == ITREE_BLACK);
+ ck_assert (! N_20.red);
+ ck_assert (! N_10.red);
+ ck_assert (! N_30.red);
+ ck_assert (N_40.red);
+
+ itree_remove (&tree, &N_10);
+
+ ck_assert_ptr_eq (tree.root, &N_30);
+ ck_assert_ptr_null (N_30.parent);
+ ck_assert_ptr_eq (N_30.left, &N_20);
+ ck_assert_ptr_eq (N_30.right, &N_40);
+ ck_assert (! N_20.red);
+ ck_assert (! N_30.red);
+ ck_assert (! N_40.red);
}
END_TEST
-#define N 3
+static void
+shuffle (int *index, int n)
+{
+ for (int i = n - 1; i >= 0; --i)
+ {
+ int j = random () % (i + 1);
+ int h = index[j];
+ index[j] = index[i];
+ index[i] = h;
+ }
+}
START_TEST (test_remove_10)
{
- struct interval_tree tree;
- struct interval_node nodes[N];
+ enum { N = 3 };
int index[N];
-
+ for (int i = 0; i < N; ++i)
+ index[i] = i;
srand (42);
+ shuffle (index, N);
+
interval_tree_init (&tree);
+ struct itree_node nodes[N];
for (int i = 0; i < N; ++i)
{
- nodes[i].begin = (i + 1) * 10;
- nodes[i].end = nodes[i].begin + 1;
- index[i] = i;
+ ptrdiff_t pos = (i + 1) * 10;
+ itree_insert (&tree, &nodes[index[i]], pos, pos + 1);
}
- shuffle (index, N);
- for (int i = 0; i < N; ++i)
- interval_tree_insert (&tree, &nodes[index[i]]);
shuffle (index, N);
for (int i = 0; i < N; ++i)
{
ck_assert (interval_tree_contains (&tree, &nodes[index[i]]));
- interval_tree_remove (&tree, &nodes[index[i]]);
+ itree_remove (&tree, &nodes[index[i]]);
}
- ck_assert (tree.root == &tree.nil);
- ck_assert (tree.size == 0);
+ ck_assert_ptr_null (tree.root);
+ ck_assert_int_eq (tree.size, 0);
}
END_TEST
@@ -819,70 +748,57 @@ END_TEST
START_TEST (test_generator_1)
{
- struct interval_tree tree;
- struct interval_node node, *n;
- struct interval_generator *g;
+ struct itree_node node, *n;
+ struct itree_iterator *g;
interval_tree_init (&tree);
- node.begin = 10;
- node.end = 20;
- interval_tree_insert (&tree, &node);
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 0, 30, ITREE_ASCENDING);
- n = interval_generator_next (g);
- ck_assert (n == &node);
- ck_assert (n->begin == 10 && n->end == 20);
- ck_assert (interval_generator_next (g) == NULL);
- ck_assert (interval_generator_next (g) == NULL);
- ck_assert (interval_generator_next (g) == NULL);
- interval_generator_destroy (g);
-
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 30, 50, ITREE_ASCENDING);
- ck_assert (interval_generator_next (g) == NULL);
- ck_assert (interval_generator_next (g) == NULL);
- ck_assert (interval_generator_next (g) == NULL);
- interval_generator_destroy (g);
+
+ itree_insert (&tree, &node, 10, 20);
+ g = itree_iterator_start (&tree, 0, 30, ITREE_ASCENDING, NULL, 0);
+ n = itree_iterator_next (g);
+ ck_assert_ptr_eq (n, &node);
+ ck_assert_int_eq (n->begin, 10);
+ ck_assert_int_eq (n->end, 20);
+ ck_assert_ptr_null (itree_iterator_next (g));
+ ck_assert_ptr_null (itree_iterator_next (g));
+ ck_assert_ptr_null (itree_iterator_next (g));
+ itree_iterator_finish (g);
+
+ g = itree_iterator_start (&tree, 30, 50, ITREE_ASCENDING, NULL, 0);
+ ck_assert_ptr_null (itree_iterator_next (g));
+ ck_assert_ptr_null (itree_iterator_next (g));
+ ck_assert_ptr_null (itree_iterator_next (g));
+ itree_iterator_finish (g);
}
END_TEST
-void
-test_check_generator (struct interval_tree *tree,
+static void
+test_check_generator (struct itree_tree *tree,
ptrdiff_t begin, ptrdiff_t end,
int n, ...)
{
va_list ap;
- struct interval_generator *g = interval_generator_create (tree);
- interval_generator_reset (g, begin, end, ITREE_ASCENDING);
+ struct itree_iterator *g =
+ itree_iterator_start (tree, begin, end, ITREE_ASCENDING, NULL, 0);
va_start (ap, n);
for (int i = 0; i < n; ++i)
{
- ptrdiff_t begin = va_arg (ap, ptrdiff_t);
- struct interval_node *node = interval_generator_next (g);
- ck_assert (node);
- ck_assert_int_eq (node->begin, begin);
+ struct itree_node *node = itree_iterator_next (g);
+ ck_assert_ptr_nonnull (node);
+ ck_assert_int_eq (node->begin, va_arg (ap, ptrdiff_t));
}
va_end (ap);
- ck_assert (! interval_generator_next (g));
- ck_assert (! interval_generator_next (g));
- interval_generator_destroy (g);
+ ck_assert_ptr_null (itree_iterator_next (g));
+ ck_assert_ptr_null (itree_iterator_next (g));
+ itree_iterator_finish (g);
}
-#define DEF_TEST_SETUP() \
-
-
START_TEST (test_generator_2)
{
- struct interval_tree tree;
- struct interval_node nodes[3];
-
interval_tree_init (&tree);
-
- for (int i = 0; i < 3; ++i) {
- nodes[i].begin = 10 * (i + 1);
- nodes[i].end = 10 * (i + 2);
- interval_tree_insert (&tree, &nodes[i]);
- }
+ struct itree_node nodes[3];
+ for (int i = 0; i < 3; ++i)
+ itree_insert (&tree, &nodes[i], 10 * (i + 1), 10 * (i + 2));
test_check_generator (&tree, 0, 50, 3,
10, 20, 30);
@@ -902,72 +818,56 @@ START_TEST (test_generator_2)
}
END_TEST
-
-struct interval_node*
-test_create_tree (struct interval_tree *tree, int n,
- bool doshuffle, ...)
+static void
+test_create_tree (struct itree_node *nodes, int n, bool doshuffle)
{
- va_list ap;
- struct interval_node *nodes = calloc (n, sizeof (struct interval_node));
int *index = calloc (n, sizeof (int));
-
- interval_tree_init (tree);
- va_start (ap, doshuffle);
for (int i = 0; i < n; ++i)
+ index[i] = i;
+ if (doshuffle)
{
- ptrdiff_t begin = va_arg (ap, ptrdiff_t);
- ptrdiff_t end = va_arg (ap, ptrdiff_t);
- nodes[i].begin = begin;
- nodes[i].end = end;
- index[i] = i;
+ srand (42);
+ shuffle (index, n);
}
- va_end (ap);
- srand (42);
- if (doshuffle)
- shuffle (index, n);
+
+ interval_tree_init (&tree);
for (int i = 0; i < n; ++i)
- interval_tree_insert (tree, &nodes[index[i]]);
+ {
+ struct itree_node *node = &nodes[index[i]];
+ itree_insert (&tree, node, node->begin, node->end);
+ }
free (index);
-
- return nodes;
}
START_TEST (test_generator_3)
{
- struct interval_tree tree;
- struct interval_node *nodes = NULL;
-
- nodes = test_create_tree (&tree, 3, true,
- 10, 10,
- 10, 10,
- 10, 10);
+ enum { N = 3 };
+ struct itree_node nodes[N] = {{.begin = 10, .end = 10},
+ {.begin = 10, .end = 10},
+ {.begin = 10, .end = 10}};
+ test_create_tree (nodes, N, true);
test_check_generator (&tree, 0, 10, 0);
- test_check_generator (&tree, 10, 10, 3, 10, 10, 10);
- test_check_generator (&tree, 10, 20, 3, 10, 10, 10);
- free (nodes);
+ test_check_generator (&tree, 10, 10, 3,
+ 10, 10, 10);
+ test_check_generator (&tree, 10, 20, 3,
+ 10, 10, 10);
}
END_TEST
-#define FOREACH(n, g) \
- for ((n) = interval_generator_next (g); (n) != NULL; \
- (n) = interval_generator_next (g))
-
START_TEST (test_generator_5)
{
- struct interval_tree tree;
- struct interval_node *nodes;
- struct interval_generator *g;
- nodes = test_create_tree (&tree, 4, false,
- 10, 30,
- 20, 40,
- 30, 50,
- 40, 60);
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 0, 100, ITREE_PRE_ORDER);
- for (int i = 0; i < 4; ++i)
+ enum { N = 4 };
+ struct itree_node nodes[N] = {{.begin = 10, .end = 30},
+ {.begin = 20, .end = 40},
+ {.begin = 30, .end = 50},
+ {.begin = 40, .end = 60}};
+ test_create_tree (nodes, N, false);
+ struct itree_iterator *g =
+ itree_iterator_start (&tree, 0, 100, ITREE_PRE_ORDER, NULL, 0);
+ for (int i = 0; i < N; ++i)
{
- struct interval_node *n = interval_generator_next (g);
- ck_assert (n);
+ struct itree_node *n = itree_iterator_next (g);
+ ck_assert_ptr_nonnull (n);
switch (i)
{
case 0: ck_assert_int_eq (20, n->begin); break;
@@ -976,28 +876,24 @@ START_TEST (test_generator_5)
case 3: ck_assert_int_eq (40, n->begin); break;
}
}
- interval_generator_destroy (g);
- free (nodes);
-
+ itree_iterator_finish (g);
}
END_TEST
START_TEST (test_generator_6)
{
- struct interval_tree tree;
- struct interval_node *nodes;
- struct interval_generator *g;
- nodes = test_create_tree (&tree, 4, true,
- 10, 30,
- 20, 40,
- 30, 50,
- 40, 60);
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 0, 100, ITREE_ASCENDING);
- for (int i = 0; i < 4; ++i)
+ enum { N = 4 };
+ struct itree_node nodes[N] = {{.begin = 10, .end = 30},
+ {.begin = 20, .end = 40},
+ {.begin = 30, .end = 50},
+ {.begin = 40, .end = 60}};
+ test_create_tree (nodes, N, true);
+ struct itree_iterator *g =
+ itree_iterator_start (&tree, 0, 100, ITREE_ASCENDING, NULL, 0);
+ for (int i = 0; i < N; ++i)
{
- struct interval_node *n = interval_generator_next (g);
- ck_assert (n);
+ struct itree_node *n = itree_iterator_next (g);
+ ck_assert_ptr_nonnull (n);
switch (i)
{
case 0: ck_assert_int_eq (10, n->begin); break;
@@ -1006,28 +902,24 @@ START_TEST (test_generator_6)
case 3: ck_assert_int_eq (40, n->begin); break;
}
}
- interval_generator_destroy (g);
- free (nodes);
-
+ itree_iterator_finish (g);
}
END_TEST
START_TEST (test_generator_7)
{
- struct interval_tree tree;
- struct interval_node *nodes;
- struct interval_generator *g;
- nodes = test_create_tree (&tree, 4, true,
- 10, 30,
- 20, 40,
- 30, 50,
- 40, 60);
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 0, 100, ITREE_DESCENDING);
- for (int i = 0; i < 4; ++i)
+ enum { N = 4 };
+ struct itree_node nodes[N] = {{.begin = 10, .end = 30},
+ {.begin = 20, .end = 40},
+ {.begin = 30, .end = 50},
+ {.begin = 40, .end = 60}};
+ test_create_tree (nodes, N, true);
+ struct itree_iterator *g =
+ itree_iterator_start (&tree, 0, 100, ITREE_DESCENDING, NULL, 0);
+ for (int i = 0; i < N; ++i)
{
- struct interval_node *n = interval_generator_next (g);
- ck_assert (n);
+ struct itree_node *n = itree_iterator_next (g);
+ ck_assert_ptr_nonnull (n);
switch (i)
{
case 0: ck_assert_int_eq (40, n->begin); break;
@@ -1036,48 +928,41 @@ START_TEST (test_generator_7)
case 3: ck_assert_int_eq (10, n->begin); break;
}
}
- interval_generator_destroy (g);
- free (nodes);
-
+ itree_iterator_finish (g);
}
END_TEST
START_TEST (test_generator_8)
{
- struct interval_tree tree;
- struct interval_node *nodes, *n;
- struct interval_generator *g;
- nodes = test_create_tree (&tree, 2, false,
- 20, 30,
- 40, 50);
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 1, 60, ITREE_DESCENDING);
- n = interval_generator_next (g);
+ enum { N = 2 };
+ struct itree_node nodes[N] = {{.begin = 20, .end = 30},
+ {.begin = 40, .end = 50}};
+ test_create_tree (nodes, N, false);
+ struct itree_iterator *g =
+ itree_iterator_start (&tree, 1, 60, ITREE_DESCENDING, NULL, 0);
+ struct itree_node *n = itree_iterator_next (g);
ck_assert_int_eq (n->begin, 40);
- interval_generator_narrow (g, 50, 60);
- n = interval_generator_next (g);
- ck_assert (n == NULL);
- free (nodes);
+ itree_iterator_narrow (g, 50, 60);
+ n = itree_iterator_next (g);
+ ck_assert_ptr_null (n);
+ itree_iterator_finish (g);
}
END_TEST
-
START_TEST (test_generator_9)
{
- struct interval_tree tree;
- struct interval_node *nodes, *n;
- struct interval_generator *g;
- nodes = test_create_tree (&tree, 2, false,
- 25, 25,
- 20, 30);
- g = interval_generator_create (&tree);
- interval_generator_reset (g, 1, 30, ITREE_DESCENDING);
- n = interval_generator_next (g);
+ enum { N = 2 };
+ struct itree_node nodes[N] = {{.begin = 25, .end = 25},
+ {.begin = 20, .end = 30}};
+ test_create_tree (nodes, N, false);
+ struct itree_iterator *g =
+ itree_iterator_start (&tree, 1, 30, ITREE_DESCENDING, NULL, 0);
+ struct itree_node *n = itree_iterator_next (g);
ck_assert_int_eq (n->begin, 25);
- interval_generator_narrow (g, 25, 35);
- n = interval_generator_next (g);
+ itree_iterator_narrow (g, 25, 30);
+ n = itree_iterator_next (g);
ck_assert_int_eq (n->begin, 20);
- free (nodes);
+ itree_iterator_finish (g);
}
END_TEST
@@ -1086,22 +971,20 @@ END_TEST
* | Insert Gap
*
+===================================================================================+
*/
-static struct interval_tree gap_tree;
-static struct interval_node gap_node;
+static struct itree_tree gap_tree;
+static struct itree_node gap_node;
-#define N_BEG (interval_tree_validate (&gap_tree, &gap_node)->begin)
-#define N_END (interval_tree_validate (&gap_tree, &gap_node)->end)
+#define N_BEG (itree_node_begin (&gap_tree, &gap_node))
+#define N_END (itree_node_end (&gap_tree, &gap_node))
static void
test_setup_gap_node (ptrdiff_t begin, ptrdiff_t end,
bool front_advance, bool rear_advance)
{
interval_tree_init (&gap_tree);
- gap_node.begin = begin;
- gap_node.end = end;
gap_node.front_advance = front_advance;
gap_node.rear_advance = rear_advance;
- interval_tree_insert (&gap_tree, &gap_node);
+ itree_insert (&gap_tree, &gap_node, begin, end);
}
static void
@@ -1112,8 +995,8 @@ test_setup_gap_node_noadvance (ptrdiff_t begin, ptrdiff_t
end)
START_TEST (test_gap_insert_1)
{
- test_setup_gap_node (100, 200, false, false);
- interval_tree_insert_gap (&gap_tree, 100 + 10, 20);
+ test_setup_gap_node_noadvance (100, 200);
+ itree_insert_gap (&gap_tree, 100 + 10, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200 + 20);
}
@@ -1121,8 +1004,8 @@ END_TEST
START_TEST (test_gap_insert_2)
{
- test_setup_gap_node (100, 200, false, false);
- interval_tree_insert_gap (&gap_tree, 300, 10);
+ test_setup_gap_node_noadvance (100, 200);
+ itree_insert_gap (&gap_tree, 300, 10, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200);
}
@@ -1130,8 +1013,8 @@ END_TEST
START_TEST (test_gap_insert_3)
{
- test_setup_gap_node (100, 200, false, false);
- interval_tree_insert_gap (&gap_tree, 0, 15);
+ test_setup_gap_node_noadvance (100, 200);
+ itree_insert_gap (&gap_tree, 0, 15, false);
ck_assert_int_eq (N_BEG, 100 + 15);
ck_assert_int_eq (N_END, 200 + 15);
}
@@ -1140,7 +1023,7 @@ END_TEST
START_TEST (test_gap_insert_4)
{
test_setup_gap_node (100, 200, true, false);
- interval_tree_insert_gap (&gap_tree, 100, 20);
+ itree_insert_gap (&gap_tree, 100, 20, false);
ck_assert_int_eq (N_BEG, 100 + 20);
ck_assert_int_eq (N_END, 200 + 20);
@@ -1149,8 +1032,8 @@ END_TEST
START_TEST (test_gap_insert_5)
{
- test_setup_gap_node (100, 200, false, false);
- interval_tree_insert_gap (&gap_tree, 100, 20);
+ test_setup_gap_node_noadvance (100, 200);
+ itree_insert_gap (&gap_tree, 100, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200 + 20);
@@ -1160,7 +1043,7 @@ END_TEST
START_TEST (test_gap_insert_6)
{
test_setup_gap_node (100, 200, false, true);
- interval_tree_insert_gap (&gap_tree, 200, 20);
+ itree_insert_gap (&gap_tree, 200, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200 + 20);
@@ -1169,8 +1052,8 @@ END_TEST
START_TEST (test_gap_insert_7)
{
- test_setup_gap_node (100, 200, false, false);
- interval_tree_insert_gap (&gap_tree, 200, 20);
+ test_setup_gap_node_noadvance (100, 200);
+ itree_insert_gap (&gap_tree, 200, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200);
@@ -1180,7 +1063,7 @@ END_TEST
START_TEST (test_gap_insert_8)
{
test_setup_gap_node (100, 100, true, true);
- interval_tree_insert_gap (&gap_tree, 100, 20);
+ itree_insert_gap (&gap_tree, 100, 20, false);
ck_assert_int_eq (N_BEG, 100 + 20);
ck_assert_int_eq (N_END, 100 + 20);
@@ -1190,7 +1073,7 @@ END_TEST
START_TEST (test_gap_insert_9)
{
test_setup_gap_node (100, 100, false, true);
- interval_tree_insert_gap (&gap_tree, 100, 20);
+ itree_insert_gap (&gap_tree, 100, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 100 + 20);
@@ -1200,7 +1083,7 @@ END_TEST
START_TEST (test_gap_insert_10)
{
test_setup_gap_node (100, 100, true, false);
- interval_tree_insert_gap (&gap_tree, 100, 20);
+ itree_insert_gap (&gap_tree, 100, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 100);
@@ -1209,8 +1092,8 @@ END_TEST
START_TEST (test_gap_insert_11)
{
- test_setup_gap_node (100, 100, false, false);
- interval_tree_insert_gap (&gap_tree, 100, 20);
+ test_setup_gap_node_noadvance (100, 100);
+ itree_insert_gap (&gap_tree, 100, 20, false);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 100);
@@ -1225,7 +1108,7 @@ END_TEST
START_TEST (test_gap_delete_1)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 100 + 10, 20);
+ itree_delete_gap (&gap_tree, 100 + 10, 20);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200 - 20);
@@ -1235,7 +1118,7 @@ END_TEST
START_TEST (test_gap_delete_2)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 200 + 10, 20);
+ itree_delete_gap (&gap_tree, 200 + 10, 20);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200);
@@ -1245,7 +1128,7 @@ END_TEST
START_TEST (test_gap_delete_3)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 200, 20);
+ itree_delete_gap (&gap_tree, 200, 20);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 200);
@@ -1255,7 +1138,7 @@ END_TEST
START_TEST (test_gap_delete_4)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 100 - 20, 20);
+ itree_delete_gap (&gap_tree, 100 - 20, 20);
ck_assert_int_eq (N_BEG, 100 - 20);
ck_assert_int_eq (N_END, 200 - 20);
@@ -1265,7 +1148,7 @@ END_TEST
START_TEST (test_gap_delete_5)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 70, 20);
+ itree_delete_gap (&gap_tree, 70, 20);
ck_assert_int_eq (N_BEG, 100 - 20);
ck_assert_int_eq (N_END, 200 - 20);
@@ -1275,7 +1158,7 @@ END_TEST
START_TEST (test_gap_delete_6)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 80, 100);
+ itree_delete_gap (&gap_tree, 80, 100);
ck_assert_int_eq (N_BEG, 80);
ck_assert_int_eq (N_END, 100);
}
@@ -1284,7 +1167,7 @@ END_TEST
START_TEST (test_gap_delete_7)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 120, 100);
+ itree_delete_gap (&gap_tree, 120, 100);
ck_assert_int_eq (N_BEG, 100);
ck_assert_int_eq (N_END, 120);
}
@@ -1293,7 +1176,7 @@ END_TEST
START_TEST (test_gap_delete_8)
{
test_setup_gap_node_noadvance (100, 200);
- interval_tree_delete_gap (&gap_tree, 100 - 20, 200 + 20);
+ itree_delete_gap (&gap_tree, 100 - 20, 200 + 20);
ck_assert_int_eq (N_BEG, 100 - 20);
ck_assert_int_eq (N_END, 100 - 20);
@@ -1302,36 +1185,58 @@ END_TEST
-Suite * basic_suite ()
+static Suite *
+basic_suite ()
{
- Suite *s = suite_create ("basic_suite");
- TCase *tc = tcase_create ("basic_test");
+ Suite *s = suite_create ("basic");
+ TCase *tc = tcase_create ("insert1");
+ tcase_add_checked_fixture (tc, test_insert1_setup, NULL);
tcase_add_test (tc, test_insert_1);
tcase_add_test (tc, test_insert_2);
tcase_add_test (tc, test_insert_3);
tcase_add_test (tc, test_insert_4);
tcase_add_test (tc, test_insert_5);
tcase_add_test (tc, test_insert_6);
+ suite_add_tcase (s, tc);
+
+ tc = tcase_create ("insert2");
+ tcase_add_checked_fixture (tc, test_insert2_setup, NULL);
tcase_add_test (tc, test_insert_7);
tcase_add_test (tc, test_insert_8);
tcase_add_test (tc, test_insert_9);
tcase_add_test (tc, test_insert_10);
tcase_add_test (tc, test_insert_11);
tcase_add_test (tc, test_insert_12);
+ suite_add_tcase (s, tc);
+
+ tc = tcase_create ("insert3");
tcase_add_test (tc, test_insert_13);
+ tcase_add_test (tc, test_insert_14);
+ suite_add_tcase (s, tc);
+ tc = tcase_create ("remove1");
+ tcase_add_checked_fixture (tc, test_remove1_setup, NULL);
tcase_add_test (tc, test_remove_1);
tcase_add_test (tc, test_remove_2);
tcase_add_test (tc, test_remove_3);
tcase_add_test (tc, test_remove_4);
+ suite_add_tcase (s, tc);
+
+ tc = tcase_create ("remove2");
+ tcase_add_checked_fixture (tc, test_remove2_setup, NULL);
tcase_add_test (tc, test_remove_5);
tcase_add_test (tc, test_remove_6);
tcase_add_test (tc, test_remove_7);
tcase_add_test (tc, test_remove_8);
+ suite_add_tcase (s, tc);
+
+ tc = tcase_create ("remove3");
tcase_add_test (tc, test_remove_9);
tcase_add_test (tc, test_remove_10);
+ suite_add_tcase (s, tc);
+ tc = tcase_create ("generator");
tcase_add_test (tc, test_generator_1);
tcase_add_test (tc, test_generator_2);
tcase_add_test (tc, test_generator_3);
@@ -1340,7 +1245,9 @@ Suite * basic_suite ()
tcase_add_test (tc, test_generator_7);
tcase_add_test (tc, test_generator_8);
tcase_add_test (tc, test_generator_9);
+ suite_add_tcase (s, tc);
+ tc = tcase_create ("insert_gap");
tcase_add_test (tc, test_gap_insert_1);
tcase_add_test (tc, test_gap_insert_2);
tcase_add_test (tc, test_gap_insert_3);
@@ -1352,7 +1259,9 @@ Suite * basic_suite ()
tcase_add_test (tc, test_gap_insert_9);
tcase_add_test (tc, test_gap_insert_10);
tcase_add_test (tc, test_gap_insert_11);
+ suite_add_tcase (s, tc);
+ tc = tcase_create ("delete_gap");
tcase_add_test (tc, test_gap_delete_1);
tcase_add_test (tc, test_gap_delete_2);
tcase_add_test (tc, test_gap_delete_3);
@@ -1361,21 +1270,20 @@ Suite * basic_suite ()
tcase_add_test (tc, test_gap_delete_6);
tcase_add_test (tc, test_gap_delete_7);
tcase_add_test (tc, test_gap_delete_8);
-
- /* tcase_set_timeout (tc, 120); */
suite_add_tcase (s, tc);
+
return s;
}
int
main (void)
{
- int nfailed;
Suite *s = basic_suite ();
SRunner *sr = srunner_create (s);
- srunner_run_all (sr, CK_NORMAL);
- nfailed = srunner_ntests_failed (sr);
+ init_itree ();
+ srunner_run_all (sr, CK_ENV);
+ int nfailed = srunner_ntests_failed (sr);
srunner_free (sr);
return (nfailed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- master fd3f51b7c3: Fix manual noverlay tests,
Basil L. Contovounesios <=