diff options
Diffstat (limited to '')
| -rw-r--r-- | testsuites/unit/tc-base64-decode.c | 186 | ||||
| -rw-r--r-- | testsuites/unit/tc-compiler-builtins.c | 1141 | ||||
| -rw-r--r-- | testsuites/unit/tc-config.c | 171 | ||||
| -rw-r--r-- | testsuites/unit/tc-crc.c | 48 | ||||
| -rw-r--r-- | testsuites/unit/tc-misaligned-builtin-memcpy.c | 57 | ||||
| -rw-r--r-- | testsuites/unit/tc-score-msgq.c | 452 | ||||
| -rw-r--r-- | testsuites/unit/tc-score-rbtree.c | 1195 | ||||
| -rw-r--r-- | testsuites/unit/ts-unit-no-clock-0.c | 80 |
8 files changed, 3330 insertions, 0 deletions
diff --git a/testsuites/unit/tc-base64-decode.c b/testsuites/unit/tc-base64-decode.c new file mode 100644 index 0000000000..4b0672d310 --- /dev/null +++ b/testsuites/unit/tc-base64-decode.c @@ -0,0 +1,186 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup TestsuitesUnitNoClock0 + */ + +/* + * Copyright (C) 2023 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <rtems/base64.h> + +#include <rtems/test.h> + +typedef struct { + Base64_Decode_control base; + uint8_t buf[64]; +} test_control; + +static int test_run(test_control* self, const char* payload) { + size_t len = strlen(payload); + + for (size_t i = 0; i < len; ++i) { + int rv = _Base64_Decode(&self->base, payload[i]); + + if (rv != 0) { + return rv; + } + } + + return 0; +} + +static int test_payload(test_control* self, const char* payload) { + memset(self->buf, 0xff, sizeof(self->buf)); + _Base64_Decode_initialize(&self->base, &self->buf[0], sizeof(self->buf)); + return test_run(self, payload); +} + +T_TEST_CASE(IOBase64Decode) { + int rv; + test_control instance; + test_control* self = &instance; + + rv = test_payload(self, "POOL"); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->base.target, &self->buf[3]); + const uint8_t expected1[] = {0x3c, 0xe3, 0x8b, 0xff}; + T_eq_mem(&self->buf[0], expected1, sizeof(expected1)); + + rv = test_payload(self, "ABCDEFGH"); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->base.target, &self->buf[6]); + const uint8_t expected2[] = {0x00, 0x10, 0x83, 0x10, 0x51, 0x87, 0xff}; + T_eq_mem(&self->buf[0], expected2, sizeof(expected2)); + + /* Non-base64 character results in an error */ + rv = test_payload(self, "PO*OL"); + T_eq_int(rv, BASE64_DECODE_INVALID_INPUT); + T_eq_int(self->base.state, BASE64_DECODE_STATE_2); + T_eq_ptr(self->base.target, &self->buf[1]); + const uint8_t expected3[] = {0x3c}; + T_eq_mem(&self->buf[0], expected3, sizeof(expected3)); + + /* Other non-base64 character results in an error */ + rv = test_payload(self, "PO\x80OL"); + T_eq_int(rv, BASE64_DECODE_INVALID_INPUT); + T_eq_int(self->base.state, BASE64_DECODE_STATE_2); + T_eq_ptr(self->base.target, &self->buf[1]); + T_eq_mem(&self->buf[0], expected3, sizeof(expected3)); + + /* Space characters should be ignored */ + rv = test_payload(self, "P OOL"); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->base.target, &self->buf[3]); + const uint8_t expected4[] = {0x3c, 0xe3, 0x8b, 0xff}; + T_eq_mem(&self->buf[0], expected4, sizeof(expected4)); + + /* Handle pad characters */ + rv = test_payload(self, "POOL=="); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->base.target, &self->buf[3]); + T_eq_ptr(self->base.target, self->base.target_end); + const uint8_t expected5[] = {0x3c, 0xe3, 0x8b, 0xff}; + T_eq_mem(&self->buf[0], expected5, sizeof(expected5)); + + /* If characters come after pad characters, an error results */ + rv = test_payload(self, "POOL==xy"); + T_eq_int(rv, BASE64_DECODE_OVERFLOW); + T_eq_int(self->base.state, BASE64_DECODE_SUCCESS); + T_eq_ptr(self->base.target, &self->buf[3]); + T_eq_ptr(self->base.target, self->base.target_end); + const uint8_t expected6[] = {0x3c, 0xe3, 0x8b, 0xff}; + T_eq_mem(&self->buf[0], expected6, sizeof(expected6)); + + rv = test_payload(self, "POOLPOOL"); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->base.target, &self->buf[6]); + const uint8_t expected7[] = {0x3c, 0xe3, 0x8b, 0x3c, 0xe3, 0x8b, 0xff}; + T_eq_mem(&self->buf[0], expected7, sizeof(expected7)); + + /* + * Test valid payload with series of target sizes. All target sizes + * less than three are invalid for the given payload and will result + * in an error. + */ + const uint8_t expected9[] = {0x3c, 0xe3, 0x8b, 0xff}; + + for (size_t i = 0; i < 4; ++i) { + memset(&self->buf[0], 0xff, sizeof(self->buf)); + _Base64_Decode_initialize(&self->base, &self->buf[0], i); + rv = test_run(self, "POOL"); + + if (i < 3) { + T_eq_int(rv, BASE64_DECODE_OVERFLOW); + T_eq_int(self->base.state, i); + T_ne_ptr(self->base.target, &self->buf[3]); + T_ne_mem(&self->buf[0], expected9, sizeof(expected9)); + } else { + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->base.target, &self->buf[3]); + T_eq_mem(&self->buf[0], expected9, sizeof(expected9)); + } + } + + /* No overflow in state 1 */ + memset(&self->buf[0], 0xff, sizeof(self->buf)); + _Base64_Decode_initialize(&self->base, &self->buf[0], 1); + rv = test_run(self, "AA"); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_2); + T_eq_ptr(self->base.target, &self->buf[1]); + const uint8_t expected10[] = {0x00, 0xff}; + T_eq_mem(&self->buf[0], expected10, sizeof(expected10)); + + /* No overflow in state 2 */ + memset(&self->buf[0], 0xff, sizeof(self->buf)); + _Base64_Decode_initialize(&self->base, &self->buf[0], 2); + rv = test_run(self, "AAA"); + T_eq_int(rv, BASE64_DECODE_SUCCESS); + T_eq_int(self->base.state, BASE64_DECODE_STATE_3); + T_eq_ptr(self->base.target, &self->buf[2]); + const uint8_t expected11[] = {0x00, 0x00, 0xff}; + T_eq_mem(&self->buf[0], expected11, sizeof(expected11)); +} + +T_TEST_CASE(IOBase64DecodeInitialize) { + Base64_Decode_control instance; + Base64_Decode_control* self = &instance; + uint8_t buf[1]; + + memset(self, 0xff, sizeof(*self)); + _Base64_Decode_initialize(self, buf, sizeof(buf)); + T_eq_int(self->state, BASE64_DECODE_STATE_0); + T_eq_ptr(self->target, &buf[0]); + T_eq_ptr(self->target_end, &buf[1]); +} diff --git a/testsuites/unit/tc-compiler-builtins.c b/testsuites/unit/tc-compiler-builtins.c new file mode 100644 index 0000000000..7a470b6632 --- /dev/null +++ b/testsuites/unit/tc-compiler-builtins.c @@ -0,0 +1,1141 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup CompilerUnitBuiltins + */ + +/* + * Copyright (C) 2023 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This file is part of the RTEMS quality process and was automatically + * generated. If you find something that needs to be fixed or + * worded better please post a report or patch to an RTEMS mailing list + * or raise a bug report: + * + * https://www.rtems.org/bugs.html + * + * For information on updating and regenerating please refer to the How-To + * section in the Software Requirements Engineering chapter of the + * RTEMS Software Engineering manual. The manual is provided as a part of + * a release. For development sources please refer to the online + * documentation at: + * + * https://docs.rtems.org + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <setjmp.h> +#include <stdint.h> + +#include "../validation/tx-support.h" + +#include <rtems/test.h> + +/** + * @defgroup CompilerUnitBuiltins spec:/compiler/unit/builtins + * + * @ingroup TestsuitesUnitNoClock0 + * + * @brief These unit tests check compiler builtins. + * + * Explicitly test the 64-bit integer division and modulo operations. They are + * essential for the timekeeping services. On most 32-bit targets, they need a + * software implementation. + * + * This test case performs the following actions: + * + * - Check the return value of __builtin_clz() for a sample set of inputs. + * + * - Check the return value of __builtin_clzll() for a sample set of inputs. + * + * - Check the return value of __builtin_ctz() for a sample set of inputs. + * + * - Check the return value of __builtin_ctzll() for a sample set of inputs. + * + * - Check the return value of __builtin_ffs() for a sample set of inputs. + * + * - Check the return value of __builtin_ffsll() for a sample set of inputs. + * + * - Check the return value of __builtin_parity() for a sample set of inputs. + * + * - Check the return value of __builtin_parityll() for a sample set of inputs. + * + * - Check the return value of __builtin_popcount() for a sample set of inputs. + * + * - Check the return value of __builtin_popcountll() for a sample set of + * inputs. + * + * - Check the return value of __builtin_bswap32() for a sample set of inputs. + * + * - Check the return value of __builtin_bswap64() for a sample set of inputs. + * + * - Check signed 64-bit comparisons for a sample set of values. + * + * - Check unsigned 64-bit comparisons for a sample set of values. + * + * - Check signed 64-bit arithmetic left shift for a sample set of values. + * + * - Check signed 64-bit arithmetic right shift for a sample set of values. + * + * - Check unsigned 64-bit logical right shift for a sample set of values. + * + * - Check signed 64-bit multiplication for a sample set of values. + * + * - Check signed 64-bit negation for a sample set of values. + * + * - Check signed 64-bit divisions for a sample set of values. + * + * - Check unsigned 64-bit divisions for a sample set of values. + * + * - Check signed 64-bit modulo operations for a sample set of values. + * + * - Check unsigned 64-bit modulo operations for a sample set of values. + * + * @{ + */ + +#if __LONG_MAX__ == 0x7fffffffL && !defined(__aarch64__) +#define TEST_UDIVMODDI4 +#endif + +#if defined(TEST_UDIVMODDI4) +uint64_t __udivmoddi4( uint64_t n, uint64_t d, uint64_t *r ); +#endif + +#if defined(TEST_UDIVMODDI4) && defined(__arm__) +/* + * Here __aeabi_uldivmod() may be used to carry out integer division + * operations even though the reminder is unused. This function is + * implemented by __udivmoddi4() which may never get called without a + * reminder for compiler generated code. + */ +#define TEST_UDIVMODDI4_WITHOUT_REMINDER +#endif + +static bool do_longjmp; + +static jmp_buf exception_return_context; + +static void Fatal( + rtems_fatal_source source, + rtems_fatal_code code, + void *arg +) +{ + (void) code; + + if ( source == RTEMS_FATAL_SOURCE_EXCEPTION && do_longjmp ) { + do_longjmp = false; + _ISR_Set_level( 0 ); + longjmp( arg, 1 ); + } +} + +static void CompilerUnitBuiltins_Setup( void *ctx ) +{ + SetFatalHandler( Fatal, exception_return_context ); +} + +static void CompilerUnitBuiltins_Teardown( void *ctx ) +{ + SetFatalHandler( NULL, NULL ); +} + +static T_fixture CompilerUnitBuiltins_Fixture = { + .setup = CompilerUnitBuiltins_Setup, + .stop = NULL, + .teardown = CompilerUnitBuiltins_Teardown, + .scope = NULL, + .initial_context = NULL +}; + +/** + * @brief Check the return value of __builtin_clz() for a sample set of inputs. + */ +static void CompilerUnitBuiltins_Action_0( void ) +{ + volatile unsigned int n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1U; + T_eq_int( __builtin_clz( n ), 31 ); + + n = 1U << 31; + T_eq_int( __builtin_clz( n ), 0 ); + + n = ~0U; + T_eq_int( __builtin_clz( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_clzll() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_1( void ) +{ + volatile unsigned long long n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1ULL; + T_eq_int( __builtin_clzll( n ), 63 ); + + n = 1ULL << 31; + T_eq_int( __builtin_clzll( n ), 32 ); + + n = 1ULL << 32; + T_eq_int( __builtin_clzll( n ), 31 ); + + n = 1ULL << 63; + T_eq_int( __builtin_clzll( n ), 0 ); + + n = ~0ULL; + T_eq_int( __builtin_clzll( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_ctz() for a sample set of inputs. + */ +static void CompilerUnitBuiltins_Action_2( void ) +{ + volatile unsigned int n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1U; + T_eq_int( __builtin_ctz( n ), 0 ); + + n = 1U << 31; + T_eq_int( __builtin_ctz( n ), 31 ); + + n = ~0U; + T_eq_int( __builtin_ctz( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_ctzll() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_3( void ) +{ + volatile unsigned long long n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1ULL; + T_eq_int( __builtin_ctzll( n ), 0 ); + + n = 1ULL << 31; + T_eq_int( __builtin_ctzll( n ), 31 ); + + n = 1ULL << 32; + T_eq_int( __builtin_ctzll( n ), 32 ); + + n = 1ULL << 63; + T_eq_int( __builtin_ctzll( n ), 63 ); + + n = ~0ULL; + T_eq_int( __builtin_ctzll( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_ffs() for a sample set of inputs. + */ +static void CompilerUnitBuiltins_Action_4( void ) +{ + volatile unsigned int n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1U; + T_eq_int( __builtin_ffs( n ), 1 ); + + n = 1U << 31; + T_eq_int( __builtin_ffs( n ), 32 ); + + n = 0U; + T_eq_int( __builtin_ffs( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_ffsll() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_5( void ) +{ + volatile unsigned long long n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1ULL; + T_eq_int( __builtin_ffsll( n ), 1 ); + + n = 1ULL << 31; + T_eq_int( __builtin_ffsll( n ), 32 ); + + n = 1ULL << 32; + T_eq_int( __builtin_ffsll( n ), 33 ); + + n = 1ULL << 63; + T_eq_int( __builtin_ffsll( n ), 64 ); + + n = 0ULL; + T_eq_int( __builtin_ffsll( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_parity() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_6( void ) +{ + volatile unsigned int n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1U; + T_eq_int( __builtin_parity( n ), 1 ); + + n = ~0U; + T_eq_int( __builtin_parity( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_parityll() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_7( void ) +{ + volatile unsigned long long n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 1ULL; + T_eq_int( __builtin_parityll( n ), 1 ); + + n = ~0ULL; + T_eq_int( __builtin_parityll( n ), 0 ); +} + +/** + * @brief Check the return value of __builtin_popcount() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_8( void ) +{ + volatile unsigned int n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 0U; + T_eq_int( __builtin_popcount( n ), 0 ); + + n = 1U; + T_eq_int( __builtin_popcount( n ), 1 ); + + n = ~0U; + T_eq_int( __builtin_popcount( n ), 32 ); +} + +/** + * @brief Check the return value of __builtin_popcountll() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_9( void ) +{ + volatile unsigned long long n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = 0ULL; + T_eq_int( __builtin_popcountll( n ), 0 ); + + n = 1ULL; + T_eq_int( __builtin_popcountll( n ), 1 ); + + n = ~0ULL; + T_eq_int( __builtin_popcountll( n ), 64 ); +} + +/** + * @brief Check the return value of __builtin_bswap32() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_10( void ) +{ + volatile uint32_t n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = UINT32_C( 0 ); + T_eq_u32( __builtin_bswap32( n ), n ); + + n = UINT32_C( 1 ); + T_eq_u32( __builtin_bswap32( n ), n << 24 ); + + n = UINT32_C( 0x12345678 ); + T_eq_u32( __builtin_bswap32( n ), UINT32_C( 0x78563412 ) ); + + n = ~UINT32_C( 0 ); + T_eq_u32( __builtin_bswap32( n ), n ); +} + +/** + * @brief Check the return value of __builtin_bswap64() for a sample set of + * inputs. + */ +static void CompilerUnitBuiltins_Action_11( void ) +{ + volatile uint64_t n; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + + n = UINT64_C( 0 ); + T_eq_u64( __builtin_bswap64( n ), n ); + + n = UINT64_C( 1 ); + T_eq_u64( __builtin_bswap64( n ), n << 56 ); + + n = UINT64_C( 0x123456789abcdef0 ); + T_eq_u64( __builtin_bswap64( n ), UINT64_C( 0xf0debc9a78563412 ) ); + + n = ~UINT64_C( 0 ); + T_eq_u64( __builtin_bswap64( n ), n ); +} + +/** + * @brief Check signed 64-bit comparisons for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_12( void ) +{ + volatile int64_t a; + volatile int64_t b; + + a = 0; + RTEMS_OBFUSCATE_VARIABLE( a ); + b = 0; + RTEMS_OBFUSCATE_VARIABLE( b ); + + a = INT64_C( 0 ); + b = INT64_C( 0 ); + T_false( a < b ); + + a = INT64_C( 0 ); + b = INT64_C( 1 ); + T_true( a < b ); + + a = INT64_C( 0x123456789abcdef0 ); + b = INT64_C( 0xf0debc9a78563412 ); + T_false( a < b ); + + a = INT64_C( 0xf0debc9a78563412 ); + b = INT64_C( 0x123456789abcdef0 ); + T_true( a < b ); +} + +/** + * @brief Check unsigned 64-bit comparisons for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_13( void ) +{ + volatile uint64_t a; + volatile uint64_t b; + + a = 0; + RTEMS_OBFUSCATE_VARIABLE( a ); + b = 0; + RTEMS_OBFUSCATE_VARIABLE( b ); + + a = UINT64_C( 0 ); + b = UINT64_C( 0 ); + T_false( a < b ); + + a = UINT64_C( 0 ); + b = UINT64_C( 1 ); + T_true( a < b ); + + a = UINT64_C( 0x123456789abcdef0 ); + b = UINT64_C( 0xf0debc9a78563412 ); + T_true( a < b ); + + a = UINT64_C( 0xf0debc9a78563412 ); + b = UINT64_C( 0x123456789abcdef0 ); + T_false( a < b ); +} + +/** + * @brief Check signed 64-bit arithmetic left shift for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_14( void ) +{ + volatile int64_t i; + volatile int s; + + i = 0; + RTEMS_OBFUSCATE_VARIABLE( i ); + s = 0; + RTEMS_OBFUSCATE_VARIABLE( s ); + + i = INT64_C( 1 ); + s = 0; + T_eq_i64( i << s, INT64_C( 1 ) ); + + i = -INT64_C( 1 ); + s = 0; + T_eq_i64( i << s, -INT64_C( 1 ) ); + + i = INT64_C( 1 ); + s = 1; + T_eq_i64( i << s, INT64_C( 2 ) ); + + i = -INT64_C( 1 ); + s = 1; + T_eq_i64( i << s, -INT64_C( 2 ) ); +} + +/** + * @brief Check signed 64-bit arithmetic right shift for a sample set of + * values. + */ +static void CompilerUnitBuiltins_Action_15( void ) +{ + volatile int64_t i; + volatile int s; + + i = 0; + RTEMS_OBFUSCATE_VARIABLE( i ); + s = 0; + RTEMS_OBFUSCATE_VARIABLE( s ); + + i = INT64_C( 1 ); + s = 0; + T_eq_i64( i >> s, INT64_C( 1 ) ); + + i = -INT64_C( 1 ); + s = 0; + T_eq_i64( i >> s, -INT64_C( 1 ) ); + + i = INT64_C( 2 ); + s = 1; + T_eq_i64( i >> s, INT64_C( 1 ) ); + + i = -INT64_C( 2 ); + s = 1; + T_eq_i64( i >> s, -INT64_C( 1 ) ); +} + +/** + * @brief Check unsigned 64-bit logical right shift for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_16( void ) +{ + volatile uint64_t i; + volatile int s; + + i = 0; + RTEMS_OBFUSCATE_VARIABLE( i ); + s = 0; + RTEMS_OBFUSCATE_VARIABLE( s ); + + i = UINT64_C( 1 ); + s = 0; + T_eq_u64( i >> s, UINT64_C( 1 ) ); + + i = -UINT64_C( 1 ); + s = 0; + T_eq_u64( i >> s, UINT64_C( 0xffffffffffffffff ) ); + + i = UINT64_C( 2 ); + s = 1; + T_eq_u64( i >> s, UINT64_C( 1 ) ); + + i = -UINT64_C( 2 ); + s = 1; + T_eq_u64( i >> s, UINT64_C( 0x7fffffffffffffff ) ); +} + +/** + * @brief Check signed 64-bit multiplication for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_17( void ) +{ + volatile int64_t a; + volatile int64_t b; + + a = 0; + RTEMS_OBFUSCATE_VARIABLE( a ); + b = 0; + RTEMS_OBFUSCATE_VARIABLE( b ); + + a = INT64_C( 1 ); + b = INT64_C( 1 ); + T_eq_i64( a * b, INT64_C( 1 ) ); + + a = INT64_C( 1 ); + b = INT64_C( 0 ); + T_eq_i64( a * b, INT64_C( 0 ) ); + + a = INT64_C( 0 ); + b = INT64_C( 1 ); + T_eq_i64( a * b, INT64_C( 0 ) ); +} + +/** + * @brief Check signed 64-bit negation for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_18( void ) +{ + volatile int64_t i; + + i = 0; + RTEMS_OBFUSCATE_VARIABLE( i ); + + i = INT64_C( 1 ); + T_eq_i64( -i, -INT64_C( 1 ) ); + + i = -INT64_C( 1 ); + T_eq_i64( -i, INT64_C( 1 ) ); +} + +/** + * @brief Check signed 64-bit divisions for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_19( void ) +{ + volatile int64_t n; + volatile int64_t d; + volatile int64_t x; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + d = 0; + RTEMS_OBFUSCATE_VARIABLE( d ); + x = 0; + RTEMS_OBFUSCATE_VARIABLE( x ); + + n = INT64_C( 0 ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + n = INT64_C( 1 ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + n = INT64_C( 0x7fffffff00000000 ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + n = INT64_C( 0 ); + d = INT64_C( 1 ); + T_eq_i64( n / d, INT64_C( 0 ) ); + + n = INT64_C( 1 ); + d = INT64_C( 1 ); + T_eq_i64( n / d, INT64_C( 1 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 1 ); + T_eq_i64( n / d, INT64_C( 9223372036854775807 ) ); + + n = INT64_C( 2 ); + d = INT64_C( 1 ); + T_eq_i64( n / d, INT64_C( 2 ) ); + + n = INT64_C( 2 ); + d = INT64_C( 1 ); + T_eq_i64( n / d, INT64_C( 2 ) ); + + n = INT64_C( 1 ); + d = INT64_C( 0x7fffffffffffffff ); + T_eq_i64( n / d, INT64_C( 0 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x7fffffffffffffff ); + T_eq_i64( n / d, INT64_C( 1 ) ); + + n = INT64_C( 1 ); + d = INT64_C( 0x7fffffff00000000 ); + T_eq_i64( n / d, INT64_C( 0 ) ); + + n = INT64_C( 0x7fffffff00000000 ); + d = INT64_C( 0x7fffffff00000000 ); + T_eq_i64( n / d, INT64_C( 1 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x7fffffff00000000 ); + T_eq_i64( n / d, INT64_C( 1 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x8000000000000000 ); + T_eq_i64( n / d, INT64_C( 0 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x0000000080000000 ); + T_eq_i64( n / d, INT64_C( 0xffffffff ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x00000000f0000000 ); + T_eq_i64( n / d, INT64_C( 2290649224 ) ); + + n = INT64_C( 0x00000001ffffffff ); + d = INT64_C( 0x00000000f0000000 ); + T_eq_i64( n / d, INT64_C( 2 ) ); + + n = INT64_C( 0x0000000fffffffff ); + d = INT64_C( 0x000000000000000f ); + T_eq_i64( n / d, INT64_C( 4581298449 ) ); + + n = INT64_C( 0x0000000100000001 ); + d = INT64_C( 0x0000000f00000000 ); + T_eq_i64( n / d, INT64_C( 0 ) ); + + n = INT64_C( 0x0000000f0000000f ); + d = INT64_C( 0x000000ff0000000f ); + T_eq_i64( n / d, INT64_C( 0 ) ); +} + +/** + * @brief Check unsigned 64-bit divisions for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_20( void ) +{ + volatile uint64_t n; + volatile uint64_t d; + volatile uint64_t x; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + d = 0; + RTEMS_OBFUSCATE_VARIABLE( d ); + x = 0; + RTEMS_OBFUSCATE_VARIABLE( x ); + + n = UINT64_C( 0 ); + d = UINT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + __udivmoddi4( n, d, NULL ); + } + #endif + + n = UINT64_C( 1 ); + d = UINT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + __udivmoddi4( n, d, NULL ); + } + #endif + + n = UINT64_C( 0x7fffffffffffffff ); + d = UINT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + __udivmoddi4( n, d, NULL ); + } + #endif + + n = UINT64_C( 0x7fffffff00000000 ); + d = UINT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + __udivmoddi4( n, d, NULL ); + } + #endif + + n = UINT64_C( 0x7fffffff00000000 ); + d = UINT64_C( 0x7fffffff00000000 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n / d; + } + + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + __udivmoddi4( n, d, NULL ); + } + #endif + + n = UINT64_C( 0 ); + d = UINT64_C( 1 ); + T_eq_u64( n / d, UINT64_C( 0 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 0 ) ); + #endif + + n = UINT64_C( 1 ); + d = UINT64_C( 1 ); + T_eq_u64( n / d, UINT64_C( 1 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 1 ) ); + #endif + + n = UINT64_C( 0xffffffffffffffff ); + d = UINT64_C( 1 ); + T_eq_u64( n / d, UINT64_C( 0xffffffffffffffff ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 0xffffffffffffffff ) ); + #endif + + n = UINT64_C( 2 ); + d = UINT64_C( 1 ); + T_eq_u64( n / d, UINT64_C( 2 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 2 ) ); + #endif + + n = UINT64_C( 1 ); + d = UINT64_C( 0xffffffffffffffff ); + T_eq_u64( n / d, UINT64_C( 0 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 0 ) ); + #endif + + n = UINT64_C( 0xffffffffffffffff ); + d = UINT64_C( 0xffffffffffffffff ); + T_eq_u64( n / d, UINT64_C( 1 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 1 ) ); + #endif + + n = UINT64_C( 0xffffffffffffffff ); + d = UINT64_C( 0x8000000000000000 ); + T_eq_u64( n / d, UINT64_C( 1 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 1 ) ); + #endif + + n = UINT64_C( 0x0000000100000001 ); + d = UINT64_C( 0x0000000f00000000 ); + T_eq_u64( n / d, UINT64_C( 0 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 0 ) ); + #endif + + n = UINT64_C( 0x0000000100000000 ); + d = UINT64_C( 0x0000000f00000001 ); + T_eq_u64( n / d, UINT64_C( 0 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 0 ) ); + #endif + + n = UINT64_C( 0xffffffff0000000f ); + d = UINT64_C( 0x000000010000000f ); + T_eq_u64( n / d, UINT64_C( 4294967280 ) ); + #if defined(TEST_UDIVMODDI4_WITHOUT_REMINDER) + T_eq_u64( __udivmoddi4( n, d, NULL ), UINT64_C( 4294967280 ) ); + #endif +} + +/** + * @brief Check signed 64-bit modulo operations for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_21( void ) +{ + volatile int64_t n; + volatile int64_t d; + volatile int64_t x; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + d = 0; + RTEMS_OBFUSCATE_VARIABLE( d ); + x = 0; + RTEMS_OBFUSCATE_VARIABLE( x ); + + n = INT64_C( 0 ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n % d; + } + + n = INT64_C( 1 ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n % d; + } + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n % d; + } + + n = INT64_C( 0x7fffffff00000000 ); + d = INT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n % d; + } + + n = INT64_C( 0 ); + d = INT64_C( 1 ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 1 ); + d = INT64_C( 1 ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 1 ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 2 ); + d = INT64_C( 1 ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 2 ); + d = INT64_C( 1 ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 1 ); + d = INT64_C( 0x7fffffffffffffff ); + T_eq_i64( n % d, INT64_C( 1 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x7fffffffffffffff ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 1 ); + d = INT64_C( 0x7fffffff00000000 ); + T_eq_i64( n % d, INT64_C( 1 ) ); + + n = INT64_C( 0x7fffffff00000000 ); + d = INT64_C( 0x7fffffff00000000 ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x7fffffff00000000 ); + T_eq_i64( n % d, INT64_C( 0xffffffff ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x8000000000000000 ); + T_eq_i64( n % d, INT64_C( 0x7fffffffffffffff ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x0000000080000000 ); + T_eq_i64( n % d, INT64_C( 2147483647 ) ); + + n = INT64_C( 0x7fffffffffffffff ); + d = INT64_C( 0x00000000f0000000 ); + T_eq_i64( n % d, INT64_C( 2147483647 ) ); + + n = INT64_C( 0x00000001ffffffff ); + d = INT64_C( 0x00000000f0000000 ); + T_eq_i64( n % d, INT64_C( 536870911 ) ); + + n = INT64_C( 0x0000000fffffffff ); + d = INT64_C( 0x000000000000000f ); + T_eq_i64( n % d, INT64_C( 0 ) ); + + n = INT64_C( 0x0000000100000001 ); + d = INT64_C( 0x0000000f00000000 ); + T_eq_i64( n % d, INT64_C( 4294967297 ) ); + + n = INT64_C( 0x0000000f0000000f ); + d = INT64_C( 0x000000ff0000000f ); + T_eq_i64( n % d, INT64_C( 64424509455 ) ); + + #if defined(TEST_UDIVMODDI4) + /* + * The above test cases may use __udivmoddi4(). However, the below + * parameter values for __udivmoddi4() cannot be obtained through the + * signed modulo or division operations. On some targets, calls to + * __udivmoddi4() may result from complex optimizations. + */ + n = INT64_C( 0xffffffff0000000f ); + d = INT64_C( 0x000000010000000f ); + T_eq_u64( __udivmoddi4( n, d, NULL ), INT64_C( 4294967280 ) ); + #endif +} + +/** + * @brief Check unsigned 64-bit modulo operations for a sample set of values. + */ +static void CompilerUnitBuiltins_Action_22( void ) +{ + volatile uint64_t n; + volatile uint64_t d; + volatile uint64_t x; + + n = 0; + RTEMS_OBFUSCATE_VARIABLE( n ); + d = 0; + RTEMS_OBFUSCATE_VARIABLE( d ); + x = 0; + RTEMS_OBFUSCATE_VARIABLE( x ); + + n = UINT64_C( 0 ); + d = UINT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n % d; + } + + n = UINT64_C( 1 ); + d = UINT64_C( 0 ); + do_longjmp = true; + + if ( setjmp( exception_return_context ) == 0 ) { + x = n % d; + } + + n = UINT64_C( 0 ); + d = UINT64_C( 1 ); + T_eq_u64( n % d, UINT64_C( 0 ) ); + + n = UINT64_C( 1 ); + d = UINT64_C( 1 ); + T_eq_u64( n % d, UINT64_C( 0 ) ); + + n = UINT64_C( 0xffffffffffffffff ); + d = UINT64_C( 1 ); + T_eq_u64( n % d, UINT64_C( 0 ) ); + + n = UINT64_C( 2 ); + d = UINT64_C( 1 ); + T_eq_u64( n % d, UINT64_C( 0 ) ); + + n = UINT64_C( 1 ); + d = UINT64_C( 0xffffffffffffffff ); + T_eq_u64( n % d, UINT64_C( 1 ) ); + + n = UINT64_C( 0xffffffffffffffff ); + d = UINT64_C( 0xffffffffffffffff ); + T_eq_u64( n % d, UINT64_C( 0 ) ); +} + +/** + * @fn void T_case_body_CompilerUnitBuiltins( void ) + */ +T_TEST_CASE_FIXTURE( CompilerUnitBuiltins, &CompilerUnitBuiltins_Fixture ) +{ + CompilerUnitBuiltins_Action_0(); + CompilerUnitBuiltins_Action_1(); + CompilerUnitBuiltins_Action_2(); + CompilerUnitBuiltins_Action_3(); + CompilerUnitBuiltins_Action_4(); + CompilerUnitBuiltins_Action_5(); + CompilerUnitBuiltins_Action_6(); + CompilerUnitBuiltins_Action_7(); + CompilerUnitBuiltins_Action_8(); + CompilerUnitBuiltins_Action_9(); + CompilerUnitBuiltins_Action_10(); + CompilerUnitBuiltins_Action_11(); + CompilerUnitBuiltins_Action_12(); + CompilerUnitBuiltins_Action_13(); + CompilerUnitBuiltins_Action_14(); + CompilerUnitBuiltins_Action_15(); + CompilerUnitBuiltins_Action_16(); + CompilerUnitBuiltins_Action_17(); + CompilerUnitBuiltins_Action_18(); + CompilerUnitBuiltins_Action_19(); + CompilerUnitBuiltins_Action_20(); + CompilerUnitBuiltins_Action_21(); + CompilerUnitBuiltins_Action_22(); +} + +/** @} */ diff --git a/testsuites/unit/tc-config.c b/testsuites/unit/tc-config.c new file mode 100644 index 0000000000..415142e1b4 --- /dev/null +++ b/testsuites/unit/tc-config.c @@ -0,0 +1,171 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup RtemsConfigUnitConfig + */ + +/* + * Copyright (C) 2021 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This file is part of the RTEMS quality process and was automatically + * generated. If you find something that needs to be fixed or + * worded better please post a report or patch to an RTEMS mailing list + * or raise a bug report: + * + * https://www.rtems.org/bugs.html + * + * For information on updating and regenerating please refer to the How-To + * section in the Software Requirements Engineering chapter of the + * RTEMS Software Engineering manual. The manual is provided as a part of + * a release. For development sources please refer to the online + * documentation at: + * + * https://docs.rtems.org + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <rtems.h> +#include <rtems/rtems/semdata.h> +#include <rtems/score/object.h> +#include <rtems/score/objectdata.h> + +#include <rtems/test.h> + +/** + * @defgroup RtemsConfigUnitConfig spec:/rtems/config/unit/config + * + * @ingroup TestsuitesUnitNoClock0 + * + * @brief Unit tests for the configuration manager. + * + * Parts of the file ``cpukit/sapi/src/getconfigmax.c`` are only executed when + * unlimited objects are configured. The space qualified code subset does not + * support this feature. This test exercises the code parts otherwise not + * reached in order to achieve full code coverage. + * + * This test case performs the following actions: + * + * - Call get_config_max() indirectly through + * rtems_configuration_get_maximum_semaphores() with a specially manipulated + * argument to enter an if-branch only accessed when unlimited objects are + * configured. + * + * - The value returned by the function call must be the one artificially + * injected by this test. + * + * @{ + */ + +#define SEMAPHORES_PER_BLOCK 32 + +/** + * @brief Test context for spec:/rtems/config/unit/config test case. + */ +typedef struct { + /** + * @brief This member contains the original value of + * ``_Semaphore_Information->objects_per_block``. + */ + Objects_Maximum objects_per_block_ori; +} RtemsConfigUnitConfig_Context; + +static RtemsConfigUnitConfig_Context + RtemsConfigUnitConfig_Instance; + +static void RtemsConfigUnitConfig_Setup( RtemsConfigUnitConfig_Context *ctx ) +{ + ctx->objects_per_block_ori = _Semaphore_Information.objects_per_block; + _Semaphore_Information.objects_per_block = SEMAPHORES_PER_BLOCK; +} + +static void RtemsConfigUnitConfig_Setup_Wrap( void *arg ) +{ + RtemsConfigUnitConfig_Context *ctx; + + ctx = arg; + RtemsConfigUnitConfig_Setup( ctx ); +} + +static void RtemsConfigUnitConfig_Teardown( + RtemsConfigUnitConfig_Context *ctx +) +{ + _Semaphore_Information.objects_per_block = ctx->objects_per_block_ori; +} + +static void RtemsConfigUnitConfig_Teardown_Wrap( void *arg ) +{ + RtemsConfigUnitConfig_Context *ctx; + + ctx = arg; + RtemsConfigUnitConfig_Teardown( ctx ); +} + +static T_fixture RtemsConfigUnitConfig_Fixture = { + .setup = RtemsConfigUnitConfig_Setup_Wrap, + .stop = NULL, + .teardown = RtemsConfigUnitConfig_Teardown_Wrap, + .scope = NULL, + .initial_context = &RtemsConfigUnitConfig_Instance +}; + +/** + * @brief Call get_config_max() indirectly through + * rtems_configuration_get_maximum_semaphores() with a specially manipulated + * argument to enter an if-branch only accessed when unlimited objects are + * configured. + */ +static void RtemsConfigUnitConfig_Action_0( + RtemsConfigUnitConfig_Context *ctx +) +{ + uint32_t max = rtems_configuration_get_maximum_semaphores(); + + /* + * The value returned by the function call must be the one artificially + * injected by this test. + */ + T_eq_u32( max, SEMAPHORES_PER_BLOCK | RTEMS_UNLIMITED_OBJECTS ); +} + +/** + * @fn void T_case_body_RtemsConfigUnitConfig( void ) + */ +T_TEST_CASE_FIXTURE( RtemsConfigUnitConfig, &RtemsConfigUnitConfig_Fixture ) +{ + RtemsConfigUnitConfig_Context *ctx; + + ctx = T_fixture_context(); + + RtemsConfigUnitConfig_Action_0( ctx ); +} + +/** @} */ diff --git a/testsuites/unit/tc-crc.c b/testsuites/unit/tc-crc.c new file mode 100644 index 0000000000..d33a837860 --- /dev/null +++ b/testsuites/unit/tc-crc.c @@ -0,0 +1,48 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup TestsuitesUnitNoClock0 + */ + +/* + * Copyright (C) 2023 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <rtems/crc.h> + +#include <rtems/test.h> + +T_TEST_CASE(CRC24Q) { + uint32_t state = _CRC24Q_Update(CRC24Q_SEED, 0); + T_eq_u32(state, 0); + state = _CRC24Q_Update(CRC24Q_SEED, '1'); + state = _CRC24Q_Update(state, '2'); + state = _CRC24Q_Update(state, '3'); + T_eq_u32(state & CRC24Q_MASK, 0x2c3045); + uint8_t bytes[] = {'1', '2', '3'}; + state = _CRC24Q_Sequence_update(CRC24Q_SEED, &bytes[0], sizeof(bytes)); + T_eq_u32(state & CRC24Q_MASK, 0x2c3045); +} diff --git a/testsuites/unit/tc-misaligned-builtin-memcpy.c b/testsuites/unit/tc-misaligned-builtin-memcpy.c new file mode 100644 index 0000000000..6ce19e0521 --- /dev/null +++ b/testsuites/unit/tc-misaligned-builtin-memcpy.c @@ -0,0 +1,57 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup TestsuitesUnitNoClock0 + */ + +/* + * Copyright (C) 2019 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <string.h> + +#include <rtems.h> + +#include <rtems/test.h> + +T_TEST_CASE(MisalignedBuiltinMemcpy) +{ + double a; + double b; + char buf[2 * sizeof(double)]; + void *p; + + p = &buf[0]; + p = (void *)((uintptr_t)p | 1); + RTEMS_OBFUSCATE_VARIABLE(p); + a = 123e4; + RTEMS_OBFUSCATE_VARIABLE(a); + a *= a; + memcpy(p, &a, sizeof(a)); + RTEMS_OBFUSCATE_VARIABLE(p); + memcpy(&b, p, sizeof(b)); + T_eq(a, b, "%f == %f", a, b); +} diff --git a/testsuites/unit/tc-score-msgq.c b/testsuites/unit/tc-score-msgq.c new file mode 100644 index 0000000000..c4cb690c2f --- /dev/null +++ b/testsuites/unit/tc-score-msgq.c @@ -0,0 +1,452 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup ScoreMsgqUnitMsgq + */ + +/* + * Copyright (C) 2021 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This file is part of the RTEMS quality process and was automatically + * generated. If you find something that needs to be fixed or + * worded better please post a report or patch to an RTEMS mailing list + * or raise a bug report: + * + * https://www.rtems.org/bugs.html + * + * For information on updating and regenerating please refer to the How-To + * section in the Software Requirements Engineering chapter of the + * RTEMS Software Engineering manual. The manual is provided as a part of + * a release. For development sources please refer to the online + * documentation at: + * + * https://docs.rtems.org + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <rtems.h> +#include <rtems/rtems/messageimpl.h> +#include <rtems/rtems/statusimpl.h> +#include <rtems/score/coremsgimpl.h> + +#include "../validation/tx-support.h" + +#include <rtems/test.h> + +/** + * @defgroup ScoreMsgqUnitMsgq spec:/score/msgq/unit/msgq + * + * @ingroup TestsuitesUnitNoClock0 + * + * @brief Unit tests for the Message Queue Handler. + * + * Parts of the files ``cpukit/score/src/coremsginsert.c``, + * ``cpukit/score/src/coremsgseize.c``, and + * ``cpukit/score/src/coremsgsubmit.c`` are only executed by the POSIX API. + * Currently, the pre-qualified subset of RTEMS does not contain the POSIX API. + * This test exercises the code parts otherwise only reached by the POSIX API + * to achieve full code coverage. + * + * This test case performs the following actions: + * + * - Use _CORE_message_queue_Insert_message() to insert two messages into a + * message queue and use the POSIX message priority to define their order in + * the queue. + * + * - Check that _CORE_message_queue_Submit() was executed successfully. + * + * - Check that the messages are in the right order in the message queue. + * + * - Submit three messages into a message queue which can only store two and + * have the third submit() blocked till a seize() occurs. + * + * - Check that the third _CORE_message_queue_Submit() did actually block + * till there was room for the message in the message queue. + * + * - Submit messages in the queue from within an ISR. + * + * - Check that the first two messages were successfully send. + * + * - Check that trying to send the third message from ISR when the message + * queue was full was rejected. + * + * @{ + */ + +#define MAXIMUM_PENDING_MESSAGES 2 +#define MAXIMUM_MESSAGE_SIZE 3 + +static void WorkerTask( rtems_task_argument argument ); + +/** + * @brief Test context for spec:/score/msgq/unit/msgq test case. + */ +typedef struct { + /** + * @brief This member contains a valid ID of a message queue. + */ + rtems_id message_queue_id; + + /** + * @brief This member is used as storage area for the message queue. + */ + RTEMS_MESSAGE_QUEUE_BUFFER( MAXIMUM_MESSAGE_SIZE ) + storage_area[ MAXIMUM_PENDING_MESSAGES]; + + /** + * @brief This member contains the task identifier of the worker task. + */ + rtems_id worker_id; + + /** + * @brief This member indicated whether the worker task is currently sending + * a message (``true``) or whether it is waiting to receive an event + * (``false``). + */ + bool is_worker_working; + + /** + * @brief This member contains the returned status code of the SendMessage() + * function. + */ + rtems_status_code send_status; +} ScoreMsgqUnitMsgq_Context; + +static ScoreMsgqUnitMsgq_Context + ScoreMsgqUnitMsgq_Instance; + +#define EVENT_SEND RTEMS_EVENT_17 +#define MESSAGE_CONTENT_LOW { 1, 2, 3 } +#define MESSAGE_CONTENT_HIGH { 4, 5 } +#define MESSAGE_PRIORITY_LOW 5 +#define MESSAGE_PRIORITY_HIGH 7 +#define DO_WAIT true + +typedef ScoreMsgqUnitMsgq_Context Context; + +/* + * This is a code fragment from rtems_message_queue_send() with the + * specialty that it uses a POSIX priority and the sender + * task will wait in case the queue is full. + */ +static rtems_status_code SubmitMessage( + rtems_id id, + uint8_t *message, + size_t message_size, + unsigned int posix_piority +) +{ + rtems_status_code status; + Thread_queue_Context queue_context; + Message_queue_Control *the_message_queue; + + T_assert_lt_uint( posix_piority, MQ_PRIO_MAX ); + + the_message_queue = _Message_queue_Get( + id, + &queue_context + ); + T_assert_not_null( the_message_queue ); + + /* The next two calls are from _POSIX_Message_queue_Send_support() */ + _Thread_queue_Context_set_enqueue_callout( + &queue_context, + _Thread_queue_Enqueue_do_nothing_extra + ); + _Thread_queue_Context_set_timeout_argument( &queue_context, NULL, true ); + + _CORE_message_queue_Acquire_critical( + &the_message_queue->message_queue, + &queue_context + ); + + status = _CORE_message_queue_Submit( + &the_message_queue->message_queue, + _Thread_Executing, + message, + message_size, + (CORE_message_queue_Submit_types) ( posix_piority * -1 ), + DO_WAIT, + &queue_context + ); + + return _Status_Get( status ); +} + +static rtems_status_code ReceiveMessage( + rtems_id id, + void *buffer, + size_t *size +) +{ + return rtems_message_queue_receive( + id, + buffer, + size, + RTEMS_LOCAL | RTEMS_NO_WAIT, + RTEMS_NO_TIMEOUT + ); +} + +static rtems_status_code ReceiveOneMessages( Context *ctx ) +{ + uint8_t message_buffer[ MAXIMUM_MESSAGE_SIZE ]; + size_t message_size; + + return ReceiveMessage( + ctx->message_queue_id, + &message_buffer, + &message_size + ); +} + +static void SendMessage( Context *ctx ) +{ + uint8_t message[] = { 100, 101, 102 }; + ctx->send_status = SubmitMessage( + ctx->message_queue_id, + message, + sizeof( message ), + MESSAGE_PRIORITY_LOW + ); +} + +static void WorkerTask( rtems_task_argument argument ) +{ + Context *ctx = (Context *) argument; + + while ( true ) { + ctx->is_worker_working = false; + ReceiveAnyEvents(); + ctx->is_worker_working = true; + SendMessage( ctx ); + T_assert_rsc_success( ctx->send_status ); + } +} + +static void WorkerSendMessage( Context *ctx ) +{ + SendEvents( ctx->worker_id, EVENT_SEND ); +} + +static void ScoreMsgqUnitMsgq_Setup( ScoreMsgqUnitMsgq_Context *ctx ) +{ + rtems_status_code status; + rtems_message_queue_config config = { + .name = rtems_build_name( 'M', 'S', 'G', 'Q' ), + .maximum_pending_messages = MAXIMUM_PENDING_MESSAGES, + .maximum_message_size = MAXIMUM_MESSAGE_SIZE, + .storage_area = ctx->storage_area, + .storage_size = sizeof( ctx->storage_area ), + .storage_free = NULL, + .attributes = RTEMS_DEFAULT_ATTRIBUTES + }; + + status = rtems_message_queue_construct( + &config, + &ctx->message_queue_id + ); + T_rsc_success( status ); + + SetSelfPriority( PRIO_NORMAL ); + + ctx->worker_id = CreateTask( "WORK", PRIO_HIGH ); + StartTask( ctx->worker_id, WorkerTask, ctx ); +} + +static void ScoreMsgqUnitMsgq_Setup_Wrap( void *arg ) +{ + ScoreMsgqUnitMsgq_Context *ctx; + + ctx = arg; + ScoreMsgqUnitMsgq_Setup( ctx ); +} + +static void ScoreMsgqUnitMsgq_Teardown( ScoreMsgqUnitMsgq_Context *ctx ) +{ + DeleteTask( ctx->worker_id ); + RestoreRunnerPriority(); + T_rsc_success( rtems_message_queue_delete( ctx->message_queue_id ) ); +} + +static void ScoreMsgqUnitMsgq_Teardown_Wrap( void *arg ) +{ + ScoreMsgqUnitMsgq_Context *ctx; + + ctx = arg; + ScoreMsgqUnitMsgq_Teardown( ctx ); +} + +static T_fixture ScoreMsgqUnitMsgq_Fixture = { + .setup = ScoreMsgqUnitMsgq_Setup_Wrap, + .stop = NULL, + .teardown = ScoreMsgqUnitMsgq_Teardown_Wrap, + .scope = NULL, + .initial_context = &ScoreMsgqUnitMsgq_Instance +}; + +/** + * @brief Use _CORE_message_queue_Insert_message() to insert two messages into + * a message queue and use the POSIX message priority to define their order + * in the queue. + */ +static void ScoreMsgqUnitMsgq_Action_0( ScoreMsgqUnitMsgq_Context *ctx ) +{ + rtems_status_code status_submit_low; + rtems_status_code status_submit_high; + rtems_status_code status_receive_low; + rtems_status_code status_receive_high; + uint8_t message_low[] = MESSAGE_CONTENT_LOW; + uint8_t message_high[] = MESSAGE_CONTENT_HIGH; + uint8_t message_buffer_low[ MAXIMUM_MESSAGE_SIZE ]; + uint8_t message_buffer_high[ MAXIMUM_MESSAGE_SIZE ]; + size_t message_size_low; + size_t message_size_high; + + status_submit_low = SubmitMessage( + ctx->message_queue_id, + message_low, + sizeof( message_low ), + MESSAGE_PRIORITY_LOW + ); + + status_submit_high = SubmitMessage( + ctx->message_queue_id, + message_high, + sizeof( message_high ), + MESSAGE_PRIORITY_HIGH + ); + + status_receive_high = ReceiveMessage( + ctx->message_queue_id, + &message_buffer_high, + &message_size_high + ); + + status_receive_low = ReceiveMessage( + ctx->message_queue_id, + &message_buffer_low, + &message_size_low + ); + + /* + * Check that _CORE_message_queue_Submit() was executed successfully. + */ + T_rsc_success( status_submit_low ); + T_rsc_success( status_submit_high ); + + /* + * Check that the messages are in the right order in the message queue. + */ + T_rsc_success( status_receive_high ); + T_eq_sz( message_size_high, sizeof( message_high ) ); + T_eq_mem( message_buffer_high, message_high, message_size_high ); + + T_rsc_success( status_receive_low ); + T_eq_sz( message_size_low, sizeof( message_low ) ); + T_eq_mem( message_buffer_low, message_low, message_size_low ); +} + +/** + * @brief Submit three messages into a message queue which can only store two + * and have the third submit() blocked till a seize() occurs. + */ +static void ScoreMsgqUnitMsgq_Action_1( ScoreMsgqUnitMsgq_Context *ctx ) +{ + bool is_worker_blocked_after_third_send; + bool is_worker_blocked_after_first_receive; + + WorkerSendMessage( ctx ); + WorkerSendMessage( ctx ); + WorkerSendMessage( ctx ); + is_worker_blocked_after_third_send = ctx->is_worker_working; + + T_rsc_success( ReceiveOneMessages( ctx ) ); + is_worker_blocked_after_first_receive = ctx->is_worker_working; + + T_rsc_success( ReceiveOneMessages( ctx ) ); + T_rsc_success( ReceiveOneMessages( ctx ) ); + + /* + * Check that the third _CORE_message_queue_Submit() did actually block till + * there was room for the message in the message queue. + */ + T_true( is_worker_blocked_after_third_send ); + T_true( !is_worker_blocked_after_first_receive ); +} + +/** + * @brief Submit messages in the queue from within an ISR. + */ +static void ScoreMsgqUnitMsgq_Action_2( ScoreMsgqUnitMsgq_Context *ctx ) +{ + rtems_status_code status_send_first_message; + rtems_status_code status_send_second_message; + rtems_status_code status_send_third_message; + + CallWithinISR( ( void (*)(void*) ) SendMessage, ctx ); + status_send_first_message = ctx->send_status; + CallWithinISR( ( void (*)(void*) ) SendMessage, ctx ); + status_send_second_message = ctx->send_status; + CallWithinISR( ( void (*)(void*) ) SendMessage, ctx ); + status_send_third_message = ctx->send_status; + + T_rsc_success( ReceiveOneMessages( ctx ) ); + T_rsc_success( ReceiveOneMessages( ctx ) ); + + /* + * Check that the first two messages were successfully send. + */ + T_assert_rsc_success( status_send_first_message ); + T_assert_rsc_success( status_send_second_message ); + + /* + * Check that trying to send the third message from ISR when the message + * queue was full was rejected. + */ + T_rsc( status_send_third_message, STATUS_CLASSIC_INTERNAL_ERROR ); +} + +/** + * @fn void T_case_body_ScoreMsgqUnitMsgq( void ) + */ +T_TEST_CASE_FIXTURE( ScoreMsgqUnitMsgq, &ScoreMsgqUnitMsgq_Fixture ) +{ + ScoreMsgqUnitMsgq_Context *ctx; + + ctx = T_fixture_context(); + + ScoreMsgqUnitMsgq_Action_0( ctx ); + ScoreMsgqUnitMsgq_Action_1( ctx ); + ScoreMsgqUnitMsgq_Action_2( ctx ); +} + +/** @} */ diff --git a/testsuites/unit/tc-score-rbtree.c b/testsuites/unit/tc-score-rbtree.c new file mode 100644 index 0000000000..ec286838d0 --- /dev/null +++ b/testsuites/unit/tc-score-rbtree.c @@ -0,0 +1,1195 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup ScoreRbtreeUnitRbtree + */ + +/* + * Copyright (C) 2021 embedded brains GmbH & Co. KG + * Copyright (C) 2010 Gedare Bloom + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This file is part of the RTEMS quality process and was automatically + * generated. If you find something that needs to be fixed or + * worded better please post a report or patch to an RTEMS mailing list + * or raise a bug report: + * + * https://www.rtems.org/bugs.html + * + * For information on updating and regenerating please refer to the How-To + * section in the Software Requirements Engineering chapter of the + * RTEMS Software Engineering manual. The manual is provided as a part of + * a release. For development sources please refer to the online + * documentation at: + * + * https://docs.rtems.org + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <string.h> +#include <rtems/score/rbtreeimpl.h> + +#include <rtems/test.h> + +/** + * @defgroup ScoreRbtreeUnitRbtree spec:/score/rbtree/unit/rbtree + * + * @ingroup TestsuitesUnitNoClock0 + * + * @brief Unit tests for the red-black tree implementation. + * + * The red-black trees are used by various handlers for priority queues and the + * timers. + * + * This test case performs the following actions: + * + * - Call _RBTree_Initialize_one() and check the tree properties. + * + * - Check that the tree is not emtpy. + * + * - Check that the tree root is is the only node. + * + * - Check that the node is not off the tree. + * + * - Check that the node has no left child. + * + * - Check that the node has no right child. + * + * - Check that the node has no parent. + * + * - Check that the node has no successor. + * + * - Check that the node has no predecessor. + * + * - Check that the minimum node is the node. + * + * - Check that the maximum node is the node. + * + * - Check that the tree is emtpy after extraction of the node. + * + * - Call _RBTree_Insert_inline() and check the return status for a sample set + * of nodes. + * + * - Insert the first node. Check that it is the new minimum node. + * + * - Insert the second node. Check that it is not the new minimum node. + * + * - Insert the third node. Check that it is the new minimum node. + * + * - Call _RBTree_Insert_inline() and _RBTree_Extract() for a sample set of + * trees. + * + * @{ + */ + +typedef struct { + int id; + int key; + RBTree_Node Node; +} TestNode; + +static TestNode node_array[ 100 ]; + +static int Color( const RBTree_Node *n ) +{ + return RB_COLOR( n, Node ); +} + +static bool Less( const void *left, const RBTree_Node *right ) +{ + const int *the_left; + const TestNode *the_right; + + the_left = left; + the_right = RTEMS_CONTAINER_OF( right, TestNode, Node ); + + return *the_left < the_right->key; +} + +/* + * recursively checks tree. if the tree is built properly it should only + * be a depth of 7 function calls for 100 entries in the tree. + */ +static int VerifyTree( RBTree_Node *root ) +{ + RBTree_Node *ln; + RBTree_Node *rn; + TestNode *tn; + TestNode *ltn; + TestNode *rtn; + int lh; + int rh; + + if ( root == NULL ) { + return 1; + } + + ln = _RBTree_Left( root ); + rn = _RBTree_Right( root ); + tn = RTEMS_CONTAINER_OF( root, TestNode, Node ); + ltn = RTEMS_CONTAINER_OF( ln, TestNode, Node ); + rtn = RTEMS_CONTAINER_OF( rn, TestNode, Node ); + + /* Consecutive red links */ + if ( + Color( root ) == RB_RED && + ( ( ln != NULL && Color( ln ) == RB_RED ) || + ( rn != NULL && Color( rn ) == RB_RED ) ) + ) { + return -1; + } + + lh = VerifyTree ( ln ); + rh = VerifyTree ( rn ); + + if ( lh == -1 || rh == -1 ) { + return -1; + } + + /* Black height mismatch */ + if ( lh != rh ) { + return -1; + } + + /* Invalid binary search tree */ + if ( + ( ln != NULL && tn->key != ltn->key && !Less( <n->key, root ) ) || + ( rn != NULL && tn->key != rtn->key && !Less( &tn->key, rn ) ) + ) { + return -1; + } + + /* Only count black links */ + return Color( root ) == RB_BLACK ? lh + 1 : lh; +} + +#define TN( i ) &node_array[ i ].Node + +typedef struct { + int key; + const RBTree_Node *parent; + const RBTree_Node *left; + const RBTree_Node *right; + int color; +} TestNodeDescription; + +typedef struct { + int current; + int count; + const TestNodeDescription *tree; +} VisitorContext; + +static bool VisitNodes( + const RBTree_Node *node, + void *visitor_arg +) +{ + VisitorContext *ctx; + const TestNodeDescription *td; + const TestNode *tn; + + ctx = visitor_arg; + td = &ctx->tree[ ctx->current ]; + tn = RTEMS_CONTAINER_OF( node, TestNode, Node ); + + T_lt_int( ctx->current, ctx->count ); + + T_eq_int( td->key, tn->key ); + + if ( td->parent == NULL ) { + T_true( _RBTree_Is_root( &tn->Node ) ); + } else { + T_eq_ptr( td->parent, _RBTree_Parent( &tn->Node ) ); + } + + T_eq_ptr( td->left, _RBTree_Left( &tn->Node ) ); + T_eq_ptr( td->right, _RBTree_Right( &tn->Node ) ); + T_eq_int( td->color, Color( &tn->Node ) ); + + ++ctx->current; + + return false; +} + +static const TestNodeDescription random_ops_tree_unique_1[] = { + { 0, NULL, NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_1[] = { + { 0, NULL, NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_2[] = { +}; + +static const TestNodeDescription random_ops_tree_multiple_2[] = { +}; + +static const TestNodeDescription random_ops_tree_unique_3[] = { + { 2, NULL, NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_3[] = { + { 1, NULL, NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_4[] = { + { 0, TN( 3 ), NULL, NULL, RB_RED }, + { 3, NULL, TN( 0 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_4[] = { + { 0, NULL, NULL, TN( 3 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_5[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, NULL, TN( 0 ), TN( 4 ), RB_BLACK }, + { 4, TN( 1 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_5[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 0, NULL, TN( 0 ), TN( 4 ), RB_BLACK }, + { 2, TN( 1 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_6[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 2, NULL, TN( 0 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_6[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 1, NULL, TN( 0 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_7[] = { + { 0, TN( 2 ), NULL, TN( 1 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED }, + { 2, NULL, TN( 0 ), TN( 5 ), RB_BLACK }, + { 4, TN( 5 ), NULL, NULL, RB_RED }, + { 5, TN( 2 ), TN( 4 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_7[] = { + { 0, TN( 2 ), NULL, TN( 1 ), RB_BLACK }, + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 1, NULL, TN( 0 ), TN( 4 ), RB_BLACK }, + { 2, TN( 4 ), NULL, NULL, RB_RED }, + { 2, TN( 2 ), TN( 5 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_8[] = { + { 0, TN( 1 ), NULL, NULL, RB_BLACK }, + { 1, NULL, TN( 0 ), TN( 6 ), RB_BLACK }, + { 5, TN( 6 ), NULL, NULL, RB_RED }, + { 6, TN( 1 ), TN( 5 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_8[] = { + { 0, TN( 5 ), NULL, TN( 0 ), RB_BLACK }, + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 2, NULL, TN( 1 ), TN( 6 ), RB_BLACK }, + { 3, TN( 5 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_9[] = { + { 1, TN( 2 ), NULL, NULL, RB_BLACK }, + { 2, TN( 6 ), TN( 1 ), TN( 4 ), RB_RED }, + { 4, TN( 2 ), NULL, TN( 5 ), RB_BLACK }, + { 5, TN( 4 ), NULL, NULL, RB_RED }, + { 6, NULL, TN( 2 ), TN( 7 ), RB_BLACK }, + { 7, TN( 6 ), NULL, TN( 8 ), RB_BLACK }, + { 8, TN( 7 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_9[] = { + { 0, TN( 2 ), NULL, NULL, RB_BLACK }, + { 1, TN( 6 ), TN( 1 ), TN( 4 ), RB_RED }, + { 2, TN( 2 ), NULL, TN( 5 ), RB_BLACK }, + { 2, TN( 4 ), NULL, NULL, RB_RED }, + { 3, NULL, TN( 2 ), TN( 7 ), RB_BLACK }, + { 3, TN( 6 ), NULL, TN( 8 ), RB_BLACK }, + { 4, TN( 7 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_10[] = { + { 0, TN( 2 ), NULL, NULL, RB_BLACK }, + { 2, TN( 6 ), TN( 0 ), TN( 4 ), RB_RED }, + { 3, TN( 4 ), NULL, NULL, RB_RED }, + { 4, TN( 2 ), TN( 3 ), NULL, RB_BLACK }, + { 6, NULL, TN( 2 ), TN( 8 ), RB_BLACK }, + { 8, TN( 6 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_10[] = { + { 0, TN( 2 ), NULL, NULL, RB_BLACK }, + { 1, TN( 6 ), TN( 0 ), TN( 4 ), RB_RED }, + { 1, TN( 4 ), NULL, NULL, RB_RED }, + { 2, TN( 2 ), TN( 3 ), NULL, RB_BLACK }, + { 3, NULL, TN( 2 ), TN( 8 ), RB_BLACK }, + { 4, TN( 6 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_11[] = { + { 2, TN( 6 ), NULL, NULL, RB_BLACK }, + { 6, NULL, TN( 2 ), TN( 8 ), RB_BLACK }, + { 7, TN( 8 ), NULL, NULL, RB_RED }, + { 8, TN( 6 ), TN( 7 ), TN( 9 ), RB_BLACK }, + { 9, TN( 8 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_11[] = { + { 1, TN( 6 ), NULL, NULL, RB_BLACK }, + { 3, NULL, TN( 2 ), TN( 8 ), RB_BLACK }, + { 3, TN( 8 ), NULL, NULL, RB_RED }, + { 4, TN( 6 ), TN( 7 ), TN( 9 ), RB_BLACK }, + { 4, TN( 8 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_12[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, TN( 3 ), TN( 0 ), TN( 2 ), RB_BLACK }, + { 2, TN( 1 ), NULL, NULL, RB_RED }, + { 3, TN( 5 ), TN( 1 ), TN( 4 ), RB_RED }, + { 4, TN( 3 ), NULL, NULL, RB_BLACK }, + { 5, NULL, TN( 3 ), TN( 9 ), RB_BLACK }, + { 9, TN( 5 ), NULL, TN( 11 ), RB_BLACK }, + { 11, TN( 9 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_12[] = { + { 0, TN( 1 ), NULL, NULL, RB_BLACK }, + { 0, TN( 5 ), TN( 0 ), TN( 3 ), RB_RED }, + { 1, TN( 1 ), NULL, TN( 2 ), RB_BLACK }, + { 1, TN( 3 ), NULL, NULL, RB_RED }, + { 2, NULL, TN( 1 ), TN( 9 ), RB_BLACK }, + { 2, TN( 9 ), NULL, NULL, RB_BLACK }, + { 4, TN( 5 ), TN( 4 ), TN( 11 ), RB_RED }, + { 5, TN( 9 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_13[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, TN( 3 ), TN( 0 ), NULL, RB_BLACK }, + { 3, TN( 8 ), TN( 1 ), TN( 5 ), RB_RED }, + { 4, TN( 5 ), NULL, NULL, RB_RED }, + { 5, TN( 3 ), TN( 4 ), TN( 6 ), RB_BLACK }, + { 6, TN( 5 ), NULL, NULL, RB_RED }, + { 8, NULL, TN( 3 ), TN( 11 ), RB_BLACK }, + { 10, TN( 11 ), NULL, NULL, RB_RED }, + { 11, TN( 8 ), TN( 10 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_13[] = { + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 0, TN( 3 ), TN( 1 ), NULL, RB_BLACK }, + { 1, TN( 6 ), TN( 0 ), TN( 4 ), RB_RED }, + { 2, TN( 3 ), NULL, TN( 5 ), RB_BLACK }, + { 2, TN( 4 ), NULL, NULL, RB_RED }, + { 3, NULL, TN( 3 ), TN( 11 ), RB_BLACK }, + { 4, TN( 11 ), NULL, NULL, RB_RED }, + { 5, TN( 6 ), TN( 8 ), TN( 10 ), RB_BLACK }, + { 5, TN( 11 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_14[] = { + { 3, TN( 5 ), NULL, NULL, RB_RED }, + { 5, TN( 6 ), TN( 3 ), NULL, RB_BLACK }, + { 6, NULL, TN( 5 ), TN( 12 ), RB_BLACK }, + { 8, TN( 12 ), NULL, NULL, RB_BLACK }, + { 12, TN( 6 ), TN( 8 ), TN( 13 ), RB_RED }, + { 13, TN( 12 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_14[] = { + { 1, TN( 5 ), NULL, NULL, RB_RED }, + { 2, TN( 6 ), TN( 3 ), NULL, RB_BLACK }, + { 3, NULL, TN( 5 ), TN( 13 ), RB_BLACK }, + { 4, TN( 13 ), NULL, NULL, RB_BLACK }, + { 6, TN( 6 ), TN( 8 ), TN( 12 ), RB_RED }, + { 6, TN( 13 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_15[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 2, TN( 8 ), TN( 0 ), TN( 7 ), RB_BLACK }, + { 7, TN( 2 ), NULL, NULL, RB_RED }, + { 8, NULL, TN( 2 ), TN( 12 ), RB_BLACK }, + { 9, TN( 12 ), NULL, TN( 10 ), RB_BLACK }, + { 10, TN( 9 ), NULL, NULL, RB_RED }, + { 12, TN( 8 ), TN( 9 ), TN( 13 ), RB_RED }, + { 13, TN( 12 ), NULL, TN( 14 ), RB_BLACK }, + { 14, TN( 13 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_15[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 1, TN( 9 ), TN( 0 ), TN( 7 ), RB_BLACK }, + { 3, TN( 2 ), NULL, NULL, RB_RED }, + { 4, NULL, TN( 2 ), TN( 10 ), RB_BLACK }, + { 4, TN( 10 ), NULL, NULL, RB_BLACK }, + { 5, TN( 9 ), TN( 8 ), TN( 12 ), RB_RED }, + { 6, TN( 12 ), NULL, NULL, RB_RED }, + { 6, TN( 10 ), TN( 13 ), TN( 14 ), RB_BLACK }, + { 7, TN( 12 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_16[] = { + { 0, TN( 5 ), NULL, TN( 3 ), RB_BLACK }, + { 3, TN( 0 ), NULL, NULL, RB_RED }, + { 5, TN( 10 ), TN( 0 ), TN( 7 ), RB_RED }, + { 7, TN( 5 ), NULL, NULL, RB_BLACK }, + { 10, NULL, TN( 5 ), TN( 12 ), RB_BLACK }, + { 12, TN( 10 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_16[] = { + { 0, TN( 5 ), NULL, TN( 3 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED }, + { 2, TN( 10 ), TN( 0 ), TN( 7 ), RB_RED }, + { 3, TN( 5 ), NULL, NULL, RB_BLACK }, + { 5, NULL, TN( 5 ), TN( 12 ), RB_BLACK }, + { 6, TN( 10 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_17[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, TN( 3 ), TN( 0 ), NULL, RB_BLACK }, + { 3, TN( 7 ), TN( 1 ), TN( 5 ), RB_RED }, + { 4, TN( 5 ), NULL, NULL, RB_RED }, + { 5, TN( 3 ), TN( 4 ), NULL, RB_BLACK }, + { 7, NULL, TN( 3 ), TN( 9 ), RB_BLACK }, + { 8, TN( 9 ), NULL, NULL, RB_BLACK }, + { 9, TN( 7 ), TN( 8 ), TN( 16 ), RB_RED }, + { 16, TN( 9 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_17[] = { + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 0, TN( 3 ), TN( 1 ), NULL, RB_BLACK }, + { 1, TN( 7 ), TN( 0 ), TN( 5 ), RB_RED }, + { 2, TN( 3 ), NULL, TN( 4 ), RB_BLACK }, + { 2, TN( 5 ), NULL, NULL, RB_RED }, + { 3, NULL, TN( 3 ), TN( 8 ), RB_BLACK }, + { 4, TN( 8 ), NULL, NULL, RB_BLACK }, + { 4, TN( 7 ), TN( 9 ), TN( 16 ), RB_RED }, + { 8, TN( 8 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_18[] = { + { 0, TN( 2 ), NULL, TN( 1 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED }, + { 2, TN( 4 ), TN( 0 ), TN( 3 ), RB_BLACK }, + { 3, TN( 2 ), NULL, NULL, RB_BLACK }, + { 4, NULL, TN( 2 ), TN( 12 ), RB_BLACK }, + { 5, TN( 6 ), NULL, NULL, RB_RED }, + { 6, TN( 8 ), TN( 5 ), TN( 7 ), RB_BLACK }, + { 7, TN( 6 ), NULL, NULL, RB_RED }, + { 8, TN( 12 ), TN( 6 ), TN( 10 ), RB_RED }, + { 9, TN( 10 ), NULL, NULL, RB_RED }, + { 10, TN( 8 ), TN( 9 ), NULL, RB_BLACK }, + { 12, TN( 4 ), TN( 8 ), TN( 17 ), RB_BLACK }, + { 14, TN( 17 ), NULL, NULL, RB_RED }, + { 17, TN( 12 ), TN( 14 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_18[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 1, TN( 4 ), TN( 0 ), TN( 2 ), RB_BLACK }, + { 1, TN( 3 ), NULL, NULL, RB_BLACK }, + { 2, NULL, TN( 3 ), TN( 12 ), RB_BLACK }, + { 2, TN( 6 ), NULL, NULL, RB_RED }, + { 3, TN( 8 ), TN( 5 ), TN( 7 ), RB_BLACK }, + { 3, TN( 6 ), NULL, NULL, RB_RED }, + { 4, TN( 12 ), TN( 6 ), TN( 10 ), RB_RED }, + { 4, TN( 10 ), NULL, NULL, RB_RED }, + { 5, TN( 8 ), TN( 9 ), NULL, RB_BLACK }, + { 6, TN( 4 ), TN( 8 ), TN( 14 ), RB_BLACK }, + { 7, TN( 12 ), NULL, TN( 17 ), RB_BLACK }, + { 8, TN( 14 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_19[] = { + { 1, TN( 2 ), NULL, NULL, RB_RED }, + { 2, TN( 6 ), TN( 1 ), NULL, RB_BLACK }, + { 6, TN( 11 ), TN( 2 ), TN( 8 ), RB_BLACK }, + { 8, TN( 6 ), NULL, TN( 9 ), RB_BLACK }, + { 9, TN( 8 ), NULL, NULL, RB_RED }, + { 11, NULL, TN( 6 ), TN( 14 ), RB_BLACK }, + { 12, TN( 14 ), NULL, NULL, RB_BLACK }, + { 14, TN( 11 ), TN( 12 ), TN( 16 ), RB_BLACK }, + { 16, TN( 14 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_19[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 1, TN( 6 ), TN( 1 ), NULL, RB_BLACK }, + { 3, TN( 11 ), TN( 2 ), TN( 9 ), RB_BLACK }, + { 4, TN( 6 ), NULL, TN( 8 ), RB_BLACK }, + { 4, TN( 9 ), NULL, NULL, RB_RED }, + { 5, NULL, TN( 6 ), TN( 14 ), RB_BLACK }, + { 6, TN( 14 ), NULL, NULL, RB_BLACK }, + { 7, TN( 11 ), TN( 12 ), TN( 16 ), RB_BLACK }, + { 8, TN( 14 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_20[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED }, + { 3, TN( 9 ), TN( 0 ), TN( 7 ), RB_BLACK }, + { 4, TN( 7 ), NULL, NULL, RB_RED }, + { 7, TN( 3 ), TN( 4 ), NULL, RB_BLACK }, + { 9, NULL, TN( 3 ), TN( 12 ), RB_BLACK }, + { 10, TN( 12 ), NULL, NULL, RB_BLACK }, + { 12, TN( 9 ), TN( 10 ), TN( 17 ), RB_BLACK }, + { 14, TN( 17 ), NULL, NULL, RB_BLACK }, + { 17, TN( 12 ), TN( 14 ), TN( 18 ), RB_RED }, + { 18, TN( 17 ), NULL, TN( 19 ), RB_BLACK }, + { 19, TN( 18 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_20[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 1, TN( 9 ), TN( 0 ), TN( 7 ), RB_BLACK }, + { 2, TN( 7 ), NULL, NULL, RB_RED }, + { 3, TN( 3 ), TN( 4 ), NULL, RB_BLACK }, + { 4, NULL, TN( 3 ), TN( 14 ), RB_BLACK }, + { 5, TN( 14 ), NULL, TN( 12 ), RB_BLACK }, + { 6, TN( 10 ), NULL, NULL, RB_RED }, + { 7, TN( 9 ), TN( 10 ), TN( 18 ), RB_BLACK }, + { 8, TN( 18 ), NULL, NULL, RB_RED }, + { 9, TN( 14 ), TN( 17 ), TN( 19 ), RB_BLACK }, + { 9, TN( 18 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_21[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED }, + { 3, TN( 11 ), TN( 0 ), TN( 5 ), RB_BLACK }, + { 4, TN( 5 ), NULL, NULL, RB_BLACK }, + { 5, TN( 3 ), TN( 4 ), TN( 8 ), RB_RED }, + { 8, TN( 5 ), NULL, NULL, RB_BLACK }, + { 11, NULL, TN( 3 ), TN( 15 ), RB_BLACK }, + { 13, TN( 15 ), NULL, NULL, RB_BLACK }, + { 15, TN( 11 ), TN( 13 ), TN( 17 ), RB_BLACK }, + { 16, TN( 17 ), NULL, NULL, RB_RED }, + { 17, TN( 15 ), TN( 16 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_21[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 1, TN( 8 ), TN( 0 ), TN( 4 ), RB_BLACK }, + { 2, TN( 3 ), NULL, TN( 5 ), RB_BLACK }, + { 2, TN( 4 ), NULL, NULL, RB_RED }, + { 4, NULL, TN( 3 ), TN( 13 ), RB_BLACK }, + { 5, TN( 13 ), NULL, NULL, RB_BLACK }, + { 6, TN( 8 ), TN( 11 ), TN( 17 ), RB_BLACK }, + { 7, TN( 17 ), NULL, NULL, RB_BLACK }, + { 8, TN( 13 ), TN( 15 ), TN( 16 ), RB_RED }, + { 8, TN( 17 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_22[] = { + { 1, TN( 3 ), NULL, TN( 2 ), RB_BLACK }, + { 2, TN( 1 ), NULL, NULL, RB_RED }, + { 3, TN( 8 ), TN( 1 ), TN( 7 ), RB_BLACK }, + { 4, TN( 7 ), NULL, NULL, RB_RED }, + { 7, TN( 3 ), TN( 4 ), NULL, RB_BLACK }, + { 8, NULL, TN( 3 ), TN( 14 ), RB_BLACK }, + { 10, TN( 11 ), NULL, NULL, RB_RED }, + { 11, TN( 14 ), TN( 10 ), NULL, RB_BLACK }, + { 14, TN( 8 ), TN( 11 ), TN( 18 ), RB_BLACK }, + { 15, TN( 18 ), NULL, NULL, RB_BLACK }, + { 18, TN( 14 ), TN( 15 ), TN( 21 ), RB_RED }, + { 21, TN( 18 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_22[] = { + { 0, TN( 3 ), NULL, NULL, RB_BLACK }, + { 1, TN( 8 ), TN( 1 ), TN( 4 ), RB_BLACK }, + { 1, TN( 4 ), NULL, NULL, RB_BLACK }, + { 2, TN( 3 ), TN( 2 ), TN( 7 ), RB_RED }, + { 3, TN( 4 ), NULL, NULL, RB_BLACK }, + { 4, NULL, TN( 3 ), TN( 14 ), RB_BLACK }, + { 5, TN( 14 ), NULL, TN( 10 ), RB_BLACK }, + { 5, TN( 11 ), NULL, NULL, RB_RED }, + { 7, TN( 8 ), TN( 11 ), TN( 18 ), RB_BLACK }, + { 7, TN( 18 ), NULL, NULL, RB_BLACK }, + { 9, TN( 14 ), TN( 15 ), TN( 21 ), RB_RED }, + { 10, TN( 18 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_23[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 2, TN( 8 ), TN( 0 ), TN( 7 ), RB_BLACK }, + { 7, TN( 2 ), NULL, NULL, RB_RED }, + { 8, TN( 12 ), TN( 2 ), TN( 11 ), RB_BLACK }, + { 11, TN( 8 ), NULL, NULL, RB_BLACK }, + { 12, NULL, TN( 8 ), TN( 17 ), RB_BLACK }, + { 13, TN( 15 ), NULL, TN( 14 ), RB_BLACK }, + { 14, TN( 13 ), NULL, NULL, RB_RED }, + { 15, TN( 17 ), TN( 13 ), TN( 16 ), RB_RED }, + { 16, TN( 15 ), NULL, NULL, RB_BLACK }, + { 17, TN( 12 ), TN( 15 ), TN( 20 ), RB_BLACK }, + { 20, TN( 17 ), NULL, TN( 21 ), RB_BLACK }, + { 21, TN( 20 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_23[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 1, TN( 8 ), TN( 0 ), TN( 7 ), RB_BLACK }, + { 3, TN( 2 ), NULL, NULL, RB_RED }, + { 4, TN( 12 ), TN( 2 ), TN( 11 ), RB_BLACK }, + { 5, TN( 8 ), NULL, NULL, RB_BLACK }, + { 6, NULL, TN( 8 ), TN( 17 ), RB_BLACK }, + { 6, TN( 15 ), NULL, NULL, RB_BLACK }, + { 7, TN( 17 ), TN( 13 ), TN( 16 ), RB_RED }, + { 7, TN( 16 ), NULL, NULL, RB_RED }, + { 8, TN( 15 ), TN( 14 ), NULL, RB_BLACK }, + { 8, TN( 12 ), TN( 15 ), TN( 20 ), RB_BLACK }, + { 10, TN( 17 ), NULL, TN( 21 ), RB_BLACK }, + { 10, TN( 20 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_24[] = { + { 4, TN( 6 ), NULL, TN( 5 ), RB_BLACK }, + { 5, TN( 4 ), NULL, NULL, RB_RED }, + { 6, TN( 14 ), TN( 4 ), TN( 10 ), RB_BLACK }, + { 8, TN( 10 ), NULL, NULL, RB_RED }, + { 10, TN( 6 ), TN( 8 ), NULL, RB_BLACK }, + { 14, NULL, TN( 6 ), TN( 20 ), RB_BLACK }, + { 15, TN( 16 ), NULL, NULL, RB_RED }, + { 16, TN( 20 ), TN( 15 ), NULL, RB_BLACK }, + { 20, TN( 14 ), TN( 16 ), TN( 22 ), RB_BLACK }, + { 22, TN( 20 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_24[] = { + { 2, TN( 6 ), NULL, TN( 5 ), RB_BLACK }, + { 2, TN( 4 ), NULL, NULL, RB_RED }, + { 3, TN( 14 ), TN( 4 ), TN( 10 ), RB_BLACK }, + { 4, TN( 10 ), NULL, NULL, RB_RED }, + { 5, TN( 6 ), TN( 8 ), NULL, RB_BLACK }, + { 7, NULL, TN( 6 ), TN( 20 ), RB_BLACK }, + { 7, TN( 16 ), NULL, NULL, RB_RED }, + { 8, TN( 20 ), TN( 15 ), NULL, RB_BLACK }, + { 10, TN( 14 ), TN( 16 ), TN( 22 ), RB_BLACK }, + { 11, TN( 20 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_25[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, TN( 3 ), TN( 0 ), NULL, RB_BLACK }, + { 3, TN( 13 ), TN( 1 ), TN( 5 ), RB_BLACK }, + { 4, TN( 5 ), NULL, NULL, RB_BLACK }, + { 5, TN( 3 ), TN( 4 ), TN( 6 ), RB_RED }, + { 6, TN( 5 ), NULL, TN( 9 ), RB_BLACK }, + { 9, TN( 6 ), NULL, NULL, RB_RED }, + { 13, NULL, TN( 3 ), TN( 19 ), RB_BLACK }, + { 14, TN( 15 ), NULL, NULL, RB_RED }, + { 15, TN( 16 ), TN( 14 ), NULL, RB_BLACK }, + { 16, TN( 19 ), TN( 15 ), TN( 17 ), RB_RED }, + { 17, TN( 16 ), NULL, NULL, RB_BLACK }, + { 19, TN( 13 ), TN( 16 ), TN( 23 ), RB_BLACK }, + { 23, TN( 19 ), NULL, TN( 24 ), RB_BLACK }, + { 24, TN( 23 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_25[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 1, TN( 13 ), TN( 0 ), TN( 4 ), RB_BLACK }, + { 2, TN( 4 ), NULL, NULL, RB_BLACK }, + { 2, TN( 3 ), TN( 5 ), TN( 6 ), RB_RED }, + { 3, TN( 4 ), NULL, TN( 9 ), RB_BLACK }, + { 4, TN( 6 ), NULL, NULL, RB_RED }, + { 6, NULL, TN( 3 ), TN( 19 ), RB_BLACK }, + { 7, TN( 17 ), NULL, TN( 14 ), RB_BLACK }, + { 7, TN( 15 ), NULL, NULL, RB_RED }, + { 8, TN( 19 ), TN( 15 ), TN( 16 ), RB_RED }, + { 8, TN( 17 ), NULL, NULL, RB_BLACK }, + { 9, TN( 13 ), TN( 17 ), TN( 23 ), RB_BLACK }, + { 11, TN( 19 ), NULL, TN( 24 ), RB_BLACK }, + { 12, TN( 23 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_26[] = { + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, TN( 3 ), TN( 0 ), NULL, RB_BLACK }, + { 3, TN( 11 ), TN( 1 ), TN( 9 ), RB_BLACK }, + { 6, TN( 9 ), NULL, NULL, RB_RED }, + { 9, TN( 3 ), TN( 6 ), TN( 10 ), RB_BLACK }, + { 10, TN( 9 ), NULL, NULL, RB_RED }, + { 11, NULL, TN( 3 ), TN( 14 ), RB_BLACK }, + { 12, TN( 14 ), NULL, TN( 13 ), RB_BLACK }, + { 13, TN( 12 ), NULL, NULL, RB_RED }, + { 14, TN( 11 ), TN( 12 ), TN( 20 ), RB_BLACK }, + { 18, TN( 20 ), NULL, NULL, RB_BLACK }, + { 20, TN( 14 ), TN( 18 ), TN( 23 ), RB_RED }, + { 21, TN( 23 ), NULL, NULL, RB_RED }, + { 23, TN( 20 ), TN( 21 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_26[] = { + { 0, TN( 3 ), NULL, TN( 0 ), RB_BLACK }, + { 0, TN( 1 ), NULL, NULL, RB_RED }, + { 1, TN( 9 ), TN( 1 ), TN( 6 ), RB_BLACK }, + { 3, TN( 3 ), NULL, NULL, RB_BLACK }, + { 4, NULL, TN( 3 ), TN( 14 ), RB_BLACK }, + { 5, TN( 12 ), NULL, TN( 10 ), RB_BLACK }, + { 5, TN( 11 ), NULL, NULL, RB_RED }, + { 6, TN( 14 ), TN( 11 ), TN( 13 ), RB_RED }, + { 6, TN( 12 ), NULL, NULL, RB_BLACK }, + { 7, TN( 9 ), TN( 12 ), TN( 20 ), RB_BLACK }, + { 9, TN( 20 ), NULL, NULL, RB_BLACK }, + { 10, TN( 14 ), TN( 18 ), TN( 23 ), RB_RED }, + { 10, TN( 23 ), NULL, NULL, RB_RED }, + { 11, TN( 20 ), TN( 21 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_27[] = { + { 3, TN( 8 ), NULL, NULL, RB_BLACK }, + { 8, TN( 19 ), TN( 3 ), TN( 17 ), RB_BLACK }, + { 12, TN( 17 ), NULL, NULL, RB_RED }, + { 17, TN( 8 ), TN( 12 ), NULL, RB_BLACK }, + { 19, NULL, TN( 8 ), TN( 24 ), RB_BLACK }, + { 20, TN( 21 ), NULL, NULL, RB_RED }, + { 21, TN( 24 ), TN( 20 ), TN( 23 ), RB_BLACK }, + { 23, TN( 21 ), NULL, NULL, RB_RED }, + { 24, TN( 19 ), TN( 21 ), TN( 25 ), RB_BLACK }, + { 25, TN( 24 ), NULL, TN( 26 ), RB_BLACK }, + { 26, TN( 25 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_27[] = { + { 1, TN( 8 ), NULL, NULL, RB_BLACK }, + { 4, TN( 19 ), TN( 3 ), TN( 17 ), RB_BLACK }, + { 6, TN( 17 ), NULL, NULL, RB_RED }, + { 8, TN( 8 ), TN( 12 ), NULL, RB_BLACK }, + { 9, NULL, TN( 8 ), TN( 25 ), RB_BLACK }, + { 10, TN( 21 ), NULL, NULL, RB_RED }, + { 10, TN( 25 ), TN( 20 ), TN( 23 ), RB_BLACK }, + { 11, TN( 21 ), NULL, NULL, RB_RED }, + { 12, TN( 19 ), TN( 21 ), TN( 24 ), RB_BLACK }, + { 12, TN( 25 ), NULL, TN( 26 ), RB_BLACK }, + { 13, TN( 24 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_28[] = { + { 0, TN( 5 ), NULL, NULL, RB_BLACK }, + { 5, TN( 13 ), TN( 0 ), TN( 7 ), RB_RED }, + { 7, TN( 5 ), NULL, NULL, RB_BLACK }, + { 13, NULL, TN( 5 ), TN( 17 ), RB_BLACK }, + { 15, TN( 17 ), NULL, NULL, RB_BLACK }, + { 17, TN( 13 ), TN( 15 ), TN( 26 ), RB_RED }, + { 21, TN( 26 ), NULL, NULL, RB_RED }, + { 26, TN( 17 ), TN( 21 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_28[] = { + { 0, TN( 5 ), NULL, NULL, RB_BLACK }, + { 2, TN( 13 ), TN( 0 ), TN( 7 ), RB_RED }, + { 3, TN( 5 ), NULL, NULL, RB_BLACK }, + { 6, NULL, TN( 5 ), TN( 17 ), RB_BLACK }, + { 7, TN( 17 ), NULL, NULL, RB_BLACK }, + { 8, TN( 13 ), TN( 15 ), TN( 26 ), RB_RED }, + { 10, TN( 26 ), NULL, NULL, RB_RED }, + { 13, TN( 17 ), TN( 21 ), NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_unique_29[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 1, TN( 0 ), NULL, NULL, RB_RED }, + { 3, TN( 12 ), TN( 0 ), TN( 6 ), RB_BLACK }, + { 4, TN( 6 ), NULL, NULL, RB_BLACK }, + { 6, TN( 3 ), TN( 4 ), TN( 8 ), RB_RED }, + { 7, TN( 8 ), NULL, NULL, RB_RED }, + { 8, TN( 6 ), TN( 7 ), TN( 11 ), RB_BLACK }, + { 11, TN( 8 ), NULL, NULL, RB_RED }, + { 12, NULL, TN( 3 ), TN( 17 ), RB_BLACK }, + { 13, TN( 17 ), NULL, TN( 14 ), RB_BLACK }, + { 14, TN( 13 ), NULL, NULL, RB_RED }, + { 17, TN( 12 ), TN( 13 ), TN( 25 ), RB_BLACK }, + { 22, TN( 25 ), NULL, NULL, RB_RED }, + { 25, TN( 17 ), TN( 22 ), TN( 27 ), RB_BLACK }, + { 27, TN( 25 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_29[] = { + { 0, TN( 3 ), NULL, TN( 1 ), RB_BLACK }, + { 0, TN( 0 ), NULL, NULL, RB_RED }, + { 1, TN( 11 ), TN( 0 ), TN( 6 ), RB_BLACK }, + { 2, TN( 6 ), NULL, NULL, RB_BLACK }, + { 3, TN( 3 ), TN( 4 ), TN( 7 ), RB_RED }, + { 3, TN( 6 ), NULL, TN( 8 ), RB_BLACK }, + { 4, TN( 7 ), NULL, NULL, RB_RED }, + { 5, NULL, TN( 3 ), TN( 22 ), RB_BLACK }, + { 6, TN( 12 ), NULL, NULL, RB_BLACK }, + { 6, TN( 22 ), TN( 13 ), TN( 17 ), RB_RED }, + { 7, TN( 17 ), NULL, NULL, RB_RED }, + { 8, TN( 12 ), TN( 14 ), NULL, RB_BLACK }, + { 11, TN( 11 ), TN( 12 ), TN( 25 ), RB_BLACK }, + { 12, TN( 22 ), NULL, TN( 27 ), RB_BLACK }, + { 13, TN( 25 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_30[] = { + { 0, TN( 4 ), NULL, NULL, RB_RED }, + { 4, TN( 6 ), TN( 0 ), NULL, RB_BLACK }, + { 6, TN( 13 ), TN( 4 ), TN( 9 ), RB_RED }, + { 8, TN( 9 ), NULL, NULL, RB_RED }, + { 9, TN( 6 ), TN( 8 ), TN( 12 ), RB_BLACK }, + { 12, TN( 9 ), NULL, NULL, RB_RED }, + { 13, NULL, TN( 6 ), TN( 18 ), RB_BLACK }, + { 14, TN( 16 ), NULL, NULL, RB_RED }, + { 16, TN( 18 ), TN( 14 ), TN( 17 ), RB_BLACK }, + { 17, TN( 16 ), NULL, NULL, RB_RED }, + { 18, TN( 13 ), TN( 16 ), TN( 27 ), RB_RED }, + { 20, TN( 27 ), NULL, NULL, RB_RED }, + { 27, TN( 18 ), TN( 20 ), TN( 28 ), RB_BLACK }, + { 28, TN( 27 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_multiple_30[] = { + { 0, TN( 4 ), NULL, NULL, RB_BLACK }, + { 2, TN( 13 ), TN( 0 ), TN( 9 ), RB_RED }, + { 3, TN( 9 ), NULL, NULL, RB_RED }, + { 4, TN( 4 ), TN( 6 ), TN( 8 ), RB_BLACK }, + { 4, TN( 9 ), NULL, NULL, RB_RED }, + { 6, TN( 14 ), TN( 4 ), TN( 12 ), RB_BLACK }, + { 6, TN( 13 ), NULL, NULL, RB_BLACK }, + { 7, NULL, TN( 13 ), TN( 18 ), RB_BLACK }, + { 8, TN( 18 ), NULL, TN( 16 ), RB_BLACK }, + { 8, TN( 17 ), NULL, NULL, RB_RED }, + { 9, TN( 14 ), TN( 17 ), TN( 27 ), RB_BLACK }, + { 10, TN( 27 ), NULL, NULL, RB_RED }, + { 13, TN( 18 ), TN( 20 ), TN( 28 ), RB_BLACK }, + { 14, TN( 27 ), NULL, NULL, RB_RED } +}; + +static const TestNodeDescription random_ops_tree_unique_31[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 2, TN( 5 ), TN( 0 ), NULL, RB_BLACK }, + { 5, TN( 11 ), TN( 2 ), TN( 9 ), RB_BLACK }, + { 7, TN( 9 ), NULL, NULL, RB_RED }, + { 9, TN( 5 ), TN( 7 ), NULL, RB_BLACK }, + { 11, NULL, TN( 5 ), TN( 21 ), RB_BLACK }, + { 14, TN( 16 ), NULL, NULL, RB_RED }, + { 16, TN( 21 ), TN( 14 ), TN( 18 ), RB_BLACK }, + { 18, TN( 16 ), NULL, NULL, RB_RED }, + { 21, TN( 11 ), TN( 16 ), TN( 30 ), RB_BLACK }, + { 30, TN( 21 ), NULL, NULL, RB_BLACK } +}; + +static const TestNodeDescription random_ops_tree_multiple_31[] = { + { 0, TN( 2 ), NULL, NULL, RB_RED }, + { 1, TN( 5 ), TN( 0 ), NULL, RB_BLACK }, + { 2, TN( 11 ), TN( 2 ), TN( 9 ), RB_BLACK }, + { 3, TN( 9 ), NULL, NULL, RB_RED }, + { 4, TN( 5 ), TN( 7 ), NULL, RB_BLACK }, + { 5, NULL, TN( 5 ), TN( 21 ), RB_BLACK }, + { 7, TN( 16 ), NULL, NULL, RB_RED }, + { 8, TN( 21 ), TN( 14 ), TN( 18 ), RB_BLACK }, + { 9, TN( 16 ), NULL, NULL, RB_RED }, + { 10, TN( 11 ), TN( 16 ), TN( 30 ), RB_BLACK }, + { 15, TN( 21 ), NULL, NULL, RB_BLACK } +}; + +#define RANDOM_OPS_TREE( i ) \ + { &random_ops_tree_multiple_##i[ 0 ], &random_ops_tree_unique_##i[ 0 ] } + +static const TestNodeDescription *const random_ops_trees[][2] = { + RANDOM_OPS_TREE( 1 ), + RANDOM_OPS_TREE( 2 ), + RANDOM_OPS_TREE( 3 ), + RANDOM_OPS_TREE( 4 ), + RANDOM_OPS_TREE( 5 ), + RANDOM_OPS_TREE( 6 ), + RANDOM_OPS_TREE( 7 ), + RANDOM_OPS_TREE( 8 ), + RANDOM_OPS_TREE( 9 ), + RANDOM_OPS_TREE( 10 ), + RANDOM_OPS_TREE( 11 ), + RANDOM_OPS_TREE( 12 ), + RANDOM_OPS_TREE( 13 ), + RANDOM_OPS_TREE( 14 ), + RANDOM_OPS_TREE( 15 ), + RANDOM_OPS_TREE( 16 ), + RANDOM_OPS_TREE( 17 ), + RANDOM_OPS_TREE( 18 ), + RANDOM_OPS_TREE( 19 ), + RANDOM_OPS_TREE( 20 ), + RANDOM_OPS_TREE( 21 ), + RANDOM_OPS_TREE( 22 ), + RANDOM_OPS_TREE( 23 ), + RANDOM_OPS_TREE( 24 ), + RANDOM_OPS_TREE( 25 ), + RANDOM_OPS_TREE( 26 ), + RANDOM_OPS_TREE( 27 ), + RANDOM_OPS_TREE( 28 ), + RANDOM_OPS_TREE( 29 ), + RANDOM_OPS_TREE( 30 ), + RANDOM_OPS_TREE( 31 ) +}; + +#define RANDOM_OPS_TREE_COUNT( i ) \ + { \ + RTEMS_ARRAY_SIZE( random_ops_tree_multiple_##i ), \ + RTEMS_ARRAY_SIZE( random_ops_tree_unique_##i ) \ + } + +static const size_t random_ops_tree_counts[][2] = { + RANDOM_OPS_TREE_COUNT( 1 ), + RANDOM_OPS_TREE_COUNT( 2 ), + RANDOM_OPS_TREE_COUNT( 3 ), + RANDOM_OPS_TREE_COUNT( 4 ), + RANDOM_OPS_TREE_COUNT( 5 ), + RANDOM_OPS_TREE_COUNT( 6 ), + RANDOM_OPS_TREE_COUNT( 7 ), + RANDOM_OPS_TREE_COUNT( 8 ), + RANDOM_OPS_TREE_COUNT( 9 ), + RANDOM_OPS_TREE_COUNT( 10 ), + RANDOM_OPS_TREE_COUNT( 11 ), + RANDOM_OPS_TREE_COUNT( 12 ), + RANDOM_OPS_TREE_COUNT( 13 ), + RANDOM_OPS_TREE_COUNT( 14 ), + RANDOM_OPS_TREE_COUNT( 15 ), + RANDOM_OPS_TREE_COUNT( 16 ), + RANDOM_OPS_TREE_COUNT( 17 ), + RANDOM_OPS_TREE_COUNT( 18 ), + RANDOM_OPS_TREE_COUNT( 19 ), + RANDOM_OPS_TREE_COUNT( 20 ), + RANDOM_OPS_TREE_COUNT( 21 ), + RANDOM_OPS_TREE_COUNT( 22 ), + RANDOM_OPS_TREE_COUNT( 23 ), + RANDOM_OPS_TREE_COUNT( 24 ), + RANDOM_OPS_TREE_COUNT( 25 ), + RANDOM_OPS_TREE_COUNT( 26 ), + RANDOM_OPS_TREE_COUNT( 27 ), + RANDOM_OPS_TREE_COUNT( 28 ), + RANDOM_OPS_TREE_COUNT( 29 ), + RANDOM_OPS_TREE_COUNT( 30 ), + RANDOM_OPS_TREE_COUNT( 31 ) +}; + +static uint32_t SimpleRandom( uint32_t v ) +{ + v *= 1664525; + v += 1013904223; + + return v; +} + +static void RandomOps( size_t n, bool unique ) +{ + VisitorContext ctx = { + .current = 0, + .count = random_ops_tree_counts[ n - 1 ][ unique ], + .tree = random_ops_trees[ n - 1 ][ unique ] + }; + RBTree_Control tree; + TestNode *nodes; + size_t m; + size_t s; + uint32_t v; + size_t i; + + nodes = &node_array[ 0 ]; + m = n * n * n; + s = unique ? 1 : 2; + v = 0xdeadbeef; + _RBTree_Initialize_empty( &tree ); + + memset( nodes, 0, n * sizeof( *nodes ) ); + + for ( i = 0; i < n; ++i ) { + nodes[ i ].key = (int) ( i / s ); + } + + for ( i = 0; i < m; ++i ) { + size_t j = ( v >> 13 ) % n; + TestNode *tn = &nodes[ j ]; + + if ( tn->id == 0 ) { + tn->id = 1; + _RBTree_Initialize_node( &tn->Node ); + _RBTree_Insert_inline( &tree, &tn->Node, &tn->key, Less ); + } else { + tn->id = 0; + _RBTree_Extract( &tree, &tn->Node ); + } + + T_ne_int( VerifyTree( _RBTree_Root( &tree ) ), -1 ); + + v = SimpleRandom( v ); + } + + _RBTree_Iterate( &tree, VisitNodes, &ctx ); + T_true( ctx.current == ctx.count ); +} + +/** + * @brief Call _RBTree_Initialize_one() and check the tree properties. + */ +static void ScoreRbtreeUnitRbtree_Action_0( void ) +{ + RBTree_Control tree; + RBTree_Node node; + + _RBTree_Initialize_node( &node ); + _RBTree_Initialize_one( &tree, &node ); + + /* + * Check that the tree is not emtpy. + */ + T_false( _RBTree_Is_empty( &tree ) ); + + /* + * Check that the tree root is is the only node. + */ + T_true( _RBTree_Is_root( &node ) ); + + /* + * Check that the node is not off the tree. + */ + T_false( _RBTree_Is_node_off_tree( &node ) ); + + /* + * Check that the node has no left child. + */ + T_null( _RBTree_Left( &node ) ); + + /* + * Check that the node has no right child. + */ + T_null( _RBTree_Right( &node ) ); + + /* + * Check that the node has no parent. + */ + T_null( _RBTree_Parent( &node ) ); + + /* + * Check that the node has no successor. + */ + T_null( _RBTree_Successor( &node ) ); + + /* + * Check that the node has no predecessor. + */ + T_null( _RBTree_Predecessor( &node ) ); + + /* + * Check that the minimum node is the node. + */ + T_eq_ptr( _RBTree_Minimum( &tree ), &node ); + + /* + * Check that the maximum node is the node. + */ + T_eq_ptr( _RBTree_Maximum( &tree ), &node ); + + /* + * Check that the tree is emtpy after extraction of the node. + */ + _RBTree_Extract( &tree, &node ); + T_true( _RBTree_Is_empty( &tree ) ); +} + +/** + * @brief Call _RBTree_Insert_inline() and check the return status for a sample + * set of nodes. + */ +static void ScoreRbtreeUnitRbtree_Action_1( void ) +{ + RBTree_Control tree; + TestNode a; + TestNode b; + TestNode c; + bool is_new_minimum; + + _RBTree_Initialize_empty( &tree ); + + /* + * Insert the first node. Check that it is the new minimum node. + */ + _RBTree_Initialize_node( &b.Node ); + b.key = 2; + is_new_minimum = _RBTree_Insert_inline( &tree, &b.Node, &b.key, Less ); + T_true( is_new_minimum ); + + /* + * Insert the second node. Check that it is not the new minimum node. + */ + _RBTree_Initialize_node( &c.Node ); + c.key = 3; + is_new_minimum = _RBTree_Insert_inline( &tree, &c.Node, &c.key, Less ); + T_false( is_new_minimum ); + + /* + * Insert the third node. Check that it is the new minimum node. + */ + _RBTree_Initialize_node( &a.Node ); + a.key = 1; + is_new_minimum = _RBTree_Insert_inline( &tree, &a.Node, &a.key, Less ); + T_true( is_new_minimum ); +} + +/** + * @brief Call _RBTree_Insert_inline() and _RBTree_Extract() for a sample set + * of trees. + */ +static void ScoreRbtreeUnitRbtree_Action_2( void ) +{ + size_t n; + + for ( n = 0; n < RTEMS_ARRAY_SIZE( random_ops_trees ); ++n ) { + RandomOps( n + 1, true ); + RandomOps( n + 1, false ); + } +} + +/** + * @fn void T_case_body_ScoreRbtreeUnitRbtree( void ) + */ +T_TEST_CASE( ScoreRbtreeUnitRbtree ) +{ + ScoreRbtreeUnitRbtree_Action_0(); + ScoreRbtreeUnitRbtree_Action_1(); + ScoreRbtreeUnitRbtree_Action_2(); +} + +/** @} */ diff --git a/testsuites/unit/ts-unit-no-clock-0.c b/testsuites/unit/ts-unit-no-clock-0.c new file mode 100644 index 0000000000..88e67f91bd --- /dev/null +++ b/testsuites/unit/ts-unit-no-clock-0.c @@ -0,0 +1,80 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ + +/** + * @file + * + * @ingroup TestsuitesUnitNoClock0 + */ + +/* + * Copyright (C) 2021 embedded brains GmbH & Co. KG + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This file is part of the RTEMS quality process and was automatically + * generated. If you find something that needs to be fixed or + * worded better please post a report or patch to an RTEMS mailing list + * or raise a bug report: + * + * https://www.rtems.org/bugs.html + * + * For information on updating and regenerating please refer to the How-To + * section in the Software Requirements Engineering chapter of the + * RTEMS Software Engineering manual. The manual is provided as a part of + * a release. For development sources please refer to the online + * documentation at: + * + * https://docs.rtems.org + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <rtems/test.h> + +/** + * @defgroup TestsuitesUnitNoClock0 spec:/testsuites/unit-no-clock-0 + * + * @ingroup RTEMSTestSuitesUnit + * + * @brief This general purpose unit test suite provides enough resources to run + * basic tests without a Clock Driver for all specified managers and + * functions. + * + * In SMP configurations, up to three scheduler instances using the SMP EDF + * scheduler are provided using up to four processors. + * + * @{ + */ + +const char rtems_test_name[] = "TestsuitesUnitNoClock0"; + +#define CONFIGURE_MAXIMUM_PROCESSORS 4 + +#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER + +#include "../validation/ts-default.h" + +/** @} */ |