diff options
| -rw-r--r-- | docs/cmap_api.md | 2 | ||||
| -rw-r--r-- | docs/cpque_api.md | 2 | ||||
| -rw-r--r-- | docs/cset_api.md | 2 | ||||
| -rw-r--r-- | docs/cstack_api.md | 2 | ||||
| -rw-r--r-- | include/stc/cdeq.h | 13 | ||||
| -rw-r--r-- | include/stc/cmap.h | 15 | ||||
| -rw-r--r-- | include/stc/cpque.h | 20 | ||||
| -rw-r--r-- | include/stc/csmap.h | 10 | ||||
| -rw-r--r-- | include/stc/cstack.h | 7 | ||||
| -rw-r--r-- | 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*
|