Mercurial > hg > ucx / changeset

--- 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

--- 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.
+ *
+ * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
+ * This function <i>always</i> 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 <code>NULL</code> 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
 }

--- 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);

--- 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/utils.h>
 
 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);
+}
+

--- 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