From d9c55a4d021b4a317a25f14f89468d62592aae0b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 28 Jan 2014 22:39:20 +0100 Subject: [PATCH] Doc: Documented growing arrays, generic allocators and related things --- ucw/alloc.h | 15 +++++++++++ ucw/doc/Makefile | 2 +- ucw/doc/alloc.txt | 24 +++++++++++++++++ ucw/doc/conf.txt | 4 +-- ucw/doc/gary.txt | 18 +++++++++++++ ucw/doc/growbuf.txt | 5 ++-- ucw/doc/index.txt | 6 ++--- ucw/doc/relnotes.txt | 11 ++++++-- ucw/gary.h | 63 +++++++++++++++++++++++++++++++++++++++++++- 9 files changed, 136 insertions(+), 12 deletions(-) create mode 100644 ucw/doc/alloc.txt create mode 100644 ucw/doc/gary.txt diff --git a/ucw/alloc.h b/ucw/alloc.h index 62924719..2c599283 100644 --- a/ucw/alloc.h +++ b/ucw/alloc.h @@ -7,6 +7,10 @@ #ifndef _UCW_ALLOC_H #define _UCW_ALLOC_H +/** + * This structure describes a generic allocator. It provides pointers + * to three functions, which handle the actual (re)allocations. + **/ struct ucw_allocator { void * (*alloc)(struct ucw_allocator *alloc, size_t size); void * (*realloc)(struct ucw_allocator *alloc, void *ptr, size_t old_size, size_t new_size); @@ -15,7 +19,18 @@ struct ucw_allocator { /* alloc-std.c */ +/** + * [[std]] + * This allocator uses xmalloc(), xrealloc() and xfree(). The memory + * it allocates is left unitialized. + **/ extern struct ucw_allocator ucw_allocator_std; + +/** + * [[zeroing]] + * This allocator uses xmalloc(), xrealloc() and xfree(). All memory + * is zeroed upon allocation. + **/ extern struct ucw_allocator ucw_allocator_zeroed; #endif diff --git a/ucw/doc/Makefile b/ucw/doc/Makefile index 962f168d..05cf5647 100644 --- a/ucw/doc/Makefile +++ b/ucw/doc/Makefile @@ -2,7 +2,7 @@ DIRS+=ucw/doc -UCW_DOCS=basics log fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap compress sort hashtable relnotes trans string time daemon signal varint opt +UCW_DOCS=basics log fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap compress sort hashtable relnotes trans string time daemon signal varint opt alloc gary UCW_INDEX=$(o)/ucw/doc/def_index.html UCW_DOCS_HTML=$(addprefix $(o)/ucw/doc/,$(addsuffix .html,$(UCW_DOCS))) diff --git a/ucw/doc/alloc.txt b/ucw/doc/alloc.txt new file mode 100644 index 00000000..adb233ff --- /dev/null +++ b/ucw/doc/alloc.txt @@ -0,0 +1,24 @@ +Generic allocators +================== + +Sometimes, we want to define data structures, whose memory allocation can be +parametrized. If we wish to squeeze out the last bit of performance, we +tie the structure to a certain allocator in compile time (as we do for + <>). If performance is not so critical, allocators +can be swapped in run time. + +This module defines a generic interface to memory allocators. You can use +the following pre-defined allocators, or define some of your own. + +* <> +* <> +* <> + +These data structures accept an allocator (more will come later): + +* Growing arrays + +ucw/alloc.h +----------- + +!!ucw/alloc.h diff --git a/ucw/doc/conf.txt b/ucw/doc/conf.txt index fbfa6429..695f78fe 100644 --- a/ucw/doc/conf.txt +++ b/ucw/doc/conf.txt @@ -153,8 +153,8 @@ For example, you can have an static array of five unsigned integers: *Dynamic arrays*:: Similar to static array, but you provide pointer to pointer to the given item (eg. if you want dynamic array of - integers, you give `**int`). The parser allocates a growing array - (see `gary.h`) of the required size. + integers, you give `**int`). The parser allocates a <> + of the required size. + If you want dynamic array of strings, you would use: + diff --git a/ucw/doc/gary.txt b/ucw/doc/gary.txt new file mode 100644 index 00000000..e7c78a1b --- /dev/null +++ b/ucw/doc/gary.txt @@ -0,0 +1,18 @@ +Growing arrays +============== + +This module provides growing arrays with items of an arbitrary type. +(Alternatively, you might want to use <>, +or the somewhat obsolete <>.) + +From the user's point of view, the array is represented as a pointer to +its first element, so it can be indexed by the usual `[]` operator. Please +keep in mind that this pointer can change, whenever the array is resized. + +Additional book-keeping information is stored before the first element +and it can be accessed using the macros below. + +ucw/gary.h +---------- + +!!ucw/gary.h diff --git a/ucw/doc/growbuf.txt b/ucw/doc/growbuf.txt index 218f7d24..c59c10b2 100644 --- a/ucw/doc/growbuf.txt +++ b/ucw/doc/growbuf.txt @@ -1,13 +1,12 @@ Growing buffers =============== +*This module is obsolete. Please use <> instead.* + It is quite usual situation when you need an array of items and you don not know how large it will be in the time you allocate it. Then you need some kind of dynamically growing buffer. -You can either use <>, which has similar -functionality, or this module. - - <> - <> diff --git a/ucw/doc/index.txt b/ucw/doc/index.txt index 33002353..de58ab96 100644 --- a/ucw/doc/index.txt +++ b/ucw/doc/index.txt @@ -24,13 +24,15 @@ Modules - <> - <> - <> +- <> - <> - <> - <> +- <> - <> - <> - <> -- <> +- <> (obsolete) - <> - <> - <> @@ -54,8 +56,6 @@ Other features Yet undocumented modules ------------------------ -- Allocators - * `gary.h` - Trie * `trie.h` - Red-black trees diff --git a/ucw/doc/relnotes.txt b/ucw/doc/relnotes.txt index 9cab4058..88dd5ba8 100644 --- a/ucw/doc/relnotes.txt +++ b/ucw/doc/relnotes.txt @@ -17,7 +17,7 @@ Release notes our <>. The <> module has been obsoleted * `` is automatically included by ``. -* *Incompatible:* It turned out that almost all users of the growing array +* *Incompatible:* It turned out that almost all users of the <> module push/pop individual elements. Therefore, we have removed the second argument (item count) of `GARY_PUSH` and `GARY_POP`. If you want to push/pop multiple elements at once, use `GARY_PUSH_MULTI` and `GARY_POP_MULTI`. @@ -28,6 +28,9 @@ Release notes operation was renamed to `HEAP_DELETE_MIN`. New operations `HEAP_REPLACE` and `HEAP_REPLACE_MIN` have been added. If you need to track positions of elements in the heap, please check the notes at individual functions. +* <> have been introduced, providing an abstract + way of memory allocation. <> are now based on such + allocators, which allows for example growing arrays in memory pools. * The <> has been improved: ** Multiple instances of the configuration parser are supported. ** *Incompatible:* As there may be more instances, we can no longer use @@ -42,6 +45,10 @@ Release notes <>, <>, and <>. +** *Incompatible:* Dynamic configuration arrays have been re-implemented in + terms of our generic <>. This makes them easier to + use and most of the interface has been preserved. The only exception is + static allocation via the DARY_ALLOC() macro, which is no longer available. * <> have been added including a new `daemon-control` utility. The old `daemon-helper` utility has been obsoleted and it is not compiled by default. @@ -91,7 +98,7 @@ Release notes mechanism for tracking resources and reporting errors. It is still considered experimental, so the API can change in future releases. -* Added a growing array module `gary.h`, similar to `gbuf.h`, but with +* Added a <> module `gary.h`, similar to `gbuf.h`, but with a much more convenient interface. * The <> can recognize unlinked nodes, diff --git a/ucw/gary.h b/ucw/gary.h index 6610e799..2c4c4edd 100644 --- a/ucw/gary.h +++ b/ucw/gary.h @@ -27,17 +27,58 @@ struct gary_hdr { #define GARY_HDR(ptr) ((struct gary_hdr *)((byte*)(ptr) - GARY_HDR_SIZE)) #define GARY_BODY(ptr) ((byte *)(ptr) + GARY_HDR_SIZE) +/** + * Create a new growing array, initially containing @n elements, + * and let @ptr point to its first element. The memory used by the + * array is allocated by xmalloc(). + **/ #define GARY_INIT(ptr, n) (ptr) = gary_init(sizeof(*(ptr)), (n), &ucw_allocator_std) + +/** + * Create a growing array like GARY_INIT() does, but all newly + * allocated elements will be automatically zeroed. + **/ #define GARY_INIT_ZERO(ptr, n) (ptr) = gary_init(sizeof(*(ptr)), (n), &ucw_allocator_zeroed) + +/** + * Create a growing array like GARY_INIT() does, but based upon the given + * <>. + **/ #define GARY_INIT_ALLOC(ptr, n, a) (ptr) = gary_init(sizeof(*(ptr)), (n), (a)) + +/** + * Create a growing array, initially containing 0 elements, but with enough + * space to keep @n of them without needing reallocation. The @ptr variable + * will point to the first element of the array. + **/ #define GARY_INIT_SPACE(ptr, n) do { GARY_INIT(ptr, n); (GARY_HDR(ptr))->num_elts = 0; } while (0) + +/** A combination of GARY_INIT_ZERO() and GARY_INIT_SPACE(). **/ #define GARY_INIT_SPACE_ZERO(ptr, n) do { GARY_INIT_ZERO(ptr, n); (GARY_HDR(ptr))->num_elts = 0; } while (0) + +/** A combination of GARY_INIT_ALLOC() and GARY_INIT_SPACE(). **/ #define GARY_INIT_SPACE_ALLOC(ptr, n, a) do { GARY_INIT_ALLOC(ptr, n, a); (GARY_HDR(ptr))->num_elts = 0; } while (0) + +/** Destroy a growing array and free memory used by it. If @ptr is NULL, nothing happens. **/ #define GARY_FREE(ptr) gary_free(ptr) + +/** Return the current number elements of the given growing array. **/ #define GARY_SIZE(ptr) (GARY_HDR(ptr)->num_elts) + +/** + * Resize the given growing array to @n elements. + * The @ptr can change, if the array has to be re-allocated. + **/ #define GARY_RESIZE(ptr, n) ((ptr) = gary_set_size((ptr), (n))) -#define GARY_INIT_OR_RESIZE(ptr, n) (ptr) = (ptr) ? gary_set_size((ptr), (n)) : gary_init(sizeof(*(ptr)), (n), 0) +/** Create a new growing array, or resize it if it already exists. **/ +#define GARY_INIT_OR_RESIZE(ptr, n) (ptr) = (ptr) ? gary_set_size((ptr), (n)) : gary_init(sizeof(*(ptr)), (n), &ucw_allocator_std) + +/** + * Push @n elements to a growing array. That is, make space for @n more elements + * at the end of the array and return a pointer to the first of these elements. + * The @ptr can change, if the array has to be re-allocated. + **/ #define GARY_PUSH_MULTI(ptr, n) ({ \ struct gary_hdr *_h = GARY_HDR(ptr); \ typeof(*(ptr)) *_c = &(ptr)[_h->num_elts]; \ @@ -46,10 +87,30 @@ struct gary_hdr { if (_h->num_elts > _h->have_space) \ (ptr) = gary_push_helper((ptr), _n, (byte **) &_c); \ _c; }) + +/** + * Push a single element at the end of a growing array and return a pointer to it. + * The @ptr can change, if the array has to be re-allocated. + **/ #define GARY_PUSH(ptr) GARY_PUSH_MULTI(ptr, 1) +/** + * Pop @n elements from the end of a growing array. + * The @ptr can change, if the array has to be re-allocated. + **/ #define GARY_POP_MULTI(ptr, n) GARY_HDR(ptr)->num_elts -= (n) + +/** + * Pop a single element from the end of a growing array. + * The @ptr can change, if the array has to be re-allocated. + **/ #define GARY_POP(ptr) GARY_POP_MULTI(ptr, 1) + +/** + * Fix size of a growing array, returning all unused memory to the + * system (or more precisely, to the underlying allocator). + * The @ptr can change. + **/ #define GARY_FIX(ptr) (ptr) = gary_fix((ptr)) /* Internal functions */ -- 2.39.5