array.h

   1 /*
   2                                      +-------+
   3                                          | ARRAY |
   4                                          +-------+
   5
   6         +-----------+--------------------+---------------------------------------+
   7         | Operation | Average complexity | Notes                                 |
   8         +-----------+--------------------+-------------------------------------- +
   9         | Lookup    | O(1)               |                                       |
  10         | Append    | O(1)               | unpredictable if capacity is exceeded |
  11         | Insert    | O(n)               | unpredictable if capacity is exceeded |
  12         | Sort      | O(n log n)         |                                       |
  13         | Find      | O(log n)           |                                       |
  14         +-----------+--------------------+---------------------------------------+
  15
  16         An array is a data structure where all elements (members) have the same size and are
  17                 located consecutively in memory.
  18
  19         Each array has a size which holds the number of current elements of the array.
  20         It also has a capacity, which is the number of elements that currently fit into
  21                 the array, which may be bigger than size.
  22
  23         The lookup complexity is O(1), which makes arrays well suited for fast lookups.
  24
  25         The complexity for appending an element at the end of the array is O(1).
  26
  27         The complexity for inserting an element at an arbitrary index of the array is O(n),
  28                 where n is the length of the array. This is because memory may need to be moved.
  29
  30         However, the insert/append complexity becomes unpredictable and largely depends on
  31                 the implementation of the C library if the capacity is exceeded. If the capacity
  32                 needs to be extended, the memory is reallocated. The mentioned complexity rules
  33                 only apply as long as (cap > siz + 1). *Usually*, realloc will have a complexity
  34                 of either O(1), if the memory block happens to be already big enough, or
  35                 O(n) + X, if a new, bigger block needs to be allocated and the memory copied.
  36
  37         Note that when the capacity is extended, it is possible to allocated more space space
  38                 than needed, to prevent frequent calls to append/insert from having to reallocate
  39                 the memory every time. If, and if yes how much additional space is allocated is
  40                 determined by the extra space field. Extra space for ext elements is allocated
  41                 whenever a growth reallocation happens.
  42
  43         The array can be sorted. In this case, the array is expected to have a comparator cmp
  44                 that is not NULL.
  45
  46         The comparison function must return an integer less than, equal to, or greater than
  47                 zero if the first argument is considered to be respectively less than, equal to,
  48                 or greater than the second. If two members compare as equal, their order in the
  49                 sorted array is undefined. [Copied from the Linux man-pages]
  50
  51         The sorting function uses the quicksort algorithm from the C library, which has an
  52                 average complexity of O(n log n).
  53
  54         To maintain the order of a sorted array, add and put should not be used.
  55 */
  56
  57 #ifndef _DRAGONSTD_ARRAY_H_ // include guard
  58 #define _DRAGONSTD_ARRAY_H_
  59
  60 #include <stddef.h>    // for size_t
  61 #include <sys/types.h> // for ssize_t
  62
  63 typedef int (*ArrayComparator)(const void *va, const void *vb);
  64
  65 typedef struct {
  66         /* public */
  67         void *ptr;           // memory
  68         size_t ext;          // extra space
  69         ArrayComparator cmp; // comparator
  70         /* private */
  71         size_t mbs;          // member size
  72         size_t siz;          // used space
  73         size_t cap;          // available space
  74 } Array;
  75
  76 void array_ini(Array *array, size_t mmb, size_t ext, ArrayComparator cmp);
  77 /*
  78         Initializes the array.
  79
  80         The array will have the member size of mmb and the extra space set to ext.
  81         mmb should be bigger than 0 and may not be changed after the initialization.
  82         ext can be 0 or bigger and may be changed any time.
  83         The comparator of the array is set to cmp and may be nil.
  84
  85         This function should be called before calling any other functions on the
  86                 array.
  87
  88         This function should not be called on an array that has been initialized before,
  89                 unless the array either has a capacity of 0 or it has been deleted using
  90                 array_del. Otherwise a memory leak will occur.
  91 */
  92
  93 void array_rlc(Array *array);
  94 /*
  95         Reallocates the array's memory to match it's capacity.
  96
  97         This function should be called every time the capacity has changed.
  98 */
  99
 100 void array_grw(Array *array, size_t n);
 101 /*
 102         Grows the array by n bytes.
 103
 104         This function increases the arrays size by n bytes. If this exceeds the capacity of
 105                 the array, the capacity set to the size and the extra space ext is added to it.
 106
 107         If the capacity is changed, the array is reallocated.
 108
 109         If n is zero, the array's capacity may still grow by extra space if it exactly
 110                 matches the current size.
 111 */
 112
 113 void array_shr(Array *array, size_t n);
 114 /*
 115         Shrinks the array by n bytes.
 116
 117         This function decreases the arrays size by n bytes.
 118
 119         If the array has additional capacity left after it has been shrunk, the capacity
 120                 is set to the new size and the array is reallocated to fit the new capacity.
 121                 For n > 0, this is always the case, for n = 0, this may be the case.
 122
 123         Note that calling this function with n = 0 is useful to shrink the array's memory to
 124                 exactly fit it's used size.
 125 */
 126
 127 void array_put(Array *array, const void *ptr, size_t n);
 128 /*
 129         Grows the array by 1 and inserts ptr at the index n.
 130
 131         This function inserts the memory pointed to by ptr before the array member at
 132                 index n, moving all elements from that index to the end of the array.
 133
 134         After this operation, the inserted element will be _at_ the index n.
 135
 136         The memory that ptr points to, which's size is assumed to be at least as big as the
 137                 array's member size is copied into the arrays memory.
 138
 139         n should be in the range from 0 to the array's size.
 140 */
 141
 142 void array_add(Array *array, const void *ptr);
 143 /*
 144         Grows the array by 1 and appends ptr at the end of the array.
 145
 146         This function's result is equivalent to calling array_put(array, ptr, array->siz),
 147                 but it is slightly faster since it saves unnecessary calls.
 148 */
 149
 150 void array_cpy(Array *array, void **ptr, size_t *n);
 151 /*
 152         Allocates a buffer big enough to fit the array's used size.
 153         Copies the array's contents into the allocated buffer.
 154         Returns the buffer in ptr and the size in n.
 155
 156         Note that the returned size is the number of elements, not the number of bytes.
 157 */
 158
 159 void array_cln(Array *dst, Array *src);
 160 /*
 161         Clones the array src to the array dst.
 162
 163         dst is initialized to have the same configuration (member size, extra space,
 164                 comparator) as src.
 165
 166         After the operation, the contents of the array dst are be the same as those of src.
 167                 The size of dst and src are the same, the capacity of dst however is the same as
 168                 the size of dst and src (which might not equal the capacity of src).
 169
 170         Since array_ini is called on dst, it should be uninitialized, empty or deleted.
 171 */
 172
 173 void array_rcy(Array *array);
 174 /*
 175         Recycles the array.
 176
 177         This function sets the used size of the array to 0 but leaves the capacity unchanged.
 178         The array's memory is not free'd and the array can be reused.
 179 */
 180
 181 void array_del(Array *array);
 182 /*
 183         Deletes the array.
 184
 185         This function frees the arrays memory. If this is not called when the array's
 186                 reference is dropped, a memory leak occurs, unless the array is empty (capacity
 187                 of 0), in which case the function does not need to be called. The function works
 188                 fine on empty arrays however.
 189
 190         After this, the array should no longer be used until reinitialized.
 191 */
 192
 193 void array_srt(Array *array);
 194 /*
 195         Sorts the array using the quicksort algorithm.
 196
 197         The array is assumed to have a non-NULL comparator.
 198         Wraps the qsort C-library routine. Please refer to it's documentation.
 199 */
 200
 201 ssize_t array_fnd(Array *array, const void *ptr, size_t *idx);
 202 /*
 203         Searches the sorted array for the element ptr.
 204         Returns the index of the element, or -1 if it wasn't found.
 205
 206         If idx is not NULL, a pointer to the last searched index is saved to where it
 207                 points to. This is the index ptr would need to be inserted at to keep the order.
 208
 209         It is assumed that the array has been sorted by array_srt before (or was empty),
 210                 and the order has been kept and the comparator has not been changed since.
 211 */
 212
 213 size_t array_ins(Array *array, const void *ptr);
 214 /*
 215         Inserts an element into a sorted array, keeping the order.
 216         Returns the index the element has been inserted at.
 217
 218         Calls array_fnd and array_put.
 219
 220         It is assumed that the array has been sorted by array_srt before (or was empty),
 221                 and the order has been kept and the comparator has not been changed since.
 222 */
 223
 224 #endif // _DRAGONSTD_ARRAY_H_