PengZheng commented on code in PR #470:
URL: https://github.com/apache/celix/pull/470#discussion_r1383248138
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -237,11 +235,12 @@ static void celix_hashMap_addEntry(celix_hash_map_t* map,
unsigned int hash, con
newEntry->next = entry;
map->buckets[bucketIndex] = newEntry;
if (map->size++ >= celix_hashMap_threshold(map)) {
- celix_hashMap_resize(map, 2 * map->bucketsSize);
+ return celix_hashMap_resize(map, 2 * map->bucketsSize);
Review Comment:
if `newEntry` is added but `celix_hashMap_resize` failed, should it return
SUCCESS or error code?
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -599,33 +675,49 @@ bool celix_longHashMapIterator_isEnd(const
celix_long_hash_map_iterator_t* iter)
void celix_stringHashMapIterator_next(celix_string_hash_map_iterator_t* iter) {
const celix_hash_map_t* map = iter->_internal[0];
celix_hash_map_entry_t *entry = iter->_internal[1];
+ iter->index += 1;
entry = celix_hashMap_nextEntry(map, entry);
- if (entry != NULL) {
+ if (entry) {
iter->_internal[1] = entry;
- iter->index += 1;
iter->key = entry->key.strKey;
iter->value = entry->value;
} else {
- memset(iter, 0, sizeof(*iter));
- iter->_internal[0] = (void*)map;
+ iter->_internal[1] = NULL;
+ iter->key = NULL;
Review Comment:
In `celix_stringHashMap_end`, `key` is set to "".
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -339,21 +327,27 @@ static bool celix_hashMap_remove(celix_hash_map_t* map,
const char* strKey, long
visit = visit->next;
}
if (removedEntry != NULL) {
+ char* removedKey = NULL;
+ if (map->keyType == CELIX_HASH_MAP_STRING_KEY) {
+ removedKey = (char*)removedEntry->key.strKey;
+ }
celix_hashMap_destroyRemovedEntry(map, removedEntry);
+ if (removedKey) {
+ celix_hashMap_destroyRemovedKey(map, removedKey);
+ }
return true;
}
return false;
}
-static void celix_hashMap_init(
+celix_status_t celix_hashMap_init(
celix_hash_map_t* map,
celix_hash_map_key_type_e keyType,
unsigned int initialCapacity,
double loadFactor,
unsigned int (*hashKeyFn)(const celix_hash_map_key_t*),
bool (*equalsKeyFn)(const celix_hash_map_key_t*, const
celix_hash_map_key_t*)) {
map->loadFactor = loadFactor;
Review Comment:
`loadFactor`, which is always less than 1, does not apply to separate
chaining hash table. It does apply to linear probing and double hashing
implementation, both of which have nothing to do with our implementation.
For separate chaining implementation, it is normal for a list to contain
about 5 or 10 keys. Our resize implementation will lead to too many
unnecessary resize.
For reference, I quote an exercise in Robert Sedgewick's Algorithms in C++:
> 14.45 Implement a version of Program 14.7 for separate chaining that
increases the table size by a factor of 10 each time the average list length is
equal to 10.
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -237,11 +235,12 @@ static void celix_hashMap_addEntry(celix_hash_map_t* map,
unsigned int hash, con
newEntry->next = entry;
map->buckets[bucketIndex] = newEntry;
if (map->size++ >= celix_hashMap_threshold(map)) {
- celix_hashMap_resize(map, 2 * map->bucketsSize);
+ return celix_hashMap_resize(map, 2 * map->bucketsSize);
Review Comment:
For weakly stored key, it will make huge difference.
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -599,33 +675,49 @@ bool celix_longHashMapIterator_isEnd(const
celix_long_hash_map_iterator_t* iter)
void celix_stringHashMapIterator_next(celix_string_hash_map_iterator_t* iter) {
const celix_hash_map_t* map = iter->_internal[0];
celix_hash_map_entry_t *entry = iter->_internal[1];
+ iter->index += 1;
Review Comment:
`iter.index` will be larger than `map->genericMap.size` even if it has
reached the end. Does this break some invariant?
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -562,6 +591,33 @@ void celix_longHashMap_clear(celix_long_hash_map_t* map) {
celix_hashMap_clear(&map->genericMap);
}
+static bool celix_hashMap_equals(const celix_hash_map_t* map1, const
celix_hash_map_t* map2) {
+ if (map1 == NULL && map2 == NULL) {
+ return true;
+ }
+ if (map1 == NULL || map2 == NULL) {
+ return false;
+ }
+ if (map1->size != map2->size) {
+ return false;
+ }
+ for (celix_hash_map_entry_t* entry = celix_hashMap_firstEntry(map1); entry
!= NULL; entry = celix_hashMap_nextEntry(map1, entry)) {
+ void* value = celix_hashMap_get(map2, entry->key.strKey,
entry->key.longKey);
+ if (value == NULL || memcmp(&entry->value, value,
sizeof(entry->value)) != 0) {
Review Comment:
This assumes `sizeof(void*) >= sizeof(double)`, which is not true on ARM32.
`celix_hashMap_get` should return `celix_hash_map_entry_t` instead.
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -256,57 +255,46 @@ static bool celix_hashMap_putValue(celix_hash_map_t* map,
const char* strKey, lo
if (replacedValueOut != NULL) {
*replacedValueOut = entry->value;
}
+ celix_hashMap_callRemovedCallback(map, entry);
memcpy(&entry->value, value, sizeof(*value));
- return true;
+ return CELIX_SUCCESS;
}
}
- celix_hashMap_addEntry(map, hash, &key, value, index);
- if (replacedValueOut != NULL) {
+ celix_status_t status = celix_hashMap_addEntry(map, hash, &key, value,
index);
+ if (status == CELIX_SUCCESS && replacedValueOut != NULL) {
memset(replacedValueOut, 0, sizeof(*replacedValueOut));
}
- return false;
+ return status;
}
-static void* celix_hashMap_put(celix_hash_map_t* map, const char* strKey, long
longKey, void* v) {
+static celix_status_t celix_hashMap_put(celix_hash_map_t* map, const char*
strKey, long longKey, void* v, void** previousValueOut) {
Review Comment:
`previousValueOut` is unused. Shall we remove it?
##########
libs/utils/src/celix_hash_map.c:
##########
@@ -94,11 +83,11 @@ static unsigned int celix_longHashMap_hash(const
celix_hash_map_key_t* key) {
return key->longKey ^ (key->longKey >> (sizeof(key->longKey)*8/2));
Review Comment:
Suppose that `sizeof(long)==8`, when the table size is very small (like 16),
only 8 bits of `longKey` (the lower 4 bits of the upper and lower 32bit) will
affect the resulting hash value. This is a bad hash functino.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscr...@celix.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
