From 422272d1d87921b4524bdb276862687bf11b344d Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 21 Nov 2021 15:04:07 +0100 Subject: Changed reverse() and resize() to return false if mem alloc failed. --- docs/cmap_api.md | 2 +- docs/cpque_api.md | 2 +- docs/cset_api.md | 2 +- docs/cstack_api.md | 2 +- include/stc/cdeq.h | 13 ++++++++----- include/stc/cmap.h | 15 ++++++++++----- include/stc/cpque.h | 20 +++++++++++--------- include/stc/csmap.h | 10 ++++++---- include/stc/cstack.h | 7 ++++--- include/stc/cvec.h | 15 +++++++++------ 10 files changed, 52 insertions(+), 36 deletions(-) diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 7f7ffe6f..a1f391bc 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -44,7 +44,7 @@ cmap_X cmap_X_clone(cmap_x map); void cmap_X_clear(cmap_X* self); void cmap_X_copy(cmap_X* self, cmap_X other); void cmap_X_max_load_factor(cmap_X* self, float max_load); // default: 0.85 -void cmap_X_reserve(cmap_X* self, size_t size); +bool cmap_X_reserve(cmap_X* self, size_t size); void cmap_X_shrink_to_fit(cmap_X* self); void cmap_X_swap(cmap_X* a, cmap_X* b); void cmap_X_del(cmap_X* self); // destructor diff --git a/docs/cpque_api.md b/docs/cpque_api.md index 365ba4b9..8f01e4c9 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -26,7 +26,7 @@ cpque_X cpque_X_init(void); cpque_X cpque_X_clone(cpque_X pq); void cpque_X_clear(cpque_X* self); -void cpque_X_reserve(cpque_X* self, size_t n); +bool cpque_X_reserve(cpque_X* self, size_t n); void cpque_X_copy(cpque_X* self, cpque_X other); void cpque_X_del(cpque_X* self); // destructor diff --git a/docs/cset_api.md b/docs/cset_api.md index 8ded9d0c..4883664d 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -30,7 +30,7 @@ cset_X cset_X_clone(cset_x set); void cset_X_clear(cset_X* self); void cset_X_copy(cset_X* self, cset_X other); void cset_X_max_load_factor(cset_X* self, float max_load); // default: 0.85 -void cset_X_reserve(cset_X* self, size_t size); +bool cset_X_reserve(cset_X* self, size_t size); void cset_X_shrink_to_fit(cset_X* self); void cset_X_swap(cset_X* a, cset_X* b); void cset_X_del(cset_X* self); // destructor diff --git a/docs/cstack_api.md b/docs/cstack_api.md index 25cbcfb7..e71b213f 100644 --- a/docs/cstack_api.md +++ b/docs/cstack_api.md @@ -28,7 +28,7 @@ cstack_X cstack_with_size(size_t size, i_val fill); cstack_X cstack_X_clone(cstack_X st); void cstack_X_clear(cstack_X* self); -void cstack_X_reserve(cstack_X* self, size_t n); +bool cstack_X_reserve(cstack_X* self, size_t n); void cstack_X_shrink_to_fit(cstack_X* self); void cstack_X_copy(cstack_X* self, cstack_X other); void cstack_X_del(cstack_X* self); // destructor diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index bd7085c7..a2314122 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -46,7 +46,7 @@ STC_API _cx_self _cx_memb(_clone)(_cx_self cx); STC_API void _cx_memb(_clear)(_cx_self* self); STC_API void _cx_memb(_del)(_cx_self* self); STC_API _cx_value* _cx_memb(_push_back)(_cx_self* self, i_val value); -STC_API void _cx_memb(_expand_right_half_)(_cx_self* self, size_t idx, size_t n); +STC_API bool _cx_memb(_expand_right_half_)(_cx_self* self, size_t idx, size_t n); #ifndef i_queue STC_API _cx_iter _cx_memb(_find_in)(_cx_iter p1, _cx_iter p2, i_valraw raw); @@ -121,10 +121,10 @@ STC_INLINE size_t _cx_memb(_index)(_cx_self cx, _cx_iter it) { return it.ref - cx.data; } -STC_INLINE void +STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { size_t sz = cdeq_rep_(self)->size; - if (n > sz) _cx_memb(_expand_right_half_)(self, sz, n - sz); + return n <= sz || _cx_memb(_expand_right_half_)(self, sz, n - sz); } STC_INLINE _cx_iter @@ -236,18 +236,20 @@ _cx_memb(_realloc_)(_cx_self* self, size_t n) { size_t nfront = _cdeq_nfront(self); rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, offsetof(struct cdeq_rep, base) + cap*sizeof(i_val)); + if (!rep) return 0; rep->size = sz, rep->cap = cap; self->_base = (_cx_value *) rep->base; self->data = self->_base + nfront; return cap; } -STC_DEF void +STC_DEF bool _cx_memb(_expand_right_half_)(_cx_self* self, size_t idx, size_t n) { struct cdeq_rep* rep = cdeq_rep_(self); size_t sz = rep->size, cap = rep->cap; size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; - if (nback >= n || sz*1.3 + n > cap && _cx_memb(_realloc_)(self, n)) { + if (nback >= n || sz*1.3 + n > cap) { + if (!_cx_memb(_realloc_)(self, n)) return false; memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); } else { #ifdef i_queue @@ -260,6 +262,7 @@ _cx_memb(_expand_right_half_)(_cx_self* self, size_t idx, size_t n) { memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); self->data = self->_base + pos; } + return true; } STC_DEF _cx_value* diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 2d0a81f7..b12b80c7 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -91,7 +91,7 @@ STC_API _cx_self _cx_memb(_with_capacity)(size_t cap); STC_API _cx_self _cx_memb(_clone)(_cx_self map); STC_API void _cx_memb(_del)(_cx_self* self); STC_API void _cx_memb(_clear)(_cx_self* self); -STC_API void _cx_memb(_reserve)(_cx_self* self, size_t capacity); +STC_API bool _cx_memb(_reserve)(_cx_self* self, size_t capacity); STC_API chash_bucket_t _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr); STC_API _cx_result _cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey); STC_API void _cx_memb(_erase_entry)(_cx_self* self, _cx_value* val); @@ -103,7 +103,7 @@ STC_INLINE bool _cx_memb(_empty)(_cx_self m) { return m.size == 0; } STC_INLINE size_t _cx_memb(_size)(_cx_self m) { return m.size; } STC_INLINE size_t _cx_memb(_bucket_count)(_cx_self map) { return map.bucket_count; } STC_INLINE size_t _cx_memb(_capacity)(_cx_self map) - { return (size_t) (map.bucket_count * map.max_load_factor); } + { return (size_t)(map.bucket_count ? (map.bucket_count - 2)*map.max_load_factor : 0.f); } STC_INLINE void _cx_memb(_swap)(_cx_self *map1, _cx_self *map2) {c_swap(_cx_self, *map1, *map2); } STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, i_keyraw rkey) { return self->size && self->_hashx[_cx_memb(_bucket_)(self, &rkey).idx]; } @@ -319,9 +319,9 @@ _cx_memb(_clone)(_cx_self m) { return clone; } -STC_DEF void +STC_DEF bool _cx_memb(_reserve)(_cx_self* self, size_t _newcap) { - if (_newcap < self->size) return; + if (_newcap < self->size) return true; size_t _oldcap = self->bucket_count; _newcap = (size_t) (2 + _newcap / self->max_load_factor) | 1; _cx_self _tmp = { @@ -331,7 +331,10 @@ _cx_memb(_reserve)(_cx_self* self, size_t _newcap) { self->max_load_factor }; /* Rehash: */ - _tmp._hashx[_newcap] = 0xff; c_swap(_cx_self, *self, _tmp); + bool ret = true; + if (!(_tmp.table && _tmp._hashx)) { ret = false; goto done; } + _tmp._hashx[_newcap] = 0xff; + c_swap(_cx_self, *self, _tmp); _cx_value* e = _tmp.table, *_slot = self->table; uint8_t* _hashx = self->_hashx; for (size_t i = 0; i < _oldcap; ++i, ++e) @@ -341,8 +344,10 @@ _cx_memb(_reserve)(_cx_self* self, size_t _newcap) { _slot[b.idx] = *e; _hashx[b.idx] = (uint8_t) b.hx; } + done: c_free(_tmp._hashx); c_free((void *) _tmp.table); + return ret; } STC_DEF void diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 964a7058..c43072c9 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -44,16 +44,17 @@ STC_API void _cx_memb(_push)(_cx_self* self, _cx_value value); STC_API _cx_self _cx_memb(_clone)(_cx_self q); STC_INLINE _cx_self _cx_memb(_init)(void) - { return c_make(_cx_self){0, 0, 0}; } + { return c_make(_cx_self){0}; } -STC_INLINE _cx_self _cx_memb(_with_capacity)(size_t cap) { - _cx_self out = {(_cx_value *) c_malloc(cap*sizeof(_cx_value)), 0, cap}; - return out; +STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { + if (n != self->size && n < self->capacity) return true; + _cx_value *t = (_cx_value *)c_realloc(self->data, n*sizeof *t); + return t ? (self->data = t, self->capacity = n) : 0; } -STC_INLINE void _cx_memb(_reserve)(_cx_self* self, size_t n) { - if (n >= self->size) - self->data = (_cx_value *)c_realloc(self->data, (self->capacity = n)*sizeof(_cx_value)); +STC_INLINE _cx_self _cx_memb(_with_capacity)(size_t cap) { + _cx_self out = {0}; _cx_memb(_reserve)(&out, cap); + return out; } STC_INLINE void _cx_memb(_clear)(_cx_self* self) { @@ -121,8 +122,9 @@ _cx_memb(_make_heap)(_cx_self* self) { } STC_DEF _cx_self _cx_memb(_clone)(_cx_self q) { - _cx_self out = {(_cx_value *) c_malloc(q.size*sizeof(_cx_value)), q.size, q.size}; - for (size_t i = 0; i < q.size; ++i, ++q.data) out.data[i] = i_valfrom(i_valto(q.data)); + _cx_self out = _cx_memb(_with_capacity)(q.size); + for (; out.size < out.capacity; ++out.size, ++q.data) + out.data[out.size] = i_valfrom(i_valto(q.data)); return out; } diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 2a0e6b89..9d205c30 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -96,7 +96,7 @@ typedef cx_SET_ONLY( i_keyraw ) STC_API _cx_self _cx_memb(_init)(void); STC_API _cx_self _cx_memb(_clone)(_cx_self tree); STC_API void _cx_memb(_del)(_cx_self* self); -STC_API void _cx_memb(_reserve)(_cx_self* self, size_t cap); +STC_API bool _cx_memb(_reserve)(_cx_self* self, size_t cap); STC_API _cx_value* _cx_memb(_find_it)(const _cx_self* self, i_keyraw rkey, _cx_iter* out); STC_API _cx_iter _cx_memb(_lower_bound)(const _cx_self* self, i_keyraw rkey); STC_API _cx_value* _cx_memb(_front)(const _cx_self* self); @@ -237,18 +237,20 @@ _cx_memb(_back)(const _cx_self* self) { return &d[tn].value; } -STC_DEF void +STC_DEF bool _cx_memb(_reserve)(_cx_self* self, size_t cap) { struct csmap_rep* rep = _csmap_rep(self); - _cx_size oldcap = rep->cap; - if (cap > oldcap) { + if (cap >= rep->size) { + _cx_size oldcap = rep->cap; rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL, sizeof(struct csmap_rep) + (cap + 1)*sizeof(_cx_node)); + if (!rep) return false; if (oldcap == 0) memset(rep, 0, sizeof(struct csmap_rep) + sizeof(_cx_node)); rep->cap = cap; self->nodes = (_cx_node *) rep->nodes; } + return true; } STC_DEF _cx_size diff --git a/include/stc/cstack.h b/include/stc/cstack.h index a57dfcb8..099c2869 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -76,9 +76,10 @@ STC_INLINE _cx_value* _cx_memb(_top)(const _cx_self* self) STC_INLINE void _cx_memb(_pop)(_cx_self* self) { _cx_value* p = &self->data[--self->size]; i_valdel(p); } -STC_INLINE void _cx_memb(_reserve)(_cx_self* self, size_t n) { - if (n >= self->size) - self->data = (_cx_value *)c_realloc(self->data, (self->capacity = n)*sizeof(_cx_value)); +STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { + if (n < self->size) return true; + _cx_value *t = (_cx_value *)c_realloc(self->data, n*sizeof *t); + return t ? (self->data = t, self->capacity = n) : 0; } STC_INLINE void _cx_memb(_shrink_to_fit)(_cx_self* self) diff --git a/include/stc/cvec.h b/include/stc/cvec.h index e58e8793..0c6bb817 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -82,8 +82,8 @@ STC_API _cx_self _cx_memb(_init)(void); STC_API _cx_self _cx_memb(_clone)(_cx_self cx); STC_API void _cx_memb(_del)(_cx_self* self); STC_API void _cx_memb(_clear)(_cx_self* self); -STC_API void _cx_memb(_reserve)(_cx_self* self, size_t cap); -STC_API void _cx_memb(_resize)(_cx_self* self, size_t size, i_val fill_val); +STC_API bool _cx_memb(_reserve)(_cx_self* self, size_t cap); +STC_API bool _cx_memb(_resize)(_cx_self* self, size_t size, i_val fill_val); STC_API int _cx_memb(_value_compare)(const _cx_value* x, const _cx_value* y); STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_valraw raw); STC_API _cx_iter _cx_memb(_bsearch_in)(_cx_iter it1, _cx_iter it2, i_valraw raw); @@ -252,28 +252,31 @@ _cx_memb(_del)(_cx_self* self) { c_free(cvec_rep_(self)); } -STC_DEF void +STC_DEF bool _cx_memb(_reserve)(_cx_self* self, size_t cap) { struct cvec_rep* rep = cvec_rep_(self); size_t len = rep->size; - if (cap >= len && cap != rep->cap) { + if (cap >= len) { rep = (struct cvec_rep*) c_realloc(rep->cap ? rep : NULL, offsetof(struct cvec_rep, data) + cap*sizeof(i_val)); + if (!rep) return false; self->data = (_cx_value*) rep->data; rep->size = len; rep->cap = cap; } + return true; } -STC_DEF void +STC_DEF bool _cx_memb(_resize)(_cx_self* self, size_t len, i_val fill) { if (len > _cx_memb(_capacity)(*self)) - _cx_memb(_reserve)(self, len); + if (!_cx_memb(_reserve)(self, len)) return false; struct cvec_rep* rep = cvec_rep_(self); size_t i, n = rep->size; for (i = len; i < n; ++i) i_valdel(&self->data[i]); for (i = n; i < len; ++i) self->data[i] = fill; if (rep->cap) rep->size = len; + return true; } STC_DEF _cx_value* -- cgit v1.2.3