diff options
Diffstat (limited to 'stc/csmap.h')
| -rw-r--r-- | stc/csmap.h | 415 |
1 files changed, 206 insertions, 209 deletions
diff --git a/stc/csmap.h b/stc/csmap.h index dd864714..c425515c 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -62,15 +62,15 @@ int main(void) { #define using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \
using_csmap_12(X, Key, Mapped, keyCompare, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- c_trivial_del, c_trivial_fromraw, c_trivial_toraw, Key)
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ c_trivial_del, c_trivial_fromraw, c_trivial_toraw, Key)
#define using_csmap_12(X, Key, Mapped, keyCompareRaw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey) \
- _using_AATREE(X, csmap_, Key, Mapped, keyCompareRaw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey)
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey) \
+ _c_using_aatree(csmap_##X, csmap_, Key, Mapped, keyCompareRaw, \
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey)
#define using_csmap_keydef(...) c_MACRO_OVERLOAD(using_csmap_keydef, __VA_ARGS__)
#define using_csmap_keydef_6(X, Key, Mapped, keyCompare, keyDel, keyClone) \
@@ -78,15 +78,15 @@ int main(void) { keyDel, keyClone, c_trivial_toraw, Key)
#define using_csmap_keydef_8(X, Key, Mapped, keyCompareRaw, \
keyDel, keyFromRaw, keyToRaw, RawKey) \
- _using_AATREE(X, csmap_, Key, Mapped, keyCompareRaw, \
- c_trivial_del, c_trivial_fromraw, c_trivial_toraw, Mapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey)
+ _c_using_aatree(csmap_##X, csmap_, Key, Mapped, keyCompareRaw, \
+ c_trivial_del, c_trivial_fromraw, c_trivial_toraw, Mapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey)
/* csmap_str, csmap_strkey, csmap_strval: */
#define using_csmap_str() \
- _using_AATREE(str, csmap_, cstr_t, cstr_t, cstr_compare_raw, \
- cstr_del, cstr_from, cstr_c_str, const char*, \
- cstr_del, cstr_from, cstr_c_str, const char*)
+ _c_using_aatree(csmap_str, csmap_, cstr_t, cstr_t, cstr_compare_raw, \
+ cstr_del, cstr_from, cstr_c_str, const char*, \
+ cstr_del, cstr_from, cstr_c_str, const char*)
#define using_csmap_strkey(...) \
c_MACRO_OVERLOAD(using_csmap_strkey, __VA_ARGS__)
@@ -96,14 +96,14 @@ int main(void) { #define using_csmap_strkey_3(X, Mapped, mappedDel) \
using_csmap_strkey_4(X, Mapped, mappedDel, c_no_clone)
#define using_csmap_strkey_4(X, Mapped, mappedDel, mappedClone) \
- _using_AATREE_strkey(X, csmap_, Mapped, mappedDel, mappedClone, c_trivial_toraw, Mapped)
+ _c_using_aatree_strkey(X, csmap_, Mapped, mappedDel, mappedClone, c_trivial_toraw, Mapped)
#define using_csmap_strkey_6(X, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \
- _using_AATREE_strkey(X, csmap_, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped)
+ _c_using_aatree_strkey(X, csmap_, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped)
-#define _using_AATREE_strkey(X, C, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \
- _using_AATREE(X, C, cstr_t, Mapped, cstr_compare_raw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- cstr_del, cstr_from, cstr_c_str, const char*)
+#define _c_using_aatree_strkey(X, C, Mapped, mappedDel, mappedFromRaw, mappedToRaw, RawMapped) \
+ _c_using_aatree(C##X, C, cstr_t, Mapped, cstr_compare_raw, \
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ cstr_del, cstr_from, cstr_c_str, const char*)
#define using_csmap_strval(...) \
c_MACRO_OVERLOAD(using_csmap_strval, __VA_ARGS__)
@@ -118,9 +118,9 @@ int main(void) { using_csmap_strval_7(X, Key, keyCompare, keyDel, keyClone, c_trivial_toraw, Key)
#define using_csmap_strval_7(X, Key, keyCompareRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \
- _using_AATREE(X, csmap_, Key, cstr_t, keyCompareRaw, \
- cstr_del, cstr_from, cstr_c_str, const char*, \
- keyDel, keyFromRaw, keyToRaw, RawKey)
+ _c_using_aatree(csmap_##X, csmap_, Key, cstr_t, keyCompareRaw, \
+ cstr_del, cstr_from, cstr_c_str, const char*, \
+ keyDel, keyFromRaw, keyToRaw, RawKey)
#define SET_ONLY_csmap_(...)
#define MAP_ONLY_csmap_(...) __VA_ARGS__
@@ -132,108 +132,108 @@ int main(void) { struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };
#define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes)
-#define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey) \
- typedef Key C##X##_key_t; \
- typedef Mapped C##X##_mapped_t; \
- typedef RawKey C##X##_rawkey_t; \
- typedef RawMapped C##X##_rawmapped_t; \
- typedef CSMAP_SIZE_T C##X##_size_t; \
-\
- typedef SET_ONLY_##C( C##X##_key_t ) \
- MAP_ONLY_##C( struct {C##X##_key_t first; \
- C##X##_mapped_t second;} ) \
- C##X##_value_t; \
+#define _c_using_aatree(CX, C, Key, Mapped, keyCompareRaw, \
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey) \
+ typedef Key CX##_key_t; \
+ typedef Mapped CX##_mapped_t; \
+ typedef RawKey CX##_rawkey_t; \
+ typedef RawMapped CX##_rawmapped_t; \
+ typedef CSMAP_SIZE_T CX##_size_t; \
+\
+ typedef SET_ONLY_##C( CX##_key_t ) \
+ MAP_ONLY_##C( struct {CX##_key_t first; \
+ CX##_mapped_t second;} ) \
+ CX##_value_t; \
\
typedef SET_ONLY_##C( RawKey ) \
MAP_ONLY_##C( struct {RawKey first; \
RawMapped second;} ) \
- C##X##_rawvalue_t; \
+ CX##_rawvalue_t; \
\
typedef struct { \
- C##X##_value_t *ref; \
+ CX##_value_t *ref; \
bool inserted; \
- } C##X##_result_t; \
+ } CX##_result_t; \
\
- typedef struct C##X##_node { \
- C##X##_size_t link[2]; \
+ typedef struct CX##_node { \
+ CX##_size_t link[2]; \
int8_t level; \
- C##X##_value_t value; \
- } C##X##_node_t; \
+ CX##_value_t value; \
+ } CX##_node_t; \
\
typedef struct { \
- C##X##_node_t* nodes; \
- } C##X; \
+ CX##_node_t* nodes; \
+ } CX; \
\
typedef struct { \
- C##X##_value_t *ref; \
- C##X##_node_t *_d; \
+ CX##_value_t *ref; \
+ CX##_node_t *_d; \
int _top; \
- C##X##_size_t _tn, _st[48]; \
- } C##X##_iter_t; \
+ CX##_size_t _tn, _st[48]; \
+ } CX##_iter_t; \
\
- STC_API C##X C##X##_init(void); \
- STC_API C##X C##X##_clone(C##X tree); \
+ STC_API CX CX##_init(void); \
+ STC_API CX CX##_clone(CX tree); \
\
STC_API void \
- C##X##_reserve(C##X* self, size_t cap); \
- STC_INLINE C##X \
- C##X##_with_capacity(size_t size) { \
- C##X x = C##X##_init(); \
- C##X##_reserve(&x, size); \
+ CX##_reserve(CX* self, size_t cap); \
+ STC_INLINE CX \
+ CX##_with_capacity(size_t size) { \
+ CX x = CX##_init(); \
+ CX##_reserve(&x, size); \
return x; \
} \
STC_INLINE bool \
- C##X##_empty(C##X tree) {return _csmap_rep(&tree)->size == 0;} \
+ CX##_empty(CX tree) {return _csmap_rep(&tree)->size == 0;} \
STC_INLINE size_t \
- C##X##_size(C##X tree) {return _csmap_rep(&tree)->size;} \
+ CX##_size(CX tree) {return _csmap_rep(&tree)->size;} \
STC_INLINE size_t \
- C##X##_capacity(C##X tree) {return _csmap_rep(&tree)->cap;} \
+ CX##_capacity(CX tree) {return _csmap_rep(&tree)->cap;} \
STC_API void \
- C##X##_del(C##X* self); \
+ CX##_del(CX* self); \
STC_INLINE void \
- C##X##_clear(C##X* self) {C##X##_del(self); *self = C##X##_init();} \
+ CX##_clear(CX* self) {CX##_del(self); *self = CX##_init();} \
STC_INLINE void \
- C##X##_swap(C##X* a, C##X* b) {c_swap(C##X, *a, *b);} \
+ CX##_swap(CX* a, CX* b) {c_swap(CX, *a, *b);} \
\
STC_INLINE void \
- C##X##_value_del(C##X##_value_t* val) { \
+ CX##_value_del(CX##_value_t* val) { \
keyDel(KEY_REF_##C(val)); \
MAP_ONLY_##C( mappedDel(&val->second); ) \
} \
- STC_INLINE C##X##_value_t \
- C##X##_value_clone(C##X##_value_t val) { \
+ STC_INLINE CX##_value_t \
+ CX##_value_clone(CX##_value_t val) { \
*KEY_REF_##C(&val) = keyFromRaw(keyToRaw(KEY_REF_##C(&val))); \
MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \
return val; \
} \
\
- STC_API C##X##_value_t* \
- C##X##_find_it(const C##X* self, RawKey rkey, C##X##_iter_t* out); \
+ STC_API CX##_value_t* \
+ CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out); \
\
- STC_API C##X##_iter_t \
- C##X##_lower_bound(const C##X* self, RawKey rkey); \
+ STC_API CX##_iter_t \
+ CX##_lower_bound(const CX* self, RawKey rkey); \
\
- STC_INLINE C##X##_iter_t \
- C##X##_find(const C##X* self, RawKey rkey) { \
- C##X##_iter_t it; \
- C##X##_find_it(self, rkey, &it); \
+ STC_INLINE CX##_iter_t \
+ CX##_find(const CX* self, RawKey rkey) { \
+ CX##_iter_t it; \
+ CX##_find_it(self, rkey, &it); \
return it; \
} \
\
STC_INLINE bool \
- C##X##_contains(const C##X* self, RawKey rkey) { \
- C##X##_iter_t it; \
- return C##X##_find_it(self, rkey, &it) != NULL; \
+ CX##_contains(const CX* self, RawKey rkey) { \
+ CX##_iter_t it; \
+ return CX##_find_it(self, rkey, &it) != NULL; \
} \
\
- STC_API C##X##_result_t \
- C##X##_insert_entry_(C##X* self, RawKey rkey); \
+ STC_API CX##_result_t \
+ CX##_insert_entry_(CX* self, RawKey rkey); \
\
- STC_INLINE C##X##_result_t \
- C##X##_emplace(C##X* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \
- C##X##_result_t res = C##X##_insert_entry_(self, rkey); \
+ STC_INLINE CX##_result_t \
+ CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \
+ CX##_result_t res = CX##_insert_entry_(self, rkey); \
if (res.inserted) { \
*KEY_REF_##C(res.ref) = keyFromRaw(rkey); \
MAP_ONLY_##C(res.ref->second = mappedFromRaw(rmapped);) \
@@ -241,134 +241,131 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; return res; \
} \
STC_INLINE void \
- C##X##_emplace_n(C##X* self, const C##X##_rawvalue_t arr[], size_t n) { \
- for (size_t i=0; i<n; ++i) SET_ONLY_##C( C##X##_emplace(self, arr[i]); ) \
- MAP_ONLY_##C( C##X##_emplace(self, arr[i].first, arr[i].second); ) \
+ CX##_emplace_n(CX* self, const CX##_rawvalue_t arr[], size_t n) { \
+ for (size_t i=0; i<n; ++i) SET_ONLY_##C( CX##_emplace(self, arr[i]); ) \
+ MAP_ONLY_##C( CX##_emplace(self, arr[i].first, arr[i].second); ) \
} \
\
- STC_INLINE C##X##_result_t \
- C##X##_insert(C##X* self, Key key MAP_ONLY_##C(, Mapped mapped)) { \
- C##X##_result_t res = C##X##_insert_entry_(self, keyToRaw(&key)); \
+ STC_INLINE CX##_result_t \
+ CX##_insert(CX* self, Key key MAP_ONLY_##C(, Mapped mapped)) { \
+ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \
if (res.inserted) {*KEY_REF_##C(res.ref) = key; MAP_ONLY_##C( res.ref->second = mapped; )} \
else {keyDel(&key); MAP_ONLY_##C( mappedDel(&mapped); )} \
return res; \
} \
\
MAP_ONLY_##C( \
- STC_INLINE C##X##_result_t \
- C##X##_insert_or_assign(C##X* self, Key key, Mapped mapped) { \
- C##X##_result_t res = C##X##_insert_entry_(self, keyToRaw(&key)); \
+ STC_INLINE CX##_result_t \
+ CX##_insert_or_assign(CX* self, Key key, Mapped mapped) { \
+ CX##_result_t res = CX##_insert_entry_(self, keyToRaw(&key)); \
if (res.inserted) res.ref->first = key; \
else {keyDel(&key); mappedDel(&res.ref->second);} \
res.ref->second = mapped; return res; \
} \
- STC_INLINE C##X##_result_t \
- C##X##_put(C##X* self, Key k, Mapped m) { \
- return C##X##_insert_or_assign(self, k, m); \
+ STC_INLINE CX##_result_t \
+ CX##_put(CX* self, Key k, Mapped m) { \
+ return CX##_insert_or_assign(self, k, m); \
} \
- STC_INLINE C##X##_result_t \
- C##X##_emplace_or_assign(C##X* self, RawKey rkey, RawMapped rmapped) { \
- C##X##_result_t res = C##X##_insert_entry_(self, rkey); \
+ STC_INLINE CX##_result_t \
+ CX##_emplace_or_assign(CX* self, RawKey rkey, RawMapped rmapped) { \
+ CX##_result_t res = CX##_insert_entry_(self, rkey); \
if (res.inserted) res.ref->first = keyFromRaw(rkey); \
else mappedDel(&res.ref->second); \
res.ref->second = mappedFromRaw(rmapped); return res; \
} \
- STC_INLINE C##X##_mapped_t* \
- C##X##_at(const C##X* self, RawKey rkey) { \
- C##X##_iter_t it; \
- return &C##X##_find_it(self, rkey, &it)->second; \
+ STC_INLINE CX##_mapped_t* \
+ CX##_at(const CX* self, RawKey rkey) { \
+ CX##_iter_t it; \
+ return &CX##_find_it(self, rkey, &it)->second; \
}) \
\
- STC_API C##X##_value_t* C##X##_front(const C##X* self); \
- STC_API C##X##_value_t* C##X##_back(const C##X* self); \
- STC_API void C##X##_next(C##X##_iter_t* it); \
+ STC_API CX##_value_t* CX##_front(const CX* self); \
+ STC_API CX##_value_t* CX##_back(const CX* self); \
+ STC_API void CX##_next(CX##_iter_t* it); \
\
- STC_INLINE C##X##_iter_t \
- C##X##_begin(const C##X* self) { \
- C##X##_iter_t it = {NULL, self->nodes, 0, (C##X##_size_t) _csmap_rep(self)->root}; \
- if (it._tn) C##X##_next(&it); \
+ STC_INLINE CX##_iter_t \
+ CX##_begin(const CX* self) { \
+ CX##_iter_t it = {NULL, self->nodes, 0, (CX##_size_t) _csmap_rep(self)->root}; \
+ if (it._tn) CX##_next(&it); \
return it; \
} \
- STC_INLINE C##X##_iter_t \
- C##X##_end(const C##X* self) {\
- C##X##_iter_t it = {NULL}; return it; \
+ STC_INLINE CX##_iter_t \
+ CX##_end(const CX* self) {\
+ CX##_iter_t it = {NULL}; return it; \
} \
- STC_INLINE C##X##_mapped_t* \
- C##X##_itval(C##X##_iter_t it) {return SET_ONLY_##C( it.ref ) \
- MAP_ONLY_##C( &it.ref->second );} \
STC_API int \
- C##X##_erase(C##X* self, RawKey rkey); \
+ CX##_erase(CX* self, RawKey rkey); \
\
- STC_API C##X##_iter_t \
- C##X##_erase_at(C##X* self, C##X##_iter_t pos); \
+ STC_API CX##_iter_t \
+ CX##_erase_at(CX* self, CX##_iter_t pos); \
\
- _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey) \
- typedef C##X C##X##_t
+ _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey) \
+ typedef CX CX##_t
/* -------------------------- IMPLEMENTATION ------------------------- */
#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
static struct csmap_rep _smap_inits = {0, 0, 0, 0};
-#define _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey) \
- STC_DEF C##X \
- C##X##_init(void) { \
- C##X tree = {(C##X##_node_t *) _smap_inits.nodes}; \
+#define _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey) \
+ STC_DEF CX \
+ CX##_init(void) { \
+ CX tree = {(CX##_node_t *) _smap_inits.nodes}; \
return tree; \
} \
\
- STC_DEF C##X##_value_t* \
- C##X##_front(const C##X* self) { \
- C##X##_node_t *d = self->nodes; \
- C##X##_size_t tn = (C##X##_size_t) _csmap_rep(self)->root; \
+ STC_DEF CX##_value_t* \
+ CX##_front(const CX* self) { \
+ CX##_node_t *d = self->nodes; \
+ CX##_size_t tn = (CX##_size_t) _csmap_rep(self)->root; \
while (d[tn].link[0]) tn = d[tn].link[0]; \
return &d[tn].value; \
} \
- STC_DEF C##X##_value_t* \
- C##X##_back(const C##X* self) { \
- C##X##_node_t *d = self->nodes; \
- C##X##_size_t tn = (C##X##_size_t) _csmap_rep(self)->root; \
+ STC_DEF CX##_value_t* \
+ CX##_back(const CX* self) { \
+ CX##_node_t *d = self->nodes; \
+ CX##_size_t tn = (CX##_size_t) _csmap_rep(self)->root; \
while (d[tn].link[1]) tn = d[tn].link[1]; \
return &d[tn].value; \
} \
\
STC_DEF void \
- C##X##_reserve(C##X* self, size_t cap) { \
+ CX##_reserve(CX* self, size_t cap) { \
struct csmap_rep* rep = _csmap_rep(self); \
- C##X##_size_t oldcap = rep->cap; \
+ CX##_size_t oldcap = rep->cap; \
if (cap > oldcap) { \
rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL, \
- sizeof(struct csmap_rep) + (cap + 1)*sizeof(C##X##_node_t)); \
+ sizeof(struct csmap_rep) + (cap + 1)*sizeof(CX##_node_t)); \
if (oldcap == 0) \
- memset(rep, 0, sizeof(struct csmap_rep) + sizeof(C##X##_node_t)); \
+ memset(rep, 0, sizeof(struct csmap_rep) + sizeof(CX##_node_t)); \
rep->cap = cap; \
- self->nodes = (C##X##_node_t *) rep->nodes; \
+ self->nodes = (CX##_node_t *) rep->nodes; \
} \
} \
\
- STC_DEF C##X##_size_t \
- C##X##_node_new_(C##X* self, int level) { \
+ STC_DEF CX##_size_t \
+ CX##_node_new_(CX* self, int level) { \
size_t tn; struct csmap_rep *rep = _csmap_rep(self); \
if (rep->disp) { \
tn = rep->disp; \
rep->disp = self->nodes[tn].link[1]; \
} else { \
- if ((tn = rep->head + 1) > rep->cap) C##X##_reserve(self, 4 + tn*3/2); \
+ if ((tn = rep->head + 1) > rep->cap) CX##_reserve(self, 4 + tn*3/2); \
++_csmap_rep(self)->head; /* do after reserve */ \
} \
- C##X##_node_t* dn = &self->nodes[tn]; \
+ CX##_node_t* dn = &self->nodes[tn]; \
dn->link[0] = dn->link[1] = 0; dn->level = level; \
- return (C##X##_size_t) tn; \
+ return (CX##_size_t) tn; \
} \
\
- STC_DEF C##X##_value_t* \
- C##X##_find_it(const C##X* self, RawKey rkey, C##X##_iter_t* out) { \
- C##X##_size_t tn = _csmap_rep(self)->root; \
- C##X##_node_t *d = out->_d = self->nodes; \
+ STC_DEF CX##_value_t* \
+ CX##_find_it(const CX* self, RawKey rkey, CX##_iter_t* out) { \
+ CX##_size_t tn = _csmap_rep(self)->root; \
+ CX##_node_t *d = out->_d = self->nodes; \
out->_top = 0; \
while (tn) { \
int c; RawKey rx = keyToRaw(KEY_REF_##C(&d[tn].value)); \
@@ -382,12 +379,12 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; return (out->ref = NULL); \
} \
\
- STC_DEF C##X##_iter_t \
- C##X##_lower_bound(const C##X* self, RawKey rkey) { \
- C##X##_iter_t it; \
- C##X##_find_it(self, rkey, &it); \
+ STC_DEF CX##_iter_t \
+ CX##_lower_bound(const CX* self, RawKey rkey) { \
+ CX##_iter_t it; \
+ CX##_find_it(self, rkey, &it); \
if (!it.ref && it._top) { \
- C##X##_size_t tn = it._st[--it._top]; \
+ CX##_size_t tn = it._st[--it._top]; \
it._tn = it._d[tn].link[1]; \
it.ref = &it._d[tn].value; \
} \
@@ -395,8 +392,8 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; } \
\
STC_DEF void \
- C##X##_next(C##X##_iter_t *it) { \
- C##X##_size_t tn = it->_tn; \
+ CX##_next(CX##_iter_t *it) { \
+ CX##_size_t tn = it->_tn; \
if (it->_top || tn) { \
while (tn) { \
it->_st[it->_top++] = tn; \
@@ -409,20 +406,20 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; it->ref = NULL; \
} \
\
- static C##X##_size_t \
- C##X##_skew_(C##X##_node_t *d, C##X##_size_t tn) { \
+ static CX##_size_t \
+ CX##_skew_(CX##_node_t *d, CX##_size_t tn) { \
if (tn && d[d[tn].link[0]].level == d[tn].level) { \
- C##X##_size_t tmp = d[tn].link[0]; \
+ CX##_size_t tmp = d[tn].link[0]; \
d[tn].link[0] = d[tmp].link[1]; \
d[tmp].link[1] = tn; \
tn = tmp; \
} \
return tn; \
} \
- static C##X##_size_t \
- C##X##_split_(C##X##_node_t *d, C##X##_size_t tn) { \
+ static CX##_size_t \
+ CX##_split_(CX##_node_t *d, CX##_size_t tn) { \
if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) { \
- C##X##_size_t tmp = d[tn].link[1]; \
+ CX##_size_t tmp = d[tn].link[1]; \
d[tn].link[1] = d[tmp].link[0]; \
d[tmp].link[0] = tn; \
tn = tmp; \
@@ -431,10 +428,10 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; return tn; \
} \
\
- static inline C##X##_size_t \
- C##X##_insert_entry_i_(C##X* self, C##X##_size_t tn, const C##X##_rawkey_t* rkey, C##X##_result_t* res) { \
- C##X##_size_t up[64], it = tn; \
- C##X##_node_t* d = self->nodes; \
+ static inline CX##_size_t \
+ CX##_insert_entry_i_(CX* self, CX##_size_t tn, const CX##_rawkey_t* rkey, CX##_result_t* res) { \
+ CX##_size_t up[64], it = tn; \
+ CX##_node_t* d = self->nodes; \
int c, top = 0, dir = 0; \
while (it) { \
up[top++] = it; \
@@ -443,50 +440,50 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; dir = (c == -1); \
it = d[it].link[dir]; \
} \
- it = C##X##_node_new_(self, 1); d = self->nodes; \
+ it = CX##_node_new_(self, 1); d = self->nodes; \
res->ref = &d[it].value, res->inserted = true; \
if (top == 0) return it; \
d[up[top - 1]].link[dir] = it; \
while (top--) { \
if (top) dir = (d[up[top - 1]].link[1] == up[top]); \
- up[top] = C##X##_skew_(d, up[top]); \
- up[top] = C##X##_split_(d, up[top]); \
+ up[top] = CX##_skew_(d, up[top]); \
+ up[top] = CX##_split_(d, up[top]); \
if (top) d[up[top - 1]].link[dir] = up[top]; \
} \
return up[0]; \
} \
\
- STC_DEF C##X##_result_t \
- C##X##_insert_entry_(C##X* self, RawKey rkey) { \
- C##X##_result_t res = {NULL, false}; \
- C##X##_size_t tn = C##X##_insert_entry_i_(self, (C##X##_size_t) _csmap_rep(self)->root, &rkey, &res); \
+ STC_DEF CX##_result_t \
+ CX##_insert_entry_(CX* self, RawKey rkey) { \
+ CX##_result_t res = {NULL, false}; \
+ CX##_size_t tn = CX##_insert_entry_i_(self, (CX##_size_t) _csmap_rep(self)->root, &rkey, &res); \
_csmap_rep(self)->root = tn; \
_csmap_rep(self)->size += res.inserted; \
return res; \
} \
\
- static C##X##_size_t \
- C##X##_erase_r_(C##X##_node_t *d, C##X##_size_t tn, const C##X##_rawkey_t* rkey, int *erased) { \
+ static CX##_size_t \
+ CX##_erase_r_(CX##_node_t *d, CX##_size_t tn, const CX##_rawkey_t* rkey, int *erased) { \
if (tn == 0) return 0; \
RawKey raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \
- C##X##_size_t tx; int c = keyCompareRaw(&raw, rkey); \
+ CX##_size_t tx; int c = keyCompareRaw(&raw, rkey); \
if (c != 0) \
- d[tn].link[c == -1] = C##X##_erase_r_(d, d[tn].link[c == -1], rkey, erased); \
+ d[tn].link[c == -1] = CX##_erase_r_(d, d[tn].link[c == -1], rkey, erased); \
else { \
- if (!*erased) {C##X##_value_del(&d[tn].value); *erased = 1;} \
+ if (!*erased) {CX##_value_del(&d[tn].value); *erased = 1;} \
if (d[tn].link[0] && d[tn].link[1]) { \
tx = d[tn].link[0]; \
while (d[tx].link[1]) \
tx = d[tx].link[1]; \
d[tn].value = d[tx].value; /* move */ \
raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \
- d[tn].link[0] = C##X##_erase_r_(d, d[tn].link[0], &raw, erased); \
+ d[tn].link[0] = CX##_erase_r_(d, d[tn].link[0], &raw, erased); \
} else { /* unlink node */ \
tx = tn; \
tn = d[tn].link[ d[tn].link[0] == 0 ]; \
/* move it to disposed nodes list */ \
struct csmap_rep *rep = c_container_of(d, struct csmap_rep, nodes); \
- d[tx].link[1] = (C##X##_size_t) rep->disp; \
+ d[tx].link[1] = (CX##_size_t) rep->disp; \
rep->disp = tx; \
} \
} \
@@ -494,70 +491,70 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; if (d[d[tn].link[0]].level < d[tn].level - 1 || d[tx].level < d[tn].level - 1) { \
if (d[tx].level > --d[tn].level) \
d[tx].level = d[tn].level; \
- tn = C##X##_skew_(d, tn); \
- tx = d[tn].link[1] = C##X##_skew_(d, d[tn].link[1]); \
- d[tx].link[1] = C##X##_skew_(d, d[tx].link[1]); \
- tn = C##X##_split_(d, tn); \
- d[tn].link[1] = C##X##_split_(d, d[tn].link[1]); \
+ tn = CX##_skew_(d, tn); \
+ tx = d[tn].link[1] = CX##_skew_(d, d[tn].link[1]); \
+ d[tx].link[1] = CX##_skew_(d, d[tx].link[1]); \
+ tn = CX##_split_(d, tn); \
+ d[tn].link[1] = CX##_split_(d, d[tn].link[1]); \
} \
return tn; \
} \
\
STC_DEF int \
- C##X##_erase(C##X* self, RawKey rkey) { \
+ CX##_erase(CX* self, RawKey rkey) { \
int erased = 0; \
- C##X##_size_t root = C##X##_erase_r_(self->nodes, (C##X##_size_t) _csmap_rep(self)->root, &rkey, &erased); \
+ CX##_size_t root = CX##_erase_r_(self->nodes, (CX##_size_t) _csmap_rep(self)->root, &rkey, &erased); \
if (erased) {_csmap_rep(self)->root = root; --_csmap_rep(self)->size;} \
return erased; \
} \
\
- STC_DEF C##X##_iter_t \
- C##X##_erase_at(C##X* self, C##X##_iter_t pos) { \
- RawKey raw = keyToRaw(KEY_REF_##C(pos.ref)); C##X##_next(&pos); \
+ STC_DEF CX##_iter_t \
+ CX##_erase_at(CX* self, CX##_iter_t pos) { \
+ RawKey raw = keyToRaw(KEY_REF_##C(pos.ref)); CX##_next(&pos); \
RawKey nxt = keyToRaw(KEY_REF_##C(pos.ref)); \
- C##X##_erase(self, raw); \
- C##X##_find_it(self, nxt, &pos); \
+ CX##_erase(self, raw); \
+ CX##_find_it(self, nxt, &pos); \
return pos; \
} \
\
- static C##X##_size_t \
- C##X##_clone_r_(C##X* self, const C##X##_node_t* src, C##X##_size_t sn) { \
+ static CX##_size_t \
+ CX##_clone_r_(CX* self, const CX##_node_t* src, CX##_size_t sn) { \
if (sn == 0) return 0; \
- C##X##_size_t tx, tn = C##X##_node_new_(self, src[sn].level); \
- self->nodes[tn].value = C##X##_value_clone(src[sn].value); \
- tx = C##X##_clone_r_(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx; \
- tx = C##X##_clone_r_(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx; \
+ CX##_size_t tx, tn = CX##_node_new_(self, src[sn].level); \
+ self->nodes[tn].value = CX##_value_clone(src[sn].value); \
+ tx = CX##_clone_r_(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx; \
+ tx = CX##_clone_r_(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx; \
return tn; \
} \
- STC_DEF C##X \
- C##X##_clone(C##X tree) { \
- C##X clone = C##X##_with_capacity(_csmap_rep(&tree)->size); \
- C##X##_size_t root = C##X##_clone_r_(&clone, tree.nodes, (C##X##_size_t) _csmap_rep(&tree)->root); \
+ STC_DEF CX \
+ CX##_clone(CX tree) { \
+ CX clone = CX##_with_capacity(_csmap_rep(&tree)->size); \
+ CX##_size_t root = CX##_clone_r_(&clone, tree.nodes, (CX##_size_t) _csmap_rep(&tree)->root); \
_csmap_rep(&clone)->root = root; \
_csmap_rep(&clone)->size = _csmap_rep(&tree)->size; \
return clone; \
} \
\
static void \
- C##X##_del_r_(C##X##_node_t* d, C##X##_size_t tn) { \
+ CX##_del_r_(CX##_node_t* d, CX##_size_t tn) { \
if (tn) { \
- C##X##_del_r_(d, d[tn].link[0]); \
- C##X##_del_r_(d, d[tn].link[1]); \
- C##X##_value_del(&d[tn].value); \
+ CX##_del_r_(d, d[tn].link[0]); \
+ CX##_del_r_(d, d[tn].link[1]); \
+ CX##_value_del(&d[tn].value); \
} \
} \
STC_DEF void \
- C##X##_del(C##X* self) { \
+ CX##_del(CX* self) { \
if (_csmap_rep(self)->root) { \
- C##X##_del_r_(self->nodes, (C##X##_size_t) _csmap_rep(self)->root); \
+ CX##_del_r_(self->nodes, (CX##_size_t) _csmap_rep(self)->root); \
c_free(_csmap_rep(self)); \
} \
}
#else
-#define _implement_AATREE(X, C, Key, Mapped, keyCompareRaw, \
- mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
- keyDel, keyFromRaw, keyToRaw, RawKey)
+#define _c_implement_aatree(CX, C, Key, Mapped, keyCompareRaw, \
+ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \
+ keyDel, keyFromRaw, keyToRaw, RawKey)
#endif
#endif
|