Mercurial > hg > ucx / changeset

--- a/src/cx/hash_map.h	Mon Feb 20 19:55:42 2023 +0100
+++ b/src/cx/hash_map.h	Thu Feb 23 18:58:15 2023 +0100
@@ -44,16 +44,7 @@
 #endif
 
 /** Internal structure for an element of a hash map. */
-struct cx_hash_map_element_s {
-    /** The value data. */
-    void *data;
-
-    /** A pointer to the next element in the current bucket. */
-    struct cx_hash_map_element_s *next;
-
-    /** The corresponding key. */
-    CxHashKey key;
-};
+struct cx_hash_map_element_s;
 
 /**
  * Internal structure for a hash map.
@@ -84,16 +75,39 @@
  * In other words, when the iterator is finished, \c index==size .
  *
  * @param allocator the allocator to use
+ * @param itemsize the size of one element
  * @param buckets the initial number of buckets in this hash map
  * @return a pointer to the new hash map
  */
 __attribute__((__nonnull__, __warn_unused_result__))
 CxMap *cxHashMapCreate(
         CxAllocator *allocator,
+        size_t itemsize,
         size_t buckets
 );
 
 /**
+ * Convenience function for creating a hash map that is storing pointers.
+ *
+ * If \p buckets is zero, an implementation defined default will be used.
+ *
+ * @param allocator the allocator to use
+ * @param buckets the initial number of buckets in this hash map
+ * @return a pointer to the new hash map
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMap *cxHashMapCreateForPointers(
+        CxAllocator *allocator,
+        size_t buckets
+) {
+    CxMap *map = cxHashMapCreate(allocator, sizeof(void *), buckets);
+    if (map != NULL) {
+        map->store_pointers = true;
+    }
+    return map;
+}
+
+/**
  * Increases the number of buckets, if necessary.
  *
  * The load threshold is \c 0.75*buckets. If the element count exceeds the load

--- a/src/cx/map.h	Mon Feb 20 19:55:42 2023 +0100
+++ b/src/cx/map.h	Thu Feb 23 18:58:15 2023 +0100
@@ -63,7 +63,15 @@
     CxAllocator *allocator;
     /** The number of elements currently stored. */
     size_t size;
-    // TODO: elemsize + a flag if values shall be copied to the map
+    /**
+     * The size of an element.
+     */
+    size_t itemsize;
+    /**
+     * True, if this map shall store pointers instead
+     * of copies of objects.
+     */
+    bool store_pointers;
 };
 
 /**
@@ -161,6 +169,38 @@
     void *value;
 };
 
+/**
+ * Advises the map to store copies of the objects (default mode of operation).
+ *
+ * Retrieving objects from this map will yield pointers to the copies stored
+ * within this list.
+ *
+ * @param map the map
+ * @see cxMapStorePointers()
+ */
+__attribute__((__nonnull__))
+static inline void cxMapStoreObjects(CxMap *map) {
+    map->store_pointers = false;
+}
+
+/**
+ * Advises the map to only store pointers to the objects.
+ *
+ * Retrieving objects from this list will yield the original pointers stored.
+ *
+ * @note This function forcibly sets the element size to the size of a pointer.
+ * Invoking this function on a non-empty map that already stores copies of
+ * objects is undefined.
+ *
+ * @param map the map
+ * @see cxMapStoreObjects()
+ */
+__attribute__((__nonnull__))
+static inline void cxMapStorePointers(CxMap *map) {
+    map->store_pointers = true;
+    map->itemsize = sizeof(void *);
+}
+
 
 /**
  * Deallocates the memory of the specified map.
@@ -221,7 +261,8 @@
  *
  * @param map the map
  * @param key the key
- * @return the removed value
+ * @return if this map is storing pointers, the removed value, \c NULL otherwise
+ * @see cxMapStorePointers()
  */
 __attribute__((__nonnull__, __warn_unused_result__))
 static inline void *cxMapRemove(

--- a/src/hash_map.c	Mon Feb 20 19:55:42 2023 +0100
+++ b/src/hash_map.c	Thu Feb 23 18:58:15 2023 +0100
@@ -30,6 +30,17 @@
 #include "cx/hash_map.h"
 #include "cx/utils.h"
 
+struct cx_hash_map_element_s {
+    /** A pointer to the next element in the current bucket. */
+    struct cx_hash_map_element_s *next;
+
+    /** The corresponding key. */
+    CxHashKey key;
+
+    /** The value data. */
+    char data[];
+};
+
 static void cx_hash_map_clear(struct cx_map_s *map) {
     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
     cx_for_n(i, hash_map->bucket_count) {
@@ -89,17 +100,27 @@
     if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
         memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
         // overwrite existing element
-        elm->data = value;
+        if (map->store_pointers) {
+            memcpy(elm->data, &value, sizeof(void *));
+        } else {
+            memcpy(elm->data, value, map->itemsize);
+        }
     } else {
         // allocate new element
-        struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
+        struct cx_hash_map_element_s *e = cxMalloc(
+                allocator,
+                sizeof(struct cx_hash_map_element_s) + map->itemsize
+        );
         if (e == NULL) {
             return -1;
         }
 
         // write the value
-        // TODO: depending on future map features, we may want to copy here
-        e->data = value;
+        if (map->store_pointers) {
+            memcpy(e->data, &value, sizeof(void *));
+        } else {
+            memcpy(e->data, value, map->itemsize);
+        }
 
         // copy the key
         void *kd = cxMalloc(allocator, key.len);
@@ -151,7 +172,7 @@
  * @param map the map
  * @param key the key to look up
  * @param remove flag indicating whether the looked up entry shall be removed
- * @return the value corresponding to the key or \c NULL
+ * @return a pointer to the value corresponding to the key or \c NULL
  */
 static void *cx_hash_map_get_remove(
         CxMap *map,
@@ -172,7 +193,12 @@
     while (elm && elm->key.hash <= hash) {
         if (elm->key.hash == hash && elm->key.len == key.len) {
             if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
-                void *data = elm->data;
+                void *data = NULL;
+                if (map->store_pointers) {
+                    data = *(void **) elm->data;
+                } else if (!remove) {
+                    data = elm->data;
+                }
                 if (remove) {
                     cx_hash_map_unlink(hash_map, slot, prev, elm);
                 }
@@ -215,9 +241,13 @@
 
 static void *cx_hash_map_iter_current_value(void const *it) {
     struct cx_iterator_s const *iter = it;
+    struct cx_hash_map_s const *map = iter->src_handle;
     struct cx_hash_map_element_s *elm = iter->elem_handle;
-    // TODO: return a pointer to data if this map is storing copies
-    return elm->data;
+    if (map->base.store_pointers) {
+        return *(void **) elm->data;
+    } else {
+        return elm->data;
+    }
 }
 
 static bool cx_hash_map_iter_valid(void const *it) {
@@ -274,8 +304,11 @@
         iter->kv_data.value = NULL;
     } else {
         iter->kv_data.key = &elm->key;
-        // TODO: pointer to data if this map is storing copies
-        iter->kv_data.value = elm->data;
+        if (map->base.store_pointers) {
+            iter->kv_data.value = *(void **) elm->data;
+        } else {
+            iter->kv_data.value = elm->data;
+        }
     }
 }
 
@@ -311,8 +344,11 @@
         }
         iter.elem_handle = elm;
         iter.kv_data.key = &elm->key;
-        // TODO: pointer to data if this map is storing copies
-        iter.kv_data.value = elm->data;
+        if (map->store_pointers) {
+            iter.kv_data.value = *(void **) elm->data;
+        } else {
+            iter.kv_data.value = elm->data;
+        }
     } else {
         iter.elem_handle = NULL;
         iter.kv_data.key = NULL;
@@ -372,6 +408,7 @@
 
 CxMap *cxHashMapCreate(
         CxAllocator *allocator,
+        size_t itemsize,
         size_t buckets
 ) {
     if (buckets == 0) {
@@ -391,9 +428,11 @@
     }
 
     // initialize base members
+    map->base.store_pointers = false;
     map->base.cl = &cx_hash_map_class;
     map->base.allocator = allocator;
     map->base.size = 0;
+    map->base.itemsize = itemsize;
 
     return (CxMap *) map;
 }

--- a/tests/test_map.cpp	Mon Feb 20 19:55:42 2023 +0100
+++ b/tests/test_map.cpp	Thu Feb 23 18:58:15 2023 +0100
@@ -28,6 +28,7 @@
 
 #include "cx/hash_map.h"
 #include "cx/utils.h"
+#include "cx/string.h"
 #include "util_allocator.h"
 
 #include <gtest/gtest.h>
@@ -114,14 +115,21 @@
 
 TEST(CxHashMap, Create) {
     CxTestingAllocator allocator;
-    auto map = cxHashMapCreate(&allocator, 0);
+    auto map = cxHashMapCreate(&allocator, 1, 0);
     auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
     EXPECT_GT(hmap->bucket_count, 0);
     cx_for_n(i, hmap->bucket_count) {
         EXPECT_EQ(hmap->buckets[i], nullptr);
     }
+    EXPECT_EQ(map->itemsize, 1);
     EXPECT_EQ(map->size, 0);
     EXPECT_EQ(map->allocator, &allocator);
+    EXPECT_FALSE(map->store_pointers);
+    cxMapStorePointers(map);
+    EXPECT_TRUE(map->store_pointers);
+    EXPECT_EQ(map->itemsize, sizeof(void *));
+    cxMapStoreObjects(map);
+    EXPECT_FALSE(map->store_pointers);
 
     cxMapDestroy(map);
     EXPECT_TRUE(allocator.verify());
@@ -130,7 +138,7 @@
 TEST(CxHashMap, BasicOperations) {
     // create the map
     CxTestingAllocator allocator;
-    auto map = cxHashMapCreate(&allocator, 8);
+    auto map = cxHashMapCreateForPointers(&allocator, 8);
 
     // create a reference map
     std::unordered_map<std::string, std::string> refmap;
@@ -174,7 +182,7 @@
 
 TEST(CxHashMap, RemoveViaIterator) {
     CxTestingAllocator allocator;
-    auto map = cxHashMapCreate(&allocator, 4);
+    auto map = cxHashMapCreateForPointers(&allocator, 4);
 
     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
@@ -203,7 +211,7 @@
 
 TEST(CxHashMap, RehashNotRequired) {
     CxTestingAllocator allocator;
-    auto map = cxHashMapCreate(&allocator, 8);
+    auto map = cxHashMapCreateForPointers(&allocator, 8);
 
     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
@@ -223,7 +231,7 @@
 
 TEST(CxHashMap, Rehash) {
     CxTestingAllocator allocator;
-    auto map = cxHashMapCreate(&allocator, 8);
+    auto map = cxHashMapCreateForPointers(&allocator, 8);
 
     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
@@ -252,7 +260,7 @@
 
 TEST(CxHashMap, Clear) {
     CxTestingAllocator allocator;
-    auto map = cxHashMapCreate(&allocator, 0);
+    auto map = cxHashMapCreateForPointers(&allocator, 0);
     
     cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
     cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
@@ -269,4 +277,49 @@
 
     cxMapDestroy(map);
     EXPECT_TRUE(allocator.verify());
-}
\ No newline at end of file
+}
+
+TEST(CxHashMap, StoreUcxStrings) {
+    // create the map
+    CxTestingAllocator allocator;
+    auto map = cxHashMapCreate(&allocator, sizeof(cxstring), 8);
+
+    // define some strings
+    cxstring s1 = CX_STR("this");
+    cxstring s2 = CX_STR("is");
+    cxstring s3 = CX_STR("a");
+    cxstring s4 = CX_STR("test");
+    cxstring s5 = CX_STR("setup");
+
+    // put them into the map
+    cxMapPut(map, cx_hash_key_str("s1"), &s1);
+    cxMapPut(map, cx_hash_key_str("s2"), &s2);
+    cxMapPut(map, cx_hash_key_str("s3"), &s3);
+    cxMapPut(map, cx_hash_key_str("s4"), &s4);
+
+    // overwrite a value
+    cxMapPut(map, cx_hash_key_str("s1"), &s5);
+
+    // look up a string
+    auto s3p = reinterpret_cast<cxstring *>(cxMapGet(map, cx_hash_key_str("s3")));
+    EXPECT_EQ(s3p->length, s3.length);
+    EXPECT_EQ(s3p->ptr, s3.ptr);
+    EXPECT_NE(s3p, &s3);
+
+    // remove a string
+    auto r = cxMapRemove(map, cx_hash_key_str("s2"));
+    EXPECT_EQ(r, nullptr);
+
+    // iterate
+    auto ref = std::vector{s5.ptr, s3.ptr, s4.ptr};
+    auto iter = cxMapIteratorValues(map);
+    cx_foreach(cxstring*, s, iter) {
+        auto found = std::find(ref.begin(), ref.end(), s->ptr);
+        ASSERT_NE(found, ref.end());
+        ref.erase(found);
+    }
+    EXPECT_EQ(ref.size(), 0);
+
+    cxMapDestroy(map);
+    EXPECT_TRUE(allocator.verify());
+}