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
10 * Authors: Andre Pang <Andre.Pang@csiro.au>
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.
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.
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 ************************************************************************/
28 #include <string.h> /* memmove(1) */
32 #define XARRAY_ASSERT_NOT_NULL(xarray) \
34 if (xarray == NULL) return XARRAY_ENULLPOINTER; \
37 #define XARRAY_BOUNDS_CHECK(xarray, index) \
40 return XARRAY_ENEGATIVEINDEX; \
41 else if (xarray->last_valid_element != -1 && \
42 (int) index > xarray->last_valid_element) \
43 return XARRAY_EINDEXTOOLARGE; \
46 #define XARRAY_GROW_ARRAY(xarray) \
48 xarray->array = (void *) realloc (xarray->array, xarray->size * 2); \
49 if (xarray->array == NULL) return XARRAY_ENOMEM; \
52 XSTATIC XArray * xarray_New (unsigned int initial_size_hint)
54 XArray *new_xarray = NULL;
56 unsigned int initial_size;
58 new_xarray = (XArray *) malloc (sizeof(XArray));
59 if (new_xarray == NULL) return NULL;
61 if (initial_size_hint <= 0)
62 initial_size = XARRAY_DEFAULT_SIZE;
64 initial_size = initial_size_hint;
66 inner_array = calloc (initial_size, sizeof(void *));
68 new_xarray->last_valid_element = -1;
69 new_xarray->size = initial_size;
70 new_xarray->last_error = 0;
72 if (inner_array == NULL)
78 new_xarray->array = inner_array;
80 /* Make a dummy reference to other functions, so that we don't get
81 * warnings about unused functions from the compiler. Ahem :) */
84 void *dummy_reference;
86 dummy_reference = xarray_AddObject;
87 dummy_reference = xarray_InsertObject;
88 dummy_reference = xarray_RemoveLastObject;
89 dummy_reference = xarray_RemoveObject;
90 dummy_reference = xarray_RemoveObjects;
91 dummy_reference = xarray_RemoveObjectsAfter;
92 dummy_reference = xarray_ReplaceObject;
94 dummy_reference = xarray_ObjectAtIndex;
95 dummy_reference = xarray_Count;
101 XSTATIC int xarray_ObjectAtIndex (XArray *xarray, unsigned int index,
104 XARRAY_ASSERT_NOT_NULL (xarray);
105 XARRAY_BOUNDS_CHECK (xarray, index);
107 *out_object = xarray->array[index];
109 return XARRAY_SUCCESS;
112 XSTATIC int xarray_AddObject (XArray *xarray, void *object)
114 XARRAY_ASSERT_NOT_NULL (xarray);
116 ++xarray->last_valid_element;
117 if (xarray->last_valid_element >= (int) xarray->size)
119 XARRAY_GROW_ARRAY (xarray);
122 xarray->array[xarray->last_valid_element] = object;
124 return XARRAY_SUCCESS;
127 XSTATIC int xarray_InsertObject (XArray *xarray, void *object,
128 unsigned int at_index)
130 XARRAY_ASSERT_NOT_NULL (xarray);
131 ++xarray->last_valid_element;
132 XARRAY_BOUNDS_CHECK (xarray, at_index);
133 if (xarray->last_valid_element >= (int) xarray->size)
135 XARRAY_GROW_ARRAY (xarray);
138 /* Shift everything from a[i] onward one pointer forward */
140 if ((int) at_index < xarray->last_valid_element)
142 (void) memmove (&xarray->array[at_index + 1],
143 &xarray->array[at_index],
144 (xarray->last_valid_element - at_index) *
148 xarray->array[at_index] = object;
150 return XARRAY_SUCCESS;
153 XSTATIC int xarray_RemoveLastObject (XArray *xarray)
155 XARRAY_ASSERT_NOT_NULL (xarray);
157 if (xarray->last_valid_element == -1)
158 return XARRAY_EEMPTYARRAY;
160 xarray->array[xarray->last_valid_element] = NULL;
161 --xarray->last_valid_element;
163 return XARRAY_SUCCESS;
166 XSTATIC int xarray_RemoveObject (XArray *xarray, unsigned int at_index)
168 XARRAY_ASSERT_NOT_NULL (xarray);
169 XARRAY_BOUNDS_CHECK (xarray, at_index);
171 /* Shift everything from a[i] onward one pointer backward */
173 if ((int) at_index < xarray->last_valid_element)
175 (void) memmove (&xarray->array[at_index],
176 &xarray->array[at_index + 1],
177 (xarray->last_valid_element - at_index) *
181 xarray->array[xarray->last_valid_element] = NULL;
182 --xarray->last_valid_element;
184 return XARRAY_SUCCESS;
187 XSTATIC int xarray_RemoveObjects (XArray *xarray, unsigned int at_index,
192 XARRAY_ASSERT_NOT_NULL (xarray);
193 XARRAY_BOUNDS_CHECK (xarray, at_index);
195 if (count == 0) return XARRAY_SUCCESS;
197 if ((int) at_index + (count - 1) > xarray->last_valid_element)
198 return XARRAY_ECOUNTOUTOFBOUNDS;
200 for (i = 0; i < count; i++)
202 int e = xarray_RemoveObject (xarray, at_index);
203 if (e != XARRAY_SUCCESS) return e;
206 return XARRAY_SUCCESS;
209 XSTATIC int xarray_RemoveObjectsAfter (XArray *xarray, unsigned int index)
211 XARRAY_ASSERT_NOT_NULL (xarray);
212 XARRAY_BOUNDS_CHECK (xarray, index);
216 while ((int) index <= xarray->last_valid_element)
218 int e = xarray_RemoveObject (xarray, index);
219 if (e != XARRAY_SUCCESS) return e;
222 return XARRAY_SUCCESS;
225 XSTATIC int xarray_ReplaceObject (XArray *xarray, unsigned int index,
228 XARRAY_ASSERT_NOT_NULL (xarray);
229 XARRAY_BOUNDS_CHECK (xarray, index);
231 xarray->array[index] = new_object;
233 return XARRAY_SUCCESS;
236 XSTATIC int xarray_Count (XArray *xarray, unsigned int *out_count)
238 XARRAY_ASSERT_NOT_NULL (xarray);
240 *out_count = xarray->last_valid_element + 1;
242 return XARRAY_SUCCESS;
246 #undef XARRAY_ASSERT_NOT_NULL
247 #undef XARRAY_BOUNDS_CHECK
248 #undef XARRAY_GROW_ARRAY