Mon, 03 Jul 2023 18:37:19 +0200
add documentation for the lists
1 ---
2 title: UCX Features
3 ---
5 <div id="modules">
7 ------------------------ ------------------------- ------------------- ---------------------------------
8 [Allocator](#allocator) [String](#string) [Buffer](#buffer) [Memory Pool](#memory-pool)
9 [Iterator](#iterator) [Collection](#collection) [List](#list) [Map](#map)
10 [Utilities](#utilities)
11 ------------------------ ------------------------- ------------------- ---------------------------------
13 </div>
15 ## Allocator
17 *Header file:* [allocator.h](api/allocator_8h.html)
19 The UCX allocator provides an interface for implementing an own memory allocation mechanism.
20 Various function in UCX provide an additional alternative signature that takes an allocator as
21 argument. A default allocator implementation using the stdlib memory management functions is
22 available via the global symbol `cxDefaultAllocator`.
24 If you want to define your own allocator, you need to initialize the `CxAllocator` structure
25 with a pointer to an allocator class (containing function pointers for the memory management
26 functions) and an optional pointer to an arbitrary memory region that can be used to store
27 state information for the allocator. An example is shown below:
29 ```c
30 struct my_allocator_state {
31 size_t total;
32 size_t avail;
33 char mem[];
34 };
36 static cx_allocator_class my_allocator_class = {
37 my_malloc_impl,
38 my_realloc_impl, // all these functions are somewhere defined
39 my_calloc_impl,
40 my_free_impl
41 };
43 CxAllocator create_my_allocator(size_t n) {
44 CxAllocator alloc;
45 alloc.cl = &my_allocator_class;
46 alloc.data = calloc(1, sizeof(struct my_allocator_state) + n);
47 return alloc;
48 }
50 void free_my_allocator(CxAllocator *alloc) {
51 free(alloc.data);
52 free(alloc);
53 }
54 ```
56 ## String
58 *Header file:* [string.h](api/string_8h.html)
60 UCX strings come in two variants: immutable (`cxstring`) and mutable (`cxmutstr`).
61 The functions of UCX are designed to work with immutable strings by default but in situations where it is necessary,
62 the API also provides alternative functions that work directly with mutable strings.
63 Functions that change a string in-place are, of course, only accepting mutable strings.
65 When you are using UCX functions, or defining your own functions, you are sometimes facing the "problem",
66 that the function only accepts arguments of type `cxstring` but you only have a `cxmutstr` at hand.
67 In this case you _should not_ introduce a wrapper function that accepts the `cxmutstr`,
68 but instead you should use the `cx_strcast()` function to cast the argument to the correct type.
70 In general, UCX strings are **not** necessarily zero-terminated. If a function guarantees to return zero-terminated
71 string, it is explicitly mentioned in the documentation of the respective function.
72 As a rule of thumb, you _should not_ pass the strings of a UCX string structure to another API without explicitly
73 ensuring that the string is zero-terminated.
75 ## Buffer
77 *Header file:* [buffer.h](api/buffer_8h.html)
79 Instances of this buffer implementation can be used to read from or write to memory like you would do with a stream.
80 This allows the use of `cx_stream_copy()` (see [Utilities](#utilities)) to copy contents from one buffer to another,
81 or from a file or network streams to the buffer and vice-versa.
83 More features for convenient use of the buffer can be enabled, like automatic memory management and automatic
84 resizing of the buffer space.
86 Since UCX 3.0, the buffer also supports automatic flushing of contents to another stream (or buffer) as an alternative
87 to automatically resizing the buffer space.
88 Please refer to the API doc for the fields prefixed with `flush_` to learn more.
90 ## Memory Pool
92 *Header file:* [mempool.h](api/mempool_8h.html)
94 A memory pool is providing an allocator implementation that automatically deallocates the memory upon its destruction.
95 It also allows you to register destructor functions for the allocated memory, which are automatically called before
96 the memory is deallocated.
97 Additionally, you may also register _independent_ destructor functions within a pool in case some external library
98 allocated memory for you, which should be destroyed together with this pool.
100 Many UCX features support the use of an allocator.
101 The [strings](#string), for instance, provide several functions suffixed with `_a` that allow specifying an allocator.
102 You can use this to keep track of the memory occupied by dynamically allocated strings and cleanup everything with
103 just a single call to `cxMempoolDestroy()`.
105 The following code illustrates this on the example of reading a CSV file into memory.
106 ```C
107 #include <stdio.h>
108 #include <cx/mempool.h>
109 #include <cx/linked_list.h>
110 #include <cx/string.h>
111 #include <cx/buffer.h>
112 #include <cx/utils.h>
114 typedef struct {
115 cxstring column_a;
116 cxstring column_b;
117 cxstring column_c;
118 } CSVData;
120 int main(void) {
121 CxMempool* pool = cxBasicMempoolCreate(128);
123 FILE *f = fopen("test.csv", "r");
124 if (!f) {
125 perror("Cannot open file");
126 return 1;
127 }
128 // close the file automatically at pool destruction
129 cxMempoolRegister(pool, f, (cx_destructor_func) fclose);
131 // create a buffer using the memory pool for destruction
132 CxBuffer *content = cxBufferCreate(NULL, 256, pool->allocator, CX_BUFFER_AUTO_EXTEND);
134 // read the file into the buffer and turn it into a string
135 cx_stream_copy(f, content, (cx_read_func) fread, (cx_write_func) cxBufferWrite);
136 cxstring contentstr = cx_strn(content->space, content->size);
138 // split the string into lines - use the mempool for allocating the target array
139 cxstring* lines;
140 size_t lc = cx_strsplit_a(pool->allocator, contentstr,
141 CX_STR("\n"), SIZE_MAX, &lines);
143 // skip the header and parse the remaining data into a linked list
144 // the nodes of the linked list shall also be allocated by the mempool
145 CxList* datalist = cxLinkedListCreate(pool->allocator, NULL, sizeof(CSVData));
146 for (size_t i = 1 ; i < lc ; i++) {
147 if (lines[i].length == 0) continue;
148 cxstring fields[3];
149 size_t fc = cx_strsplit(lines[i], CX_STR(";"), 3, fields);
150 if (fc != 3) {
151 fprintf(stderr, "Syntax error in line %zu.\n", i);
152 cxMempoolDestroy(pool);
153 return 1;
154 }
155 CSVData* data = cxMalloc(pool->allocator, sizeof(CSVData));
156 data->column_a = fields[0];
157 data->column_b = fields[1];
158 data->column_c = fields[2];
159 cxListAdd(datalist, data);
160 }
162 // iterate through the list and output the data
163 CxIterator iter = cxListIterator(datalist);
164 cx_foreach(CSVData*, data, iter) {
165 printf("Column A: %.*s | "
166 "Column B: %.*s | "
167 "Column C: %.*s\n",
168 (int)data->column_a.length, data->column_a.ptr,
169 (int)data->column_b.length, data->column_b.ptr,
170 (int)data->column_c.length, data->column_c.ptr
171 );
172 }
174 // cleanup everything, no manual free() needed
175 cxMempoolDestroy(pool);
177 return 0;
178 }
179 ```
181 ## Iterator
183 *Header file:* [iterator.h](api/iterator_8h.html)
185 ## Collection
187 *Header file:* [collection.h](api/collection_8h.html)
189 Collections in UCX 3 have several common features.
190 If you want to implement an own collection data type that uses the same features, you can use the
191 `CX_COLLECTION_MEMBERS` macro at the beginning of your struct to roll out all members a usual UCX collection has.
192 ```c
193 struct my_fancy_collection_s {
194 CX_COLLECTION_MEMBERS
195 struct my_collection_data_s *data;
196 };
197 ```
198 Based on this structure, this header provides some convenience macros for invoking the destructor functions
199 that are part of the basic collection members.
200 The idea of having destructor functions within a collection is that you can destroy the collection _and_ the
201 contents with one single function call.
202 When you are implementing a collection, you are responsible for invoking the destructors at the right places, e.g.
203 when removing (and deleting) elements in the collection, clearing the collection, or - the most prominent case -
204 destroying the collection.
206 You can always look at the UCX list and map implementations if you need some inspiration.
208 ## List
210 *Header file:* [list.h](api/list_8h.html)
212 This header defines a common interface for all list implementations, which is basically as simple as the following
213 structure.
214 ```c
215 struct cx_list_s {
216 CX_COLLECTION_MEMBERS // size, capacity, etc.
217 cx_list_class const *cl; // The list class definition
218 };
219 ```
220 The actual structure contains one more class pointer that is used when wrapping a list into a pointer aware list
221 with `cxListStorePointers()`. What this means, is that - if you want to implement your own list structure - you
222 only need to cover the case where the list is storing copies of your objects.
224 UCX comes with two common list implementations (linked list and array list) that should cover most use cases.
225 But if you feel the need to implement an own list, the only thing you need to do is to define a struct where
226 `struct cx_list_s`, and set an appropriate list class that implements the functionality.
227 It is strongly recommended that this class is shared among all instances of the same list type, because otherwise
228 the `cxListCompare` function cannot use the optimized implementation of your class and will instead fall back to
229 using iterators to compare the contents element-wise.
231 ### Linked List
233 *Header file:* [linked_list.h](api/linked__list_8h.html)
235 On top of implementing the list interface, this header also defines several low-level functions that
236 work with arbitrary structures.
237 Low-level functions, in contrast to the high-level list interface, can easily be recognized by their snake-casing.
238 The function `cx_linked_list_at`, for example, implements a similar functionality like `cxListAt`, but operates
239 on arbitrary structures.
240 The following snippet shows how it is used.
241 All other low-level functions work similarly.
242 ```c
243 struct node {
244 node *next;
245 node *prev;
246 int data;
247 };
249 const ptrdiff_t loc_prev = offsetof(struct node, prev);
250 const ptrdiff_t loc_next = offsetof(struct node, next);
251 const ptrdiff_t loc_data = offsetof(struct node, data);
253 struct node a = {0}, b = {0}, c = {0}, d = {0};
254 cx_linked_list_link(&a, &b, loc_prev, loc_next);
255 cx_linked_list_link(&b, &c, loc_prev, loc_next);
256 cx_linked_list_link(&c, &d, loc_prev, loc_next);
258 cx_linked_list_at(&a, 0, loc_next, 2); // returns pointer to c
259 ```
261 ### Array List
263 *Header file:* [array_list.h](api/array__list_8h.html)
265 Since low-level array lists are just plain arrays, there is no need for such many low-level functions as for linked
266 lists.
267 However, there is one extremely powerful function that can be used for several complex tasks: `cx_array_copy`.
268 The full signature is shown below:
269 ```c
270 enum cx_array_copy_result cx_array_copy(
271 void **target,
272 size_t *size,
273 size_t *capacity, // optional
274 size_t index,
275 void const *src,
276 size_t elem_size,
277 size_t elem_count,
278 struct cx_array_reallocator_s *reallocator // optional
279 );
280 ```
281 The `target` argument is a pointer to the target array pointer.
282 The reason for this additional indirection is that - given that you provide a `reallocator` - this function writes
283 back the pointer to the possibly reallocated array.
284 THe next two arguments are pointers to the `size` and `capacity` of the target array.
285 Tracking the capacity is optional.
286 If you do not specify a pointer for the capacity, automatic reallocation of the array is entirely disabled (i.e. it
287 does not make sense to specify a `reallocator` then).
288 In this case, the function cannot copy more than `size-index` elements and if you try, it will return
289 `CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED` and do nothing.
291 On a successful invocation, the function copies `elem_count` number of elements, each of size `elem_size` from
292 `src` to `*target` and uses the `reallocator` to extend the array when necessary.
293 Finally, the size, capacity, and the pointer to the array are all updated and the function returns
294 `CX_ARRAY_COPY_SUCCESS`.
296 The third, but extremely rare, return code is `CX_ARRAY_COPY_REALLOC_FAILED` and speaks for itself.
298 A few things to note:
299 * `*target` and `src` can point to the same memory region, effectively copying elements within the array with `memmove`
300 * `*target` does not need to point to the start of the array, but `size` and `capacity` always start counting from the
301 position, `*target` points to - in this scenario, specifying a `reallocator` is forbidden for obvious reasons
302 * `index` does not need to be within size of the current array, if `capacity` is specified
303 * `index` does not even need to be within the capacity of the array, if `reallocator` is specified
306 ## Map
308 *Header file:* [map.h](api/map_8h.html)
310 ### Hash Map
312 *Header file:* [hash_map.h](api/hash__map_8h.html)
314 ## Utilities
316 *Header file:* [utils.h](api/utils_8h.html)
318 UCX provides some utilities for routine tasks. Most of them are simple macros, like e.g. the `cx_for_n()` macro,
319 creating a `for` loop counting from zero to (n-1) which is extremely useful to traverse the indices of
320 an array.
322 But the most useful utilities are the *stream copy* functions, which provide a simple way to copy all - or a
323 bounded amount of - data from one stream to another. Since the read/write functions of a UCX buffer are
324 fully compatible with stream read/write functions, you can easily transfer data from file or network streams to
325 a UCX buffer or vice-versa.
327 The following example shows, how easy it is to read the contents of a file into a buffer:
328 ```c
329 FILE *inputfile = fopen(infilename, "r");
330 if (inputfile) {
331 CxBuffer fbuf;
332 cxBufferInit(&fbuf, NULL, 4096, NULL, CX_BUFFER_AUTO_EXTEND);
333 cx_stream_copy(inputfile, &fbuf,
334 (cx_read_func) fread,
335 (cx_write_func) cxBufferWrite);
336 fclose(inputfile);
338 // ... do something meaningful with the contents ...
340 cxBufferDestroy(&fbuf);
341 } else {
342 perror("Error opening input file");
343 if (fout != stdout) {
344 fclose(fout);
345 }
346 }
347 ```
349 ### Printf Functions
351 *Header file:* [printf.h](api/printf_8h.html)
353 In this utility header you can find `printf()`-like functions that can write the formatted output to an arbitrary
354 stream (or UCX buffer, resp.), or to memory allocated by an allocator within a single function call.
355 With the help of these convenience functions, you do not need to `snprintf` your string to a temporary buffer anymore,
356 plus you do not need to worry about too small buffer sizes, because the functions will automatically allocate enough
357 memory to contain the entire formatted string.
359 ### Compare Functions
361 *Header file:* [compare.h](api/compare_8h.html)
363 This header file contains a collection of compare functions for various data types.
364 Their signatures are designed to be compatible with the `cx_compare_func` function pointer type.