From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: "Basil L. Contovounesios" via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#58976: 29.0.50; Manual noverlay tests fail to build Date: Thu, 03 Nov 2022 14:31:02 +0200 Message-ID: <87mt98dxtl.fsf@tcd.ie> References: <87mt98285r.fsf@tcd.ie> Reply-To: "Basil L. Contovounesios" Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="10477"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) To: 58976@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Nov 03 13:32:29 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oqZOW-0002Ru-Hk for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 03 Nov 2022 13:32:28 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oqZOJ-0000Y5-FS; Thu, 03 Nov 2022 08:32:15 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oqZO6-0000XZ-Dc for bug-gnu-emacs@gnu.org; Thu, 03 Nov 2022 08:32:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oqZO6-0007gp-53 for bug-gnu-emacs@gnu.org; Thu, 03 Nov 2022 08:32:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oqZO5-0004Tz-Vz for bug-gnu-emacs@gnu.org; Thu, 03 Nov 2022 08:32:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: "Basil L. Contovounesios" Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 03 Nov 2022 12:32:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58976 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 58976-submit@debbugs.gnu.org id=B58976.166747867917173 (code B ref 58976); Thu, 03 Nov 2022 12:32:01 +0000 Original-Received: (at 58976) by debbugs.gnu.org; 3 Nov 2022 12:31:19 +0000 Original-Received: from localhost ([127.0.0.1]:48309 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oqZNL-0004Ss-Me for submit@debbugs.gnu.org; Thu, 03 Nov 2022 08:31:19 -0400 Original-Received: from mail-ed1-f47.google.com ([209.85.208.47]:38873) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oqZNH-0004SZ-DE for 58976@debbugs.gnu.org; Thu, 03 Nov 2022 08:31:15 -0400 Original-Received: by mail-ed1-f47.google.com with SMTP id y69so2746703ede.5 for <58976@debbugs.gnu.org>; Thu, 03 Nov 2022 05:31:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tcd.ie; s=google21; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:to:from:from:to:cc:subject:date:message-id:reply-to; bh=PWz8Ywz8JCB1nnFkIUgGyVfjUweVM71Lo5vh/t0oa34=; b=d57dmgcCf2C0oUgCi8yWklmNholl33yzlUnImm87naD6FVPaZ6biWT4K+AUCiRiDy3 zZ4hVMJhvhpL+E3DE+5UCB0SS5p3ETEFb4cx8vrQi3SpwNufavTxIYUK2Ww8L1nN6qBH /dx8dTKhfFg/+R9K82Iyp4kVn8jteYfz44QkLxBcYeHaPDdMTbgivKyt+X6k+m7c1RvY p0HBJJcMrYDAXYnyj0f43FjaDbOtDZU5n0OtpJ15ZheyJGr/vNUv/b+yF1EkydoHnC2W T1Ldw8B2PC/QYWVL8GNQDop/7XT93ryAnI3qz7q9607zmDF4n+PZSbKCqC22Sn25CsfY +00A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=PWz8Ywz8JCB1nnFkIUgGyVfjUweVM71Lo5vh/t0oa34=; b=lRcMs9vB1v++3jbJ0lidls22oQxYvy3mOekJNaM+SOMLKrXjXB7WbSWY01QU1q73xo VoGiaZnRPk67GOXX2oSRkJ8vTtZefTjN1XwfCIyj8N8a6e1/TE97UvXc6R30wgJFkqm3 NDL0MFEplr05skMNnTnQ6TdFBZgK2F2MfjkI+XAQ1/2gN+q+m6Byvxbw8YRsSW+UuozF r93v/Zm+7ctQRCzi1JAWtDEq/ezDBbWzsye/GA0hbIQZuME6YHLv4RiWdf/4DVE8wlQ8 kEjIMf1hye/nc/sO0ukMGEKClXFRNusFp0iGUTFNcxwmTi/mFF6IHwwIc43P3OXtjJUg v03w== X-Gm-Message-State: ACrzQf0pdEHsnCQHyUGlI3P5stZjlr4Hz082t/fpw+4yqL6Ze2gq2kw7 3K0OlXQsvSyOhDB08eHsGNUA5413d9i4hA== X-Google-Smtp-Source: AMsMyM7IhqXfiLXbmG+HKShSO+AZHnPFIrGX0uIRH5ZgIJEcqDx8q5l3MOZNIak2sx8alelNsQtHXg== X-Received: by 2002:a05:6402:3487:b0:463:9585:ae40 with SMTP id v7-20020a056402348700b004639585ae40mr17071521edc.31.1667478665053; Thu, 03 Nov 2022 05:31:05 -0700 (PDT) Original-Received: from localhost ([2a02:587:320c:8829:23:8156:16ed:40c2]) by smtp.gmail.com with ESMTPSA id m7-20020a1709066d0700b007add1c4dadbsm431046ejr.153.2022.11.03.05.31.03 for <58976@debbugs.gnu.org> (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 03 Nov 2022 05:31:03 -0700 (PDT) In-Reply-To: <87mt98285r.fsf@tcd.ie> (Basil L. Contovounesios" via "Bug reports for GNU Emacs, the Swiss army knife of text editors's message of "Thu, 03 Nov 2022 02:28:32 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: "bug-gnu-emacs" Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:246955 Archived-At: --=-=-= Content-Type: text/plain Basil L. Contovounesios [2022-11-03 02:28 +0200] wrote: > This patch lets the tests build and succeed: Here's an updated patch further to https://bugs.gnu.org/58975#8, and depending on that patch landing first. -- Basil --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=0001-Fix-manual-noverlay-tests.patch >From d540cb00865368bb9df9299838006dfe09255bc6 Mon Sep 17 00:00:00 2001 From: "Basil L. Contovounesios" Date: Wed, 2 Nov 2022 03:52:16 +0200 Subject: [PATCH] Fix manual noverlay tests * test/manual/noverlay/Makefile.in: Add copyright notice. (LIBS): Rename... (PACKAGES): ...to this, to avoid confusion with Autoconf's LIBS. All uses changed. (CFLAGS): Break out -I flag... (CPPFLAGS): ...into this new variable. (LDFLAGS): Rename... (LDLIBS): ...to this, which is expected to hold -l flags. (top_builddir): New variable. (EMACS): Define in terms of it. (.PHONY): Add clean, distclean, and perf targets. (have-libcheck): Remove redundant target. All uses updated. (itree-tests.o): Remove redundant dependency on its source file. (itree-tests): Remove redundant (and uncompilable) rule. * test/manual/noverlay/check-sanitize.sh: Use /usr/bin/env. Add copyright notice. Enable pipefail option, to propagate itree-tests exit status to caller. Fix typo in usage message. Strip less information from Check's error messages. * test/manual/noverlay/emacs-compat.h: Add copyright notice. Include stdlib.h. (emacs_abort, eassert): Consistently use EXIT_FAILURE. (eassume): Define when necessary. * test/manual/noverlay/itree-tests.c: Add copyright notice. Include standard headers before third-party ones. Use most narrowly applicable ck_assert* macro for the types being checked, e.g. ck_assert_ptr_* macros for pointer values. Replace removed names and APIs with current ones, e.g. the itree_node field 'color' is now called 'red'. Ensure preconditions of itree API are satisfied before use, e.g. itree_node otick being set appropriately before insertion, or global iterator being initialized before (implicit) use (bug#58976). Make all functions static. (DEF_TEST_SETUP): Remove all instances, replacing with... (test_insert1_setup, test_insert2_setup, test_remove1_setup) (test_remove2_setup): ...these new test fixtures. (A, B, C, D, E, N_05, N_10, N_15, N_20, N_30, N_40, N_50, N_70) (N_80, N_90, N_85, N_95): Define as static variables rather than macros. (test_get_tree4): Remove, inlining salient parts. (shuffle): Move closer to users. (test_create_tree): Accept itree_nodes as argument instead of dynamically allocating them. All callers changed. (FOREACH): Remove unused macro. (N_BEG, N_END): Define in terms of itree_node_begin and itree_node_end, respectively. (test_gap_insert_1, test_gap_insert_2, test_gap_insert_3) (test_gap_insert_5, test_gap_insert_7, test_gap_insert_11): Use test_setup_gap_node_noadvance. (basic_suite): Group unit tests into test cases and fixtures. Run previously forgotten test_insert_14. (main): Run suite as CK_ENV to allow specifying desired verbosity in the environment. --- test/manual/noverlay/Makefile.in | 41 +- test/manual/noverlay/check-sanitize.sh | 28 +- test/manual/noverlay/emacs-compat.h | 36 +- test/manual/noverlay/itree-tests.c | 1284 +++++++++++------------- 4 files changed, 679 insertions(+), 710 deletions(-) diff --git a/test/manual/noverlay/Makefile.in b/test/manual/noverlay/Makefile.in index beef1dbc09..3c8dba1ce1 100644 --- a/test/manual/noverlay/Makefile.in +++ b/test/manual/noverlay/Makefile.in @@ -1,26 +1,41 @@ +### @configure_input@ + +# Copyright (C) 2017-2022 Free Software Foundation, Inc. + +# This file is part of GNU Emacs. + +# GNU Emacs is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# GNU Emacs is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with GNU Emacs. If not, see . + PROGRAM = itree-tests -LIBS = check +PACKAGES = check top_srcdir = @top_srcdir@ -CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(LIBS)) -I $(top_srcdir)/src -LDFLAGS += $(shell pkg-config --libs $(LIBS)) -lm +top_builddir = @top_builddir@ +CPPFLAGS += -I $(top_srcdir)/src +CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(PACKAGES)) +LDLIBS += $(shell pkg-config --libs $(PACKAGES)) -lm OBJECTS = itree-tests.o CC = gcc -EMACS ?= ../../../src/emacs +EMACS ?= $(top_builddir)/src/emacs -.PHONY: all check have-libcheck +.PHONY: all check clean distclean perf all: check -have-libcheck: - pkg-config --cflags $(LIBS) - -check: have-libcheck $(PROGRAM) +check: $(PROGRAM) ./check-sanitize.sh ./$(PROGRAM) -itree-tests.o: emacs-compat.h itree-tests.c $(top_srcdir)/src/itree.c $(top_srcdir)/src/itree.h - -$(PROGRAM): $(OBJECTS) - $(CC) $(CFLAGS) $(LDFLAGS) $(OBJECTS) -o $(PROGRAM) +itree-tests.o: emacs-compat.h $(top_srcdir)/src/itree.c $(top_srcdir)/src/itree.h perf: -$(EMACS) -Q -l ./overlay-perf.el -f perf-run-batch diff --git a/test/manual/noverlay/check-sanitize.sh b/test/manual/noverlay/check-sanitize.sh index 03eedce8a6..9a67818dc8 100755 --- a/test/manual/noverlay/check-sanitize.sh +++ b/test/manual/noverlay/check-sanitize.sh @@ -1,11 +1,33 @@ -#!/bin/bash +#!/usr/bin/env bash +### check-sanitize.sh - strip confusing parts of Check error output + +## Copyright (C) 2017-2022 Free Software Foundation, Inc. + +## This file is part of GNU Emacs. + +## GNU Emacs is free software: you can redistribute it and/or modify +## it under the terms of the GNU General Public License as published by +## the Free Software Foundation, either version 3 of the License, or +## (at your option) any later version. + +## GNU Emacs is distributed in the hope that it will be useful, +## but WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. + +## You should have received a copy of the GNU General Public License +## along with GNU Emacs. If not, see . + +set -o pipefail prog=$1 shift [ -z "$prog" ] && { - echo "usage:$(basename $0) CHECK_PRGOGRAM"; + echo "usage:$(basename $0) CHECK_PROGRAM"; exit 1; } -"$prog" "$@" | sed -e 's/^\([^:]\+\):\([0-9]\+\):[PFE]:[^:]*:\([^:]*\):[^:]*: *\(.*\)/\1:\2:\3:\4/' +# FIXME: This would be unnecessary if +# compilation-error-regexp-alist-alist understood libcheck OOTB. +"$prog" "$@" | sed -e 's/^\([^:]\+\):\([0-9]\+\):\([PFE]\):\([^:]*\):\([^:]*\):[^:]*:\(.*\)/\1:\2:\3:\4:\5:\6/' diff --git a/test/manual/noverlay/emacs-compat.h b/test/manual/noverlay/emacs-compat.h index 812f8e48a3..d2448b12db 100644 --- a/test/manual/noverlay/emacs-compat.h +++ b/test/manual/noverlay/emacs-compat.h @@ -1,8 +1,28 @@ +/* Mock necessary parts of lisp.h. + +Copyright (C) 2017-2022 Free Software Foundation, Inc. + +This file is part of GNU Emacs. + +GNU Emacs is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or (at +your option) any later version. + +GNU Emacs is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Emacs. If not, see . */ + #ifndef TEST_COMPAT_H #define TEST_COMPAT_H -#include #include +#include +#include typedef int Lisp_Object; @@ -28,20 +48,24 @@ xrealloc (void *block, size_t size) 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 @@ #define max(x,y) ((x) >= (y) ? (x) : (y)) #define min(x,y) ((x) <= (y) ? (x) : (y)) #endif -#endif +#endif /* TEST_COMPAT_H */ diff --git a/test/manual/noverlay/itree-tests.c b/test/manual/noverlay/itree-tests.c index a318389213..8c68dc50b9 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 . */ + #include -#include -#include + #include +#include + +#include #include "emacs-compat.h" #define EMACS_LISP_H /* lisp.h inclusion guard */ @@ -9,7 +30,14 @@ #define ITREE_DEBUG 1 #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 @@ #define ITREE_TESTING /* 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 @@ #define DEF_TEST_SETUP() \ * [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 @@ #define DEF_TEST_SETUP() \ * [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 @@ START_TEST (test_remove_10) 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 @@ START_TEST (test_generator_9) * | 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 200 + 20); } @@ -1121,8 +1004,8 @@ START_TEST (test_gap_insert_1) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 200); } @@ -1130,8 +1013,8 @@ START_TEST (test_gap_insert_2) 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); ck_assert_int_eq (N_BEG, 100 + 15); ck_assert_int_eq (N_END, 200 + 15); } @@ -1140,7 +1023,7 @@ START_TEST (test_gap_insert_3) 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); ck_assert_int_eq (N_BEG, 100 + 20); ck_assert_int_eq (N_END, 200 + 20); @@ -1149,8 +1032,8 @@ START_TEST (test_gap_insert_4) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 200 + 20); @@ -1160,7 +1043,7 @@ START_TEST (test_gap_insert_5) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 200 + 20); @@ -1169,8 +1052,8 @@ START_TEST (test_gap_insert_6) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 200); @@ -1180,7 +1063,7 @@ START_TEST (test_gap_insert_7) 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); ck_assert_int_eq (N_BEG, 100 + 20); ck_assert_int_eq (N_END, 100 + 20); @@ -1190,7 +1073,7 @@ START_TEST (test_gap_insert_8) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 100 + 20); @@ -1200,7 +1083,7 @@ START_TEST (test_gap_insert_9) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 100); @@ -1209,8 +1092,8 @@ START_TEST (test_gap_insert_10) 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); ck_assert_int_eq (N_BEG, 100); ck_assert_int_eq (N_END, 100); @@ -1225,7 +1108,7 @@ START_TEST (test_gap_insert_11) 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 @@ START_TEST (test_gap_delete_1) 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 @@ START_TEST (test_gap_delete_2) 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 @@ START_TEST (test_gap_delete_3) 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 @@ START_TEST (test_gap_delete_4) 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 @@ START_TEST (test_gap_delete_5) 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 @@ START_TEST (test_gap_delete_6) 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 @@ START_TEST (test_gap_delete_7) 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 @@ START_TEST (test_gap_delete_8) -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 @@ START_TEST (test_gap_delete_8) 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 @@ START_TEST (test_gap_delete_8) 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 @@ START_TEST (test_gap_delete_8) 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; } -- 2.35.1 --=-=-=--