Wed, 09 May 2018 20:15:10 +0200
adds new shift operations for UcxBuffer (including tests and a usage example in modules.md)
universe@264 | 1 | --- |
universe@264 | 2 | title: Modules |
universe@264 | 3 | --- |
universe@259 | 4 | |
universe@259 | 5 | UCX provides several modules for data structures and algorithms. |
universe@259 | 6 | You may choose to use specific modules by inclueding the corresponding header |
universe@259 | 7 | file. |
universe@259 | 8 | Please note, that some modules make use of other UCX modules. |
universe@259 | 9 | For instance, the [Allocator](#allocator) module is used by many other modules |
universe@259 | 10 | to allow flexible memory allocation. |
universe@259 | 11 | By default the header files are placed into an `ucx` directory within your |
universe@282 | 12 | systems include directory. In this case you can use a module by including it |
universe@259 | 13 | via `#include <ucx/MODULENAME.h>`. |
universe@259 | 14 | Required modules are included automatically. |
universe@259 | 15 | |
universe@267 | 16 | <div id="modules" align="center"> |
universe@267 | 17 | |
universe@280 | 18 | ----------------------- ---------------------- ---------------------------- ------------------------- |
universe@280 | 19 | [Allocator](#allocator) [AVL Tree](#avl-tree) [Buffer](#buffer) [List](#list) |
universe@280 | 20 | [Logging](#logging) [Map](#map) [Memory Pool](#memory-pool) [Properties](#properties) |
universe@280 | 21 | [Stack](#stack) [String](#string) [Testing](#testing) [Utilities](#utilities) |
universe@280 | 22 | ----------------------- ---------------------- ---------------------------- ------------------------- |
universe@267 | 23 | |
universe@267 | 24 | </div> |
universe@267 | 25 | |
universe@259 | 26 | ## Allocator |
universe@259 | 27 | |
universe@259 | 28 | *Header file:* [allocator.h](api/allocator_8h.html) |
universe@259 | 29 | *Required modules:* None. |
universe@259 | 30 | |
universe@259 | 31 | A UCX allocator consists of a pointer to the memory area / pool and four |
universe@259 | 32 | function pointers to memory management functions operating on this memory |
universe@259 | 33 | area / pool. These functions shall behave equivalent to the standard libc |
universe@259 | 34 | functions `malloc`, `calloc`, `realloc` and `free`. |
universe@259 | 35 | |
universe@259 | 36 | The signature of the memory management functions is based on the signature |
universe@259 | 37 | of the respective libc function but each of them takes the pointer to the |
universe@259 | 38 | memory area / pool as first argument. |
universe@259 | 39 | |
universe@259 | 40 | As the pointer to the memory area / pool can be arbitrarily chosen, any data |
universe@259 | 41 | can be provided to the memory management functions. One example is the |
universe@280 | 42 | [UCX Memory Pool](#memory-pool). |
universe@259 | 43 | |
universe@259 | 44 | ## AVL Tree |
universe@259 | 45 | |
universe@259 | 46 | *Header file:* [avl.h](api/avl_8h.html) |
universe@259 | 47 | *Required modules:* [Allocator](#allocator) |
universe@259 | 48 | |
universe@259 | 49 | This binary search tree implementation allows average O(1) insertion and |
universe@259 | 50 | removal of elements (excluding binary search time). |
universe@259 | 51 | All common binary tree operations are implemented. Furthermore, this module |
universe@259 | 52 | provides search functions via lower and upper bounds. |
universe@259 | 53 | |
universe@287 | 54 | ### Filtering items with a time window |
universe@287 | 55 | |
universe@287 | 56 | Suppose you have a list of items which contain a `time_t` value and your task |
universe@287 | 57 | is to find all items within a time window `[t_start, t_end]`. |
universe@287 | 58 | With AVL Trees this is easy: |
universe@287 | 59 | ```C |
universe@287 | 60 | /* --------------------- |
universe@287 | 61 | * Somewhere in a header |
universe@287 | 62 | */ |
universe@287 | 63 | typedef struct { |
universe@287 | 64 | time_t ts; |
universe@287 | 65 | // other important data |
universe@287 | 66 | } MyObject; |
universe@287 | 67 | |
universe@287 | 68 | /* ----------- |
universe@287 | 69 | * Source code |
universe@287 | 70 | */ |
universe@287 | 71 | |
universe@287 | 72 | UcxAVLTree* tree = ucx_avl_new(ucx_longintcmp); |
universe@287 | 73 | // ... populate tree with objects, use '& MyObject.ts' as key ... |
universe@287 | 74 | |
universe@287 | 75 | |
universe@287 | 76 | // Now find every item, with 30 <= ts <= 70 |
universe@287 | 77 | time_t ts_start = 30; |
universe@287 | 78 | time_t ts_end = 70; |
universe@287 | 79 | |
universe@287 | 80 | printf("Values in range:\n"); |
universe@287 | 81 | for ( |
universe@287 | 82 | UcxAVLNode* node = ucx_avl_find_node( |
universe@287 | 83 | tree, (intptr_t) &ts_start, |
universe@287 | 84 | ucx_longintdist, UCX_AVL_FIND_LOWER_BOUNDED); |
universe@287 | 85 | node && (*(time_t*)node->key) <= ts_end; |
universe@287 | 86 | node = ucx_avl_succ(node) |
universe@287 | 87 | ) { |
universe@287 | 88 | printf(" ts: %ld\n", ((MyObject*)node->value)->ts); |
universe@287 | 89 | } |
universe@287 | 90 | |
universe@287 | 91 | ucx_avl_free_content(tree, free); |
universe@287 | 92 | ucx_avl_free(tree); |
universe@287 | 93 | ``` |
universe@287 | 94 | |
universe@259 | 95 | ## Buffer |
universe@259 | 96 | |
universe@259 | 97 | *Header file:* [buffer.h](api/buffer_8h.html) |
universe@259 | 98 | *Required modules:* None. |
universe@259 | 99 | |
universe@259 | 100 | Instances of this buffer implementation can be used to read from or to write to |
universe@259 | 101 | memory like you would do with a stream. This allows the use of |
universe@282 | 102 | `ucx_stream_copy()` from the [Utilities](#utilities) module to copy contents |
universe@282 | 103 | from one buffer to another or from file or network streams to the buffer and |
universe@259 | 104 | vice-versa. |
universe@259 | 105 | |
universe@259 | 106 | More features for convenient use of the buffer can be enabled, like automatic |
universe@259 | 107 | memory management and automatic resizing of the buffer space. |
universe@259 | 108 | See the documentation of the macro constants in the header file for more |
universe@259 | 109 | information. |
universe@259 | 110 | |
universe@290 | 111 | ### Add line numbers to a file |
universe@290 | 112 | |
universe@290 | 113 | When reading a file line by line, you have three options: first, you could limit |
universe@290 | 114 | the maximum supported line length. |
universe@290 | 115 | Second, you allocate a god buffer large |
universe@290 | 116 | enough for the most lines a text file could have. |
universe@290 | 117 | And third, undoubtedly the best option, you start with a small buffer, which |
universe@290 | 118 | adjusts on demand. |
universe@290 | 119 | An `UcxBuffer` can be created to do just that for you. |
universe@290 | 120 | Just pass the `UCX_BUFFER_AUTOEXTEND` option to the initialization function. |
universe@290 | 121 | Here is a full working program, which adds line numbers to a file. |
universe@290 | 122 | ```C |
universe@290 | 123 | #include <stdio.h> |
universe@290 | 124 | #include <ucx/buffer.h> |
universe@290 | 125 | #include <ucx/utils.h> |
universe@290 | 126 | |
universe@290 | 127 | int main(int argc, char** argv) { |
universe@290 | 128 | |
universe@290 | 129 | if (argc != 2) { |
universe@290 | 130 | fprintf(stderr, "Usage: %s <file>\n", argv[0]); |
universe@290 | 131 | return 1; |
universe@290 | 132 | } |
universe@290 | 133 | |
universe@290 | 134 | FILE* input = fopen(argv[1], "r"); |
universe@290 | 135 | if (!input) { |
universe@290 | 136 | perror("Canno read input"); |
universe@290 | 137 | return 1; |
universe@290 | 138 | } |
universe@290 | 139 | |
universe@290 | 140 | const size_t chunksize = 256; |
universe@290 | 141 | |
universe@290 | 142 | UcxBuffer* linebuf = |
universe@290 | 143 | ucx_buffer_new( |
universe@290 | 144 | NULL, // the buffer should manage the memory area for us |
universe@290 | 145 | chunksize, // initial buffer size should be the chunk size |
universe@290 | 146 | UCX_BUFFER_AUTOEXTEND); // the buffer will grow when necessary |
universe@290 | 147 | |
universe@290 | 148 | size_t lineno = 1; |
universe@290 | 149 | do { |
universe@290 | 150 | // read line chunk |
universe@290 | 151 | size_t read = ucx_stream_ncopy( |
universe@290 | 152 | input, linebuf, fread, ucx_buffer_write, chunksize); |
universe@290 | 153 | if (read == 0) break; |
universe@290 | 154 | |
universe@290 | 155 | // handle line endings |
universe@290 | 156 | do { |
universe@290 | 157 | sstr_t bufstr = ucx_buffer_to_sstr(linebuf); |
universe@290 | 158 | sstr_t nl = sstrchr(bufstr, '\n'); |
universe@290 | 159 | if (nl.length == 0) break; |
universe@290 | 160 | |
universe@290 | 161 | size_t linelen = bufstr.length - nl.length; |
universe@290 | 162 | sstr_t linestr = sstrsubsl(bufstr, 0, linelen); |
universe@290 | 163 | |
universe@290 | 164 | printf("%zu: %" PRIsstr "\n", lineno++, SFMT(linestr)); |
universe@290 | 165 | |
universe@290 | 166 | // shift the buffer to the next line |
universe@290 | 167 | ucx_buffer_shift_left(linebuf, linelen+1); |
universe@290 | 168 | } while(1); |
universe@290 | 169 | |
universe@290 | 170 | } while(1); |
universe@290 | 171 | |
universe@290 | 172 | // print the 'noeol' line, if any |
universe@290 | 173 | sstr_t lastline = ucx_buffer_to_sstr(linebuf); |
universe@290 | 174 | if (lastline.length > 0) { |
universe@290 | 175 | printf("%zu: %" PRIsstr, lineno, SFMT(lastline)); |
universe@290 | 176 | } |
universe@290 | 177 | |
universe@290 | 178 | fclose(input); |
universe@290 | 179 | ucx_buffer_free(linebuf); |
universe@290 | 180 | |
universe@290 | 181 | return 0; |
universe@290 | 182 | } |
universe@290 | 183 | ``` |
universe@290 | 184 | |
universe@259 | 185 | ## List |
universe@259 | 186 | |
universe@259 | 187 | *Header file:* [list.h](api/list_8h.html) |
universe@259 | 188 | *Required modules:* [Allocator](#allocator) |
universe@259 | 189 | |
universe@259 | 190 | This module provides the data structure and several functions for a doubly |
universe@259 | 191 | linked list. Among the common operations like insert, remove, search and sort, |
universe@259 | 192 | we allow convenient iteration via a special `UCX_FOREACH` macro. |
universe@259 | 193 | |
universe@259 | 194 | ## Logging |
universe@259 | 195 | |
universe@259 | 196 | *Header file:* [logging.h](api/logging_8h.html) |
universe@259 | 197 | *Required modules:* [Map](#map), [String](#string) |
universe@259 | 198 | |
universe@259 | 199 | The logging module comes with some predefined log levels and allows some more |
universe@259 | 200 | customization. You may choose if you want to get timestamps or source file and |
universe@259 | 201 | line number logged automatically when outputting a message. |
universe@259 | 202 | |
universe@259 | 203 | |
universe@259 | 204 | ## Map |
universe@259 | 205 | |
universe@259 | 206 | *Header file:* [map.h](api/map_8h.html) |
universe@259 | 207 | *Required modules:* [Allocator](#allocator), [String](#string) |
universe@259 | 208 | |
universe@259 | 209 | This module provides a hash map implementation using murmur hash 2 and separate |
universe@259 | 210 | chaining with linked lists. Similarly to the list module, we provide a |
universe@259 | 211 | `UCX_MAP_FOREACH` macro to conveniently iterate through the key/value pairs. |
universe@259 | 212 | |
universe@259 | 213 | ## Memory Pool |
universe@259 | 214 | |
universe@259 | 215 | *Header file:* [mempool.h](api/mempool_8h.html) |
universe@259 | 216 | *Required modules:* [Allocator](#allocator) |
universe@259 | 217 | |
universe@259 | 218 | Here we have a concrete allocator implementation in the sense of a memory pool. |
universe@259 | 219 | This pool allows you to register destructor functions for the allocated memory, |
universe@259 | 220 | which are automatically called on the destruction of the pool. |
universe@259 | 221 | But you may also register *independent* destructor functions within a pool in |
universe@259 | 222 | case, some external library allocated memory for you, which you wish to be |
universe@259 | 223 | destroyed together with this pool. |
universe@259 | 224 | |
universe@259 | 225 | ## Properties |
universe@259 | 226 | |
universe@259 | 227 | *Header file:* [properties.h](api/properties_8h.html) |
universe@259 | 228 | *Required modules:* [Map](#map) |
universe@259 | 229 | |
universe@259 | 230 | This module provides load and store function for `*.properties` files. |
universe@259 | 231 | The key/value pairs are stored within an UCX Map. |
universe@259 | 232 | |
universe@277 | 233 | ### Example: Loading properties from a file |
universe@277 | 234 | |
universe@277 | 235 | ```C |
universe@277 | 236 | // Open the file as usual |
universe@277 | 237 | FILE* file = fopen("myprops.properties", "r"); |
universe@277 | 238 | if (!file) { |
universe@277 | 239 | // error handling |
universe@277 | 240 | return 1; |
universe@277 | 241 | } |
universe@277 | 242 | |
universe@277 | 243 | // Load the properties from the file |
universe@277 | 244 | UcxMap* myprops = ucx_map_new(16); |
universe@277 | 245 | if (ucx_properties_load(myprops, file)) { |
universe@277 | 246 | // error handling |
universe@277 | 247 | fclose(file); |
universe@277 | 248 | ucx_map_free(myprops); |
universe@277 | 249 | return 1; |
universe@277 | 250 | } |
universe@277 | 251 | |
universe@277 | 252 | // Print out the key/value pairs |
universe@277 | 253 | char* propval; |
universe@277 | 254 | UcxMapIterator propiter = ucx_map_iterator(myprops); |
universe@277 | 255 | UCX_MAP_FOREACH(key, propval, propiter) { |
universe@277 | 256 | printf("%s = %s\n", (char*)key.data, propval); |
universe@277 | 257 | } |
universe@277 | 258 | |
universe@277 | 259 | // Don't forget to free the values before freeing the map |
universe@277 | 260 | ucx_map_free_content(myprops, NULL); |
universe@277 | 261 | ucx_map_free(myprops); |
universe@277 | 262 | fclose(file); |
universe@277 | 263 | ``` |
universe@259 | 264 | ## Stack |
universe@259 | 265 | |
universe@259 | 266 | *Header file:* [stack.h](api/stack_8h.html) |
universe@259 | 267 | *Required modules:* [Allocator](#allocator) |
universe@259 | 268 | |
universe@259 | 269 | This concrete implementation of an UCX Allocator allows you to grab some amount |
universe@259 | 270 | of memory which is then handled as a stack. |
universe@259 | 271 | Please note, that the term *stack* only refers to the behavior of this |
universe@259 | 272 | allocator. You may still choose if you want to use stack or heap memory |
universe@259 | 273 | for the underlying space. |
universe@259 | 274 | |
universe@259 | 275 | A typical use case is an algorithm where you need to allocate and free large |
universe@259 | 276 | amounts of memory very frequently. |
universe@259 | 277 | |
universe@259 | 278 | ## String |
universe@259 | 279 | |
universe@259 | 280 | *Header file:* [string.h](api/string_8h.html) |
universe@259 | 281 | *Required modules:* [Allocator](#allocator) |
universe@259 | 282 | |
universe@259 | 283 | This module provides a safe implementation of bounded string. |
universe@259 | 284 | Usually C strings do not carry a length. While for zero-terminated strings you |
universe@259 | 285 | can easily get the length with `strlen`, this is not generally possible for |
universe@259 | 286 | arbitrary strings. |
universe@259 | 287 | The `sstr_t` type of this module always carries the string and its length to |
universe@259 | 288 | reduce the risk of buffer overflows dramatically. |
universe@259 | 289 | |
universe@267 | 290 | ### Initialization |
universe@267 | 291 | |
universe@267 | 292 | There are several ways to create an `sstr_t`: |
universe@267 | 293 | |
universe@267 | 294 | ```C |
universe@267 | 295 | /* (1) sstr() uses strlen() internally, hence cstr MUST be zero-terminated */ |
universe@267 | 296 | sstr_t a = sstr(cstr); |
universe@267 | 297 | |
universe@267 | 298 | /* (2) cstr does not need to be zero-terminated, if length is specified */ |
universe@267 | 299 | sstr_t b = sstrn(cstr, len); |
universe@267 | 300 | |
universe@267 | 301 | /* (3) S() macro creates sstr_t from a string using sizeof() and using sstrn(). |
universe@267 | 302 | This version is especially useful for function arguments */ |
universe@267 | 303 | sstr_t c = S("hello"); |
universe@267 | 304 | |
universe@267 | 305 | /* (4) ST() macro creates sstr_t struct literal using sizeof() */ |
universe@267 | 306 | sstr_t d = ST("hello"); |
universe@267 | 307 | ``` |
universe@267 | 308 | |
universe@267 | 309 | You should not use the `S()` or `ST()` macro with string of unknown origin, |
universe@267 | 310 | since the `sizeof()` call might not coincide with the string length in those |
universe@267 | 311 | cases. If you know what you are doing, it can save you some performance, |
universe@267 | 312 | because you do not need the `strlen()` call. |
universe@267 | 313 | |
universe@267 | 314 | ### Finding the position of a substring |
universe@267 | 315 | |
universe@267 | 316 | The `sstrstr()` function gives you a new `sstr_t` object starting with the |
universe@267 | 317 | requested substring. Thus determining the position comes down to a simple |
universe@267 | 318 | subtraction. |
universe@267 | 319 | |
universe@267 | 320 | ```C |
universe@267 | 321 | sstr_t haystack = ST("Here we go!"); |
universe@267 | 322 | sstr_t needle = ST("we"); |
universe@267 | 323 | sstr_t result = sstrstr(haystack, needle); |
universe@267 | 324 | if (result.ptr) |
universe@267 | 325 | printf("Found at position %zd.\n", haystack.length-result.length); |
universe@267 | 326 | else |
universe@267 | 327 | printf("Not found.\n"); |
universe@267 | 328 | ``` |
universe@267 | 329 | |
universe@267 | 330 | ### Spliting a string by a delimiter |
universe@267 | 331 | |
universe@267 | 332 | The `sstrsplit()` function (and its allocator based version `sstrsplit_a()`) is |
universe@267 | 333 | very powerful and might look a bit nasty at a first glance. But it is indeed |
universe@267 | 334 | very simple to use. It is even more convenient in combination with a memory |
universe@267 | 335 | pool. |
universe@267 | 336 | |
universe@267 | 337 | ```C |
universe@267 | 338 | sstr_t test = ST("here::are::some::strings"); |
universe@267 | 339 | sstr_t delim = ST("::"); |
universe@267 | 340 | |
universe@267 | 341 | ssize_t count = 0; /* no limit */ |
universe@267 | 342 | UcxMempool* pool = ucx_mempool_new_default(); |
universe@267 | 343 | |
universe@267 | 344 | sstr_t* result = sstrsplit_a(pool->allocator, test, delim, &count); |
universe@267 | 345 | for (ssize_t i = 0 ; i < count ; i++) { |
universe@267 | 346 | /* don't forget to specify the length via the %*s format specifier */ |
universe@267 | 347 | printf("%*s\n", result[i].length, result[i].ptr); |
universe@267 | 348 | } |
universe@267 | 349 | |
universe@267 | 350 | ucx_mempool_destroy(pool); |
universe@267 | 351 | ``` |
universe@267 | 352 | The output is: |
universe@267 | 353 | |
universe@267 | 354 | here |
universe@267 | 355 | are |
universe@267 | 356 | some |
universe@267 | 357 | strings |
universe@267 | 358 | |
universe@267 | 359 | The memory pool ensures, that all strings are freed. |
universe@267 | 360 | |
universe@259 | 361 | ## Testing |
universe@259 | 362 | |
universe@259 | 363 | *Header file:* [test.h](api/test_8h.html) |
universe@259 | 364 | *Required modules:* None. |
universe@259 | 365 | |
universe@259 | 366 | This module provides a testing framework which allows you to execute test cases |
universe@259 | 367 | within test suites. |
universe@259 | 368 | To avoid code duplication within tests, we also provide the possibility to |
universe@259 | 369 | define test subroutines. |
universe@259 | 370 | |
universe@259 | 371 | ## Utilities |
universe@259 | 372 | |
universe@259 | 373 | *Header file:* [utils.h](api/utils_8h.html) |
universe@259 | 374 | *Required modules:* [Allocator](#allocator), [String](#string) |
universe@259 | 375 | |
universe@259 | 376 | In this module we provide very general utility function for copy and compare |
universe@259 | 377 | operations. |
universe@259 | 378 | We also provide several `printf` variants to conveniently print formatted data |
universe@259 | 379 | to streams or strings. |
universe@259 | 380 | |
universe@279 | 381 | ### A simple copy program |
universe@279 | 382 | |
universe@279 | 383 | The utilities package provides several stream copy functions. |
universe@279 | 384 | One of them has a very simple interface and can, for instance, be used to copy |
universe@279 | 385 | whole files in a single call. |
universe@279 | 386 | This is a minimal working example: |
universe@279 | 387 | ```C |
universe@279 | 388 | #include <stdio.h> |
universe@279 | 389 | #include <ucx/utils.h> |
universe@279 | 390 | |
universe@279 | 391 | int main(int argc, char** argv) { |
universe@279 | 392 | |
universe@279 | 393 | if (argc != 3) { |
universe@279 | 394 | fprintf(stderr, "Use %s <src> <dest>", argv[0]); |
universe@279 | 395 | return 1; |
universe@279 | 396 | } |
universe@279 | 397 | |
universe@279 | 398 | FILE *srcf = fopen(argv[1], "r"); // insert error handling on your own |
universe@279 | 399 | FILE *destf = fopen(argv[2], "w"); |
universe@279 | 400 | |
universe@279 | 401 | size_t n = ucx_stream_copy(srcf, destf, fread, fwrite); |
universe@279 | 402 | printf("%zu bytes copied.\n", n); |
universe@279 | 403 | |
universe@279 | 404 | fclose(srcf); |
universe@279 | 405 | fclose(destf); |
universe@279 | 406 | |
universe@279 | 407 | |
universe@279 | 408 | return 0; |
universe@279 | 409 | } |
universe@279 | 410 | ``` |
universe@279 | 411 | |
universe@281 | 412 | ### Automatic allocation for formatted strings |
universe@279 | 413 | |
universe@281 | 414 | The UCX utility function `ucx_asprintf()` and it's convenient shortcut |
universe@281 | 415 | `ucx_sprintf` allow easy formatting of strings, without ever having to worry |
universe@281 | 416 | about the required space. |
universe@281 | 417 | ```C |
universe@281 | 418 | sstr_t mystring = ucx_sprintf("The answer is: %d!", 42); |
universe@281 | 419 | ``` |
universe@281 | 420 | Still, you have to pass `mystring.ptr` to `free()` (or the free function of |
universe@281 | 421 | your allocator, if you use `ucx_asprintf`). |
universe@281 | 422 | If you don't have all the information ready to build your string, you can even |
universe@281 | 423 | use a [UcxBuffer](#buffer) as a target with the utility function |
universe@281 | 424 | `ucx_bprintf()`. |
universe@281 | 425 | ```C |
universe@281 | 426 | UcxBuffer* strbuffer = ucx_buffer_new(NULL, 512, UCX_BUFFER_AUTOEXTEND); |
universe@281 | 427 | |
universe@281 | 428 | for (unsigned int i = 2 ; i < 100 ; i++) { |
universe@281 | 429 | ucx_bprintf(strbuffer, "Integer %d is %s\n", |
universe@281 | 430 | i, prime(i) ? "prime" : "not prime"); |
universe@281 | 431 | } |
universe@281 | 432 | |
universe@281 | 433 | // print the result to stdout |
universe@281 | 434 | printf("%s", (char*)strbuffer->space); |
universe@281 | 435 | |
universe@281 | 436 | ucx_buffer_free(strbuffer); |
universe@281 | 437 | ``` |