summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--examples/csmap_ex.c27
-rw-r--r--stc/csmap.h98
2 files changed, 62 insertions, 63 deletions
diff --git a/examples/csmap_ex.c b/examples/csmap_ex.c
index dac82339..13fbe977 100644
--- a/examples/csmap_ex.c
+++ b/examples/csmap_ex.c
@@ -11,40 +11,45 @@ using_csset_str();
int main(int argc, char **argv)
{
csmap_i map = csmap_i_init();
- time_t seed = time(NULL);
+ time_t seed = 123 ; // time(NULL);
- size_t n = 1000000;
+ size_t n = 5000000;
uint64_t mask = (1ull << 20) - 1;
+ csmap_i_iter_t it;
+
stc64_srandom(seed);
for (size_t i = 0; i < n; ++i) {
- csmap_i_emplace(&map, stc64_random() & mask, i);
+ uint64_t val = stc64_random() & mask;
+ csmap_i_emplace(&map, val, i);
+ if (!csmap_i_find(&map, val, &it)) {
+ printf("Not found: %zu, %zu: ", i, val);
+ }
}
- puts("inserted");
stc64_srandom(seed);
for (unsigned int i = 0; i < n - 50; ++i) {
csmap_i_erase(&map, stc64_random() & mask);
}
-
+
csmap_i_emplace(&map, 500000, 5);
c_foreach (i, csmap_i, map)
printf("-- %d: %d\n", i.ref->first, i.ref->second);
puts("");
- csmap_i_iter_t it;
- printf("min/max: %d -- %d: %d: %zu\n\n", csmap_i_front(&map)->first,
- csmap_i_back(&map)->first,
- csmap_i_find(&map, 500000, &it) != NULL,
- csmap_i_size(map));
+ csmap_i_find(&map, 500000, &it);
c_foreach (i, csmap_i, it, csmap_i_end(&map))
printf("-- %d: %d\n", i.ref->first, i.ref->second);
printf("\n%d: %d\n", 500000, *csmap_i_at(&map, 500000));
+ printf("min/max: %d -- %d: %d: %zu\n\n", csmap_i_front(&map)->first,
+ csmap_i_back(&map)->first,
+ csmap_i_find(&map, 500000, &it) != NULL,
+ csmap_i_size(map));
+
csmap_i_del(&map);
puts("done\n");
-
c_init (csset_str, names, {
"Hello", "Try this", "Awesome", "Works well", "Greetings"
});
diff --git a/stc/csmap.h b/stc/csmap.h
index b4a215c6..49600b96 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -265,15 +265,13 @@ int main(void) {
return &tn->value; \
} \
\
- STC_INLINE void \
- C##_##X##_next(C##_##X##_iter_t* it) { \
- cbst_next((csmap___iter_t*) it, offsetof(C##_##X##_node_t, value)); \
- } \
+ STC_API void \
+ C##_##X##_next(C##_##X##_iter_t* it); \
+\
STC_INLINE C##_##X##_iter_t \
C##_##X##_begin(C##_##X* self) { \
C##_##X##_iter_t it = {NULL, 0, self->root}; \
- cbst_next((csmap___iter_t*) &it, offsetof(C##_##X##_node_t, value)); \
- return it; \
+ C##_##X##_next(&it); return it; \
} \
STC_INLINE C##_##X##_iter_t \
C##_##X##_end(C##_##X* self) {\
@@ -304,10 +302,6 @@ int main(void) {
_using_CBST_types(_, csmap, int, int);
static csmap___node_t cbst_nil = {&cbst_nil, &cbst_nil, 0};
-STC_API csmap___node_t* cbst_skew(csmap___node_t *tn);
-STC_API csmap___node_t* cbst_split(csmap___node_t *tn);
-STC_API void cbst_next(csmap___iter_t *it, size_t offset);
-
/* -------------------------- IMPLEMENTATION ------------------------- */
#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)
@@ -328,6 +322,44 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
} \
} \
\
+ static C##_##X##_node_t * \
+ C##_##X##_skew_(C##_##X##_node_t *tn) { \
+ if (tn->link[0]->level == tn->level && tn->level) { \
+ C##_##X##_node_t *tmp = tn->link[0]; \
+ tn->link[0] = tmp->link[1]; \
+ tmp->link[1] = tn; \
+ tn = tmp; \
+ } \
+ return tn; \
+ } \
+\
+ static C##_##X##_node_t * \
+ C##_##X##_split_(C##_##X##_node_t *tn) { \
+ if (tn->link[1]->link[1]->level == tn->level && tn->level) { \
+ C##_##X##_node_t *tmp = tn->link[1]; \
+ tn->link[1] = tmp->link[0]; \
+ tmp->link[0] = tn; \
+ tn = tmp; \
+ ++tn->level; \
+ } \
+ return tn; \
+ } \
+\
+ STC_DEF void \
+ C##_##X##_next(C##_##X##_iter_t *it) { \
+ C##_##X##_node_t *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; \
+ } \
+\
STC_DEF C##_##X##_node_t* \
C##_##X##_insert_key_r_(C##_##X##_node_t* tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \
if (tn->level == 0) { \
@@ -341,8 +373,8 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
int c = keyCompareRaw(&r, rkey); \
if (c == 0) { res->first = &tn->value; return tn; } \
tn->link[c == -1] = C##_##X##_insert_key_r_(tn->link[c == -1], rkey, res); \
- tn = (C##_##X##_node_t*) cbst_skew((csmap___node_t*) tn); \
- tn = (C##_##X##_node_t*) cbst_split((csmap___node_t*) tn); \
+ tn = C##_##X##_skew_(tn); \
+ tn = C##_##X##_split_(tn); \
return tn; \
} \
\
@@ -381,8 +413,8 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
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 = (C##_##X##_node_t*) cbst_skew((csmap___node_t*) tn); \
- tn = (C##_##X##_node_t*) cbst_split((csmap___node_t*) tn); \
+ tn = C##_##X##_skew_(tn); \
+ tn = C##_##X##_split_(tn); \
} \
return tn; \
} \
@@ -413,44 +445,6 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
return cn; \
}
-STC_DEF csmap___node_t *
-cbst_skew(csmap___node_t *tn) {
- if (tn->link[0]->level == tn->level && tn->level) {
- csmap___node_t *tmp = tn->link[0];
- tn->link[0] = tmp->link[1];
- tmp->link[1] = tn;
- tn = tmp;
- }
- return tn;
-}
-
-STC_DEF csmap___node_t *
-cbst_split(csmap___node_t *tn) {
- if (tn->link[1]->link[1]->level == tn->level && tn->level) {
- csmap___node_t *tmp = tn->link[1];
- tn->link[1] = tmp->link[0];
- tmp->link[0] = tn;
- tn = tmp;
- ++tn->level;
- }
- return tn;
-}
-
-STC_DEF void
-cbst_next(csmap___iter_t *it, size_t offset) {
- csmap___node_t *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 = (csmap___value_t *) ((uint8_t *)tn + offset);
- } else
- it->ref = NULL;
-}
-
#else
#define _implement_CBST(X, C, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \
keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped)
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-01 10:20:23 +0000