array.c

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