From 173d32f0eb194b30b40fb5eb6e708bc3c4f8f421 Mon Sep 17 00:00:00 2001 From: Tylo Date: Sat, 20 Jun 2020 20:47:56 +0200 Subject: Renamed CMap to CHash, to reflect that it now supports both (unordered) Map and Set. Second arg in declare_CHash() should be 'set' or 'map'. Refactored copt.h to be more consistent with other types. Added cvector_make(size, fillvalue) constructor. --- README.md | 69 ++++++------ advanced_example.c | 22 ++-- benchmark.c | 18 +-- demos.c | 66 ++++++----- stc/cdefs.h | 2 +- stc/clist.h | 2 +- stc/cmap.h | 326 ++++++++++++++++++++++++++++------------------------- stc/copt.h | 40 +++---- stc/cvector.h | 21 +++- 9 files changed, 301 insertions(+), 265 deletions(-) diff --git a/README.md b/README.md index f4276f40..689a62bd 100644 --- a/README.md +++ b/README.md @@ -3,12 +3,14 @@ STC - C99 Standard Container Library Introduction ------------ -A modern, generic, typesafe, and very efficient standard container library for C99. -This is a small headers only library with the most used data structures: **cstring**, **cvector**, **carray**, **clist** and **map**. +An elegant, modern, generic, typesafe, and very efficient standard container library for C99. + +This is a small headers only library with the most used container components: **cstring**, **cvector**, **carray**, **clist** and **chash**. + +Usage by examples +----------------- -Usage ------ CString demo ``` #include @@ -69,58 +71,53 @@ int main() { cvector_cs_destroy(&names); } ``` -Simple CMap, int -> int: +CHash map of int -> int ``` #include -declare_CMap(ii, int, int); +declare_CHash(ii, map, int, int); int main() { - CMap_ii nums = cmap_init; - cmap_ii_put(&nums, 8, 64); - cmap_ii_put(&nums, 11, 121); + CHash_ii nums = cmap_init; + chash_ii_put(&nums, 8, 64); + chash_ii_put(&nums, 11, 121); - printf("%d\n", cmap_ii_get(nums, 8)->value); - cmap_ii_destroy(&nums); + printf("%d\n", chash_ii_get(nums, 8)->value); + chash_ii_destroy(&nums); } ``` -Simple CMap, CString -> int +CHash set of CString ``` #include #include -declare_CMap_stringkey(si, int); // Shorthand macro for the general declare_CMap expansion. -// CString keys are "magically" managed internally, although CMap is ignorant of CString. +declare_CHash_string(s, set); // Shorthand macro for the general declare_CHash expansion. +// CString keys are managed internally, although CHash is ignorant of CString. int main() { - CMap_si nums = cmap_init; - cmap_si_put(&nums, "Hello", 64); - cmap_si_put(&nums, "Groovy", 121); - cmap_si_put(&nums, "Groovy", 200); // overwrite previous + CHash_s words = cmap_init; + chash_s_put(&words, "Hello"); + chash_s_put(&words, "Groovy"); + chash_s_erase(&words, "Hello"); // iterate the map: - for (cmap_si_iter_t i = cmap_si_begin(&nums); i.item; i = cmap_si_next(i)) - printf("%s: %d\n", i.item->key.str, i.item->value); - - // or rather use the shorter form: - c_foreach (i, cmap_si, nums) - printf("%s: %d\n", i.item->key.str, i.item->value); - - cmap_si_destroy(&nums); + c_foreach (i, chash_s, words) + printf("%s\n", i.item->key.str); + chash_s_destroy(&words); } ``` -CMap, with CString -> CString. Temporary CString values are created by "make", and moved to the container +CHash map of CString -> CString. Temporary CString values are created by "make", and moved to the container ``` #include #include -declare_CMap_stringkey(ss, CString, cstring_destroy); +declare_CHash_string(ss, map, CString, cstring_destroy); int main() { - CMap_ss table = cmap_init; - cmap_ss_put(&table, "Make", cstring_make("my")); - cmap_ss_put(&table, "Sunny", cstring_make("day")); - printf("Sunny: %s\n", cmap_ss_get(table, "Sunny")->value.str); - cmap_ss_erase(&table, "Make"); - - printf("size %d\n", cmap_size(table)); - cmap_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). + CHash_ss table = cmap_init; + chash_ss_put(&table, "Make", cstring_make("my")); + chash_ss_put(&table, "Sunny", cstring_make("day")); + printf("Sunny: %s\n", chash_ss_get(table, "Sunny")->value.str); + chash_ss_erase(&table, "Make"); + + printf("size %d\n", chash_size(table)); + chash_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). } ``` diff --git a/advanced_example.c b/advanced_example.c index 449bddb3..b85b433e 100644 --- a/advanced_example.c +++ b/advanced_example.c @@ -1,4 +1,4 @@ -/*To be able to use CMap with a user-defined key-type, you need to define two things: +/*To be able to use CHash with a user-defined key-type, you need to define two things: 1. A hash function; this must be a function that calculates the hash value given an object of the key-type. @@ -64,28 +64,26 @@ size_t personview_hash(const struct PersonView* pv, size_t ignore) { /*``` With this in place, we can declare the map Person -> int: ```*/ -declare_CMap(ex, struct Person, int, c_noDestroy, person_destroy, - struct PersonView, personview_hash, personview_compare, - person_getView, person_fromView); +declare_CHash(ex, map, struct Person, int, c_emptyDestroy, personview_hash, personview_compare, + struct PersonView, person_destroy, person_getView, person_fromView); /*``` Note we use struct PersonView to put keys in the map, but keys are stored as struct Person with proper dynamically allocated CStrings to store name and surname. ```*/ int main() { - CMap_ex m6 = cmap_init; - cmap_ex_put(&m6, (struct PersonView){"John", "Doe", 24}, 1001); - cmap_ex_put(&m6, (struct PersonView){"Jane", "Doe", 21}, 1002); - cmap_ex_put(&m6, (struct PersonView){"John", "Travolta", 66}, 1003); + CHash_ex m6 = chash_init; + chash_ex_put(&m6, (struct PersonView){"John", "Doe", 24}, 1001); + chash_ex_put(&m6, (struct PersonView){"Jane", "Doe", 21}, 1002); + chash_ex_put(&m6, (struct PersonView){"John", "Travolta", 66}, 1003); - c_foreach (it, cmap_ex, m6) { + c_foreach (it, chash_ex, m6) { if (cstring_equals(it.item->key.name, "John")) printf("%s %s %d -> %d\n", it.item->key.name.str, it.item->key.surname.str, it.item->key.age, it.item->value); } - cmap_ex_destroy(&m6); + chash_ex_destroy(&m6); } /*``` -CMap uses personview_hash() for hash value calculations, and the personview_compare() for equality checks. The cmap_ex_destroy() function will free CStrings name, surname and the value for each item in the map, in addition to the CMap hash table itself. +CHash uses personview_hash() for hash value calculations, and the personview_compare() for equality checks. The chash_ex_destroy() function will free CStrings name, surname and the value for each item in the map, in addition to the CHash hash table itself. */ - diff --git a/benchmark.c b/benchmark.c index 8b6a49c8..72e47699 100644 --- a/benchmark.c +++ b/benchmark.c @@ -19,7 +19,7 @@ static inline uint32_t fibonacci_hash(const void* data, size_t len) { const uint64_t key = *(const uint64_t *) data; return (uint32_t) (key * 11400714819323198485llu); } -declare_CMap(ii, int64_t, int64_t, c_noDestroy, fibonacci_hash); // c_lowbias32Hash); +declare_CHash(ii, map, int64_t, int64_t, c_emptyDestroy, fibonacci_hash); // c_lowbias32Hash); KHASH_MAP_INIT_INT64(ii, uint64_t) @@ -34,14 +34,14 @@ sfc64_t rng; //#define RAND(N) (mt19937_rand(&rng) & ((1 << N) - 1)) -#define CMAP_SETUP(tag, Key, Value) CMap_##tag map = cmap_init; \ - cmap_##tag##_setMaxLoadFactor(&map, maxLoadFactor) -#define CMAP_PUT(tag, key, val) cmap_##tag##_put(&map, key, val)->value -#define CMAP_ERASE(tag, key) cmap_##tag##_erase(&map, key) -#define CMAP_FIND(tag, key) (cmap_##tag##_get(map, key) != NULL) -#define CMAP_SIZE(tag) cmap_size(map) -#define CMAP_BUCKETS(tag) cmap_bucketCount(map) -#define CMAP_CLEAR(tag) cmap_##tag##_destroy(&map) +#define CMAP_SETUP(tag, Key, Value) CHash_##tag map = chash_init; \ + chash_##tag##_setMaxLoadFactor(&map, maxLoadFactor) +#define CMAP_PUT(tag, key, val) chash_##tag##_put(&map, key, val)->value +#define CMAP_ERASE(tag, key) chash_##tag##_erase(&map, key) +#define CMAP_FIND(tag, key) (chash_##tag##_get(map, key) != NULL) +#define CMAP_SIZE(tag) chash_size(map) +#define CMAP_BUCKETS(tag) chash_bucketCount(map) +#define CMAP_CLEAR(tag) chash_##tag##_destroy(&map) #define KMAP_SETUP(tag, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret #define KMAP_PUT(tag, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) diff --git a/demos.c b/demos.c index 2f1cc099..18be0e00 100644 --- a/demos.c +++ b/demos.c @@ -98,60 +98,73 @@ void listdemo1() clist_ix_destroy(&nums); } +declare_CHash(i, set, int); + +void setdemo1() +{ + printf("\nSETDEMO1\n"); + CHash_i nums = chash_init; + chash_i_put(&nums, 8); + chash_i_put(&nums, 11); + + c_foreach (i, chash_i, nums) + printf("set: %d\n", i.item->key); + chash_i_destroy(&nums); +} -declare_CMap(ii, int, int); + +declare_CHash(ii, map, int, int); void mapdemo1() { printf("\nMAPDEMO1\n"); - CMap_ii nums = cmap_init; - cmap_ii_put(&nums, 8, 64); - cmap_ii_put(&nums, 11, 121); + CHash_ii nums = chash_init; + chash_ii_put(&nums, 8, 64); + chash_ii_put(&nums, 11, 121); - printf("get 8: %d\n", cmap_ii_get(&nums, 8)->value); - cmap_ii_destroy(&nums); + printf("get 8: %d\n", chash_ii_get(&nums, 8)->value); + chash_ii_destroy(&nums); } - -declare_CMap_stringkey(si, int); // Shorthand macro for the general declare_CMap expansion. +declare_CHash_string(si, map, int); // Shorthand macro for the general declare_CHash expansion. void mapdemo2() { printf("\nMAPDEMO2\n"); - CMap_si nums = cmap_init; - cmap_si_put(&nums, "Hello", 64); - cmap_si_put(&nums, "Groovy", 121); - cmap_si_put(&nums, "Groovy", 200); // overwrite previous + CHash_si nums = chash_init; + chash_si_put(&nums, "Hello", 64); + chash_si_put(&nums, "Groovy", 121); + chash_si_put(&nums, "Groovy", 200); // overwrite previous // iterate the map: - for (cmap_si_iter_t i = cmap_si_begin(&nums); i.item; i = cmap_si_next(i)) + for (chash_si_iter_t i = chash_si_begin(&nums); i.item; i = chash_si_next(i)) printf("long: %s: %d\n", i.item->key.str, i.item->value); // or rather use the short form: - c_foreach (i, cmap_si, nums) + c_foreach (i, chash_si, nums) printf("short: %s: %d\n", i.item->key.str, i.item->value); - cmap_si_destroy(&nums); + chash_si_destroy(&nums); } -declare_CMap_stringkey(ss, CString, cstring_destroy); +declare_CHash_string(ss, map, CString, cstring_destroy); void mapdemo3() { printf("\nMAPDEMO3\n"); - CMap_ss table = cmap_init; - cmap_ss_put(&table, "Map", cstring_make("test")); - cmap_ss_put(&table, "Make", cstring_make("my")); - cmap_ss_put(&table, "Sunny", cstring_make("day")); - printf("remove: Make: %s\n", cmap_ss_get(&table, "Make")->value.str); - cmap_ss_erase(&table, "Make"); - - printf("size %zu\n", cmap_size(table)); - c_foreach (i, cmap_ss, table) + CHash_ss table = chash_init; + chash_ss_put(&table, "Map", cstring_make("test")); + chash_ss_put(&table, "Make", cstring_make("my")); + chash_ss_put(&table, "Sunny", cstring_make("day")); + printf("remove: Make: %s\n", chash_ss_get(&table, "Make")->value.str); + chash_ss_erase(&table, "Make"); + + printf("size %zu\n", chash_size(table)); + c_foreach (i, chash_ss, table) printf("key: %s\n", i.item->key.str); - cmap_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). + chash_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). } @@ -162,6 +175,7 @@ int main() vectordemo1(); vectordemo2(); listdemo1(); + setdemo1(); mapdemo1(); mapdemo2(); mapdemo3(); diff --git a/stc/cdefs.h b/stc/cdefs.h index 3d5e5766..d8e3228d 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -65,7 +65,7 @@ #define c_noCompare(x, y) (0) #define c_defaultEquals(x, y) (*(x) == *(y)) #define c_memEquals(x, y) (memcmp(x, y, sizeof(*(y))) == 0) -#define c_noDestroy(p) ((void)0) +#define c_emptyDestroy(p) ((void)0) #define c_foreach(it, prefix, container) \ for (prefix##_iter_t it = prefix##_begin(&container); it.item; it = prefix##_next(it)) diff --git a/stc/clist.h b/stc/clist.h index ae294705..cd00479b 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -74,7 +74,7 @@ #define declare_CList(...) c_MACRO_OVERLOAD(declare_CList, __VA_ARGS__) #define declare_CList_2(tag, Value) \ - declare_CList_3(tag, Value, c_noDestroy) + declare_CList_3(tag, Value, c_emptyDestroy) #define declare_CList_3(tag, Value, valueDestroy) \ declare_CList_4(tag, Value, valueDestroy, c_defaultCompare) #define declare_CList_4(tag, Value, valueDestroy, valueCompare) \ diff --git a/stc/cmap.h b/stc/cmap.h index 0aef3f14..a53f7d75 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -24,185 +24,201 @@ /* // Example: #include #include "stc/cmap.h" -declare_CMap(ex, int, char); +declare_CHash(sx, set, int); +declare_CHash(mx, map, int, char); int main(void) { - CMap_ex h = cmap_init; - cmap_ex_put(&h, 5, 'a'); - cmap_ex_put(&h, 8, 'b'); - cmap_ex_put(&h, 12, 'c'); - CMapEntry_ex *e = cmap_ex_get(&h, 10); // = NULL - char val = cmap_ex_get(&h, 5)->value; - cmap_ex_put(&h, 5, 'd'); // update - cmap_ex_erase(&h, 8); - c_foreach (i, cmap_ex, h) - printf("%d: %c\n", i.item->key, i.item->value); - cmap_ex_destroy(&h); + CHash_sx s = chash_init; + chash_sx_put(&s, 5); + chash_sx_put(&s, 8); + c_foreach (i, chash_sx, s) printf("set %d\n", i.item->key); + chash_mx_destroy(&s); + + CHash_mx m = chash_init; + chash_mx_put(&m, 5, 'a'); + chash_mx_put(&m, 8, 'b'); + chash_mx_put(&m, 12, 'c'); + CHashEntry_mx *e = chash_mx_get(&m, 10); // = NULL + char val = chash_mx_get(&m, 5)->value; + chash_mx_put(&m, 5, 'd'); // update + chash_mx_erase(&m, 8); + c_foreach (i, chash_mx, m) printf("map %d: %c\n", i.item->key, i.item->value); + chash_mx_destroy(&m); } */ -#ifndef CMAP__H__ -#define CMAP__H__ + +#ifndef CHASH__H__ +#define CHASH__H__ #include #include "cdefs.h" -#define cmap_init {NULL, NULL, 0, 0, 90, 0} -#define cmap_size(map) ((size_t) (map)._size) -#define cmap_bucketCount(map) ((size_t) (map)._cap) +#define chash_init {NULL, NULL, 0, 0, 90, 0} +#define chash_size(map) ((size_t) (map)._size) +#define chash_bucketCount(map) ((size_t) (map)._cap) /* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ -#define cmap_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) +#define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) + +enum {chash_HASH = 0x7f, chash_USED = 0x80}; -enum {cmapentry_HASH=0x7f, cmapentry_USED=0x80}; +/* CHash: */ +#define declare_CHash(...) \ + c_MACRO_OVERLOAD(declare_CHash, __VA_ARGS__) -/* CMap: */ -#define declare_CMap(...) \ - c_MACRO_OVERLOAD(declare_CMap, __VA_ARGS__) +#define declare_CHash_3(tag, type, Key) \ + declare_CHash_4(tag, type, Key, void) -#define declare_CMap_3(tag, Key, Value) \ - declare_CMap_4(tag, Key, Value, c_noDestroy) +#define declare_CHash_4(tag, type, Key, Value) \ + declare_CHash_5(tag, type, Key, Value, c_emptyDestroy) -#define declare_CMap_4(tag, Key, Value, valueDestroy) \ - declare_CMap_5(tag, Key, Value, valueDestroy, c_defaultHash) +#define declare_CHash_5(tag, type, Key, Value, valueDestroy) \ + declare_CHash_6(tag, type, Key, Value, valueDestroy, c_defaultHash) -#define declare_CMap_5(tag, Key, Value, valueDestroy, keyHash) \ - declare_CMap_6(tag, Key, Value, valueDestroy, keyHash, c_defaultEquals) +#define declare_CHash_6(tag, type, Key, Value, valueDestroy, keyHash) \ + declare_CHash_7(tag, type, Key, Value, valueDestroy, keyHash, c_defaultEquals) -#define declare_CMap_6(tag, Key, Value, valueDestroy, keyHash, keyEquals) \ - declare_CMap_10(tag, Key, Value, valueDestroy, c_noDestroy, Key, \ - keyHash, keyEquals, c_defaultGetRaw, c_defaultInitRaw) +#define declare_CHash_7(tag, type, Key, Value, valueDestroy, keyHash, keyEquals) \ + declare_CHash_11(tag, type, Key, Value, valueDestroy, keyHash, keyEquals, \ + Key, c_emptyDestroy, c_defaultGetRaw, c_defaultInitRaw) +/* CHash: */ +#define declare_CHash_string(...) \ + c_MACRO_OVERLOAD(declare_CHash_string, __VA_ARGS__) -/* CMap: */ -#define declare_CMap_stringkey(...) \ - c_MACRO_OVERLOAD(declare_CMap_stringkey, __VA_ARGS__) +#define declare_CHash_string_2(tag, type) \ + declare_CHash_string_3(tag, type, void) -#define declare_CMap_stringkey_2(tag, Value) \ - declare_CMap_stringkey_3(tag, Value, c_noDestroy) +#define declare_CHash_string_3(tag, type, Value) \ + declare_CHash_string_4(tag, type, Value, c_emptyDestroy) -#define declare_CMap_stringkey_3(tag, Value, valueDestroy) \ - declare_CMap_10(tag, CString, Value, valueDestroy, cstring_destroy, const char*, \ - cstring_hashRaw, cstring_equalsRaw, cstring_getRaw, cstring_make) +#define declare_CHash_string_4(tag, type, Value, valueDestroy) \ + declare_CHash_11(tag, type, CString, Value, valueDestroy, cstring_hashRaw, cstring_equalsRaw, \ + const char*, cstring_destroy, cstring_getRaw, cstring_make) +#define _chash1_set(x) +#define _chash2_set(x, y) x +#define _chash1_map(x) x +#define _chash2_map(x, y) x, y -/* CMap full: */ -#define declare_CMap_10(tag, Key, Value, valueDestroy, keyDestroy, RawKey, \ - keyHashRaw, keyEqualsRaw, keyGetRaw, keyInitRaw) \ -typedef struct CMapEntry_##tag { \ +/* CHash full: */ +#define declare_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ +typedef struct CHashEntry_##tag { \ Key key; \ - Value value; \ -} CMapEntry_##tag; \ + _chash1_##type(Value value;) \ +} CHashEntry_##tag; \ \ -static inline CMapEntry_##tag cmapentry_##tag##_make(Key key, Value value) { \ - CMapEntry_##tag e = {key, value}; return e; \ +static inline CHashEntry_##tag chashentry_##tag##_make(_chash2_##type(Key k, Value v)) { \ + CHashEntry_##tag e = {_chash2_##type(k, v)}; return e; \ } \ static inline void \ -cmapentry_##tag##_destroy(CMapEntry_##tag* e) { \ +chashentry_##tag##_destroy(CHashEntry_##tag* e) { \ keyDestroy(&e->key); \ - valueDestroy(&e->value); \ + _chash1_##type(valueDestroy(&e->value);) \ } \ \ -typedef RawKey CMapRawKey_##tag; \ +typedef RawKey CHashRawKey_##tag; \ \ -typedef struct CMap_##tag { \ - CMapEntry_##tag* _table; \ +typedef struct CHash_##tag { \ + CHashEntry_##tag* _table; \ uint8_t* _hashx; \ uint32_t _size, _cap; \ uint8_t maxLoadPercent; \ uint8_t shrinkLimitPercent; \ -} CMap_##tag; \ +} CHash_##tag; \ \ typedef struct { \ - CMapEntry_##tag *item, *_end; \ + CHashEntry_##tag *item, *_end; \ uint8_t* _hx; \ -} CMapIter_##tag, cmap_##tag##_iter_t; \ +} CHashIter_##tag, chash_##tag##_iter_t; \ \ typedef struct { \ - CMapRawKey_##tag rawKey; \ + CHashRawKey_##tag rawKey; \ size_t index; \ uint32_t hashx; \ -} CMapBucket_##tag; \ +} CHashBucket_##tag; \ \ STC_API void \ -cmap_##tag##_destroy(CMap_##tag* self); \ +chash_##tag##_destroy(CHash_##tag* self); \ STC_API void \ -cmap_##tag##_clear(CMap_##tag* self); \ +chash_##tag##_clear(CHash_##tag* self); \ STC_API void \ -cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, double fac); \ +chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac); \ STC_API void \ -cmap_##tag##_setShrinkLimitFactor(CMap_##tag* self, double limit); \ +chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit); \ STC_API size_t \ -cmap_##tag##_bucket(const CMap_##tag* self, const CMapRawKey_##tag* rawKeyPtr, uint32_t* hxPtr); \ -STC_API CMapEntry_##tag* \ -cmap_##tag##_get(const CMap_##tag* self, CMapRawKey_##tag rawKey); \ -STC_API CMapEntry_##tag* \ -cmap_##tag##_put(CMap_##tag* self, CMapRawKey_##tag rawKey, Value value); \ -STC_API CMapEntry_##tag* \ -cmap_##tag##_find(CMap_##tag* self, CMapRawKey_##tag rawKey, CMapBucket_##tag* b); \ +chash_##tag##_bucket(const CHash_##tag* self, const CHashRawKey_##tag* rawKeyPtr, uint32_t* hxPtr); \ +STC_API CHashEntry_##tag* \ +chash_##tag##_get(const CHash_##tag* self, CHashRawKey_##tag rawKey); \ +STC_API CHashEntry_##tag* \ +chash_##tag##_put(CHash_##tag* self, _chash2_##type(CHashRawKey_##tag rawKey, Value value)); \ +STC_API CHashEntry_##tag* \ +chash_##tag##_find(CHash_##tag* self, CHashRawKey_##tag rawKey, CHashBucket_##tag* b); \ STC_API void \ -cmap_##tag##_insert(CMap_##tag* self, CMapBucket_##tag b, Value value); \ +chash_##tag##_insert(CHash_##tag* self, _chash2_##type(CHashBucket_##tag b, Value value)); \ STC_API size_t \ -cmap_##tag##_reserve(CMap_##tag* self, size_t size); \ +chash_##tag##_reserve(CHash_##tag* self, size_t size); \ STC_API bool \ -cmap_##tag##_eraseBucket(CMap_##tag* self, size_t i); \ +chash_##tag##_eraseBucket(CHash_##tag* self, size_t i); \ STC_API bool \ -cmap_##tag##_erase(CMap_##tag* self, CMapRawKey_##tag rawKey); \ -STC_API cmap_##tag##_iter_t \ -cmap_##tag##_begin(CMap_##tag* map); \ -STC_API cmap_##tag##_iter_t \ -cmap_##tag##_next(cmap_##tag##_iter_t it); \ +chash_##tag##_erase(CHash_##tag* self, CHashRawKey_##tag rawKey); \ +STC_API chash_##tag##_iter_t \ +chash_##tag##_begin(CHash_##tag* map); \ +STC_API chash_##tag##_iter_t \ +chash_##tag##_next(chash_##tag##_iter_t it); \ \ -implement_CMap_10(tag, Key, Value, valueDestroy, keyDestroy, RawKey, \ - keyHashRaw, keyEqualsRaw, keyGetRaw, keyInitRaw) \ -typedef Key CMapKey_##tag; \ -typedef Value CMapValue_##tag +implement_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ +typedef Key CHashKey_##tag; \ +typedef Value CHashValue_##tag /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_CMap_10(tag, Key, Value, valueDestroy, keyDestroy, RawKey, \ - keyHashRaw, keyEqualsRaw, keyGetRaw, keyInitRaw) \ +#define implement_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ \ STC_API void \ -cmap_##tag##_destroy(CMap_##tag* self) { \ - if (cmap_size(*self)) { \ - size_t cap = cmap_bucketCount(*self); \ - CMapEntry_##tag* e = self->_table, *end = e + cap; \ +chash_##tag##_destroy(CHash_##tag* self) { \ + if (chash_size(*self)) { \ + size_t cap = chash_bucketCount(*self); \ + CHashEntry_##tag* e = self->_table, *end = e + cap; \ uint8_t *hashx = self->_hashx; \ - for (; e != end; ++e) if (*hashx++) cmapentry_##tag##_destroy(e); \ + for (; e != end; ++e) if (*hashx++) chashentry_##tag##_destroy(e); \ } \ free(self->_hashx); \ free(self->_table); \ } \ \ -STC_API void cmap_##tag##_clear(CMap_##tag* self) { \ - cmap_##tag##_destroy(self); \ +STC_API void chash_##tag##_clear(CHash_##tag* self) { \ + chash_##tag##_destroy(self); \ self->_cap = self->_size = 0; \ } \ \ STC_API void \ -cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, double fac) { \ +chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac) { \ self->maxLoadPercent = (uint8_t) (fac * 100); \ - if (cmap_size(*self) >= cmap_bucketCount(*self) * fac) \ - cmap_##tag##_reserve(self, (size_t) (cmap_size(*self) / fac)); \ + if (chash_size(*self) >= chash_bucketCount(*self) * fac) \ + chash_##tag##_reserve(self, (size_t) (chash_size(*self) / fac)); \ } \ \ STC_API void \ -cmap_##tag##_setShrinkLimitFactor(CMap_##tag* self, double limit) { \ +chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit) { \ self->shrinkLimitPercent = (uint8_t) (limit * 100); \ - if (cmap_size(*self) < cmap_bucketCount(*self) * limit) \ - cmap_##tag##_reserve(self, (size_t) (cmap_size(*self) * 1.2 / limit)); \ + if (chash_size(*self) < chash_bucketCount(*self) * limit) \ + chash_##tag##_reserve(self, (size_t) (chash_size(*self) * 1.2 / limit)); \ } \ \ STC_API size_t \ -cmap_##tag##_bucket(const CMap_##tag* self, const CMapRawKey_##tag* rawKeyPtr, uint32_t* hxPtr) { \ - uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(CMapRawKey_##tag)); \ - uint32_t sx, hx = (hash & cmapentry_HASH) | cmapentry_USED; \ - size_t cap = cmap_bucketCount(*self); \ - size_t idx = cmap_reduce(hash, cap); \ +chash_##tag##_bucket(const CHash_##tag* self, const CHashRawKey_##tag* rawKeyPtr, uint32_t* hxPtr) { \ + uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(CHashRawKey_##tag)); \ + uint32_t sx, hx = (hash & chash_HASH) | chash_USED; \ + size_t cap = chash_bucketCount(*self); \ + size_t idx = chash_reduce(hash, cap); \ uint8_t* hashx = self->_hashx; \ while ((sx = hashx[idx])) { \ if (sx == hx) { \ - CMapRawKey_##tag r = keyGetRaw(&self->_table[idx].key); \ + CHashRawKey_##tag r = keyGetRaw(&self->_table[idx].key); \ if (keyEqualsRaw(&r, rawKeyPtr)) break; \ } \ if (++idx == cap) idx = 0; \ @@ -211,81 +227,81 @@ cmap_##tag##_bucket(const CMap_##tag* self, const CMapRawKey_##tag* rawKeyPtr, u return idx; \ } \ \ -STC_API CMapEntry_##tag* \ -cmap_##tag##_get(const CMap_##tag* self, CMapRawKey_##tag rawKey) { \ - if (cmap_bucketCount(*self) == 0) return NULL; \ +STC_API CHashEntry_##tag* \ +chash_##tag##_get(const CHash_##tag* self, CHashRawKey_##tag rawKey) { \ + if (chash_bucketCount(*self) == 0) return NULL; \ uint32_t hx; \ - size_t idx = cmap_##tag##_bucket(self, &rawKey, &hx); \ + size_t idx = chash_##tag##_bucket(self, &rawKey, &hx); \ return self->_hashx[idx] ? &self->_table[idx] : NULL; \ } \ \ -static inline void _cmap_##tag##_reserveExpand(CMap_##tag* self) { \ - if (cmap_size(*self) + 1 >= cmap_bucketCount(*self) * self->maxLoadPercent * 0.01) \ - cmap_##tag##_reserve(self, (size_t) 7 + (1.6 * cmap_bucketCount(*self))); \ +static inline void _chash_##tag##_reserveExpand(CHash_##tag* self) { \ + if (chash_size(*self) + 1 >= chash_bucketCount(*self) * self->maxLoadPercent * 0.01) \ + chash_##tag##_reserve(self, (size_t) 7 + (1.6 * chash_bucketCount(*self))); \ } \ \ -STC_API CMapEntry_##tag* \ -cmap_##tag##_put(CMap_##tag* self, CMapRawKey_##tag rawKey, Value value) { \ - _cmap_##tag##_reserveExpand(self); \ +STC_API CHashEntry_##tag* \ +chash_##tag##_put(CHash_##tag* self, _chash2_##type(CHashRawKey_##tag rawKey, Value value)) { \ + _chash_##tag##_reserveExpand(self); \ uint32_t hx; \ - size_t idx = cmap_##tag##_bucket(self, &rawKey, &hx); \ - CMapEntry_##tag* e = &self->_table[idx]; \ + size_t idx = chash_##tag##_bucket(self, &rawKey, &hx); \ + CHashEntry_##tag* e = &self->_table[idx]; \ if (self->_hashx[idx]) \ - valueDestroy(&e->value); \ + _chash1_##type(valueDestroy(&e->value)) ; \ else { \ e->key = keyInitRaw(rawKey); \ self->_hashx[idx] = (uint8_t) hx; \ ++self->_size; \ } \ - e->value = value; \ + _chash1_##type(e->value = value;) \ return e; \ } \ \ -STC_API CMapEntry_##tag* \ -cmap_##tag##_find(CMap_##tag* self, CMapRawKey_##tag rawKey, CMapBucket_##tag* b) { \ - _cmap_##tag##_reserveExpand(self); \ +STC_API CHashEntry_##tag* \ +chash_##tag##_find(CHash_##tag* self, CHashRawKey_##tag rawKey, CHashBucket_##tag* b) { \ + _chash_##tag##_reserveExpand(self); \ b->rawKey = rawKey; \ - b->index = cmap_##tag##_bucket(self, &rawKey, &b->hashx); \ + b->index = chash_##tag##_bucket(self, &rawKey, &b->hashx); \ return self->_hashx[b->index] ? &self->_table[b->index] : NULL; \ } \ \ STC_API void \ -cmap_##tag##_insert(CMap_##tag* self, CMapBucket_##tag b, Value value) { \ - CMapEntry_##tag* e = &self->_table[b.index]; \ +chash_##tag##_insert(CHash_##tag* self, _chash2_##type(CHashBucket_##tag b, Value value)) { \ + CHashEntry_##tag* e = &self->_table[b.index]; \ if (self->_hashx[b.index]) \ - valueDestroy(&e->value); \ + _chash1_##type(valueDestroy(&e->value)) ; \ else { \ e->key = keyInitRaw(b.rawKey); \ self->_hashx[b.index] = (uint8_t) b.hashx; \ ++self->_size; \ } \ - e->value = value; \ + _chash1_##type(e->value = value;) \ } \ \ static inline void \ -cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \ - c_swap(CMap_##tag, *a, *b); \ +chash_##tag##_swap(CHash_##tag* a, CHash_##tag* b) { \ + c_swap(CHash_##tag, *a, *b); \ } \ \ STC_API size_t \ -cmap_##tag##_reserve(CMap_##tag* self, size_t newcap) { \ - size_t oldcap = cmap_bucketCount(*self); newcap |= 1; \ - if (cmap_size(*self) >= newcap * self->maxLoadPercent * 0.01) return oldcap; \ - CMap_##tag tmp = { \ - c_new_2(CMapEntry_##tag, newcap), \ +chash_##tag##_reserve(CHash_##tag* self, size_t newcap) { \ + size_t oldcap = chash_bucketCount(*self); newcap |= 1; \ + if (chash_size(*self) >= newcap * self->maxLoadPercent * 0.01) return oldcap; \ + CHash_##tag tmp = { \ + c_new_2(CHashEntry_##tag, newcap), \ (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ self->_size, (uint32_t) newcap, \ self->maxLoadPercent, self->shrinkLimitPercent \ }; \ - cmap_##tag##_swap(self, &tmp); \ + chash_##tag##_swap(self, &tmp); \ \ - CMapEntry_##tag* e = tmp._table, *slot = self->_table; \ + CHashEntry_##tag* e = tmp._table, *slot = self->_table; \ uint8_t* hashx = self->_hashx; \ uint32_t hx; \ for (size_t i = 0; i < oldcap; ++i, ++e) \ if (tmp._hashx[i]) { \ - CMapRawKey_##tag r = keyGetRaw(&e->key); \ - size_t idx = cmap_##tag##_bucket(self, &r, &hx); \ + CHashRawKey_##tag r = keyGetRaw(&e->key); \ + size_t idx = chash_##tag##_bucket(self, &r, &hx); \ slot[idx] = *e, \ hashx[idx] = (uint8_t) hx; \ } \ @@ -295,11 +311,11 @@ cmap_##tag##_reserve(CMap_##tag* self, size_t newcap) { \ } \ \ STC_API bool \ -cmap_##tag##_eraseBucket(CMap_##tag* self, size_t i) { \ - size_t j = i, k, cap = cmap_bucketCount(*self); \ - CMapEntry_##tag* slot = self->_table; \ +chash_##tag##_eraseBucket(CHash_##tag* self, size_t i) { \ + size_t j = i, k, cap = chash_bucketCount(*self); \ + CHashEntry_##tag* slot = self->_table; \ uint8_t* hashx = self->_hashx; \ - CMapRawKey_##tag r; \ + CHashRawKey_##tag r; \ if (! hashx[i]) \ return false; \ do { /* deletion from hash table without tombstone */ \ @@ -307,46 +323,46 @@ cmap_##tag##_eraseBucket(CMap_##tag* self, size_t i) { \ if (! hashx[j]) \ break; \ r = keyGetRaw(&slot[j].key); \ - k = cmap_reduce(keyHashRaw(&r, sizeof(CMapRawKey_##tag)), cap); \ + k = chash_reduce(keyHashRaw(&r, sizeof(CHashRawKey_##tag)), cap); \ if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ } while (true); \ hashx[i] = 0; \ - cmapentry_##tag##_destroy(&slot[i]); \ + chashentry_##tag##_destroy(&slot[i]); \ --self->_size; \ return true; \ } \ \ STC_API bool \ -cmap_##tag##_erase(CMap_##tag* self, CMapRawKey_##tag rawKey) { \ - if (cmap_size(*self) == 0) \ +chash_##tag##_erase(CHash_##tag* self, CHashRawKey_##tag rawKey) { \ + if (chash_size(*self) == 0) \ return false; \ - size_t cap = cmap_bucketCount(*self); \ - if (cmap_size(*self) < cap * self->shrinkLimitPercent * 0.01) \ - cmap_##tag##_reserve(self, cmap_size(*self) * 120 / self->maxLoadPercent); \ + size_t cap = chash_bucketCount(*self); \ + if (chash_size(*self) < cap * self->shrinkLimitPercent * 0.01) \ + chash_##tag##_reserve(self, chash_size(*self) * 120 / self->maxLoadPercent); \ uint32_t hx; \ - size_t i = cmap_##tag##_bucket(self, &rawKey, &hx); \ - return cmap_##tag##_eraseBucket(self, i); \ + size_t i = chash_##tag##_bucket(self, &rawKey, &hx); \ + return chash_##tag##_eraseBucket(self, i); \ } \ \ -STC_API cmap_##tag##_iter_t \ -cmap_##tag##_begin(CMap_##tag* map) { \ +STC_API chash_##tag##_iter_t \ +chash_##tag##_begin(CHash_##tag* map) { \ uint8_t* hx = map->_hashx; \ - CMapEntry_##tag* e = map->_table, *end = e + cmap_bucketCount(*map); \ + CHashEntry_##tag* e = map->_table, *end = e + chash_bucketCount(*map); \ while (e != end && !*hx) ++e, ++hx; \ - cmap_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return it; \ + chash_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return it; \ } \ \ -STC_API cmap_##tag##_iter_t \ -cmap_##tag##_next(cmap_##tag##_iter_t it) { \ +STC_API chash_##tag##_iter_t \ +chash_##tag##_next(chash_##tag##_iter_t it) { \ do { ++it.item, ++it._hx; } while (it.item != it._end && !*it._hx); \ if (it.item == it._end) it.item = NULL; \ return it; \ } #else -#define implement_CMap_10(tag, Key, Value, valueDestroy, keyDestroy, RawKey, \ - keyHashRaw, keyEqualsRaw, keyGetRaw, keyInitRaw) +#define implement_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) #endif #endif diff --git a/stc/copt.h b/stc/copt.h index 4c6af63d..78500210 100644 --- a/stc/copt.h +++ b/stc/copt.h @@ -20,21 +20,21 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ -#ifndef COPT__H__ -#define COPT__H__ +#ifndef COPTION__H__ +#define COPTION__H__ /* Inspired by https://attractivechaos.wordpress.com/2018/08/31/a-survey-of-argument-parsing-libraries-in-c-c Fixed major bugs with option arguments (both long and short). Added arg->faulty output field, and has a more consistent API. - copt_getopt() has a very similar interface to GNU's getopt_long(). Each call + coption_get() has a very similar interface to GNU's getopt_long(). Each call parses one option and returns the option name. opt->arg points to the option argument if present. The function returns -1 when all command-line arguments are parsed. In this case, opt->ind is the index of the first non-option argument. Example: int main(int argc, char *argv[]) { - struct copt_option longopts[] = { + COptLong longopts[] = { {"foo", copt_no_argument, 'f'}, {"bar", copt_required_argument, 'b'}, {"opt", copt_optional_argument, 'o'}, @@ -43,8 +43,8 @@ Example: const char* optstr = "xy:z::123"; printf("program -x -y ARG -z [ARG] -1 -2 -3 --foo --bar ARG --opt [ARG] [ARGUMENTS]\n"); int c; - copt_t opt = copt_init; - while ((c = copt_getopt(&opt, argc, argv, optstr, longopts)) != -1) { + COption opt = coption_init; + while ((c = coption_get(&opt, argc, argv, optstr, longopts)) != -1) { switch (c) { case '?': printf("error: unknown option: %s\n", opt.faulty); break; case ':': printf("error: missing argument for %s\n", opt.faulty); break; @@ -75,17 +75,17 @@ typedef struct { int longindex; /* idx of long option; or -1 if short */ int _i, _pos, _nargs; char _faulty[4]; -} copt_t; +} COption; -struct copt_option { +typedef struct { char *name; int has_arg; int val; -}; +} COptLong; -static const copt_t copt_init = {1, 0, NULL, NULL, -1, 1, 0, 0, {'-', '?', '\0'}}; +static const COption coption_init = {1, 0, NULL, NULL, -1, 1, 0, 0, {'-', '?', '\0'}}; -static void _copt_permute(char *argv[], int j, int n) { /* move argv[j] over n elements to the left */ +static void _coption_permute(char *argv[], int j, int n) { /* move argv[j] over n elements to the left */ int k; char *p = argv[j]; for (k = 0; k < n; ++k) @@ -93,13 +93,13 @@ static void _copt_permute(char *argv[], int j, int n) { /* move argv[j] over n e argv[j - k] = p; } -/* @param opt output; must be initialized to copt_init on first call - * @return ASCII val for a short option; longopt.val for a long option; - * -1 if argv[] is fully processed; '?' for an unknown option or - * an ambiguous long option; ':' if an option argument is missing +/* @param opt output; must be initialized to coption_init on first call + * @return ASCII val for a short option; longopt.val for a long option; + * -1 if argv[] is fully processed; '?' for an unknown option or + * an ambiguous long option; ':' if an option argument is missing */ -static int copt_getopt(copt_t *opt, int argc, char *argv[], - const char *shortopts, const struct copt_option *longopts) { +static int coption_get(COption *opt, int argc, char *argv[], + const char *shortopts, const COptLong *longopts) { int optc = -1, i0, j, posixly_correct = (shortopts[0] == '+'); if (!posixly_correct) { while (opt->_i < argc && (argv[opt->_i][0] != '-' || argv[opt->_i][1] == '\0')) @@ -112,14 +112,14 @@ static int copt_getopt(copt_t *opt, int argc, char *argv[], } if (argv[opt->_i][0] == '-' && argv[opt->_i][1] == '-') { /* "--" or a long option */ if (argv[opt->_i][2] == '\0') { /* a bare "--" */ - _copt_permute(argv, opt->_i, opt->_nargs); + _coption_permute(argv, opt->_i, opt->_nargs); ++opt->_i, opt->ind = opt->_i - opt->_nargs; return -1; } opt->opt = 0, optc = '?', opt->_pos = -1; if (longopts) { /* parse long options */ int k, n_exact = 0, n_partial = 0; - const struct copt_option *o = 0, *o_exact = 0, *o_partial = 0; + const COptLong *o = 0, *o_exact = 0, *o_partial = 0; for (j = 2; argv[opt->_i][j] != '\0' && argv[opt->_i][j] != '='; ++j) {} /* find the end of the option name */ for (k = 0; longopts[k].name != 0; ++k) if (strncmp(&argv[opt->_i][2], longopts[k].name, j - 2) == 0) { @@ -164,7 +164,7 @@ static int copt_getopt(copt_t *opt, int argc, char *argv[], ++opt->_i, opt->_pos = 0; if (opt->_nargs > 0) /* permute */ for (j = i0; j < opt->_i; ++j) - _copt_permute(argv, j, opt->_nargs); + _coption_permute(argv, j, opt->_nargs); } opt->ind = opt->_i - opt->_nargs; return optc; diff --git a/stc/cvector.h b/stc/cvector.h index 8b92018a..f85a5c1b 100644 --- a/stc/cvector.h +++ b/stc/cvector.h @@ -34,21 +34,23 @@ #define declare_CVector(...) c_MACRO_OVERLOAD(declare_CVector, __VA_ARGS__) #define declare_CVector_2(tag, Value) \ - declare_CVector_3(tag, Value, c_noDestroy) + declare_CVector_3(tag, Value, c_emptyDestroy) #define declare_CVector_3(tag, Value, valueDestroy) \ declare_CVector_4(tag, Value, valueDestroy, c_defaultCompare) #define declare_CVector_4(tag, Value, valueDestroy, valueCompare) \ - declare_CVector_6(tag, Value, valueDestroy, Value, valueCompare, c_defaultGetRaw) + declare_CVector_6(tag, Value, valueDestroy, valueCompare, Value, c_defaultGetRaw) #define declare_CVector_string(tag) \ - declare_CVector_6(tag, CString, cstring_destroy, const char*, cstring_compareRaw, cstring_getRaw) + declare_CVector_6(tag, CString, cstring_destroy, cstring_compareRaw, const char*, cstring_getRaw) -#define declare_CVector_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \ +#define declare_CVector_6(tag, Value, valueDestroy, valueCompareRaw, RawValue, valueGetRaw) \ \ typedef struct CVector_##tag { \ Value* data; \ } CVector_##tag; \ \ +STC_API CVector_##tag \ +cvector_##tag##_make(size_t size, Value null); \ STC_API void \ cvector_##tag##_destroy(CVector_##tag* self); \ STC_API void \ @@ -104,6 +106,15 @@ typedef RawValue CVectorRawValue_##tag #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_CVector_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \ \ +STC_API CVector_##tag \ +cvector_##tag##_make(size_t size, Value null) { \ + CVector_##tag vec = cvector_init; \ + cvector_##tag##_reserve(&vec, size); \ + _cvector_size(vec) = size; \ + for (size_t i=0; idata; \ @@ -184,7 +195,7 @@ cvector_##tag##_sort(CVector_##tag* self) { \ } #else -#define implement_CVector_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) +#define implement_CVector_6(tag, Value, valueDestroy, valueCompareRaw, RawValue, valueGetRaw) #endif #if defined(_WIN32) && defined(_DLL) -- cgit v1.2.3