From 2c1382a7cefea370a321ba00e83bcf29df48e5fd Mon Sep 17 00:00:00 2001 From: Tylo Date: Thu, 18 Jun 2020 15:42:36 +0200 Subject: Added cmap_eraseBucket, and split cmap_erase in two. Cleanup white spaces and comments/examples. --- stc/clist.h | 41 +++++++++++++---------------------------- stc/cmap.h | 49 ++++++++++++++++++++++++------------------------- stc/cvector.h | 13 ------------- 3 files changed, 37 insertions(+), 66 deletions(-) diff --git a/stc/clist.h b/stc/clist.h index eba49d1a..ae294705 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -41,18 +41,16 @@ CList_i list = clist_init; CList_s slist = clist_init; int n; - - // Add one million random numbers... - for (int i=0; i<1000000; ++i) + for (int i=0; i<1000000; ++i) // one million clist_i_pushBack(&list, rand() * rand()); n = 0; c_foreach (i, clist_i, list) - if (++n % 10000 == 0) printf("%d: %lld\n", n, i.item->value); + if (++n % 10000 == 0) printf("%d: %zd\n", n, i.item->value); // Sort them... clist_i_sort(&list); // mergesort O(n*log n) n = 0; c_foreach (i, clist_i, list) - if (++n % 10000 == 0) printf("%d: %lld\n", n, i.item->value); + if (++n % 10000 == 0) printf("%d: %zd\n", n, i.item->value); clist_i_destroy(&list); // Test CList with CStrings @@ -60,13 +58,13 @@ clist_s_pushBack(&slist, cstring_make("Item 2")); clist_s_pushBack(&slist, cstring_make("Item X")); clist_s_pushBack(&slist, cstring_make("Item 3")); - printf("\n"); + puts(""); c_foreach (i, clist_s, slist) printf("%s\n", i.item->value.str); - // Change the list... + // Modify clist_s_pushFront(&slist, cstring_make("Item 0")); clist_s_remove(&slist, "Item X"); - printf("\n"); + puts(""); c_foreach (i, clist_s, slist) printf("%s\n", i.item->value.str); clist_s_destroy(&slist); @@ -110,37 +108,26 @@ \ STC_API void \ clist_##tag##_destroy(CList_##tag* self); \ - \ + STC_API void \ + clist_##tag##_pushBack(CList_##tag* self, Value value); \ STC_API void \ clist_##tag##_pushFront(CList_##tag* self, Value value); \ - \ STC_API void \ clist_##tag##_popFront(CList_##tag* self); \ - \ - STC_API void \ - clist_##tag##_pushBack(CList_##tag* self, Value value); \ - \ STC_API void \ clist_##tag##_insertAfter(CList_##tag* self, clist_##tag##_iter_t pos, Value value); \ - \ STC_API void \ clist_##tag##_eraseAfter(CList_##tag* self, clist_##tag##_iter_t pos); \ - \ STC_API void \ clist_##tag##_spliceFront(CList_##tag* self, CList_##tag* other); \ - \ STC_API void \ clist_##tag##_spliceAfter(CList_##tag* self, clist_##tag##_iter_t pos, CList_##tag* other); \ - \ STC_API clist_##tag##_iter_t \ clist_##tag##_findBefore(CList_##tag* self, RawValue val); \ - \ STC_API Value* \ clist_##tag##_find(CList_##tag* self, RawValue val); \ - \ STC_API clist_##tag##_iter_t \ clist_##tag##_remove(CList_##tag* self, RawValue val); \ - \ STC_API void \ clist_##tag##_sort(CList_##tag* self); \ \ @@ -174,6 +161,11 @@ clist_##tag##_popFront(self); \ } \ \ + STC_API void \ + clist_##tag##_pushBack(CList_##tag* self, Value value) { \ + _clist_insertAfter(self, tag, self->last, value); \ + self->last = entry; \ + } \ STC_API void \ clist_##tag##_pushFront(CList_##tag* self, Value value) { \ _clist_insertAfter(self, tag, self->last, value); \ @@ -183,19 +175,12 @@ clist_##tag##_popFront(CList_##tag* self) { \ _clist_eraseAfter(self, tag, self->last, valueDestroy); \ } \ - \ - STC_API void \ - clist_##tag##_pushBack(CList_##tag* self, Value value) { \ - _clist_insertAfter(self, tag, self->last, value); \ - self->last = entry; \ - } \ \ STC_API void \ clist_##tag##_insertAfter(CList_##tag* self, clist_##tag##_iter_t pos, Value value) { \ _clist_insertAfter(self, tag, pos.item, value); \ if (!self->last || pos.item == self->last) self->last = entry; \ } \ - \ STC_API void \ clist_##tag##_eraseAfter(CList_##tag* self, clist_##tag##_iter_t pos) { \ _clist_eraseAfter(self, tag, pos.item, valueDestroy); \ diff --git a/stc/cmap.h b/stc/cmap.h index cfe57519..0aef3f14 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -30,9 +30,10 @@ int main(void) { CMap_ex h = cmap_init; cmap_ex_put(&h, 5, 'a'); cmap_ex_put(&h, 8, 'b'); - CMapEntry_ex* b = cmap_ex_get(h, 10); // = NULL - char val = cmap_ex_get(h, 5)->value; - cmap_ex_put(&h, 5, 'd'); + 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); @@ -123,43 +124,35 @@ typedef struct { \ \ STC_API void \ cmap_##tag##_destroy(CMap_##tag* self); \ - \ STC_API void \ cmap_##tag##_clear(CMap_##tag* self); \ - \ STC_API void \ cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, double fac); \ - \ STC_API void \ cmap_##tag##_setShrinkLimitFactor(CMap_##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); \ - \ STC_API void \ cmap_##tag##_insert(CMap_##tag* self, CMapBucket_##tag b, Value value); \ - \ STC_API size_t \ cmap_##tag##_reserve(CMap_##tag* self, size_t size); \ - \ +STC_API bool \ +cmap_##tag##_eraseBucket(CMap_##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); \ \ implement_CMap_10(tag, Key, Value, valueDestroy, keyDestroy, RawKey, \ keyHashRaw, keyEqualsRaw, keyGetRaw, keyInitRaw) \ - \ typedef Key CMapKey_##tag; \ typedef Value CMapValue_##tag @@ -200,7 +193,7 @@ cmap_##tag##_setShrinkLimitFactor(CMap_##tag* self, double limit) { \ cmap_##tag##_reserve(self, (size_t) (cmap_size(*self) * 1.2 / limit)); \ } \ \ -static inline size_t \ +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; \ @@ -302,21 +295,15 @@ cmap_##tag##_reserve(CMap_##tag* self, size_t newcap) { \ } \ \ STC_API bool \ -cmap_##tag##_erase(CMap_##tag* self, CMapRawKey_##tag rawKey) { \ - if (cmap_size(*self) == 0) \ - return false; \ - size_t cap = cmap_bucketCount(*self); \ - if (cmap_size(*self) < cap * self->shrinkLimitPercent * 0.01) \ - cap = cmap_##tag##_reserve(self, cmap_size(*self) * 120 / self->maxLoadPercent); \ - uint32_t hx; \ - size_t i = cmap_##tag##_bucket(self, &rawKey, &hx), j = i, k; \ +cmap_##tag##_eraseBucket(CMap_##tag* self, size_t i) { \ + size_t j = i, k, cap = cmap_bucketCount(*self); \ CMapEntry_##tag* slot = self->_table; \ uint8_t* hashx = self->_hashx; \ CMapRawKey_##tag r; \ if (! hashx[i]) \ return false; \ do { /* deletion from hash table without tombstone */ \ - if (++j == cap) j = 0; /* ++j %= cap; is slow */ \ + if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ if (! hashx[j]) \ break; \ r = keyGetRaw(&slot[j].key); \ @@ -330,6 +317,18 @@ cmap_##tag##_erase(CMap_##tag* self, CMapRawKey_##tag rawKey) { \ return true; \ } \ \ +STC_API bool \ +cmap_##tag##_erase(CMap_##tag* self, CMapRawKey_##tag rawKey) { \ + if (cmap_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); \ + uint32_t hx; \ + size_t i = cmap_##tag##_bucket(self, &rawKey, &hx); \ + return cmap_##tag##_eraseBucket(self, i); \ +} \ + \ STC_API cmap_##tag##_iter_t \ cmap_##tag##_begin(CMap_##tag* map) { \ uint8_t* hx = map->_hashx; \ diff --git a/stc/cvector.h b/stc/cvector.h index cee33e27..8b92018a 100644 --- a/stc/cvector.h +++ b/stc/cvector.h @@ -51,45 +51,34 @@ typedef struct CVector_##tag { \ \ STC_API void \ cvector_##tag##_destroy(CVector_##tag* self); \ - \ STC_API void \ cvector_##tag##_reserve(CVector_##tag* self, size_t cap); \ - \ STC_API void \ cvector_##tag##_clear(CVector_##tag* self); \ - \ STC_API void \ cvector_##tag##_pushBack(CVector_##tag* self, Value value); \ - \ static inline void \ cvector_##tag##_popBack(CVector_##tag* self) { \ valueDestroy(&self->data[_cvector_size(*self) - 1]); \ --_cvector_size(*self); \ } \ - \ static inline Value \ cvector_##tag##_back(CVector_##tag cv) { \ return cv.data[_cvector_size(cv) - 1]; \ } \ - \ STC_API void \ cvector_##tag##_insert(CVector_##tag* self, size_t pos, Value value); \ - \ STC_API void \ cvector_##tag##_erase(CVector_##tag* self, size_t pos, size_t size); \ - \ STC_API void \ cvector_##tag##_sort(CVector_##tag* self); \ - \ STC_API size_t \ cvector_##tag##_find(CVector_##tag cv, RawValue rawValue); \ - \ static inline void \ cvector_##tag##_swap(CVector_##tag* a, CVector_##tag* b) { \ c_swap(Value*, a->data, b->data); \ } \ \ - \ typedef struct { \ Value *item, *end; \ } CVectorIter_##tag, cvector_##tag##_iter_t; \ @@ -100,7 +89,6 @@ cvector_##tag##_begin(CVector_##tag* vec) { \ cvector_##tag##_iter_t it = {n ? vec->data : NULL, vec->data + n}; \ return it; \ } \ - \ static inline cvector_##tag##_iter_t \ cvector_##tag##_next(cvector_##tag##_iter_t it) { \ if (++it.item == it.end) it.item = NULL; \ @@ -108,7 +96,6 @@ cvector_##tag##_next(cvector_##tag##_iter_t it) { \ } \ \ implement_CVector_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \ - \ typedef Value CVectorValue_##tag; \ typedef RawValue CVectorRawValue_##tag -- cgit v1.2.3