summaryrefslogtreecommitdiffhomepage
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/stc/alt/csmap.h822
-rw-r--r--include/stc/alt/cstr.h4
-rw-r--r--include/stc/cmap.h68
-rw-r--r--include/stc/csmap.h134
-rw-r--r--include/stc/cstr.h4
-rw-r--r--include/stc/forward.h35
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; \
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-01 11:23:24 +0000