dav: comparison ucx/hash

-:bbe2925eb590
+:83fdf679df99
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 #include "cx/hash_map.h"
-#include "cx/utils.h"
 #include <string.h>
 #include <assert.h>
+#include <errno.h>
 struct cx_hash_map_element_s {
 /** A pointer to the next element in the current bucket. */
 struct cx_hash_map_element_s *next;
 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) {
+for (size_t i = 0; i < hash_map->bucket_count; i++) {
 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
 if (elem != NULL) {
 do {
 struct cx_hash_map_element_s *next = elem->next;
 // invoke the destructor
 CxMap *map,
 CxHashKey key,
 void *value
 ) {
 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
-CxAllocator const *allocator = map->collection.allocator;
+const CxAllocator *allocator = map->collection.allocator;
 unsigned hash = key.hash;
 if (hash == 0) {
 cx_hash_murmur(&key);
 hash = key.hash;
 // allocate new element
 struct cx_hash_map_element_s *e = cxMalloc(
 allocator,
 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size
 );
-if (e == NULL) {
+if (e == NULL) return -1;
-return -1;
-}
 // write the value
 if (map->collection.store_pointer) {
 memcpy(e->data, &value, sizeof(void *));
 } else {
 memcpy(e->data, value, map->collection.elem_size);
 }
 // copy the key
 void *kd = cxMalloc(allocator, key.len);
-if (kd == NULL) {
+if (kd == NULL) return -1;
-return -1;
-}
 memcpy(kd, key.data, key.len);
 e->key.data = kd;
 e->key.len = key.len;
 e->key.hash = hash;
 }
 /**
 * Helper function to avoid code duplication.
 *
+* If @p remove is true, and @p targetbuf is @c NULL, the element
+* will be destroyed when found.
+*
+* If @p remove is true, and @p targetbuf is set, the element will
+* be copied to that buffer and no destructor function is called.
+*
+* If @p remove is false, @p targetbuf must not be non-null and
+* either the pointer, when the map is storing pointers, is copied
+* to the target buffer, or a pointer to the stored object will
+* be copied to the target buffer.
+*
 * @param map the map
 * @param key the key to look up
+* @param targetbuf see description
 * @param remove flag indicating whether the looked up entry shall be removed
-* @param destroy flag indicating whether the destructor shall be invoked
+* @return zero, if the key was found, non-zero otherwise
-* @return a pointer to the value corresponding to the key or \c NULL
 */
-static void *cx_hash_map_get_remove(
+static int cx_hash_map_get_remove(
 CxMap *map,
 CxHashKey key,
-bool remove,
+void *targetbuf,
-bool destroy
+bool remove
 ) {
 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
 unsigned hash = key.hash;
 if (hash == 0) {
 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
 struct cx_hash_map_element_s *prev = NULL;
 while (elm && elm->key.hash <= hash) {
 if (elm->key.hash == hash && elm->key.len == key.len) {
 if (memcmp(elm->key.data, key.data, key.len) == 0) {
-void *data = NULL;
+if (remove) {
-if (destroy) {
+if (targetbuf == NULL) {
 cx_invoke_destructor(map, elm->data);
+} else {
+memcpy(targetbuf, elm->data, map->collection.elem_size);
+}
+cx_hash_map_unlink(hash_map, slot, prev, elm);
 } else {
+assert(targetbuf != NULL);
+void *data = NULL;
 if (map->collection.store_pointer) {
 data = *(void **) elm->data;
 } else {
 data = elm->data;
 }
+memcpy(targetbuf, &data, sizeof(void *));
 }
-if (remove) {
+return 0;
-cx_hash_map_unlink(hash_map, slot, prev, elm);
-}
-return data;
 }
 }
 prev = elm;
 elm = prev->next;
 }
-return NULL;
+return 1;
 }
 static void *cx_hash_map_get(
-CxMap const *map,
+const CxMap *map,
 CxHashKey key
 ) {
 // we can safely cast, because we know the map stays untouched
-return cx_hash_map_get_remove((CxMap *) map, key, false, false);
+void *ptr = NULL;
-}
+int found = cx_hash_map_get_remove((CxMap *) map, key, &ptr, false);
+return found == 0 ? ptr : NULL;
-static void *cx_hash_map_remove(
+}
+static int cx_hash_map_remove(
 CxMap *map,
 CxHashKey key,
-bool destroy
+void *targetbuf
 ) {
-return cx_hash_map_get_remove(map, key, true, destroy);
+return cx_hash_map_get_remove(map, key, targetbuf, true);
 }
-static void *cx_hash_map_iter_current_entry(void const *it) {
+static void *cx_hash_map_iter_current_entry(const void *it) {
-struct cx_iterator_s const *iter = it;
+const struct cx_iterator_s *iter = it;
 // struct has to have a compatible signature
 return (struct cx_map_entry_s *) &(iter->kv_data);
 }
-static void *cx_hash_map_iter_current_key(void const *it) {
+static void *cx_hash_map_iter_current_key(const void *it) {
-struct cx_iterator_s const *iter = it;
+const struct cx_iterator_s *iter = it;
 struct cx_hash_map_element_s *elm = iter->elem_handle;
 return &elm->key;
 }
-static void *cx_hash_map_iter_current_value(void const *it) {
+static void *cx_hash_map_iter_current_value(const void *it) {
-struct cx_iterator_s const *iter = it;
+const struct cx_iterator_s *iter = it;
-struct cx_hash_map_s const *map = iter->src_handle.c;
+const struct cx_hash_map_s *map = iter->src_handle.c;
 struct cx_hash_map_element_s *elm = iter->elem_handle;
 if (map->base.collection.store_pointer) {
 return *(void **) elm->data;
 } else {
 return elm->data;
 }
 }
-static bool cx_hash_map_iter_valid(void const *it) {
+static bool cx_hash_map_iter_valid(const void *it) {
-struct cx_iterator_s const *iter = it;
+const struct cx_iterator_s *iter = it;
 return iter->elem_handle != NULL;
 }
 static void cx_hash_map_iter_next(void *it) {
 struct cx_iterator_s *iter = it;
 }
 }
 }
 static CxIterator cx_hash_map_iterator(
-CxMap const *map,
+const CxMap *map,
 enum cx_map_iterator_type type
 ) {
 CxIterator iter;
 iter.src_handle.c = map;
 case CX_MAP_ITERATOR_VALUES:
 iter.elem_size = map->collection.elem_size;
 iter.base.current = cx_hash_map_iter_current_value;
 break;
 default:
-assert(false);
+assert(false); // LCOV_EXCL_LINE
 }
 iter.base.valid = cx_hash_map_iter_valid;
 iter.base.next = cx_hash_map_iter_next;
 iter.base.remove = false;
 cx_hash_map_remove,
 cx_hash_map_iterator,
 };
 CxMap *cxHashMapCreate(
-CxAllocator const *allocator,
+const CxAllocator *allocator,
 size_t itemsize,
 size_t buckets
 ) {
+if (allocator == NULL) {
+allocator = cxDefaultAllocator;
+}
 if (buckets == 0) {
 // implementation defined default
 buckets = 16;
 }
 // initialize hash map members
 map->bucket_count = buckets;
 map->buckets = cxCalloc(allocator, buckets,
 sizeof(struct cx_hash_map_element_s *));
-if (map->buckets == NULL) {
+if (map->buckets == NULL) { // LCOV_EXCL_START
 cxFree(allocator, map);
 return NULL;
-}
+} // LCOV_EXCL_STOP
 // initialize base members
 map->base.cl = &cx_hash_map_class;
 map->base.collection.allocator = allocator;
 int cxMapRehash(CxMap *map) {
 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) {
 size_t new_bucket_count = (map->collection.size * 5) >> 1;
+if (new_bucket_count < hash_map->bucket_count) {
+errno = EOVERFLOW;
+return 1;
+}
 struct cx_hash_map_element_s **new_buckets = cxCalloc(
 map->collection.allocator,
 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
 );
-if (new_buckets == NULL) {
+if (new_buckets == NULL) return 1;
-return 1;
-}
 // iterate through the elements and assign them to their new slots
-cx_for_n(slot, hash_map->bucket_count) {
+for (size_t slot = 0; slot < hash_map->bucket_count; slot++) {
 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
 while (elm != NULL) {
 struct cx_hash_map_element_s *next = elm->next;
 size_t new_slot = elm->key.hash % new_bucket_count;

comparison: ucx/hash_map.c

ucx/hash_map.c

Mercurial > hg > dav / file comparison

comparison: ucx/hash_map.c

ucx/hash_map.c