From 6337f29dd5310fd3c471ee1261077e755c3c2c39 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Mon, 2 Jan 2023 00:06:15 +0100 Subject: Add sets --- examples/Makefile | 5 ++- examples/gehashmap.c | 14 +------ examples/geset.c | 73 +++++++++++++++++++++++++++++++++++ src/gehashmap.h | 10 ++++- src/geset.h | 107 +++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 194 insertions(+), 15 deletions(-) create mode 100644 examples/geset.c create mode 100644 src/geset.h diff --git a/examples/Makefile b/examples/Makefile index c6c5643..e86f074 100644 --- a/examples/Makefile +++ b/examples/Makefile @@ -2,14 +2,15 @@ CC = cc CFLAGS = -Wall -Wextra -Wpedantic -Werror \ - -Og -g -ggdb + -Og -g -ggdb -std=c99 LDFLAGS = -I../src -progs = gehashmap gevector +progs = gehashmap geset gevector all: ${progs} gehashmap: gehashmap.c +geset: geset.c gevector: gevector.c clean: diff --git a/examples/gehashmap.c b/examples/gehashmap.c index a29ef14..85c007f 100644 --- a/examples/gehashmap.c +++ b/examples/gehashmap.c @@ -1,3 +1,5 @@ +#define _XOPEN_SOURCE 500 + #include #include #include @@ -19,18 +21,6 @@ itoumap_key_iseq(int a, int b) return a == b; } -void -atoimap_key_free(char *s) -{ - free(s); -} - -void -itoumap_key_free(int a) -{ - (void) a; -} - size_t atoimap_key_hash(char *s) { diff --git a/examples/geset.c b/examples/geset.c new file mode 100644 index 0000000..e4514cd --- /dev/null +++ b/examples/geset.c @@ -0,0 +1,73 @@ +#include +#include + +#include + +GESET_DEF(size_t, sizeset) + +bool +sizeset_elem_iseq(size_t a, size_t b) +{ + return a == b; +} + +size_t +sizeset_elem_hash(size_t n) +{ + return n; +} + +int +main(void) +{ + size_t i; + sizeset_t *set; + + sizeset_new(set = malloc(sizeof(sizeset_t)), 0, 0); + + if (sizeset_has(set, 69)) { + puts("Something went wrong..."); + exit(EXIT_FAILURE); + } + + sizeset_add(set, 69); + sizeset_add(set, 69); + sizeset_add(set, 69); + sizeset_add(set, 69); + + if (!sizeset_has(set, 69)) { + puts("Something went wrong..."); + exit(EXIT_FAILURE); + } + + sizeset_add(set, 42); + sizeset_add(set, 420); + sizeset_remove(set, 42); + + GESET_FOREACH(sizeset, size_t, n, *set) { + GESET_FOREACH(sizeset, size_t, m, *set) + printf("Set -> %zu, %zu\n", n, m); + } + + sizeset_add(set, 1); + sizeset_add(set, 2); + sizeset_add(set, 3); + sizeset_add(set, 4); + sizeset_add(set, 5); + sizeset_add(set, 6); + sizeset_add(set, 7); + sizeset_add(set, 8); + sizeset_add(set, 9); + + i = 0; + GESET_FOREACH(sizeset, size_t, n, *set) + printf("Set[%zu] -> %zu\n", i++, n); + + printf("Set Size -> %zu\n", sizeset_size(set)); + + GESET_FOREACH_SAFE(sizeset, size_t, n, *set) + sizeset_remove(set, n); + + sizeset_free(set); + free(set); +} diff --git a/src/gehashmap.h b/src/gehashmap.h index 832d047..ccd7a60 100644 --- a/src/gehashmap.h +++ b/src/gehashmap.h @@ -42,7 +42,7 @@ \ /* A structure representing an actual hashmap */ \ typedef struct { \ - size_t __size, /* The number of used buckets */ \ + size_t __size, /* The number of elements in the map */ \ __cap; /* The number of allocated buckets */ \ double __loadf; /* The % of the hashmap that must be * filled before the map grows */ \ @@ -54,6 +54,7 @@ int n##_set(n_t *, k, v); \ bool n##_get(n_t *, k, v *); \ bool n##_has(n_t *, k); \ + size_t n##_size(n_t *); \ int n##_remove(n_t *, k); \ int n##_resize(n_t *, size_t); \ bool n##_key_iseq(k, k); \ @@ -160,6 +161,13 @@ return n##_get(map, key, NULL); \ } \ \ + /* Function to get the number of elements in a hashmap. */ \ + size_t \ + n##_size(n_t *map) \ + { \ + return map->__size; \ + } \ + \ /* Function to remove an element with a given key from a hashmap. If * the key or value were dynamically allocated they will not be freed. * On error -1 is returned, otherwise 0 is returned. diff --git a/src/geset.h b/src/geset.h new file mode 100644 index 0000000..da463f2 --- /dev/null +++ b/src/geset.h @@ -0,0 +1,107 @@ +#ifndef LIBGE_GESET_H +#define LIBGE_GESET_H + +#include + +#include + +#define GESET_FOREACH(n, t, e, s) \ + for (size_t __ge_i = 0; __ge_i < (s).__cap; __ge_i++) \ + for (struct __##n##_hashmap_entry *__ge_e = (s).__ents[__ge_i]; \ + __ge_e != NULL; \ + __ge_e = __ge_e->__next) \ + for (bool __ge_c = true; __ge_c; __ge_c = false) \ + for (t e = __ge_e->key; __ge_c; __ge_c = false) + +#define GESET_FOREACH_SAFE(n, t, e, s) \ + for (size_t __ge_i = 0; __ge_i < (s).__cap; __ge_i++) \ + for (struct __##n##_hashmap_entry *__ge_e = (s).__ents[__ge_i], \ + *__ge_t = __ge_e ? __ge_e->__next : NULL; \ + __ge_e != NULL; \ + __ge_e = __ge_t, __ge_t = __ge_e ? __ge_e->__next : NULL) \ + for (bool __ge_c = true; __ge_c; __ge_c = false) \ + for (t e = __ge_e->key; __ge_c; __ge_c = false) + +#define GESET_DEF(t, n) \ + GESET_DEF_API(t, n) \ + GESET_DEF_IMPL(t, n) + +#define GESET_DEF_API(t, n) \ + GESET_DEF_API_HELPER(t, n, n##_t, __##n##_hashmap) +#define GESET_DEF_API_HELPER(t, n, n_t, int_n) \ + GEHASHMAP_DEF_API(t, int, int_n) \ + \ + typedef int_n##_t n_t; \ + \ + int n##_new(n_t *, size_t, double); \ + void n##_free(n_t *); \ + int n##_add(n_t *, t); \ + bool n##_has(n_t *, t); \ + size_t n##_size(n_t *); \ + int n##_remove(n_t *, t); \ + int n##_resize(n_t *, size_t); \ + bool int_n##_key_iseq(t, t); \ + size_t int_n##_key_hash(t); \ + bool n##_elem_iseq(t, t); \ + size_t n##_elem_hash(t); + +#define GESET_DEF_IMPL(t, n) \ + GESET_DEF_IMPL_HELPER(t, n, n##_t, __##n##_hashmap) +#define GESET_DEF_IMPL_HELPER(t, n, n_t, int_n) \ + GEHASHMAP_DEF_IMPL(t, int, int_n) \ + \ + bool \ + int_n##_key_iseq(t a, t b) \ + { \ + return n##_elem_iseq(a, b); \ + } \ + \ + size_t \ + int_n##_key_hash(t e) \ + { \ + return n##_elem_hash(e); \ + } \ + \ + int \ + n##_new(n_t *set, size_t cap, double loadf) \ + { \ + return int_n##_new(set, cap, loadf); \ + } \ + \ + void \ + n##_free(n_t *set) \ + { \ + int_n##_free(set); \ + } \ + \ + int \ + n##_add(n_t *set, t e) \ + { \ + return int_n##_set(set, e, 0); \ + } \ + \ + bool \ + n##_has(n_t *set, t e) \ + { \ + return int_n##_has(set, e); \ + } \ + \ + size_t \ + n##_size(n_t *set) \ + { \ + return int_n##_size(set); \ + } \ + \ + int \ + n##_remove(n_t *set, t e) \ + { \ + return int_n##_remove(set, e); \ + } \ + \ + int \ + n##_resize(n_t *set, size_t ncap) \ + { \ + return int_n##_resize(set, ncap); \ + } + +#endif /* !LIBGE_GESET_H */ -- cgit v1.2.3