aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBasil L. Contovounesios2022-11-02 03:52:16 +0200
committerBasil L. Contovounesios2022-11-04 13:38:02 +0200
commitfd3f51b7c3a6649ee3db12d33b056b1afdbfa7e9 (patch)
treea71040416668b74469af493d3f9a741e975d1202
parent01471b5fdff21fcb23b7718d9cd99bf5c08645ba (diff)
downloademacs-fd3f51b7c3a6649ee3db12d33b056b1afdbfa7e9.tar.gz
emacs-fd3f51b7c3a6649ee3db12d33b056b1afdbfa7e9.zip
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.
Diffstat
-rw-r--r--test/manual/noverlay/Makefile.in41
-rwxr-xr-xtest/manual/noverlay/check-sanitize.sh28
-rw-r--r--test/manual/noverlay/emacs-compat.h36
-rw-r--r--test/manual/noverlay/itree-tests.c1284
4 files changed, 679 insertions, 710 deletions
diff --git a/test/manual/noverlay/Makefile.in b/test/manual/noverlay/Makefile.in
index beef1dbc097..3c8dba1ce1f 100644
--- a/test/manual/noverlay/Makefile.in
+++ b/test/manual/noverlay/Makefile.in
@@ -1,26 +1,41 @@
1### @configure_input@
2
3# Copyright (C) 2017-2022 Free Software Foundation, Inc.
4
5# This file is part of GNU Emacs.
6
7# GNU Emacs is free software: you can redistribute it and/or modify
8# it under the terms of the GNU General Public License as published by
9# the Free Software Foundation, either version 3 of the License, or
10# (at your option) any later version.
11
12# GNU Emacs is distributed in the hope that it will be useful,
13# but WITHOUT ANY WARRANTY; without even the implied warranty of
14# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15# GNU General Public License for more details.
16
17# You should have received a copy of the GNU General Public License
18# along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
19
1PROGRAM = itree-tests 20PROGRAM = itree-tests
2LIBS = check 21PACKAGES = check
3top_srcdir = @top_srcdir@ 22top_srcdir = @top_srcdir@
4CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(LIBS)) -I $(top_srcdir)/src 23top_builddir = @top_builddir@
5LDFLAGS += $(shell pkg-config --libs $(LIBS)) -lm 24CPPFLAGS += -I $(top_srcdir)/src
25CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(PACKAGES))
26LDLIBS += $(shell pkg-config --libs $(PACKAGES)) -lm
6OBJECTS = itree-tests.o 27OBJECTS = itree-tests.o
7CC = gcc 28CC = gcc
8EMACS ?= ../../../src/emacs 29EMACS ?= $(top_builddir)/src/emacs
9 30
10.PHONY: all check have-libcheck 31.PHONY: all check clean distclean perf
11 32
12all: check 33all: check
13 34
14have-libcheck: 35check: $(PROGRAM)
15 pkg-config --cflags $(LIBS)
16
17check: have-libcheck $(PROGRAM)
18 ./check-sanitize.sh ./$(PROGRAM) 36 ./check-sanitize.sh ./$(PROGRAM)
19 37
20itree-tests.o: emacs-compat.h itree-tests.c $(top_srcdir)/src/itree.c $(top_srcdir)/src/itree.h 38itree-tests.o: emacs-compat.h $(top_srcdir)/src/itree.c $(top_srcdir)/src/itree.h
21
22$(PROGRAM): $(OBJECTS)
23 $(CC) $(CFLAGS) $(LDFLAGS) $(OBJECTS) -o $(PROGRAM)
24 39
25perf: 40perf:
26 -$(EMACS) -Q -l ./overlay-perf.el -f perf-run-batch 41 -$(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 03eedce8a67..9a67818dc8f 100755
--- a/test/manual/noverlay/check-sanitize.sh
+++ b/test/manual/noverlay/check-sanitize.sh
@@ -1,11 +1,33 @@
1#!/bin/bash 1#!/usr/bin/env bash
2### check-sanitize.sh - strip confusing parts of Check error output
3
4## Copyright (C) 2017-2022 Free Software Foundation, Inc.
5
6## This file is part of GNU Emacs.
7
8## GNU Emacs is free software: you can redistribute it and/or modify
9## it under the terms of the GNU General Public License as published by
10## the Free Software Foundation, either version 3 of the License, or
11## (at your option) any later version.
12
13## GNU Emacs is distributed in the hope that it will be useful,
14## but WITHOUT ANY WARRANTY; without even the implied warranty of
15## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16## GNU General Public License for more details.
17
18## You should have received a copy of the GNU General Public License
19## along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
20
21set -o pipefail
2 22
3prog=$1 23prog=$1
4shift 24shift
5 25
6[ -z "$prog" ] && { 26[ -z "$prog" ] && {
7 echo "usage:$(basename $0) CHECK_PRGOGRAM"; 27 echo "usage:$(basename $0) CHECK_PROGRAM";
8 exit 1; 28 exit 1;
9} 29}
10 30
11"$prog" "$@" | sed -e 's/^\([^:]\+\):\([0-9]\+\):[PFE]:[^:]*:\([^:]*\):[^:]*: *\(.*\)/\1:\2:\3:\4/' 31# FIXME: This would be unnecessary if
32# compilation-error-regexp-alist-alist understood libcheck OOTB.
33"$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 812f8e48a36..d2448b12db3 100644
--- a/test/manual/noverlay/emacs-compat.h
+++ b/test/manual/noverlay/emacs-compat.h
@@ -1,8 +1,28 @@
1/* Mock necessary parts of lisp.h.
2
3Copyright (C) 2017-2022 Free Software Foundation, Inc.
4
5This file is part of GNU Emacs.
6
7GNU Emacs is free software: you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation, either version 3 of the License, or (at
10your option) any later version.
11
12GNU Emacs is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
19
1#ifndef TEST_COMPAT_H 20#ifndef TEST_COMPAT_H
2#define TEST_COMPAT_H 21#define TEST_COMPAT_H
3 22
4#include <stdio.h>
5#include <limits.h> 23#include <limits.h>
24#include <stdio.h>
25#include <stdlib.h>
6 26
7typedef int Lisp_Object; 27typedef int Lisp_Object;
8 28
@@ -28,20 +48,24 @@ void
28emacs_abort () 48emacs_abort ()
29{ 49{
30 fprintf (stderr, "Aborting...\n"); 50 fprintf (stderr, "Aborting...\n");
31 exit (1); 51 exit (EXIT_FAILURE);
32} 52}
33 53
34#ifndef eassert 54#ifndef eassert
35#define eassert(cond) \ 55#define eassert(cond) \
36 do { \ 56 do { \
37 if (! (cond)) { \ 57 if (! (cond)) { \
38 fprintf (stderr, "\n%s:%d:eassert condition failed: %s\n", \ 58 fprintf (stderr, "%s:%d:eassert condition failed: %s\n", \
39 __FILE__, __LINE__ ,#cond); \ 59 __FILE__, __LINE__ , # cond); \
40 exit (1); \ 60 exit (EXIT_FAILURE); \
41 } \ 61 } \
42 } while (0) 62 } while (0)
43#endif 63#endif
44 64
65#ifndef eassume
66#define eassume eassert
67#endif
68
45#ifndef max 69#ifndef max
46#define max(x,y) ((x) >= (y) ? (x) : (y)) 70#define max(x,y) ((x) >= (y) ? (x) : (y))
47#endif 71#endif
@@ -49,4 +73,4 @@ emacs_abort ()
49#define min(x,y) ((x) <= (y) ? (x) : (y)) 73#define min(x,y) ((x) <= (y) ? (x) : (y))
50#endif 74#endif
51 75
52#endif 76#endif /* TEST_COMPAT_H */
diff --git a/test/manual/noverlay/itree-tests.c b/test/manual/noverlay/itree-tests.c
index a3183892132..278e65f9bf7 100644
--- a/test/manual/noverlay/itree-tests.c
+++ b/test/manual/noverlay/itree-tests.c
@@ -1,7 +1,28 @@
1/* Test the interval data-structure in itree.c.
2
3Copyright (c) 2017-2022 Free Software Foundation, Inc.
4
5This file is part of GNU Emacs.
6
7GNU Emacs is free software: you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation, either version 3 of the License, or (at
10your option) any later version.
11
12GNU Emacs is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
19
1#include <config.h> 20#include <config.h>
2#include <check.h> 21
3#include <stdlib.h>
4#include <stdarg.h> 22#include <stdarg.h>
23#include <stdlib.h>
24
25#include <check.h>
5#include "emacs-compat.h" 26#include "emacs-compat.h"
6 27
7#define EMACS_LISP_H /* lisp.h inclusion guard */ 28#define EMACS_LISP_H /* lisp.h inclusion guard */
@@ -9,7 +30,14 @@
9#define ITREE_TESTING 30#define ITREE_TESTING
10#include "itree.c" 31#include "itree.c"
11 32
12/* Basic tests of the interval_tree data-structure. */ 33/* Globals. */
34
35static struct itree_tree tree;
36static struct itree_node A, B, C, D, E;
37static struct itree_node N_05, N_10, N_15, N_20, N_30, N_40;
38static struct itree_node N_50, N_70, N_80, N_90, N_85, N_95;
39
40/* Basic tests of the itree_tree data-structure. */
13 41
14/* +===================================================================================+ 42/* +===================================================================================+
15 * | Insert 43 * | Insert
@@ -17,25 +45,21 @@
17 45
18/* The graphs below display the trees after each insertion (as they 46/* The graphs below display the trees after each insertion (as they
19 should be). See the source code for the different cases 47 should be). See the source code for the different cases
20 applied. */ 48 applied. */
21 49
22#define N_50 (n[0]) 50static void
23#define N_30 (n[1]) 51test_insert1_setup (void)
24#define N_20 (n[2]) 52{
25#define N_10 (n[3]) 53 enum { N = 6 };
26#define N_15 (n[4]) 54 const int values[N] = {50, 30, 20, 10, 15, 5};
27#define N_05 (n[5]) 55 struct itree_node *nodes[N] = {&N_50, &N_30, &N_20, &N_10, &N_15, &N_05};
28 56 interval_tree_init (&tree);
29#define DEF_TEST_SETUP() \ 57 for (int i = 0; i < N; ++i)
30 struct interval_tree tree; \ 58 {
31 struct interval_node n[6]; \ 59 nodes[i]->begin = nodes[i]->end = values[i];
32 interval_tree_init (&tree); \ 60 nodes[i]->otick = tree.otick;
33 const int values[] = {50, 30, 20, 10, 15, 5}; \
34 for (int i = 0; i < 6; ++i) \
35 { \
36 n[i].begin = values[i]; \
37 n[i].end = values[i]; \
38 } 61 }
62}
39 63
40START_TEST (test_insert_1) 64START_TEST (test_insert_1)
41{ 65{
@@ -43,10 +67,9 @@ START_TEST (test_insert_1)
43 * [50] 67 * [50]
44 */ 68 */
45 69
46 DEF_TEST_SETUP ();
47 interval_tree_insert (&tree, &N_50); 70 interval_tree_insert (&tree, &N_50);
48 ck_assert (N_50.color == ITREE_BLACK); 71 ck_assert (! N_50.red);
49 ck_assert (&N_50 == tree.root); 72 ck_assert_ptr_eq (&N_50, tree.root);
50} 73}
51END_TEST 74END_TEST
52 75
@@ -58,17 +81,16 @@ START_TEST (test_insert_2)
58 * (30) 81 * (30)
59 */ 82 */
60 83
61 DEF_TEST_SETUP ();
62 interval_tree_insert (&tree, &N_50); 84 interval_tree_insert (&tree, &N_50);
63 interval_tree_insert (&tree, &N_30); 85 interval_tree_insert (&tree, &N_30);
64 ck_assert (N_50.color == ITREE_BLACK); 86 ck_assert (! N_50.red);
65 ck_assert (N_30.color == ITREE_RED); 87 ck_assert (N_30.red);
66 ck_assert (&N_50 == tree.root); 88 ck_assert_ptr_eq (&N_50, tree.root);
67 ck_assert (N_30.parent == &N_50); 89 ck_assert_ptr_eq (N_30.parent, &N_50);
68 ck_assert (N_50.left == &N_30); 90 ck_assert_ptr_eq (N_50.left, &N_30);
69 ck_assert (N_50.right == &tree.nil); 91 ck_assert_ptr_null (N_50.right);
70 ck_assert (N_30.left == &tree.nil); 92 ck_assert_ptr_null (N_30.left);
71 ck_assert (N_30.right == &tree.nil); 93 ck_assert_ptr_null (N_30.right);
72} 94}
73END_TEST 95END_TEST
74 96
@@ -80,20 +102,19 @@ START_TEST (test_insert_3)
80 * (20) (50) 102 * (20) (50)
81 */ 103 */
82 104
83 DEF_TEST_SETUP ();
84 interval_tree_insert (&tree, &N_50); 105 interval_tree_insert (&tree, &N_50);
85 interval_tree_insert (&tree, &N_30); 106 interval_tree_insert (&tree, &N_30);
86 interval_tree_insert (&tree, &N_20); 107 interval_tree_insert (&tree, &N_20);
87 ck_assert (N_50.color == ITREE_RED); 108 ck_assert (N_50.red);
88 ck_assert (N_30.color == ITREE_BLACK); 109 ck_assert (! N_30.red);
89 ck_assert (N_20.color == ITREE_RED); 110 ck_assert (N_20.red);
90 ck_assert (&N_30 == tree.root); 111 ck_assert_ptr_eq (&N_30, tree.root);
91 ck_assert (N_50.parent == &N_30); 112 ck_assert_ptr_eq (N_50.parent, &N_30);
92 ck_assert (N_30.right == &N_50); 113 ck_assert_ptr_eq (N_30.right, &N_50);
93 ck_assert (N_30.left == &N_20); 114 ck_assert_ptr_eq (N_30.left, &N_20);
94 ck_assert (N_20.left == &tree.nil); 115 ck_assert_ptr_null (N_20.left);
95 ck_assert (N_20.right == &tree.nil); 116 ck_assert_ptr_null (N_20.right);
96 ck_assert (N_20.parent == &N_30); 117 ck_assert_ptr_eq (N_20.parent, &N_30);
97} 118}
98END_TEST 119END_TEST
99 120
@@ -107,25 +128,24 @@ START_TEST (test_insert_4)
107 * (10) 128 * (10)
108 */ 129 */
109 130
110 DEF_TEST_SETUP ();
111 interval_tree_insert (&tree, &N_50); 131 interval_tree_insert (&tree, &N_50);
112 interval_tree_insert (&tree, &N_30); 132 interval_tree_insert (&tree, &N_30);
113 interval_tree_insert (&tree, &N_20); 133 interval_tree_insert (&tree, &N_20);
114 interval_tree_insert (&tree, &N_10); 134 interval_tree_insert (&tree, &N_10);
115 ck_assert (N_50.color == ITREE_BLACK); 135 ck_assert (! N_50.red);
116 ck_assert (N_30.color == ITREE_BLACK); 136 ck_assert (! N_30.red);
117 ck_assert (N_20.color == ITREE_BLACK); 137 ck_assert (! N_20.red);
118 ck_assert (N_10.color == ITREE_RED); 138 ck_assert (N_10.red);
119 ck_assert (&N_30 == tree.root); 139 ck_assert_ptr_eq (&N_30, tree.root);
120 ck_assert (N_50.parent == &N_30); 140 ck_assert_ptr_eq (N_50.parent, &N_30);
121 ck_assert (N_30.right == &N_50); 141 ck_assert_ptr_eq (N_30.right, &N_50);
122 ck_assert (N_30.left == &N_20); 142 ck_assert_ptr_eq (N_30.left, &N_20);
123 ck_assert (N_20.left == &N_10); 143 ck_assert_ptr_eq (N_20.left, &N_10);
124 ck_assert (N_20.right == &tree.nil); 144 ck_assert_ptr_null (N_20.right);
125 ck_assert (N_20.parent == &N_30); 145 ck_assert_ptr_eq (N_20.parent, &N_30);
126 ck_assert (N_10.parent == &N_20); 146 ck_assert_ptr_eq (N_10.parent, &N_20);
127 ck_assert (N_20.left == &N_10); 147 ck_assert_ptr_eq (N_20.left, &N_10);
128 ck_assert (N_10.right == &tree.nil); 148 ck_assert_ptr_null (N_10.right);
129} 149}
130END_TEST 150END_TEST
131 151
@@ -139,31 +159,29 @@ START_TEST (test_insert_5)
139 * (10) (20) 159 * (10) (20)
140 */ 160 */
141 161
142 DEF_TEST_SETUP ();
143 interval_tree_insert (&tree, &N_50); 162 interval_tree_insert (&tree, &N_50);
144 interval_tree_insert (&tree, &N_30); 163 interval_tree_insert (&tree, &N_30);
145 interval_tree_insert (&tree, &N_20); 164 interval_tree_insert (&tree, &N_20);
146 interval_tree_insert (&tree, &N_10); 165 interval_tree_insert (&tree, &N_10);
147 interval_tree_insert (&tree, &N_15); 166 interval_tree_insert (&tree, &N_15);
148 ck_assert (N_50.color == ITREE_BLACK); 167 ck_assert (! N_50.red);
149 ck_assert (N_30.color == ITREE_BLACK); 168 ck_assert (! N_30.red);
150 ck_assert (N_20.color == ITREE_RED); 169 ck_assert (N_20.red);
151 ck_assert (N_10.color == ITREE_RED); 170 ck_assert (N_10.red);
152 ck_assert (N_15.color == ITREE_BLACK); 171 ck_assert (! N_15.red);
153 ck_assert (&N_30 == tree.root); 172 ck_assert_ptr_eq (&N_30, tree.root);
154 ck_assert (N_50.parent == &N_30); 173 ck_assert_ptr_eq (N_50.parent, &N_30);
155 ck_assert (N_30.right == &N_50); 174 ck_assert_ptr_eq (N_30.right, &N_50);
156 ck_assert (N_30.left == &N_15); 175 ck_assert_ptr_eq (N_30.left, &N_15);
157 ck_assert (N_20.left == &tree.nil); 176 ck_assert_ptr_null (N_20.left);
158 ck_assert (N_20.right == &tree.nil); 177 ck_assert_ptr_null (N_20.right);
159 ck_assert (N_20.parent == &N_15); 178 ck_assert_ptr_eq (N_20.parent, &N_15);
160 ck_assert (N_10.parent == &N_15); 179 ck_assert_ptr_eq (N_10.parent, &N_15);
161 ck_assert (N_20.left == &tree.nil); 180 ck_assert_ptr_null (N_20.left);
162 ck_assert (N_10.right == &tree.nil); 181 ck_assert_ptr_null (N_10.right);
163 ck_assert (N_15.right == &N_20); 182 ck_assert_ptr_eq (N_15.right, &N_20);
164 ck_assert (N_15.left == &N_10); 183 ck_assert_ptr_eq (N_15.left, &N_10);
165 ck_assert (N_15.parent == &N_30); 184 ck_assert_ptr_eq (N_15.parent, &N_30);
166
167} 185}
168END_TEST 186END_TEST
169 187
@@ -179,67 +197,54 @@ START_TEST (test_insert_6)
179 * (5) 197 * (5)
180 */ 198 */
181 199
182 DEF_TEST_SETUP ();
183 interval_tree_insert (&tree, &N_50); 200 interval_tree_insert (&tree, &N_50);
184 interval_tree_insert (&tree, &N_30); 201 interval_tree_insert (&tree, &N_30);
185 interval_tree_insert (&tree, &N_20); 202 interval_tree_insert (&tree, &N_20);
186 interval_tree_insert (&tree, &N_10); 203 interval_tree_insert (&tree, &N_10);
187 interval_tree_insert (&tree, &N_15); 204 interval_tree_insert (&tree, &N_15);
188 interval_tree_insert (&tree, &N_05); 205 interval_tree_insert (&tree, &N_05);
189 ck_assert (N_50.color == ITREE_BLACK); 206 ck_assert (! N_50.red);
190 ck_assert (N_30.color == ITREE_BLACK); 207 ck_assert (! N_30.red);
191 ck_assert (N_20.color == ITREE_BLACK); 208 ck_assert (! N_20.red);
192 ck_assert (N_10.color == ITREE_BLACK); 209 ck_assert (! N_10.red);
193 ck_assert (N_15.color == ITREE_RED); 210 ck_assert (N_15.red);
194 ck_assert (N_05.color == ITREE_RED); 211 ck_assert (N_05.red);
195 ck_assert (&N_30 == tree.root); 212 ck_assert_ptr_eq (&N_30, tree.root);
196 ck_assert (N_50.parent == &N_30); 213 ck_assert_ptr_eq (N_50.parent, &N_30);
197 ck_assert (N_30.right == &N_50); 214 ck_assert_ptr_eq (N_30.right, &N_50);
198 ck_assert (N_30.left == &N_15); 215 ck_assert_ptr_eq (N_30.left, &N_15);
199 ck_assert (N_20.left == &tree.nil); 216 ck_assert_ptr_null (N_20.left);
200 ck_assert (N_20.right == &tree.nil); 217 ck_assert_ptr_null (N_20.right);
201 ck_assert (N_20.parent == &N_15); 218 ck_assert_ptr_eq (N_20.parent, &N_15);
202 ck_assert (N_10.parent == &N_15); 219 ck_assert_ptr_eq (N_10.parent, &N_15);
203 ck_assert (N_20.left == &tree.nil); 220 ck_assert_ptr_null (N_20.left);
204 ck_assert (N_10.right == &tree.nil); 221 ck_assert_ptr_null (N_10.right);
205 ck_assert (N_15.right == &N_20); 222 ck_assert_ptr_eq (N_15.right, &N_20);
206 ck_assert (N_15.left == &N_10); 223 ck_assert_ptr_eq (N_15.left, &N_10);
207 ck_assert (N_15.parent == &N_30); 224 ck_assert_ptr_eq (N_15.parent, &N_30);
208 ck_assert (N_05.parent == &N_10); 225 ck_assert_ptr_eq (N_05.parent, &N_10);
209 ck_assert (N_10.left == &N_05); 226 ck_assert_ptr_eq (N_10.left, &N_05);
210 ck_assert (N_05.right == &tree.nil); 227 ck_assert_ptr_null (N_05.right);
211} 228}
212END_TEST 229END_TEST
213 230
214#undef N_50
215#undef N_30
216#undef N_20
217#undef N_10
218#undef N_15
219#undef N_05
220#undef DEF_TEST_SETUP
221
222 231
223 232
224/* These are the mirror cases to the above ones. */ 233/* These are the mirror cases to the above ones. */
225 234
226#define N_50 (n[0]) 235static void
227#define N_70 (n[1]) 236test_insert2_setup (void)
228#define N_80 (n[2]) 237{
229#define N_90 (n[3]) 238 enum { N = 6 };
230#define N_85 (n[4]) 239 const int values[] = {50, 70, 80, 90, 85, 95};
231#define N_95 (n[5]) 240 struct itree_node *nodes[N] = {&N_50, &N_70, &N_80, &N_90, &N_85, &N_95};
232 241 interval_tree_init (&tree);
233#define DEF_TEST_SETUP() \ 242 for (int i = 0; i < N; ++i)
234 struct interval_tree tree; \ 243 {
235 struct interval_node n[6]; \ 244 nodes[i]->begin = nodes[i]->end = values[i];
236 interval_tree_init (&tree); \ 245 nodes[i]->otick = tree.otick;
237 const int values[] = {50, 70, 80, 90, 85, 95}; \
238 for (int i = 0; i < 6; ++i) \
239 { \
240 n[i].begin = values[i]; \
241 n[i].end = values[i]; \
242 } 246 }
247}
243 248
244START_TEST (test_insert_7) 249START_TEST (test_insert_7)
245{ 250{
@@ -247,10 +252,9 @@ START_TEST (test_insert_7)
247 * [50] 252 * [50]
248 */ 253 */
249 254
250 DEF_TEST_SETUP ();
251 interval_tree_insert (&tree, &N_50); 255 interval_tree_insert (&tree, &N_50);
252 ck_assert (N_50.color == ITREE_BLACK); 256 ck_assert (! N_50.red);
253 ck_assert (&N_50 == tree.root); 257 ck_assert_ptr_eq (&N_50, tree.root);
254} 258}
255END_TEST 259END_TEST
256 260
@@ -262,17 +266,16 @@ START_TEST (test_insert_8)
262 * (70) 266 * (70)
263 */ 267 */
264 268
265 DEF_TEST_SETUP ();
266 interval_tree_insert (&tree, &N_50); 269 interval_tree_insert (&tree, &N_50);
267 interval_tree_insert (&tree, &N_70); 270 interval_tree_insert (&tree, &N_70);
268 ck_assert (N_50.color == ITREE_BLACK); 271 ck_assert (! N_50.red);
269 ck_assert (N_70.color == ITREE_RED); 272 ck_assert (N_70.red);
270 ck_assert (&N_50 == tree.root); 273 ck_assert_ptr_eq (&N_50, tree.root);
271 ck_assert (N_70.parent == &N_50); 274 ck_assert_ptr_eq (N_70.parent, &N_50);
272 ck_assert (N_50.right == &N_70); 275 ck_assert_ptr_eq (N_50.right, &N_70);
273 ck_assert (N_50.left == &tree.nil); 276 ck_assert_ptr_null (N_50.left);
274 ck_assert (N_70.right == &tree.nil); 277 ck_assert_ptr_null (N_70.right);
275 ck_assert (N_70.left == &tree.nil); 278 ck_assert_ptr_null (N_70.left);
276} 279}
277END_TEST 280END_TEST
278 281
@@ -284,20 +287,19 @@ START_TEST (test_insert_9)
284 * (50) (80) 287 * (50) (80)
285 */ 288 */
286 289
287 DEF_TEST_SETUP ();
288 interval_tree_insert (&tree, &N_50); 290 interval_tree_insert (&tree, &N_50);
289 interval_tree_insert (&tree, &N_70); 291 interval_tree_insert (&tree, &N_70);
290 interval_tree_insert (&tree, &N_80); 292 interval_tree_insert (&tree, &N_80);
291 ck_assert (N_50.color == ITREE_RED); 293 ck_assert (N_50.red);
292 ck_assert (N_70.color == ITREE_BLACK); 294 ck_assert (! N_70.red);
293 ck_assert (N_80.color == ITREE_RED); 295 ck_assert (N_80.red);
294 ck_assert (&N_70 == tree.root); 296 ck_assert_ptr_eq (&N_70, tree.root);
295 ck_assert (N_50.parent == &N_70); 297 ck_assert_ptr_eq (N_50.parent, &N_70);
296 ck_assert (N_70.right == &N_80); 298 ck_assert_ptr_eq (N_70.right, &N_80);
297 ck_assert (N_70.left == &N_50); 299 ck_assert_ptr_eq (N_70.left, &N_50);
298 ck_assert (N_80.right == &tree.nil); 300 ck_assert_ptr_null (N_80.right);
299 ck_assert (N_80.left == &tree.nil); 301 ck_assert_ptr_null (N_80.left);
300 ck_assert (N_80.parent == &N_70); 302 ck_assert_ptr_eq (N_80.parent, &N_70);
301} 303}
302END_TEST 304END_TEST
303 305
@@ -311,25 +313,24 @@ START_TEST (test_insert_10)
311 * (90) 313 * (90)
312 */ 314 */
313 315
314 DEF_TEST_SETUP ();
315 interval_tree_insert (&tree, &N_50); 316 interval_tree_insert (&tree, &N_50);
316 interval_tree_insert (&tree, &N_70); 317 interval_tree_insert (&tree, &N_70);
317 interval_tree_insert (&tree, &N_80); 318 interval_tree_insert (&tree, &N_80);
318 interval_tree_insert (&tree, &N_90); 319 interval_tree_insert (&tree, &N_90);
319 ck_assert (N_50.color == ITREE_BLACK); 320 ck_assert (! N_50.red);
320 ck_assert (N_70.color == ITREE_BLACK); 321 ck_assert (! N_70.red);
321 ck_assert (N_80.color == ITREE_BLACK); 322 ck_assert (! N_80.red);
322 ck_assert (N_90.color == ITREE_RED); 323 ck_assert (N_90.red);
323 ck_assert (&N_70 == tree.root); 324 ck_assert_ptr_eq (&N_70, tree.root);
324 ck_assert (N_50.parent == &N_70); 325 ck_assert_ptr_eq (N_50.parent, &N_70);
325 ck_assert (N_70.right == &N_80); 326 ck_assert_ptr_eq (N_70.right, &N_80);
326 ck_assert (N_70.left == &N_50); 327 ck_assert_ptr_eq (N_70.left, &N_50);
327 ck_assert (N_80.right == &N_90); 328 ck_assert_ptr_eq (N_80.right, &N_90);
328 ck_assert (N_80.left == &tree.nil); 329 ck_assert_ptr_null (N_80.left);
329 ck_assert (N_80.parent == &N_70); 330 ck_assert_ptr_eq (N_80.parent, &N_70);
330 ck_assert (N_90.parent == &N_80); 331 ck_assert_ptr_eq (N_90.parent, &N_80);
331 ck_assert (N_80.right == &N_90); 332 ck_assert_ptr_eq (N_80.right, &N_90);
332 ck_assert (N_90.left == &tree.nil); 333 ck_assert_ptr_null (N_90.left);
333} 334}
334END_TEST 335END_TEST
335 336
@@ -343,30 +344,29 @@ START_TEST (test_insert_11)
343 * (80) (90) 344 * (80) (90)
344 */ 345 */
345 346
346 DEF_TEST_SETUP ();
347 interval_tree_insert (&tree, &N_50); 347 interval_tree_insert (&tree, &N_50);
348 interval_tree_insert (&tree, &N_70); 348 interval_tree_insert (&tree, &N_70);
349 interval_tree_insert (&tree, &N_80); 349 interval_tree_insert (&tree, &N_80);
350 interval_tree_insert (&tree, &N_90); 350 interval_tree_insert (&tree, &N_90);
351 interval_tree_insert (&tree, &N_85); 351 interval_tree_insert (&tree, &N_85);
352 ck_assert (N_50.color == ITREE_BLACK); 352 ck_assert (! N_50.red);
353 ck_assert (N_70.color == ITREE_BLACK); 353 ck_assert (! N_70.red);
354 ck_assert (N_80.color == ITREE_RED); 354 ck_assert (N_80.red);
355 ck_assert (N_90.color == ITREE_RED); 355 ck_assert (N_90.red);
356 ck_assert (N_85.color == ITREE_BLACK); 356 ck_assert (! N_85.red);
357 ck_assert (&N_70 == tree.root); 357 ck_assert_ptr_eq (&N_70, tree.root);
358 ck_assert (N_50.parent == &N_70); 358 ck_assert_ptr_eq (N_50.parent, &N_70);
359 ck_assert (N_70.right == &N_85); 359 ck_assert_ptr_eq (N_70.right, &N_85);
360 ck_assert (N_70.left == &N_50); 360 ck_assert_ptr_eq (N_70.left, &N_50);
361 ck_assert (N_80.right == &tree.nil); 361 ck_assert_ptr_null (N_80.right);
362 ck_assert (N_80.left == &tree.nil); 362 ck_assert_ptr_null (N_80.left);
363 ck_assert (N_80.parent == &N_85); 363 ck_assert_ptr_eq (N_80.parent, &N_85);
364 ck_assert (N_90.parent == &N_85); 364 ck_assert_ptr_eq (N_90.parent, &N_85);
365 ck_assert (N_80.right == &tree.nil); 365 ck_assert_ptr_null (N_80.right);
366 ck_assert (N_90.left == &tree.nil); 366 ck_assert_ptr_null (N_90.left);
367 ck_assert (N_85.right == &N_90); 367 ck_assert_ptr_eq (N_85.right, &N_90);
368 ck_assert (N_85.left == &N_80); 368 ck_assert_ptr_eq (N_85.left, &N_80);
369 ck_assert (N_85.parent == &N_70); 369 ck_assert_ptr_eq (N_85.parent, &N_70);
370 370
371} 371}
372END_TEST 372END_TEST
@@ -383,139 +383,90 @@ START_TEST (test_insert_12)
383 * (95) 383 * (95)
384 */ 384 */
385 385
386 DEF_TEST_SETUP ();
387 interval_tree_insert (&tree, &N_50); 386 interval_tree_insert (&tree, &N_50);
388 interval_tree_insert (&tree, &N_70); 387 interval_tree_insert (&tree, &N_70);
389 interval_tree_insert (&tree, &N_80); 388 interval_tree_insert (&tree, &N_80);
390 interval_tree_insert (&tree, &N_90); 389 interval_tree_insert (&tree, &N_90);
391 interval_tree_insert (&tree, &N_85); 390 interval_tree_insert (&tree, &N_85);
392 interval_tree_insert (&tree, &N_95); 391 interval_tree_insert (&tree, &N_95);
393 ck_assert (N_50.color == ITREE_BLACK); 392 ck_assert (! N_50.red);
394 ck_assert (N_70.color == ITREE_BLACK); 393 ck_assert (! N_70.red);
395 ck_assert (N_80.color == ITREE_BLACK); 394 ck_assert (! N_80.red);
396 ck_assert (N_90.color == ITREE_BLACK); 395 ck_assert (! N_90.red);
397 ck_assert (N_85.color == ITREE_RED); 396 ck_assert (N_85.red);
398 ck_assert (N_95.color == ITREE_RED); 397 ck_assert (N_95.red);
399 ck_assert (&N_70 == tree.root); 398 ck_assert_ptr_eq (&N_70, tree.root);
400 ck_assert (N_50.parent == &N_70); 399 ck_assert_ptr_eq (N_50.parent, &N_70);
401 ck_assert (N_70.right == &N_85); 400 ck_assert_ptr_eq (N_70.right, &N_85);
402 ck_assert (N_70.left == &N_50); 401 ck_assert_ptr_eq (N_70.left, &N_50);
403 ck_assert (N_80.right == &tree.nil); 402 ck_assert_ptr_null (N_80.right);
404 ck_assert (N_80.left == &tree.nil); 403 ck_assert_ptr_null (N_80.left);
405 ck_assert (N_80.parent == &N_85); 404 ck_assert_ptr_eq (N_80.parent, &N_85);
406 ck_assert (N_90.parent == &N_85); 405 ck_assert_ptr_eq (N_90.parent, &N_85);
407 ck_assert (N_80.right == &tree.nil); 406 ck_assert_ptr_null (N_80.right);
408 ck_assert (N_90.left == &tree.nil); 407 ck_assert_ptr_null (N_90.left);
409 ck_assert (N_85.right == &N_90); 408 ck_assert_ptr_eq (N_85.right, &N_90);
410 ck_assert (N_85.left == &N_80); 409 ck_assert_ptr_eq (N_85.left, &N_80);
411 ck_assert (N_85.parent == &N_70); 410 ck_assert_ptr_eq (N_85.parent, &N_70);
412 ck_assert (N_95.parent == &N_90); 411 ck_assert_ptr_eq (N_95.parent, &N_90);
413 ck_assert (N_90.right == &N_95); 412 ck_assert_ptr_eq (N_90.right, &N_95);
414 ck_assert (N_95.left == &tree.nil); 413 ck_assert_ptr_null (N_95.left);
415} 414}
416END_TEST 415END_TEST
417 416
418#undef N_50
419#undef N_70
420#undef N_80
421#undef N_90
422#undef N_85
423#undef N_95
424#undef DEF_TEST_SETUP
425
426struct interval_tree*
427test_get_tree4 (struct interval_node **n)
428{
429 static struct interval_tree tree;
430 static struct interval_node nodes[4];
431 memset (&tree, 0, sizeof (struct interval_tree));
432 memset (&nodes, 0, 4 * sizeof (struct interval_node));
433 interval_tree_init (&tree);
434 for (int i = 0; i < 4; ++i)
435 {
436 nodes[i].begin = 10 * (i + 1);
437 nodes[i].end = nodes[i].begin;
438 interval_tree_insert (&tree, &nodes[i]);
439 }
440 *n = nodes;
441 return &tree;
442}
443
444static void
445shuffle (int *index, int n)
446{
447 for (int i = n - 1; i >= 0; --i)
448 {
449 int j = random () % (i + 1);
450 int h = index[j];
451 index[j] = index[i];
452 index[i] = h;
453 }
454}
455
456#define N_10 (nodes[0])
457#define N_20 (nodes[1])
458#define N_30 (nodes[2])
459#define N_40 (nodes[3])
460
461START_TEST (test_insert_13) 417START_TEST (test_insert_13)
462{ 418{
463 struct interval_node *nodes = NULL; 419 enum { N = 4 };
464 struct interval_tree *tree = test_get_tree4 (&nodes); 420 const int values[N] = {10, 20, 30, 40};
465 421 struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
466 422 interval_tree_init (&tree);
467 ck_assert (tree->root == &N_20); 423 for (int i = 0; i < N; ++i)
468 ck_assert (N_20.left == &N_10); 424 itree_insert (&tree, nodes[i], values[i], values[i]);
469 ck_assert (N_20.right == &N_30); 425
470 ck_assert (N_30.right == &N_40); 426 ck_assert_ptr_eq (tree.root, &N_20);
471 ck_assert (N_10.color == ITREE_BLACK); 427 ck_assert_ptr_eq (N_20.left, &N_10);
472 ck_assert (N_20.color == ITREE_BLACK); 428 ck_assert_ptr_eq (N_20.right, &N_30);
473 ck_assert (N_30.color == ITREE_BLACK); 429 ck_assert_ptr_eq (N_30.right, &N_40);
474 ck_assert (N_40.color == ITREE_RED); 430 ck_assert (! N_10.red);
431 ck_assert (! N_20.red);
432 ck_assert (! N_30.red);
433 ck_assert (N_40.red);
475} 434}
476END_TEST 435END_TEST
477 436
478START_TEST (test_insert_14) 437START_TEST (test_insert_14)
479{ 438{
480 struct interval_tree tree; 439 enum { N = 3 };
481 struct interval_node nodes[3]; 440 struct itree_node nodes[N];
482 441 interval_tree_init (&tree);
483 nodes[0].begin = nodes[1].begin = nodes[2].begin = 10;
484 nodes[0].end = nodes[1].end = nodes[2].end = 10;
485 442
486 for (int i = 0; i < 3; ++i) 443 for (int i = 0; i < N; ++i)
487 interval_tree_insert (&tree, &nodes[i]); 444 itree_insert (&tree, &nodes[i], 10, 10);
488 for (int i = 0; i < 3; ++i) 445 for (int i = 0; i < N; ++i)
489 ck_assert (interval_tree_contains (&tree, &nodes[i])); 446 ck_assert (interval_tree_contains (&tree, &nodes[i]));
490} 447}
491END_TEST 448END_TEST
492 449
493
494
495 450
496/* +===================================================================================+ 451/* +===================================================================================+
497 * | Remove 452 * | Remove
498 * +===================================================================================+ */ 453 * +===================================================================================+ */
499 454
500#define A (nodes[0])
501#define B (nodes[1])
502#define C (nodes[2])
503#define D (nodes[3])
504#define E (nodes[4])
505
506/* Creating proper test trees for the formal tests via insertions is 455/* Creating proper test trees for the formal tests via insertions is
507 way to tedious, so we just fake it and only test the 456 way too tedious, so we just fake it and only test the
508 fix-routine. */ 457 fix-routine. */
509#define DEF_TEST_SETUP() \ 458static void
510 struct interval_tree tree; \ 459test_remove1_setup (void)
511 struct interval_node nodes[5]; \ 460{
512 interval_tree_init (&tree); \ 461 interval_tree_init (&tree);
513 tree.root = &B; \ 462 tree.root = &B;
514 A.parent = &B; B.parent = &tree.nil; C.parent = &D; \ 463 A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
515 D.parent = &B; E.parent = &D; \ 464 A.left = A.right = C.left = C.right = E.left = E.right = NULL;
516 A.left = A.right = C.left = C.right = &tree.nil; \ 465 B.left = &A; B.right = &D;
517 E.left = E.right = &tree.nil; \ 466 D.left = &C; D.right = &E;
518 B.left = &A; B.right = &D; D.left = &C; D.right = &E \ 467 A.offset = B.offset = C.offset = D.offset = E.offset = 0;
468 A.otick = B.otick = C.otick = D.otick = E.otick = tree.otick;
469}
519 470
520/* 1.a -> 2.a 471/* 1.a -> 2.a
521 * [B] 472 * [B]
@@ -525,126 +476,106 @@ END_TEST
525 * [C] [E] 476 * [C] [E]
526 */ 477 */
527 478
528
529START_TEST (test_remove_1) 479START_TEST (test_remove_1)
530{ 480{
531 DEF_TEST_SETUP (); 481 B.red = A.red = C.red = E.red = false;
532 B.color = A.color = C.color = E.color = ITREE_BLACK; 482 D.red = true;
533 D.color = ITREE_RED; 483 interval_tree_remove_fix (&tree, &A, &B);
534 interval_tree_remove_fix (&tree, &A); 484
535 485 ck_assert (! A.red);
536 ck_assert (A.color == ITREE_BLACK); 486 ck_assert (! B.red);
537 ck_assert (B.color == ITREE_BLACK); 487 ck_assert (C.red);
538 ck_assert (C.color == ITREE_RED); 488 ck_assert (! D.red);
539 ck_assert (D.color == ITREE_BLACK); 489 ck_assert (! E.red);
540 ck_assert (E.color == ITREE_BLACK); 490 ck_assert_ptr_eq (A.parent, &B);
541 ck_assert (A.parent == &B); 491 ck_assert_ptr_eq (B.left, &A);
542 ck_assert (B.left == &A); 492 ck_assert_ptr_eq (B.right, &C);
543 ck_assert (B.right == &C); 493 ck_assert_ptr_eq (C.parent, &B);
544 ck_assert (C.parent == &B); 494 ck_assert_ptr_eq (E.parent, &D);
545 ck_assert (E.parent == &D); 495 ck_assert_ptr_eq (D.right, &E);
546 ck_assert (D.right == &E); 496 ck_assert_ptr_eq (D.left, &B);
547 ck_assert (D.left == &B); 497 ck_assert_ptr_eq (tree.root, &D);
548 ck_assert (tree.root == &D);
549} 498}
550END_TEST 499END_TEST
551 500
552/* 2.a */ 501/* 2.a */
553START_TEST (test_remove_2) 502START_TEST (test_remove_2)
554{ 503{
555 DEF_TEST_SETUP (); 504 B.red = D.red = A.red = C.red = E.red = false;
556 B.color = D.color = A.color = C.color = E.color = ITREE_BLACK; 505 interval_tree_remove_fix (&tree, &A, &B);
557 interval_tree_remove_fix (&tree, &A); 506
558 507 ck_assert (! A.red);
559 ck_assert (A.color == ITREE_BLACK); 508 ck_assert (! B.red);
560 ck_assert (B.color == ITREE_BLACK); 509 ck_assert (! C.red);
561 ck_assert (C.color == ITREE_BLACK); 510 ck_assert (D.red);
562 ck_assert (D.color == ITREE_RED); 511 ck_assert (! E.red);
563 ck_assert (E.color == ITREE_BLACK); 512 ck_assert_ptr_eq (A.parent, &B);
564 ck_assert (A.parent == &B); 513 ck_assert_ptr_eq (B.left, &A);
565 ck_assert (B.left == &A); 514 ck_assert_ptr_eq (B.right, &D);
566 ck_assert (B.right == &D); 515 ck_assert_ptr_eq (C.parent, &D);
567 ck_assert (C.parent == &D); 516 ck_assert_ptr_eq (E.parent, &D);
568 ck_assert (E.parent == &D); 517 ck_assert_ptr_eq (tree.root, &B);
569 ck_assert (tree.root == &B);
570} 518}
571END_TEST 519END_TEST
572 520
573/* 3.a -> 4.a*/ 521/* 3.a -> 4.a */
574START_TEST (test_remove_3) 522START_TEST (test_remove_3)
575{ 523{
576 DEF_TEST_SETUP (); 524 D.red = A.red = E.red = false;
577 D.color = A.color = E.color = ITREE_BLACK; 525 B.red = C.red = true;
578 B.color = C.color = ITREE_RED; 526 interval_tree_remove_fix (&tree, &A, &B);
579 interval_tree_remove_fix (&tree, &A); 527
580 528 ck_assert (! A.red);
581 ck_assert (A.color == ITREE_BLACK); 529 ck_assert (! B.red);
582 ck_assert (B.color == ITREE_BLACK); 530 ck_assert (! C.red);
583 ck_assert (C.color == ITREE_BLACK); 531 ck_assert (! D.red);
584 ck_assert (D.color == ITREE_BLACK); 532 ck_assert (! E.red);
585 ck_assert (E.color == ITREE_BLACK); 533 ck_assert_ptr_eq (A.parent, &B);
586 ck_assert (A.parent == &B); 534 ck_assert_ptr_eq (B.left, &A);
587 ck_assert (B.left == &A); 535 ck_assert_ptr_null (B.right);
588 ck_assert (B.right == &tree.nil); 536 ck_assert_ptr_eq (&C, tree.root);
589 ck_assert (&C == tree.root); 537 ck_assert_ptr_eq (C.left, &B);
590 ck_assert (C.left == &B); 538 ck_assert_ptr_eq (C.right, &D);
591 ck_assert (C.right == &D); 539 ck_assert_ptr_eq (E.parent, &D);
592 ck_assert (E.parent == &D); 540 ck_assert_ptr_null (D.left);
593 ck_assert (D.left == &tree.nil);
594
595} 541}
596END_TEST 542END_TEST
597 543
598/* 4.a */ 544/* 4.a */
599START_TEST (test_remove_4) 545START_TEST (test_remove_4)
600{ 546{
601 DEF_TEST_SETUP (); 547 B.red = C.red = E.red = true;
602 B.color = C.color = E.color = ITREE_RED; 548 A.red = D.red = false;
603 A.color = D.color = ITREE_BLACK; 549 interval_tree_remove_fix (&tree, &A, &B);
604 interval_tree_remove_fix (&tree, &A); 550
605 551 ck_assert (! A.red);
606 ck_assert (A.color == ITREE_BLACK); 552 ck_assert (! B.red);
607 ck_assert (B.color == ITREE_BLACK); 553 ck_assert (C.red);
608 ck_assert (C.color == ITREE_RED); 554 ck_assert (! D.red);
609 ck_assert (D.color == ITREE_BLACK); 555 ck_assert (! E.red);
610 ck_assert (E.color == ITREE_BLACK); 556 ck_assert_ptr_eq (A.parent, &B);
611 ck_assert (A.parent == &B); 557 ck_assert_ptr_eq (B.left, &A);
612 ck_assert (B.left == &A); 558 ck_assert_ptr_eq (B.right, &C);
613 ck_assert (B.right == &C); 559 ck_assert_ptr_eq (C.parent, &B);
614 ck_assert (C.parent == &B); 560 ck_assert_ptr_eq (E.parent, &D);
615 ck_assert (E.parent == &D); 561 ck_assert_ptr_eq (tree.root, &D);
616 ck_assert (tree.root == &D);
617} 562}
618END_TEST 563END_TEST
619 564
620
621#undef A
622#undef B
623#undef C
624#undef D
625#undef E
626#undef DEF_TEST_SETUP
627
628 565
629 566
630/* These are the mirrored cases. */ 567/* These are the mirrored cases. */
631 568
632#define A (nodes[0]) 569static void
633#define B (nodes[1]) 570test_remove2_setup (void)
634#define C (nodes[2]) 571{
635#define D (nodes[3]) 572 interval_tree_init (&tree);
636#define E (nodes[4]) 573 tree.root = &B;
637 574 A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
638#define DEF_TEST_SETUP() \ 575 A.right = A.left = C.right = C.left = E.right = E.left = NULL;
639 struct interval_tree tree; \ 576 B.right = &A; B.left = &D;
640 struct interval_node nodes[5]; \ 577 D.right = &C; D.left = &E;
641 interval_tree_init (&tree); \ 578}
642 tree.root = &B; \
643 A.parent = &B; B.parent = &tree.nil; C.parent = &D; \
644 D.parent = &B; E.parent = &D; \
645 A.right = A.left = C.right = C.left = &tree.nil; \
646 E.right = E.left = &tree.nil; \
647 B.right = &A; B.left = &D; D.right = &C; D.left = &E \
648 579
649/* 1.b -> 2.b 580/* 1.b -> 2.b
650 * [B] 581 * [B]
@@ -654,161 +585,159 @@ END_TEST
654 * [C] [E] 585 * [C] [E]
655 */ 586 */
656 587
657
658START_TEST (test_remove_5) 588START_TEST (test_remove_5)
659{ 589{
660 DEF_TEST_SETUP (); 590 B.red = A.red = C.red = E.red = false;
661 B.color = A.color = C.color = E.color = ITREE_BLACK; 591 D.red = true;
662 D.color = ITREE_RED; 592 interval_tree_remove_fix (&tree, &A, &B);
663 interval_tree_remove_fix (&tree, &A); 593
664 594 ck_assert (! A.red);
665 ck_assert (A.color == ITREE_BLACK); 595 ck_assert (! B.red);
666 ck_assert (B.color == ITREE_BLACK); 596 ck_assert (C.red);
667 ck_assert (C.color == ITREE_RED); 597 ck_assert (! D.red);
668 ck_assert (D.color == ITREE_BLACK); 598 ck_assert (! E.red);
669 ck_assert (E.color == ITREE_BLACK); 599 ck_assert_ptr_eq (A.parent, &B);
670 ck_assert (A.parent == &B); 600 ck_assert_ptr_eq (B.right, &A);
671 ck_assert (B.right == &A); 601 ck_assert_ptr_eq (B.left, &C);
672 ck_assert (B.left == &C); 602 ck_assert_ptr_eq (C.parent, &B);
673 ck_assert (C.parent == &B); 603 ck_assert_ptr_eq (E.parent, &D);
674 ck_assert (E.parent == &D); 604 ck_assert_ptr_eq (D.left, &E);
675 ck_assert (D.left == &E); 605 ck_assert_ptr_eq (D.right, &B);
676 ck_assert (D.right == &B); 606 ck_assert_ptr_eq (tree.root, &D);
677 ck_assert (tree.root == &D);
678} 607}
679END_TEST 608END_TEST
680 609
681/* 2.b */ 610/* 2.b */
682START_TEST (test_remove_6) 611START_TEST (test_remove_6)
683{ 612{
684 DEF_TEST_SETUP (); 613 B.red = D.red = A.red = C.red = E.red = false;
685 B.color = D.color = A.color = C.color = E.color = ITREE_BLACK; 614 interval_tree_remove_fix (&tree, &A, &B);
686 interval_tree_remove_fix (&tree, &A); 615
687 616 ck_assert (! A.red);
688 ck_assert (A.color == ITREE_BLACK); 617 ck_assert (! B.red);
689 ck_assert (B.color == ITREE_BLACK); 618 ck_assert (! C.red);
690 ck_assert (C.color == ITREE_BLACK); 619 ck_assert (D.red);
691 ck_assert (D.color == ITREE_RED); 620 ck_assert (! E.red);
692 ck_assert (E.color == ITREE_BLACK); 621 ck_assert_ptr_eq (A.parent, &B);
693 ck_assert (A.parent == &B); 622 ck_assert_ptr_eq (B.right, &A);
694 ck_assert (B.right == &A); 623 ck_assert_ptr_eq (B.left, &D);
695 ck_assert (B.left == &D); 624 ck_assert_ptr_eq (C.parent, &D);
696 ck_assert (C.parent == &D); 625 ck_assert_ptr_eq (E.parent, &D);
697 ck_assert (E.parent == &D); 626 ck_assert_ptr_eq (tree.root, &B);
698 ck_assert (tree.root == &B);
699} 627}
700END_TEST 628END_TEST
701 629
702/* 3.b -> 4.b*/ 630/* 3.b -> 4.b */
703START_TEST (test_remove_7) 631START_TEST (test_remove_7)
704{ 632{
705 DEF_TEST_SETUP (); 633 D.red = A.red = E.red = false;
706 D.color = A.color = E.color = ITREE_BLACK; 634 B.red = C.red = true;
707 B.color = C.color = ITREE_RED; 635 interval_tree_remove_fix (&tree, &A, &B);
708 interval_tree_remove_fix (&tree, &A); 636
709 637 ck_assert (! A.red);
710 ck_assert (A.color == ITREE_BLACK); 638 ck_assert (! B.red);
711 ck_assert (B.color == ITREE_BLACK); 639 ck_assert (! C.red);
712 ck_assert (C.color == ITREE_BLACK); 640 ck_assert (! D.red);
713 ck_assert (D.color == ITREE_BLACK); 641 ck_assert (! E.red);
714 ck_assert (E.color == ITREE_BLACK); 642 ck_assert_ptr_eq (A.parent, &B);
715 ck_assert (A.parent == &B); 643 ck_assert_ptr_eq (B.right, &A);
716 ck_assert (B.right == &A); 644 ck_assert_ptr_null (B.left);
717 ck_assert (B.left == &tree.nil); 645 ck_assert_ptr_eq (&C, tree.root);
718 ck_assert (&C == tree.root); 646 ck_assert_ptr_eq (C.right, &B);
719 ck_assert (C.right == &B); 647 ck_assert_ptr_eq (C.left, &D);
720 ck_assert (C.left == &D); 648 ck_assert_ptr_eq (E.parent, &D);
721 ck_assert (E.parent == &D); 649 ck_assert_ptr_null (D.right);
722 ck_assert (D.right == &tree.nil);
723
724} 650}
725END_TEST 651END_TEST
726 652
727/* 4.b */ 653/* 4.b */
728START_TEST (test_remove_8) 654START_TEST (test_remove_8)
729{ 655{
730 DEF_TEST_SETUP (); 656 B.red = C.red = E.red = true;
731 B.color = C.color = E.color = ITREE_RED; 657 A.red = D.red = false;
732 A.color = D.color = ITREE_BLACK; 658 interval_tree_remove_fix (&tree, &A, &B);
733 interval_tree_remove_fix (&tree, &A); 659
734 660 ck_assert (! A.red);
735 ck_assert (A.color == ITREE_BLACK); 661 ck_assert (! B.red);
736 ck_assert (B.color == ITREE_BLACK); 662 ck_assert (C.red);
737 ck_assert (C.color == ITREE_RED); 663 ck_assert (! D.red);
738 ck_assert (D.color == ITREE_BLACK); 664 ck_assert (! E.red);
739 ck_assert (E.color == ITREE_BLACK); 665 ck_assert_ptr_eq (A.parent, &B);
740 ck_assert (A.parent == &B); 666 ck_assert_ptr_eq (B.right, &A);
741 ck_assert (B.right == &A); 667 ck_assert_ptr_eq (B.left, &C);
742 ck_assert (B.left == &C); 668 ck_assert_ptr_eq (C.parent, &B);
743 ck_assert (C.parent == &B); 669 ck_assert_ptr_eq (E.parent, &D);
744 ck_assert (E.parent == &D); 670 ck_assert_ptr_eq (tree.root, &D);
745 ck_assert (tree.root == &D);
746} 671}
747END_TEST 672END_TEST
748 673
749
750#undef A
751#undef B
752#undef C
753#undef D
754#undef E
755#undef DEF_TEST_SETUP
756
757
758START_TEST (test_remove_9) 674START_TEST (test_remove_9)
759{ 675{
760 struct interval_node *nodes = NULL; 676 enum { N = 4 };
761 struct interval_tree *tree = test_get_tree4 (&nodes); 677 const int values[N] = {10, 20, 30, 40};
678 struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
679 interval_tree_init (&tree);
680 for (int i = 0; i < N; ++i)
681 itree_insert (&tree, nodes[i], values[i], values[i]);
762 682
763 ck_assert (tree->root == &N_20); 683 ck_assert (tree.root == &N_20);
764 ck_assert (N_20.left == &N_10); 684 ck_assert (N_20.left == &N_10);
765 ck_assert (N_20.right == &N_30); 685 ck_assert (N_20.right == &N_30);
766 ck_assert (N_30.right == &N_40); 686 ck_assert (N_30.right == &N_40);
767 ck_assert (N_20.color == ITREE_BLACK); 687 ck_assert (! N_20.red);
768 ck_assert (N_10.color == ITREE_BLACK); 688 ck_assert (! N_10.red);
769 ck_assert (N_30.color == ITREE_BLACK); 689 ck_assert (! N_30.red);
770 ck_assert (N_40.color == ITREE_RED); 690 ck_assert (N_40.red);
771 691
772 interval_tree_remove (tree, &N_10); 692 itree_remove (&tree, &N_10);
773 693
774 ck_assert (tree->root == &N_30); 694 ck_assert_ptr_eq (tree.root, &N_30);
775 ck_assert (N_30.parent == &tree->nil); 695 ck_assert_ptr_null (N_30.parent);
776 ck_assert (N_30.left == &N_20); 696 ck_assert_ptr_eq (N_30.left, &N_20);
777 ck_assert (N_30.right == &N_40); 697 ck_assert_ptr_eq (N_30.right, &N_40);
778 ck_assert (N_20.color == ITREE_BLACK); 698 ck_assert (! N_20.red);
779 ck_assert (N_30.color == ITREE_BLACK); 699 ck_assert (! N_30.red);
780 ck_assert (N_40.color == ITREE_BLACK); 700 ck_assert (! N_40.red);
781} 701}
782END_TEST 702END_TEST
783 703
784#define N 3 704static void
705shuffle (int *index, int n)
706{
707 for (int i = n - 1; i >= 0; --i)
708 {
709 int j = random () % (i + 1);
710 int h = index[j];
711 index[j] = index[i];
712 index[i] = h;
713 }
714}
785 715
786START_TEST (test_remove_10) 716START_TEST (test_remove_10)
787{ 717{
788 struct interval_tree tree; 718 enum { N = 3 };
789 struct interval_node nodes[N];
790 int index[N]; 719 int index[N];
791 720 for (int i = 0; i < N; ++i)
721 index[i] = i;
792 srand (42); 722 srand (42);
723 shuffle (index, N);
724
793 interval_tree_init (&tree); 725 interval_tree_init (&tree);
726 struct itree_node nodes[N];
794 for (int i = 0; i < N; ++i) 727 for (int i = 0; i < N; ++i)
795 { 728 {
796 nodes[i].begin = (i + 1) * 10; 729 ptrdiff_t pos = (i + 1) * 10;
797 nodes[i].end = nodes[i].begin + 1; 730 itree_insert (&tree, &nodes[index[i]], pos, pos + 1);
798 index[i] = i;
799 } 731 }
800 shuffle (index, N);
801 for (int i = 0; i < N; ++i)
802 interval_tree_insert (&tree, &nodes[index[i]]);
803 732
804 shuffle (index, N); 733 shuffle (index, N);
805 for (int i = 0; i < N; ++i) 734 for (int i = 0; i < N; ++i)
806 { 735 {
807 ck_assert (interval_tree_contains (&tree, &nodes[index[i]])); 736 ck_assert (interval_tree_contains (&tree, &nodes[index[i]]));
808 interval_tree_remove (&tree, &nodes[index[i]]); 737 itree_remove (&tree, &nodes[index[i]]);
809 } 738 }
810 ck_assert (tree.root == &tree.nil); 739 ck_assert_ptr_null (tree.root);
811 ck_assert (tree.size == 0); 740 ck_assert_int_eq (tree.size, 0);
812} 741}
813END_TEST 742END_TEST
814 743
@@ -819,70 +748,57 @@ END_TEST
819 748
820START_TEST (test_generator_1) 749START_TEST (test_generator_1)
821{ 750{
822 struct interval_tree tree; 751 struct itree_node node, *n;
823 struct interval_node node, *n; 752 struct itree_iterator *g;
824 struct interval_generator *g;
825 interval_tree_init (&tree); 753 interval_tree_init (&tree);
826 node.begin = 10; 754
827 node.end = 20; 755 itree_insert (&tree, &node, 10, 20);
828 interval_tree_insert (&tree, &node); 756 g = itree_iterator_start (&tree, 0, 30, ITREE_ASCENDING, NULL, 0);
829 g = interval_generator_create (&tree); 757 n = itree_iterator_next (g);
830 interval_generator_reset (g, 0, 30, ITREE_ASCENDING); 758 ck_assert_ptr_eq (n, &node);
831 n = interval_generator_next (g); 759 ck_assert_int_eq (n->begin, 10);
832 ck_assert (n == &node); 760 ck_assert_int_eq (n->end, 20);
833 ck_assert (n->begin == 10 && n->end == 20); 761 ck_assert_ptr_null (itree_iterator_next (g));
834 ck_assert (interval_generator_next (g) == NULL); 762 ck_assert_ptr_null (itree_iterator_next (g));
835 ck_assert (interval_generator_next (g) == NULL); 763 ck_assert_ptr_null (itree_iterator_next (g));
836 ck_assert (interval_generator_next (g) == NULL); 764 itree_iterator_finish (g);
837 interval_generator_destroy (g); 765
838 766 g = itree_iterator_start (&tree, 30, 50, ITREE_ASCENDING, NULL, 0);
839 g = interval_generator_create (&tree); 767 ck_assert_ptr_null (itree_iterator_next (g));
840 interval_generator_reset (g, 30, 50, ITREE_ASCENDING); 768 ck_assert_ptr_null (itree_iterator_next (g));
841 ck_assert (interval_generator_next (g) == NULL); 769 ck_assert_ptr_null (itree_iterator_next (g));
842 ck_assert (interval_generator_next (g) == NULL); 770 itree_iterator_finish (g);
843 ck_assert (interval_generator_next (g) == NULL);
844 interval_generator_destroy (g);
845} 771}
846END_TEST 772END_TEST
847 773
848void 774static void
849test_check_generator (struct interval_tree *tree, 775test_check_generator (struct itree_tree *tree,
850 ptrdiff_t begin, ptrdiff_t end, 776 ptrdiff_t begin, ptrdiff_t end,
851 int n, ...) 777 int n, ...)
852{ 778{
853 va_list ap; 779 va_list ap;
854 struct interval_generator *g = interval_generator_create (tree); 780 struct itree_iterator *g =
855 interval_generator_reset (g, begin, end, ITREE_ASCENDING); 781 itree_iterator_start (tree, begin, end, ITREE_ASCENDING, NULL, 0);
856 782
857 va_start (ap, n); 783 va_start (ap, n);
858 for (int i = 0; i < n; ++i) 784 for (int i = 0; i < n; ++i)
859 { 785 {
860 ptrdiff_t begin = va_arg (ap, ptrdiff_t); 786 struct itree_node *node = itree_iterator_next (g);
861 struct interval_node *node = interval_generator_next (g); 787 ck_assert_ptr_nonnull (node);
862 ck_assert (node); 788 ck_assert_int_eq (node->begin, va_arg (ap, ptrdiff_t));
863 ck_assert_int_eq (node->begin, begin);
864 } 789 }
865 va_end (ap); 790 va_end (ap);
866 ck_assert (! interval_generator_next (g)); 791 ck_assert_ptr_null (itree_iterator_next (g));
867 ck_assert (! interval_generator_next (g)); 792 ck_assert_ptr_null (itree_iterator_next (g));
868 interval_generator_destroy (g); 793 itree_iterator_finish (g);
869} 794}
870 795
871#define DEF_TEST_SETUP() \
872
873
874START_TEST (test_generator_2) 796START_TEST (test_generator_2)
875{ 797{
876 struct interval_tree tree;
877 struct interval_node nodes[3];
878
879 interval_tree_init (&tree); 798 interval_tree_init (&tree);
880 799 struct itree_node nodes[3];
881 for (int i = 0; i < 3; ++i) { 800 for (int i = 0; i < 3; ++i)
882 nodes[i].begin = 10 * (i + 1); 801 itree_insert (&tree, &nodes[i], 10 * (i + 1), 10 * (i + 2));
883 nodes[i].end = 10 * (i + 2);
884 interval_tree_insert (&tree, &nodes[i]);
885 }
886 802
887 test_check_generator (&tree, 0, 50, 3, 803 test_check_generator (&tree, 0, 50, 3,
888 10, 20, 30); 804 10, 20, 30);
@@ -902,72 +818,56 @@ START_TEST (test_generator_2)
902} 818}
903END_TEST 819END_TEST
904 820
905 821static void
906struct interval_node* 822test_create_tree (struct itree_node *nodes, int n, bool doshuffle)
907test_create_tree (struct interval_tree *tree, int n,
908 bool doshuffle, ...)
909{ 823{
910 va_list ap;
911 struct interval_node *nodes = calloc (n, sizeof (struct interval_node));
912 int *index = calloc (n, sizeof (int)); 824 int *index = calloc (n, sizeof (int));
913
914 interval_tree_init (tree);
915 va_start (ap, doshuffle);
916 for (int i = 0; i < n; ++i) 825 for (int i = 0; i < n; ++i)
826 index[i] = i;
827 if (doshuffle)
917 { 828 {
918 ptrdiff_t begin = va_arg (ap, ptrdiff_t); 829 srand (42);
919 ptrdiff_t end = va_arg (ap, ptrdiff_t); 830 shuffle (index, n);
920 nodes[i].begin = begin;
921 nodes[i].end = end;
922 index[i] = i;
923 } 831 }
924 va_end (ap); 832
925 srand (42); 833 interval_tree_init (&tree);
926 if (doshuffle)
927 shuffle (index, n);
928 for (int i = 0; i < n; ++i) 834 for (int i = 0; i < n; ++i)
929 interval_tree_insert (tree, &nodes[index[i]]); 835 {
836 struct itree_node *node = &nodes[index[i]];
837 itree_insert (&tree, node, node->begin, node->end);
838 }
930 free (index); 839 free (index);
931
932 return nodes;
933} 840}
934 841
935START_TEST (test_generator_3) 842START_TEST (test_generator_3)
936{ 843{
937 struct interval_tree tree; 844 enum { N = 3 };
938 struct interval_node *nodes = NULL; 845 struct itree_node nodes[N] = {{.begin = 10, .end = 10},
939 846 {.begin = 10, .end = 10},
940 nodes = test_create_tree (&tree, 3, true, 847 {.begin = 10, .end = 10}};
941 10, 10, 848 test_create_tree (nodes, N, true);
942 10, 10,
943 10, 10);
944 test_check_generator (&tree, 0, 10, 0); 849 test_check_generator (&tree, 0, 10, 0);
945 test_check_generator (&tree, 10, 10, 3, 10, 10, 10); 850 test_check_generator (&tree, 10, 10, 3,
946 test_check_generator (&tree, 10, 20, 3, 10, 10, 10); 851 10, 10, 10);
947 free (nodes); 852 test_check_generator (&tree, 10, 20, 3,
853 10, 10, 10);
948} 854}
949END_TEST 855END_TEST
950 856
951#define FOREACH(n, g) \
952 for ((n) = interval_generator_next (g); (n) != NULL; \
953 (n) = interval_generator_next (g))
954
955START_TEST (test_generator_5) 857START_TEST (test_generator_5)
956{ 858{
957 struct interval_tree tree; 859 enum { N = 4 };
958 struct interval_node *nodes; 860 struct itree_node nodes[N] = {{.begin = 10, .end = 30},
959 struct interval_generator *g; 861 {.begin = 20, .end = 40},
960 nodes = test_create_tree (&tree, 4, false, 862 {.begin = 30, .end = 50},
961 10, 30, 863 {.begin = 40, .end = 60}};
962 20, 40, 864 test_create_tree (nodes, N, false);
963 30, 50, 865 struct itree_iterator *g =
964 40, 60); 866 itree_iterator_start (&tree, 0, 100, ITREE_PRE_ORDER, NULL, 0);
965 g = interval_generator_create (&tree); 867 for (int i = 0; i < N; ++i)
966 interval_generator_reset (g, 0, 100, ITREE_PRE_ORDER);
967 for (int i = 0; i < 4; ++i)
968 { 868 {
969 struct interval_node *n = interval_generator_next (g); 869 struct itree_node *n = itree_iterator_next (g);
970 ck_assert (n); 870 ck_assert_ptr_nonnull (n);
971 switch (i) 871 switch (i)
972 { 872 {
973 case 0: ck_assert_int_eq (20, n->begin); break; 873 case 0: ck_assert_int_eq (20, n->begin); break;
@@ -976,28 +876,24 @@ START_TEST (test_generator_5)
976 case 3: ck_assert_int_eq (40, n->begin); break; 876 case 3: ck_assert_int_eq (40, n->begin); break;
977 } 877 }
978 } 878 }
979 interval_generator_destroy (g); 879 itree_iterator_finish (g);
980 free (nodes);
981
982} 880}
983END_TEST 881END_TEST
984 882
985START_TEST (test_generator_6) 883START_TEST (test_generator_6)
986{ 884{
987 struct interval_tree tree; 885 enum { N = 4 };
988 struct interval_node *nodes; 886 struct itree_node nodes[N] = {{.begin = 10, .end = 30},
989 struct interval_generator *g; 887 {.begin = 20, .end = 40},
990 nodes = test_create_tree (&tree, 4, true, 888 {.begin = 30, .end = 50},
991 10, 30, 889 {.begin = 40, .end = 60}};
992 20, 40, 890 test_create_tree (nodes, N, true);
993 30, 50, 891 struct itree_iterator *g =
994 40, 60); 892 itree_iterator_start (&tree, 0, 100, ITREE_ASCENDING, NULL, 0);
995 g = interval_generator_create (&tree); 893 for (int i = 0; i < N; ++i)
996 interval_generator_reset (g, 0, 100, ITREE_ASCENDING);
997 for (int i = 0; i < 4; ++i)
998 { 894 {
999 struct interval_node *n = interval_generator_next (g); 895 struct itree_node *n = itree_iterator_next (g);
1000 ck_assert (n); 896 ck_assert_ptr_nonnull (n);
1001 switch (i) 897 switch (i)
1002 { 898 {
1003 case 0: ck_assert_int_eq (10, n->begin); break; 899 case 0: ck_assert_int_eq (10, n->begin); break;
@@ -1006,28 +902,24 @@ START_TEST (test_generator_6)
1006 case 3: ck_assert_int_eq (40, n->begin); break; 902 case 3: ck_assert_int_eq (40, n->begin); break;
1007 } 903 }
1008 } 904 }
1009 interval_generator_destroy (g); 905 itree_iterator_finish (g);
1010 free (nodes);
1011
1012} 906}
1013END_TEST 907END_TEST
1014 908
1015START_TEST (test_generator_7) 909START_TEST (test_generator_7)
1016{ 910{
1017 struct interval_tree tree; 911 enum { N = 4 };
1018 struct interval_node *nodes; 912 struct itree_node nodes[N] = {{.begin = 10, .end = 30},
1019 struct interval_generator *g; 913 {.begin = 20, .end = 40},
1020 nodes = test_create_tree (&tree, 4, true, 914 {.begin = 30, .end = 50},
1021 10, 30, 915 {.begin = 40, .end = 60}};
1022 20, 40, 916 test_create_tree (nodes, N, true);
1023 30, 50, 917 struct itree_iterator *g =
1024 40, 60); 918 itree_iterator_start (&tree, 0, 100, ITREE_DESCENDING, NULL, 0);
1025 g = interval_generator_create (&tree); 919 for (int i = 0; i < N; ++i)
1026 interval_generator_reset (g, 0, 100, ITREE_DESCENDING);
1027 for (int i = 0; i < 4; ++i)
1028 { 920 {
1029 struct interval_node *n = interval_generator_next (g); 921 struct itree_node *n = itree_iterator_next (g);
1030 ck_assert (n); 922 ck_assert_ptr_nonnull (n);
1031 switch (i) 923 switch (i)
1032 { 924 {
1033 case 0: ck_assert_int_eq (40, n->begin); break; 925 case 0: ck_assert_int_eq (40, n->begin); break;
@@ -1036,48 +928,41 @@ START_TEST (test_generator_7)
1036 case 3: ck_assert_int_eq (10, n->begin); break; 928 case 3: ck_assert_int_eq (10, n->begin); break;
1037 } 929 }
1038 } 930 }
1039 interval_generator_destroy (g); 931 itree_iterator_finish (g);
1040 free (nodes);
1041
1042} 932}
1043END_TEST 933END_TEST
1044 934
1045START_TEST (test_generator_8) 935START_TEST (test_generator_8)
1046{ 936{
1047 struct interval_tree tree; 937 enum { N = 2 };
1048 struct interval_node *nodes, *n; 938 struct itree_node nodes[N] = {{.begin = 20, .end = 30},
1049 struct interval_generator *g; 939 {.begin = 40, .end = 50}};
1050 nodes = test_create_tree (&tree, 2, false, 940 test_create_tree (nodes, N, false);
1051 20, 30, 941 struct itree_iterator *g =
1052 40, 50); 942 itree_iterator_start (&tree, 1, 60, ITREE_DESCENDING, NULL, 0);
1053 g = interval_generator_create (&tree); 943 struct itree_node *n = itree_iterator_next (g);
1054 interval_generator_reset (g, 1, 60, ITREE_DESCENDING);
1055 n = interval_generator_next (g);
1056 ck_assert_int_eq (n->begin, 40); 944 ck_assert_int_eq (n->begin, 40);
1057 interval_generator_narrow (g, 50, 60); 945 itree_iterator_narrow (g, 50, 60);
1058 n = interval_generator_next (g); 946 n = itree_iterator_next (g);
1059 ck_assert (n == NULL); 947 ck_assert_ptr_null (n);
1060 free (nodes); 948 itree_iterator_finish (g);
1061} 949}
1062END_TEST 950END_TEST
1063 951
1064
1065START_TEST (test_generator_9) 952START_TEST (test_generator_9)
1066{ 953{
1067 struct interval_tree tree; 954 enum { N = 2 };
1068 struct interval_node *nodes, *n; 955 struct itree_node nodes[N] = {{.begin = 25, .end = 25},
1069 struct interval_generator *g; 956 {.begin = 20, .end = 30}};
1070 nodes = test_create_tree (&tree, 2, false, 957 test_create_tree (nodes, N, false);
1071 25, 25, 958 struct itree_iterator *g =
1072 20, 30); 959 itree_iterator_start (&tree, 1, 30, ITREE_DESCENDING, NULL, 0);
1073 g = interval_generator_create (&tree); 960 struct itree_node *n = itree_iterator_next (g);
1074 interval_generator_reset (g, 1, 30, ITREE_DESCENDING);
1075 n = interval_generator_next (g);
1076 ck_assert_int_eq (n->begin, 25); 961 ck_assert_int_eq (n->begin, 25);
1077 interval_generator_narrow (g, 25, 35); 962 itree_iterator_narrow (g, 25, 30);
1078 n = interval_generator_next (g); 963 n = itree_iterator_next (g);
1079 ck_assert_int_eq (n->begin, 20); 964 ck_assert_int_eq (n->begin, 20);
1080 free (nodes); 965 itree_iterator_finish (g);
1081} 966}
1082END_TEST 967END_TEST
1083 968
@@ -1086,22 +971,20 @@ END_TEST
1086 * | Insert Gap 971 * | Insert Gap
1087 * +===================================================================================+ */ 972 * +===================================================================================+ */
1088 973
1089static struct interval_tree gap_tree; 974static struct itree_tree gap_tree;
1090static struct interval_node gap_node; 975static struct itree_node gap_node;
1091 976
1092#define N_BEG (interval_tree_validate (&gap_tree, &gap_node)->begin) 977#define N_BEG (itree_node_begin (&gap_tree, &gap_node))
1093#define N_END (interval_tree_validate (&gap_tree, &gap_node)->end) 978#define N_END (itree_node_end (&gap_tree, &gap_node))
1094 979
1095static void 980static void
1096test_setup_gap_node (ptrdiff_t begin, ptrdiff_t end, 981test_setup_gap_node (ptrdiff_t begin, ptrdiff_t end,
1097 bool front_advance, bool rear_advance) 982 bool front_advance, bool rear_advance)
1098{ 983{
1099 interval_tree_init (&gap_tree); 984 interval_tree_init (&gap_tree);
1100 gap_node.begin = begin;
1101 gap_node.end = end;
1102 gap_node.front_advance = front_advance; 985 gap_node.front_advance = front_advance;
1103 gap_node.rear_advance = rear_advance; 986 gap_node.rear_advance = rear_advance;
1104 interval_tree_insert (&gap_tree, &gap_node); 987 itree_insert (&gap_tree, &gap_node, begin, end);
1105} 988}
1106 989
1107static void 990static void
@@ -1112,8 +995,8 @@ test_setup_gap_node_noadvance (ptrdiff_t begin, ptrdiff_t end)
1112 995
1113START_TEST (test_gap_insert_1) 996START_TEST (test_gap_insert_1)
1114{ 997{
1115 test_setup_gap_node (100, 200, false, false); 998 test_setup_gap_node_noadvance (100, 200);
1116 interval_tree_insert_gap (&gap_tree, 100 + 10, 20); 999 itree_insert_gap (&gap_tree, 100 + 10, 20, false);
1117 ck_assert_int_eq (N_BEG, 100); 1000 ck_assert_int_eq (N_BEG, 100);
1118 ck_assert_int_eq (N_END, 200 + 20); 1001 ck_assert_int_eq (N_END, 200 + 20);
1119} 1002}
@@ -1121,8 +1004,8 @@ END_TEST
1121 1004
1122START_TEST (test_gap_insert_2) 1005START_TEST (test_gap_insert_2)
1123{ 1006{
1124 test_setup_gap_node (100, 200, false, false); 1007 test_setup_gap_node_noadvance (100, 200);
1125 interval_tree_insert_gap (&gap_tree, 300, 10); 1008 itree_insert_gap (&gap_tree, 300, 10, false);
1126 ck_assert_int_eq (N_BEG, 100); 1009 ck_assert_int_eq (N_BEG, 100);
1127 ck_assert_int_eq (N_END, 200); 1010 ck_assert_int_eq (N_END, 200);
1128} 1011}
@@ -1130,8 +1013,8 @@ END_TEST
1130 1013
1131START_TEST (test_gap_insert_3) 1014START_TEST (test_gap_insert_3)
1132{ 1015{
1133 test_setup_gap_node (100, 200, false, false); 1016 test_setup_gap_node_noadvance (100, 200);
1134 interval_tree_insert_gap (&gap_tree, 0, 15); 1017 itree_insert_gap (&gap_tree, 0, 15, false);
1135 ck_assert_int_eq (N_BEG, 100 + 15); 1018 ck_assert_int_eq (N_BEG, 100 + 15);
1136 ck_assert_int_eq (N_END, 200 + 15); 1019 ck_assert_int_eq (N_END, 200 + 15);
1137} 1020}
@@ -1140,7 +1023,7 @@ END_TEST
1140START_TEST (test_gap_insert_4) 1023START_TEST (test_gap_insert_4)
1141{ 1024{
1142 test_setup_gap_node (100, 200, true, false); 1025 test_setup_gap_node (100, 200, true, false);
1143 interval_tree_insert_gap (&gap_tree, 100, 20); 1026 itree_insert_gap (&gap_tree, 100, 20, false);
1144 ck_assert_int_eq (N_BEG, 100 + 20); 1027 ck_assert_int_eq (N_BEG, 100 + 20);
1145 ck_assert_int_eq (N_END, 200 + 20); 1028 ck_assert_int_eq (N_END, 200 + 20);
1146 1029
@@ -1149,8 +1032,8 @@ END_TEST
1149 1032
1150START_TEST (test_gap_insert_5) 1033START_TEST (test_gap_insert_5)
1151{ 1034{
1152 test_setup_gap_node (100, 200, false, false); 1035 test_setup_gap_node_noadvance (100, 200);
1153 interval_tree_insert_gap (&gap_tree, 100, 20); 1036 itree_insert_gap (&gap_tree, 100, 20, false);
1154 ck_assert_int_eq (N_BEG, 100); 1037 ck_assert_int_eq (N_BEG, 100);
1155 ck_assert_int_eq (N_END, 200 + 20); 1038 ck_assert_int_eq (N_END, 200 + 20);
1156 1039
@@ -1160,7 +1043,7 @@ END_TEST
1160START_TEST (test_gap_insert_6) 1043START_TEST (test_gap_insert_6)
1161{ 1044{
1162 test_setup_gap_node (100, 200, false, true); 1045 test_setup_gap_node (100, 200, false, true);
1163 interval_tree_insert_gap (&gap_tree, 200, 20); 1046 itree_insert_gap (&gap_tree, 200, 20, false);
1164 ck_assert_int_eq (N_BEG, 100); 1047 ck_assert_int_eq (N_BEG, 100);
1165 ck_assert_int_eq (N_END, 200 + 20); 1048 ck_assert_int_eq (N_END, 200 + 20);
1166 1049
@@ -1169,8 +1052,8 @@ END_TEST
1169 1052
1170START_TEST (test_gap_insert_7) 1053START_TEST (test_gap_insert_7)
1171{ 1054{
1172 test_setup_gap_node (100, 200, false, false); 1055 test_setup_gap_node_noadvance (100, 200);
1173 interval_tree_insert_gap (&gap_tree, 200, 20); 1056 itree_insert_gap (&gap_tree, 200, 20, false);
1174 ck_assert_int_eq (N_BEG, 100); 1057 ck_assert_int_eq (N_BEG, 100);
1175 ck_assert_int_eq (N_END, 200); 1058 ck_assert_int_eq (N_END, 200);
1176 1059
@@ -1180,7 +1063,7 @@ END_TEST
1180START_TEST (test_gap_insert_8) 1063START_TEST (test_gap_insert_8)
1181{ 1064{
1182 test_setup_gap_node (100, 100, true, true); 1065 test_setup_gap_node (100, 100, true, true);
1183 interval_tree_insert_gap (&gap_tree, 100, 20); 1066 itree_insert_gap (&gap_tree, 100, 20, false);
1184 ck_assert_int_eq (N_BEG, 100 + 20); 1067 ck_assert_int_eq (N_BEG, 100 + 20);
1185 ck_assert_int_eq (N_END, 100 + 20); 1068 ck_assert_int_eq (N_END, 100 + 20);
1186 1069
@@ -1190,7 +1073,7 @@ END_TEST
1190START_TEST (test_gap_insert_9) 1073START_TEST (test_gap_insert_9)
1191{ 1074{
1192 test_setup_gap_node (100, 100, false, true); 1075 test_setup_gap_node (100, 100, false, true);
1193 interval_tree_insert_gap (&gap_tree, 100, 20); 1076 itree_insert_gap (&gap_tree, 100, 20, false);
1194 ck_assert_int_eq (N_BEG, 100); 1077 ck_assert_int_eq (N_BEG, 100);
1195 ck_assert_int_eq (N_END, 100 + 20); 1078 ck_assert_int_eq (N_END, 100 + 20);
1196 1079
@@ -1200,7 +1083,7 @@ END_TEST
1200START_TEST (test_gap_insert_10) 1083START_TEST (test_gap_insert_10)
1201{ 1084{
1202 test_setup_gap_node (100, 100, true, false); 1085 test_setup_gap_node (100, 100, true, false);
1203 interval_tree_insert_gap (&gap_tree, 100, 20); 1086 itree_insert_gap (&gap_tree, 100, 20, false);
1204 ck_assert_int_eq (N_BEG, 100); 1087 ck_assert_int_eq (N_BEG, 100);
1205 ck_assert_int_eq (N_END, 100); 1088 ck_assert_int_eq (N_END, 100);
1206 1089
@@ -1209,8 +1092,8 @@ END_TEST
1209 1092
1210START_TEST (test_gap_insert_11) 1093START_TEST (test_gap_insert_11)
1211{ 1094{
1212 test_setup_gap_node (100, 100, false, false); 1095 test_setup_gap_node_noadvance (100, 100);
1213 interval_tree_insert_gap (&gap_tree, 100, 20); 1096 itree_insert_gap (&gap_tree, 100, 20, false);
1214 ck_assert_int_eq (N_BEG, 100); 1097 ck_assert_int_eq (N_BEG, 100);
1215 ck_assert_int_eq (N_END, 100); 1098 ck_assert_int_eq (N_END, 100);
1216 1099
@@ -1225,7 +1108,7 @@ END_TEST
1225START_TEST (test_gap_delete_1) 1108START_TEST (test_gap_delete_1)
1226{ 1109{
1227 test_setup_gap_node_noadvance (100, 200); 1110 test_setup_gap_node_noadvance (100, 200);
1228 interval_tree_delete_gap (&gap_tree, 100 + 10, 20); 1111 itree_delete_gap (&gap_tree, 100 + 10, 20);
1229 ck_assert_int_eq (N_BEG, 100); 1112 ck_assert_int_eq (N_BEG, 100);
1230 ck_assert_int_eq (N_END, 200 - 20); 1113 ck_assert_int_eq (N_END, 200 - 20);
1231 1114
@@ -1235,7 +1118,7 @@ END_TEST
1235START_TEST (test_gap_delete_2) 1118START_TEST (test_gap_delete_2)
1236{ 1119{
1237 test_setup_gap_node_noadvance (100, 200); 1120 test_setup_gap_node_noadvance (100, 200);
1238 interval_tree_delete_gap (&gap_tree, 200 + 10, 20); 1121 itree_delete_gap (&gap_tree, 200 + 10, 20);
1239 ck_assert_int_eq (N_BEG, 100); 1122 ck_assert_int_eq (N_BEG, 100);
1240 ck_assert_int_eq (N_END, 200); 1123 ck_assert_int_eq (N_END, 200);
1241 1124
@@ -1245,7 +1128,7 @@ END_TEST
1245START_TEST (test_gap_delete_3) 1128START_TEST (test_gap_delete_3)
1246{ 1129{
1247 test_setup_gap_node_noadvance (100, 200); 1130 test_setup_gap_node_noadvance (100, 200);
1248 interval_tree_delete_gap (&gap_tree, 200, 20); 1131 itree_delete_gap (&gap_tree, 200, 20);
1249 ck_assert_int_eq (N_BEG, 100); 1132 ck_assert_int_eq (N_BEG, 100);
1250 ck_assert_int_eq (N_END, 200); 1133 ck_assert_int_eq (N_END, 200);
1251 1134
@@ -1255,7 +1138,7 @@ END_TEST
1255START_TEST (test_gap_delete_4) 1138START_TEST (test_gap_delete_4)
1256{ 1139{
1257 test_setup_gap_node_noadvance (100, 200); 1140 test_setup_gap_node_noadvance (100, 200);
1258 interval_tree_delete_gap (&gap_tree, 100 - 20, 20); 1141 itree_delete_gap (&gap_tree, 100 - 20, 20);
1259 ck_assert_int_eq (N_BEG, 100 - 20); 1142 ck_assert_int_eq (N_BEG, 100 - 20);
1260 ck_assert_int_eq (N_END, 200 - 20); 1143 ck_assert_int_eq (N_END, 200 - 20);
1261 1144
@@ -1265,7 +1148,7 @@ END_TEST
1265START_TEST (test_gap_delete_5) 1148START_TEST (test_gap_delete_5)
1266{ 1149{
1267 test_setup_gap_node_noadvance (100, 200); 1150 test_setup_gap_node_noadvance (100, 200);
1268 interval_tree_delete_gap (&gap_tree, 70, 20); 1151 itree_delete_gap (&gap_tree, 70, 20);
1269 ck_assert_int_eq (N_BEG, 100 - 20); 1152 ck_assert_int_eq (N_BEG, 100 - 20);
1270 ck_assert_int_eq (N_END, 200 - 20); 1153 ck_assert_int_eq (N_END, 200 - 20);
1271 1154
@@ -1275,7 +1158,7 @@ END_TEST
1275START_TEST (test_gap_delete_6) 1158START_TEST (test_gap_delete_6)
1276{ 1159{
1277 test_setup_gap_node_noadvance (100, 200); 1160 test_setup_gap_node_noadvance (100, 200);
1278 interval_tree_delete_gap (&gap_tree, 80, 100); 1161 itree_delete_gap (&gap_tree, 80, 100);
1279 ck_assert_int_eq (N_BEG, 80); 1162 ck_assert_int_eq (N_BEG, 80);
1280 ck_assert_int_eq (N_END, 100); 1163 ck_assert_int_eq (N_END, 100);
1281} 1164}
@@ -1284,7 +1167,7 @@ END_TEST
1284START_TEST (test_gap_delete_7) 1167START_TEST (test_gap_delete_7)
1285{ 1168{
1286 test_setup_gap_node_noadvance (100, 200); 1169 test_setup_gap_node_noadvance (100, 200);
1287 interval_tree_delete_gap (&gap_tree, 120, 100); 1170 itree_delete_gap (&gap_tree, 120, 100);
1288 ck_assert_int_eq (N_BEG, 100); 1171 ck_assert_int_eq (N_BEG, 100);
1289 ck_assert_int_eq (N_END, 120); 1172 ck_assert_int_eq (N_END, 120);
1290} 1173}
@@ -1293,7 +1176,7 @@ END_TEST
1293START_TEST (test_gap_delete_8) 1176START_TEST (test_gap_delete_8)
1294{ 1177{
1295 test_setup_gap_node_noadvance (100, 200); 1178 test_setup_gap_node_noadvance (100, 200);
1296 interval_tree_delete_gap (&gap_tree, 100 - 20, 200 + 20); 1179 itree_delete_gap (&gap_tree, 100 - 20, 200 + 20);
1297 ck_assert_int_eq (N_BEG, 100 - 20); 1180 ck_assert_int_eq (N_BEG, 100 - 20);
1298 ck_assert_int_eq (N_END, 100 - 20); 1181 ck_assert_int_eq (N_END, 100 - 20);
1299 1182
@@ -1302,36 +1185,58 @@ END_TEST
1302 1185
1303 1186
1304 1187
1305Suite * basic_suite () 1188static Suite *
1189basic_suite ()
1306{ 1190{
1307 Suite *s = suite_create ("basic_suite"); 1191 Suite *s = suite_create ("basic");
1308 TCase *tc = tcase_create ("basic_test");
1309 1192
1193 TCase *tc = tcase_create ("insert1");
1194 tcase_add_checked_fixture (tc, test_insert1_setup, NULL);
1310 tcase_add_test (tc, test_insert_1); 1195 tcase_add_test (tc, test_insert_1);
1311 tcase_add_test (tc, test_insert_2); 1196 tcase_add_test (tc, test_insert_2);
1312 tcase_add_test (tc, test_insert_3); 1197 tcase_add_test (tc, test_insert_3);
1313 tcase_add_test (tc, test_insert_4); 1198 tcase_add_test (tc, test_insert_4);
1314 tcase_add_test (tc, test_insert_5); 1199 tcase_add_test (tc, test_insert_5);
1315 tcase_add_test (tc, test_insert_6); 1200 tcase_add_test (tc, test_insert_6);
1201 suite_add_tcase (s, tc);
1202
1203 tc = tcase_create ("insert2");
1204 tcase_add_checked_fixture (tc, test_insert2_setup, NULL);
1316 tcase_add_test (tc, test_insert_7); 1205 tcase_add_test (tc, test_insert_7);
1317 tcase_add_test (tc, test_insert_8); 1206 tcase_add_test (tc, test_insert_8);
1318 tcase_add_test (tc, test_insert_9); 1207 tcase_add_test (tc, test_insert_9);
1319 tcase_add_test (tc, test_insert_10); 1208 tcase_add_test (tc, test_insert_10);
1320 tcase_add_test (tc, test_insert_11); 1209 tcase_add_test (tc, test_insert_11);
1321 tcase_add_test (tc, test_insert_12); 1210 tcase_add_test (tc, test_insert_12);
1211 suite_add_tcase (s, tc);
1212
1213 tc = tcase_create ("insert3");
1322 tcase_add_test (tc, test_insert_13); 1214 tcase_add_test (tc, test_insert_13);
1215 tcase_add_test (tc, test_insert_14);
1216 suite_add_tcase (s, tc);
1323 1217
1218 tc = tcase_create ("remove1");
1219 tcase_add_checked_fixture (tc, test_remove1_setup, NULL);
1324 tcase_add_test (tc, test_remove_1); 1220 tcase_add_test (tc, test_remove_1);
1325 tcase_add_test (tc, test_remove_2); 1221 tcase_add_test (tc, test_remove_2);
1326 tcase_add_test (tc, test_remove_3); 1222 tcase_add_test (tc, test_remove_3);
1327 tcase_add_test (tc, test_remove_4); 1223 tcase_add_test (tc, test_remove_4);
1224 suite_add_tcase (s, tc);
1225
1226 tc = tcase_create ("remove2");
1227 tcase_add_checked_fixture (tc, test_remove2_setup, NULL);
1328 tcase_add_test (tc, test_remove_5); 1228 tcase_add_test (tc, test_remove_5);
1329 tcase_add_test (tc, test_remove_6); 1229 tcase_add_test (tc, test_remove_6);
1330 tcase_add_test (tc, test_remove_7); 1230 tcase_add_test (tc, test_remove_7);
1331 tcase_add_test (tc, test_remove_8); 1231 tcase_add_test (tc, test_remove_8);
1232 suite_add_tcase (s, tc);
1233
1234 tc = tcase_create ("remove3");
1332 tcase_add_test (tc, test_remove_9); 1235 tcase_add_test (tc, test_remove_9);
1333 tcase_add_test (tc, test_remove_10); 1236 tcase_add_test (tc, test_remove_10);
1237 suite_add_tcase (s, tc);
1334 1238
1239 tc = tcase_create ("generator");
1335 tcase_add_test (tc, test_generator_1); 1240 tcase_add_test (tc, test_generator_1);
1336 tcase_add_test (tc, test_generator_2); 1241 tcase_add_test (tc, test_generator_2);
1337 tcase_add_test (tc, test_generator_3); 1242 tcase_add_test (tc, test_generator_3);
@@ -1340,7 +1245,9 @@ Suite * basic_suite ()
1340 tcase_add_test (tc, test_generator_7); 1245 tcase_add_test (tc, test_generator_7);
1341 tcase_add_test (tc, test_generator_8); 1246 tcase_add_test (tc, test_generator_8);
1342 tcase_add_test (tc, test_generator_9); 1247 tcase_add_test (tc, test_generator_9);
1248 suite_add_tcase (s, tc);
1343 1249
1250 tc = tcase_create ("insert_gap");
1344 tcase_add_test (tc, test_gap_insert_1); 1251 tcase_add_test (tc, test_gap_insert_1);
1345 tcase_add_test (tc, test_gap_insert_2); 1252 tcase_add_test (tc, test_gap_insert_2);
1346 tcase_add_test (tc, test_gap_insert_3); 1253 tcase_add_test (tc, test_gap_insert_3);
@@ -1352,7 +1259,9 @@ Suite * basic_suite ()
1352 tcase_add_test (tc, test_gap_insert_9); 1259 tcase_add_test (tc, test_gap_insert_9);
1353 tcase_add_test (tc, test_gap_insert_10); 1260 tcase_add_test (tc, test_gap_insert_10);
1354 tcase_add_test (tc, test_gap_insert_11); 1261 tcase_add_test (tc, test_gap_insert_11);
1262 suite_add_tcase (s, tc);
1355 1263
1264 tc = tcase_create ("delete_gap");
1356 tcase_add_test (tc, test_gap_delete_1); 1265 tcase_add_test (tc, test_gap_delete_1);
1357 tcase_add_test (tc, test_gap_delete_2); 1266 tcase_add_test (tc, test_gap_delete_2);
1358 tcase_add_test (tc, test_gap_delete_3); 1267 tcase_add_test (tc, test_gap_delete_3);
@@ -1361,21 +1270,20 @@ Suite * basic_suite ()
1361 tcase_add_test (tc, test_gap_delete_6); 1270 tcase_add_test (tc, test_gap_delete_6);
1362 tcase_add_test (tc, test_gap_delete_7); 1271 tcase_add_test (tc, test_gap_delete_7);
1363 tcase_add_test (tc, test_gap_delete_8); 1272 tcase_add_test (tc, test_gap_delete_8);
1364
1365 /* tcase_set_timeout (tc, 120); */
1366 suite_add_tcase (s, tc); 1273 suite_add_tcase (s, tc);
1274
1367 return s; 1275 return s;
1368} 1276}
1369 1277
1370int 1278int
1371main (void) 1279main (void)
1372{ 1280{
1373 int nfailed;
1374 Suite *s = basic_suite (); 1281 Suite *s = basic_suite ();
1375 SRunner *sr = srunner_create (s); 1282 SRunner *sr = srunner_create (s);
1376 1283
1377 srunner_run_all (sr, CK_NORMAL); 1284 init_itree ();
1378 nfailed = srunner_ntests_failed (sr); 1285 srunner_run_all (sr, CK_ENV);
1286 int nfailed = srunner_ntests_failed (sr);
1379 srunner_free (sr); 1287 srunner_free (sr);
1380 return (nfailed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; 1288 return (nfailed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
1381} 1289}
generated by cgit v1.2.1 (git 2.18.0) at 2026-02-25 03:49:32 +0000