src/array.c

   1 #include "array.h"
   2
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <stdio.h>
   6
   7 void *_array_create_helper(size_t e_size)
   8 {
   9    _private_container *c = malloc(sizeof(_private_container) - 1 + e_size);
  10 #ifdef DEBUGGING
  11    c->_sentinel = SENTINEL;
  12 #endif
  13    c->_reserved = 1;
  14    c->_size = 0;
  15    return c->_array;
  16 }
  17
  18 static void _array_resize_container(_private_container **c_, size_t e_size, int new_size)
  19 {
  20    assert( new_size >= 0 );
  21    _private_container *c = *c_;
  22
  23    if (new_size > c->_reserved) {
  24       /* increases the reserved space */
  25       do
  26          c->_reserved *= 2;
  27       while (new_size < c->_reserved);
  28
  29       c = realloc(c, sizeof(_private_container) - 1 + e_size * c->_reserved);
  30    }
  31
  32    c->_size = new_size;
  33    *c_ = c;
  34 }
  35
  36 void _array_resize_helper(void **a, size_t e_size, int new_size)
  37 {
  38    _private_container *c = _array_private_container(*a);
  39    _array_resize_container(&c, e_size, new_size);
  40    *a = c->_array;
  41 }
  42
  43 void *_array_grow_helper(void **a, size_t e_size)
  44 {
  45    _private_container *c = _array_private_container(*a);
  46    if (c->_size == c->_reserved) {
  47       /* Array full, doubles the reserved memory */
  48       c->_reserved *= 2;
  49       c = realloc(c, sizeof(_private_container) - 1 + e_size * c->_reserved);
  50       *a = c->_array;
  51    }
  52
  53    return c->_array + (c->_size++) * e_size;
  54 }
  55
  56 void _array_erase_helper(void **a, size_t e_size, void *first, void *last)
  57 {
  58    intptr_t diff = (char *)last - (char *)first;
  59
  60    /* copies the memory */
  61    _private_container *c = _array_private_container(*a);
  62    char *end = c->_array + c->_size * e_size;
  63    memmove(first, last, end - (char *)last);
  64
  65    /* resizes the array */
  66    assert("Invalid iterators passed to array erase" && (diff % e_size == 0));
  67    c->_size -= diff / e_size;
  68 }
  69
  70 void _array_shrink_helper(void **a, size_t e_size)
  71 {
  72    _private_container *c = _array_private_container(*a);
  73    if (c->_size != 0) {
  74       c = realloc(c, sizeof(_private_container) - 1 + e_size * c->_size);
  75       c->_reserved = c->_size;
  76    } else {
  77       c = realloc(c, sizeof(_private_container) - 1 + e_size);
  78       c->_reserved = 1;
  79    }
  80    *a = c->_array;
  81 }
  82
  83 void _array_free_helper(void *a)
  84 {
  85    free(_array_private_container(a));
  86 }
  87
  88 #if 0
  89 int main() {
  90    const int size = 100;
  91
  92    int i;
  93    int *array = array_create(int);
  94
  95    /* pushes some elements */
  96    for (i = 0; i < size; ++i)
  97       array_push_back(&array, i);
  98    assert(array_size(array) == size);
  99    assert(array_size(array) <= array_reserved(array));
 100    for (i = 0; i < size; ++i)
 101       assert(array[i] == i);
 102
 103    /* erases second half */
 104    array_erase(&array, array + size / 2, array + size);
 105    assert(array_size(array) == size / 2);
 106    assert(array_size(array) <= array_reserved(array));
 107    for (i = 0; i < size / 2; ++i)
 108       assert(array[i] == i);
 109
 110    /* shrinks */
 111    array_shrink(&array);
 112    assert(array_size(array) == array_reserved(array));
 113
 114    /* pushes back second half */
 115    for (i = size / 2; i < size; ++i)
 116       array_push_back(&array, i);
 117    assert(array_size(array) == size);
 118    assert(array_size(array) <= array_reserved(array));
 119    for (i = 0; i < size; ++i)
 120       assert(array[i] == i);
 121
 122    /* erases middle half */
 123    array_erase(&array, array + size / 4, array + 3 * size / 4);
 124    assert(array_size(array) == size / 2);
 125    assert(array_size(array) <= array_reserved(array));
 126    for (i = 0; i < size / 4; ++i)
 127       assert(array[i] == i);
 128    for (; i < size / 2; ++i)
 129       assert(array[i] == i + size / 2);
 130
 131    /* shrinks */
 132    array_shrink(&array);
 133    assert(array_size(array) == array_reserved(array));
 134
 135    /* erases one element */
 136    array_erase(&array, array, array + 1);
 137    assert(array_size(array) == size / 2 - 1);
 138    for (i = 1; i < size / 4; ++i)
 139       assert(array[i - 1] == i);
 140    for (; i < size / 2; ++i)
 141       assert(array[i - 1] == i + size / 2);
 142
 143    /* erases no elements */
 144    array_erase(&array, array, array);
 145    array_erase(&array, array + array_size(array), array + array_size(array));
 146    assert(array_size(array) == size / 2 - 1);
 147    for (i = 1; i < size / 4; ++i)
 148       assert(array[i - 1] == i);
 149    for (; i < size / 2; ++i)
 150       assert(array[i - 1] == i + size / 2);
 151
 152    /* erases all elements */
 153    array_erase(&array, array, array + array_size(array));
 154    assert(array_size(array) == 0);
 155
 156    /* shrinks */
 157    array_shrink(&array);
 158    assert(array_size(array) == 0);
 159    assert(array_reserved(array) == 1);
 160
 161    return 0;
 162 }
 163 #endif