Sat, 01 Jul 2023 14:29:16 +0200
add documentation for collection.h
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@720 | 212 | ### Linked List |
universe@720 | 213 | |
universe@720 | 214 | *Header file:* [linked_list.h](api/linked__list_8h.html) |
universe@720 | 215 | |
universe@720 | 216 | ### Array List |
universe@720 | 217 | |
universe@720 | 218 | *Header file:* [array_list.h](api/array__list_8h.html) |
universe@720 | 219 | |
universe@720 | 220 | ## Map |
universe@720 | 221 | |
universe@720 | 222 | *Header file:* [map.h](api/map_8h.html) |
universe@720 | 223 | |
universe@720 | 224 | ### Hash Map |
universe@720 | 225 | |
universe@720 | 226 | *Header file:* [hash_map.h](api/hash__map_8h.html) |
universe@720 | 227 | |
universe@720 | 228 | ## Utilities |
universe@720 | 229 | |
universe@720 | 230 | *Header file:* [utils.h](api/utils_8h.html) |
universe@720 | 231 | |
universe@724 | 232 | UCX provides some utilities for routine tasks. Most of them are simple macros, like e.g. the `cx_for_n()` macro, |
universe@724 | 233 | creating a `for` loop counting from zero to (n-1) which is extremely useful to traverse the indices of |
universe@724 | 234 | an array. |
universe@724 | 235 | |
universe@724 | 236 | But the most useful utilities are the *stream copy* functions, which provide a simple way to copy all - or a |
universe@724 | 237 | bounded amount of - data from one stream to another. Since the read/write functions of a UCX buffer are |
universe@724 | 238 | fully compatible with stream read/write functions, you can easily transfer data from file or network streams to |
universe@724 | 239 | a UCX buffer or vice-versa. |
universe@724 | 240 | |
universe@724 | 241 | The following example shows, how easy it is to read the contents of a file into a buffer: |
universe@724 | 242 | ```c |
universe@724 | 243 | FILE *inputfile = fopen(infilename, "r"); |
universe@724 | 244 | if (inputfile) { |
universe@724 | 245 | CxBuffer fbuf; |
universe@724 | 246 | cxBufferInit(&fbuf, NULL, 4096, NULL, CX_BUFFER_AUTO_EXTEND); |
universe@724 | 247 | cx_stream_copy(inputfile, &fbuf, |
universe@724 | 248 | (cx_read_func) fread, |
universe@724 | 249 | (cx_write_func) cxBufferWrite); |
universe@724 | 250 | fclose(inputfile); |
universe@724 | 251 | |
universe@724 | 252 | // ... do something meaningful with the contents ... |
universe@724 | 253 | |
universe@724 | 254 | cxBufferDestroy(&fbuf); |
universe@724 | 255 | } else { |
universe@724 | 256 | perror("Error opening input file"); |
universe@724 | 257 | if (fout != stdout) { |
universe@724 | 258 | fclose(fout); |
universe@724 | 259 | } |
universe@724 | 260 | } |
universe@724 | 261 | ``` |
universe@724 | 262 | |
universe@720 | 263 | ### Printf Functions |
universe@720 | 264 | |
universe@720 | 265 | *Header file:* [printf.h](api/printf_8h.html) |
universe@720 | 266 | |
universe@725 | 267 | In this utility header you can find `printf()`-like functions that can write the formatted output to an arbitrary |
universe@725 | 268 | stream (or UCX buffer, resp.), or to memory allocated by an allocator within a single function call. |
universe@725 | 269 | With the help of these convenience functions, you do not need to `snprintf` your string to a temporary buffer anymore, |
universe@725 | 270 | plus you do not need to worry about too small buffer sizes, because the functions will automatically allocate enough |
universe@725 | 271 | memory to contain the entire formatted string. |
universe@725 | 272 | |
universe@720 | 273 | ### Compare Functions |
universe@720 | 274 | |
universe@720 | 275 | *Header file:* [compare.h](api/compare_8h.html) |
universe@725 | 276 | |
universe@725 | 277 | This header file contains a collection of compare functions for various data types. |
universe@725 | 278 | Their signatures are designed to be compatible with the `cx_compare_func` function pointer type. |