From 779b2b9ff0223135396989b7abb5825a9e0e1e8e Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 15 Mar 2021 16:08:14 +0100 Subject: Added csmap_X_lower_bound() method (find >= key). Updated docs a little. --- docs/cmap_api.md | 4 ++-- docs/csmap_api.md | 7 ++++--- docs/cstr_api.md | 3 ++- stc/csmap.h | 25 ++++++++++++++++++++++--- stc/cvec.h | 2 +- 5 files changed, 31 insertions(+), 10 deletions(-) diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 06f2c987..593f78ab 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -61,16 +61,16 @@ size_t cmap_X_bucket_count(cmap_X map); 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_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 cmap_X_result_t cmap_X_put(cmap_X* self, Key key, Mapped mapped); // alias for insert_or_assign + cmap_X_result_t cmap_X_emplace(cmap_X* self, RawKey rkey, RawMapped rmapped); // no change if rkey in map cmap_X_result_t cmap_X_emplace_or_assign(cmap_X* self, RawKey rkey, RawMapped rmapped); // always update rmapped void cmap_X_emplace_n(cmap_X* self, const cmap_X_rawvalue_t arr[], size_t size); -cmap_X_mapped_t* cmap_X_at(const cmap_X* self, RawKey rkey); // rkey must be in map. - size_t cmap_X_erase(cmap_X* self, RawKey rkey); cmap_X_iter_t cmap_X_erase_at(cmap_X* self, cmap_X_iter_t pos); void cmap_X_erase_entry(cmap_X* self, cmap_X_value_t* entry); diff --git a/docs/csmap_api.md b/docs/csmap_api.md index d314958e..4b8f058a 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -55,18 +55,19 @@ 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_value_t* csmap_X_find_it(const csmap_X* self, RawKey rkey, csmap_X_iter_t* out); // return NULL if not found +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_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 csmap_X_result_t csmap_X_put(csmap_X* self, Key key, Mapped mapped); // alias for insert_or_assign + csmap_X_result_t csmap_X_emplace(csmap_X* self, RawKey rkey, RawMapped rmapped); // no change if rkey in map csmap_X_result_t csmap_X_emplace_or_assign(csmap_X* self, RawKey rkey, RawMapped rmapped); // always update rmapped void csmap_X_emplace_n(csmap_X* self, const csmap_X_rawvalue_t arr[], size_t size); -csmap_X_mapped_t* csmap_X_at(const csmap_X* self, RawKey rkey); // rkey must be in map. - size_t csmap_X_erase(csmap_X* self, RawKey rkey); csmap_X_iter_t csmap_X_erase_at(csmap_X* self, csmap_X_iter_t pos); diff --git a/docs/cstr_api.md b/docs/cstr_api.md index 7a483370..e528aafb 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -42,7 +42,7 @@ cstr* cstr_assign_n(cstr* self, const char* str, size_t n); cstr* cstr_append(cstr* self, const char* str); cstr* cstr_append_s(cstr* self, cstr s); -cstr* cstr_append_n(cstr* self, const char* str, size_t n); // appends len characters +cstr* cstr_append_n(cstr* self, const char* str, size_t n); // appends len characters void cstr_insert(cstr* self, size_t pos, const char* str); void cstr_insert_s(cstr* self, size_t pos, cstr s); @@ -51,6 +51,7 @@ void cstr_insert_n(cstr* self, size_t pos, const char* str, size_t n); void cstr_replace(cstr* self, size_t pos, size_t len, const char* str); void cstr_replace_s(cstr* self, size_t pos, size_t len, cstr s); void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n); + void cstr_erase(cstr* self, size_t pos); void cstr_erase_n(cstr* self, size_t pos, size_t n); diff --git a/stc/csmap.h b/stc/csmap.h index e2cc6fcf..05ba949b 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -228,6 +228,9 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; \ STC_API C##X##_value_t* \ C##X##_find_it(const C##X* self, RawKey rkey, C##X##_iter_t* out); \ +\ + STC_API C##X##_iter_t \ + C##X##_lower_bound(const C##X* self, RawKey rkey); \ \ STC_INLINE C##X##_iter_t \ C##X##_find(const C##X* self, RawKey rkey) { \ @@ -235,6 +238,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; C##X##_find_it(self, rkey, &it); \ return it; \ } \ +\ STC_INLINE bool \ C##X##_contains(const C##X* self, RawKey rkey) { \ C##X##_iter_t it; \ @@ -387,12 +391,27 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; out->_top = 0; \ while (tn) { \ int c; C##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&d[tn].value)); \ - if ((c = keyCompareRaw(&rx, &rkey)) < 0) tn = d[tn].link[1]; \ - else if (c > 0) {out->_st[out->_top++] = tn; tn = d[tn].link[0];} \ - else {out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value);} \ + if ((c = keyCompareRaw(&rx, &rkey)) < 0) \ + tn = d[tn].link[1]; \ + else if (c > 0) \ + { out->_st[out->_top++] = tn; tn = d[tn].link[0]; } \ + else \ + { out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value); } \ } \ return (out->ref = NULL); \ } \ +\ + STC_DEF C##X##_iter_t \ + C##X##_lower_bound(const C##X* self, RawKey rkey) { \ + C##X##_iter_t it; \ + C##X##_find_it(self, rkey, &it); \ + if (!it.ref && it._top) { \ + C##X##_size_t tn = it._st[--it._top]; \ + it._tn = it._d[tn].link[1]; \ + it.ref = &it._d[tn].value; \ + } \ + return it; \ + } \ \ STC_DEF void \ C##X##_next(C##X##_iter_t *it) { \ diff --git a/stc/cvec.h b/stc/cvec.h index de76ff97..fdbf958d 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -73,7 +73,7 @@ typedef int (*c_cmp_fn)(const void*, const void*); STC_API void \ cvec_##X##_resize(cvec_##X* self, size_t size, Value fill_val); \ STC_INLINE void \ - cvec_##X##_swap(cvec_##X* a, cvec_##X* b) {c_swap(cvec_##X##_value_t*, a->data, b->data);} \ + cvec_##X##_swap(cvec_##X* a, cvec_##X* b) {c_swap(cvec_##X, *a, *b);} \ \ STC_INLINE cvec_##X \ cvec_##X##_with_size(size_t size, Value null_val) { \ -- cgit v1.2.3