git.sesse.net Git - vlc/blob - modules/codec/cmml/xarray.c

   1 /*************************************************************************
   2  * xarray.c: Mutable (dynamically growable) array
   3  *************************************************************************
   4  * Copyright (C) 2004 Commonwealth Scientific and Industrial Research
   5  *                    Organisation (CSIRO) Australia
   6  * Copyright (C) 2004 the VideoLAN team
   7  *
   8  * $Id$
   9  *
  10  * Authors: Andre Pang <Andre.Pang@csiro.au>
  11  *
  12  * This program is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * This program is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with this program; if not, write to the Free Software
  24  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  25  ************************************************************************/
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <stddef.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include "xarray.h"
  34
  35 #define XARRAY_ASSERT_NOT_NULL(xarray) \
  36     { \
  37         if (xarray == NULL) return XARRAY_ENULLPOINTER; \
  38     }
  39
  40 #define XARRAY_BOUNDS_CHECK(xarray, index) \
  41     { \
  42         if (index < 0) \
  43             return XARRAY_ENEGATIVEINDEX; \
  44         else if (xarray->last_valid_element != -1 && \
  45                  (int) index > xarray->last_valid_element) \
  46             return XARRAY_EINDEXTOOLARGE; \
  47     }
  48
  49 #define XARRAY_GROW_ARRAY(xarray) \
  50     { \
  51         xarray->array = (void *) realloc (xarray->array, xarray->size * 2); \
  52         if (xarray->array == NULL) return XARRAY_ENOMEM; \
  53     }
  54
  55 XSTATIC XArray * xarray_New (unsigned int initial_size_hint)
  56 {
  57     XArray *new_xarray = NULL;
  58     void *inner_array;
  59     unsigned int initial_size;
  60
  61     new_xarray = (XArray *) malloc (sizeof(XArray));
  62     if (new_xarray == NULL) return NULL;
  63
  64     if (initial_size_hint <= 0)
  65         initial_size = XARRAY_DEFAULT_SIZE;
  66     else
  67         initial_size = initial_size_hint;
  68
  69     inner_array = calloc (initial_size, sizeof(void *));
  70
  71     new_xarray->last_valid_element = -1;
  72     new_xarray->size = initial_size;
  73     new_xarray->last_error = 0;
  74
  75     if (inner_array == NULL)
  76     {
  77         free (new_xarray);
  78         return NULL;
  79     }
  80
  81     new_xarray->array = inner_array;
  82
  83     /* Make a dummy reference to other functions, so that we don't get
  84      * warnings about unused functions from the compiler.  Ahem :) */
  85     while (0)
  86     {
  87         void *dummy_reference;
  88
  89         dummy_reference = xarray_AddObject;
  90         dummy_reference = xarray_InsertObject;
  91         dummy_reference = xarray_RemoveLastObject;
  92         dummy_reference = xarray_RemoveObject;
  93         dummy_reference = xarray_RemoveObjects;
  94         dummy_reference = xarray_RemoveObjectsAfter;
  95         dummy_reference = xarray_ReplaceObject;
  96
  97         dummy_reference = xarray_ObjectAtIndex;
  98         dummy_reference = xarray_Count;
  99     }
 100
 101     return new_xarray;
 102 }
 103
 104 XSTATIC int xarray_ObjectAtIndex (XArray *xarray, unsigned int index,
 105         void **out_object)
 106 {
 107     XARRAY_ASSERT_NOT_NULL (xarray);
 108     XARRAY_BOUNDS_CHECK (xarray, index);
 109
 110     *out_object = xarray->array[index];
 111
 112     return XARRAY_SUCCESS;
 113 }
 114
 115 XSTATIC int xarray_AddObject (XArray *xarray, void *object)
 116 {
 117     XARRAY_ASSERT_NOT_NULL (xarray);
 118
 119     ++xarray->last_valid_element;
 120     if (xarray->last_valid_element >= (int) xarray->size)
 121     {
 122         XARRAY_GROW_ARRAY (xarray);
 123     }
 124
 125     xarray->array[xarray->last_valid_element] = object;
 126
 127     return XARRAY_SUCCESS;
 128 }
 129
 130 XSTATIC int xarray_InsertObject (XArray *xarray, void *object,
 131         unsigned int at_index)
 132 {
 133     XARRAY_ASSERT_NOT_NULL (xarray);
 134     ++xarray->last_valid_element;
 135     XARRAY_BOUNDS_CHECK (xarray, at_index);
 136     if (xarray->last_valid_element >= (int) xarray->size)
 137     {
 138         XARRAY_GROW_ARRAY (xarray);
 139     }
 140
 141     /* Shift everything from a[i] onward one pointer forward */
 142
 143     if ((int) at_index < xarray->last_valid_element)
 144     {
 145         (void) memmove (&xarray->array[at_index + 1],
 146                         &xarray->array[at_index],
 147                         (xarray->last_valid_element - at_index) *
 148                             sizeof(void *));
 149     }
 150
 151     xarray->array[at_index] = object;
 152
 153     return XARRAY_SUCCESS;
 154 }
 155
 156 XSTATIC int xarray_RemoveLastObject (XArray *xarray)
 157 {
 158     XARRAY_ASSERT_NOT_NULL (xarray);
 159
 160     if (xarray->last_valid_element == -1)
 161         return XARRAY_EEMPTYARRAY;
 162
 163     xarray->array[xarray->last_valid_element] = NULL;
 164     --xarray->last_valid_element;
 165
 166     return XARRAY_SUCCESS;
 167 }
 168
 169 XSTATIC int xarray_RemoveObject (XArray *xarray, unsigned int at_index)
 170 {
 171     XARRAY_ASSERT_NOT_NULL (xarray);
 172     XARRAY_BOUNDS_CHECK (xarray, at_index);
 173
 174     /* Shift everything from a[i] onward one pointer backward */
 175
 176     if ((int) at_index < xarray->last_valid_element)
 177     {
 178         (void) memmove (&xarray->array[at_index],
 179                         &xarray->array[at_index + 1],
 180                         (xarray->last_valid_element - at_index) *
 181                             sizeof(void *));
 182     }
 183
 184     xarray->array[xarray->last_valid_element] = NULL;
 185     --xarray->last_valid_element;
 186
 187     return XARRAY_SUCCESS;
 188 }
 189
 190 XSTATIC int xarray_RemoveObjects (XArray *xarray, unsigned int at_index,
 191         int count)
 192 {
 193     int i;
 194
 195     XARRAY_ASSERT_NOT_NULL (xarray);
 196     XARRAY_BOUNDS_CHECK (xarray, at_index);
 197
 198     if (count == 0) return XARRAY_SUCCESS;
 199
 200     if ((int) at_index + (count - 1) > xarray->last_valid_element)
 201         return XARRAY_ECOUNTOUTOFBOUNDS;
 202
 203     for (i = 0; i < count; i++)
 204     {
 205         int e = xarray_RemoveObject (xarray, at_index);
 206         if (e != XARRAY_SUCCESS) return e;
 207     }
 208
 209     return XARRAY_SUCCESS;
 210 }
 211
 212 XSTATIC int xarray_RemoveObjectsAfter (XArray *xarray, unsigned int index)
 213 {
 214     XARRAY_ASSERT_NOT_NULL (xarray);
 215     XARRAY_BOUNDS_CHECK (xarray, index);
 216
 217     index++;
 218
 219     while ((int) index <= xarray->last_valid_element)
 220     {
 221         int e = xarray_RemoveObject (xarray, index);
 222         if (e != XARRAY_SUCCESS) return e;
 223     }
 224
 225     return XARRAY_SUCCESS;
 226 }
 227
 228 XSTATIC int xarray_ReplaceObject (XArray *xarray, unsigned int index,
 229         void *new_object)
 230 {
 231     XARRAY_ASSERT_NOT_NULL (xarray);
 232     XARRAY_BOUNDS_CHECK (xarray, index);
 233
 234     xarray->array[index] = new_object;
 235
 236     return XARRAY_SUCCESS;
 237 }
 238
 239 XSTATIC int xarray_Count (XArray *xarray, unsigned int *out_count)
 240 {
 241     XARRAY_ASSERT_NOT_NULL (xarray);
 242
 243     *out_count = xarray->last_valid_element + 1;
 244
 245     return XARRAY_SUCCESS;
 246 }
 247
 248
 249 #undef XARRAY_ASSERT_NOT_NULL
 250 #undef XARRAY_BOUNDS_CHECK
 251 #undef XARRAY_GROW_ARRAY
 252