libcitadel/lib/array.c

   1 /*
   2  * This is a quickly-hacked-together implementation of an elastic array class.  It includes constructor and destructor
   3  * methods, append and access methods, and that's about it.  The memory allocation is very naive: whenever we are about
   4  * to append beyond the size of the buffer, we double its size.
   5  *
   6  * Copyright (c) 2021 by Art Cancro
   7  *
   8  * This program is open source software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 3 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  21  */
  22
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <stdio.h>
  27 #include "libcitadel.h"
  28
  29 /*
  30  * Constructor for elastic array
  31  */
  32 Array *array_new(size_t element_size) {
  33         Array *newarr = malloc(sizeof(Array));
  34         if (newarr) {
  35                 memset(newarr, 0, sizeof(Array));
  36         }
  37         newarr->element_size = element_size;
  38         return newarr;
  39 }
  40
  41
  42 /*
  43  * Destructor for elastic array
  44  */
  45 void array_free(Array *arr) {
  46         free(arr->the_elements);
  47         free(arr);
  48 }
  49
  50
  51 /*
  52  * Append an element to an array (we already know the element size because it's in the data type)
  53  */
  54 void array_append(Array *arr, void *new_element) {
  55
  56         if (!arr) {                                             // silently fail if they gave us a null array
  57                 return;
  58         }
  59
  60         if ( (arr->the_elements == NULL) || (arr->num_alloc == 0)) {
  61                 arr->num_alloc = 1;
  62                 arr->num_elements = 0;
  63                 arr->the_elements = malloc(arr->element_size * arr->num_alloc);
  64                 if (arr->the_elements == NULL) {
  65                         abort();
  66                 }
  67         }
  68
  69         ++arr->num_elements;
  70         if (arr->num_elements > arr->num_alloc) {
  71                 arr->num_alloc = arr->num_alloc * 2;            // whenever we exceed the buffer size, we double it.
  72                 arr->the_elements = realloc(arr->the_elements, (arr->element_size * arr->num_alloc));
  73                 if (arr->the_elements == NULL) {
  74                         abort();
  75                 }
  76         }
  77
  78         memcpy((arr->the_elements + ( (arr->num_elements-1) * arr->element_size )), new_element, arr->element_size);
  79 }
  80
  81
  82 /*
  83  * Return the element in an array at the specified index
  84  */
  85 void *array_get_element_at(Array *arr, int index) {
  86         return (arr->the_elements + ( index * arr->element_size ));
  87 }
  88
  89
  90 /*
  91  * Return the number of elements in an array
  92  */
  93 int array_len(Array *arr) {
  94         return arr->num_elements;
  95 }
  96
  97
  98 /*
  99  * Sort an array.  We already know the element size and number of elements, so all we need is
 100  * a sort function, which we will pass along to qsort().
 101  */
 102 void array_sort(Array *arr, int (*compar)(const void *, const void *)) {
 103         qsort(arr->the_elements, arr->num_elements, arr->element_size, compar);
 104 }
 105
 106
 107 /*
 108  * Delete an element from an array
 109  */
 110 void array_delete_element_at(Array *arr, int index) {
 111
 112         if (index >= arr->num_elements) {               // If the supplied index is out of bounds, return quietly.
 113                 return;
 114         }
 115
 116         if (index < 0) {                                // If the supplied index is invalid, return quietly.
 117                 return;
 118         }
 119
 120         --arr->num_elements;
 121
 122         if (index == arr->num_elements) {               // If we deleted the element at the end, there's no more to be done.
 123                 return;
 124         }
 125
 126         memcpy(
 127                 (arr->the_elements + (index * arr->element_size)),
 128                 arr->the_elements + ((index+1) * arr->element_size),
 129                 (arr->num_elements - index) * arr->element_size
 130         );
 131 }