From 13f25229cfa7a3ec2215656c29783df7c63c7164 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 29 Apr 2021 19:33:15 +0200 Subject: Added new constructors to carray.h. Made cmap and csmap keys immutable. Added get() method to cmap and csmap. --- docs/carray_api.md | 52 +++++++++++++++-------------- docs/cmap_api.md | 5 +-- docs/cset_api.md | 21 ++++++------ docs/csmap_api.md | 11 +++--- docs/csset_api.md | 25 +++++++------- examples/advanced.c | 2 +- examples/complex.c | 2 +- examples/demos.c | 22 ++++++------ examples/ex_gauss1.c | 8 +++-- stc/carray.h | 62 ++++++++++++++++++---------------- stc/cmap.h | 79 ++++++++++++++++++++++--------------------- stc/csmap.h | 94 +++++++++++++++++++++++++--------------------------- 12 files changed, 198 insertions(+), 185 deletions(-) diff --git a/docs/carray_api.md b/docs/carray_api.md index 3fbd8c37..51688fd3 100644 --- a/docs/carray_api.md +++ b/docs/carray_api.md @@ -28,14 +28,15 @@ be replaced by `i` in all of the following documentation. ## Methods ```c -carray2X carray2X_init(size_t xdim, size_t ydim, Value val); -carray2X carray2X_from(Value* array, size_t xdim, size_t ydim); +carray2X carray2X_init(size_t xdim, size_t ydim); +carray2X carray2X_with_value(size_t xdim, size_t ydim, Value val); +carray2X carray2X_with_storage(size_t xdim, size_t ydim, Value* array); carray2X carray2X_clone(carray2X arr); -Value* carray2X_release(carray2X* self); // give away data +Value* carray2X_release(carray2X* self); // release storage (not freed) void carray2X_del(carray2X* self); size_t carray2X_size(carray2X arr); -Value* carray2X_data(carray2X* self); // contiguous memory +Value* carray2X_data(carray2X* self); // access storage data Value* carray2X_at(carray2X* self, size_t x, size_t y); carray2X_iter_t carray2X_begin(const carray2X* self); @@ -43,14 +44,15 @@ carray2X_iter_t carray2X_end(const carray2X* self); void carray2X_next(carray2X_iter_t* it); ``` ```c -carray3X carray3X_init(size_t xdim, size_t ydim, size_t zdim, Value val); -carray3X carray3X_from(Value* array, size_t xdim, size_t ydim, size_t zdim); +carray3X carray3X_init(size_t xdim, size_t ydim, size_t zdim); +carray3X carray3X_with_value(size_t xdim, size_t ydim, size_t zdim, Value val); +carray3X carray3X_with_storage(size_t xdim, size_t ydim, size_t zdim, Value* array); carray3X carray3X_clone(carray3X arr); -Value* carray3X_release(carray3X* self); // give away data +Value* carray3X_release(carray3X* self); // release storage (not freed) void carray3X_del(carray3X* self); size_t carray3X_size(carray3X arr); -Value* carray3X_data(carray3X* self); // contiguous memory +Value* carray3X_data(carray3X* self); // access storage data Value* carray3X_at(carray3X* self, size_t x, size_t y, size_t z); carray3X_iter_t carray3X_begin(const carray3X* self); @@ -59,14 +61,14 @@ void carray3X_next(carray3X_iter_t* it); ``` ## Types -| Type name | Type definition | Used to represent... | -|:---------------------|:---------------------------------------------------|:--------------------------| -| `carray2X` | `struct { Value **data; size_t xdim,ydim; }` | The carray2 type | -| `carray2X_value_t` | `Value` | The value type | -| `carray2X_iter_t` | `struct { Value *ref; }` | Iterator type | -| `carray3X` | `struct { Value ***data; size_t xdim,ydim,zdim; }` | The carray3 type | -| `carray3X_value_t` | `Value` | The value type | -| `carray3X_iter_t` | `struct { Value *ref; }` | Iterator type | +| Type name | Type definition | Used to represent... | +|:---------------------|:-----------------------------------------------------|:--------------------------| +| `carray2X` | `struct { Value **data; size_t xdim, ydim; }` | The carray2 type | +| `carray2X_value_t` | `Value` | The value type | +| `carray2X_iter_t` | `struct { Value *ref; }` | Iterator type | +| `carray3X` | `struct { Value ***data; size_t xdim, ydim, zdim; }` | The carray3 type | +| `carray3X_value_t` | `Value` | The value type | +| `carray3X_iter_t` | `struct { Value *ref; }` | Iterator type | The **carray** elements can be accessed like `carray3i arr = ...; int val = arr.data[x][y][z];`, or with `carray3i_at(&arr, x, y, z)`. @@ -82,20 +84,20 @@ int main() { // Ex1 int xd = 30, yd = 20, zd = 10; - carray3f a3 = carray3f_init(xd, yd, zd, 0.0f); // define a3[30][20][10], init with 0.0f. - a3.data[5][4][3] = 3.14f; + carray3f arr3 = carray3f_init(xd, yd, zd, 0.0f); // define arr3[30][20][10], init with 0.0f. + arr3.data[5][4][3] = 3.14f; - float *a1 = a3.data[5][4]; - float **a2 = a3.data[5]; + float *arr1 = arr3.data[5][4]; + float **arr2 = arr3.data[5]; - printf("%f\n", a1[3]); // 3.14 - printf("%f\n", a2[4][3]); // 3.14 - printf("%f\n", a3.data[5][4][3]); // 3.14 - carray3f_del(&a3); // free array + printf("%f\n", arr1[3]); // 3.14 + printf("%f\n", arr2[4][3]); // 3.14 + printf("%f\n", arr3.data[5][4][3]); // 3.14 + carray3f_del(&arr3); // free array // Ex2 int w = 256, h = 128; - carray2i image = carray2i_from(c_new_n(uint32_t, w*h), w, h); // no value init + carray2i image = carray2i_init(w, h); int n = 0; c_foreach (i, carray2i, image) { uint32_t t = n++ % 256; diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 78aecfa9..8d12288c 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -62,9 +62,10 @@ size_t cmap_X_size(cmap_X map); size_t cmap_X_capacity(cmap_X map); // buckets * max_load_factor size_t cmap_X_bucket_count(cmap_X map); // num. of allocated buckets -cmap_X_iter_t cmap_X_find(const cmap_X* self, RawKey rkey); bool cmap_X_contains(const cmap_X* self, RawKey rkey); cmap_X_mapped_t* cmap_X_at(const cmap_X* self, RawKey rkey); // rkey must be in map. +cmap_X_value_t* cmap_X_get(const cmap_X* self, RawKey rkey); // return NULL if not found +cmap_X_iter_t cmap_X_find(const cmap_X* self, RawKey rkey); cmap_X_result_t cmap_X_insert(cmap_X* self, Key key, Mapped mapped); // no change if key in map cmap_X_result_t cmap_X_insert_or_assign(cmap_X* self, Key key, Mapped mapped); // always update mapped @@ -106,7 +107,7 @@ void c_trivial_del(Type* val); // doe | `cmap_X_rawvalue_t` | `struct { RawKey first; RawMapped second; }` | RawKey + RawMapped type | | `cmap_X_key_t` | `Key` | The key type | | `cmap_X_mapped_t` | `Mapped` | The mapped type | -| `cmap_X_value_t` | `struct { Key first; Mapped second; }` | The value type | +| `cmap_X_value_t` | `struct { const Key first; Mapped second; }` | The value: key is immutable | | `cmap_X_result_t` | `struct { cmap_X_value_t *ref; bool inserted; }`| Result of insert/put/emplace | | `cmap_X_iter_t` | `struct { cmap_X_value_t *ref; ... }` | Iterator type | diff --git a/docs/cset_api.md b/docs/cset_api.md index a1265ee8..be083b75 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -39,8 +39,9 @@ size_t cset_X_size(cset_X set); size_t cset_X_capacity(cset_X set); // buckets * max_load_factor size_t cset_X_bucket_count(cset_X set); -cset_X_iter_t cset_X_find(const cset_X* self, RawKey rkey); bool cset_X_contains(const cset_X* self, RawKey rkey); +cset_X_value_t* cset_X_get(const cset_X* self, RawKey rkey); // return NULL if not found +cset_X_iter_t cset_X_find(const cset_X* self, RawKey rkey); cset_X_result_t cset_X_insert(cset_X* self, Key key); cset_X_result_t cset_X_emplace(cset_X* self, RawKey rkey); @@ -59,15 +60,15 @@ cset_X_value_t cset_X_value_clone(cset_X_value_t val); ## Types -| Type name | Type definition | Used to represent... | -|:---------------------|:-------------------------------------------------|:-------------------------| -| `cset_X` | `struct { ... }` | The cset type | -| `cset_X_rawkey_t` | `RawKey` | The raw key type | -| `cset_X_rawvalue_t` | `cset_X_rawkey_t` | The raw key type | -| `cset_X_key_t` | `Key` | The key type | -| `cset_X_value_t` | `cset_X_key_t` | The value type | -| `cset_X_result_t` | `struct { cset_X_value_t* ref; bool inserted; }` | Result of insert/emplace | -| `cset_X_iter_t` | `struct { cset_X_value_t *ref; ... }` | Iterator type | +| Type name | Type definition | Used to represent... | +|:---------------------|:-------------------------------------------------|:----------------------------| +| `cset_X` | `struct { ... }` | The cset type | +| `cset_X_rawkey_t` | `RawKey` | The raw key type | +| `cset_X_rawvalue_t` | `RawKey` | The raw value type | +| `cset_X_key_t` | `Key` | The key type | +| `cset_X_value_t` | `const Key` | The value: key is immutable | +| `cset_X_result_t` | `struct { cset_X_value_t* ref; bool inserted; }` | Result of insert/emplace | +| `cset_X_iter_t` | `struct { cset_X_value_t *ref; ... }` | Iterator type | ## Example ```c diff --git a/docs/csmap_api.md b/docs/csmap_api.md index 5717c287..ba9a2978 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -54,11 +54,12 @@ void csmap_X_del(csmap_X* self); bool csmap_X_empty(csmap_X map); size_t csmap_X_size(csmap_X map); -csmap_X_iter_t csmap_X_find(const csmap_X* self, RawKey rkey); -csmap_X_iter_t csmap_X_lower_bound(const csmap_X* self, RawKey rkey); // find closest entry >= rkey bool csmap_X_contains(const csmap_X* self, RawKey rkey); -csmap_X_value_t* csmap_X_find_it(const csmap_X* self, RawKey rkey, csmap_X_iter_t* out); // return NULL if not found csmap_X_mapped_t* csmap_X_at(const csmap_X* self, RawKey rkey); // rkey must be in map. +csmap_X_value_t* csmap_X_get(const csmap_X* self, RawKey rkey); // return NULL if not found +csmap_X_iter_t csmap_X_lower_bound(const csmap_X* self, RawKey rkey); // find closest entry >= rkey +csmap_X_iter_t csmap_X_find(const csmap_X* self, RawKey rkey); +csmap_X_value_t* csmap_X_find_it(const csmap_X* self, RawKey rkey, csmap_X_iter_t* out); // return NULL if not found csmap_X_result_t csmap_X_insert(csmap_X* self, Key key, Mapped mapped); // no change if key in map csmap_X_result_t csmap_X_insert_or_assign(csmap_X* self, Key key, Mapped mapped); // always update mapped @@ -85,10 +86,10 @@ csmap_X_value_t csmap_X_value_clone(csmap_X_value_t val); | `csmap_X` | `struct { ... }` | The csmap type | | `csmap_X_rawkey_t` | `RawKey` | The raw key type | | `csmap_X_rawmapped_t` | `RawMapped` | The raw mapped type | -| `csmap_X_rawvalue_t` | `struct { RawKey first; RawMapped second; }` | RawKey + RawVal type | +| `csmap_X_rawvalue_t` | `struct { RawKey first; RawMapped second; }` | RawKey+RawMapped type | | `csmap_X_key_t` | `Key` | The key type | | `csmap_X_mapped_t` | `Mapped` | The mapped type | -| `csmap_X_value_t` | `struct { Key first; Mapped second; }` | The value type | +| `csmap_X_value_t` | `struct { const Key first; Mapped second; }` | The value: key is immutable | | `csmap_X_result_t` | `struct { csmap_X_value_t *ref; bool inserted; }` | Result of insert/put/emplace | | `csmap_X_iter_t` | `struct { csmap_X_value_t *ref; ... }` | Iterator type | diff --git a/docs/csset_api.md b/docs/csset_api.md index 500e38e4..3e8f1aff 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -34,10 +34,11 @@ void csset_X_del(csset_X* self); bool csset_X_empty(csset_X set); size_t csset_X_size(csset_X set); -csset_X_iter_t csset_X_find(const csset_X* self, RawKey rkey); -csset_X_iter_t csset_X_lower_bound(const csset_X* self, RawKey rkey); // find closest entry >= rkey -csset_X_value_t* csset_X_find_it(const csset_X* self, RawKey rkey, csset_X_iter_t* out); bool csset_X_contains(const csset_X* self, RawKey rkey); +csset_X_value_t* csset_X_get(const csset_X* self, RawKey rkey); // return NULL if not found +csset_X_iter_t csset_X_lower_bound(const csset_X* self, RawKey rkey); // find closest entry >= rkey +csset_X_iter_t csset_X_find(const csset_X* self, RawKey rkey); +csset_X_value_t* csset_X_find_it(const csset_X* self, RawKey rkey, csset_X_iter_t* out); // return NULL if not found csset_X_result_t csset_X_insert(csset_X* self, Key key); csset_X_result_t csset_X_emplace(csset_X* self, RawKey rkey); @@ -56,15 +57,15 @@ csset_X_value_t csset_X_value_clone(csset_X_value_t val); ## Types -| Type name | Type definition | Used to represent... | -|:---------------------|:--------------------------------------------------|:-------------------------| -| `csset_X` | `struct { ... }` | The csset type | -| `csset_X_rawkey_t` | `RawKey` | The raw key type | -| `csset_X_rawvalue_t` | `csset_X_rawkey_t` | The raw key type | -| `csset_X_key_t` | `Key` | The key type | -| `csset_X_value_t` | `csset_X_key_t` | The value type | -| `csset_X_result_t` | `struct { csset_X_value_t* ref; bool inserted; }` | Result of insert/emplace | -| `csset_X_iter_t` | `struct { csset_X_value_t *ref; ... }` | Iterator type | +| Type name | Type definition | Used to represent... | +|:---------------------|:--------------------------------------------------|:----------------------------| +| `csset_X` | `struct { ... }` | The csset type | +| `csset_X_rawkey_t` | `RawKey` | The raw key type | +| `csset_X_rawvalue_t` | `csset_X_rawkey_t` | The raw key type | +| `csset_X_key_t` | `Key` | The key type | +| `csset_X_value_t` | `const Key` | The value: key is immutable | +| `csset_X_result_t` | `struct { csset_X_value_t* ref; bool inserted; }` | Result of insert/emplace | +| `csset_X_iter_t` | `struct { csset_X_value_t *ref; ... }` | Iterator type | ## Example ```c diff --git a/examples/advanced.c b/examples/advanced.c index 795f3f63..84e148ac 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -30,7 +30,7 @@ static inline int vikingraw_equals(const VikingRaw* rx, const VikingRaw* ry) { static inline Viking viking_fromRaw(VikingRaw raw) { // note: parameter is by value Viking vk = {cstr_from(raw.name), cstr_from(raw.country)}; return vk; } -static inline VikingRaw viking_toRaw(Viking* vk) { +static inline VikingRaw viking_toRaw(const Viking* vk) { VikingRaw raw = {vk->name.str, vk->country.str}; return raw; } diff --git a/examples/complex.c b/examples/complex.c index 32bbd057..eea92dbd 100644 --- a/examples/complex.c +++ b/examples/complex.c @@ -22,7 +22,7 @@ int main() { cmap_map myMap = cmap_map_init(); cmap_lst listMap = cmap_lst_init(); clist_arr tableList = clist_arr_init(); - carray2f arr2 = carray2f_init(xdim, ydim, 1.f); + carray2f arr2 = carray2f_with_value(xdim, ydim, 1.f); printf("arr2 size: %zu x %zu\n", arr2.xdim, arr2.ydim); diff --git a/examples/demos.c b/examples/demos.c index 286c2e79..3502f5f1 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -184,23 +184,23 @@ using_carray3(f, float); void arraydemo1() { printf("\nARRAYDEMO1\n"); - carray3f a3 = carray3f_init(30, 20, 10, 0.0f); - a3.data[5][4][3] = 10.2f; - float **a2 = a3.data[5]; - float *a1 = a3.data[5][4]; + carray3f arr3 = carray3f_with_value(30, 20, 10, 0.0f); + arr3.data[5][4][3] = 10.2f; + float **arr2 = arr3.data[5]; + float *arr1 = arr3.data[5][4]; - printf("a3: %zu: (%zu, %zu, %zu) = %zu\n", sizeof(a3), a3.xdim, a3.ydim, a3.zdim, carray3f_size(a3)); + printf("arr3: %zu: (%zu, %zu, %zu) = %zu\n", sizeof(arr3), arr3.xdim, arr3.ydim, arr3.zdim, carray3f_size(arr3)); - printf("%g\n", a1[3]); // = 10.2 - printf("%g\n", a2[4][3]); // = 10.2 - printf("%g\n", a3.data[5][4][3]); // = 10.2 + printf("%g\n", arr1[3]); // = 10.2 + printf("%g\n", arr2[4][3]); // = 10.2 + printf("%g\n", arr3.data[5][4][3]); // = 10.2 float x = 0.0; - c_foreach (i, carray3f, a3) + c_foreach (i, carray3f, arr3) *i.ref = ++x; - printf("%g\n", a3.data[29][19][9]); // = 6000 + printf("%g\n", arr3.data[29][19][9]); // = 6000 - carray3f_del(&a3); + carray3f_del(&arr3); } diff --git a/examples/ex_gauss1.c b/examples/ex_gauss1.c index 99d17b23..75b96482 100644 --- a/examples/ex_gauss1.c +++ b/examples/ex_gauss1.c @@ -10,10 +10,12 @@ using_cmap(i, int, size_t); // Declare int vector with map entries that can be sorted by map keys. -static int compare(cmap_i_value_t *a, cmap_i_value_t *b) { +struct mapval {int first; size_t second;}; +static int compare(struct mapval *a, struct mapval *b) { return c_default_compare(&a->first, &b->first); } -using_cvec(e, cmap_i_value_t, compare); + +using_cvec(e, struct mapval, compare); int main() { @@ -37,7 +39,7 @@ int main() // Transfer map to vec and sort it by map keys. cvec_e vhist = cvec_e_init(); c_foreach (i, cmap_i, mhist) - cvec_e_push_back(&vhist, *i.ref); + cvec_e_push_back(&vhist, (struct mapval){i.ref->first, i.ref->second}); cvec_e_sort(&vhist); // Print the gaussian bar chart diff --git a/stc/carray.h b/stc/carray.h index ebb20321..3fad0df7 100644 --- a/stc/carray.h +++ b/stc/carray.h @@ -67,10 +67,13 @@ int main() { typedef struct { CX##_value_t **data; size_t xdim, ydim; } CX; \ typedef struct { CX##_value_t *ref; } CX##_iter_t; \ \ - STC_API CX CX##_from(CX##_value_t* block, size_t xdim, size_t ydim); \ - STC_API CX CX##_init(size_t xdim, size_t ydim, Value value); \ + STC_API CX CX##_with_value(size_t xdim, size_t ydim, Value value); \ + STC_API CX CX##_with_storage(size_t xdim, size_t ydim, CX##_value_t* storage); \ STC_API CX CX##_clone(CX src); \ \ + STC_INLINE CX CX##_init(size_t xdim, size_t ydim) { \ + return CX##_with_storage(xdim, ydim, c_new_n(CX##_value_t, xdim*ydim)); \ + } \ STC_INLINE size_t CX##_size(CX arr) { return arr.xdim*arr.ydim; } \ STC_INLINE CX##_value_t *CX##_data(CX* self) { return *self->data; } \ STC_INLINE CX##_value_t *CX##_at(CX* self, size_t x, size_t y) { \ @@ -84,7 +87,7 @@ int main() { CX##_iter_t it = {*self->data}; return it; \ } \ STC_INLINE CX##_iter_t CX##_end(const CX* self) { \ - CX##_iter_t it = {*self->data + CX##_size(*self)}; return it; \ + CX##_iter_t it = {*self->data + self->xdim*self->ydim}; return it; \ } \ STC_INLINE void CX##_next(CX##_iter_t* it) { ++it->ref; } \ \ @@ -108,17 +111,23 @@ int main() { typedef struct { CX##_value_t ***data; size_t xdim, ydim, zdim; } CX; \ typedef struct { CX##_value_t *ref; } CX##_iter_t; \ \ - STC_API CX CX##_from(CX##_value_t* block, size_t xdim, size_t ydim, size_t zdim); \ - STC_API CX CX##_init(size_t xdim, size_t ydim, size_t zdim, Value value); \ + STC_API CX CX##_with_value(size_t xdim, size_t ydim, size_t zdim, Value value); \ + STC_API CX CX##_with_storage(size_t xdim, size_t ydim, size_t zdim, CX##_value_t* storage); \ STC_API CX CX##_clone(CX src); \ \ + STC_INLINE CX CX##_init(size_t xdim, size_t ydim, size_t zdim) { \ + return CX##_with_storage(xdim, ydim, zdim, c_new_n(CX##_value_t, xdim*ydim*zdim)); \ + } \ STC_INLINE size_t CX##_size(CX arr) { return arr.xdim*arr.ydim*arr.zdim; } \ - STC_INLINE CX##_value_t *CX##_data(CX* self) { return **self->data; } \ - STC_INLINE CX##_value_t *CX##_at(CX* self, size_t x, size_t y, size_t z) { \ + STC_INLINE CX##_value_t* CX##_data(CX* self) { return **self->data; } \ + STC_INLINE CX##_value_t* CX##_at(CX* self, size_t x, size_t y, size_t z) { \ return **self->data + self->zdim*(self->ydim*x + y) + z; \ } \ - STC_INLINE CX##_value_t *CX##_release(CX* self) { \ - CX##_value_t *t = **self->data; c_free(self->data); self->data = NULL; return t; \ +\ + STC_INLINE CX##_value_t* CX##_release(CX* self) { \ + CX##_value_t *values = **self->data; \ + c_free(self->data); self->data = NULL; \ + return values; \ } \ \ STC_INLINE CX##_iter_t CX##_begin(const CX* self) { \ @@ -138,43 +147,40 @@ int main() { #define _c_implement_carray2(CX, Value, valueDel, valueClone) \ \ - STC_DEF CX CX##_from(CX##_value_t* block, size_t xdim, size_t ydim) { \ - size_t n = xdim * ydim; \ + STC_DEF CX CX##_with_storage(size_t xdim, size_t ydim, CX##_value_t* block) { \ CX _arr = {c_new_n(CX##_value_t*, xdim), xdim, ydim}; \ for (size_t x = 0; x < xdim; ++x, block += ydim) \ _arr.data[x] = block; \ return _arr; \ } \ \ - STC_DEF CX CX##_init(size_t xdim, size_t ydim, Value value) { \ - size_t n = xdim*ydim; \ - CX _arr = CX##_from(c_new_n(CX##_value_t, n), xdim, ydim); \ - for (CX##_value_t* p = _arr.data[0], *e = p + n; p != e; ++p) \ + STC_DEF CX CX##_with_value(size_t xdim, size_t ydim, Value value) { \ + CX _arr = CX##_init(xdim, ydim); \ + for (CX##_value_t* p = _arr.data[0], *e = p + xdim*ydim; p != e; ++p) \ *p = value; \ return _arr; \ } \ \ STC_DEF CX CX##_clone(CX src) { \ - size_t n = src.xdim*src.ydim; \ - CX _arr = CX##_from(c_new_n(CX##_value_t, n), src.xdim, src.ydim); \ - for (CX##_value_t* p = _arr.data[0], *q = src.data[0], *e = p + n; p != e; ++p, ++q) \ + CX _arr = CX##_init(src.xdim, src.ydim); \ + for (CX##_value_t* p = _arr.data[0], *q = src.data[0], *e = p + CX##_size(src); p != e; ++p, ++q) \ *p = valueClone(*q); \ return _arr; \ } \ \ STC_DEF void CX##_del(CX* self) { \ if (!self->data) return; \ - for (CX##_value_t* p = self->data[0], *e = p + self->xdim*self->ydim; p != e; ++p) \ + for (CX##_value_t* p = self->data[0], *e = p + CX##_size(*self); p != e; ++p) \ valueDel(p); \ c_free(self->data[0]); /* data */ \ - c_free(self->data); \ + c_free(self->data); /* pointers */ \ } // carray3 impl. #define _c_implement_carray3(CX, Value, valueDel, valueClone) \ \ - STC_DEF CX CX##_from(CX##_value_t* block, size_t xdim, size_t ydim, size_t zdim) { \ + STC_DEF CX CX##_with_storage(size_t xdim, size_t ydim, size_t zdim, CX##_value_t* block) { \ CX _arr = {c_new_n(CX##_value_t**, xdim*(ydim + 1)), xdim, ydim, zdim}; \ CX##_value_t** p = (CX##_value_t**) &_arr.data[xdim]; \ for (size_t x = 0, y; x < xdim; ++x, p += ydim) \ @@ -183,18 +189,16 @@ int main() { return _arr; \ } \ \ - STC_DEF CX CX##_init(size_t xdim, size_t ydim, size_t zdim, Value value) { \ - size_t n = xdim*ydim*zdim; \ - CX _arr = CX##_from(c_new_n(CX##_value_t, n), xdim, ydim, zdim); \ - for (CX##_value_t* p = **_arr.data, *e = p + n; p != e; ++p) \ + STC_DEF CX CX##_with_value(size_t xdim, size_t ydim, size_t zdim, Value value) { \ + CX _arr = CX##_init(xdim, ydim, zdim); \ + for (CX##_value_t* p = **_arr.data, *e = p + xdim*ydim*zdim; p != e; ++p) \ *p = value; \ return _arr; \ } \ \ STC_DEF CX CX##_clone(CX src) { \ - size_t n = CX##_size(src); \ - CX _arr = CX##_from(c_new_n(CX##_value_t, n), src.xdim, src.ydim, src.zdim); \ - for (CX##_value_t* p = **_arr.data, *q = **src.data, *e = p + n; p != e; ++p, ++q) \ + CX _arr = CX##_init(src.xdim, src.ydim, src.zdim); \ + for (CX##_value_t* p = **_arr.data, *q = **src.data, *e = p + CX##_size(src); p != e; ++p, ++q) \ *p = valueClone(*q); \ return _arr; \ } \ @@ -204,7 +208,7 @@ int main() { for (CX##_value_t* p = **self->data, *e = p + CX##_size(*self); p != e; ++p) \ valueDel(p); \ c_free(self->data[0][0]); /* data */ \ - c_free(self->data); /* pointers */ \ + c_free(self->data); /* pointers */ \ } #else diff --git a/stc/cmap.h b/stc/cmap.h index 1e1863eb..4994ce7f 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -153,8 +153,8 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) typedef RawMapped CX##_rawmapped_t; \ typedef CMAP_SIZE_T CX##_size_t; \ \ - typedef SET_ONLY_##C( Key ) \ - MAP_ONLY_##C( struct {Key first; \ + typedef SET_ONLY_##C( const CX##_key_t ) \ + MAP_ONLY_##C( struct {const CX##_key_t first; \ Mapped second;} ) \ CX##_value_t; \ \ @@ -180,38 +180,39 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) uint8_t* _hx; \ } CX##_iter_t; \ \ - STC_API CX CX##_with_capacity(size_t cap); \ - STC_API CX CX##_clone(CX map); \ - STC_API void CX##_del(CX* self); \ - STC_API void CX##_clear(CX* self); \ - STC_API void CX##_reserve(CX* self, size_t capacity); \ - STC_API chash_bucket_t CX##_bucket_(const CX* self, const CX##_rawkey_t* rkeyptr); \ - STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ - STC_API CX##_iter_t CX##_find(const CX* self, RawKey rkey); \ - STC_API void CX##_erase_entry(CX* self, CX##_value_t* val); \ + STC_API CX CX##_with_capacity(size_t cap); \ + STC_API CX CX##_clone(CX map); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_clear(CX* self); \ + STC_API void CX##_reserve(CX* self, size_t capacity); \ + STC_API chash_bucket_t CX##_bucket_(const CX* self, const CX##_rawkey_t* rkeyptr); \ + STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ + STC_API CX##_iter_t CX##_find(const CX* self, RawKey rkey); \ + STC_API void CX##_erase_entry(CX* self, CX##_value_t* val); \ \ - STC_INLINE CX CX##_init(void) {CX m = _cmap_inits; return m;} \ - STC_INLINE void CX##_shrink_to_fit(CX* self) {CX##_reserve(self, self->size);} \ - STC_INLINE void CX##_max_load_factor(CX* self, float ml) {self->max_load_factor = ml;} \ - STC_INLINE bool CX##_empty(CX m) {return m.size == 0;} \ - STC_INLINE size_t CX##_size(CX m) {return m.size;} \ - STC_INLINE size_t CX##_bucket_count(CX map) {return map.bucket_count;} \ - STC_INLINE size_t CX##_capacity(CX map) \ + STC_INLINE CX CX##_init(void) {CX m = _cmap_inits; return m;} \ + STC_INLINE void CX##_shrink_to_fit(CX* self) {CX##_reserve(self, self->size);} \ + STC_INLINE void CX##_max_load_factor(CX* self, float ml) {self->max_load_factor = ml;} \ + STC_INLINE bool CX##_empty(CX m) {return m.size == 0;} \ + STC_INLINE size_t CX##_size(CX m) {return m.size;} \ + STC_INLINE size_t CX##_bucket_count(CX map) {return map.bucket_count;} \ + STC_INLINE size_t CX##_capacity(CX map) \ {return (size_t) (map.bucket_count * map.max_load_factor);} \ - STC_INLINE void CX##_swap(CX *map1, CX *map2) {c_swap(CX, *map1, *map2);} \ - STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \ + STC_INLINE void CX##_swap(CX *map1, CX *map2) {c_swap(CX, *map1, *map2);} \ + STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \ {return self->size && self->_hashx[CX##_bucket_(self, &rkey).idx];} \ + STC_INLINE CX##_value_t* CX##_get(const CX* self, RawKey rkey) \ + {return CX##_find(self, rkey).ref;} \ \ - STC_INLINE CX##_value_t \ - CX##_value_clone(CX##_value_t val) { \ - *KEY_REF_##C(&val) = keyFromRaw(keyToRaw(KEY_REF_##C(&val))); \ - MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ - return val; \ + STC_INLINE void \ + CX##_value_clone(CX##_value_t* dst, CX##_value_t* val) { \ + *(CX##_key_t*) KEY_REF_##C(dst) = keyFromRaw(keyToRaw(KEY_REF_##C(val))); \ + MAP_ONLY_##C( dst->second = mappedFromRaw(mappedToRaw(&val->second)); ) \ } \ \ STC_INLINE void \ CX##_value_del(CX##_value_t* val) { \ - keyDel(KEY_REF_##C(val)); \ + keyDel((CX##_key_t*) KEY_REF_##C(val)); \ MAP_ONLY_##C( mappedDel(&val->second); ) \ } \ \ @@ -219,7 +220,7 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ CX##_result_t res = CX##_insert_entry_(self, rkey); \ if (res.inserted) { \ - *KEY_REF_##C(res.ref) = keyFromRaw(rkey); \ + *(CX##_key_t*) KEY_REF_##C(res.ref) = keyFromRaw(rkey); \ MAP_ONLY_##C(res.ref->second = mappedFromRaw(rmapped);) \ } \ return res; \ @@ -234,7 +235,7 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) STC_INLINE CX##_result_t \ CX##_insert(CX* self, Key key MAP_ONLY_##C(, Mapped mapped)) { \ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \ - if (res.inserted) {*KEY_REF_##C(res.ref) = key; MAP_ONLY_##C( res.ref->second = mapped; )} \ + if (res.inserted) {*(CX##_key_t*) KEY_REF_##C(res.ref) = key; MAP_ONLY_##C( res.ref->second = mapped; )} \ else {keyDel(&key); MAP_ONLY_##C( mappedDel(&mapped); )} \ return res; \ } \ @@ -243,25 +244,27 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) STC_INLINE CX##_result_t \ CX##_insert_or_assign(CX* self, Key key, Mapped mapped) { \ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \ - if (res.inserted) res.ref->first = key; \ + if (res.inserted) *(CX##_key_t*) &res.ref->first = key; \ else {keyDel(&key); mappedDel(&res.ref->second);} \ res.ref->second = mapped; return res; \ } \ + \ STC_INLINE CX##_result_t \ CX##_put(CX* self, Key k, Mapped m) { /* shorter, like operator[] */ \ return CX##_insert_or_assign(self, k, m); \ } \ + \ STC_INLINE CX##_result_t \ CX##_emplace_or_assign(CX* self, RawKey rkey, RawMapped rmapped) { \ CX##_result_t res = CX##_insert_entry_(self, rkey); \ - if (res.inserted) res.ref->first = keyFromRaw(rkey); \ + if (res.inserted) *(CX##_key_t*) &res.ref->first = keyFromRaw(rkey); \ else mappedDel(&res.ref->second); \ res.ref->second = mappedFromRaw(rmapped); return res; \ } \ + \ STC_INLINE CX##_mapped_t* \ CX##_at(const CX* self, RawKey rkey) { \ chash_bucket_t b = CX##_bucket_(self, &rkey); \ - assert(self->_hashx[b.idx]); \ return &self->table[b.idx].second; \ }) \ \ @@ -271,10 +274,12 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx; \ return it; \ } \ +\ STC_INLINE CX##_iter_t \ CX##_end(const CX* self) {\ CX##_iter_t it = {self->table + self->bucket_count}; return it; \ } \ +\ STC_INLINE void \ CX##_next(CX##_iter_t* it) { \ while ((++it->ref, *++it->_hx == 0)) ; \ @@ -331,7 +336,7 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ STC_DEF void CX##_del(CX* self) { \ CX##_wipe_(self); \ c_free(self->_hashx); \ - c_free(self->table); \ + c_free((void *) self->table); \ } \ \ STC_DEF void CX##_clear(CX* self) { \ @@ -388,7 +393,7 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ }; \ CX##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \ - if (*hx) *dst = CX##_value_clone(*e); \ + if (*hx) CX##_value_clone(dst, e); \ return clone; \ } \ \ @@ -411,11 +416,11 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ if (tmp._hashx[i]) { \ CX##_rawkey_t raw = keyToRaw(KEY_REF_##C(e)); \ chash_bucket_t b = CX##_bucket_(self, &raw); \ - slot[b.idx] = *e, \ + memcpy((void *) &slot[b.idx], e, sizeof *e); \ hashx[b.idx] = (uint8_t) b.hx; \ } \ c_free(tmp._hashx); \ - c_free(tmp.table); \ + c_free((void *) tmp.table); \ } \ \ STC_DEF void \ @@ -428,10 +433,10 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ if (++j == cap) j = 0; \ if (! hashx[j]) \ break; \ - CX##_rawkey_t raw = keyToRaw(KEY_REF_##C(slot + j)); \ + CX##_rawkey_t raw = keyToRaw(KEY_REF_##C(slot+j)); \ k = _c_SELECT(fastrange,CMAP_SIZE_T)(keyHashRaw(&raw, sizeof raw), cap); \ if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ - slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ + memcpy((void *) &slot[i], &slot[j], sizeof *slot), hashx[i] = hashx[j], i = j; \ } \ hashx[i] = 0; \ --self->size; \ diff --git a/stc/csmap.h b/stc/csmap.h index 04f7fcaa..fc1e37a5 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -142,8 +142,8 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; typedef RawMapped CX##_rawmapped_t; \ typedef CSMAP_SIZE_T CX##_size_t; \ \ - typedef SET_ONLY_##C( CX##_key_t ) \ - MAP_ONLY_##C( struct {CX##_key_t first; \ + typedef SET_ONLY_##C( const CX##_key_t ) \ + MAP_ONLY_##C( struct {const CX##_key_t first; \ CX##_mapped_t second;} ) \ CX##_value_t; \ \ @@ -174,43 +174,46 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; CX##_size_t _tn, _st[36]; \ } CX##_iter_t; \ \ - STC_API CX CX##_init(void); \ - STC_API CX CX##_clone(CX tree); \ - STC_API void CX##_del(CX* self); \ - STC_API void CX##_reserve(CX* self, size_t cap); \ - STC_API CX##_value_t* CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out); \ - STC_API CX##_iter_t CX##_lower_bound(const CX* self, RawKey rkey); \ - STC_API CX##_value_t* CX##_front(const CX* self); \ - STC_API CX##_value_t* CX##_back(const CX* self); \ - STC_API int CX##_erase(CX* self, RawKey rkey); \ - STC_API CX##_iter_t CX##_erase_at(CX* self, CX##_iter_t it); \ - STC_API CX##_iter_t CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ - STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ - STC_API void CX##_next(CX##_iter_t* it); \ -\ - STC_INLINE bool CX##_empty(CX tree) {return _csmap_rep(&tree)->size == 0;} \ - STC_INLINE size_t CX##_size(CX tree) {return _csmap_rep(&tree)->size;} \ - STC_INLINE size_t CX##_capacity(CX tree) {return _csmap_rep(&tree)->cap;} \ - STC_INLINE void CX##_clear(CX* self) {CX##_del(self); *self = CX##_init();} \ - STC_INLINE void CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ + STC_API CX CX##_init(void); \ + STC_API CX CX##_clone(CX tree); \ + STC_API void CX##_del(CX* self); \ + STC_API void CX##_reserve(CX* self, size_t cap); \ + STC_API CX##_value_t* CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out); \ + STC_API CX##_iter_t CX##_lower_bound(const CX* self, RawKey rkey); \ + STC_API CX##_value_t* CX##_front(const CX* self); \ + STC_API CX##_value_t* CX##_back(const CX* self); \ + STC_API int CX##_erase(CX* self, RawKey rkey); \ + STC_API CX##_iter_t CX##_erase_at(CX* self, CX##_iter_t it); \ + STC_API CX##_iter_t CX##_erase_range(CX* self, CX##_iter_t it1, CX##_iter_t it2); \ + STC_API CX##_result_t CX##_insert_entry_(CX* self, RawKey rkey); \ + STC_API void CX##_next(CX##_iter_t* it); \ +\ + STC_INLINE bool CX##_empty(CX tree) {return _csmap_rep(&tree)->size == 0;} \ + STC_INLINE size_t CX##_size(CX tree) {return _csmap_rep(&tree)->size;} \ + STC_INLINE size_t CX##_capacity(CX tree) {return _csmap_rep(&tree)->cap;} \ + STC_INLINE void CX##_clear(CX* self) {CX##_del(self); *self = CX##_init();} \ + STC_INLINE void CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \ + STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \ + {CX##_iter_t it; return CX##_find_it(self, rkey, &it) != NULL;} \ + STC_INLINE CX##_value_t* CX##_get(const CX* self, RawKey rkey) \ + {CX##_iter_t it; return CX##_find_it(self, rkey, &it);} \ \ STC_INLINE CX \ CX##_with_capacity(size_t size) { \ - CX x = CX##_init(); \ - CX##_reserve(&x, size); \ - return x; \ + CX tree = CX##_init(); \ + CX##_reserve(&tree, size); \ + return tree; \ } \ \ STC_INLINE void \ CX##_value_del(CX##_value_t* val) { \ - keyDel(KEY_REF_##C(val)); \ + keyDel((CX##_key_t*) KEY_REF_##C(val)); \ MAP_ONLY_##C( mappedDel(&val->second); ) \ } \ - STC_INLINE CX##_value_t \ - CX##_value_clone(CX##_value_t val) { \ - *KEY_REF_##C(&val) = keyFromRaw(keyToRaw(KEY_REF_##C(&val))); \ - MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \ - return val; \ + STC_INLINE void \ + CX##_value_clone(CX##_value_t* dst, CX##_value_t* val) { \ + *(CX##_key_t*) KEY_REF_##C(dst) = keyFromRaw(keyToRaw(KEY_REF_##C(val))); \ + MAP_ONLY_##C( dst->second = mappedFromRaw(mappedToRaw(&val->second)); ) \ } \ \ STC_INLINE CX##_iter_t \ @@ -219,18 +222,12 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; CX##_find_it(self, rkey, &it); \ return it; \ } \ -\ - STC_INLINE bool \ - CX##_contains(const CX* self, RawKey rkey) { \ - CX##_iter_t it; \ - return CX##_find_it(self, rkey, &it) != NULL; \ - } \ \ STC_INLINE CX##_result_t \ CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ CX##_result_t res = CX##_insert_entry_(self, rkey); \ if (res.inserted) { \ - *KEY_REF_##C(res.ref) = keyFromRaw(rkey); \ + *(CX##_key_t*) KEY_REF_##C(res.ref) = keyFromRaw(rkey); \ MAP_ONLY_##C(res.ref->second = mappedFromRaw(rmapped);) \ } \ return res; \ @@ -245,7 +242,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; STC_INLINE CX##_result_t \ CX##_insert(CX* self, Key key MAP_ONLY_##C(, Mapped mapped)) { \ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \ - if (res.inserted) {*KEY_REF_##C(res.ref) = key; MAP_ONLY_##C( res.ref->second = mapped; )} \ + if (res.inserted) {*(CX##_key_t*) KEY_REF_##C(res.ref) = key; MAP_ONLY_##C( res.ref->second = mapped; )} \ else {keyDel(&key); MAP_ONLY_##C( mappedDel(&mapped); )} \ return res; \ } \ @@ -254,24 +251,24 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; STC_INLINE CX##_result_t \ CX##_insert_or_assign(CX* self, Key key, Mapped mapped) { \ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \ - if (res.inserted) res.ref->first = key; \ + if (res.inserted) *(CX##_key_t*) &res.ref->first = key; \ else {keyDel(&key); mappedDel(&res.ref->second);} \ res.ref->second = mapped; return res; \ } \ -\ + \ STC_INLINE CX##_result_t \ CX##_put(CX* self, Key key, Mapped mapped) { \ return CX##_insert_or_assign(self, key, mapped); \ } \ -\ + \ STC_INLINE CX##_result_t \ CX##_emplace_or_assign(CX* self, RawKey rkey, RawMapped rmapped) { \ CX##_result_t res = CX##_insert_entry_(self, rkey); \ - if (res.inserted) res.ref->first = keyFromRaw(rkey); \ + if (res.inserted) *(CX##_key_t*) &res.ref->first = keyFromRaw(rkey); \ else mappedDel(&res.ref->second); \ res.ref->second = mappedFromRaw(rmapped); return res; \ } \ -\ + \ STC_INLINE CX##_mapped_t* \ CX##_at(const CX* self, RawKey rkey) { \ CX##_iter_t it; \ @@ -463,12 +460,12 @@ static struct csmap_rep _csmap_inits = {0, 0, 0, 0}; if (c != 0) \ d[tn].link[c < 0] = CX##_erase_r_(d, d[tn].link[c < 0], rkey, erased); \ else { \ - if (!*erased) {CX##_value_del(&d[tn].value); *erased = 1;} \ + if (!(*erased)++) CX##_value_del(&d[tn].value); \ if (d[tn].link[0] && d[tn].link[1]) { \ tx = d[tn].link[0]; \ while (d[tx].link[1]) \ tx = d[tx].link[1]; \ - d[tn].value = d[tx].value; /* move */ \ + memcpy((void *) &d[tn].value, &d[tx].value, sizeof d[0].value); /* move */ \ raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \ d[tn].link[0] = CX##_erase_r_(d, d[tn].link[0], &raw, erased); \ } else { /* unlink node */ \ @@ -497,8 +494,7 @@ static struct csmap_rep _csmap_inits = {0, 0, 0, 0}; CX##_erase(CX* self, RawKey rkey) { \ int erased = 0; \ CX##_size_t root = CX##_erase_r_(self->nodes, (CX##_size_t) _csmap_rep(self)->root, &rkey, &erased); \ - if (erased) {_csmap_rep(self)->root = root; --_csmap_rep(self)->size;} \ - return erased; \ + return erased ? (_csmap_rep(self)->root = root, --_csmap_rep(self)->size, 1) : 0; \ } \ \ STC_DEF CX##_iter_t \ @@ -526,10 +522,10 @@ static struct csmap_rep _csmap_inits = {0, 0, 0, 0}; } \ \ static CX##_size_t \ - CX##_clone_r_(CX* self, const CX##_node_t* src, CX##_size_t sn) { \ + CX##_clone_r_(CX* self, CX##_node_t* src, CX##_size_t sn) { \ if (sn == 0) return 0; \ CX##_size_t tx, tn = CX##_node_new_(self, src[sn].level); \ - self->nodes[tn].value = CX##_value_clone(src[sn].value); \ + CX##_value_clone(&self->nodes[tn].value, &src[sn].value); \ tx = CX##_clone_r_(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx; \ tx = CX##_clone_r_(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx; \ return tn; \ -- cgit v1.2.3