universe@720: ---
universe@720: title: UCX Features
universe@720: ---
universe@720:
universe@720:
universe@720:
universe@720: ------------------------ ------------------------- ------------------- ---------------------------------
universe@720: [Allocator](#allocator) [String](#string) [Buffer](#buffer) [Memory Pool](#memory-pool)
universe@720: [Iterator](#iterator) [Collection](#collection) [List](#list) [Map](#map)
universe@720: [Utilities](#utilities)
universe@720: ------------------------ ------------------------- ------------------- ---------------------------------
universe@720:
universe@720:
universe@720:
universe@720: ## Allocator
universe@720:
universe@720: *Header file:* [allocator.h](api/allocator_8h.html)
universe@720:
universe@722: The UCX allocator provides an interface for implementing an own memory allocation mechanism.
universe@722: Various function in UCX provide an additional alternative signature that takes an allocator as
universe@722: argument. A default allocator implementation using the stdlib memory management functions is
universe@722: available via the global symbol `cxDefaultAllocator`.
universe@722:
universe@722: If you want to define your own allocator, you need to initialize the `CxAllocator` structure
universe@722: with a pointer to an allocator class (containing function pointers for the memory management
universe@722: functions) and an optional pointer to an arbitrary memory region that can be used to store
universe@722: state information for the allocator. An example is shown below:
universe@722:
universe@722: ```c
universe@722: struct my_allocator_state {
universe@722: size_t total;
universe@722: size_t avail;
universe@727: char mem[];
universe@722: };
universe@722:
universe@722: static cx_allocator_class my_allocator_class = {
universe@722: my_malloc_impl,
universe@722: my_realloc_impl, // all these functions are somewhere defined
universe@722: my_calloc_impl,
universe@722: my_free_impl
universe@722: };
universe@722:
universe@722: CxAllocator create_my_allocator(size_t n) {
universe@722: CxAllocator alloc;
universe@722: alloc.cl = &my_allocator_class;
universe@722: alloc.data = calloc(1, sizeof(struct my_allocator_state) + n);
universe@722: return alloc;
universe@722: }
universe@722: ```
universe@722:
universe@720: ## String
universe@720:
universe@720: *Header file:* [string.h](api/string_8h.html)
universe@720:
universe@723: UCX strings come in two variants: immutable (`cxstring`) and mutable (`cxmutstr`).
universe@723: The functions of UCX are designed to work with immutable strings by default but in situations where it is necessary,
universe@723: the API also provides alternative functions that work directly with mutable strings.
universe@723: Functions that change a string in-place are, of course, only accepting mutable strings.
universe@723:
universe@723: When you are using UCX functions, or defining your own functions, you are sometimes facing the "problem",
universe@723: that the function only accepts arguments of type `cxstring` but you only have a `cxmutstr` at hand.
universe@723: In this case you _should not_ introduce a wrapper function that accepts the `cxmutstr`,
universe@723: but instead you should use the `cx_strcast()` function to cast the argument to the correct type.
universe@723:
universe@723: In general, UCX strings are **not** necessarily zero-terminated. If a function guarantees to return zero-terminated
universe@723: string, it is explicitly mentioned in the documentation of the respective function.
universe@723: As a rule of thumb, you _should not_ pass the strings of a UCX string structure to another API without explicitly
universe@723: ensuring that the string is zero-terminated.
universe@723:
universe@720: ## Buffer
universe@720:
universe@724: *Header file:* [buffer.h](api/buffer_8h.html)
universe@724:
universe@724: Instances of this buffer implementation can be used to read from or write to memory like you would do with a stream.
universe@724: This allows the use of `cx_stream_copy()` (see [Utilities](#utilities)) to copy contents from one buffer to another,
universe@724: or from a file or network streams to the buffer and vice-versa.
universe@724:
universe@724: More features for convenient use of the buffer can be enabled, like automatic memory management and automatic
universe@724: resizing of the buffer space.
universe@724:
universe@724: Since UCX 3.0, the buffer also supports automatic flushing of contents to another stream (or buffer) as an alternative
universe@724: to automatically resizing the buffer space.
universe@724: Please refer to the API doc for the fields prefixed with `flush_` to learn more.
universe@720:
universe@720: ## Memory Pool
universe@720:
universe@725: *Header file:* [mempool.h](api/mempool_8h.html)
universe@720:
universe@729: A memory pool is providing an allocator implementation that automatically deallocates the memory upon its destruction.
universe@729: It also allows you to register destructor functions for the allocated memory, which are automatically called before
universe@729: the memory is deallocated.
universe@729: Additionally, you may also register _independent_ destructor functions within a pool in case some external library
universe@729: allocated memory for you, which should be destroyed together with this pool.
universe@729:
universe@729: Many UCX features support the use of an allocator.
universe@729: The [strings](#string), for instance, provide several functions suffixed with `_a` that allow specifying an allocator.
universe@729: You can use this to keep track of the memory occupied by dynamically allocated strings and cleanup everything with
universe@729: just a single call to `cxMempoolDestroy()`.
universe@729:
universe@729: The following code illustrates this on the example of reading a CSV file into memory.
universe@729: ```C
universe@729: #include
universe@729: #include
universe@729: #include
universe@729: #include
universe@729: #include
universe@729: #include
universe@729:
universe@729: typedef struct {
universe@729: cxstring column_a;
universe@729: cxstring column_b;
universe@729: cxstring column_c;
universe@729: } CSVData;
universe@729:
universe@729: int main(void) {
universe@729: CxMempool* pool = cxBasicMempoolCreate(128);
universe@729:
universe@729: FILE *f = fopen("test.csv", "r");
universe@729: if (!f) {
universe@729: perror("Cannot open file");
universe@729: return 1;
universe@729: }
universe@729: // close the file automatically at pool destruction
universe@729: cxMempoolRegister(pool, f, (cx_destructor_func) fclose);
universe@729:
universe@729: // create a buffer using the memory pool for destruction
universe@729: CxBuffer *content = cxBufferCreate(NULL, 256, pool->allocator, CX_BUFFER_AUTO_EXTEND);
universe@729:
universe@729: // read the file into the buffer and turn it into a string
universe@729: cx_stream_copy(f, content, (cx_read_func) fread, (cx_write_func) cxBufferWrite);
universe@745: fclose(f);
universe@729: cxstring contentstr = cx_strn(content->space, content->size);
universe@729:
universe@729: // split the string into lines - use the mempool for allocating the target array
universe@729: cxstring* lines;
universe@729: size_t lc = cx_strsplit_a(pool->allocator, contentstr,
universe@729: CX_STR("\n"), SIZE_MAX, &lines);
universe@729:
universe@729: // skip the header and parse the remaining data into a linked list
universe@729: // the nodes of the linked list shall also be allocated by the mempool
universe@729: CxList* datalist = cxLinkedListCreate(pool->allocator, NULL, sizeof(CSVData));
universe@729: for (size_t i = 1 ; i < lc ; i++) {
universe@729: if (lines[i].length == 0) continue;
universe@729: cxstring fields[3];
universe@729: size_t fc = cx_strsplit(lines[i], CX_STR(";"), 3, fields);
universe@729: if (fc != 3) {
universe@729: fprintf(stderr, "Syntax error in line %zu.\n", i);
universe@729: cxMempoolDestroy(pool);
universe@729: return 1;
universe@729: }
universe@746: CSVData data;
universe@746: data.column_a = fields[0];
universe@746: data.column_b = fields[1];
universe@746: data.column_c = fields[2];
universe@746: cxListAdd(datalist, &data);
universe@729: }
universe@729:
universe@729: // iterate through the list and output the data
universe@729: CxIterator iter = cxListIterator(datalist);
universe@729: cx_foreach(CSVData*, data, iter) {
universe@729: printf("Column A: %.*s | "
universe@729: "Column B: %.*s | "
universe@729: "Column C: %.*s\n",
universe@729: (int)data->column_a.length, data->column_a.ptr,
universe@729: (int)data->column_b.length, data->column_b.ptr,
universe@729: (int)data->column_c.length, data->column_c.ptr
universe@729: );
universe@729: }
universe@729:
universe@729: // cleanup everything, no manual free() needed
universe@729: cxMempoolDestroy(pool);
universe@729:
universe@729: return 0;
universe@729: }
universe@729: ```
universe@729:
universe@720: ## Iterator
universe@720:
universe@720: *Header file:* [iterator.h](api/iterator_8h.html)
universe@720:
universe@733: In UCX 3 a new feature has been introduced to write own iterators, that work with the `cx_foreach` macro.
universe@733: In previous UCX releases there were different hard-coded foreach macros for lists and maps that were not customizable.
universe@733: Now, creating an iterator is as simple as creating a `CxIterator` struct and setting the fields in a meaningful way.
universe@733:
universe@733: You do not always need all fields in the iterator structure, depending on your use case.
universe@733: Sometimes you only need the `index` (for example when iterating over simple lists), and other times you will need the
universe@733: `slot` and `kv_data` fields (for example when iterating over maps).
universe@733:
universe@733: Usually an iterator is not mutating the collection it is iterating over.
universe@733: In some programming languages it is even disallowed to change the collection while iterating with foreach.
universe@733: But sometimes it is desirable to remove an element from the collection while iterating over it.
universe@733: This is, what the `CxMutIterator` is for.
universe@733: The only differences are, that the `mutating` flag is `true` and the `src_handle` is not const.
universe@733: On mutating iterators it is allowed to call the `cxFlagForRemoval()` function, which instructs the iterator to remove
universe@733: the current element from the collection on the next call to `cxIteratorNext()` and clear the flag afterward.
universe@733: If you are implementing your own iterator, it is up to you to implement this behavior in your `next` method, or
universe@733: make the implementation of the `flag_removal` method always return `false`.
universe@733:
universe@720: ## Collection
universe@720:
universe@720: *Header file:* [collection.h](api/collection_8h.html)
universe@720:
universe@730: Collections in UCX 3 have several common features.
universe@730: If you want to implement an own collection data type that uses the same features, you can use the
universe@730: `CX_COLLECTION_MEMBERS` macro at the beginning of your struct to roll out all members a usual UCX collection has.
universe@730: ```c
universe@730: struct my_fancy_collection_s {
universe@730: CX_COLLECTION_MEMBERS
universe@730: struct my_collection_data_s *data;
universe@730: };
universe@730: ```
universe@730: Based on this structure, this header provides some convenience macros for invoking the destructor functions
universe@730: that are part of the basic collection members.
universe@730: The idea of having destructor functions within a collection is that you can destroy the collection _and_ the
universe@730: contents with one single function call.
universe@730: When you are implementing a collection, you are responsible for invoking the destructors at the right places, e.g.
universe@730: when removing (and deleting) elements in the collection, clearing the collection, or - the most prominent case -
universe@730: destroying the collection.
universe@730:
universe@730: You can always look at the UCX list and map implementations if you need some inspiration.
universe@730:
universe@720: ## List
universe@720:
universe@720: *Header file:* [list.h](api/list_8h.html)
universe@720:
universe@731: This header defines a common interface for all list implementations, which is basically as simple as the following
universe@731: structure.
universe@731: ```c
universe@731: struct cx_list_s {
universe@731: CX_COLLECTION_MEMBERS // size, capacity, etc.
universe@731: cx_list_class const *cl; // The list class definition
universe@731: };
universe@731: ```
universe@745: The actual structure contains one more class pointer that is used when wrapping a list into a pointer-aware list
universe@731: with `cxListStorePointers()`. What this means, is that - if you want to implement your own list structure - you
universe@731: only need to cover the case where the list is storing copies of your objects.
universe@731:
universe@731: UCX comes with two common list implementations (linked list and array list) that should cover most use cases.
universe@731: But if you feel the need to implement an own list, the only thing you need to do is to define a struct where
universe@731: `struct cx_list_s`, and set an appropriate list class that implements the functionality.
universe@731: It is strongly recommended that this class is shared among all instances of the same list type, because otherwise
universe@731: the `cxListCompare` function cannot use the optimized implementation of your class and will instead fall back to
universe@731: using iterators to compare the contents element-wise.
universe@731:
universe@720: ### Linked List
universe@720:
universe@720: *Header file:* [linked_list.h](api/linked__list_8h.html)
universe@720:
universe@731: On top of implementing the list interface, this header also defines several low-level functions that
universe@731: work with arbitrary structures.
universe@731: Low-level functions, in contrast to the high-level list interface, can easily be recognized by their snake-casing.
universe@731: The function `cx_linked_list_at`, for example, implements a similar functionality like `cxListAt`, but operates
universe@731: on arbitrary structures.
universe@731: The following snippet shows how it is used.
universe@731: All other low-level functions work similarly.
universe@731: ```c
universe@731: struct node {
universe@731: node *next;
universe@731: node *prev;
universe@731: int data;
universe@731: };
universe@731:
universe@731: const ptrdiff_t loc_prev = offsetof(struct node, prev);
universe@731: const ptrdiff_t loc_next = offsetof(struct node, next);
universe@731: const ptrdiff_t loc_data = offsetof(struct node, data);
universe@731:
universe@731: struct node a = {0}, b = {0}, c = {0}, d = {0};
universe@731: cx_linked_list_link(&a, &b, loc_prev, loc_next);
universe@731: cx_linked_list_link(&b, &c, loc_prev, loc_next);
universe@731: cx_linked_list_link(&c, &d, loc_prev, loc_next);
universe@731:
universe@731: cx_linked_list_at(&a, 0, loc_next, 2); // returns pointer to c
universe@731: ```
universe@731:
universe@720: ### Array List
universe@720:
universe@720: *Header file:* [array_list.h](api/array__list_8h.html)
universe@720:
universe@731: Since low-level array lists are just plain arrays, there is no need for such many low-level functions as for linked
universe@731: lists.
universe@731: However, there is one extremely powerful function that can be used for several complex tasks: `cx_array_copy`.
universe@731: The full signature is shown below:
universe@731: ```c
universe@731: enum cx_array_copy_result cx_array_copy(
universe@731: void **target,
universe@731: size_t *size,
universe@731: size_t *capacity, // optional
universe@731: size_t index,
universe@731: void const *src,
universe@731: size_t elem_size,
universe@731: size_t elem_count,
universe@731: struct cx_array_reallocator_s *reallocator // optional
universe@731: );
universe@731: ```
universe@731: The `target` argument is a pointer to the target array pointer.
universe@731: The reason for this additional indirection is that - given that you provide a `reallocator` - this function writes
universe@731: back the pointer to the possibly reallocated array.
universe@731: THe next two arguments are pointers to the `size` and `capacity` of the target array.
universe@731: Tracking the capacity is optional.
universe@731: If you do not specify a pointer for the capacity, automatic reallocation of the array is entirely disabled (i.e. it
universe@731: does not make sense to specify a `reallocator` then).
universe@731: In this case, the function cannot copy more than `size-index` elements and if you try, it will return
universe@731: `CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED` and do nothing.
universe@731:
universe@731: On a successful invocation, the function copies `elem_count` number of elements, each of size `elem_size` from
universe@731: `src` to `*target` and uses the `reallocator` to extend the array when necessary.
universe@731: Finally, the size, capacity, and the pointer to the array are all updated and the function returns
universe@731: `CX_ARRAY_COPY_SUCCESS`.
universe@731:
universe@731: The third, but extremely rare, return code is `CX_ARRAY_COPY_REALLOC_FAILED` and speaks for itself.
universe@731:
universe@731: A few things to note:
universe@731: * `*target` and `src` can point to the same memory region, effectively copying elements within the array with `memmove`
universe@731: * `*target` does not need to point to the start of the array, but `size` and `capacity` always start counting from the
universe@731: position, `*target` points to - in this scenario, specifying a `reallocator` is forbidden for obvious reasons
universe@731: * `index` does not need to be within size of the current array, if `capacity` is specified
universe@731: * `index` does not even need to be within the capacity of the array, if `reallocator` is specified
universe@731:
universe@731:
universe@720: ## Map
universe@720:
universe@720: *Header file:* [map.h](api/map_8h.html)
universe@720:
universe@732: Similar to the list interface, the map interface provides a common API for implementing maps.
universe@732: There are some minor subtle differences, though.
universe@732:
universe@732: First, the `remove` method is not always a destructive removal.
universe@732: Instead, the last argument is a Boolean that indicates whether the element shall be destroyed or returned.
universe@732: ```c
universe@732: void *(*remove)(CxMap *map, CxHashKey key, bool destroy);
universe@732: ```
universe@732: When you implement this method, you are either supposed to invoke the destructors and return `NULL`,
universe@732: or just remove the element from the map and return it.
universe@732:
universe@732: Secondly, the iterator method is a bit more complete. The signature is as follows:
universe@732: ```c
universe@732: CxIterator (*iterator)(CxMap const *map, enum cx_map_iterator_type type);
universe@732: ```
universe@732: There are three map iterator types: for values, for keys, for pairs.
universe@732: Depending on the iterator type requested, you need to create an iterator with the correct methods that
universe@732: return the requested thing.
universe@732: There are no automatic checks to enforce this - it's completely up to you.
universe@732: If you need inspiration on how to do that, check the hash map implementation that comes with UCX.
universe@732:
universe@720: ### Hash Map
universe@720:
universe@720: *Header file:* [hash_map.h](api/hash__map_8h.html)
universe@720:
universe@732: UCX provides a basic hash map implementation with a configurable amount of buckets.
universe@732: If you do not specify the number of buckets, a default of 16 buckets will be used.
universe@732: You can always rehash the map with `cxMapRehash()` to change the number of buckets to something more efficient,
universe@732: but you need to be careful, because when you use this function you are effectively locking into using this
universe@732: specific hash map implementation, and you would need to remove all calls to this function when you want to
universe@732: exchange the concrete map implementation with something different.
universe@732:
universe@720: ## Utilities
universe@720:
universe@720: *Header file:* [utils.h](api/utils_8h.html)
universe@720:
universe@724: UCX provides some utilities for routine tasks. Most of them are simple macros, like e.g. the `cx_for_n()` macro,
universe@724: creating a `for` loop counting from zero to (n-1) which is extremely useful to traverse the indices of
universe@724: an array.
universe@724:
universe@724: But the most useful utilities are the *stream copy* functions, which provide a simple way to copy all - or a
universe@724: bounded amount of - data from one stream to another. Since the read/write functions of a UCX buffer are
universe@724: fully compatible with stream read/write functions, you can easily transfer data from file or network streams to
universe@724: a UCX buffer or vice-versa.
universe@724:
universe@724: The following example shows, how easy it is to read the contents of a file into a buffer:
universe@724: ```c
universe@724: FILE *inputfile = fopen(infilename, "r");
universe@724: if (inputfile) {
universe@724: CxBuffer fbuf;
universe@724: cxBufferInit(&fbuf, NULL, 4096, NULL, CX_BUFFER_AUTO_EXTEND);
universe@724: cx_stream_copy(inputfile, &fbuf,
universe@724: (cx_read_func) fread,
universe@724: (cx_write_func) cxBufferWrite);
universe@724: fclose(inputfile);
universe@724:
universe@724: // ... do something meaningful with the contents ...
universe@724:
universe@724: cxBufferDestroy(&fbuf);
universe@724: } else {
universe@724: perror("Error opening input file");
universe@724: if (fout != stdout) {
universe@724: fclose(fout);
universe@724: }
universe@724: }
universe@724: ```
universe@724:
universe@720: ### Printf Functions
universe@720:
universe@720: *Header file:* [printf.h](api/printf_8h.html)
universe@720:
universe@725: In this utility header you can find `printf()`-like functions that can write the formatted output to an arbitrary
universe@725: stream (or UCX buffer, resp.), or to memory allocated by an allocator within a single function call.
universe@725: With the help of these convenience functions, you do not need to `snprintf` your string to a temporary buffer anymore,
universe@725: plus you do not need to worry about too small buffer sizes, because the functions will automatically allocate enough
universe@725: memory to contain the entire formatted string.
universe@725:
universe@720: ### Compare Functions
universe@720:
universe@720: *Header file:* [compare.h](api/compare_8h.html)
universe@725:
universe@725: This header file contains a collection of compare functions for various data types.
universe@725: Their signatures are designed to be compatible with the `cx_compare_func` function pointer type.