# HG changeset patch # User Mike Becker # Date 1576781921 -3600 # Node ID be77fb2da242d115855cbefc49ce2f1a2ca00e6c # Parent 6f63f5ed3cabe194f87104ff286c38c88f1b5af6 adds set operations for UcxMap diff -r 6f63f5ed3cab -r be77fb2da242 src/map.c --- a/src/map.c Thu Dec 19 18:47:23 2019 +0100 +++ b/src/map.c Thu Dec 19 19:58:41 2019 +0100 @@ -103,7 +103,7 @@ map->count = 0; } -int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data) { +int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) { UcxMapIterator i = ucx_map_iterator(from); void *value; UCX_MAP_FOREACH(key, value, i) { @@ -114,9 +114,14 @@ return 0; } -UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) { +UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data) { + return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data); +} + +UcxMap *ucx_map_clone_a(UcxAllocator *allocator, + UcxMap const *map, copy_func fnc, void *data) { size_t bs = (map->count * 5) >> 1; - UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size); + UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size); if (!newmap) { return NULL; } @@ -235,8 +240,8 @@ return NULL; } -void *ucx_map_get(UcxMap *map, UcxKey key) { - return ucx_map_get_and_remove(map, key, 0); +void *ucx_map_get(UcxMap const *map, UcxKey key) { + return ucx_map_get_and_remove((UcxMap *)map, key, 0); } void *ucx_map_remove(UcxMap *map, UcxKey key) { @@ -294,7 +299,7 @@ return h; } -UcxMapIterator ucx_map_iterator(UcxMap *map) { +UcxMapIterator ucx_map_iterator(UcxMap const *map) { UcxMapIterator i; i.map = map; i.cur = NULL; @@ -335,3 +340,63 @@ return 0; } +UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata) { + return ucx_map_union_a(ucx_default_allocator(), + first, second, cpfnc, cpdata); +} + +UcxMap* ucx_map_union_a(UcxAllocator *allocator, + const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata) { + UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata); + ucx_map_copy(second, result, cpfnc, cpdata); + return result; +} + +UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata) { + return ucx_map_intersection_a(ucx_default_allocator(), + first, second, cpfnc, cpdata); +} + +UcxMap* ucx_map_intersection_a(UcxAllocator *allocator, + const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata) { + UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ? + first->size : second->size); + + UcxMapIterator iter = ucx_map_iterator(first); + void* value; + UCX_MAP_FOREACH(key, value, iter) { + if (ucx_map_get(second, key)) { + ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value); + } + } + + return result; +} + +UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata) { + return ucx_map_difference_a(ucx_default_allocator(), + first, second, cpfnc, cpdata); +} + +UcxMap* ucx_map_difference_a(UcxAllocator *allocator, + const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata) { + + UcxMap *result = ucx_map_new_a(allocator, first->size - second->count); + + UcxMapIterator iter = ucx_map_iterator(first); + void* value; + UCX_MAP_FOREACH(key, value, iter) { + if (!ucx_map_get(second, key)) { + ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value); + } + } + + ucx_map_rehash(result); + return result; +} \ No newline at end of file diff -r 6f63f5ed3cab -r be77fb2da242 src/ucx/map.h --- a/src/ucx/map.h Thu Dec 19 18:47:23 2019 +0100 +++ b/src/ucx/map.h Thu Dec 19 19:58:41 2019 +0100 @@ -124,7 +124,7 @@ /** Structure for an iterator over a UcxMap. */ struct UcxMapIterator { /** The map to iterate over. */ - UcxMap *map; + UcxMap const *map; /** The current map element. */ UcxMapElement *cur; @@ -211,7 +211,7 @@ * @param data additional data for the copy function * @return 0 on success or a non-zero value on memory allocation errors */ -int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data); +int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data); /** * Clones the map and rehashes if necessary. @@ -227,7 +227,25 @@ * @return the cloned map * @see ucx_map_copy() */ -UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data); +UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data); + +/** + * Clones the map and rehashes if necessary. + * + * Note: In contrast to ucx_map_rehash() the load factor is irrelevant. + * This function always ensures a new UcxMap.size of at least + * 2.5*UcxMap.count. + * + * @param allocator the allocator to use for the cloned map + * @param map the map to clone + * @param fnc the copy function to use or NULL if the new and + * the old map shall share the data pointers + * @param data additional data for the copy function + * @return the cloned map + * @see ucx_map_copy() + */ +UcxMap *ucx_map_clone_a(UcxAllocator *allocator, + UcxMap const *map, copy_func fnc, void *data); /** * Increases size of the hash map, if necessary. @@ -264,7 +282,7 @@ * @param key the key * @return the value */ -void* ucx_map_get(UcxMap *map, UcxKey key); +void* ucx_map_get(UcxMap const *map, UcxKey key); /** * Removes a key/value-pair from the map by using the key. @@ -406,7 +424,7 @@ * first element list * @see ucx_map_iter_next() */ -UcxMapIterator ucx_map_iterator(UcxMap *map); +UcxMapIterator ucx_map_iterator(UcxMap const *map); /** * Proceeds to the next element of the map (if any). @@ -426,6 +444,102 @@ */ int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value); +/** + * Returns the union of two maps. + * + * The union is a fresh map which is filled by two successive calls of + * ucx_map_copy() on the two input maps. + * + * @param first the first source map + * @param second the second source map + * @param cpfnc a function to copy the elements + * @param cpdata additional data for the copy function + * @return a new map containing the union + */ +UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata); + +/** + * Returns the union of two maps. + * + * The union is a fresh map which is filled by two successive calls of + * ucx_map_copy() on the two input maps. + * + * @param allocator the allocator that shall be used by the new map + * @param first the first source map + * @param second the second source map + * @param cpfnc a function to copy the elements + * @param cpdata additional data for the copy function + * @return a new map containing the union + */ +UcxMap* ucx_map_union_a(UcxAllocator *allocator, + const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata); + +/** + * Returns the intersection of two maps. + * + * The intersection is defined as a copy of the first map with every element + * removed that has no valid key in the second map. + * + * @param first the first source map + * @param second the second source map + * @param cpfnc a function to copy the elements + * @param cpdata additional data for the copy function + * @return a new map containing the intersection + */ +UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata); + +/** + * Returns the intersection of two maps. + * + * The intersection is defined as a copy of the first map with every element + * removed that has no valid key in the second map. + * + * @param allocator the allocator that shall be used by the new map + * @param first the first source map + * @param second the second source map + * @param cpfnc a function to copy the elements + * @param cpdata additional data for the copy function + * @return a new map containing the intersection + */ +UcxMap* ucx_map_intersection_a(UcxAllocator *allocator, + const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata); + +/** + * Returns the difference of two maps. + * + * The difference contains a copy of all elements of the first map + * for which the corresponding keys cannot be found in the second map. + * + * @param first the first source map + * @param second the second source map + * @param cpfnc a function to copy the elements + * @param cpdata additional data for the copy function + * @return a new list containing the difference + */ +UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata); + +/** + * Returns the difference of two maps. + * + * The difference contains a copy of all elements of the first map + * for which the corresponding keys cannot be found in the second map. + * + * @param allocator the allocator that shall be used by the new map + * @param first the first source map + * @param second the second source map + * @param cpfnc a function to copy the elements + * @param cpdata additional data for the copy function + * @return a new list containing the difference + */ +UcxMap* ucx_map_difference_a(UcxAllocator *allocator, + const UcxMap *first, const UcxMap *second, + copy_func cpfnc, void* cpdata); + #ifdef __cplusplus } diff -r 6f63f5ed3cab -r be77fb2da242 test/main.c --- a/test/main.c Thu Dec 19 18:47:23 2019 +0100 +++ b/test/main.c Thu Dec 19 19:58:41 2019 +0100 @@ -213,6 +213,9 @@ ucx_test_register(suite, test_ucx_map_iterator_chain); ucx_test_register(suite, test_ucx_map_clone); ucx_test_register(suite, test_ucx_map_rehash); + ucx_test_register(suite, test_ucx_map_union); + ucx_test_register(suite, test_ucx_map_intersection); + ucx_test_register(suite, test_ucx_map_difference); /* UcxPropertiesParser Tests */ ucx_test_register(suite, test_ucx_properties_new); diff -r 6f63f5ed3cab -r be77fb2da242 test/map_tests.c --- a/test/map_tests.c Thu Dec 19 18:47:23 2019 +0100 +++ b/test/map_tests.c Thu Dec 19 19:58:41 2019 +0100 @@ -27,6 +27,7 @@ */ #include "map_tests.h" +#include UCX_TEST(test_ucx_map_new) { UcxMap *map = ucx_map_new(16); @@ -304,3 +305,127 @@ ucx_map_free(map); } + +UCX_TEST(test_ucx_map_union) { + int td[5]; + size_t intlen = sizeof(int); + td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000; + + UcxMap *first = ucx_map_new(4); + UcxMap *second = ucx_map_new(4); + + ucx_map_cstr_put(first, "key0", &td[0]); + ucx_map_cstr_put(first, "key1", &td[1]); + ucx_map_cstr_put(second, "key2", &td[2]); + ucx_map_cstr_put(second, "key0", &td[3]); + ucx_map_cstr_put(second, "key3", &td[4]); + + UcxMap *result = ucx_map_union(first, second, ucx_memcpy, &intlen); + + UCX_TEST_BEGIN + + int* r; + UCX_TEST_ASSERT(result->count == 4, + "result has incorrect number of elements"); + + r = (int*)ucx_map_cstr_get(result, "key0"); + UCX_TEST_ASSERT(!!r, "key0 is not present"); + UCX_TEST_ASSERT(*r == td[3], "key0 has not been overwritten"); + r = (int*)ucx_map_cstr_get(result, "key1"); + UCX_TEST_ASSERT(!!r, "key1 is not present"); + UCX_TEST_ASSERT(*r == td[1], "key1 contains wrong data"); + r = (int*)ucx_map_cstr_get(result, "key2"); + UCX_TEST_ASSERT(!!r, "key2 is not present"); + UCX_TEST_ASSERT(*r == td[2], "key2 contains wrong data"); + r = (int*)ucx_map_cstr_get(result, "key3"); + UCX_TEST_ASSERT(!!r, "key3 is not present"); + UCX_TEST_ASSERT(*r == td[4], "key3 contains wrong data"); + + UCX_TEST_END + + ucx_map_free_content(result, NULL); + ucx_map_free(result); + ucx_map_free(second); + ucx_map_free(first); +} + +UCX_TEST(test_ucx_map_intersection) { + int td[5]; + size_t intlen = sizeof(int); + td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000; + + UcxMap *first = ucx_map_new(4); + UcxMap *second = ucx_map_new(4); + + ucx_map_cstr_put(first, "key0", &td[0]); + ucx_map_cstr_put(first, "key1", &td[1]); + ucx_map_cstr_put(first, "key4", &td[3]); + ucx_map_cstr_put(second, "key2", &td[2]); + ucx_map_cstr_put(second, "key0", &td[3]); + ucx_map_cstr_put(second, "key3", &td[4]); + ucx_map_cstr_put(second, "key4", &td[4]); + + UcxMap *result = ucx_map_intersection(first, second, + ucx_memcpy, &intlen); + + UCX_TEST_BEGIN + + int* r; + UCX_TEST_ASSERT(result->count == 2, + "result has incorrect number of elements"); + + r = (int*)ucx_map_cstr_get(result, "key0"); + UCX_TEST_ASSERT(!!r, "key0 is not present"); + UCX_TEST_ASSERT(*r == td[0], "key0 has not original data"); + r = (int*)ucx_map_cstr_get(result, "key4"); + UCX_TEST_ASSERT(!!r, "key4 is not present"); + UCX_TEST_ASSERT(*r == td[3], "key4 has not original data"); + + UCX_TEST_END + + ucx_map_free_content(result, NULL); + ucx_map_free(result); + ucx_map_free(second); + ucx_map_free(first); +} + + +UCX_TEST(test_ucx_map_difference) { + int td[5]; + size_t intlen = sizeof(int); + td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000; + + UcxMap *first = ucx_map_new(4); + UcxMap *second = ucx_map_new(4); + + ucx_map_cstr_put(first, "key0", &td[0]); + ucx_map_cstr_put(first, "key1", &td[1]); + ucx_map_cstr_put(first, "key2", &td[2]); + ucx_map_cstr_put(first, "key4", &td[3]); + ucx_map_cstr_put(second, "key0", &td[3]); + ucx_map_cstr_put(second, "key3", &td[4]); + ucx_map_cstr_put(second, "key4", &td[4]); + + UcxMap *result = ucx_map_difference(first, second, ucx_memcpy, &intlen); + + UCX_TEST_BEGIN + + int* r; + UCX_TEST_ASSERT(result->count == 2, + "result has incorrect number of elements"); + + r = (int*)ucx_map_cstr_get(result, "key1"); + UCX_TEST_ASSERT(!!r, "key1 is not present"); + UCX_TEST_ASSERT(*r == td[1], "key1 has incorrect data"); + r = (int*)ucx_map_cstr_get(result, "key2"); + UCX_TEST_ASSERT(!!r, "key2 is not present"); + UCX_TEST_ASSERT(*r == td[2], "key2 has incorrect data"); + + UCX_TEST_END + + ucx_map_free_content(result, NULL); + ucx_map_free(result); + ucx_map_free(second); + ucx_map_free(first); +} + diff -r 6f63f5ed3cab -r be77fb2da242 test/map_tests.h --- a/test/map_tests.h Thu Dec 19 18:47:23 2019 +0100 +++ b/test/map_tests.h Thu Dec 19 19:58:41 2019 +0100 @@ -46,6 +46,9 @@ UCX_TEST(test_ucx_map_iterator_chain); UCX_TEST(test_ucx_map_clone); UCX_TEST(test_ucx_map_rehash); +UCX_TEST(test_ucx_map_union); +UCX_TEST(test_ucx_map_intersection); +UCX_TEST(test_ucx_map_difference); #ifdef __cplusplus