tests/utests/basic/test_hash_table.c - github/CESNET/libyang - Gitiles

 /**
  * @file test_hash_table.c
  * @author: Radek Krejci <rkrejci@cesnet.cz>
  * @brief unit tests for functions from hash_table.c
  *
  * Copyright (c) 2018 CESNET, z.s.p.o.
  *
  * This source code is licensed under BSD 3-Clause License (the "License").
  * You may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     https://opensource.org/licenses/BSD-3-Clause
  */
 #define _UTEST_MAIN_
 #include "utests.h"

 #include <stdlib.h>

 #include "hash_table.h"
 #include "ly_common.h"

 static void
 test_invalid_arguments(void **state)
 {
     assert_int_equal(LY_EINVAL, lydict_insert(NULL, NULL, 0, NULL));
     CHECK_LOG_LASTMSG("Invalid argument ctx (lydict_insert()).");

     assert_int_equal(LY_EINVAL, lydict_insert_zc(NULL, NULL, NULL));
     CHECK_LOG_LASTMSG("Invalid argument ctx (lydict_insert_zc()).");
     assert_int_equal(LY_EINVAL, lydict_insert_zc(UTEST_LYCTX, NULL, NULL));
     CHECK_LOG_CTX("Invalid argument str_p (lydict_insert_zc()).", NULL, 0);
 }

 static void
 test_dict_hit(void **state)
 {
     const char *str1, *str2, *str3;

     /* insert 2 strings, one of them repeatedly */
     assert_int_equal(LY_SUCCESS, lydict_insert(UTEST_LYCTX, "test1", 0, &str1));
     assert_non_null(str1);
     /* via zerocopy we have to get the same pointer as provided */
     assert_non_null(str2 = strdup("test2"));
     assert_int_equal(LY_SUCCESS, lydict_insert_zc(UTEST_LYCTX, (char *)str2, &str3));
     assert_ptr_equal(str2, str3);
     /* here we get the same pointer as in case the string was inserted first time */
     assert_int_equal(LY_SUCCESS, lydict_insert(UTEST_LYCTX, "test1", 0, &str2));
     assert_non_null(str2);
     assert_ptr_equal(str1, str2);

     /* remove strings, but the repeatedly inserted only once */
     lydict_remove(UTEST_LYCTX, "test1");
     lydict_remove(UTEST_LYCTX, "test2");

     /* destroy dictionary - should raise warning about data presence */
     ly_ctx_destroy(UTEST_LYCTX);
     UTEST_LYCTX = NULL;
     CHECK_LOG_LASTMSG("String \"test1\" not freed from the dictionary, refcount 1.");

 #ifndef NDEBUG
     /* cleanup */
     free((char *)str1);
 #endif
 }

 static uint8_t
 ht_equal_clb(void *val1, void *val2, uint8_t mod, void *cb_data)
 {
     int *v1, *v2;

     (void)mod;
     (void)cb_data;

     v1 = (int *)val1;
     v2 = (int *)val2;

     return *v1 == *v2;
 }

 static void
 test_ht_basic(void **UNUSED(state))
 {
     uint32_t i;
     struct ly_ht *ht;

     assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 0));

     i = 2;
     assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
     assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
     assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
     assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
     assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
     assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
     CHECK_LOG_LASTMSG("Invalid argument hash (lyht_remove_with_resize_cb()).");

     lyht_free(ht, NULL);
 }

 static void
 test_ht_resize(void **UNUSED(state))
 {
     uint32_t i;
     struct ly_ht *ht;

     assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
     assert_int_equal(8, ht->size);

     /* insert records into indexes 2-7 */
     for (i = 2; i < 8; ++i) {
         assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
     }
     /* check that table resized */
     assert_int_equal(16, ht->size);

     /* check expected content of the table */
     for (i = 0; i < 16; ++i) {
         if ((i >= 2) && (i < 8)) {
             /* inserted data on indexes 2-7 */
             assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
             assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
         } else {
             /* nothing otherwise */
             assert_int_equal(UINT32_MAX, ht->hlists[i].first);
             assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
         }
     }

     /* removing not present data should fail */
     for (i = 0; i < 2; ++i) {
         assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
         CHECK_LOG_LASTMSG("Invalid argument hash (lyht_remove_with_resize_cb()).");
     }
     /* removing present data, resize should happened
      * when we are below 25% of the table filled, so with 3 records left */
     for ( ; i < 5; ++i) {
         assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
     }
     assert_int_equal(8, ht->size);

     /* remove the rest */
     for ( ; i < 8; ++i) {
         assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
     }

     for (i = 0; i < 8; ++i) {
         assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
     }

     /* cleanup */
     lyht_free(ht, NULL);
 }

 static void
 test_ht_collisions(void **UNUSED(state))
 {
 #define GET_REC_INT(rec) (*((uint32_t *)&(rec)->val))

     uint32_t i;
     struct ly_ht_rec *rec;
     struct ly_ht *ht;
     uint32_t rec_idx;
     int count;

     assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));

     for (i = 2; i < 6; ++i) {
         assert_int_equal(lyht_insert(ht, &i, 2, NULL), 0);
     }

     /* check all records */
     for (i = 0; i < 8; ++i) {
         if (i == 2) {
             assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
         } else {
             assert_int_equal(UINT32_MAX, ht->hlists[i].first);
         }
     }
     for (i = 0; i < 8; ++i) {
         if ((i >= 2) && (i < 6)) {
             assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
         } else {
             assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
         }
     }
     rec_idx = ht->hlists[2].first;
     count = 0;
     while (rec_idx != UINT32_MAX) {
         rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
         rec_idx = rec->next;
         assert_int_equal(rec->hash, 2);
         count++;
     }
     assert_int_equal(count, 4);

     i = 4;
     assert_int_equal(lyht_remove(ht, &i, 2), 0);

     rec = lyht_get_rec(ht->recs, ht->rec_size, i);

     i = 2;
     assert_int_equal(lyht_remove(ht, &i, 2), 0);

     /* check all records */
     for (i = 0; i < 8; ++i) {
         if (i == 2) {
             assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
         } else {
             assert_int_equal(UINT32_MAX, ht->hlists[i].first);
         }
     }
     for (i = 0; i < 8; ++i) {
         if ((i == 3) || (i == 5)) {
             assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
         } else {
             assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
         }
     }
     rec_idx = ht->hlists[2].first;
     count = 0;
     while (rec_idx != UINT32_MAX) {
         rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
         rec_idx = rec->next;
         assert_int_equal(rec->hash, 2);
         count++;
     }
     assert_int_equal(count, 2);

     for (i = 0; i < 8; ++i) {
         if ((i == 3) || (i == 5)) {
             assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
         } else {
             assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
         }
     }

     i = 3;
     assert_int_equal(lyht_remove(ht, &i, 2), 0);
     i = 5;
     assert_int_equal(lyht_remove(ht, &i, 2), 0);

     /* check all records */
     for (i = 0; i < 8; ++i) {
         assert_int_equal(UINT32_MAX, ht->hlists[i].first);
     }

     lyht_free(ht, NULL);
 }

 int
 main(void)
 {
     const struct CMUnitTest tests[] = {
         UTEST(test_invalid_arguments),
         UTEST(test_dict_hit),
         UTEST(test_ht_basic),
         UTEST(test_ht_resize),
         UTEST(test_ht_collisions),
     };

     return cmocka_run_group_tests(tests, NULL, NULL);
 }
	/**
	* @file test_hash_table.c
	* @author: Radek Krejci <rkrejci@cesnet.cz>
	* @brief unit tests for functions from hash_table.c
	*
	* Copyright (c) 2018 CESNET, z.s.p.o.
	*
	* This source code is licensed under BSD 3-Clause License (the "License").
	* You may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* https://opensource.org/licenses/BSD-3-Clause
	*/
	#define _UTEST_MAIN_
	#include "utests.h"

	#include <stdlib.h>

	#include "hash_table.h"
	#include "ly_common.h"

	static void
	test_invalid_arguments(void **state)
	{
	assert_int_equal(LY_EINVAL, lydict_insert(NULL, NULL, 0, NULL));
	CHECK_LOG_LASTMSG("Invalid argument ctx (lydict_insert()).");

	assert_int_equal(LY_EINVAL, lydict_insert_zc(NULL, NULL, NULL));
	CHECK_LOG_LASTMSG("Invalid argument ctx (lydict_insert_zc()).");
	assert_int_equal(LY_EINVAL, lydict_insert_zc(UTEST_LYCTX, NULL, NULL));
	CHECK_LOG_CTX("Invalid argument str_p (lydict_insert_zc()).", NULL, 0);
	}

	static void
	test_dict_hit(void **state)
	{
	const char str1, str2, *str3;

	/* insert 2 strings, one of them repeatedly */
	assert_int_equal(LY_SUCCESS, lydict_insert(UTEST_LYCTX, "test1", 0, &str1));
	assert_non_null(str1);
	/* via zerocopy we have to get the same pointer as provided */
	assert_non_null(str2 = strdup("test2"));
	assert_int_equal(LY_SUCCESS, lydict_insert_zc(UTEST_LYCTX, (char *)str2, &str3));
	assert_ptr_equal(str2, str3);
	/* here we get the same pointer as in case the string was inserted first time */
	assert_int_equal(LY_SUCCESS, lydict_insert(UTEST_LYCTX, "test1", 0, &str2));
	assert_non_null(str2);
	assert_ptr_equal(str1, str2);

	/* remove strings, but the repeatedly inserted only once */
	lydict_remove(UTEST_LYCTX, "test1");
	lydict_remove(UTEST_LYCTX, "test2");

	/* destroy dictionary - should raise warning about data presence */
	ly_ctx_destroy(UTEST_LYCTX);
	UTEST_LYCTX = NULL;
	CHECK_LOG_LASTMSG("String \"test1\" not freed from the dictionary, refcount 1.");

	#ifndef NDEBUG
	/* cleanup */
	free((char *)str1);
	#endif
	}

	static uint8_t
	ht_equal_clb(void val1, void val2, uint8_t mod, void *cb_data)
	{
	int v1, v2;

	(void)mod;
	(void)cb_data;

	v1 = (int *)val1;
	v2 = (int *)val2;

	return v1 == v2;
	}

	static void
	test_ht_basic(void **UNUSED(state))
	{
	uint32_t i;
	struct ly_ht *ht;

	assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 0));

	i = 2;
	assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
	assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
	assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
	assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
	assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
	assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
	CHECK_LOG_LASTMSG("Invalid argument hash (lyht_remove_with_resize_cb()).");

	lyht_free(ht, NULL);
	}

	static void
	test_ht_resize(void **UNUSED(state))
	{
	uint32_t i;
	struct ly_ht *ht;

	assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
	assert_int_equal(8, ht->size);

	/* insert records into indexes 2-7 */
	for (i = 2; i < 8; ++i) {
	assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
	}
	/* check that table resized */
	assert_int_equal(16, ht->size);

	/* check expected content of the table */
	for (i = 0; i < 16; ++i) {
	if ((i >= 2) && (i < 8)) {
	/* inserted data on indexes 2-7 */
	assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
	assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
	} else {
	/* nothing otherwise */
	assert_int_equal(UINT32_MAX, ht->hlists[i].first);
	assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
	}
	}

	/* removing not present data should fail */
	for (i = 0; i < 2; ++i) {
	assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
	CHECK_LOG_LASTMSG("Invalid argument hash (lyht_remove_with_resize_cb()).");
	}
	/* removing present data, resize should happened
	* when we are below 25% of the table filled, so with 3 records left */
	for ( ; i < 5; ++i) {
	assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
	}
	assert_int_equal(8, ht->size);

	/* remove the rest */
	for ( ; i < 8; ++i) {
	assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
	}

	for (i = 0; i < 8; ++i) {
	assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
	}

	/* cleanup */
	lyht_free(ht, NULL);
	}

	static void
	test_ht_collisions(void **UNUSED(state))
	{
	#define GET_REC_INT(rec) (((uint32_t )&(rec)->val))

	uint32_t i;
	struct ly_ht_rec *rec;
	struct ly_ht *ht;
	uint32_t rec_idx;
	int count;

	assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));

	for (i = 2; i < 6; ++i) {
	assert_int_equal(lyht_insert(ht, &i, 2, NULL), 0);
	}

	/* check all records */
	for (i = 0; i < 8; ++i) {
	if (i == 2) {
	assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
	} else {
	assert_int_equal(UINT32_MAX, ht->hlists[i].first);
	}
	}
	for (i = 0; i < 8; ++i) {
	if ((i >= 2) && (i < 6)) {
	assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
	} else {
	assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
	}
	}
	rec_idx = ht->hlists[2].first;
	count = 0;
	while (rec_idx != UINT32_MAX) {
	rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
	rec_idx = rec->next;
	assert_int_equal(rec->hash, 2);
	count++;
	}
	assert_int_equal(count, 4);

	i = 4;
	assert_int_equal(lyht_remove(ht, &i, 2), 0);

	rec = lyht_get_rec(ht->recs, ht->rec_size, i);

	i = 2;
	assert_int_equal(lyht_remove(ht, &i, 2), 0);

	/* check all records */
	for (i = 0; i < 8; ++i) {
	if (i == 2) {
	assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
	} else {
	assert_int_equal(UINT32_MAX, ht->hlists[i].first);
	}
	}
	for (i = 0; i < 8; ++i) {
	if ((i == 3) \|\| (i == 5)) {
	assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
	} else {
	assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
	}
	}
	rec_idx = ht->hlists[2].first;
	count = 0;
	while (rec_idx != UINT32_MAX) {
	rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
	rec_idx = rec->next;
	assert_int_equal(rec->hash, 2);
	count++;
	}
	assert_int_equal(count, 2);

	for (i = 0; i < 8; ++i) {
	if ((i == 3) \|\| (i == 5)) {
	assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
	} else {
	assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
	}
	}

	i = 3;
	assert_int_equal(lyht_remove(ht, &i, 2), 0);
	i = 5;
	assert_int_equal(lyht_remove(ht, &i, 2), 0);

	/* check all records */
	for (i = 0; i < 8; ++i) {
	assert_int_equal(UINT32_MAX, ht->hlists[i].first);
	}

	lyht_free(ht, NULL);
	}

	int
	main(void)
	{
	const struct CMUnitTest tests[] = {
	UTEST(test_invalid_arguments),
	UTEST(test_dict_hit),
	UTEST(test_ht_basic),
	UTEST(test_ht_resize),
	UTEST(test_ht_collisions),
	};

	return cmocka_run_group_tests(tests, NULL, NULL);
	}