Mercurial > hg > ucx / changeset

     1.1 --- a/src/map.c	Thu Dec 19 18:47:23 2019 +0100
     1.2 +++ b/src/map.c	Thu Dec 19 19:58:41 2019 +0100
     1.3 @@ -103,7 +103,7 @@
     1.4      map->count = 0;
     1.5  }
     1.6  
     1.7 -int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data) {
     1.8 +int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) {
     1.9      UcxMapIterator i = ucx_map_iterator(from);
    1.10      void *value;
    1.11      UCX_MAP_FOREACH(key, value, i) {
    1.12 @@ -114,9 +114,14 @@
    1.13      return 0;
    1.14  }
    1.15  
    1.16 -UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {
    1.17 +UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data) {
    1.18 +    return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data);
    1.19 +}
    1.20 +
    1.21 +UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
    1.22 +        UcxMap const *map, copy_func fnc, void *data) {
    1.23      size_t bs = (map->count * 5) >> 1;
    1.24 -    UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);
    1.25 +    UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size);
    1.26      if (!newmap) {
    1.27          return NULL;
    1.28      }
    1.29 @@ -235,8 +240,8 @@
    1.30      return NULL;
    1.31  }
    1.32  
    1.33 -void *ucx_map_get(UcxMap *map, UcxKey key) {
    1.34 -    return ucx_map_get_and_remove(map, key, 0);
    1.35 +void *ucx_map_get(UcxMap const *map, UcxKey key) {
    1.36 +    return ucx_map_get_and_remove((UcxMap *)map, key, 0);
    1.37  }
    1.38  
    1.39  void *ucx_map_remove(UcxMap *map, UcxKey key) {
    1.40 @@ -294,7 +299,7 @@
    1.41      return h;
    1.42  }
    1.43  
    1.44 -UcxMapIterator ucx_map_iterator(UcxMap *map) {
    1.45 +UcxMapIterator ucx_map_iterator(UcxMap const *map) {
    1.46      UcxMapIterator i;
    1.47      i.map = map;
    1.48      i.cur = NULL;
    1.49 @@ -335,3 +340,63 @@
    1.50      return 0;
    1.51  }
    1.52  
    1.53 +UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
    1.54 +                      copy_func cpfnc, void* cpdata) {
    1.55 +    return ucx_map_union_a(ucx_default_allocator(),
    1.56 +            first, second, cpfnc, cpdata);
    1.57 +}
    1.58 +
    1.59 +UcxMap* ucx_map_union_a(UcxAllocator *allocator,
    1.60 +                        const UcxMap *first, const UcxMap *second,
    1.61 +                        copy_func cpfnc, void* cpdata) {
    1.62 +    UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata);
    1.63 +    ucx_map_copy(second, result, cpfnc, cpdata);
    1.64 +    return result;
    1.65 +}
    1.66 +
    1.67 +UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
    1.68 +                             copy_func cpfnc, void* cpdata) {
    1.69 +    return ucx_map_intersection_a(ucx_default_allocator(),
    1.70 +            first, second, cpfnc, cpdata);
    1.71 +}
    1.72 +
    1.73 +UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
    1.74 +                               const UcxMap *first, const UcxMap *second,
    1.75 +                               copy_func cpfnc, void* cpdata) {
    1.76 +    UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ?
    1.77 +            first->size : second->size);
    1.78 +
    1.79 +    UcxMapIterator iter = ucx_map_iterator(first);
    1.80 +    void* value;
    1.81 +    UCX_MAP_FOREACH(key, value, iter) {
    1.82 +        if (ucx_map_get(second, key)) {
    1.83 +            ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
    1.84 +        }
    1.85 +    }
    1.86 +
    1.87 +    return result;
    1.88 +}
    1.89 +
    1.90 +UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
    1.91 +                           copy_func cpfnc, void* cpdata) {
    1.92 +    return ucx_map_difference_a(ucx_default_allocator(),
    1.93 +            first, second, cpfnc, cpdata);
    1.94 +}
    1.95 +
    1.96 +UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
    1.97 +                             const UcxMap *first, const UcxMap *second,
    1.98 +                             copy_func cpfnc, void* cpdata) {
    1.99 +
   1.100 +    UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);
   1.101 +
   1.102 +    UcxMapIterator iter = ucx_map_iterator(first);
   1.103 +    void* value;
   1.104 +    UCX_MAP_FOREACH(key, value, iter) {
   1.105 +        if (!ucx_map_get(second, key)) {
   1.106 +            ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
   1.107 +        }
   1.108 +    }
   1.109 +
   1.110 +    ucx_map_rehash(result);
   1.111 +    return result;
   1.112 +}
   1.113 \ No newline at end of file

     2.1 --- a/src/ucx/map.h	Thu Dec 19 18:47:23 2019 +0100
     2.2 +++ b/src/ucx/map.h	Thu Dec 19 19:58:41 2019 +0100
     2.3 @@ -124,7 +124,7 @@
     2.4  /** Structure for an iterator over a UcxMap. */
     2.5  struct UcxMapIterator {
     2.6      /** The map to iterate over. */
     2.7 -    UcxMap        *map;
     2.8 +    UcxMap const  *map;
     2.9      
    2.10      /** The current map element. */
    2.11      UcxMapElement *cur;
    2.12 @@ -211,7 +211,7 @@
    2.13   * @param data additional data for the copy function
    2.14   * @return 0 on success or a non-zero value on memory allocation errors
    2.15   */
    2.16 -int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data);
    2.17 +int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data);
    2.18  
    2.19  /**
    2.20   * Clones the map and rehashes if necessary.
    2.21 @@ -227,7 +227,25 @@
    2.22   * @return the cloned map
    2.23   * @see ucx_map_copy()
    2.24   */
    2.25 -UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data);
    2.26 +UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data);
    2.27 +
    2.28 +/**
    2.29 + * Clones the map and rehashes if necessary.
    2.30 + *
    2.31 + * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
    2.32 + * This function <i>always</i> ensures a new UcxMap.size of at least
    2.33 + * 2.5*UcxMap.count.
    2.34 + *
    2.35 + * @param allocator the allocator to use for the cloned map
    2.36 + * @param map the map to clone
    2.37 + * @param fnc the copy function to use or <code>NULL</code> if the new and
    2.38 + * the old map shall share the data pointers
    2.39 + * @param data additional data for the copy function
    2.40 + * @return the cloned map
    2.41 + * @see ucx_map_copy()
    2.42 + */
    2.43 +UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
    2.44 +                        UcxMap const *map, copy_func fnc, void *data);
    2.45  
    2.46  /**
    2.47   * Increases size of the hash map, if necessary.
    2.48 @@ -264,7 +282,7 @@
    2.49   * @param key the key
    2.50   * @return the value
    2.51   */
    2.52 -void* ucx_map_get(UcxMap *map, UcxKey key);
    2.53 +void* ucx_map_get(UcxMap const *map, UcxKey key);
    2.54  
    2.55  /**
    2.56   * Removes a key/value-pair from the map by using the key.
    2.57 @@ -406,7 +424,7 @@
    2.58   * first element list
    2.59   * @see ucx_map_iter_next()
    2.60   */
    2.61 -UcxMapIterator ucx_map_iterator(UcxMap *map);
    2.62 +UcxMapIterator ucx_map_iterator(UcxMap const *map);
    2.63  
    2.64  /**
    2.65   * Proceeds to the next element of the map (if any).
    2.66 @@ -426,6 +444,102 @@
    2.67   */
    2.68  int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value);
    2.69  
    2.70 +/**
    2.71 + * Returns the union of two maps.
    2.72 + *
    2.73 + * The union is a fresh map which is filled by two successive calls of
    2.74 + * ucx_map_copy() on the two input maps.
    2.75 + *
    2.76 + * @param first the first source map
    2.77 + * @param second the second source map
    2.78 + * @param cpfnc a function to copy the elements
    2.79 + * @param cpdata additional data for the copy function
    2.80 + * @return a new map containing the union
    2.81 + */
    2.82 +UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
    2.83 +                      copy_func cpfnc, void* cpdata);
    2.84 +
    2.85 +/**
    2.86 + * Returns the union of two maps.
    2.87 + *
    2.88 + * The union is a fresh map which is filled by two successive calls of
    2.89 + * ucx_map_copy() on the two input maps.
    2.90 + *
    2.91 + * @param allocator the allocator that shall be used by the new map
    2.92 + * @param first the first source map
    2.93 + * @param second the second source map
    2.94 + * @param cpfnc a function to copy the elements
    2.95 + * @param cpdata additional data for the copy function
    2.96 + * @return a new map containing the union
    2.97 + */
    2.98 +UcxMap* ucx_map_union_a(UcxAllocator *allocator,
    2.99 +                        const UcxMap *first, const UcxMap *second,
   2.100 +                        copy_func cpfnc, void* cpdata);
   2.101 +
   2.102 +/**
   2.103 + * Returns the intersection of two maps.
   2.104 + *
   2.105 + * The intersection is defined as a copy of the first map with every element
   2.106 + * removed that has no valid key in the second map.
   2.107 + *
   2.108 + * @param first the first source map
   2.109 + * @param second the second source map
   2.110 + * @param cpfnc a function to copy the elements
   2.111 + * @param cpdata additional data for the copy function
   2.112 + * @return a new map containing the intersection
   2.113 + */
   2.114 +UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
   2.115 +                             copy_func cpfnc, void* cpdata);
   2.116 +
   2.117 +/**
   2.118 + * Returns the intersection of two maps.
   2.119 + *
   2.120 + * The intersection is defined as a copy of the first map with every element
   2.121 + * removed that has no valid key in the second map.
   2.122 + *
   2.123 + * @param allocator the allocator that shall be used by the new map
   2.124 + * @param first the first source map
   2.125 + * @param second the second source map
   2.126 + * @param cpfnc a function to copy the elements
   2.127 + * @param cpdata additional data for the copy function
   2.128 + * @return a new map containing the intersection
   2.129 + */
   2.130 +UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
   2.131 +                               const UcxMap *first, const UcxMap *second,
   2.132 +                               copy_func cpfnc, void* cpdata);
   2.133 +
   2.134 +/**
   2.135 + * Returns the difference of two maps.
   2.136 + *
   2.137 + * The difference contains a copy of all elements of the first map
   2.138 + * for which the corresponding keys cannot be found in the second map.
   2.139 + *
   2.140 + * @param first the first source map
   2.141 + * @param second the second source map
   2.142 + * @param cpfnc a function to copy the elements
   2.143 + * @param cpdata additional data for the copy function
   2.144 + * @return a new list containing the difference
   2.145 + */
   2.146 +UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
   2.147 +                           copy_func cpfnc, void* cpdata);
   2.148 +
   2.149 +/**
   2.150 + * Returns the difference of two maps.
   2.151 + *
   2.152 + * The difference contains a copy of all elements of the first map
   2.153 + * for which the corresponding keys cannot be found in the second map.
   2.154 + *
   2.155 + * @param allocator the allocator that shall be used by the new map
   2.156 + * @param first the first source map
   2.157 + * @param second the second source map
   2.158 + * @param cpfnc a function to copy the elements
   2.159 + * @param cpdata additional data for the copy function
   2.160 + * @return a new list containing the difference
   2.161 + */
   2.162 +UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
   2.163 +                             const UcxMap *first, const UcxMap *second,
   2.164 +                             copy_func cpfnc, void* cpdata);
   2.165 +
   2.166  
   2.167  #ifdef	__cplusplus
   2.168  }

     3.1 --- a/test/main.c	Thu Dec 19 18:47:23 2019 +0100
     3.2 +++ b/test/main.c	Thu Dec 19 19:58:41 2019 +0100
     3.3 @@ -213,6 +213,9 @@
     3.4          ucx_test_register(suite, test_ucx_map_iterator_chain);
     3.5          ucx_test_register(suite, test_ucx_map_clone);
     3.6          ucx_test_register(suite, test_ucx_map_rehash);
     3.7 +        ucx_test_register(suite, test_ucx_map_union);
     3.8 +        ucx_test_register(suite, test_ucx_map_intersection);
     3.9 +        ucx_test_register(suite, test_ucx_map_difference);
    3.10          
    3.11          /* UcxPropertiesParser Tests */
    3.12          ucx_test_register(suite, test_ucx_properties_new);

     4.1 --- a/test/map_tests.c	Thu Dec 19 18:47:23 2019 +0100
     4.2 +++ b/test/map_tests.c	Thu Dec 19 19:58:41 2019 +0100
     4.3 @@ -27,6 +27,7 @@
     4.4   */
     4.5  
     4.6  #include "map_tests.h"
     4.7 +#include <ucx/utils.h>
     4.8  
     4.9  UCX_TEST(test_ucx_map_new) {
    4.10      UcxMap *map = ucx_map_new(16);
    4.11 @@ -304,3 +305,127 @@
    4.12  
    4.13      ucx_map_free(map);
    4.14  }
    4.15 +
    4.16 +UCX_TEST(test_ucx_map_union) {
    4.17 +    int td[5];
    4.18 +    size_t intlen = sizeof(int);
    4.19 +    td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000;
    4.20 +
    4.21 +    UcxMap *first = ucx_map_new(4);
    4.22 +    UcxMap *second = ucx_map_new(4);
    4.23 +
    4.24 +    ucx_map_cstr_put(first, "key0", &td[0]);
    4.25 +    ucx_map_cstr_put(first, "key1", &td[1]);
    4.26 +    ucx_map_cstr_put(second, "key2", &td[2]);
    4.27 +    ucx_map_cstr_put(second, "key0", &td[3]);
    4.28 +    ucx_map_cstr_put(second, "key3", &td[4]);
    4.29 +
    4.30 +    UcxMap *result = ucx_map_union(first, second, ucx_memcpy, &intlen);
    4.31 +
    4.32 +    UCX_TEST_BEGIN
    4.33 +
    4.34 +    int* r;
    4.35 +    UCX_TEST_ASSERT(result->count == 4,
    4.36 +            "result has incorrect number of elements");
    4.37 +
    4.38 +    r = (int*)ucx_map_cstr_get(result, "key0");
    4.39 +    UCX_TEST_ASSERT(!!r, "key0 is not present");
    4.40 +    UCX_TEST_ASSERT(*r == td[3], "key0 has not been overwritten");
    4.41 +    r = (int*)ucx_map_cstr_get(result, "key1");
    4.42 +    UCX_TEST_ASSERT(!!r, "key1 is not present");
    4.43 +    UCX_TEST_ASSERT(*r == td[1], "key1 contains wrong data");
    4.44 +    r = (int*)ucx_map_cstr_get(result, "key2");
    4.45 +    UCX_TEST_ASSERT(!!r, "key2 is not present");
    4.46 +    UCX_TEST_ASSERT(*r == td[2], "key2 contains wrong data");
    4.47 +    r = (int*)ucx_map_cstr_get(result, "key3");
    4.48 +    UCX_TEST_ASSERT(!!r, "key3 is not present");
    4.49 +    UCX_TEST_ASSERT(*r == td[4], "key3 contains wrong data");
    4.50 +
    4.51 +    UCX_TEST_END
    4.52 +
    4.53 +    ucx_map_free_content(result, NULL);
    4.54 +    ucx_map_free(result);
    4.55 +    ucx_map_free(second);
    4.56 +    ucx_map_free(first);
    4.57 +}
    4.58 +
    4.59 +UCX_TEST(test_ucx_map_intersection) {
    4.60 +        int td[5];
    4.61 +        size_t intlen = sizeof(int);
    4.62 +        td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000;
    4.63 +
    4.64 +        UcxMap *first = ucx_map_new(4);
    4.65 +        UcxMap *second = ucx_map_new(4);
    4.66 +
    4.67 +        ucx_map_cstr_put(first, "key0", &td[0]);
    4.68 +        ucx_map_cstr_put(first, "key1", &td[1]);
    4.69 +        ucx_map_cstr_put(first, "key4", &td[3]);
    4.70 +        ucx_map_cstr_put(second, "key2", &td[2]);
    4.71 +        ucx_map_cstr_put(second, "key0", &td[3]);
    4.72 +        ucx_map_cstr_put(second, "key3", &td[4]);
    4.73 +        ucx_map_cstr_put(second, "key4", &td[4]);
    4.74 +
    4.75 +        UcxMap *result = ucx_map_intersection(first, second,
    4.76 +                ucx_memcpy, &intlen);
    4.77 +
    4.78 +        UCX_TEST_BEGIN
    4.79 +
    4.80 +        int* r;
    4.81 +        UCX_TEST_ASSERT(result->count == 2,
    4.82 +                "result has incorrect number of elements");
    4.83 +
    4.84 +        r = (int*)ucx_map_cstr_get(result, "key0");
    4.85 +        UCX_TEST_ASSERT(!!r, "key0 is not present");
    4.86 +        UCX_TEST_ASSERT(*r == td[0], "key0 has not original data");
    4.87 +        r = (int*)ucx_map_cstr_get(result, "key4");
    4.88 +        UCX_TEST_ASSERT(!!r, "key4 is not present");
    4.89 +        UCX_TEST_ASSERT(*r == td[3], "key4 has not original data");
    4.90 +
    4.91 +        UCX_TEST_END
    4.92 +
    4.93 +        ucx_map_free_content(result, NULL);
    4.94 +        ucx_map_free(result);
    4.95 +        ucx_map_free(second);
    4.96 +        ucx_map_free(first);
    4.97 +}
    4.98 +
    4.99 +
   4.100 +UCX_TEST(test_ucx_map_difference) {
   4.101 +        int td[5];
   4.102 +        size_t intlen = sizeof(int);
   4.103 +        td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000;
   4.104 +
   4.105 +        UcxMap *first = ucx_map_new(4);
   4.106 +        UcxMap *second = ucx_map_new(4);
   4.107 +
   4.108 +        ucx_map_cstr_put(first, "key0", &td[0]);
   4.109 +        ucx_map_cstr_put(first, "key1", &td[1]);
   4.110 +        ucx_map_cstr_put(first, "key2", &td[2]);
   4.111 +        ucx_map_cstr_put(first, "key4", &td[3]);
   4.112 +        ucx_map_cstr_put(second, "key0", &td[3]);
   4.113 +        ucx_map_cstr_put(second, "key3", &td[4]);
   4.114 +        ucx_map_cstr_put(second, "key4", &td[4]);
   4.115 +
   4.116 +        UcxMap *result = ucx_map_difference(first, second, ucx_memcpy, &intlen);
   4.117 +
   4.118 +        UCX_TEST_BEGIN
   4.119 +
   4.120 +        int* r;
   4.121 +        UCX_TEST_ASSERT(result->count == 2,
   4.122 +                "result has incorrect number of elements");
   4.123 +
   4.124 +        r = (int*)ucx_map_cstr_get(result, "key1");
   4.125 +        UCX_TEST_ASSERT(!!r, "key1 is not present");
   4.126 +        UCX_TEST_ASSERT(*r == td[1], "key1 has incorrect data");
   4.127 +        r = (int*)ucx_map_cstr_get(result, "key2");
   4.128 +        UCX_TEST_ASSERT(!!r, "key2 is not present");
   4.129 +        UCX_TEST_ASSERT(*r == td[2], "key2 has incorrect data");
   4.130 +
   4.131 +        UCX_TEST_END
   4.132 +
   4.133 +        ucx_map_free_content(result, NULL);
   4.134 +        ucx_map_free(result);
   4.135 +        ucx_map_free(second);
   4.136 +        ucx_map_free(first);
   4.137 +}
   4.138 +

     5.1 --- a/test/map_tests.h	Thu Dec 19 18:47:23 2019 +0100
     5.2 +++ b/test/map_tests.h	Thu Dec 19 19:58:41 2019 +0100
     5.3 @@ -46,6 +46,9 @@
     5.4  UCX_TEST(test_ucx_map_iterator_chain);
     5.5  UCX_TEST(test_ucx_map_clone);
     5.6  UCX_TEST(test_ucx_map_rehash);
     5.7 +UCX_TEST(test_ucx_map_union);
     5.8 +UCX_TEST(test_ucx_map_intersection);
     5.9 +UCX_TEST(test_ucx_map_difference);
    5.10  
    5.11  
    5.12  #ifdef	__cplusplus