From 4a24e15301d4fd290b6ac211d9385676e61f2014 Mon Sep 17 00:00:00 2001 From: Martin Kronbichler Date: Fri, 30 Jun 2023 11:39:55 +0200 Subject: [PATCH] Test case that would previously run in quadratic complexity --- tests/base/index_set_33.cc | 48 ++++++++++++++++++++++++++++++++++ tests/base/index_set_33.output | 2 ++ 2 files changed, 50 insertions(+) create mode 100644 tests/base/index_set_33.cc create mode 100644 tests/base/index_set_33.output diff --git a/tests/base/index_set_33.cc b/tests/base/index_set_33.cc new file mode 100644 index 0000000000..1e41ce0a8f --- /dev/null +++ b/tests/base/index_set_33.cc @@ -0,0 +1,48 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2023 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE.md at +// the top level directory of deal.II. +// +// --------------------------------------------------------------------- + + +// Test that IndexSet::add_index runs in linear complexity when adding the +// same indices many times + +#include + +#include "../tests.h" + + +void +test() +{ + IndexSet set(20); + + // Choose a large number of entries, which would time-out for quadratic + // complexity + for (unsigned int t = 0; t < 200000; ++t) + for (unsigned int i = 4; i < 15; ++i) + set.add_index(i); + + set.compress(); + deallog << "OK" << std::endl; +} + + + +int +main() +{ + initlog(); + + test(); +} diff --git a/tests/base/index_set_33.output b/tests/base/index_set_33.output new file mode 100644 index 0000000000..0fd8fc12f0 --- /dev/null +++ b/tests/base/index_set_33.output @@ -0,0 +1,2 @@ + +DEAL::OK -- 2.39.5