universe@264: --- universe@264: title: Modules universe@264: --- universe@259: universe@259: UCX provides several modules for data structures and algorithms. universe@259: You may choose to use specific modules by inclueding the corresponding header universe@259: file. universe@259: Please note, that some modules make use of other UCX modules. universe@259: For instance, the [Allocator](#allocator) module is used by many other modules universe@259: to allow flexible memory allocation. universe@259: By default the header files are placed into an `ucx` directory within your universe@282: systems include directory. In this case you can use a module by including it universe@259: via `#include `. universe@259: Required modules are included automatically. universe@259: universe@267:
universe@267: universe@280: ----------------------- ---------------------- ---------------------------- ------------------------- universe@280: [Allocator](#allocator) [AVL Tree](#avl-tree) [Buffer](#buffer) [List](#list) universe@280: [Logging](#logging) [Map](#map) [Memory Pool](#memory-pool) [Properties](#properties) universe@280: [Stack](#stack) [String](#string) [Testing](#testing) [Utilities](#utilities) universe@280: ----------------------- ---------------------- ---------------------------- ------------------------- universe@267: universe@267:
universe@267: universe@259: ## Allocator universe@259: universe@259: *Header file:* [allocator.h](api/allocator_8h.html) universe@259: *Required modules:* None. universe@259: universe@259: A UCX allocator consists of a pointer to the memory area / pool and four universe@259: function pointers to memory management functions operating on this memory universe@259: area / pool. These functions shall behave equivalent to the standard libc universe@259: functions `malloc`, `calloc`, `realloc` and `free`. universe@259: universe@259: The signature of the memory management functions is based on the signature universe@259: of the respective libc function but each of them takes the pointer to the universe@259: memory area / pool as first argument. universe@259: universe@259: As the pointer to the memory area / pool can be arbitrarily chosen, any data universe@259: can be provided to the memory management functions. One example is the universe@280: [UCX Memory Pool](#memory-pool). universe@259: universe@259: ## AVL Tree universe@259: universe@259: *Header file:* [avl.h](api/avl_8h.html) universe@259: *Required modules:* [Allocator](#allocator) universe@259: universe@259: This binary search tree implementation allows average O(1) insertion and universe@259: removal of elements (excluding binary search time). universe@259: All common binary tree operations are implemented. Furthermore, this module universe@259: provides search functions via lower and upper bounds. universe@259: universe@287: ### Filtering items with a time window universe@287: universe@287: Suppose you have a list of items which contain a `time_t` value and your task universe@287: is to find all items within a time window `[t_start, t_end]`. universe@287: With AVL Trees this is easy: universe@287: ```C universe@287: /* --------------------- universe@287: * Somewhere in a header universe@287: */ universe@287: typedef struct { universe@287: time_t ts; universe@294: /* other important data */ universe@287: } MyObject; universe@287: universe@287: /* ----------- universe@287: * Source code universe@287: */ universe@287: universe@287: UcxAVLTree* tree = ucx_avl_new(ucx_longintcmp); universe@294: /* ... populate tree with objects, use '& MyObject.ts' as key ... */ universe@287: universe@287: universe@294: /* Now find every item, with 30 <= ts <= 70 */ universe@287: time_t ts_start = 30; universe@287: time_t ts_end = 70; universe@287: universe@287: printf("Values in range:\n"); universe@287: for ( universe@287: UcxAVLNode* node = ucx_avl_find_node( universe@287: tree, (intptr_t) &ts_start, universe@287: ucx_longintdist, UCX_AVL_FIND_LOWER_BOUNDED); universe@287: node && (*(time_t*)node->key) <= ts_end; universe@287: node = ucx_avl_succ(node) universe@287: ) { universe@287: printf(" ts: %ld\n", ((MyObject*)node->value)->ts); universe@287: } universe@287: universe@287: ucx_avl_free_content(tree, free); universe@287: ucx_avl_free(tree); universe@287: ``` universe@287: universe@259: ## Buffer universe@259: universe@259: *Header file:* [buffer.h](api/buffer_8h.html) universe@259: *Required modules:* None. universe@259: universe@259: Instances of this buffer implementation can be used to read from or to write to universe@259: memory like you would do with a stream. This allows the use of universe@282: `ucx_stream_copy()` from the [Utilities](#utilities) module to copy contents universe@282: from one buffer to another or from file or network streams to the buffer and universe@259: vice-versa. universe@259: universe@259: More features for convenient use of the buffer can be enabled, like automatic universe@259: memory management and automatic resizing of the buffer space. universe@259: See the documentation of the macro constants in the header file for more universe@259: information. universe@259: universe@290: ### Add line numbers to a file universe@290: universe@290: When reading a file line by line, you have three options: first, you could limit universe@290: the maximum supported line length. universe@290: Second, you allocate a god buffer large universe@290: enough for the most lines a text file could have. universe@290: And third, undoubtedly the best option, you start with a small buffer, which universe@290: adjusts on demand. universe@290: An `UcxBuffer` can be created to do just that for you. universe@290: Just pass the `UCX_BUFFER_AUTOEXTEND` option to the initialization function. universe@290: Here is a full working program, which adds line numbers to a file. universe@290: ```C universe@290: #include universe@290: #include universe@290: #include universe@290: universe@290: int main(int argc, char** argv) { universe@290: universe@290: if (argc != 2) { universe@290: fprintf(stderr, "Usage: %s \n", argv[0]); universe@290: return 1; universe@290: } universe@290: universe@290: FILE* input = fopen(argv[1], "r"); universe@290: if (!input) { universe@290: perror("Canno read input"); universe@290: return 1; universe@290: } universe@290: universe@290: const size_t chunksize = 256; universe@290: universe@290: UcxBuffer* linebuf = universe@290: ucx_buffer_new( universe@294: NULL, /* the buffer should manage the memory area for us */ universe@294: 2*chunksize, /* initial size should be twice the chunk size */ universe@294: UCX_BUFFER_AUTOEXTEND); /* the buffer will grow when necessary */ universe@290: universe@290: size_t lineno = 1; universe@290: do { universe@294: /* read line chunk */ universe@290: size_t read = ucx_stream_ncopy( universe@290: input, linebuf, fread, ucx_buffer_write, chunksize); universe@290: if (read == 0) break; universe@290: universe@294: /* handle line endings */ universe@290: do { universe@290: sstr_t bufstr = ucx_buffer_to_sstr(linebuf); universe@290: sstr_t nl = sstrchr(bufstr, '\n'); universe@290: if (nl.length == 0) break; universe@290: universe@290: size_t linelen = bufstr.length - nl.length; universe@290: sstr_t linestr = sstrsubsl(bufstr, 0, linelen); universe@290: universe@290: printf("%zu: %" PRIsstr "\n", lineno++, SFMT(linestr)); universe@290: universe@294: /* shift the buffer to the next line */ universe@290: ucx_buffer_shift_left(linebuf, linelen+1); universe@290: } while(1); universe@290: universe@290: } while(1); universe@290: universe@294: /* print the 'noeol' line, if any */ universe@290: sstr_t lastline = ucx_buffer_to_sstr(linebuf); universe@290: if (lastline.length > 0) { universe@290: printf("%zu: %" PRIsstr, lineno, SFMT(lastline)); universe@290: } universe@290: universe@290: fclose(input); universe@290: ucx_buffer_free(linebuf); universe@290: universe@290: return 0; universe@290: } universe@290: ``` universe@290: universe@259: ## List universe@259: universe@259: *Header file:* [list.h](api/list_8h.html) universe@259: *Required modules:* [Allocator](#allocator) universe@259: universe@259: This module provides the data structure and several functions for a doubly universe@259: linked list. Among the common operations like insert, remove, search and sort, universe@259: we allow convenient iteration via a special `UCX_FOREACH` macro. universe@259: universe@294: ### Remove duplicates from an array of strings universe@294: universe@294: Assume you are given an array of `sstr_t` and want to create a list of these universe@294: strings without duplicates. universe@294: ```C universe@294: #include universe@294: #include universe@294: #include universe@294: #include universe@294: universe@294: UcxList* remove_duplicates(sstr_t* array, size_t arrlen) { universe@294: UcxList* list = NULL; universe@294: for (size_t i = 0 ; i < arrlen ; ++i) { universe@294: if (ucx_list_find(list, array+i, ucx_sstrcmp, NULL) == -1) { universe@294: sstr_t* s = malloc(sizeof(sstr_t)); universe@294: *s = sstrdup(array[i]); universe@294: list = ucx_list_append(list, s); universe@294: } universe@294: } universe@294: return list; universe@294: } universe@294: universe@294: /* we will need this function to clean up the list contents later */ universe@294: void free_sstr(void* ptr) { universe@294: sstr_t* s = ptr; universe@294: free(s->ptr); universe@294: free(s); universe@294: } universe@294: universe@294: /* ... */ universe@294: universe@294: sstr_t* array = /* some array of strings */ universe@294: size_t arrlen = /* the length of the array */ universe@294: universe@294: UcxList* list = remove_duplicates(array,arrlen); universe@294: universe@294: /* Iterate over the list and print the elements */ universe@294: UCX_FOREACH(elem, list) { universe@294: sstr_t s = *((sstr_t*)elem->data); universe@294: printf("%" PRIsstr "\n", SFMT(s)); universe@294: } universe@294: universe@294: /* Use our free function to free the duplicated strings. */ universe@294: ucx_list_free_content(list, free_sstr); universe@294: ucx_list_free(list); universe@294: ``` universe@294: universe@259: ## Logging universe@259: universe@259: *Header file:* [logging.h](api/logging_8h.html) universe@259: *Required modules:* [Map](#map), [String](#string) universe@259: universe@259: The logging module comes with some predefined log levels and allows some more universe@259: customization. You may choose if you want to get timestamps or source file and universe@259: line number logged automatically when outputting a message. universe@295: The following function call initializes a debug logger with all of the above universe@295: information: universe@295: ```C universe@295: log = ucx_logger_new(stdout, UCX_LOGGER_DEBUG, universe@295: UCX_LOGGER_LEVEL | UCX_LOGGER_TIMESTAMP | UCX_LOGGER_SOURCE); universe@295: ``` universe@295: Afterwards you can use this logger with the predefined macros universe@295: ```C universe@295: ucx_logger_trace(log, "Verbose output"); universe@295: ucx_logger_debug(log, "Debug message"); universe@295: ucx_logger_info(log, "Information"); universe@295: ucx_logger_warn(log, "Warning"); universe@295: ucx_logger_error(log, "Error message"); universe@295: ``` universe@295: or you use universe@295: ```C universe@295: ucx_logger_log(log, CUSTOM_LEVEL, "Some message") universe@295: ``` universe@295: When you use your custom log level, don't forget to register it with universe@295: ```C universe@295: ucx_logger_register_level(log, CUSTOM_LEVEL, "CUSTOM") universe@295: ``` universe@295: where the last argument must be a string literal. universe@259: universe@259: ## Map universe@259: universe@259: *Header file:* [map.h](api/map_8h.html) universe@259: *Required modules:* [Allocator](#allocator), [String](#string) universe@259: universe@259: This module provides a hash map implementation using murmur hash 2 and separate universe@259: chaining with linked lists. Similarly to the list module, we provide a universe@259: `UCX_MAP_FOREACH` macro to conveniently iterate through the key/value pairs. universe@259: universe@298: ### Parsing command line options universe@298: universe@298: Assume you want to parse command line options and record them within a map. universe@298: One way to do this is shown by the following code sample: universe@298: ```C universe@298: UcxMap* options = ucx_map_new(16); universe@298: const char *NOARG = ""; universe@298: universe@298: char *option = NULL; universe@298: char optchar = 0; universe@298: for(int i=1;i 1 && arg[0] == '-') { universe@298: if(option) { universe@298: fprintf(stderr, universe@298: "Missing argument for option -%c\n", optchar); universe@298: return 1; universe@298: } universe@298: for(int c=1;callocator, test, delim, &count); universe@267: for (ssize_t i = 0 ; i < count ; i++) { universe@267: /* don't forget to specify the length via the %*s format specifier */ universe@267: printf("%*s\n", result[i].length, result[i].ptr); universe@267: } universe@267: universe@267: ucx_mempool_destroy(pool); universe@267: ``` universe@267: The output is: universe@267: universe@267: here universe@267: are universe@267: some universe@267: strings universe@267: universe@267: The memory pool ensures, that all strings are freed. universe@267: universe@259: ## Testing universe@259: universe@259: *Header file:* [test.h](api/test_8h.html) universe@259: *Required modules:* None. universe@259: universe@259: This module provides a testing framework which allows you to execute test cases universe@259: within test suites. universe@259: To avoid code duplication within tests, we also provide the possibility to universe@259: define test subroutines. universe@259: universe@297: You should declare test cases and subroutines in a header file per test unit universe@297: and implement them as you would implement normal functions. universe@297: ```C universe@297: /* myunit.h */ universe@297: UCX_TEST(function_name); universe@297: UCX_TEST_SUBROUTINE(subroutine_name, paramlist); /* optional */ universe@297: universe@297: universe@297: /* myunit.c */ universe@297: UCX_TEST_SUBROUTINE(subroutine_name, paramlist) { universe@297: /* ... reusable tests with UCX_TEST_ASSERT() ... */ universe@297: } universe@297: universe@297: UCX_TEST(function_name) { universe@297: /* ... resource allocation and other test preparation ... */ universe@297: universe@297: /* mandatory marker for the start of the tests */ universe@297: UCX_TEST_BEGIN universe@297: universe@297: /* ... verifications with UCX_TEST_ASSERT() ... universe@297: * (and/or calls with UCX_TEST_CALL_SUBROUTINE()) universe@297: */ universe@297: universe@297: /* mandatory marker for the end of the tests */ universe@297: UCX_TEST_END universe@297: universe@297: /* ... resource cleanup ... universe@297: * (all code after UCX_TEST_END is always executed) universe@297: */ universe@297: } universe@297: ``` universe@297: If you want to use the `UCX_TEST_ASSERT()` macro in a function, you are universe@297: *required* to use a `UCX_TEST_SUBROUTINE`. universe@297: Otherwise the testing framework does not know where to jump, when the assertion universe@297: fails. universe@297: universe@297: After implementing the tests, you can easily build a test suite and execute it: universe@297: ```C universe@297: UcxTestSuite* suite = ucx_test_suite_new(); universe@297: ucx_test_register(suite, testMyTestCase01); universe@297: ucx_test_register(suite, testMyTestCase02); universe@297: /* ... */ universe@297: ucx_test_run(suite, stdout); /* stdout, or any other FILE stream */ universe@297: ``` universe@297: universe@259: ## Utilities universe@259: universe@259: *Header file:* [utils.h](api/utils_8h.html) universe@259: *Required modules:* [Allocator](#allocator), [String](#string) universe@259: universe@259: In this module we provide very general utility function for copy and compare universe@259: operations. universe@259: We also provide several `printf` variants to conveniently print formatted data universe@259: to streams or strings. universe@259: universe@279: ### A simple copy program universe@279: universe@279: The utilities package provides several stream copy functions. universe@279: One of them has a very simple interface and can, for instance, be used to copy universe@279: whole files in a single call. universe@279: This is a minimal working example: universe@279: ```C universe@279: #include universe@279: #include universe@279: universe@279: int main(int argc, char** argv) { universe@279: universe@279: if (argc != 3) { universe@279: fprintf(stderr, "Use %s ", argv[0]); universe@279: return 1; universe@279: } universe@279: universe@294: FILE *srcf = fopen(argv[1], "r"); /* insert error handling on your own */ universe@279: FILE *destf = fopen(argv[2], "w"); universe@279: universe@279: size_t n = ucx_stream_copy(srcf, destf, fread, fwrite); universe@279: printf("%zu bytes copied.\n", n); universe@279: universe@279: fclose(srcf); universe@279: fclose(destf); universe@279: universe@279: universe@279: return 0; universe@279: } universe@279: ``` universe@279: universe@281: ### Automatic allocation for formatted strings universe@279: universe@281: The UCX utility function `ucx_asprintf()` and it's convenient shortcut universe@281: `ucx_sprintf` allow easy formatting of strings, without ever having to worry universe@281: about the required space. universe@281: ```C universe@281: sstr_t mystring = ucx_sprintf("The answer is: %d!", 42); universe@281: ``` universe@281: Still, you have to pass `mystring.ptr` to `free()` (or the free function of universe@281: your allocator, if you use `ucx_asprintf`). universe@281: If you don't have all the information ready to build your string, you can even universe@281: use a [UcxBuffer](#buffer) as a target with the utility function universe@281: `ucx_bprintf()`. universe@281: ```C universe@281: UcxBuffer* strbuffer = ucx_buffer_new(NULL, 512, UCX_BUFFER_AUTOEXTEND); universe@281: universe@281: for (unsigned int i = 2 ; i < 100 ; i++) { universe@281: ucx_bprintf(strbuffer, "Integer %d is %s\n", universe@281: i, prime(i) ? "prime" : "not prime"); universe@281: } universe@281: universe@294: /* print the result to stdout */ universe@281: printf("%s", (char*)strbuffer->space); universe@281: universe@281: ucx_buffer_free(strbuffer); universe@281: ```