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