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.

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 @@
+### @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 03eedce8a67..9a67818dc8f 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 812f8e48a36..d2448b12db3 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 a3183892132..278e65f9bf7 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;
 }