Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/hash_map.h	Fri May 27 14:14:55 2022 +0200
     1.2 +++ b/src/cx/hash_map.h	Fri May 27 17:40:27 2022 +0200
     1.3 @@ -108,41 +108,23 @@
     1.4  /**
     1.5   * Increases the number of buckets, if necessary.
     1.6   *
     1.7 - * The load value is \c loadFactor*buckets. If the element count exceeds the load
     1.8 - * value, the map needs to be rehashed. Otherwise, no action is performed and
     1.9 + * The load threshold is \c 0.75*buckets. If the element count exceeds the load
    1.10 + * threshold, the map will be rehashed. Otherwise, no action is performed and
    1.11   * this function simply returns 0.
    1.12   *
    1.13   * The rehashing process ensures, that the number of buckets is at least
    1.14 - * \p bucketFactor times the number of stored items. So there is enough room for additional
    1.15 + * 2.5 times the element count. So there is enough room for additional
    1.16   * elements without the need of another soon rehashing.
    1.17   *
    1.18 - * You can use this function after filling a map to dramatically increase access performance.
    1.19 + * You can use this function after filling a map to increase access performance.
    1.20   *
    1.21   * @note If the specified map is not a hash map, the behavior is undefined.
    1.22   *
    1.23   * @param map the map to rehash
    1.24 - * @param loadFactor a percentage threshold for the load of the map
    1.25 - * @param bucketFactor a factor for the number of buckets that shall be available after rehashing
    1.26   * @return zero on success, non-zero if a memory allocation error occurred
    1.27   */
    1.28  __attribute__((__nonnull__))
    1.29 -int cxMapRehash2(
    1.30 -        CxMap *map,
    1.31 -        float loadFactor,
    1.32 -        float bucketFactor
    1.33 -);
    1.34 -
    1.35 -/**
    1.36 - * Rehashes the map with load factor 0.75 and bucket factor 2.5.
    1.37 - *
    1.38 - * @param map the map to rehash
    1.39 - * @return zero on success, non-zero if a memory allocation error occurred
    1.40 - * @see cxMapRehash2()
    1.41 - */
    1.42 -__attribute__((__nonnull__))
    1.43 -static inline int cxMapRehash(CxMap *map) {
    1.44 -    return cxMapRehash2(map, 0.75f, 2.5f);
    1.45 -}
    1.46 +int cxMapRehash(CxMap *map);
    1.47  
    1.48  
    1.49  #ifdef __cplusplus

     2.1 --- a/src/hash_map.c	Fri May 27 14:14:55 2022 +0200
     2.2 +++ b/src/hash_map.c	Fri May 27 17:40:27 2022 +0200
     2.3 @@ -396,3 +396,52 @@
     2.4  
     2.5      return (CxMap *) map;
     2.6  }
     2.7 +
     2.8 +int cxMapRehash(CxMap *map) {
     2.9 +    struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    2.10 +    if (map->size > ((hash_map->bucket_count * 3) >> 2)) {
    2.11 +
    2.12 +        size_t new_bucket_count = (map->size * 5) >> 1;
    2.13 +        struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator,
    2.14 +                                                              new_bucket_count, sizeof(struct cx_hash_map_element_s *));
    2.15 +
    2.16 +        if (new_buckets == NULL) {
    2.17 +            return 1;
    2.18 +        }
    2.19 +
    2.20 +        // iterate through the elements and assign them to their new slots
    2.21 +        cx_for_n(slot, hash_map->bucket_count) {
    2.22 +            struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
    2.23 +            while (elm != NULL) {
    2.24 +                struct cx_hash_map_element_s *next = elm->next;
    2.25 +                size_t new_slot = elm->key.hash % new_bucket_count;
    2.26 +
    2.27 +                // find position where to insert
    2.28 +                struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];
    2.29 +                struct cx_hash_map_element_s *bucket_prev = NULL;
    2.30 +                while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) {
    2.31 +                    bucket_prev = bucket_next;
    2.32 +                    bucket_next = bucket_next->next;
    2.33 +                }
    2.34 +
    2.35 +                // insert
    2.36 +                if (bucket_prev == NULL) {
    2.37 +                    elm->next = new_buckets[new_slot];
    2.38 +                    new_buckets[new_slot] = elm;
    2.39 +                } else {
    2.40 +                    bucket_prev->next = elm;
    2.41 +                    elm->next = bucket_next;
    2.42 +                }
    2.43 +
    2.44 +                // advance
    2.45 +                elm = next;
    2.46 +            }
    2.47 +        }
    2.48 +
    2.49 +        // assign result to the map
    2.50 +        hash_map->bucket_count = new_bucket_count;
    2.51 +        cxFree(map->allocator, hash_map->buckets);
    2.52 +        hash_map->buckets = new_buckets;
    2.53 +    }
    2.54 +    return 0;
    2.55 +}

     3.1 --- a/test/test_map.cpp	Fri May 27 14:14:55 2022 +0200
     3.2 +++ b/test/test_map.cpp	Fri May 27 17:40:27 2022 +0200
     3.3 @@ -200,3 +200,52 @@
     3.4      cxMapDestroy(map);
     3.5      EXPECT_TRUE(allocator.verify());
     3.6  }
     3.7 +
     3.8 +TEST(CxHashMap, RehashNotRequired) {
     3.9 +    CxTestingAllocator allocator;
    3.10 +    auto map = cxHashMapCreate(&allocator, 8);
    3.11 +
    3.12 +    cxMapPut(map, cxMapKeyStr("key 1"), (void *) "val 1");
    3.13 +    cxMapPut(map, cxMapKeyStr("key 2"), (void *) "val 2");
    3.14 +    cxMapPut(map, cxMapKeyStr("key 3"), (void *) "val 3");
    3.15 +    cxMapPut(map, cxMapKeyStr("key 4"), (void *) "val 4");
    3.16 +    cxMapPut(map, cxMapKeyStr("key 5"), (void *) "val 5");
    3.17 +    cxMapPut(map, cxMapKeyStr("key 6"), (void *) "val 6");
    3.18 +
    3.19 +    // 6/8 does not exceed 0.75, therefore the function should not rehash
    3.20 +    int result = cxMapRehash(map);
    3.21 +    EXPECT_EQ(result, 0);
    3.22 +    EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
    3.23 +
    3.24 +    cxMapDestroy(map);
    3.25 +    EXPECT_TRUE(allocator.verify());
    3.26 +}
    3.27 +
    3.28 +TEST(CxHashMap, Rehash) {
    3.29 +    CxTestingAllocator allocator;
    3.30 +    auto map = cxHashMapCreate(&allocator, 8);
    3.31 +
    3.32 +    cxMapPut(map, cxMapKeyStr("key 1"), (void *) "val 1");
    3.33 +    cxMapPut(map, cxMapKeyStr("key 2"), (void *) "val 2");
    3.34 +    cxMapPut(map, cxMapKeyStr("key 3"), (void *) "val 3");
    3.35 +    cxMapPut(map, cxMapKeyStr("key 4"), (void *) "val 4");
    3.36 +    cxMapPut(map, cxMapKeyStr("key 5"), (void *) "val 5");
    3.37 +    cxMapPut(map, cxMapKeyStr("key 6"), (void *) "val 6");
    3.38 +    cxMapPut(map, cxMapKeyStr("key 7"), (void *) "val 7");
    3.39 +
    3.40 +    int result = cxMapRehash(map);
    3.41 +    EXPECT_EQ(result, 0);
    3.42 +    EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);
    3.43 +    EXPECT_EQ(map->size, 7);
    3.44 +
    3.45 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 1")), "val 1"), 0);
    3.46 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 2")), "val 2"), 0);
    3.47 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 3")), "val 3"), 0);
    3.48 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 4")), "val 4"), 0);
    3.49 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 5")), "val 5"), 0);
    3.50 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 6")), "val 6"), 0);
    3.51 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 7")), "val 7"), 0);
    3.52 +
    3.53 +    cxMapDestroy(map);
    3.54 +    EXPECT_TRUE(allocator.verify());
    3.55 +}
    3.56 \ No newline at end of file