array.c

   1 #include <stdlib.h> // for malloc, realloc, free, qsort
   2 #include <string.h> // for memmove, memcpy
   3 #include "array.h"
   4
   5 void array_ini(Array *array, size_t mbs, size_t ext)
   6 {
   7         array->mbs = mbs;
   8         array->ext = ext;
   9         array->siz = 0;
  10         array->cap = 0;
  11         array->ptr = NULL;
  12 }
  13
  14 void array_rlc(Array *array)
  15 {
  16         array->ptr = realloc(array->ptr, array->cap * array->mbs);
  17 }
  18
  19 void array_grw(Array *array, size_t n)
  20 {
  21         array->siz += n;
  22
  23         if (array->siz > array->cap) {
  24                 array->cap = array->siz + array->ext;
  25                 array_rlc(array);
  26         }
  27 }
  28
  29 void array_shr(Array *array, size_t n)
  30 {
  31         array->siz -= n;
  32
  33         if (array->cap > array->siz) {
  34                 array->cap = array->siz;
  35                 array_rlc(array);
  36         }
  37 }
  38
  39 void array_put(Array *array, const void *ptr, size_t n)
  40 {
  41         size_t oldsiz = array->siz;
  42         array_grw(array, 1);
  43
  44         char *iptr = array->ptr + n * array->mbs;
  45         memmove(iptr + array->mbs, iptr, (oldsiz - n) * array->mbs);
  46         memcpy(iptr, ptr, array->mbs);
  47 }
  48
  49 void array_apd(Array *array, const void *ptr)
  50 {
  51         size_t oldsiz = array->siz;
  52         array_grw(array, 1);
  53
  54         memcpy(array->ptr + oldsiz * array->mbs, ptr, array->mbs);
  55 }
  56
  57 void array_cpy(Array *array, void **ptr, size_t *n)
  58 {
  59         *n = array->siz;
  60         size_t size = array->siz * array->mbs;
  61         *ptr = malloc(size);
  62         memcpy(*ptr, array->ptr, size);
  63 }
  64
  65 void array_cln(Array *dst, Array *src)
  66 {
  67         array_ini(dst, src->mbs, src->ext);
  68         array_cpy(src, &dst->ptr, &dst->siz);
  69         dst->cap = dst->siz;
  70 }
  71
  72 void array_rcy(Array *array)
  73 {
  74         array->siz = 0;
  75 }
  76
  77 void array_clr(Array *array)
  78 {
  79         if (array->ptr)
  80                 free(array->ptr);
  81         array_ini(array, array->mbs, array->ext);
  82 }
  83
  84 void array_srt(Array *array, Comparator cmp)
  85 {
  86         qsort(array->ptr, array->siz, array->mbs, cmp);
  87 }
  88
  89 ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, Comparator cmp)
  90 {
  91         size_t low, high, mid;
  92
  93         low = 0;
  94         high = array->siz;
  95
  96         while (low < high) {
  97                 mid = (low + high) / 2;
  98
  99                 int rel = cmp(ptr, array->ptr + mid * array->mbs);
 100
 101                 if (rel == 0)
 102                         return idx ? (*idx = mid) : mid;
 103                 else if (rel < 0)
 104                         high = mid;
 105                 else // (rel > 0)
 106                         low = mid + 1;
 107         }
 108
 109         if (idx)
 110                 *idx = low;
 111
 112         return -1;
 113 }
 114
 115 size_t array_ins(Array *array, const void *ptr, Comparator cmp)
 116 {
 117         size_t n;
 118
 119         array_fnd(array, ptr, &n, cmp);
 120         array_put(array, ptr, n);
 121
 122         return n;
 123 }