diff options
Diffstat (limited to 'clib/cunit/map.c')
-rw-r--r-- | clib/cunit/map.c | 301 |
1 files changed, 301 insertions, 0 deletions
diff --git a/clib/cunit/map.c b/clib/cunit/map.c new file mode 100644 index 0000000..3761b1a --- /dev/null +++ b/clib/cunit/map.c @@ -0,0 +1,301 @@ +/* + * 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 <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <clib/libclib.h> + +#include <clib/slab.h> +#include <clib/map.h> +#include <clib/map_iter.h> + +#include <CUnit/Basic.h> + +#define COUNT 20000 +#define SEED 22 + +slab_t slab; + +typedef struct { + map_node_t node; + int i; + float f; +} data_t; + +static int init_map(void) { + slab_init(&slab, "my_slab", sizeof(data_t), 4096); + return 0; +} + +static int clean_map(void) { + slab_delete(&slab); + return 0; +} + +static void __insert(map_t * t, int i) { + data_t * d = (data_t *)slab_alloc(&slab); + + i %= INT32_MAX; + + d->i = i; + d->f = (float)i; + map_node_init(&d->node, (const void *)(intptr_t)(d->i)); + + if (map_insert(t, &d->node) < 0) { + 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(map_t * t, int i) { + + i %= INT32_MAX; + + map_node_t * n = map_find(t, (const void *)i); + if (n == NULL) map_dump(t, stdout); + CU_ASSERT_PTR_NOT_NULL_FATAL(n); + + map_remove(t, n); + + data_t * d = container_of(n, data_t, node); + CU_ASSERT_PTR_NOT_NULL_FATAL(n); + + if (0 <= i) + CU_ASSERT((int)d->node.key == 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 map_1(void) { + map_t t; + map_init(&t, compare); + + CU_ASSERT(map_min(&t) == NULL); + CU_ASSERT(map_max(&t) == NULL); + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); +} + +static void map_2(void) { + map_t t; + map_init(&t, compare); + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, i); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(i == (int)map_min(&t)->key); + CU_ASSERT(COUNT == (int)map_max(&t)->key); + __remove(&t, (int)map_min(&t)->key); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, i); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(1 == (int)map_min(&t)->key); + CU_ASSERT(COUNT - i + 1 == (int)map_max(&t)->key); + __remove(&t, (int)map_max(&t)->key); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); +} + +static void map_3(void) { + map_t t; + map_init(&t, compare); + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, COUNT - i + 1); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(1 == (int)map_min(&t)->key); + CU_ASSERT(COUNT - i + 1 == (int)map_max(&t)->key); + __remove(&t, (int)map_max(&t)->key); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + for (int i=1; i<=COUNT; i++) + __insert(&t, COUNT - i + 1); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + CU_ASSERT(i == (int)map_min(&t)->key); + CU_ASSERT(COUNT == (int)map_max(&t)->key); + __remove(&t, (int)map_min(&t)->key); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); +} + +static void map_4(void) { + map_t t; + map_init(&t, compare); + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, (int)random()); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + __remove(&t, (int)map_min(&t)->key); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, (int)random()); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + for (int i=1; i<=COUNT; i++) { + __remove(&t, (int)map_max(&t)->key); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, (int)random()); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) { + __remove(&t, (int)random()); + CU_ASSERT(map_size(&t) + i == COUNT); + } + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); +} + +static void map_5(void) { + map_t t; + map_init(&t, compare); + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, (int)random()); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + data_t * d; + int key = 0; + + map_iter_t it; + map_iter_init(&it, &t, MI_FLAG_FWD); + map_for_each(&it, d, node) { + CU_ASSERT(key < (int)d->node.key); + key = (int)d->node.key; + } + + key = INT32_MAX; + map_iter_init(&it, &t, MI_FLAG_BWD); + map_for_each(&it, d, node) { + CU_ASSERT((int)d->node.key < key); + key = (int)d->node.key; + } +} + +static void map_6(void) { + map_t t; + map_init(&t, compare); + + CU_ASSERT(map_empty(&t) == true); + CU_ASSERT(map_size(&t) == 0); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) + __insert(&t, (int)random()); + + CU_ASSERT(map_empty(&t) == false); + CU_ASSERT(map_size(&t) == COUNT); + + srandom(SEED); + for (int i=1; i<=COUNT; i++) { + map_node_t * node = map_find(&t, (const void *)random()); + CU_ASSERT_PTR_NOT_NULL_FATAL(node); + } +} + +void map_test(void) { + CU_pSuite suite = CU_add_suite("map", init_map, clean_map); + if (NULL == suite) + return; + + if (CU_add_test(suite, "test of --> map_1", map_1) == NULL) return; + if (CU_add_test(suite, "test of --> map_2", map_2) == NULL) return; + if (CU_add_test(suite, "test of --> map_3", map_3) == NULL) return; + if (CU_add_test(suite, "test of --> map_4", map_4) == NULL) return; + if (CU_add_test(suite, "test of --> map_5", map_5) == NULL) return; + if (CU_add_test(suite, "test of --> map_6", map_6) == NULL) return; +} |