diff options
| author | Tyge Løvset <[email protected]> | 2022-05-07 16:38:58 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2022-05-07 16:38:58 +0200 |
| commit | e9c30e66af9c5c3054735eeb65c0bb384dea96b4 (patch) | |
| tree | e144846216b6be8937a0067802d7c1bfdfac269c /include/stc | |
| parent | d9dc93a90e1ac0a42e946be52b169e1175377c4f (diff) | |
| download | STC-modified-e9c30e66af9c5c3054735eeb65c0bb384dea96b4.tar.gz STC-modified-e9c30e66af9c5c3054735eeb65c0bb384dea96b4.zip | |
Updated alt/csmap.h to be synced with current csmap.h; alt-version allocates each node separately on the heap, regular uses an array.
Now alt-version of csmap and cstr can be used by defining -DSTC_CSMAP_V1 and -DSTC_CSTR_V1 when compiling.
Improved code readability by making line breaks after if and while (also cmap.h).
Note, the alt-versions may be removed in the future, but the alt csmap.h may be made into an intrusive sorted map, where the creation and destruction of nodes must be done by the user.
Diffstat (limited to 'include/stc')
| -rw-r--r-- | include/stc/alt/csmap.h | 822 | ||||
| -rw-r--r-- | include/stc/alt/cstr.h | 4 | ||||
| -rw-r--r-- | include/stc/cmap.h | 68 | ||||
| -rw-r--r-- | include/stc/csmap.h | 134 | ||||
| -rw-r--r-- | include/stc/cstr.h | 4 | ||||
| -rw-r--r-- | include/stc/forward.h | 35 |
6 files changed, 627 insertions, 440 deletions
diff --git a/include/stc/alt/csmap.h b/include/stc/alt/csmap.h index 6794bec3..b7c4fe39 100644 --- a/include/stc/alt/csmap.h +++ b/include/stc/alt/csmap.h @@ -20,385 +20,491 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
-#ifndef CSMAP_H_INCLUDED
-#define CSMAP_H_INCLUDED
// Sorted/Ordered set and map - implemented as an AA-tree.
/*
#include <stdio.h>
+#include <stc/cstr.h>
+
+#define i_tag sx // Sorted map<cstr, double>
+#define i_key_str
+#define i_val double
#include <stc/csmap.h>
-using_csmap(mx, int, char); // Sorted map<int, char>
int main(void) {
- c_autovar (csmap_mx m = csmap_mx_init(), csmap_mx_drop(&m))
+ c_autovar (csmap_sx m = csmap_sx_init(), csmap_sx_drop(&m))
{
- csmap_mx_insert(&m, 5, 'a');
- csmap_mx_insert(&m, 8, 'b');
- csmap_mx_insert(&m, 12, 'c');
+ csmap_sx_emplace(&m, "Testing one", 1.234);
+ csmap_sx_emplace(&m, "Testing two", 12.34);
+ csmap_sx_emplace(&m, "Testing three", 123.4);
- csmap_mx_iter it = csmap_mx_find(&m, 10); // none
- char val = csmap_mx_find(&m, 5).ref->second;
- csmap_mx_push(&m, 5, 'd'); // update
- csmap_mx_erase(&m, 8);
+ csmap_sx_value *v = csmap_sx_get(&m, "Testing five"); // NULL
+ double num = *csmap_sx_at(&m, "Testing one");
+ csmap_sx_emplace_or_assign(&m, "Testing three", 1000.0); // update
+ csmap_sx_erase(&m, "Testing two");
- c_foreach (i, csmap_mx, m)
- printf("map %d: %c\n", i.ref->first, i.ref->second);
+ c_foreach (i, csmap_sx, m)
+ printf("map %s: %g\n", cstr_str(&i.ref->first), i.ref->second);
}
}
*/
#include <stc/ccommon.h>
-#include <stc/template.h>
+
+#ifndef CSMAP_H_INCLUDED
+#define STC_CSMAP_V1 1
+#include <stc/forward.h>
#include <stdlib.h>
#include <string.h>
+#endif // CSMAP_H_INCLUDED
-#define KEY_REF_csmap_(vp) (&(vp)->first)
-#define _c_aatree_complete_types(_cx_self, C) \
- _i_MAP_ONLY( struct _cx_value { \
- _cx_key first; \
- _cx_mapped second; \
- }; ) \
- struct _cx_node { \
- struct _cx_node *link[2]; \
- uint8_t level; \
- _cx_value value; \
- }
+#ifndef _i_prefix
+#define _i_prefix csmap_
+#endif
+#ifdef _i_isset
+ #define _i_MAP_ONLY c_false
+ #define _i_SET_ONLY c_true
+ #define _i_keyref(vp) (vp)
+#else
+ #define _i_ismap
+ #define _i_MAP_ONLY c_true
+ #define _i_SET_ONLY c_false
+ #define _i_keyref(vp) (&(vp)->first)
+#endif
+#include <stc/template.h>
-#ifndef cx_forwarded
- _c_aatree_types(_cx_self, C, i_key, i_val, i_size);
-#endif
-
- _c_aatree_complete_types(_cx_self, C); \
-\
- typedef i_keyraw _cx_rawkey; \
- typedef i_valraw _cx_memb(_rawmapped); \
- typedef _i_SET_ONLY( _cx_rawkey ) \
- _i_MAP_ONLY( struct { _cx_rawkey first; \
- _cx_memb(_rawmapped) second; } ) \
- _cx_raw; \
-\
- STC_API _cx_self _cx_memb(_init)(void); \
- 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); \
- STC_API _cx_value* _cx_memb(_back)(const _cx_self* self); \
- STC_API _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it); \
- STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2); \
- STC_API _cx_node* _cx_memb(_erase_r_)(_cx_node *tn, const _cx_rawkey* rkey, int *erased); \
- STC_API void _cx_memb(_del_r_)(_cx_node* tn); \
- STC_API _cx_node* _cx_memb(_clone_r_)(_cx_node *tn); \
- STC_API _cx_result _cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey); \
- STC_API void _cx_memb(_next)(_cx_iter* it); \
-\
- STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return cx.size == 0; } \
- STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return cx.size; } \
- STC_INLINE void _cx_memb(_drop)(_cx_self* self) { _cx_memb(_del_r_)(self->root); } \
- STC_INLINE void _cx_memb(_clear)(_cx_self* self) { _cx_memb(_drop)(self); *self = _cx_memb(_init)(); } \
- STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) {c_swap(_cx_self, *a, *b); } \
- STC_INLINE _cx_self _cx_memb(_clone)(_cx_self cx) { return c_make(_cx_self){ _cx_memb(_clone_r_)(cx.root), cx.size}; } \
- STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey) \
- {_cx_iter it; _cx_memb(_find_it)(self, rkey, &it); return it; } \
- STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, i_keyraw rkey) \
- {_cx_iter it; return _cx_memb(_find_it)(self, rkey, &it) != NULL; } \
- STC_INLINE _cx_value* _cx_memb(_get)(const _cx_self* self, i_keyraw rkey) \
- {_cx_iter it; return _cx_memb(_find_it)(self, rkey, &it); } \
-\
- STC_INLINE void \
- _cx_memb(_value_drop)(_cx_value* val) { \
- i_keydrop(_i_keyref(val)); \
- _i_MAP_ONLY( i_valdrop((&val->second)); ) \
- } \
-\
- STC_INLINE void \
- _cx_memb(_value_clone)(_cx_value* dst, _cx_value* val) { \
- *_i_keyref(dst) = i_keyfrom(i_keyto(_i_keyref(val))); \
- _i_MAP_ONLY( i_valraw r = i_valto((&val->second)); dst->second = i_valfrom(r); ) \
- } \
-\
- STC_INLINE _cx_result \
- _cx_memb(_emplace)(_cx_self* self, i_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)) { \
- _cx_result res = _cx_memb(_insert_entry_)(self, rkey); \
- if (res.inserted) { \
- *_i_keyref(res.ref) = i_keyfrom(rkey); \
- _i_MAP_ONLY(res.ref->second = i_valfrom(rmapped);) \
- } \
- return res; \
- } \
-\
- STC_INLINE void \
- _cx_memb(_emplace_items)(_cx_self* self, const _cx_raw arr[], size_t n) { \
- for (size_t i=0; i<n; ++i) _i_SET_ONLY( _cx_memb(_emplace)(self, arr[i]); ) \
- _i_MAP_ONLY( _cx_memb(_emplace)(self, arr[i].first, arr[i].second); ) \
- } \
-\
- STC_INLINE _cx_result \
- _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)) { \
- _cx_result res = _cx_memb(_insert_entry_)(self, i_keyto((&key))); \
- if (res.inserted) {*_i_keyref(res.ref) = key; _i_MAP_ONLY( res.ref->second = mapped; )} \
- else {i_keydrop((&key)); _i_MAP_ONLY( i_valdrop((&mapped)); )} \
- return res; \
- } \
-\
- _i_MAP_ONLY( \
- STC_INLINE _cx_result \
- _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped) { \
- _cx_result res = _cx_memb(_insert_entry_)(self, i_keyto((&key))); \
- if (res.inserted) res.ref->first = key; \
- else {i_keydrop((&key)); i_valdrop((&res.ref->second)); } \
- res.ref->second = mapped; return res; \
- } \
- \
- STC_INLINE _cx_result \
- _cx_memb(_put)(_cx_self* self, i_key key, i_val mapped) { \
- return _cx_memb(_insert_or_assign)(self, key, mapped); \
- } \
- \
- STC_INLINE _cx_result \
- _cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped) { \
- _cx_result res = _cx_memb(_insert_entry_)(self, rkey); \
- if (res.inserted) res.ref->first = i_keyfrom(rkey); \
- else i_valdrop((&res.ref->second)); \
- res.ref->second = i_valfrom(rmapped); return res; \
- } \
- \
- STC_INLINE const _cx_mapped* \
- _cx_memb(_at)(const _cx_self* self, i_keyraw rkey) { \
- _cx_iter it; \
- return &_cx_memb(_find_it)(self, rkey, &it)->second; \
- }) \
-\
- STC_INLINE _cx_iter \
- _cx_memb(_begin)(const _cx_self* self) { \
- _cx_iter it = {NULL, 0, self->root}; \
- _cx_memb(_next)(&it); return it; \
- } \
-\
- STC_INLINE _cx_iter \
- _cx_memb(_end)(const _cx_self* self) {\
- _cx_iter it = {NULL}; return it; \
- } \
-\
- STC_INLINE size_t \
- _cx_memb(_erase)(_cx_self* self, i_keyraw rkey) { \
- int erased = 0; \
- self->root = _cx_memb(_erase_r_)(self->root, &rkey, &erased); \
- self->size -= erased; return erased; \
- } \
-\
- STC_INLINE _cx_iter \
- _cx_memb(_advance)(_cx_iter it, size_t n) { \
- while (n-- && it.ref) _cx_memb(_next)(&it); \
- return it; \
- } \
-\
- _c_implement_aatree(_cx_self, C, i_key, i_val, i_cmp, \
- i_valdrop, i_valfrom, i_valto, i_valraw, \
- i_keydrop, i_keyfrom, i_keyto, i_keyraw) \
- struct stc_trailing_semicolon
+#if !c_option(c_is_fwd)
+_cx_deftypes(_c_aatree_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY);
+#endif
-/* -------------------------- IMPLEMENTATION ------------------------- */
+_i_MAP_ONLY( struct _cx_value {
+ _cx_key first;
+ _cx_mapped second;
+}; )
+struct _cx_node {
+ struct _cx_node *link[2];
+ uint8_t level;
+ _cx_value value;
+};
+
+typedef i_keyraw _cx_rawkey;
+typedef i_valraw _cx_memb(_rawmapped);
+typedef _i_SET_ONLY( i_keyraw )
+ _i_MAP_ONLY( struct { i_keyraw first; i_valraw second; } )
+ _cx_raw;
+#if !defined _i_no_clone
+STC_API _cx_self _cx_memb(_clone)(_cx_self cx);
+#if !defined _i_no_emplace
+STC_API _cx_result _cx_memb(_emplace)(_cx_self* self, i_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped));
+#endif // !_i_no_emplace
+#endif // !_i_no_clone
+STC_API _cx_self _cx_memb(_init)(void);
+STC_API _cx_result _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped));
+STC_API _cx_result _cx_memb(_push)(_cx_self* self, _cx_value _val);
+STC_API void _cx_memb(_drop)(_cx_self* self);
+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);
+STC_API _cx_value* _cx_memb(_back)(const _cx_self* self);
+STC_API int _cx_memb(_erase)(_cx_self* self, i_keyraw rkey);
+STC_API _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it);
+STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2);
+STC_API void _cx_memb(_next)(_cx_iter* it);
+
+STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return cx.size == 0; }
+STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return cx.size; }
+STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); }
+STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey)
+ { _cx_iter it; _cx_memb(_find_it)(self, rkey, &it); return it; }
+STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, i_keyraw rkey)
+ { _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it) != NULL; }
+STC_INLINE const _cx_value* _cx_memb(_get)(const _cx_self* self, i_keyraw rkey)
+ { _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it); }
+STC_INLINE _cx_value* _cx_memb(_get_mut)(_cx_self* self, i_keyraw rkey)
+ { _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it); }
+
+STC_INLINE void
+_cx_memb(_clear)(_cx_self* self)
+ { _cx_memb(_drop)(self); *self = _cx_memb(_init)(); }
+
+STC_INLINE _cx_raw
+_cx_memb(_value_toraw)(_cx_value* val) {
+ return _i_SET_ONLY( i_keyto(val) )
+ _i_MAP_ONLY( c_make(_cx_raw){i_keyto((&val->first)),
+ i_valto((&val->second))} );
+}
+
+STC_INLINE int
+_cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y) {
+ _cx_rawkey rx = i_keyto(_i_keyref(x)), ry = i_keyto(_i_keyref(y));
+ return i_cmp((&rx), (&ry));
+}
+
+STC_INLINE void
+_cx_memb(_value_drop)(_cx_value* val) {
+ i_keydrop(_i_keyref(val));
+ _i_MAP_ONLY( i_valdrop((&val->second)); )
+}
+
+#if !defined _i_no_clone
+STC_INLINE _cx_value
+_cx_memb(_value_clone)(_cx_value _val) {
+ *_i_keyref(&_val) = i_keyclone((*_i_keyref(&_val)));
+ _i_MAP_ONLY( _val.second = i_valclone(_val.second); )
+ return _val;
+}
+
+STC_INLINE void
+_cx_memb(_copy)(_cx_self *self, _cx_self other) {
+ if (self->root == other.root)
+ return;
+ _cx_memb(_drop)(self);
+ *self = _cx_memb(_clone)(other);
+}
+#endif // !_i_no_clone
+
+#ifndef _i_isset
+ #if !defined _i_no_clone && !defined _i_no_emplace
+ STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped);
+ #endif
+ STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped);
+
+ STC_INLINE const _cx_mapped*
+ _cx_memb(_at)(const _cx_self* self, i_keyraw rkey)
+ { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; }
+ STC_INLINE _cx_mapped*
+ _cx_memb(_at_mut)(_cx_self* self, i_keyraw rkey)
+ { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; }
+#endif // !_i_isset
+
+STC_INLINE _cx_iter
+_cx_memb(_begin)(const _cx_self* self) {
+ _cx_iter it;
+ it.ref = NULL, it._top = 0, it._tn = self->root;
+ _cx_memb(_next)(&it);
+ return it;
+}
+
+STC_INLINE _cx_iter
+_cx_memb(_end)(const _cx_self* self) {
+ (void)self;
+ _cx_iter it; it.ref = NULL, it._top = 0, it._tn = NULL;
+ return it;
+}
+
+STC_INLINE _cx_iter
+_cx_memb(_advance)(_cx_iter it, size_t n) {
+ while (n-- && it.ref)
+ _cx_memb(_next)(&it);
+ return it;
+}
+
+/* -------------------------- IMPLEMENTATION ------------------------- */
#if defined(i_implement)
-_c_aatree_types(csmap_SENTINEL, csmap_, int, int, i_size);
-_c_aatree_complete_types(csmap_SENTINEL, csmap_);
-static csmap_SENTINEL_node _aatree_sentinel = {&_aatree_sentinel, &_aatree_sentinel, 0};
-
-#define _c_implement_aatree(_cx_self, C, i_key, i_val, i_cmp, \
- i_valdrop, i_valfrom, i_valto, i_valraw, \
- i_keydrop, i_keyfrom, i_keyto, i_keyraw) \
- STC_DEF _cx_self \
- _cx_memb(_init)(void) { \
- _cx_self cx = {(_cx_node *) &_aatree_sentinel, 0}; \
- return cx; \
- } \
-\
- STC_DEF _cx_value* \
- _cx_memb(_front)(const _cx_self* self) { \
- _cx_node *tn = self->root; \
- while (tn->link[0]->level) tn = tn->link[0]; \
- return &tn->value; \
- } \
-\
- STC_DEF _cx_value* \
- _cx_memb(_back)(const _cx_self* self) { \
- _cx_node *tn = self->root; \
- while (tn->link[1]->level) tn = tn->link[1]; \
- return &tn->value; \
- } \
-\
- STC_DEF _cx_value* \
- _cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) { \
- _cx_node *tn = self->root; \
- out->_top = 0; \
- while (tn->level) { \
- int c; _cx_rawkey rx = i_keyto(_i_keyref(&tn->value)); \
- if ((c = (i_cmp((&rx), (&rkey)))) < 0) tn = tn->link[1]; \
- else if (c > 0) {out->_st[out->_top++] = tn; tn = tn->link[0]; } \
- else {out->_tn = tn->link[1]; return (out->ref = &tn->value); } \
- } \
- return (out->ref = NULL); \
- } \
-\
- STC_DEF _cx_iter \
- _cx_memb(_lower_bound)(const _cx_self* self, i_keyraw rkey) { \
- _cx_iter it; \
- _cx_memb(_find_it)(self, rkey, &it); \
- if (!it.ref && it._top) { \
- _cx_node *tn = it._st[--it._top]; \
- it._tn = tn->link[1]; \
- it.ref = &tn->value; \
- } \
- return it; \
- } \
-\
- STC_DEF void \
- _cx_memb(_next)(_cx_iter *it) { \
- _cx_node *tn = it->_tn; \
- if (it->_top || tn->level) { \
- while (tn->level) { \
- it->_st[it->_top++] = tn; \
- tn = tn->link[0]; \
- } \
- tn = it->_st[--it->_top]; \
- it->_tn = tn->link[1]; \
- it->ref = &tn->value; \
- } else \
- it->ref = NULL; \
- } \
-\
- static _cx_node * \
- _cx_memb(_skew_)(_cx_node *tn) { \
- if (tn && tn->link[0]->level == tn->level && tn->level) { \
- _cx_node *tmp = tn->link[0]; \
- tn->link[0] = tmp->link[1]; \
- tmp->link[1] = tn; \
- tn = tmp; \
- } \
- return tn; \
- } \
-\
- static _cx_node * \
- _cx_memb(_split_)(_cx_node *tn) { \
- if (tn->link[1]->link[1]->level == tn->level && tn->level) { \
- _cx_node *tmp = tn->link[1]; \
- tn->link[1] = tmp->link[0]; \
- tmp->link[0] = tn; \
- tn = tmp; \
- ++tn->level; \
- } \
- return tn; \
- } \
-\
- static inline _cx_node* \
- _cx_memb(_insert_entry_i_)(_cx_node* tn, const _cx_rawkey* rkey, _cx_result* res) { \
- _cx_node *up[64], *tx = tn; \
- int c, top = 0, dir = 0; \
- while (tx->level) { \
- up[top++] = tx; \
- _cx_rawkey r = i_keyto(_i_keyref(&tx->value)); \
- if (!(c = (i_cmp((&r), rkey)))) {res->ref = &tx->value; return tn; } \
- tx = tx->link[(dir = (c < 0))]; \
- } \
- tn = c_alloc(_cx_node); \
- res->ref = &tn->value, res->inserted = true; \
- tn->link[0] = tn->link[1] = (_cx_node*) &_aatree_sentinel, tn->level = 1; \
- if (top == 0) return tn; \
- up[top - 1]->link[dir] = tn; \
- while (top--) { \
- if (top) dir = (up[top - 1]->link[1] == up[top]); \
- up[top] = _cx_memb(_skew_)(up[top]); \
- up[top] = _cx_memb(_split_)(up[top]); \
- if (top) up[top - 1]->link[dir] = up[top]; \
- } \
- return up[0]; \
- } \
-\
- STC_DEF _cx_result \
- _cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey) { \
- _cx_result res = {NULL, false}; \
- self->root = _cx_memb(_insert_entry_i_)(self->root, &rkey, &res); \
- self->size += res.inserted; \
- return res; \
- } \
-\
- STC_DEF _cx_node* \
- _cx_memb(_erase_r_)(_cx_node *tn, const _cx_rawkey* rkey, int *erased) { \
- if (tn->level == 0) \
- return tn; \
- _cx_rawkey raw = i_keyto(_i_keyref(&tn->value)); \
- _cx_node *tx; int c = (i_cmp((&raw), rkey)); \
- if (c != 0) \
- tn->link[c < 0] = _cx_memb(_erase_r_)(tn->link[c < 0], rkey, erased); \
- else { \
- if (!*erased) { _cx_memb(_value_drop)(&tn->value); *erased = 1; } \
- if (tn->link[0]->level && tn->link[1]->level) { \
- tx = tn->link[0]; \
- while (tx->link[1]->level) \
- tx = tx->link[1]; \
- tn->value = tx->value; \
- raw = i_keyto(_i_keyref(&tn->value)); \
- tn->link[0] = _cx_memb(_erase_r_)(tn->link[0], &raw, erased); \
- } else { \
- tx = tn; \
- tn = tn->link[tn->link[0]->level == 0]; \
- c_free(tx); \
- } \
- } \
- if (tn->link[0]->level < tn->level - 1 || tn->link[1]->level < tn->level - 1) { \
- if (tn->link[1]->level > --tn->level) \
- tn->link[1]->level = tn->level; \
- tn = _cx_memb(_skew_)(tn); \
- tx = tn->link[0] = _cx_memb(_skew_)(tn->link[0]); \
- tx->link[0] = _cx_memb(_skew_)(tx->link[0]); \
- tn = _cx_memb(_split_)(tn); \
- tn->link[0] = _cx_memb(_split_)(tn->link[0]); \
- } \
- return tn; \
- } \
- STC_DEF _cx_iter \
- _cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { \
- _cx_rawkey raw = i_keyto(_i_keyref(it.ref)), nxt; \
- _cx_memb(_next)(&it); \
- if (it.ref) nxt = i_keyto(_i_keyref(it.ref)); \
- _cx_memb(_erase)(self, raw); \
- if (it.ref) _cx_memb(_find_it)(self, nxt, &it); \
- return it; \
- } \
-\
- STC_DEF _cx_iter \
- _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) { \
- if (!it2.ref) { while (it1.ref) it1 = _cx_memb(_erase_at)(self, it1); \
- return it1; } \
- _cx_key k1 = *_i_keyref(it1.ref), k2 = *_i_keyref(it2.ref); \
- _cx_rawkey r1 = i_keyto((&k1)); \
- for (;;) { \
- if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; \
- _cx_memb(_next)(&it1); k1 = *_i_keyref(it1.ref); \
- _cx_memb(_erase)(self, r1); \
- _cx_memb(_find_it)(self, (r1 = i_keyto((&k1))), &it1); \
- } \
- } \
-\
- STC_DEF _cx_node* \
- _cx_memb(_clone_r_)(_cx_node *tn) { \
- if (! tn->level) return tn; \
- _cx_node *cn = c_alloc(_cx_node); \
- cn->link[0] = _cx_memb(_clone_r_)(tn->link[0]); \
- cn->link[1] = _cx_memb(_clone_r_)(tn->link[1]); \
- cn->level = tn->level; \
- _cx_memb(_value_clone)(&cn->value, &tn->value); \
- return cn; \
- } \
-\
- STC_DEF void \
- _cx_memb(_del_r_)(_cx_node* tn) { \
- if (tn->level != 0) { \
- _cx_memb(_del_r_)(tn->link[0]); \
- _cx_memb(_del_r_)(tn->link[1]); \
- _cx_memb(_value_drop)(&tn->value); \
- c_free(tn); \
- } \
+#ifndef CSMAP_H_INCLUDED
+static struct { void *link[2]; uint8_t level; }
+_csmap_sentinel = {{&_csmap_sentinel, &_csmap_sentinel}, 0};
+#endif
+
+static _cx_result _cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey);
+
+STC_DEF _cx_self
+_cx_memb(_init)(void) {
+ _cx_self cx = {(_cx_node *)&_csmap_sentinel, 0};
+ return cx;
+}
+
+STC_DEF _cx_value*
+_cx_memb(_front)(const _cx_self* self) {
+ _cx_node *tn = self->root;
+ while (tn->link[0]->level)
+ tn = tn->link[0];
+ return &tn->value;
+}
+
+STC_DEF _cx_value*
+_cx_memb(_back)(const _cx_self* self) {
+ _cx_node *tn = self->root;
+ while (tn->link[1]->level)
+ tn = tn->link[1];
+ return &tn->value;
+}
+
+STC_DEF _cx_result
+_cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)) {
+ _cx_result res = _cx_memb(_insert_entry_)(self, i_keyto((&key)));
+ if (res.inserted)
+ { *_i_keyref(res.ref) = key; _i_MAP_ONLY( res.ref->second = mapped; )}
+ else
+ { i_keydrop((&key)); _i_MAP_ONLY( i_valdrop((&mapped)); )}
+ return res;
+}
+
+STC_DEF _cx_result
+_cx_memb(_push)(_cx_self* self, _cx_value _val) {
+ _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val)));
+ if (_res.inserted)
+ *_res.ref = _val;
+ else
+ _cx_memb(_value_drop)(&_val);
+ return _res;
+}
+
+#ifndef _i_isset
+ STC_DEF _cx_result
+ _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped) {
+ _cx_result res = _cx_memb(_insert_entry_)(self, i_keyto((&key)));
+ if (res.inserted)
+ res.ref->first = key;
+ else
+ { i_keydrop((&key)); i_valdrop((&res.ref->second)); }
+ res.ref->second = mapped;
+ return res;
}
+ #if !defined _i_no_clone && !defined _i_no_emplace
+ STC_DEF _cx_result
+ _cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped) {
+ _cx_result res = _cx_memb(_insert_entry_)(self, rkey);
+ if (res.inserted)
+ res.ref->first = i_keyfrom(rkey);
+ else
+ { i_valdrop((&res.ref->second)); }
+ res.ref->second = i_valfrom(rmapped);
+ return res;
+ }
+ #endif // !_i_no_clone && !_i_no_emplace
+#endif // !_i_isset
-#endif
-#endif
+STC_DEF _cx_value*
+_cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) {
+ _cx_node *tn = self->root;
+ out->_top = 0;
+ while (tn->level) {
+ int c; _cx_rawkey raw = i_keyto(_i_keyref(&tn->value));
+ if ((c = i_cmp((&raw), (&rkey))) < 0)
+ tn = tn->link[1];
+ else if (c > 0)
+ { out->_st[out->_top++] = tn; tn = tn->link[0]; }
+ else
+ { out->_tn = tn->link[1]; return (out->ref = &tn->value); }
+ }
+ return (out->ref = NULL);
+}
+
+STC_DEF _cx_iter
+_cx_memb(_lower_bound)(const _cx_self* self, i_keyraw rkey) {
+ _cx_iter it;
+ _cx_memb(_find_it)(self, rkey, &it);
+ if (!it.ref && it._top) {
+ _cx_node *tn = it._st[--it._top];
+ it._tn = tn->link[1];
+ it.ref = &tn->value;
+ }
+ return it;
+}
+
+STC_DEF void
+_cx_memb(_next)(_cx_iter *it) {
+ _cx_node *tn = it->_tn;
+ if (it->_top || tn->level) {
+ while (tn->level) {
+ it->_st[it->_top++] = tn;
+ tn = tn->link[0];
+ }
+ tn = it->_st[--it->_top];
+ it->_tn = tn->link[1];
+ it->ref = &tn->value;
+ } else
+ it->ref = NULL;
+}
+
+static _cx_node *
+_cx_memb(_skew_)(_cx_node *tn) {
+ if (tn && tn->link[0]->level == tn->level && tn->level) {
+ _cx_node *tmp = tn->link[0];
+ tn->link[0] = tmp->link[1];
+ tmp->link[1] = tn;
+ tn = tmp;
+ }
+ return tn;
+}
+
+static _cx_node *
+_cx_memb(_split_)(_cx_node *tn) {
+ if (tn->link[1]->link[1]->level == tn->level && tn->level) {
+ _cx_node *tmp = tn->link[1];
+ tn->link[1] = tmp->link[0];
+ tmp->link[0] = tn;
+ tn = tmp;
+ ++tn->level;
+ }
+ return tn;
+}
+
+static _cx_node*
+_cx_memb(_insert_entry_i_)(_cx_node* tn, const _cx_rawkey* rkey, _cx_result* res) {
+ _cx_node *up[64], *tx = tn;
+ int c, top = 0, dir = 0;
+ while (tx->level) {
+ up[top++] = tx;
+ _cx_rawkey r = i_keyto(_i_keyref(&tx->value));
+ if (!(c = (i_cmp((&r), rkey))))
+ { res->ref = &tx->value; return tn; }
+ dir = (c < 0);
+ tx = tx->link[dir];
+ }
+ tn = c_alloc(_cx_node);
+ tn->link[0] = tn->link[1] = (_cx_node*)&_csmap_sentinel;
+ tn->level = 1;
+ res->ref = &tn->value, res->inserted = true;
+ if (top == 0)
+ return tn;
+ up[top - 1]->link[dir] = tn;
+ while (top--) {
+ if (top)
+ dir = (up[top - 1]->link[1] == up[top]);
+ up[top] = _cx_memb(_skew_)(up[top]);
+ up[top] = _cx_memb(_split_)(up[top]);
+ if (top)
+ up[top - 1]->link[dir] = up[top];
+ }
+ return up[0];
+}
+
+STC_DEF _cx_result
+_cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey) {
+ _cx_result res = {NULL};
+ self->root = _cx_memb(_insert_entry_i_)(self->root, &rkey, &res);
+ self->size += res.inserted;
+ return res;
+}
+
+static _cx_node*
+_cx_memb(_erase_r_)(_cx_node *tn, const _cx_rawkey* rkey, int *erased) {
+ if (tn->level == 0)
+ return tn;
+ _cx_rawkey raw = i_keyto(_i_keyref(&tn->value));
+ _cx_node *tx; int c = (i_cmp((&raw), rkey));
+ if (c != 0)
+ tn->link[c < 0] = _cx_memb(_erase_r_)(tn->link[c < 0], rkey, erased);
+ else {
+ if (!*erased)
+ { _cx_memb(_value_drop)(&tn->value); *erased = 1; }
+ if (tn->link[0]->level && tn->link[1]->level) {
+ tx = tn->link[0];
+ while (tx->link[1]->level)
+ tx = tx->link[1];
+ tn->value = tx->value;
+ raw = i_keyto(_i_keyref(&tn->value));
+ tn->link[0] = _cx_memb(_erase_r_)(tn->link[0], &raw, erased);
+ } else { /* unlink node */
+ tx = tn;
+ tn = tn->link[tn->link[0]->level == 0];
+ c_free(tx);
+ }
+ }
+ if (tn->link[0]->level < tn->level - 1 || tn->link[1]->level < tn->level - 1) {
+ if (tn->link[1]->level > --tn->level)
+ tn->link[1]->level = tn->level;
+ tn = _cx_memb(_skew_)(tn);
+ tx = tn->link[0] = _cx_memb(_skew_)(tn->link[0]);
+ tx->link[0] = _cx_memb(_skew_)(tx->link[0]);
+ tn = _cx_memb(_split_)(tn);
+ tn->link[0] = _cx_memb(_split_)(tn->link[0]);
+ }
+ return tn;
+}
+
+STC_DEF int
+_cx_memb(_erase)(_cx_self* self, i_keyraw rkey) {
+ int erased = 0;
+ self->root = _cx_memb(_erase_r_)(self->root, &rkey, &erased);
+ self->size -= erased;
+ return erased;
+}
+
+STC_DEF _cx_iter
+_cx_memb(_erase_at)(_cx_self* self, _cx_iter it) {
+ _cx_rawkey raw = i_keyto(_i_keyref(it.ref)), nxt;
+ _cx_memb(_next)(&it);
+ if (it.ref)
+ nxt = i_keyto(_i_keyref(it.ref));
+ _cx_memb(_erase)(self, raw);
+ if (it.ref)
+ _cx_memb(_find_it)(self, nxt, &it);
+ return it;
+}
+
+STC_DEF _cx_iter
+_cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) {
+ if (!it2.ref) {
+ while (it1.ref)
+ it1 = _cx_memb(_erase_at)(self, it1);
+ return it1;
+ }
+ _cx_key k1 = *_i_keyref(it1.ref), k2 = *_i_keyref(it2.ref);
+ _cx_rawkey r1 = i_keyto((&k1));
+ for (;;) {
+ if (memcmp(&k1, &k2, sizeof k1) == 0)
+ return it1;
+ _cx_memb(_next)(&it1); k1 = *_i_keyref(it1.ref);
+ _cx_memb(_erase)(self, r1);
+ _cx_memb(_find_it)(self, (r1 = i_keyto((&k1))), &it1);
+ }
+}
+
+#if !defined _i_no_clone
+static _cx_node*
+_cx_memb(_clone_r_)(_cx_node *tn) {
+ if (! tn->level)
+ return tn;
+ _cx_node *cn = c_alloc(_cx_node);
+ cn->level = tn->level;
+ cn->value = _cx_memb(_value_clone)(tn->value);
+ cn->link[0] = _cx_memb(_clone_r_)(tn->link[0]);
+ cn->link[1] = _cx_memb(_clone_r_)(tn->link[1]);
+ return cn;
+}
+
+STC_DEF _cx_self
+_cx_memb(_clone)(_cx_self cx) {
+ return c_make(_cx_self){_cx_memb(_clone_r_)(cx.root), cx.size};
+}
+
+#if !defined _i_no_emplace
+STC_DEF _cx_result
+_cx_memb(_emplace)(_cx_self* self, i_keyraw rkey _i_MAP_ONLY(, i_valraw rmapped)) {
+ _cx_result res = _cx_memb(_insert_entry_)(self, rkey);
+ if (res.inserted) {
+ *_i_keyref(res.ref) = i_keyfrom(rkey);
+ _i_MAP_ONLY(res.ref->second = i_valfrom(rmapped);)
+ }
+ return res;
+}
+#endif // _i_no_emplace
+#endif // !_i_no_clone
+
+static void
+_cx_memb(_drop_r_)(_cx_node* tn) {
+ if (tn->level != 0) {
+ _cx_memb(_drop_r_)(tn->link[0]);
+ _cx_memb(_drop_r_)(tn->link[1]);
+ _cx_memb(_value_drop)(&tn->value);
+ c_free(tn);
+ }
+}
+
+STC_DEF void
+_cx_memb(_drop)(_cx_self* self) {
+ _cx_memb(_drop_r_)(self->root);
+}
+
+#endif // i_implement
+#undef _i_isset
+#undef _i_ismap
+#undef _i_keyref
+#undef _i_MAP_ONLY
+#undef _i_SET_ONLY
+#define CSMAP_H_INCLUDED
+#include <stc/template.h>
diff --git a/include/stc/alt/cstr.h b/include/stc/alt/cstr.h index db9c0505..98f5c8f5 100644 --- a/include/stc/alt/cstr.h +++ b/include/stc/alt/cstr.h @@ -22,7 +22,7 @@ */
#ifndef CSTR_H_INCLUDED
#define CSTR_H_INCLUDED
-#define STC_OLD_CSTR 1
+#define STC_CSTR_V1 1
#include <stc/ccommon.h>
#include <stc/forward.h>
@@ -386,5 +386,5 @@ cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { }
#endif
-#endif
+#endif // CSTR_H_INCLUDED
#undef i_opt
diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 3da6b071..627664d2 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -130,8 +130,10 @@ STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, i_keyraw rkey) #if !defined _i_no_clone
STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) {
- if (self->table == other.table) return;
- _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other);
+ if (self->table == other.table)
+ return;
+ _cx_memb(_drop)(self);
+ *self = _cx_memb(_clone)(other);
}
STC_INLINE _cx_value
@@ -169,15 +171,20 @@ _cx_memb(_value_drop)(_cx_value* _val) { STC_INLINE _cx_result
_cx_memb(_insert)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) {
_cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto((&_key)));
- if (_res.inserted) { *_i_keyref(_res.ref) = _key; _i_MAP_ONLY( _res.ref->second = _mapped; )}
- else { i_keydrop((&_key)); _i_MAP_ONLY( i_valdrop((&_mapped)); )}
+ if (_res.inserted)
+ { *_i_keyref(_res.ref) = _key; _i_MAP_ONLY( _res.ref->second = _mapped; )}
+ else
+ { i_keydrop((&_key)); _i_MAP_ONLY( i_valdrop((&_mapped)); )}
return _res;
}
STC_INLINE _cx_result
_cx_memb(_push)(_cx_self* self, _cx_value _val) {
_cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val)));
- if (_res.inserted) *_res.ref = _val; else _cx_memb(_value_drop)(&_val);
+ if (_res.inserted)
+ *_res.ref = _val;
+ else
+ _cx_memb(_value_drop)(&_val);
return _res;
}
@@ -192,18 +199,21 @@ _cx_memb(_find)(const _cx_self* self, i_keyraw rkey) { STC_INLINE const _cx_value*
_cx_memb(_get)(const _cx_self* self, i_keyraw rkey) {
i_size idx;
- return self->size && self->_hashx[idx = _cx_memb(_bucket_)(self, &rkey).idx] ?
- self->table + idx : NULL;
+ if (self->size && self->_hashx[idx = _cx_memb(_bucket_)(self, &rkey).idx])
+ return self->table + idx;
+ return NULL;
}
STC_INLINE _cx_value*
_cx_memb(_get_mut)(const _cx_self* self, i_keyraw rkey)
- { return (_cx_value*) _cx_memb(_get)(self, rkey); }
+ { return (_cx_value*)_cx_memb(_get)(self, rkey); }
STC_INLINE _cx_iter
_cx_memb(_begin)(const _cx_self* self) {
_cx_iter it = {self->table, self->_hashx};
- if (it._hx) while (*it._hx == 0) ++it.ref, ++it._hx;
+ if (it._hx)
+ while (*it._hx == 0)
+ ++it.ref, ++it._hx;
return it;
}
@@ -224,7 +234,8 @@ _cx_memb(_advance)(_cx_iter it, size_t n) { STC_INLINE size_t
_cx_memb(_erase)(_cx_self* self, i_keyraw rkey) {
- if (self->size == 0) return 0;
+ if (self->size == 0)
+ return 0;
chash_bucket_t b = _cx_memb(_bucket_)(self, &rkey);
return self->_hashx[b.idx] ? _cx_memb(_erase_entry)(self, self->table + b.idx), 1 : 0;
}
@@ -232,7 +243,8 @@ _cx_memb(_erase)(_cx_self* self, i_keyraw rkey) { STC_INLINE _cx_iter
_cx_memb(_erase_at)(_cx_self* self, _cx_iter it) {
_cx_memb(_erase_entry)(self, it.ref);
- if (*it._hx == 0) _cx_memb(_next)(&it);
+ if (*it._hx == 0)
+ _cx_memb(_next)(&it);
return it;
}
@@ -254,10 +266,13 @@ _cx_memb(_with_capacity)(const size_t cap) { }
STC_INLINE void _cx_memb(_wipe_)(_cx_self* self) {
- if (self->size == 0) return;
+ if (self->size == 0)
+ return;
_cx_value* e = self->table, *end = e + self->bucket_count;
uint8_t *hx = self->_hashx;
- for (; e != end; ++e) if (*hx++) _cx_memb(_value_drop)(e);
+ for (; e != end; ++e)
+ if (*hx++)
+ _cx_memb(_value_drop)(e);
}
STC_DEF void _cx_memb(_drop)(_cx_self* self) {
@@ -276,18 +291,24 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { STC_DEF _cx_result
_cx_memb(_insert_or_assign)(_cx_self* self, i_key _key, i_val _mapped) {
_cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto((&_key)));
- if (_res.inserted) _res.ref->first = _key;
- else { i_keydrop((&_key)); i_valdrop((&_res.ref->second)); }
- _res.ref->second = _mapped; return _res;
+ if (_res.inserted)
+ _res.ref->first = _key;
+ else
+ { i_keydrop((&_key)); i_valdrop((&_res.ref->second)); }
+ _res.ref->second = _mapped;
+ return _res;
}
#if !defined _i_no_clone && !defined _i_no_emplace
STC_DEF _cx_result
_cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped) {
_cx_result _res = _cx_memb(_insert_entry_)(self, rkey);
- if (_res.inserted) _res.ref->first = i_keyfrom(rkey);
- else { i_valdrop((&_res.ref->second)); }
- _res.ref->second = i_valfrom(rmapped); return _res;
+ if (_res.inserted)
+ _res.ref->first = i_keyfrom(rkey);
+ else
+ { i_valdrop((&_res.ref->second)); }
+ _res.ref->second = i_valfrom(rmapped);
+ return _res;
}
#endif // !_i_no_clone && !_i_no_emplace
#endif // !_i_isset
@@ -301,7 +322,8 @@ _cx_memb(_bucket_)(const _cx_self* self, const _cx_rawkey* rkeyptr) { while ((_hx = _hashx[b.idx])) {
if (_hx == b.hx) {
_cx_rawkey _raw = i_keyto(_i_keyref(self->table + b.idx));
- if (i_eq((&_raw), rkeyptr)) break;
+ if (i_eq((&_raw), rkeyptr))
+ break;
}
if (++b.idx == _cap)
b.idx = 0;
@@ -332,7 +354,8 @@ _cx_memb(_clone)(_cx_self m) { { c_free(t), c_free(h), t = 0, h = 0, m.bucket_count = 0; }
else
for (; m.table != m_end; ++m.table, ++m._hashx, ++dst)
- if (*m._hashx) *dst = _cx_memb(_value_clone)(*m.table);
+ if (*m._hashx)
+ *dst = _cx_memb(_value_clone)(*m.table);
m.table = t, m._hashx = h;
return m;
}
@@ -342,7 +365,8 @@ STC_DEF bool _cx_memb(_reserve)(_cx_self* self, const size_t _newcap) {
const i_size _oldbuckets = self->bucket_count;
const i_size _nbuckets = ((i_size)(_newcap/self->max_load_factor) + 2) | 1;
- if (_newcap != self->size && _newcap <= _oldbuckets) return true;
+ if (_newcap != self->size && _newcap <= _oldbuckets)
+ return true;
_cx_self m = {
c_alloc_n(_cx_value, _nbuckets),
(uint8_t *) c_calloc(_nbuckets + 1, 1),
diff --git a/include/stc/csmap.h b/include/stc/csmap.h index c7bf8e47..405ca5bb 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -48,6 +48,9 @@ int main(void) { }
}
*/
+#ifdef STC_CSMAP_V1
+#include "alt/csmap.h"
+#else
#include "ccommon.h"
#ifndef CSMAP_H_INCLUDED
@@ -114,11 +117,12 @@ STC_API _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it); STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2);
STC_API void _cx_memb(_next)(_cx_iter* it);
-STC_INLINE bool _cx_memb(_empty)(_cx_self tree) { return _csmap_rep(&tree)->size == 0; }
-STC_INLINE size_t _cx_memb(_size)(_cx_self tree) { return _csmap_rep(&tree)->size; }
-STC_INLINE size_t _cx_memb(_capacity)(_cx_self tree) { return _csmap_rep(&tree)->cap; }
-
+STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return _csmap_rep(&cx)->size == 0; }
+STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return _csmap_rep(&cx)->size; }
+STC_INLINE size_t _cx_memb(_capacity)(_cx_self cx) { return _csmap_rep(&cx)->cap; }
STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); }
+STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey)
+ { _cx_iter it; _cx_memb(_find_it)(self, rkey, &it); return it; }
STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, i_keyraw rkey)
{ _cx_iter it; return _cx_memb(_find_it)(self, rkey, &it) != NULL; }
STC_INLINE const _cx_value* _cx_memb(_get)(const _cx_self* self, i_keyraw rkey)
@@ -140,7 +144,8 @@ _cx_memb(_clear)(_cx_self* self) STC_INLINE _cx_raw
_cx_memb(_value_toraw)(_cx_value* val) {
return _i_SET_ONLY( i_keyto(val) )
- _i_MAP_ONLY( c_make(_cx_raw){i_keyto((&val->first)), i_valto((&val->second))} );
+ _i_MAP_ONLY( c_make(_cx_raw){i_keyto((&val->first)),
+ i_valto((&val->second))} );
}
STC_INLINE int
@@ -165,7 +170,8 @@ _cx_memb(_value_clone)(_cx_value _val) { STC_INLINE void
_cx_memb(_copy)(_cx_self *self, _cx_self other) {
- if (self->nodes == other.nodes) return;
+ if (self->nodes == other.nodes)
+ return;
_cx_memb(_drop)(self);
*self = _cx_memb(_clone)(other);
}
@@ -192,29 +198,26 @@ _cx_memb(_shrink_to_fit)(_cx_self *self) { #endif // !_i_isset
STC_INLINE _cx_iter
-_cx_memb(_find)(const _cx_self* self, i_keyraw rkey) {
- _cx_iter it;
- _cx_memb(_find_it)(self, rkey, &it);
- return it;
-}
-
-STC_INLINE _cx_iter
_cx_memb(_begin)(const _cx_self* self) {
- _cx_iter it; it._d = self->nodes, it._top = 0;
+ _cx_iter it;
+ it._d = self->nodes, it._top = 0;
it._tn = (i_size) _csmap_rep(self)->root;
- if (it._tn) _cx_memb(_next)(&it);
+ if (it._tn)
+ _cx_memb(_next)(&it);
return it;
}
STC_INLINE _cx_iter
_cx_memb(_end)(const _cx_self* self) {
(void)self;
- return c_make(_cx_iter){.ref = NULL};
+ _cx_iter it; it.ref = NULL, it._top = 0, it._tn = 0;
+ return it;
}
STC_INLINE _cx_iter
_cx_memb(_advance)(_cx_iter it, size_t n) {
- while (n-- && it.ref) _cx_memb(_next)(&it);
+ while (n-- && it.ref)
+ _cx_memb(_next)(&it);
return it;
}
@@ -231,22 +234,6 @@ _cx_memb(_init)(void) { return tree;
}
-STC_DEF _cx_value*
-_cx_memb(_front)(const _cx_self* self) {
- _cx_node *d = self->nodes;
- i_size tn = (i_size) _csmap_rep(self)->root;
- while (d[tn].link[0]) tn = d[tn].link[0];
- return &d[tn].value;
-}
-
-STC_DEF _cx_value*
-_cx_memb(_back)(const _cx_self* self) {
- _cx_node *d = self->nodes;
- i_size tn = (i_size) _csmap_rep(self)->root;
- while (d[tn].link[1]) tn = d[tn].link[1];
- return &d[tn].value;
-}
-
STC_DEF bool
_cx_memb(_reserve)(_cx_self* self, const size_t cap) {
struct csmap_rep* rep = _csmap_rep(self), *oldrep;
@@ -255,7 +242,8 @@ _cx_memb(_reserve)(_cx_self* self, const size_t cap) { oldrep = rep->cap && rep != &_csmap_sentinel ? rep : NULL;
rep = (struct csmap_rep*) c_realloc(oldrep, offsetof(struct csmap_rep, nodes) +
(cap + 1)*sizeof(_cx_node));
- if (!rep) return false;
+ if (!rep)
+ return false;
if (oldrep == NULL)
memset(rep, 0, offsetof(struct csmap_rep, nodes) + sizeof(_cx_node));
rep->cap = cap;
@@ -264,6 +252,24 @@ _cx_memb(_reserve)(_cx_self* self, const size_t cap) { return true;
}
+STC_DEF _cx_value*
+_cx_memb(_front)(const _cx_self* self) {
+ _cx_node *d = self->nodes;
+ i_size tn = (i_size) _csmap_rep(self)->root;
+ while (d[tn].link[0])
+ tn = d[tn].link[0];
+ return &d[tn].value;
+}
+
+STC_DEF _cx_value*
+_cx_memb(_back)(const _cx_self* self) {
+ _cx_node *d = self->nodes;
+ i_size tn = (i_size) _csmap_rep(self)->root;
+ while (d[tn].link[1])
+ tn = d[tn].link[1];
+ return &d[tn].value;
+}
+
static i_size
_cx_memb(_new_node_)(_cx_self* self, int level) {
i_size tn; struct csmap_rep *rep = _csmap_rep(self);
@@ -286,16 +292,20 @@ static _cx_result _cx_memb(_insert_entry_)(_cx_self* self, i_keyraw rkey); STC_DEF _cx_result
_cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)) {
_cx_result res = _cx_memb(_insert_entry_)(self, i_keyto((&key)));
- if (res.inserted) { *_i_keyref(res.ref) = key; _i_MAP_ONLY( res.ref->second = mapped; )}
- else { i_keydrop((&key)); _i_MAP_ONLY( i_valdrop((&mapped)); )}
+ if (res.inserted)
+ { *_i_keyref(res.ref) = key; _i_MAP_ONLY( res.ref->second = mapped; )}
+ else
+ { i_keydrop((&key)); _i_MAP_ONLY( i_valdrop((&mapped)); )}
return res;
}
STC_DEF _cx_result
_cx_memb(_push)(_cx_self* self, _cx_value _val) {
_cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val)));
- if (_res.inserted) *_res.ref = _val;
- else _cx_memb(_value_drop)(&_val);
+ if (_res.inserted)
+ *_res.ref = _val;
+ else
+ _cx_memb(_value_drop)(&_val);
return _res;
}
@@ -304,8 +314,10 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped) {
_cx_result res = _cx_memb(_insert_entry_)(self, i_keyto((&key)));
if (!res.nomem_error) {
- if (res.inserted) res.ref->first = key;
- else { i_keydrop((&key)); i_valdrop((&res.ref->second)); }
+ if (res.inserted)
+ res.ref->first = key;
+ else
+ { i_keydrop((&key)); i_valdrop((&res.ref->second)); }
res.ref->second = mapped;
}
return res;
@@ -316,8 +328,10 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { _cx_memb(_emplace_or_assign)(_cx_self* self, i_keyraw rkey, i_valraw rmapped) {
_cx_result res = _cx_memb(_insert_entry_)(self, rkey);
if (!res.nomem_error) {
- if (res.inserted) res.ref->first = i_keyfrom(rkey);
- else { i_valdrop((&res.ref->second)); }
+ if (res.inserted)
+ res.ref->first = i_keyfrom(rkey);
+ else
+ { i_valdrop((&res.ref->second)); }
res.ref->second = i_valfrom(rmapped);
}
return res;
@@ -409,13 +423,16 @@ _cx_memb(_insert_entry_i_)(_cx_self* self, i_size tn, const _cx_rawkey* rkey, _c { res->nomem_error = true; return 0; }
d = self->nodes;
res->ref = &d[tx].value, res->inserted = true;
- if (top == 0) return tx;
+ if (top == 0)
+ return tx;
d[up[top - 1]].link[dir] = tx;
while (top--) {
- if (top) dir = (d[up[top - 1]].link[1] == up[top]);
+ if (top)
+ dir = (d[up[top - 1]].link[1] == up[top]);
up[top] = _cx_memb(_skew_)(d, up[top]);
up[top] = _cx_memb(_split_)(d, up[top]);
- if (top) d[up[top - 1]].link[dir] = up[top];
+ if (top)
+ d[up[top - 1]].link[dir] = up[top];
}
return up[0];
}
@@ -473,27 +490,38 @@ STC_DEF int _cx_memb(_erase)(_cx_self* self, i_keyraw rkey) {
int erased = 0;
i_size root = _cx_memb(_erase_r_)(self->nodes, (i_size) _csmap_rep(self)->root, &rkey, &erased);
- return erased ? (_csmap_rep(self)->root = root, --_csmap_rep(self)->size, 1) : 0;
+ if (erased) {
+ _csmap_rep(self)->root = root;
+ --_csmap_rep(self)->size;
+ return 1;
+ }
+ return 0;
}
STC_DEF _cx_iter
_cx_memb(_erase_at)(_cx_self* self, _cx_iter it) {
_cx_rawkey raw = i_keyto(_i_keyref(it.ref)), nxt;
_cx_memb(_next)(&it);
- if (it.ref) nxt = i_keyto(_i_keyref(it.ref));
+ if (it.ref)
+ nxt = i_keyto(_i_keyref(it.ref));
_cx_memb(_erase)(self, raw);
- if (it.ref) _cx_memb(_find_it)(self, nxt, &it);
+ if (it.ref)
+ _cx_memb(_find_it)(self, nxt, &it);
return it;
}
STC_DEF _cx_iter
_cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) {
- if (!it2.ref) { while (it1.ref) it1 = _cx_memb(_erase_at)(self, it1);
- return it1; }
+ if (!it2.ref) {
+ while (it1.ref)
+ it1 = _cx_memb(_erase_at)(self, it1);
+ return it1;
+ }
_cx_key k1 = *_i_keyref(it1.ref), k2 = *_i_keyref(it2.ref);
_cx_rawkey r1 = i_keyto((&k1));
for (;;) {
- if (memcmp(&k1, &k2, sizeof k1) == 0) return it1;
+ if (memcmp(&k1, &k2, sizeof k1) == 0)
+ return it1;
_cx_memb(_next)(&it1); k1 = *_i_keyref(it1.ref);
_cx_memb(_erase)(self, r1);
_cx_memb(_find_it)(self, (r1 = i_keyto((&k1))), &it1);
@@ -503,7 +531,8 @@ _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) { #if !defined _i_no_clone
static i_size
_cx_memb(_clone_r_)(_cx_self* self, _cx_node* src, i_size sn) {
- if (sn == 0) return 0;
+ if (sn == 0)
+ return 0;
i_size tx, tn = _cx_memb(_new_node_)(self, src[sn].level);
self->nodes[tn].value = _cx_memb(_value_clone)(src[sn].value);
tx = _cx_memb(_clone_r_)(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx;
@@ -560,3 +589,4 @@ _cx_memb(_drop)(_cx_self* self) { #undef _i_SET_ONLY
#define CSMAP_H_INCLUDED
#include "template.h"
+#endif // !STC_CSMAP_V1
diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 85c5061f..dadb6ee5 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -24,7 +24,7 @@ /* A string type with short string optimization in C99 with optimal short string
* utilization (23 characters with 24 bytes string representation).
*/
-#ifdef STC_OLD_CSTR
+#ifdef STC_CSTR_V1
#include "alt/cstr.h"
#else
#ifndef CSTR_H_INCLUDED
@@ -478,5 +478,5 @@ STC_DEF int cstr_printf(cstr* self, const char* fmt, ...) { # pragma GCC diagnostic pop
#endif
#endif // CSTR_H_INCLUDED
-#endif
#undef i_opt
+#endif // !STC_CSTR_V1
diff --git a/include/stc/forward.h b/include/stc/forward.h index 9952416a..635c63df 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -44,13 +44,13 @@ typedef struct { char* data; size_t size, cap; } cstr_buf;
typedef char cstr_value;
-#ifndef STC_OLD_CSTR
+#if defined STC_CSTR_V1
+ typedef struct cstr { char* str; } cstr;
+#else
typedef union {
struct { char data[sizeof(cstr_buf) - 1]; unsigned char last; } sml;
struct { char* data; size_t size, ncap; } lon;
} cstr;
-#else
- typedef struct cstr { char* str; } cstr;
#endif
typedef struct csview { const char* str; size_t size; } csview;
@@ -128,6 +128,33 @@ typedef char csview_value; float max_load_factor; \
} SELF
+#if defined STC_CSMAP_V1
+#define _c_aatree_types(SELF, KEY, VAL, SZ, MAP_ONLY, SET_ONLY) \
+ typedef KEY SELF##_key; \
+ typedef VAL SELF##_mapped; \
+ typedef SZ SELF##_size_t; \
+ typedef struct SELF##_node SELF##_node; \
+\
+ typedef SET_ONLY( SELF##_key ) \
+ MAP_ONLY( struct SELF##_value ) \
+ SELF##_value; \
+\
+ typedef struct { \
+ SELF##_value *ref; \
+ bool inserted, nomem_error; \
+ } SELF##_result; \
+\
+ typedef struct { \
+ SELF##_value *ref; \
+ int _top; \
+ SELF##_node *_tn, *_st[36]; \
+ } SELF##_iter; \
+\
+ typedef struct { \
+ SELF##_node *root; \
+ SELF##_size_t size; \
+ } SELF
+#else
#define _c_aatree_types(SELF, KEY, VAL, SZ, MAP_ONLY, SET_ONLY) \
typedef KEY SELF##_key; \
typedef VAL SELF##_mapped; \
@@ -153,7 +180,7 @@ typedef char csview_value; typedef struct { \
SELF##_node *nodes; \
} SELF
-
+#endif
#define _c_cstack_types(SELF, VAL) \
typedef VAL SELF##_value; \
typedef struct { SELF##_value *ref; } SELF##_iter; \
|