array.h

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