From bf4630076762d9c20c16c80c1c791f352b046dd1 Mon Sep 17 00:00:00 2001 From: Brad Bishop Date: Mon, 30 Jun 2014 22:10:16 -0500 Subject: Port FFS tools over from Building Block repository. --- clib/cunit/splay.c | 384 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 384 insertions(+) create mode 100644 clib/cunit/splay.c (limited to 'clib/cunit/splay.c') diff --git a/clib/cunit/splay.c b/clib/cunit/splay.c new file mode 100644 index 0000000..302310e --- /dev/null +++ b/clib/cunit/splay.c @@ -0,0 +1,384 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include +#include + +#include + +#include +#include +#include + +#include + +#define COUNT 30000 +#define SEED 22 + +slab_t slab; + +typedef struct { + tree_node_t node; + int i; + float f; +} data_t; + +static int init_splay(void) { + slab_init(&slab, "my_slab", sizeof(data_t), 4096); + return 0; +} + +static int clean_splay(void) { + slab_delete(&slab); + return 0; +} + +static void __insert(tree_t * t, int i) { + data_t * d = (data_t *)slab_alloc(&slab); + + d->i = i; + d->f = (float)i; + + tree_node_init(&d->node, (const void *)(d->i)); + + if (splay_insert(t, &d->node) < 0) { + tree_dump(t, stdout); + + fprintf(stdout, "key: %d root->key: %d\n", + i, (int)tree_root(t)->key); + + err_t * err = err_get(); + fprintf(stderr, "%s(%d): %.*s\n", + err_file(err), err_line(err), err_size(err), + (const char *)err_data(err)); + } +} + +static data_t * __remove(tree_t * t, int i) { + tree_node_t * n = tree_find(t, (const void *)i); + if (n == NULL) tree_dump(t, stdout); + CU_ASSERT_PTR_NOT_NULL_FATAL(n); + + splay_remove(t, n); + CU_ASSERT_PTR_NULL(tree_node_parent(n)); + CU_ASSERT_PTR_NULL(tree_node_left(n)); + CU_ASSERT_PTR_NULL(tree_node_right(n)); + CU_ASSERT_PTR_NOT_NULL(tree_node_key(n)); + + data_t * d = container_of(n, data_t, node); + CU_ASSERT_PTR_NOT_NULL_FATAL(n); + + if (0 <= i) + CU_ASSERT(d->i == i); + + return d; +} + +static int compare(const void * v1, const void * v2) { + const int i1 = (const int)v1, i2 = (const int)v2; + return i1 - i2; +} + +static void splay_1(void) { + tree_t t; + tree_init(&t, compare); + + CU_ASSERT(tree_min(&t) == NULL); + CU_ASSERT(tree_max(&t) == NULL); + CU_ASSERT(t.compare != NULL); + + CU_ASSERT(tree_root(&t) == NULL); + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); +} + +static void splay_2(void) { + tree_t t; + tree_init(&t, compare); + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, i); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_root(&t) != NULL); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(i == (int)tree_min(&t)->key); + CU_ASSERT(COUNT == (int)tree_max(&t)->key); + __remove(&t, (int)tree_min(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, i); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_root(&t) != NULL); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(1 == (int)tree_min(&t)->key); + CU_ASSERT(COUNT - i + 1 == (int)tree_max(&t)->key); + __remove(&t, (int)tree_max(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); +} + +static void splay_3(void) { + tree_t t; + tree_init(&t, compare); + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, COUNT - i + 1); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_root(&t) != NULL); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(1 == (int)tree_min(&t)->key); + CU_ASSERT(COUNT - i + 1 == (int)tree_max(&t)->key); + __remove(&t, (int)tree_max(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, COUNT - i + 1); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_root(&t) != NULL); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(i == (int)tree_min(&t)->key); + CU_ASSERT(COUNT == (int)tree_max(&t)->key); + __remove(&t, (int)tree_min(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); +} + +static void splay_4(void) { + tree_t t; + tree_init(&t, compare); + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + __remove(&t, (int)tree_min(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + __remove(&t, (int)tree_max(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + __remove(&t, (int)tree_root(&t)->key); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) { + __remove(&t, random()); + CU_ASSERT(tree_size(&t) + i == COUNT); + } + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); +} + +static void splay_5(void) { + tree_t t; + tree_init(&t, compare); + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + data_t * d; + + tree_iter_t it; + + int key = 0; + tree_iter_init(&it, &t, TI_FLAG_FWD); + tree_for_each(&it, d, node) { + CU_ASSERT(key < d->i); + key = d->i; + } + + key = INT32_MAX; + tree_iter_init(&it, &t, TI_FLAG_BWD); + tree_for_each(&it, d, node) { + CU_ASSERT(d->i < key); + key = d->i; + } +} + +static void splay_6(void) { + tree_t t; + tree_init(&t, compare); + + data_t * d; + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + tree_iter_t it; + tree_iter_init(&it, &t, TI_FLAG_FWD); + + int key = 0; + tree_for_each(&it, d, node) { + CU_ASSERT(key < d->i); + key = d->i; + } + + __remove(&t, (int)tree_min(&t)->key); + + if (0 < tree_size(&t)) { + CU_ASSERT(tree_min(&t) != NULL); + } else if (tree_size(&t) <= 0) { + CU_ASSERT(tree_min(&t) == NULL); + } + + CU_ASSERT(tree_size(&t) + i == COUNT); + } +} + +static void splay_7(void) { + tree_t t; + tree_init(&t, compare); + + data_t * d; + + CU_ASSERT(tree_empty(&t) == true); + CU_ASSERT(tree_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, random()); + + CU_ASSERT(tree_empty(&t) == false); + CU_ASSERT(tree_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + tree_iter_t it; + + int key = INT32_MAX; + tree_iter_init(&it, &t, TI_FLAG_BWD); + tree_for_each(&it, d, node) { + CU_ASSERT(d->i < key); + key = d->i; + } + + __remove(&t, (int)tree_max(&t)->key); + + if (0 < tree_size(&t)) { + CU_ASSERT(tree_max(&t) != NULL); + } else if ( tree_size(&t) <= 0) { + CU_ASSERT(tree_max(&t) == NULL); + } + + CU_ASSERT(tree_size(&t) + i == COUNT); + } +} + +void splay_test(void) { + CU_pSuite suite = CU_add_suite("splay", init_splay, clean_splay); + if (NULL == suite) + return; + + if (CU_add_test(suite, "test of --> splay_1", splay_1) == NULL) return; + if (CU_add_test(suite, "test of --> splay_2", splay_2) == NULL) return; + if (CU_add_test(suite, "test of --> splay_3", splay_3) == NULL) return; + if (CU_add_test(suite, "test of --> splay_4", splay_4) == NULL) return; + if (CU_add_test(suite, "test of --> splay_5", splay_5) == NULL) return; + if (CU_add_test(suite, "test of --> splay_6", splay_6) == NULL) return; + if (CU_add_test(suite, "test of --> splay_7", splay_7) == NULL) return; +} -- cgit v1.2.1