Thu, 03 May 2018 10:44:33 +0200
adds ucx_avl_free_content() function and documentation in modules.md
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 ## List
113 *Header file:* [list.h](api/list_8h.html)
114 *Required modules:* [Allocator](#allocator)
116 This module provides the data structure and several functions for a doubly
117 linked list. Among the common operations like insert, remove, search and sort,
118 we allow convenient iteration via a special `UCX_FOREACH` macro.
120 ## Logging
122 *Header file:* [logging.h](api/logging_8h.html)
123 *Required modules:* [Map](#map), [String](#string)
125 The logging module comes with some predefined log levels and allows some more
126 customization. You may choose if you want to get timestamps or source file and
127 line number logged automatically when outputting a message.
130 ## Map
132 *Header file:* [map.h](api/map_8h.html)
133 *Required modules:* [Allocator](#allocator), [String](#string)
135 This module provides a hash map implementation using murmur hash 2 and separate
136 chaining with linked lists. Similarly to the list module, we provide a
137 `UCX_MAP_FOREACH` macro to conveniently iterate through the key/value pairs.
139 ## Memory Pool
141 *Header file:* [mempool.h](api/mempool_8h.html)
142 *Required modules:* [Allocator](#allocator)
144 Here we have a concrete allocator implementation in the sense of a memory pool.
145 This pool allows you to register destructor functions for the allocated memory,
146 which are automatically called on the destruction of the pool.
147 But you may also register *independent* destructor functions within a pool in
148 case, some external library allocated memory for you, which you wish to be
149 destroyed together with this pool.
151 ## Properties
153 *Header file:* [properties.h](api/properties_8h.html)
154 *Required modules:* [Map](#map)
156 This module provides load and store function for `*.properties` files.
157 The key/value pairs are stored within an UCX Map.
159 ### Example: Loading properties from a file
161 ```C
162 // Open the file as usual
163 FILE* file = fopen("myprops.properties", "r");
164 if (!file) {
165 // error handling
166 return 1;
167 }
169 // Load the properties from the file
170 UcxMap* myprops = ucx_map_new(16);
171 if (ucx_properties_load(myprops, file)) {
172 // error handling
173 fclose(file);
174 ucx_map_free(myprops);
175 return 1;
176 }
178 // Print out the key/value pairs
179 char* propval;
180 UcxMapIterator propiter = ucx_map_iterator(myprops);
181 UCX_MAP_FOREACH(key, propval, propiter) {
182 printf("%s = %s\n", (char*)key.data, propval);
183 }
185 // Don't forget to free the values before freeing the map
186 ucx_map_free_content(myprops, NULL);
187 ucx_map_free(myprops);
188 fclose(file);
189 ```
190 ## Stack
192 *Header file:* [stack.h](api/stack_8h.html)
193 *Required modules:* [Allocator](#allocator)
195 This concrete implementation of an UCX Allocator allows you to grab some amount
196 of memory which is then handled as a stack.
197 Please note, that the term *stack* only refers to the behavior of this
198 allocator. You may still choose if you want to use stack or heap memory
199 for the underlying space.
201 A typical use case is an algorithm where you need to allocate and free large
202 amounts of memory very frequently.
204 ## String
206 *Header file:* [string.h](api/string_8h.html)
207 *Required modules:* [Allocator](#allocator)
209 This module provides a safe implementation of bounded string.
210 Usually C strings do not carry a length. While for zero-terminated strings you
211 can easily get the length with `strlen`, this is not generally possible for
212 arbitrary strings.
213 The `sstr_t` type of this module always carries the string and its length to
214 reduce the risk of buffer overflows dramatically.
216 ### Initialization
218 There are several ways to create an `sstr_t`:
220 ```C
221 /* (1) sstr() uses strlen() internally, hence cstr MUST be zero-terminated */
222 sstr_t a = sstr(cstr);
224 /* (2) cstr does not need to be zero-terminated, if length is specified */
225 sstr_t b = sstrn(cstr, len);
227 /* (3) S() macro creates sstr_t from a string using sizeof() and using sstrn().
228 This version is especially useful for function arguments */
229 sstr_t c = S("hello");
231 /* (4) ST() macro creates sstr_t struct literal using sizeof() */
232 sstr_t d = ST("hello");
233 ```
235 You should not use the `S()` or `ST()` macro with string of unknown origin,
236 since the `sizeof()` call might not coincide with the string length in those
237 cases. If you know what you are doing, it can save you some performance,
238 because you do not need the `strlen()` call.
240 ### Finding the position of a substring
242 The `sstrstr()` function gives you a new `sstr_t` object starting with the
243 requested substring. Thus determining the position comes down to a simple
244 subtraction.
246 ```C
247 sstr_t haystack = ST("Here we go!");
248 sstr_t needle = ST("we");
249 sstr_t result = sstrstr(haystack, needle);
250 if (result.ptr)
251 printf("Found at position %zd.\n", haystack.length-result.length);
252 else
253 printf("Not found.\n");
254 ```
256 ### Spliting a string by a delimiter
258 The `sstrsplit()` function (and its allocator based version `sstrsplit_a()`) is
259 very powerful and might look a bit nasty at a first glance. But it is indeed
260 very simple to use. It is even more convenient in combination with a memory
261 pool.
263 ```C
264 sstr_t test = ST("here::are::some::strings");
265 sstr_t delim = ST("::");
267 ssize_t count = 0; /* no limit */
268 UcxMempool* pool = ucx_mempool_new_default();
270 sstr_t* result = sstrsplit_a(pool->allocator, test, delim, &count);
271 for (ssize_t i = 0 ; i < count ; i++) {
272 /* don't forget to specify the length via the %*s format specifier */
273 printf("%*s\n", result[i].length, result[i].ptr);
274 }
276 ucx_mempool_destroy(pool);
277 ```
278 The output is:
280 here
281 are
282 some
283 strings
285 The memory pool ensures, that all strings are freed.
287 ## Testing
289 *Header file:* [test.h](api/test_8h.html)
290 *Required modules:* None.
292 This module provides a testing framework which allows you to execute test cases
293 within test suites.
294 To avoid code duplication within tests, we also provide the possibility to
295 define test subroutines.
297 ## Utilities
299 *Header file:* [utils.h](api/utils_8h.html)
300 *Required modules:* [Allocator](#allocator), [String](#string)
302 In this module we provide very general utility function for copy and compare
303 operations.
304 We also provide several `printf` variants to conveniently print formatted data
305 to streams or strings.
307 ### A simple copy program
309 The utilities package provides several stream copy functions.
310 One of them has a very simple interface and can, for instance, be used to copy
311 whole files in a single call.
312 This is a minimal working example:
313 ```C
314 #include <stdio.h>
315 #include <ucx/utils.h>
317 int main(int argc, char** argv) {
319 if (argc != 3) {
320 fprintf(stderr, "Use %s <src> <dest>", argv[0]);
321 return 1;
322 }
324 FILE *srcf = fopen(argv[1], "r"); // insert error handling on your own
325 FILE *destf = fopen(argv[2], "w");
327 size_t n = ucx_stream_copy(srcf, destf, fread, fwrite);
328 printf("%zu bytes copied.\n", n);
330 fclose(srcf);
331 fclose(destf);
334 return 0;
335 }
336 ```
338 ### Automatic allocation for formatted strings
340 The UCX utility function `ucx_asprintf()` and it's convenient shortcut
341 `ucx_sprintf` allow easy formatting of strings, without ever having to worry
342 about the required space.
343 ```C
344 sstr_t mystring = ucx_sprintf("The answer is: %d!", 42);
345 ```
346 Still, you have to pass `mystring.ptr` to `free()` (or the free function of
347 your allocator, if you use `ucx_asprintf`).
348 If you don't have all the information ready to build your string, you can even
349 use a [UcxBuffer](#buffer) as a target with the utility function
350 `ucx_bprintf()`.
351 ```C
352 UcxBuffer* strbuffer = ucx_buffer_new(NULL, 512, UCX_BUFFER_AUTOEXTEND);
354 for (unsigned int i = 2 ; i < 100 ; i++) {
355 ucx_bprintf(strbuffer, "Integer %d is %s\n",
356 i, prime(i) ? "prime" : "not prime");
357 }
359 // print the result to stdout
360 printf("%s", (char*)strbuffer->space);
362 ucx_buffer_free(strbuffer);
363 ```