src/libical/icalarray.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*-
   2   ======================================================================
   3   FILE: icalarray.c
   4   CREATOR: Damon Chaplin 07 March 2001
   5
   6   $Id: icalarray.c,v 1.7 2008-01-15 23:17:40 dothebart Exp $
   7   $Locker:  $
   8
   9  (C) COPYRIGHT 2001, Ximian, Inc.
  10
  11  This program is free software; you can redistribute it and/or modify
  12  it under the terms of either:
  13
  14     The LGPL as published by the Free Software Foundation, version
  15     2.1, available at: http://www.fsf.org/copyleft/lesser.html
  16
  17   Or:
  18
  19     The Mozilla Public License Version 1.0. You may obtain a copy of
  20     the License at http://www.mozilla.org/MPL/
  21
  22
  23  ======================================================================*/
  24
  25 /** @file icalarray.c
  26  *
  27  *  @brief An array of arbitrarily-sized elements which grows
  28  *  dynamically as elements are added.
  29  */
  30
  31 #ifdef HAVE_CONFIG_H
  32 #include "config.h"
  33 #endif
  34
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include "icalarray.h"
  39 #include "icalerror.h"
  40
  41 static void icalarray_expand            (icalarray      *array,
  42                                          int             space_needed);
  43
  44 /** @brief Constructor
  45  */
  46
  47 icalarray*
  48 icalarray_new                   (int             element_size,
  49                                  int             increment_size)
  50 {
  51     icalarray *array;
  52
  53     array = (icalarray*) malloc (sizeof (icalarray));
  54     if (!array) {
  55         icalerror_set_errno(ICAL_NEWFAILED_ERROR);
  56         return NULL;
  57     }
  58
  59     array->element_size = element_size;
  60     array->increment_size = increment_size;
  61     array->num_elements = 0;
  62     array->space_allocated = 0;
  63     array->chunks = NULL;
  64
  65     return array;
  66 }
  67
  68 static void *
  69 icalarray_alloc_chunk(icalarray *array)
  70 {
  71     void *chunk = malloc(array->element_size * array->increment_size);
  72     if (!chunk)
  73       icalerror_set_errno(ICAL_NEWFAILED_ERROR);
  74     return chunk;
  75 }
  76
  77 icalarray *icalarray_copy       (icalarray      *originalarray)
  78 {
  79     icalarray *array = icalarray_new(originalarray->element_size, originalarray->increment_size);
  80     int chunks = originalarray->space_allocated / originalarray->increment_size;
  81     int chunk;
  82
  83     if (!array)
  84         return NULL;
  85
  86     array->num_elements = originalarray->num_elements;
  87     array->space_allocated = originalarray->space_allocated;
  88
  89     array->chunks = malloc(chunks * sizeof (void *));
  90     if (array->chunks) {
  91       for (chunk = 0; chunk < chunks; chunk++) {
  92           array->chunks[chunk] = icalarray_alloc_chunk(array);
  93           if (array->chunks[chunk])
  94               memcpy(array->chunks[chunk], originalarray->chunks[chunk],
  95                      array->increment_size * array->element_size);
  96       }
  97
  98     } else {
  99         icalerror_set_errno(ICAL_ALLOCATION_ERROR);
 100     }
 101
 102     return array;
 103 }
 104
 105
 106 /** @brief Destructor
 107  */
 108
 109 void
 110 icalarray_free                  (icalarray      *array)
 111 {
 112     if (array->chunks) {
 113       int chunks = array->space_allocated / array->increment_size;
 114       int chunk;
 115       for (chunk = 0; chunk < chunks; chunk++)
 116           free(array->chunks[chunk]);
 117       free (array->chunks);
 118       array->chunks = 0;
 119     }
 120     free (array);
 121     array = 0;
 122 }
 123
 124
 125 void
 126 icalarray_append                (icalarray      *array,
 127                                  const void             *element)
 128 {
 129     int pos;
 130     if (array->num_elements >= array->space_allocated)
 131         icalarray_expand (array, 1);
 132
 133     pos = array->num_elements++;
 134     memcpy (icalarray_element_at(array, pos), element, array->element_size);
 135 }
 136
 137
 138 void*
 139 icalarray_element_at            (icalarray      *array,
 140                                  int             position)
 141 {
 142     int       chunk = position / array->increment_size;
 143     int offset = position % array->increment_size;
 144
 145     assert (position >= 0);
 146     assert ((unsigned int)position < array->num_elements);
 147     return (char *)(array->chunks[chunk]) + (offset * array->element_size);
 148 }
 149
 150
 151 void
 152 icalarray_remove_element_at     (icalarray      *array,
 153                                  int             position)
 154 {
 155     void *dest;
 156     int elements_to_move;
 157
 158     assert (position >= 0);
 159     assert ((unsigned int)position < array->num_elements);
 160
 161     while (position < array->num_elements - 1) {
 162       memmove(icalarray_element_at(array, position),
 163               icalarray_element_at(array, position + 1),
 164               array->element_size);
 165       position++;
 166     }
 167
 168     array->num_elements--;
 169 }
 170
 171
 172 void
 173 icalarray_sort                  (icalarray      *array,
 174                                  int           (*compare) (const void *,
 175                                                            const void *))
 176 {
 177     if (array->num_elements == 0) {
 178         return;
 179     }
 180
 181     if (array->num_elements <= array->increment_size) {
 182       qsort(array->chunks[0], array->num_elements, array->element_size, compare);
 183     } else {
 184       int pos;
 185       void *tmp = malloc (array->num_elements * array->element_size);
 186       if (!tmp)
 187           return;
 188       for (pos = 0; pos < array->num_elements; pos++)
 189           memcpy((char *) tmp + array->element_size * pos, icalarray_element_at(array, pos), array->element_size);
 190
 191       qsort (tmp, array->num_elements, array->element_size, compare);
 192
 193       for (pos = 0; pos < array->num_elements; pos++)
 194           memcpy(icalarray_element_at(array, pos), (char *) tmp + array->element_size * pos, array->element_size);
 195       free (tmp);
 196     }
 197 }
 198
 199
 200 static void
 201 icalarray_expand                (icalarray      *array,
 202                                  int             space_needed)
 203 {
 204     int num_chunks = array->space_allocated / array->increment_size;
 205     int num_new_chunks;
 206     int c;
 207     void **new_chunks;
 208
 209     num_new_chunks = (space_needed + array->increment_size - 1) / array->increment_size;
 210     if (!num_new_chunks)
 211       num_new_chunks = 1;
 212
 213     new_chunks = malloc ((num_chunks + num_new_chunks) * sizeof (void *));
 214
 215     if (new_chunks) {
 216       memcpy(new_chunks, array->chunks, num_chunks * sizeof (void *));
 217       for (c = 0; c < num_new_chunks; c++)
 218           new_chunks[c + num_chunks] = icalarray_alloc_chunk(array);
 219       if (array->chunks)
 220           free (array->chunks);
 221       array->chunks = new_chunks;
 222       array->space_allocated = array->space_allocated + num_new_chunks * array->increment_size;
 223     } else
 224         icalerror_set_errno(ICAL_ALLOCATION_ERROR);
 225 }
 226
 227