-
Notifications
You must be signed in to change notification settings - Fork 7
Home
CTL is a fast compiling, type safe, header only, template-like container library for ISO C99/C11.
Configure a CTL container with a built-in or typedef type T
.
#include <stdio.h>
#define POD
#define T int
#include <ctl/vector.h>
int compare(int* a, int* b) { return *b < *a; }
int main(void)
{
vec_int a = vec_int_init();
vec_int_push_back(&a, 9);
vec_int_push_back(&a, 1);
vec_int_push_back(&a, 8);
vec_int_push_back(&a, 3);
vec_int_push_back(&a, 4);
vec_int_sort(&a, compare);
foreach(vec_int, &a, it)
printf("%d\n", *it.ref);
vec_int_free(&a);
}
Definition POD
states type T
is Plain Old Data (POD).
For a much more thorough getting started guide, see the wiki: https://github.com/rurban/ctl/wiki and https://github.com/glouw/ctl/wiki for the original sample with three-letter names.
CTL aims to improve ISO C99/C11 developer productivity by implementing the following STL containers in ISO C99/C11:
CTL | = C++ STL | C prefix |
---|---|---|
ctl/deque.h | std::deque | deq |
ctl/list.h | std::list | list |
ctl/priority_queue.h | std::priority_queue | pqu |
ctl/queue.h | std::queue | queue |
ctl/set.h | std::set | set |
ctl/stack.h | std::stack | stack |
ctl/string.h | std::string | str |
ctl/vector.h | std::vector | vec |
ctl/map.h | std::map | map |
ctl/unordered_map.h | std::unordered_map | umap |
ctl/unordered_set.h | std::unordered_set | uset |
In work:
ctl/forward_list.h, ctl/u8string.h, ctl/u8ident.h
It is based on glouw's ctl, but with proper names, and using the incpath ctl/
prefix.
Types with memory ownership require definition POD
be omitted, and require
function declarations for the C++ equivalent of the destructor and copy constructor,
prior to the inclusion of the container:
typedef struct { ... } type;
void type_free(type*);
type type_copy(type*);
#define T type
#include <ctl/vector.h>
Forgetting a declaration will print a human-readable error message:
tests/test_c11.c:11:11: error: ‘type_free’ undeclared (first use in this function)
11 | #define T type
CTL performance is presented in solid colors, and STL in dotted colors,
for template type T
as type int
for all measurements.
Omitted from these performance measurements are queue.h
, stack.h
, and string.h
,
as their performance characteristics can be inferred from deque.h
, and vector.h
,
respectively.
unordered_set.h
not yet.
Note, CTL strings do not support short strings yet.
To run all functional tests, run:
make
To compile examples, run:
make examples
To generate performance graphs, run:
sh gen_images.sh
# Graphing requires python3 and the Plotly family of libraries via pip3.
To do all of the above in one step, run:
./all.sh
For maintaining CTL, a container templated to type int
can be
output to stdout
by running make on the container name with .i, eg:
make deque.i
make list.i
make priority_queue.i
make queue.i
make set.i
make stack.i
make string.i
make vector.i
make map.i
make unordered_set.i
make unordered_map.i
STL variants of multi-sets and multi-maps will not be implemented because
similar behaviour can be implemented as an amalgamation of a set
and list
.
See Differences below.
vector.h: realloc
string.h: vector.h
deque.h: realloc (paged)
queue.h: deque.h
stack.h: deque.h
priority_queue.h: vector.h
list.h: doubly linked list
forward_list.h: single linked list
set.h: red black tree
map.h: set.h
unordered_set.h: hashed forward linked lists (will change)
unordered_map.h: unordered_set.h
vec str deq list set map pqu que stk uset umap
+------------------------------------------------------------------------+
empty x x x x x x x x x x x
each x x x x x x x x
equal x x x x x x x x x x x
swap x x x x x x x x x x x
load_factor x x
max_load_factor x x
max_bucket_count x x
insert_or_assign x x
rehash x x
reserve x x x x
insert x x x x x x x x
init x x x x x x x x x x x
free x x x x x x x x x x x
step x x x x x x x x
range x x x x x x x x
find x x x x x x x x
count x x x x x
erase x x x x x x x x
copy x x x x x x x x
begin x x x x x x x x
end x x x x x x x x
intersection x x x x
union x x x x
difference x x x x
symmetric_difference x x x x
top x x
push x x x
pop x x x
at x x x
front x x x x x
back x x x x x
set x x x
pop_back x x x x
pop_front x x
clear x x x x x
push_back x x x x
push_front x x
transfer x
disconnect x
connect x
assign x x x x
resize x x x x
reverse x
shrink_to_fit x x
data x x
erase_node x
sort x x x x
remove_if x x x x x
splice x
merge x
unique x
append x
insert_str x
replace x x
c_str x
find x
contains x
rfind x
find_first_of x
find_last_of x
find_first_not_of x
find_last_not_of x
substr x
compare x
key_compare x
Differences to the original https://github.com/glouw/ctl
#include
with the ctl/
prefix.
Use the original long names, not three-letter abbrevations.
#define POD
not P
Added some minor missing methods, like max_size
, size
, capacity
, ...
Added map and unordered_map.
Reproducible tests with SEED=n
hashmaps are auto-rehashed when exceeding max_load_factor()
(0.85).
added max_bucket_count()
.
hashmaps will be changed from chained lists to open addressing, thus no internal bucket methods, and much faster.
On errors, like size > max_size
return silently. This avoids DDOS attacks.
When assert is used, throw them. (when assert.h included, no NDEBUG)
glouw/ctl does not treat errors at all. There cannot be any.
STL multiset and multimap variants will not be implemented because
similar behaviour can be implemented as an amalgamation of a set
and list
.
STL array and span is missing. array is just a vector.
emplace and erase_if missing (needs pair), most C++20 methods also still missing.
No short string optimization yet.
hashmaps will not rely on chained lists with buckets, and will be either changed
to open addressing or a better modern layout, such greg7mdp/parallel-hashmap.
Thus the bucket interface methods will go, except maybe max_bucket_count
.
u8string will get proper utf-8/unicode support, exceeding C++ STL. compare will check u8strings normalized to NFD. No wstring, u16string and u32string (most likely).
u8ident: POSIX std extension for people using utf-8 identifiers, but need security. See http://unicode.org/reports/tr39/ Like a kernel filesystem or user database or programming language in a UTF-8 terminal, UI widget or editor wishes to present identifiers, like names, paths or files identifiable. I.e. normalized and with identifiable characters only. Most don't display names as puny-code as webbrowers or email clients. Implement the Moderately Restrictive restriction level for identifiers as default.
- All characters in the string are in the ASCII range, or
- The string is single-script, according to the definition in TR39 Section 5.1, or
- The string is covered by any of the following sets of scripts, according to the definition in TR39 Section 5.1: Latin + Han + Hiragana + Katakana; or equivalently: Latn + Jpan Latin + Han + Bopomofo; or equivalently: Latn + Hanb Latin + Han + Hangul; or equivalently: Latn + Kore, or
- The string is covered by Latin and any one other Recommended script, except Cyrillic, Greek.
- The string must be validated UTF-8 and normalized, and only consist of valid identifier characters. Reject violations, optionally warn about confusables.
No exceptions or errors. Just ignore or return NULL. No bloat and no indirect calls.
Thank you glouw
for the initial three-letter variant https://github.com/glouw/ctl.
Thank you kully
for the Plotly code, and thank you for the general review.
Thank you smlckz
for the foreach
cleanup.