From fc26b38cb71cbc98504f511192d8fa2124fd1e4e Mon Sep 17 00:00:00 2001 From: Tylo Date: Sun, 21 Jun 2020 15:26:22 +0200 Subject: Renamed files and classes: cmap -> chash, copt -> coption --- README.md | 12 +- advanced_example.c | 2 +- advanced_example.md | 22 ++-- benchmark.c | 2 +- demos.c | 2 +- stc/chash.h | 368 ++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/cmap.h | 368 ---------------------------------------------------- stc/copt.h | 173 ------------------------ stc/coption.h | 173 ++++++++++++++++++++++++ 9 files changed, 561 insertions(+), 561 deletions(-) create mode 100644 stc/chash.h delete mode 100644 stc/cmap.h delete mode 100644 stc/copt.h create mode 100644 stc/coption.h diff --git a/README.md b/README.md index 689a62bd..55862655 100644 --- a/README.md +++ b/README.md @@ -73,11 +73,11 @@ int main() { ``` CHash map of int -> int ``` -#include +#include declare_CHash(ii, map, int, int); int main() { - CHash_ii nums = cmap_init; + CHash_ii nums = chash_init; chash_ii_put(&nums, 8, 64); chash_ii_put(&nums, 11, 121); @@ -88,12 +88,12 @@ int main() { CHash set of CString ``` #include -#include +#include 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() { - CHash_s words = cmap_init; + CHash_s words = chash_init; chash_s_put(&words, "Hello"); chash_s_put(&words, "Groovy"); chash_s_erase(&words, "Hello"); @@ -107,11 +107,11 @@ int main() { CHash map of CString -> CString. Temporary CString values are created by "make", and moved to the container ``` #include -#include +#include declare_CHash_string(ss, map, CString, cstring_destroy); int main() { - CHash_ss table = cmap_init; + CHash_ss table = chash_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); diff --git a/advanced_example.c b/advanced_example.c index b85b433e..6649ab29 100644 --- a/advanced_example.c +++ b/advanced_example.c @@ -9,7 +9,7 @@ The difficulty with the hash function is that if your key type consists of sever Assuming a key-type like this, and want string as value, we define the functions person_make(), person_destroy() and person_compare(): ```*/ #include -#include "stc/cmap.h" +#include "stc/chash.h" #include "stc/cstring.h" struct Person { diff --git a/advanced_example.md b/advanced_example.md index 0206d4a2..031db20d 100644 --- a/advanced_example.md +++ b/advanced_example.md @@ -9,7 +9,8 @@ The difficulty with the hash function is that if your key type consists of sever Assuming a key-type like this, and want string as value, we define the functions person_make(), person_destroy() and person_compare(): ``` #include -#include + +#include #include struct Person { @@ -64,27 +65,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); + CMap_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. +CMap 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 CMap hash table itself. diff --git a/benchmark.c b/benchmark.c index 72e47699..7d0c9e48 100644 --- a/benchmark.c +++ b/benchmark.c @@ -1,6 +1,6 @@ #include "stc/crandom.h" #include "stc/cstring.h" -#include "stc/cmap.h" +#include "stc/chash.h" #include "others/khash.h" #include diff --git a/demos.c b/demos.c index 18be0e00..5735a900 100644 --- a/demos.c +++ b/demos.c @@ -1,6 +1,6 @@ #include "stc/cvector.h" #include "stc/clist.h" -#include "stc/cmap.h" +#include "stc/chash.h" #include "stc/cstring.h" diff --git a/stc/chash.h b/stc/chash.h new file mode 100644 index 00000000..a53f7d75 --- /dev/null +++ b/stc/chash.h @@ -0,0 +1,368 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* // Example: +#include +#include "stc/cmap.h" +declare_CHash(sx, set, int); +declare_CHash(mx, map, int, char); + +int main(void) { + 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 CHASH__H__ +#define CHASH__H__ + +#include +#include "cdefs.h" + +#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 chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) + +enum {chash_HASH = 0x7f, chash_USED = 0x80}; + +/* CHash: */ +#define declare_CHash(...) \ + c_MACRO_OVERLOAD(declare_CHash, __VA_ARGS__) + +#define declare_CHash_3(tag, type, Key) \ + declare_CHash_4(tag, type, Key, void) + +#define declare_CHash_4(tag, type, Key, Value) \ + declare_CHash_5(tag, type, Key, Value, c_emptyDestroy) + +#define declare_CHash_5(tag, type, Key, Value, valueDestroy) \ + declare_CHash_6(tag, type, Key, Value, valueDestroy, c_defaultHash) + +#define declare_CHash_6(tag, type, Key, Value, valueDestroy, keyHash) \ + declare_CHash_7(tag, type, Key, Value, valueDestroy, keyHash, c_defaultEquals) + +#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__) + +#define declare_CHash_string_2(tag, type) \ + declare_CHash_string_3(tag, type, void) + +#define declare_CHash_string_3(tag, type, Value) \ + declare_CHash_string_4(tag, type, Value, c_emptyDestroy) + +#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 + +/* CHash full: */ +#define declare_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ +typedef struct CHashEntry_##tag { \ + Key key; \ + _chash1_##type(Value value;) \ +} CHashEntry_##tag; \ + \ +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 \ +chashentry_##tag##_destroy(CHashEntry_##tag* e) { \ + keyDestroy(&e->key); \ + _chash1_##type(valueDestroy(&e->value);) \ +} \ + \ +typedef RawKey CHashRawKey_##tag; \ + \ +typedef struct CHash_##tag { \ + CHashEntry_##tag* _table; \ + uint8_t* _hashx; \ + uint32_t _size, _cap; \ + uint8_t maxLoadPercent; \ + uint8_t shrinkLimitPercent; \ +} CHash_##tag; \ + \ +typedef struct { \ + CHashEntry_##tag *item, *_end; \ + uint8_t* _hx; \ +} CHashIter_##tag, chash_##tag##_iter_t; \ + \ +typedef struct { \ + CHashRawKey_##tag rawKey; \ + size_t index; \ + uint32_t hashx; \ +} CHashBucket_##tag; \ + \ +STC_API void \ +chash_##tag##_destroy(CHash_##tag* self); \ +STC_API void \ +chash_##tag##_clear(CHash_##tag* self); \ +STC_API void \ +chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac); \ +STC_API void \ +chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit); \ +STC_API size_t \ +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 \ +chash_##tag##_insert(CHash_##tag* self, _chash2_##type(CHashBucket_##tag b, Value value)); \ +STC_API size_t \ +chash_##tag##_reserve(CHash_##tag* self, size_t size); \ +STC_API bool \ +chash_##tag##_eraseBucket(CHash_##tag* self, size_t i); \ +STC_API bool \ +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_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_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ + \ +STC_API void \ +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++) chashentry_##tag##_destroy(e); \ + } \ + free(self->_hashx); \ + free(self->_table); \ +} \ + \ +STC_API void chash_##tag##_clear(CHash_##tag* self) { \ + chash_##tag##_destroy(self); \ + self->_cap = self->_size = 0; \ +} \ + \ +STC_API void \ +chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac) { \ + self->maxLoadPercent = (uint8_t) (fac * 100); \ + if (chash_size(*self) >= chash_bucketCount(*self) * fac) \ + chash_##tag##_reserve(self, (size_t) (chash_size(*self) / fac)); \ +} \ + \ +STC_API void \ +chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit) { \ + self->shrinkLimitPercent = (uint8_t) (limit * 100); \ + if (chash_size(*self) < chash_bucketCount(*self) * limit) \ + chash_##tag##_reserve(self, (size_t) (chash_size(*self) * 1.2 / limit)); \ +} \ + \ +STC_API size_t \ +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) { \ + CHashRawKey_##tag r = keyGetRaw(&self->_table[idx].key); \ + if (keyEqualsRaw(&r, rawKeyPtr)) break; \ + } \ + if (++idx == cap) idx = 0; \ + } \ + *hxPtr = hx; \ + return idx; \ +} \ + \ +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 = chash_##tag##_bucket(self, &rawKey, &hx); \ + return self->_hashx[idx] ? &self->_table[idx] : NULL; \ +} \ + \ +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 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 = chash_##tag##_bucket(self, &rawKey, &hx); \ + CHashEntry_##tag* e = &self->_table[idx]; \ + if (self->_hashx[idx]) \ + _chash1_##type(valueDestroy(&e->value)) ; \ + else { \ + e->key = keyInitRaw(rawKey); \ + self->_hashx[idx] = (uint8_t) hx; \ + ++self->_size; \ + } \ + _chash1_##type(e->value = value;) \ + return e; \ +} \ + \ +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 = chash_##tag##_bucket(self, &rawKey, &b->hashx); \ + return self->_hashx[b->index] ? &self->_table[b->index] : NULL; \ +} \ + \ +STC_API void \ +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]) \ + _chash1_##type(valueDestroy(&e->value)) ; \ + else { \ + e->key = keyInitRaw(b.rawKey); \ + self->_hashx[b.index] = (uint8_t) b.hashx; \ + ++self->_size; \ + } \ + _chash1_##type(e->value = value;) \ +} \ + \ +static inline void \ +chash_##tag##_swap(CHash_##tag* a, CHash_##tag* b) { \ + c_swap(CHash_##tag, *a, *b); \ +} \ + \ +STC_API size_t \ +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 \ + }; \ + chash_##tag##_swap(self, &tmp); \ + \ + 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]) { \ + CHashRawKey_##tag r = keyGetRaw(&e->key); \ + size_t idx = chash_##tag##_bucket(self, &r, &hx); \ + slot[idx] = *e, \ + hashx[idx] = (uint8_t) hx; \ + } \ + free(tmp._hashx); \ + free(tmp._table); \ + return newcap; \ +} \ + \ +STC_API bool \ +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; \ + CHashRawKey_##tag r; \ + if (! hashx[i]) \ + return false; \ + do { /* deletion from hash table without tombstone */ \ + if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ + if (! hashx[j]) \ + break; \ + r = keyGetRaw(&slot[j].key); \ + 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; \ + chashentry_##tag##_destroy(&slot[i]); \ + --self->_size; \ + return true; \ +} \ + \ +STC_API bool \ +chash_##tag##_erase(CHash_##tag* self, CHashRawKey_##tag rawKey) { \ + if (chash_size(*self) == 0) \ + return false; \ + 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 = chash_##tag##_bucket(self, &rawKey, &hx); \ + return chash_##tag##_eraseBucket(self, i); \ +} \ + \ +STC_API chash_##tag##_iter_t \ +chash_##tag##_begin(CHash_##tag* map) { \ + uint8_t* hx = map->_hashx; \ + CHashEntry_##tag* e = map->_table, *end = e + chash_bucketCount(*map); \ + while (e != end && !*hx) ++e, ++hx; \ + chash_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return 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_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ + RawKey, keyDestroy, keyGetRaw, keyInitRaw) +#endif + +#endif diff --git a/stc/cmap.h b/stc/cmap.h deleted file mode 100644 index a53f7d75..00000000 --- a/stc/cmap.h +++ /dev/null @@ -1,368 +0,0 @@ -/* MIT License - * - * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -/* // Example: -#include -#include "stc/cmap.h" -declare_CHash(sx, set, int); -declare_CHash(mx, map, int, char); - -int main(void) { - 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 CHASH__H__ -#define CHASH__H__ - -#include -#include "cdefs.h" - -#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 chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) - -enum {chash_HASH = 0x7f, chash_USED = 0x80}; - -/* CHash: */ -#define declare_CHash(...) \ - c_MACRO_OVERLOAD(declare_CHash, __VA_ARGS__) - -#define declare_CHash_3(tag, type, Key) \ - declare_CHash_4(tag, type, Key, void) - -#define declare_CHash_4(tag, type, Key, Value) \ - declare_CHash_5(tag, type, Key, Value, c_emptyDestroy) - -#define declare_CHash_5(tag, type, Key, Value, valueDestroy) \ - declare_CHash_6(tag, type, Key, Value, valueDestroy, c_defaultHash) - -#define declare_CHash_6(tag, type, Key, Value, valueDestroy, keyHash) \ - declare_CHash_7(tag, type, Key, Value, valueDestroy, keyHash, c_defaultEquals) - -#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__) - -#define declare_CHash_string_2(tag, type) \ - declare_CHash_string_3(tag, type, void) - -#define declare_CHash_string_3(tag, type, Value) \ - declare_CHash_string_4(tag, type, Value, c_emptyDestroy) - -#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 - -/* CHash full: */ -#define declare_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ -typedef struct CHashEntry_##tag { \ - Key key; \ - _chash1_##type(Value value;) \ -} CHashEntry_##tag; \ - \ -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 \ -chashentry_##tag##_destroy(CHashEntry_##tag* e) { \ - keyDestroy(&e->key); \ - _chash1_##type(valueDestroy(&e->value);) \ -} \ - \ -typedef RawKey CHashRawKey_##tag; \ - \ -typedef struct CHash_##tag { \ - CHashEntry_##tag* _table; \ - uint8_t* _hashx; \ - uint32_t _size, _cap; \ - uint8_t maxLoadPercent; \ - uint8_t shrinkLimitPercent; \ -} CHash_##tag; \ - \ -typedef struct { \ - CHashEntry_##tag *item, *_end; \ - uint8_t* _hx; \ -} CHashIter_##tag, chash_##tag##_iter_t; \ - \ -typedef struct { \ - CHashRawKey_##tag rawKey; \ - size_t index; \ - uint32_t hashx; \ -} CHashBucket_##tag; \ - \ -STC_API void \ -chash_##tag##_destroy(CHash_##tag* self); \ -STC_API void \ -chash_##tag##_clear(CHash_##tag* self); \ -STC_API void \ -chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac); \ -STC_API void \ -chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit); \ -STC_API size_t \ -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 \ -chash_##tag##_insert(CHash_##tag* self, _chash2_##type(CHashBucket_##tag b, Value value)); \ -STC_API size_t \ -chash_##tag##_reserve(CHash_##tag* self, size_t size); \ -STC_API bool \ -chash_##tag##_eraseBucket(CHash_##tag* self, size_t i); \ -STC_API bool \ -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_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_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ - RawKey, keyDestroy, keyGetRaw, keyInitRaw) \ - \ -STC_API void \ -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++) chashentry_##tag##_destroy(e); \ - } \ - free(self->_hashx); \ - free(self->_table); \ -} \ - \ -STC_API void chash_##tag##_clear(CHash_##tag* self) { \ - chash_##tag##_destroy(self); \ - self->_cap = self->_size = 0; \ -} \ - \ -STC_API void \ -chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac) { \ - self->maxLoadPercent = (uint8_t) (fac * 100); \ - if (chash_size(*self) >= chash_bucketCount(*self) * fac) \ - chash_##tag##_reserve(self, (size_t) (chash_size(*self) / fac)); \ -} \ - \ -STC_API void \ -chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit) { \ - self->shrinkLimitPercent = (uint8_t) (limit * 100); \ - if (chash_size(*self) < chash_bucketCount(*self) * limit) \ - chash_##tag##_reserve(self, (size_t) (chash_size(*self) * 1.2 / limit)); \ -} \ - \ -STC_API size_t \ -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) { \ - CHashRawKey_##tag r = keyGetRaw(&self->_table[idx].key); \ - if (keyEqualsRaw(&r, rawKeyPtr)) break; \ - } \ - if (++idx == cap) idx = 0; \ - } \ - *hxPtr = hx; \ - return idx; \ -} \ - \ -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 = chash_##tag##_bucket(self, &rawKey, &hx); \ - return self->_hashx[idx] ? &self->_table[idx] : NULL; \ -} \ - \ -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 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 = chash_##tag##_bucket(self, &rawKey, &hx); \ - CHashEntry_##tag* e = &self->_table[idx]; \ - if (self->_hashx[idx]) \ - _chash1_##type(valueDestroy(&e->value)) ; \ - else { \ - e->key = keyInitRaw(rawKey); \ - self->_hashx[idx] = (uint8_t) hx; \ - ++self->_size; \ - } \ - _chash1_##type(e->value = value;) \ - return e; \ -} \ - \ -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 = chash_##tag##_bucket(self, &rawKey, &b->hashx); \ - return self->_hashx[b->index] ? &self->_table[b->index] : NULL; \ -} \ - \ -STC_API void \ -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]) \ - _chash1_##type(valueDestroy(&e->value)) ; \ - else { \ - e->key = keyInitRaw(b.rawKey); \ - self->_hashx[b.index] = (uint8_t) b.hashx; \ - ++self->_size; \ - } \ - _chash1_##type(e->value = value;) \ -} \ - \ -static inline void \ -chash_##tag##_swap(CHash_##tag* a, CHash_##tag* b) { \ - c_swap(CHash_##tag, *a, *b); \ -} \ - \ -STC_API size_t \ -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 \ - }; \ - chash_##tag##_swap(self, &tmp); \ - \ - 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]) { \ - CHashRawKey_##tag r = keyGetRaw(&e->key); \ - size_t idx = chash_##tag##_bucket(self, &r, &hx); \ - slot[idx] = *e, \ - hashx[idx] = (uint8_t) hx; \ - } \ - free(tmp._hashx); \ - free(tmp._table); \ - return newcap; \ -} \ - \ -STC_API bool \ -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; \ - CHashRawKey_##tag r; \ - if (! hashx[i]) \ - return false; \ - do { /* deletion from hash table without tombstone */ \ - if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ - if (! hashx[j]) \ - break; \ - r = keyGetRaw(&slot[j].key); \ - 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; \ - chashentry_##tag##_destroy(&slot[i]); \ - --self->_size; \ - return true; \ -} \ - \ -STC_API bool \ -chash_##tag##_erase(CHash_##tag* self, CHashRawKey_##tag rawKey) { \ - if (chash_size(*self) == 0) \ - return false; \ - 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 = chash_##tag##_bucket(self, &rawKey, &hx); \ - return chash_##tag##_eraseBucket(self, i); \ -} \ - \ -STC_API chash_##tag##_iter_t \ -chash_##tag##_begin(CHash_##tag* map) { \ - uint8_t* hx = map->_hashx; \ - CHashEntry_##tag* e = map->_table, *end = e + chash_bucketCount(*map); \ - while (e != end && !*hx) ++e, ++hx; \ - chash_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return 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_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 deleted file mode 100644 index 78500210..00000000 --- a/stc/copt.h +++ /dev/null @@ -1,173 +0,0 @@ -/* MIT License - * - * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -#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. - - 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[]) - { - COptLong longopts[] = { - {"foo", copt_no_argument, 'f'}, - {"bar", copt_required_argument, 'b'}, - {"opt", copt_optional_argument, 'o'}, - {NULL} - }; - 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; - 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; - default: printf("option: %c [%s]\n", c, opt.arg ? opt.arg : ""); break; - } - } - printf("\nNon-option arguments:"); - for (int i = opt.ind; i < argc; ++i) - printf(" %s", argv[i]); - putchar('\n'); - return 0; - } -*/ - -#include -#include - -enum { - copt_no_argument = 0, - copt_required_argument = 1, - copt_optional_argument = 2 -}; -typedef struct { - int ind; /* equivalent to optind */ - int opt; /* equivalent to optopt */ - char *arg; /* equivalent to optarg */ - char *faulty; /* points to the faulty option */ - int longindex; /* idx of long option; or -1 if short */ - int _i, _pos, _nargs; - char _faulty[4]; -} COption; - -typedef struct { - char *name; - int has_arg; - int val; -} COptLong; - -static const COption coption_init = {1, 0, NULL, NULL, -1, 1, 0, 0, {'-', '?', '\0'}}; - -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) - argv[j - k] = argv[j - k - 1]; - argv[j - k] = p; -} - -/* @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 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')) - ++opt->_i, ++opt->_nargs; - } - opt->arg = 0, opt->longindex = -1, i0 = opt->_i; - if (opt->_i >= argc || argv[opt->_i][0] != '-' || argv[opt->_i][1] == '\0') { - opt->ind = opt->_i - opt->_nargs; - return -1; - } - if (argv[opt->_i][0] == '-' && argv[opt->_i][1] == '-') { /* "--" or a long option */ - if (argv[opt->_i][2] == '\0') { /* a bare "--" */ - _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 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) { - if (longopts[k].name[j - 2] == 0) ++n_exact, o_exact = &longopts[k]; - else ++n_partial, o_partial = &longopts[k]; - } - opt->faulty = argv[opt->_i]; - if (n_exact > 1 || (n_exact == 0 && n_partial > 1)) return '?'; - o = n_exact == 1? o_exact : n_partial == 1? o_partial : 0; - if (o) { - opt->opt = optc = o->val, opt->longindex = o - longopts; - if (o->has_arg != copt_no_argument) { - if (argv[opt->_i][j] == '=') - opt->arg = &argv[opt->_i][j + 1]; - else if (argv[opt->_i][j] == '\0' && opt->_i < argc - 1 && (o->has_arg == copt_required_argument || - argv[opt->_i + 1][0] != '-')) - opt->arg = argv[++opt->_i]; - else if (o->has_arg == copt_required_argument) - optc = ':'; /* missing option argument */ - } - } - } - } else { /* a short option */ - const char *p; - if (opt->_pos == 0) opt->_pos = 1; - optc = opt->opt = argv[opt->_i][opt->_pos++]; - opt->_faulty[1] = optc, opt->faulty = opt->_faulty; - p = strchr((char *) shortopts, optc); - if (p == 0) { - optc = '?'; /* unknown option */ - } else if (p[1] == ':') { - if (argv[opt->_i][opt->_pos] != '\0') - opt->arg = &argv[opt->_i][opt->_pos]; - else if (opt->_i < argc - 1 && (p[2] != ':' || argv[opt->_i + 1][0] != '-')) - opt->arg = argv[++opt->_i]; - else if (p[2] != ':') - optc = ':'; - opt->_pos = -1; - } - } - if (opt->_pos < 0 || argv[opt->_i][opt->_pos] == 0) { - ++opt->_i, opt->_pos = 0; - if (opt->_nargs > 0) /* permute */ - for (j = i0; j < opt->_i; ++j) - _coption_permute(argv, j, opt->_nargs); - } - opt->ind = opt->_i - opt->_nargs; - return optc; -} - -#endif diff --git a/stc/coption.h b/stc/coption.h new file mode 100644 index 00000000..78500210 --- /dev/null +++ b/stc/coption.h @@ -0,0 +1,173 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +#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. + + 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[]) + { + COptLong longopts[] = { + {"foo", copt_no_argument, 'f'}, + {"bar", copt_required_argument, 'b'}, + {"opt", copt_optional_argument, 'o'}, + {NULL} + }; + 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; + 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; + default: printf("option: %c [%s]\n", c, opt.arg ? opt.arg : ""); break; + } + } + printf("\nNon-option arguments:"); + for (int i = opt.ind; i < argc; ++i) + printf(" %s", argv[i]); + putchar('\n'); + return 0; + } +*/ + +#include +#include + +enum { + copt_no_argument = 0, + copt_required_argument = 1, + copt_optional_argument = 2 +}; +typedef struct { + int ind; /* equivalent to optind */ + int opt; /* equivalent to optopt */ + char *arg; /* equivalent to optarg */ + char *faulty; /* points to the faulty option */ + int longindex; /* idx of long option; or -1 if short */ + int _i, _pos, _nargs; + char _faulty[4]; +} COption; + +typedef struct { + char *name; + int has_arg; + int val; +} COptLong; + +static const COption coption_init = {1, 0, NULL, NULL, -1, 1, 0, 0, {'-', '?', '\0'}}; + +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) + argv[j - k] = argv[j - k - 1]; + argv[j - k] = p; +} + +/* @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 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')) + ++opt->_i, ++opt->_nargs; + } + opt->arg = 0, opt->longindex = -1, i0 = opt->_i; + if (opt->_i >= argc || argv[opt->_i][0] != '-' || argv[opt->_i][1] == '\0') { + opt->ind = opt->_i - opt->_nargs; + return -1; + } + if (argv[opt->_i][0] == '-' && argv[opt->_i][1] == '-') { /* "--" or a long option */ + if (argv[opt->_i][2] == '\0') { /* a bare "--" */ + _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 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) { + if (longopts[k].name[j - 2] == 0) ++n_exact, o_exact = &longopts[k]; + else ++n_partial, o_partial = &longopts[k]; + } + opt->faulty = argv[opt->_i]; + if (n_exact > 1 || (n_exact == 0 && n_partial > 1)) return '?'; + o = n_exact == 1? o_exact : n_partial == 1? o_partial : 0; + if (o) { + opt->opt = optc = o->val, opt->longindex = o - longopts; + if (o->has_arg != copt_no_argument) { + if (argv[opt->_i][j] == '=') + opt->arg = &argv[opt->_i][j + 1]; + else if (argv[opt->_i][j] == '\0' && opt->_i < argc - 1 && (o->has_arg == copt_required_argument || + argv[opt->_i + 1][0] != '-')) + opt->arg = argv[++opt->_i]; + else if (o->has_arg == copt_required_argument) + optc = ':'; /* missing option argument */ + } + } + } + } else { /* a short option */ + const char *p; + if (opt->_pos == 0) opt->_pos = 1; + optc = opt->opt = argv[opt->_i][opt->_pos++]; + opt->_faulty[1] = optc, opt->faulty = opt->_faulty; + p = strchr((char *) shortopts, optc); + if (p == 0) { + optc = '?'; /* unknown option */ + } else if (p[1] == ':') { + if (argv[opt->_i][opt->_pos] != '\0') + opt->arg = &argv[opt->_i][opt->_pos]; + else if (opt->_i < argc - 1 && (p[2] != ':' || argv[opt->_i + 1][0] != '-')) + opt->arg = argv[++opt->_i]; + else if (p[2] != ':') + optc = ':'; + opt->_pos = -1; + } + } + if (opt->_pos < 0 || argv[opt->_i][opt->_pos] == 0) { + ++opt->_i, opt->_pos = 0; + if (opt->_nargs > 0) /* permute */ + for (j = i0; j < opt->_i; ++j) + _coption_permute(argv, j, opt->_nargs); + } + opt->ind = opt->_i - opt->_nargs; + return optc; +} + +#endif -- cgit v1.2.3