Sun, 13 May 2018 17:34:06 +0200
documentation for the UcxStack
1 ---
2 title: Modules
3 ---
5 UCX provides several modules for data structures and algorithms.
6 You may choose to use specific modules by inclueding the corresponding header
7 file.
8 Please note, that some modules make use of other UCX modules.
9 For instance, the [Allocator](#allocator) module is used by many other modules
10 to allow flexible memory allocation.
11 By default the header files are placed into an `ucx` directory within your
12 systems include directory. In this case you can use a module by including it
13 via `#include <ucx/MODULENAME.h>`.
14 Required modules are included automatically.
16 <div id="modules" align="center">
18 ----------------------- ---------------------- ---------------------------- -------------------------
19 [Allocator](#allocator) [AVL Tree](#avl-tree) [Buffer](#buffer) [List](#list)
20 [Logging](#logging) [Map](#map) [Memory Pool](#memory-pool) [Properties](#properties)
21 [Stack](#stack) [String](#string) [Testing](#testing) [Utilities](#utilities)
22 ----------------------- ---------------------- ---------------------------- -------------------------
24 </div>
26 ## Allocator
28 *Header file:* [allocator.h](api/allocator_8h.html)
29 *Required modules:* None.
31 A UCX allocator consists of a pointer to the memory area / pool and four
32 function pointers to memory management functions operating on this memory
33 area / pool. These functions shall behave equivalent to the standard libc
34 functions `malloc`, `calloc`, `realloc` and `free`.
36 The signature of the memory management functions is based on the signature
37 of the respective libc function but each of them takes the pointer to the
38 memory area / pool as first argument.
40 As the pointer to the memory area / pool can be arbitrarily chosen, any data
41 can be provided to the memory management functions. One example is the
42 [UCX Memory Pool](#memory-pool).
44 ## AVL Tree
46 *Header file:* [avl.h](api/avl_8h.html)
47 *Required modules:* [Allocator](#allocator)
49 This binary search tree implementation allows average O(1) insertion and
50 removal of elements (excluding binary search time).
51 All common binary tree operations are implemented. Furthermore, this module
52 provides search functions via lower and upper bounds.
54 ### Filtering items with a time window
56 Suppose you have a list of items which contain a `time_t` value and your task
57 is to find all items within a time window `[t_start, t_end]`.
58 With AVL Trees this is easy:
59 ```C
60 /* ---------------------
61 * Somewhere in a header
62 */
63 typedef struct {
64 time_t ts;
65 /* other important data */
66 } MyObject;
68 /* -----------
69 * Source code
70 */
72 UcxAVLTree* tree = ucx_avl_new(ucx_longintcmp);
73 /* ... populate tree with objects, use '& MyObject.ts' as key ... */
76 /* Now find every item, with 30 <= ts <= 70 */
77 time_t ts_start = 30;
78 time_t ts_end = 70;
80 printf("Values in range:\n");
81 for (
82 UcxAVLNode* node = ucx_avl_find_node(
83 tree, (intptr_t) &ts_start,
84 ucx_longintdist, UCX_AVL_FIND_LOWER_BOUNDED);
85 node && (*(time_t*)node->key) <= ts_end;
86 node = ucx_avl_succ(node)
87 ) {
88 printf(" ts: %ld\n", ((MyObject*)node->value)->ts);
89 }
91 ucx_avl_free_content(tree, free);
92 ucx_avl_free(tree);
93 ```
95 ## Buffer
97 *Header file:* [buffer.h](api/buffer_8h.html)
98 *Required modules:* None.
100 Instances of this buffer implementation can be used to read from or to write to
101 memory like you would do with a stream. This allows the use of
102 `ucx_stream_copy()` from the [Utilities](#utilities) module to copy contents
103 from one buffer to another or from file or network streams to the buffer and
104 vice-versa.
106 More features for convenient use of the buffer can be enabled, like automatic
107 memory management and automatic resizing of the buffer space.
108 See the documentation of the macro constants in the header file for more
109 information.
111 ### Add line numbers to a file
113 When reading a file line by line, you have three options: first, you could limit
114 the maximum supported line length.
115 Second, you allocate a god buffer large
116 enough for the most lines a text file could have.
117 And third, undoubtedly the best option, you start with a small buffer, which
118 adjusts on demand.
119 An `UcxBuffer` can be created to do just that for you.
120 Just pass the `UCX_BUFFER_AUTOEXTEND` option to the initialization function.
121 Here is a full working program, which adds line numbers to a file.
122 ```C
123 #include <stdio.h>
124 #include <ucx/buffer.h>
125 #include <ucx/utils.h>
127 int main(int argc, char** argv) {
129 if (argc != 2) {
130 fprintf(stderr, "Usage: %s <file>\n", argv[0]);
131 return 1;
132 }
134 FILE* input = fopen(argv[1], "r");
135 if (!input) {
136 perror("Canno read input");
137 return 1;
138 }
140 const size_t chunksize = 256;
142 UcxBuffer* linebuf =
143 ucx_buffer_new(
144 NULL, /* the buffer should manage the memory area for us */
145 2*chunksize, /* initial size should be twice the chunk size */
146 UCX_BUFFER_AUTOEXTEND); /* the buffer will grow when necessary */
148 size_t lineno = 1;
149 do {
150 /* read line chunk */
151 size_t read = ucx_stream_ncopy(
152 input, linebuf, fread, ucx_buffer_write, chunksize);
153 if (read == 0) break;
155 /* handle line endings */
156 do {
157 sstr_t bufstr = ucx_buffer_to_sstr(linebuf);
158 sstr_t nl = sstrchr(bufstr, '\n');
159 if (nl.length == 0) break;
161 size_t linelen = bufstr.length - nl.length;
162 sstr_t linestr = sstrsubsl(bufstr, 0, linelen);
164 printf("%zu: %" PRIsstr "\n", lineno++, SFMT(linestr));
166 /* shift the buffer to the next line */
167 ucx_buffer_shift_left(linebuf, linelen+1);
168 } while(1);
170 } while(1);
172 /* print the 'noeol' line, if any */
173 sstr_t lastline = ucx_buffer_to_sstr(linebuf);
174 if (lastline.length > 0) {
175 printf("%zu: %" PRIsstr, lineno, SFMT(lastline));
176 }
178 fclose(input);
179 ucx_buffer_free(linebuf);
181 return 0;
182 }
183 ```
185 ## List
187 *Header file:* [list.h](api/list_8h.html)
188 *Required modules:* [Allocator](#allocator)
190 This module provides the data structure and several functions for a doubly
191 linked list. Among the common operations like insert, remove, search and sort,
192 we allow convenient iteration via a special `UCX_FOREACH` macro.
194 ### Remove duplicates from an array of strings
196 Assume you are given an array of `sstr_t` and want to create a list of these
197 strings without duplicates.
198 ```C
199 #include <stdio.h>
200 #include <ucx/list.h>
201 #include <ucx/string.h>
202 #include <ucx/utils.h>
204 UcxList* remove_duplicates(sstr_t* array, size_t arrlen) {
205 UcxList* list = NULL;
206 for (size_t i = 0 ; i < arrlen ; ++i) {
207 if (ucx_list_find(list, array+i, ucx_sstrcmp, NULL) == -1) {
208 sstr_t* s = malloc(sizeof(sstr_t));
209 *s = sstrdup(array[i]);
210 list = ucx_list_append(list, s);
211 }
212 }
213 return list;
214 }
216 /* we will need this function to clean up the list contents later */
217 void free_sstr(void* ptr) {
218 sstr_t* s = ptr;
219 free(s->ptr);
220 free(s);
221 }
223 /* ... */
225 sstr_t* array = /* some array of strings */
226 size_t arrlen = /* the length of the array */
228 UcxList* list = remove_duplicates(array,arrlen);
230 /* Iterate over the list and print the elements */
231 UCX_FOREACH(elem, list) {
232 sstr_t s = *((sstr_t*)elem->data);
233 printf("%" PRIsstr "\n", SFMT(s));
234 }
236 /* Use our free function to free the duplicated strings. */
237 ucx_list_free_content(list, free_sstr);
238 ucx_list_free(list);
239 ```
241 ## Logging
243 *Header file:* [logging.h](api/logging_8h.html)
244 *Required modules:* [Map](#map), [String](#string)
246 The logging module comes with some predefined log levels and allows some more
247 customization. You may choose if you want to get timestamps or source file and
248 line number logged automatically when outputting a message.
249 The following function call initializes a debug logger with all of the above
250 information:
251 ```C
252 log = ucx_logger_new(stdout, UCX_LOGGER_DEBUG,
253 UCX_LOGGER_LEVEL | UCX_LOGGER_TIMESTAMP | UCX_LOGGER_SOURCE);
254 ```
255 Afterwards you can use this logger with the predefined macros
256 ```C
257 ucx_logger_trace(log, "Verbose output");
258 ucx_logger_debug(log, "Debug message");
259 ucx_logger_info(log, "Information");
260 ucx_logger_warn(log, "Warning");
261 ucx_logger_error(log, "Error message");
262 ```
263 or you use
264 ```C
265 ucx_logger_log(log, CUSTOM_LEVEL, "Some message")
266 ```
267 When you use your custom log level, don't forget to register it with
268 ```C
269 ucx_logger_register_level(log, CUSTOM_LEVEL, "CUSTOM")
270 ```
271 where the last argument must be a string literal.
273 ## Map
275 *Header file:* [map.h](api/map_8h.html)
276 *Required modules:* [Allocator](#allocator), [String](#string)
278 This module provides a hash map implementation using murmur hash 2 and separate
279 chaining with linked lists. Similarly to the list module, we provide a
280 `UCX_MAP_FOREACH` macro to conveniently iterate through the key/value pairs.
282 ### Parsing command line options
284 Assume you want to parse command line options and record them within a map.
285 One way to do this is shown by the following code sample:
286 ```C
287 UcxMap* options = ucx_map_new(16);
288 const char *NOARG = "";
290 char *option = NULL;
291 char optchar = 0;
292 for(int i=1;i<argc;i++) {
293 char *arg = argv[i];
294 size_t len = strlen(arg);
295 if(len > 1 && arg[0] == '-') {
296 for(int c=1;c<len;c++) {
297 if(option) {
298 fprintf(stderr,
299 "Missing argument for option -%c\n", optchar);
300 return 1;
301 }
302 switch(arg[c]) {
303 default: {
304 fprintf(stderr, "Unknown option -%c\n\n", arg[c]);
305 return 1;
306 }
307 case 'v': {
308 ucx_map_cstr_put(options, "verbose", NOARG);
309 break;
310 }
311 case 'o': {
312 option = "output";
313 optchar = 'o';
314 break;
315 }
316 }
317 }
318 } else if(option) {
319 ucx_map_cstr_put(options, option, arg);
320 option = NULL;
321 } else {
322 /* ... handle argument that is not an option ... */
323 }
324 }
325 if(option) {
326 fprintf(stderr,
327 "Missing argument for option -%c\n", optchar);
328 return 1;
329 }
330 ```
331 With the following loop, you can access the previously recorded options:
332 ```C
333 UcxMapIterator iter = ucx_map_iterator(options);
334 char *arg;
335 UCX_MAP_FOREACH(optkey, arg, iter) {
336 char* opt = optkey.data;
337 if (*arg) {
338 printf("%s = %s\n", opt, arg);
339 } else {
340 printf("%s active\n", opt);
341 }
342 }
343 ```
344 Don't forget to call `ucx_map_free()`, when you are done with the map.
346 ## Memory Pool
348 *Header file:* [mempool.h](api/mempool_8h.html)
349 *Required modules:* [Allocator](#allocator)
351 Here we have a concrete allocator implementation in the sense of a memory pool.
352 This pool allows you to register destructor functions for the allocated memory,
353 which are automatically called on the destruction of the pool.
354 But you may also register *independent* destructor functions within a pool in
355 case, some external library allocated memory for you, which you wish to be
356 destroyed together with this pool.
358 ## Properties
360 *Header file:* [properties.h](api/properties_8h.html)
361 *Required modules:* [Map](#map)
363 This module provides load and store function for `*.properties` files.
364 The key/value pairs are stored within an UCX Map.
366 ### Example: Loading properties from a file
368 ```C
369 /* Open the file as usual */
370 FILE* file = fopen("myprops.properties", "r");
371 if (!file) {
372 // error handling
373 return 1;
374 }
376 /* Load the properties from the file */
377 UcxMap* myprops = ucx_map_new(16);
378 if (ucx_properties_load(myprops, file)) {
379 /* ... error handling ... */
380 fclose(file);
381 ucx_map_free(myprops);
382 return 1;
383 }
385 /* Print out the key/value pairs */
386 char* propval;
387 UcxMapIterator propiter = ucx_map_iterator(myprops);
388 UCX_MAP_FOREACH(key, propval, propiter) {
389 printf("%s = %s\n", (char*)key.data, propval);
390 }
392 /* Don't forget to free the values before freeing the map */
393 ucx_map_free_content(myprops, NULL);
394 ucx_map_free(myprops);
395 fclose(file);
396 ```
398 ## Stack
400 *Header file:* [stack.h](api/stack_8h.html)
401 *Required modules:* [Allocator](#allocator)
403 This concrete implementation of an UCX Allocator allows you to grab some amount
404 of memory which is then handled as a stack.
405 Please note, that the term *stack* only refers to the behavior of this
406 allocator. You may still choose to use either stack or heap memory
407 for the underlying space.
408 A typical use case is an algorithm where you need to allocate and free large
409 amounts of memory very frequently.
411 The following code sample shows how to initialize a stack and push and pop
412 simple data.
413 ```C
414 const size_t len = 1024;
415 char space[len];
416 UcxStack stack;
417 ucx_stack_init(&stack, space, len);
419 int i = 42;
420 float f = 3.14f;
421 const char* str = "Hello!";
422 size_t strn = 7;
424 /* push the integer */
425 ucx_stack_push(&stack, sizeof(int), &i);
427 /* push the float and rember the address */
428 float* remember = ucx_stack_push(&stack, sizeof(float), &f);
430 /* push the string with zero terminator */
431 ucx_stack_push(&stack, strn, str);
433 /* if we forget, how big an element was, we can ask the stack */
434 printf("Length of string: %zu\n", ucx_stack_topsize(&stack)-1);
436 /* retrieve the string as sstr_t, without zero terminator! */
437 sstr_t s;
438 s.length = ucx_stack_topsize(&stack)-1;
439 s.ptr = malloc(s.length);
440 ucx_stack_popn(&stack, s.ptr, s.length);
441 printf("%" PRIsstr "\n", SFMT(s));
443 /* print the float directly from the stack and free it */
444 printf("Float: %f\n", *remember);
445 ucx_stack_free(&stack, remember);
447 /* the last element is the integer */
448 int j;
449 ucx_stack_pop(&stack, &j);
450 printf("Integer: %d\n", j);
451 ```
455 ## String
457 *Header file:* [string.h](api/string_8h.html)
458 *Required modules:* [Allocator](#allocator)
460 This module provides a safe implementation of bounded string.
461 Usually C strings do not carry a length. While for zero-terminated strings you
462 can easily get the length with `strlen`, this is not generally possible for
463 arbitrary strings.
464 The `sstr_t` type of this module always carries the string and its length to
465 reduce the risk of buffer overflows dramatically.
467 ### Initialization
469 There are several ways to create an `sstr_t`:
471 ```C
472 /* (1) sstr() uses strlen() internally, hence cstr MUST be zero-terminated */
473 sstr_t a = sstr(cstr);
475 /* (2) cstr does not need to be zero-terminated, if length is specified */
476 sstr_t b = sstrn(cstr, len);
478 /* (3) S() macro creates sstr_t from a string using sizeof() and using sstrn().
479 This version is especially useful for function arguments */
480 sstr_t c = S("hello");
482 /* (4) ST() macro creates sstr_t struct literal using sizeof() */
483 sstr_t d = ST("hello");
484 ```
486 You should not use the `S()` or `ST()` macro with string of unknown origin,
487 since the `sizeof()` call might not coincide with the string length in those
488 cases. If you know what you are doing, it can save you some performance,
489 because you do not need the `strlen()` call.
491 ### Finding the position of a substring
493 The `sstrstr()` function gives you a new `sstr_t` object starting with the
494 requested substring. Thus determining the position comes down to a simple
495 subtraction.
497 ```C
498 sstr_t haystack = ST("Here we go!");
499 sstr_t needle = ST("we");
500 sstr_t result = sstrstr(haystack, needle);
501 if (result.ptr)
502 printf("Found at position %zd.\n", haystack.length-result.length);
503 else
504 printf("Not found.\n");
505 ```
507 ### Spliting a string by a delimiter
509 The `sstrsplit()` function (and its allocator based version `sstrsplit_a()`) is
510 very powerful and might look a bit nasty at a first glance. But it is indeed
511 very simple to use. It is even more convenient in combination with a memory
512 pool.
514 ```C
515 sstr_t test = ST("here::are::some::strings");
516 sstr_t delim = ST("::");
518 ssize_t count = 0; /* no limit */
519 UcxMempool* pool = ucx_mempool_new_default();
521 sstr_t* result = sstrsplit_a(pool->allocator, test, delim, &count);
522 for (ssize_t i = 0 ; i < count ; i++) {
523 /* don't forget to specify the length via the %*s format specifier */
524 printf("%*s\n", result[i].length, result[i].ptr);
525 }
527 ucx_mempool_destroy(pool);
528 ```
529 The output is:
531 here
532 are
533 some
534 strings
536 The memory pool ensures, that all strings are freed.
538 ## Testing
540 *Header file:* [test.h](api/test_8h.html)
541 *Required modules:* None.
543 This module provides a testing framework which allows you to execute test cases
544 within test suites.
545 To avoid code duplication within tests, we also provide the possibility to
546 define test subroutines.
548 You should declare test cases and subroutines in a header file per test unit
549 and implement them as you would implement normal functions.
550 ```C
551 /* myunit.h */
552 UCX_TEST(function_name);
553 UCX_TEST_SUBROUTINE(subroutine_name, paramlist); /* optional */
556 /* myunit.c */
557 UCX_TEST_SUBROUTINE(subroutine_name, paramlist) {
558 /* ... reusable tests with UCX_TEST_ASSERT() ... */
559 }
561 UCX_TEST(function_name) {
562 /* ... resource allocation and other test preparation ... */
564 /* mandatory marker for the start of the tests */
565 UCX_TEST_BEGIN
567 /* ... verifications with UCX_TEST_ASSERT() ...
568 * (and/or calls with UCX_TEST_CALL_SUBROUTINE())
569 */
571 /* mandatory marker for the end of the tests */
572 UCX_TEST_END
574 /* ... resource cleanup ...
575 * (all code after UCX_TEST_END is always executed)
576 */
577 }
578 ```
579 If you want to use the `UCX_TEST_ASSERT()` macro in a function, you are
580 *required* to use a `UCX_TEST_SUBROUTINE`.
581 Otherwise the testing framework does not know where to jump, when the assertion
582 fails.
584 After implementing the tests, you can easily build a test suite and execute it:
585 ```C
586 UcxTestSuite* suite = ucx_test_suite_new();
587 ucx_test_register(suite, testMyTestCase01);
588 ucx_test_register(suite, testMyTestCase02);
589 /* ... */
590 ucx_test_run(suite, stdout); /* stdout, or any other FILE stream */
591 ```
593 ## Utilities
595 *Header file:* [utils.h](api/utils_8h.html)
596 *Required modules:* [Allocator](#allocator), [String](#string)
598 In this module we provide very general utility function for copy and compare
599 operations.
600 We also provide several `printf` variants to conveniently print formatted data
601 to streams or strings.
603 ### A simple copy program
605 The utilities package provides several stream copy functions.
606 One of them has a very simple interface and can, for instance, be used to copy
607 whole files in a single call.
608 This is a minimal working example:
609 ```C
610 #include <stdio.h>
611 #include <ucx/utils.h>
613 int main(int argc, char** argv) {
615 if (argc != 3) {
616 fprintf(stderr, "Use %s <src> <dest>", argv[0]);
617 return 1;
618 }
620 FILE *srcf = fopen(argv[1], "r"); /* insert error handling on your own */
621 FILE *destf = fopen(argv[2], "w");
623 size_t n = ucx_stream_copy(srcf, destf, fread, fwrite);
624 printf("%zu bytes copied.\n", n);
626 fclose(srcf);
627 fclose(destf);
630 return 0;
631 }
632 ```
634 ### Automatic allocation for formatted strings
636 The UCX utility function `ucx_asprintf()` and it's convenient shortcut
637 `ucx_sprintf` allow easy formatting of strings, without ever having to worry
638 about the required space.
639 ```C
640 sstr_t mystring = ucx_sprintf("The answer is: %d!", 42);
641 ```
642 Still, you have to pass `mystring.ptr` to `free()` (or the free function of
643 your allocator, if you use `ucx_asprintf`).
644 If you don't have all the information ready to build your string, you can even
645 use a [UcxBuffer](#buffer) as a target with the utility function
646 `ucx_bprintf()`.
647 ```C
648 UcxBuffer* strbuffer = ucx_buffer_new(NULL, 512, UCX_BUFFER_AUTOEXTEND);
650 for (unsigned int i = 2 ; i < 100 ; i++) {
651 ucx_bprintf(strbuffer, "Integer %d is %s\n",
652 i, prime(i) ? "prime" : "not prime");
653 }
655 /* print the result to stdout */
656 printf("%s", (char*)strbuffer->space);
658 ucx_buffer_free(strbuffer);
659 ```