diff options
| -rw-r--r-- | README.md | 6 | ||||
| -rw-r--r-- | docs/clist_api.md | 15 | ||||
| -rw-r--r-- | docs/csset_api.md | 7 | ||||
| -rw-r--r-- | examples/csset_erase.c | 29 | ||||
| -rw-r--r-- | stc/csmap.h | 2 |
5 files changed, 46 insertions, 13 deletions
@@ -8,7 +8,11 @@ Introduction A modern, templated, user-friendly, fast, fully type-safe, and customizable container library for C99,
with a uniform API across the containers, and is similar to the c++ standard library containers API.
-It is a compact, header-only library with the all the major "standard" data containers, except for the multi-map/set variants:
+Please read [this blog](https://iafisher.com/blog/2020/06/type-safe-generics-in-c) by Ian Fisher for
+an introduction to type-safe generic data structures in C.
+
+STC is a compact, header-only library with the all the major "standard" data containers, except for
+the multi-map/set variants:
- [***carray*** - **multi-dim array** type](docs/carray_api.md)
- [***cbits*** - **std::bitset** alike type](docs/cbits_api.md)
- [***cdeq*** - **std::deque** alike type](docs/cdeq_api.md)
diff --git a/docs/clist_api.md b/docs/clist_api.md index 9d0945d6..d1219046 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -7,7 +7,7 @@ Fast random access is not supported. Unlike the c++ class *std::forward_list*, **clist** has an API similar to ***std::list***, and also supports *push_back()* (**O**(1) time). It is still implemented as a singly-linked list. A **clist** object occupies only one pointer in memory, and like *std::forward_list* the length of the list is not stored. -The method *clist_X_count()* returns size of list, computed in **O**(*n*) time. +All functions have **O**(1) complexity, apart from *clist_X_count()*, which returns size of list in **O**(*n*) time. ***Iterator invalidation***: Adding, removing and moving the elements within the list, or across several lists will invalidate other iterators currently refering to these elements and their immediate succesive elements. @@ -51,7 +51,7 @@ void clist_X_clear(clist_X* self); void clist_X_del(clist_X* self); // destructor bool clist_X_empty(clist_X list); -size_t clist_X_count(clist_X list); // size() in O(n) +size_t clist_X_count(clist_X list); // size() in O(n) time clist_X_value_t* clist_X_front(const clist_X* self); clist_X_value_t* clist_X_back(const clist_X* self); @@ -60,11 +60,11 @@ void clist_X_push_front(clist_X* self, Value value); void clist_X_emplace_front(clist_X* self, RawValue raw); void clist_X_pop_front(clist_X* self); -void clist_X_push_back(clist_X* self, Value value); +void clist_X_push_back(clist_X* self, Value value); // note: no pop_back(). void clist_X_emplace_back(clist_X* self, RawValue raw); void clist_X_emplace_n(clist_X *self, const clist_X_rawvalue_t arr[], size_t size); -clist_X_iter_t clist_X_insert(clist_X* self, clist_X_iter_t it, Value value); // return iter to new elem; 'it' may be end +clist_X_iter_t clist_X_insert(clist_X* self, clist_X_iter_t it, Value value); // return iter to new elem; End allowed clist_X_iter_t clist_X_emplace(clist_X* self, clist_X_iter_t it, RawValue raw); clist_X_iter_t clist_X_erase_at(clist_X* self, clist_X_iter_t it); // return iter after it @@ -72,9 +72,9 @@ clist_X_iter_t clist_X_erase_range(clist_X* self, clist_X_iter_t it1, clist size_t clist_X_remove(clist_X* self, RawValue raw); // removes all elements equal to raw void clist_X_splice(clist_X* self, clist_X_iter_t it, clist_X* other); -void clist_X_splice_range(clist_X* self, clist_X_iter_t it, +void clist_X_splice_range(clist_X* self, clist_X_iter_t it, // see std::list::splice() docs clist_X* other, clist_X_iter_t it1, clist_X_iter_t it2); - // non-std: split out [it1, it2) from self, returned as a clist + // split out [it1, it2) from self, and return as a clist clist_X clist_X_split(clist_X* self, clist_X_iter_t it1, clist_X_iter_t it2); clist_X_iter_t clist_X_find(const clist_X* self, RawValue raw); @@ -87,8 +87,7 @@ clist_X_iter_t clist_X_begin(const clist_X* self); clist_X_iter_t clist_X_end(const clist_X* self); void clist_X_next(clist_X_iter_t* it); - // advance iter n elements forward. accepts and can return end. -clist_X_iter_t clist_X_fwd(clist_X_iter it, size_t n); +clist_X_iter_t clist_X_fwd(clist_X_iter it, size_t n); // return it n elements ahead. End allowed. clist_X_value_t clist_X_value_clone(clist_X_value_t val); ``` diff --git a/docs/csset_api.md b/docs/csset_api.md index 002752f7..67e3c6a7 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -29,13 +29,13 @@ csset_X csset_X_clone(csset_x set); void csset_X_clear(csset_X* self);
void csset_X_swap(csset_X* a, csset_X* b);
-void csset_X_del(csset_X* self); // destructor
+void csset_X_del(csset_X* self); // destructor
bool csset_X_empty(csset_X set);
size_t csset_X_size(csset_X set);
csset_X_iter_t csset_X_find(const csset_X* self, RawKey rkey);
-csset_X_iter_t csset_X_lower_bound(const csset_X* self, RawKey rkey); // find closest entry >= rkey
+csset_X_iter_t csset_X_lower_bound(const csset_X* self, RawKey rkey); // find closest entry >= rkey
csset_X_value_t* csset_X_find_it(const csset_X* self, RawKey rkey, csset_X_iter_t* out);
bool csset_X_contains(const csset_X* self, RawKey rkey);
@@ -44,7 +44,8 @@ csset_X_result_t csset_X_emplace(csset_X* self, RawKey rkey); void csset_X_emplace_n(csset_X* self, const RawKey arr[], size_t size);
size_t csset_X_erase(csset_X* self, RawKey rkey);
-csset_X_iter_t csset_X_erase_at(csset_X* self, csset_X_iter_t pos);
+csset_X_iter_t csset_X_erase_at(csset_X* self, csset_X_iter_t it); // return iter after it
+csset_X_iter_t csset_X_erase_range(csset_X* self, csset_X_iter_t it1, csset_X_iter_t it2); // return updated it2
csset_X_iter_t csset_X_begin(const csset_X* self);
csset_X_iter_t csset_X_end(const csset_X* self);
diff --git a/examples/csset_erase.c b/examples/csset_erase.c new file mode 100644 index 00000000..9a05290d --- /dev/null +++ b/examples/csset_erase.c @@ -0,0 +1,29 @@ +#include <stc/csset.h>
+#include <stdio.h>
+
+using_csset(i, int);
+
+int main()
+{
+ c_init(csset_i, set, {30, 20, 80, 40, 60, 90, 10, 70, 50});
+ c_foreach (k, csset_i, set) printf(" %d", *k.ref); puts("");
+
+ int val = 64;
+ csset_i_iter_t it;
+ printf("Show values >= %d:\n", val);
+ it = csset_i_lower_bound(&set, val);
+ c_foreach (k, csset_i, it, csset_i_end(&set)) printf(" %d", *k.ref); puts("");
+
+ printf("Erase values >= %d:\n", val);
+ while (it.ref) it = csset_i_erase_at(&set, it);
+ c_foreach (k, csset_i, set) printf(" %d", *k.ref); puts("");
+
+ val = 35;
+ printf("Erase values < %d:\n", val);
+ it = csset_i_lower_bound(&set, val);
+ csset_i_erase_range(&set, csset_i_begin(&set), it);
+ c_foreach (k, csset_i, set) printf(" %d", *k.ref); puts("");
+
+ csset_i_del(&set);
+}
+
diff --git a/stc/csmap.h b/stc/csmap.h index 7e433c1d..dcf6d04d 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -171,7 +171,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; CX##_value_t *ref; \
CX##_node_t *_d; \
int _top; \
- CX##_size_t _tn, _st[40]; \
+ CX##_size_t _tn, _st[36]; \
} CX##_iter_t; \
\
STC_API CX CX##_init(void); \
|