# HG changeset patch # User Mike Becker # Date 1677175095 -3600 # Node ID 56c62780582e96521f401a1bea629e27c76fe98d # Parent 3eeadf666d6b1c0a206463c831b824bfa46170c6 make hashmap store objects instead of pointers by default - fixes #239 diff -r 3eeadf666d6b -r 56c62780582e src/cx/hash_map.h --- 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 diff -r 3eeadf666d6b -r 56c62780582e src/cx/map.h --- 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( diff -r 3eeadf666d6b -r 56c62780582e src/hash_map.c --- 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; } diff -r 3eeadf666d6b -r 56c62780582e tests/test_map.cpp --- 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 @@ -114,14 +115,21 @@ TEST(CxHashMap, Create) { CxTestingAllocator allocator; - auto map = cxHashMapCreate(&allocator, 0); + auto map = cxHashMapCreate(&allocator, 1, 0); auto hmap = reinterpret_cast(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 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(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()); +}