array.h

   1 /*
   2         Array
   3         -----
   4
   5         Data structure where all elements (members) have the same size and are
   6                 located consecutively in memory.
   7
   8 */
   9
  10 #ifndef _DRAGONSTD_ARRAY_H_ // include guard
  11 #define _DRAGONSTD_ARRAY_H_
  12
  13 #include <stddef.h>        // for size_t
  14 #include <sys/types.h>     // for ssize_t
  15 #include "bits/compare.h"  // for cmp_ref (not used in file)
  16
  17 typedef struct {
  18         /* public */
  19         void *ptr;  // memory
  20         size_t ext; // extra space
  21         /* private */
  22         size_t mbs; // member size
  23         size_t siz; // used space
  24         size_t cap; // available space
  25 } Array;
  26
  27 void array_ini(Array *array, size_t mmb, size_t ext);
  28 /*
  29         Initializes the array.
  30
  31         The array will have the member size of mmb and the extra space set to ext.
  32         mmb should be bigger than 0 and may not be changed after the initialization.
  33         ext can be 0 or bigger and may be changed any time.
  34
  35         This function should be called before calling any other functions on the
  36                 array.
  37
  38         This function should not be called on an array that has been initialized before,
  39                 unless the array has a capacity of 0. Otherwise a memory leak will occur.
  40 */
  41
  42 void array_rlc(Array *array);
  43 /*
  44         Reallocates the array's memory to match it's capacity.
  45
  46         This function should be called every time the capacity has changed.
  47 */
  48
  49 void array_grw(Array *array, size_t n);
  50 /*
  51         Grows the array by n bytes.
  52
  53         This function increases the arrays size by n bytes. If this exceeds the capacity of
  54                 the array, the capacity set to the size and the extra space ext is added to it.
  55
  56         If the capacity is changed, the array is reallocated.
  57
  58         If n is zero, the array's capacity may still grow by extra space if it exactly
  59                 matches the current size.
  60 */
  61
  62 void array_shr(Array *array, size_t n);
  63 /*
  64         Shrinks the array by n bytes.
  65
  66         This function decreases the arrays size by n bytes.
  67
  68         If the array has additional capacity left after it has been shrunk, the capacity
  69                 is set to the new size and the array is reallocated to fit the new capacity.
  70                 For n > 0, this is always the case, for n = 0, this may be the case.
  71
  72         Note that calling this function with n = 0 is useful to shrink the array's memory to
  73                 exactly fit it's used size.
  74 */
  75
  76 void array_put(Array *array, const void *ptr, size_t n);
  77 /*
  78         Grows the array by 1 and inserts ptr at the index n.
  79
  80         This function inserts the memory pointed to by ptr before the array member at
  81                 index n, moving all elements from that index to the end of the array.
  82
  83         After this operation, the inserted element will be _at_ the index n.
  84
  85         The memory that ptr points to, which's size is assumed to be at least as big as the
  86                 array's member size is copied into the arrays memory.
  87
  88         n should be in the range from 0 to the array's size.
  89 */
  90
  91 void array_apd(Array *array, const void *ptr);
  92 /*
  93         Grows the array by 1 and appends ptr at the end of the array.
  94
  95         This function's result is equivalent to calling array_put(array, ptr, array->siz),
  96                 but it is slightly faster since it saves unnecessary calls.
  97 */
  98
  99 ssize_t array_idx(Array *array, const void *ptr);
 100 /*
 101         Returns the index of the first element that equals ptr, or none if no matches.
 102
 103         Uses memcmp to compare the elements.
 104 */
 105
 106 void array_cpy(Array *array, void **ptr, size_t *n);
 107 /*
 108         Allocates a buffer big enough to fit the array's used size.
 109         Copies the array's contents into the allocated buffer.
 110         Returns the buffer in ptr and the size in n.
 111
 112         Note that the returned size is the number of elements, not the number of bytes.
 113 */
 114
 115 void array_cln(Array *dst, Array *src);
 116 /*
 117         Clones the array src to the array dst.
 118
 119         dst is initialized to have the same configuration (member size, extra space) as src.
 120
 121         After the operation, the contents of the array dst are be the same as those of src.
 122                 The size of dst and src are the same, the capacity of dst however is the same as
 123                 the size of dst and src (which might not equal the capacity of src).
 124
 125         Since array_ini is called on dst, it should be uninitialized, empty or deleted.
 126 */
 127
 128 void array_rcy(Array *array);
 129 /*
 130         Recycles the array.
 131
 132         This function sets the used size of the array to 0 but leaves the capacity unchanged.
 133         The array's memory is not free'd and the array can be reused.
 134 */
 135
 136 void array_clr(Array *array);
 137 /*
 138         Clears the array.
 139
 140         This function frees the arrays memory. If this is not called when the array's
 141                 reference is dropped, a memory leak occurs, unless the array is empty (capacity
 142                 of 0), in which case the function does not need to be called. The function works
 143                 fine on empty arrays however.
 144
 145         After this, the array is empty and can be reused.
 146 */
 147
 148 void array_srt(Array *array, void *cmp);
 149 /*
 150         Sorts the array using the quicksort algorithm.
 151
 152         Comparator must not be NULL.
 153         Wraps the qsort C-library routine. Please refer to it's documentation.
 154 */
 155
 156 ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, void *cmp);
 157 /*
 158         Searches the sorted array for the element ptr.
 159         Returns the index of the element, or -1 if it wasn't found.
 160
 161         If idx is not NULL, a pointer to the last searched index is saved to where it
 162                 points to. This is the index ptr would need to be inserted at to keep the order.
 163
 164         It is assumed that the array has been sorted by array_srt before (or was empty),
 165                 and the order has been kept and the same comparator is used.
 166 */
 167
 168 size_t array_ins(Array *array, const void *ptr, void *cmp);
 169 /*
 170         Inserts an element into a sorted array, keeping the order.
 171         Returns the index the element has been inserted at.
 172
 173         Calls array_fnd and array_put.
 174
 175         It is assumed that the array has been sorted by array_srt before (or was empty),
 176                 and the order has been kept and the same comparator is used.
 177 */
 178
 179 #endif // _DRAGONSTD_ARRAY_H_