Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/hash_map.h	Mon Feb 20 19:55:42 2023 +0100
     1.2 +++ b/src/cx/hash_map.h	Thu Feb 23 18:58:15 2023 +0100
     1.3 @@ -44,16 +44,7 @@
     1.4  #endif
     1.5  
     1.6  /** Internal structure for an element of a hash map. */
     1.7 -struct cx_hash_map_element_s {
     1.8 -    /** The value data. */
     1.9 -    void *data;
    1.10 -
    1.11 -    /** A pointer to the next element in the current bucket. */
    1.12 -    struct cx_hash_map_element_s *next;
    1.13 -
    1.14 -    /** The corresponding key. */
    1.15 -    CxHashKey key;
    1.16 -};
    1.17 +struct cx_hash_map_element_s;
    1.18  
    1.19  /**
    1.20   * Internal structure for a hash map.
    1.21 @@ -84,16 +75,39 @@
    1.22   * In other words, when the iterator is finished, \c index==size .
    1.23   *
    1.24   * @param allocator the allocator to use
    1.25 + * @param itemsize the size of one element
    1.26   * @param buckets the initial number of buckets in this hash map
    1.27   * @return a pointer to the new hash map
    1.28   */
    1.29  __attribute__((__nonnull__, __warn_unused_result__))
    1.30  CxMap *cxHashMapCreate(
    1.31          CxAllocator *allocator,
    1.32 +        size_t itemsize,
    1.33          size_t buckets
    1.34  );
    1.35  
    1.36  /**
    1.37 + * Convenience function for creating a hash map that is storing pointers.
    1.38 + *
    1.39 + * If \p buckets is zero, an implementation defined default will be used.
    1.40 + *
    1.41 + * @param allocator the allocator to use
    1.42 + * @param buckets the initial number of buckets in this hash map
    1.43 + * @return a pointer to the new hash map
    1.44 + */
    1.45 +__attribute__((__nonnull__, __warn_unused_result__))
    1.46 +static inline CxMap *cxHashMapCreateForPointers(
    1.47 +        CxAllocator *allocator,
    1.48 +        size_t buckets
    1.49 +) {
    1.50 +    CxMap *map = cxHashMapCreate(allocator, sizeof(void *), buckets);
    1.51 +    if (map != NULL) {
    1.52 +        map->store_pointers = true;
    1.53 +    }
    1.54 +    return map;
    1.55 +}
    1.56 +
    1.57 +/**
    1.58   * Increases the number of buckets, if necessary.
    1.59   *
    1.60   * The load threshold is \c 0.75*buckets. If the element count exceeds the load

     2.1 --- a/src/cx/map.h	Mon Feb 20 19:55:42 2023 +0100
     2.2 +++ b/src/cx/map.h	Thu Feb 23 18:58:15 2023 +0100
     2.3 @@ -63,7 +63,15 @@
     2.4      CxAllocator *allocator;
     2.5      /** The number of elements currently stored. */
     2.6      size_t size;
     2.7 -    // TODO: elemsize + a flag if values shall be copied to the map
     2.8 +    /**
     2.9 +     * The size of an element.
    2.10 +     */
    2.11 +    size_t itemsize;
    2.12 +    /**
    2.13 +     * True, if this map shall store pointers instead
    2.14 +     * of copies of objects.
    2.15 +     */
    2.16 +    bool store_pointers;
    2.17  };
    2.18  
    2.19  /**
    2.20 @@ -161,6 +169,38 @@
    2.21      void *value;
    2.22  };
    2.23  
    2.24 +/**
    2.25 + * Advises the map to store copies of the objects (default mode of operation).
    2.26 + *
    2.27 + * Retrieving objects from this map will yield pointers to the copies stored
    2.28 + * within this list.
    2.29 + *
    2.30 + * @param map the map
    2.31 + * @see cxMapStorePointers()
    2.32 + */
    2.33 +__attribute__((__nonnull__))
    2.34 +static inline void cxMapStoreObjects(CxMap *map) {
    2.35 +    map->store_pointers = false;
    2.36 +}
    2.37 +
    2.38 +/**
    2.39 + * Advises the map to only store pointers to the objects.
    2.40 + *
    2.41 + * Retrieving objects from this list will yield the original pointers stored.
    2.42 + *
    2.43 + * @note This function forcibly sets the element size to the size of a pointer.
    2.44 + * Invoking this function on a non-empty map that already stores copies of
    2.45 + * objects is undefined.
    2.46 + *
    2.47 + * @param map the map
    2.48 + * @see cxMapStoreObjects()
    2.49 + */
    2.50 +__attribute__((__nonnull__))
    2.51 +static inline void cxMapStorePointers(CxMap *map) {
    2.52 +    map->store_pointers = true;
    2.53 +    map->itemsize = sizeof(void *);
    2.54 +}
    2.55 +
    2.56  
    2.57  /**
    2.58   * Deallocates the memory of the specified map.
    2.59 @@ -221,7 +261,8 @@
    2.60   *
    2.61   * @param map the map
    2.62   * @param key the key
    2.63 - * @return the removed value
    2.64 + * @return if this map is storing pointers, the removed value, \c NULL otherwise
    2.65 + * @see cxMapStorePointers()
    2.66   */
    2.67  __attribute__((__nonnull__, __warn_unused_result__))
    2.68  static inline void *cxMapRemove(

     3.1 --- a/src/hash_map.c	Mon Feb 20 19:55:42 2023 +0100
     3.2 +++ b/src/hash_map.c	Thu Feb 23 18:58:15 2023 +0100
     3.3 @@ -30,6 +30,17 @@
     3.4  #include "cx/hash_map.h"
     3.5  #include "cx/utils.h"
     3.6  
     3.7 +struct cx_hash_map_element_s {
     3.8 +    /** A pointer to the next element in the current bucket. */
     3.9 +    struct cx_hash_map_element_s *next;
    3.10 +
    3.11 +    /** The corresponding key. */
    3.12 +    CxHashKey key;
    3.13 +
    3.14 +    /** The value data. */
    3.15 +    char data[];
    3.16 +};
    3.17 +
    3.18  static void cx_hash_map_clear(struct cx_map_s *map) {
    3.19      struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    3.20      cx_for_n(i, hash_map->bucket_count) {
    3.21 @@ -89,17 +100,27 @@
    3.22      if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
    3.23          memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
    3.24          // overwrite existing element
    3.25 -        elm->data = value;
    3.26 +        if (map->store_pointers) {
    3.27 +            memcpy(elm->data, &value, sizeof(void *));
    3.28 +        } else {
    3.29 +            memcpy(elm->data, value, map->itemsize);
    3.30 +        }
    3.31      } else {
    3.32          // allocate new element
    3.33 -        struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
    3.34 +        struct cx_hash_map_element_s *e = cxMalloc(
    3.35 +                allocator,
    3.36 +                sizeof(struct cx_hash_map_element_s) + map->itemsize
    3.37 +        );
    3.38          if (e == NULL) {
    3.39              return -1;
    3.40          }
    3.41  
    3.42          // write the value
    3.43 -        // TODO: depending on future map features, we may want to copy here
    3.44 -        e->data = value;
    3.45 +        if (map->store_pointers) {
    3.46 +            memcpy(e->data, &value, sizeof(void *));
    3.47 +        } else {
    3.48 +            memcpy(e->data, value, map->itemsize);
    3.49 +        }
    3.50  
    3.51          // copy the key
    3.52          void *kd = cxMalloc(allocator, key.len);
    3.53 @@ -151,7 +172,7 @@
    3.54   * @param map the map
    3.55   * @param key the key to look up
    3.56   * @param remove flag indicating whether the looked up entry shall be removed
    3.57 - * @return the value corresponding to the key or \c NULL
    3.58 + * @return a pointer to the value corresponding to the key or \c NULL
    3.59   */
    3.60  static void *cx_hash_map_get_remove(
    3.61          CxMap *map,
    3.62 @@ -172,7 +193,12 @@
    3.63      while (elm && elm->key.hash <= hash) {
    3.64          if (elm->key.hash == hash && elm->key.len == key.len) {
    3.65              if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
    3.66 -                void *data = elm->data;
    3.67 +                void *data = NULL;
    3.68 +                if (map->store_pointers) {
    3.69 +                    data = *(void **) elm->data;
    3.70 +                } else if (!remove) {
    3.71 +                    data = elm->data;
    3.72 +                }
    3.73                  if (remove) {
    3.74                      cx_hash_map_unlink(hash_map, slot, prev, elm);
    3.75                  }
    3.76 @@ -215,9 +241,13 @@
    3.77  
    3.78  static void *cx_hash_map_iter_current_value(void const *it) {
    3.79      struct cx_iterator_s const *iter = it;
    3.80 +    struct cx_hash_map_s const *map = iter->src_handle;
    3.81      struct cx_hash_map_element_s *elm = iter->elem_handle;
    3.82 -    // TODO: return a pointer to data if this map is storing copies
    3.83 -    return elm->data;
    3.84 +    if (map->base.store_pointers) {
    3.85 +        return *(void **) elm->data;
    3.86 +    } else {
    3.87 +        return elm->data;
    3.88 +    }
    3.89  }
    3.90  
    3.91  static bool cx_hash_map_iter_valid(void const *it) {
    3.92 @@ -274,8 +304,11 @@
    3.93          iter->kv_data.value = NULL;
    3.94      } else {
    3.95          iter->kv_data.key = &elm->key;
    3.96 -        // TODO: pointer to data if this map is storing copies
    3.97 -        iter->kv_data.value = elm->data;
    3.98 +        if (map->base.store_pointers) {
    3.99 +            iter->kv_data.value = *(void **) elm->data;
   3.100 +        } else {
   3.101 +            iter->kv_data.value = elm->data;
   3.102 +        }
   3.103      }
   3.104  }
   3.105  
   3.106 @@ -311,8 +344,11 @@
   3.107          }
   3.108          iter.elem_handle = elm;
   3.109          iter.kv_data.key = &elm->key;
   3.110 -        // TODO: pointer to data if this map is storing copies
   3.111 -        iter.kv_data.value = elm->data;
   3.112 +        if (map->store_pointers) {
   3.113 +            iter.kv_data.value = *(void **) elm->data;
   3.114 +        } else {
   3.115 +            iter.kv_data.value = elm->data;
   3.116 +        }
   3.117      } else {
   3.118          iter.elem_handle = NULL;
   3.119          iter.kv_data.key = NULL;
   3.120 @@ -372,6 +408,7 @@
   3.121  
   3.122  CxMap *cxHashMapCreate(
   3.123          CxAllocator *allocator,
   3.124 +        size_t itemsize,
   3.125          size_t buckets
   3.126  ) {
   3.127      if (buckets == 0) {
   3.128 @@ -391,9 +428,11 @@
   3.129      }
   3.130  
   3.131      // initialize base members
   3.132 +    map->base.store_pointers = false;
   3.133      map->base.cl = &cx_hash_map_class;
   3.134      map->base.allocator = allocator;
   3.135      map->base.size = 0;
   3.136 +    map->base.itemsize = itemsize;
   3.137  
   3.138      return (CxMap *) map;
   3.139  }

     4.1 --- a/tests/test_map.cpp	Mon Feb 20 19:55:42 2023 +0100
     4.2 +++ b/tests/test_map.cpp	Thu Feb 23 18:58:15 2023 +0100
     4.3 @@ -28,6 +28,7 @@
     4.4  
     4.5  #include "cx/hash_map.h"
     4.6  #include "cx/utils.h"
     4.7 +#include "cx/string.h"
     4.8  #include "util_allocator.h"
     4.9  
    4.10  #include <gtest/gtest.h>
    4.11 @@ -114,14 +115,21 @@
    4.12  
    4.13  TEST(CxHashMap, Create) {
    4.14      CxTestingAllocator allocator;
    4.15 -    auto map = cxHashMapCreate(&allocator, 0);
    4.16 +    auto map = cxHashMapCreate(&allocator, 1, 0);
    4.17      auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
    4.18      EXPECT_GT(hmap->bucket_count, 0);
    4.19      cx_for_n(i, hmap->bucket_count) {
    4.20          EXPECT_EQ(hmap->buckets[i], nullptr);
    4.21      }
    4.22 +    EXPECT_EQ(map->itemsize, 1);
    4.23      EXPECT_EQ(map->size, 0);
    4.24      EXPECT_EQ(map->allocator, &allocator);
    4.25 +    EXPECT_FALSE(map->store_pointers);
    4.26 +    cxMapStorePointers(map);
    4.27 +    EXPECT_TRUE(map->store_pointers);
    4.28 +    EXPECT_EQ(map->itemsize, sizeof(void *));
    4.29 +    cxMapStoreObjects(map);
    4.30 +    EXPECT_FALSE(map->store_pointers);
    4.31  
    4.32      cxMapDestroy(map);
    4.33      EXPECT_TRUE(allocator.verify());
    4.34 @@ -130,7 +138,7 @@
    4.35  TEST(CxHashMap, BasicOperations) {
    4.36      // create the map
    4.37      CxTestingAllocator allocator;
    4.38 -    auto map = cxHashMapCreate(&allocator, 8);
    4.39 +    auto map = cxHashMapCreateForPointers(&allocator, 8);
    4.40  
    4.41      // create a reference map
    4.42      std::unordered_map<std::string, std::string> refmap;
    4.43 @@ -174,7 +182,7 @@
    4.44  
    4.45  TEST(CxHashMap, RemoveViaIterator) {
    4.46      CxTestingAllocator allocator;
    4.47 -    auto map = cxHashMapCreate(&allocator, 4);
    4.48 +    auto map = cxHashMapCreateForPointers(&allocator, 4);
    4.49  
    4.50      cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
    4.51      cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
    4.52 @@ -203,7 +211,7 @@
    4.53  
    4.54  TEST(CxHashMap, RehashNotRequired) {
    4.55      CxTestingAllocator allocator;
    4.56 -    auto map = cxHashMapCreate(&allocator, 8);
    4.57 +    auto map = cxHashMapCreateForPointers(&allocator, 8);
    4.58  
    4.59      cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
    4.60      cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
    4.61 @@ -223,7 +231,7 @@
    4.62  
    4.63  TEST(CxHashMap, Rehash) {
    4.64      CxTestingAllocator allocator;
    4.65 -    auto map = cxHashMapCreate(&allocator, 8);
    4.66 +    auto map = cxHashMapCreateForPointers(&allocator, 8);
    4.67  
    4.68      cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
    4.69      cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
    4.70 @@ -252,7 +260,7 @@
    4.71  
    4.72  TEST(CxHashMap, Clear) {
    4.73      CxTestingAllocator allocator;
    4.74 -    auto map = cxHashMapCreate(&allocator, 0);
    4.75 +    auto map = cxHashMapCreateForPointers(&allocator, 0);
    4.76      
    4.77      cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
    4.78      cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
    4.79 @@ -269,4 +277,49 @@
    4.80  
    4.81      cxMapDestroy(map);
    4.82      EXPECT_TRUE(allocator.verify());
    4.83 -}
    4.84 \ No newline at end of file
    4.85 +}
    4.86 +
    4.87 +TEST(CxHashMap, StoreUcxStrings) {
    4.88 +    // create the map
    4.89 +    CxTestingAllocator allocator;
    4.90 +    auto map = cxHashMapCreate(&allocator, sizeof(cxstring), 8);
    4.91 +
    4.92 +    // define some strings
    4.93 +    cxstring s1 = CX_STR("this");
    4.94 +    cxstring s2 = CX_STR("is");
    4.95 +    cxstring s3 = CX_STR("a");
    4.96 +    cxstring s4 = CX_STR("test");
    4.97 +    cxstring s5 = CX_STR("setup");
    4.98 +
    4.99 +    // put them into the map
   4.100 +    cxMapPut(map, cx_hash_key_str("s1"), &s1);
   4.101 +    cxMapPut(map, cx_hash_key_str("s2"), &s2);
   4.102 +    cxMapPut(map, cx_hash_key_str("s3"), &s3);
   4.103 +    cxMapPut(map, cx_hash_key_str("s4"), &s4);
   4.104 +
   4.105 +    // overwrite a value
   4.106 +    cxMapPut(map, cx_hash_key_str("s1"), &s5);
   4.107 +
   4.108 +    // look up a string
   4.109 +    auto s3p = reinterpret_cast<cxstring *>(cxMapGet(map, cx_hash_key_str("s3")));
   4.110 +    EXPECT_EQ(s3p->length, s3.length);
   4.111 +    EXPECT_EQ(s3p->ptr, s3.ptr);
   4.112 +    EXPECT_NE(s3p, &s3);
   4.113 +
   4.114 +    // remove a string
   4.115 +    auto r = cxMapRemove(map, cx_hash_key_str("s2"));
   4.116 +    EXPECT_EQ(r, nullptr);
   4.117 +
   4.118 +    // iterate
   4.119 +    auto ref = std::vector{s5.ptr, s3.ptr, s4.ptr};
   4.120 +    auto iter = cxMapIteratorValues(map);
   4.121 +    cx_foreach(cxstring*, s, iter) {
   4.122 +        auto found = std::find(ref.begin(), ref.end(), s->ptr);
   4.123 +        ASSERT_NE(found, ref.end());
   4.124 +        ref.erase(found);
   4.125 +    }
   4.126 +    EXPECT_EQ(ref.size(), 0);
   4.127 +
   4.128 +    cxMapDestroy(map);
   4.129 +    EXPECT_TRUE(allocator.verify());
   4.130 +}