--- a/src/ucx/map.c Tue Aug 13 22:14:32 2019 +0200
+++ b/src/ucx/map.c Sat Sep 24 16:26:10 2022 +0200
@@ -1,7 +1,7 @@
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
- * Copyright 2016 Olaf Wintermann. All rights reserved.
+ * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
@@ -26,11 +26,11 @@
* POSSIBILITY OF SUCH DAMAGE.
*/
+#include "ucx/map.h"
+
#include <stdlib.h>
#include <string.h>
-#include "map.h"
-
UcxMap *ucx_map_new(size_t size) {
return ucx_map_new_a(NULL, size);
}
@@ -86,7 +86,11 @@
UcxMapIterator iter = ucx_map_iterator(map);
void *val;
UCX_MAP_FOREACH(key, val, iter) {
- destr(val);
+ if (destr) {
+ destr(val);
+ } else {
+ alfree(map->allocator, val);
+ }
}
}
@@ -99,8 +103,7 @@
map->count = 0;
}
-int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,
- copy_func fnc, void *data) {
+int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) {
UcxMapIterator i = ucx_map_iterator(from);
void *value;
UCX_MAP_FOREACH(key, value, i) {
@@ -111,9 +114,14 @@
return 0;
}
-UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {
+UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data) {
+ return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data);
+}
+
+UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
+ UcxMap const *map, copy_func fnc, void *data) {
size_t bs = (map->count * 5) >> 1;
- UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);
+ UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size);
if (!newmap) {
return NULL;
}
@@ -151,19 +159,22 @@
UcxAllocator *allocator = map->allocator;
if (key.hash == 0) {
- key.hash = ucx_hash((char*)key.data, key.len);
+ key.hash = ucx_hash((const char*)key.data, key.len);
}
+
+ struct UcxMapKey mapkey;
+ mapkey.hash = key.hash;
- size_t slot = key.hash%map->size;
- UcxMapElement *restrict elm = map->map[slot];
- UcxMapElement *restrict prev = NULL;
+ size_t slot = mapkey.hash%map->size;
+ UcxMapElement *elm = map->map[slot];
+ UcxMapElement *prev = NULL;
- while (elm && elm->key.hash < key.hash) {
+ while (elm && elm->key.hash < mapkey.hash) {
prev = elm;
elm = elm->next;
}
- if (!elm || elm->key.hash != key.hash) {
+ if (!elm || elm->key.hash != mapkey.hash) {
UcxMapElement *e = (UcxMapElement*)almalloc(
allocator, sizeof(UcxMapElement));
if (!e) {
@@ -185,8 +196,9 @@
return -1;
}
memcpy(kd, key.data, key.len);
- key.data = kd;
- elm->key = key;
+ mapkey.data = kd;
+ mapkey.len = key.len;
+ elm->key = mapkey;
map->count++;
}
elm->data = data;
@@ -194,14 +206,14 @@
return 0;
}
-void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {
+static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) {
if(key.hash == 0) {
- key.hash = ucx_hash((char*)key.data, key.len);
+ key.hash = ucx_hash((const char*)key.data, key.len);
}
size_t slot = key.hash%map->size;
- UcxMapElement *restrict elm = map->map[slot];
- UcxMapElement *restrict pelm = NULL;
+ UcxMapElement *elm = map->map[slot];
+ UcxMapElement *pelm = NULL;
while (elm && elm->key.hash <= key.hash) {
if(elm->key.hash == key.hash) {
int n = (key.len > elm->key.len) ? elm->key.len : key.len;
@@ -228,19 +240,19 @@
return NULL;
}
-void *ucx_map_get(UcxMap *map, UcxKey key) {
- return ucx_map_get_and_remove(map, key, 0);
+void *ucx_map_get(UcxMap const *map, UcxKey key) {
+ return ucx_map_get_and_remove((UcxMap *)map, key, 0);
}
void *ucx_map_remove(UcxMap *map, UcxKey key) {
return ucx_map_get_and_remove(map, key, 1);
}
-UcxKey ucx_key(void *data, size_t len) {
+UcxKey ucx_key(const void *data, size_t len) {
UcxKey key;
key.data = data;
key.len = len;
- key.hash = ucx_hash((const char*) data, len);
+ key.hash = ucx_hash((const char*)data, len);
return key;
}
@@ -287,7 +299,7 @@
return h;
}
-UcxMapIterator ucx_map_iterator(UcxMap *map) {
+UcxMapIterator ucx_map_iterator(UcxMap const *map) {
UcxMapIterator i;
i.map = map;
i.cur = NULL;
@@ -309,7 +321,9 @@
if (e->data) {
i->cur = e;
*elm = e->data;
- *key = e->key;
+ key->data = e->key.data;
+ key->hash = e->key.hash;
+ key->len = e->key.len;
return 1;
}
@@ -326,3 +340,63 @@
return 0;
}
+UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
+ copy_func cpfnc, void* cpdata) {
+ return ucx_map_union_a(ucx_default_allocator(),
+ first, second, cpfnc, cpdata);
+}
+
+UcxMap* ucx_map_union_a(UcxAllocator *allocator,
+ const UcxMap *first, const UcxMap *second,
+ copy_func cpfnc, void* cpdata) {
+ UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata);
+ ucx_map_copy(second, result, cpfnc, cpdata);
+ return result;
+}
+
+UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
+ copy_func cpfnc, void* cpdata) {
+ return ucx_map_intersection_a(ucx_default_allocator(),
+ first, second, cpfnc, cpdata);
+}
+
+UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
+ const UcxMap *first, const UcxMap *second,
+ copy_func cpfnc, void* cpdata) {
+ UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ?
+ first->size : second->size);
+
+ UcxMapIterator iter = ucx_map_iterator(first);
+ void* value;
+ UCX_MAP_FOREACH(key, value, iter) {
+ if (ucx_map_get(second, key)) {
+ ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
+ }
+ }
+
+ return result;
+}
+
+UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
+ copy_func cpfnc, void* cpdata) {
+ return ucx_map_difference_a(ucx_default_allocator(),
+ first, second, cpfnc, cpdata);
+}
+
+UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
+ const UcxMap *first, const UcxMap *second,
+ copy_func cpfnc, void* cpdata) {
+
+ UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);
+
+ UcxMapIterator iter = ucx_map_iterator(first);
+ void* value;
+ UCX_MAP_FOREACH(key, value, iter) {
+ if (!ucx_map_get(second, key)) {
+ ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
+ }
+ }
+
+ ucx_map_rehash(result);
+ return result;
+}
\ No newline at end of file