1 /*
2 * This file is part of the Sofia-SIP package
3 *
4 * Copyright (C) 2005 Nokia Corporation.
5 *
6 * Contact: Pekka Pessi <pekka.pessi@nokia.com>
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
21 * 02110-1301 USA
22 *
23 */
24
25 /**@defgroup su_vector Vectors
26 *
27 * Pointer vectors.
28 *
29 * Unidimensional arrays using #su_home_t.
30 *
31 */
32
33 /**@ingroup su_vector
34 * @CFILE su_vector.c
35 * @brief Simple pointer vectors
36 *
37 * The vectors are resizeable unidimensional arrays.
38 *
39 * @author Pekka Pessi <Pekka.Pessi@nokia.com>
40 *
41 * @date Created: Fri Sep 27 14:43:29 2002 ppessi
42 */
43
44 #include "config.h"
45
46 #include <stdlib.h>
47 #include <stddef.h>
48 #include <memory.h>
49 #include <limits.h>
50 #include <string.h>
51
52 #include <assert.h>
53
54 #include "sofia-sip/su_config.h"
55 #include "sofia-sip/su_vector.h"
56
57 enum { N = 8 };
58
59 struct su_vector_s
60 {
61 su_home_t v_home[1];
62 su_home_t *v_parent;
63 size_t v_size;
64 size_t v_len;
65 su_free_func_t v_free_func;
66 void **v_list;
67 };
68
69 /** Create a vector.
70 *
71 * The function su_vector_create() creates a pointer vector object. The
72 * vector is initially empty. The function clones a memory home for the
73 * vector object from @a home. If a @a free_func is provided then that
74 * will be used to free the individual nodes (NULL if not used).
75 */
su_vector_create(su_home_t * home,su_free_func_t free_func)76 su_vector_t *su_vector_create(su_home_t *home, su_free_func_t free_func)
77 {
78 su_vector_t *vector;
79
80 vector = su_home_clone(home, sizeof(*vector) + N * sizeof(*vector->v_list));
81 if (vector) {
82 vector->v_parent = home;
83 vector->v_size = N;
84 vector->v_free_func = free_func;
85 vector->v_list = (void **)(vector + 1);
86 }
87 return vector;
88 }
89
90 /** Destroy a vector.
91 *
92 * The function su_vector_destroy() destroys a vector and frees all
93 * its nodes if a freeing function is available
94 */
su_vector_destroy(su_vector_t * vector)95 void su_vector_destroy(su_vector_t *vector)
96 {
97 size_t i;
98
99 if (vector) {
100 if (vector->v_free_func != NULL) {
101 for (i = 0; i < vector->v_len; i++) {
102 (vector->v_free_func)(vector->v_list[i]);
103 }
104 }
105
106 su_home_zap(vector->v_home);
107 }
108 }
109
110 /** Increase the list size for next item, if necessary. */
su_vector_make_place(su_vector_t * vector,usize_t index)111 static int su_vector_make_place(su_vector_t *vector, usize_t index)
112 {
113 if (vector->v_size <= vector->v_len + 1) {
114 size_t newsize = 2 * vector->v_size * sizeof(vector->v_list[0]);
115 void **list;
116
117 if (newsize < vector->v_size * sizeof(vector->v_list[0])) /* overflow */
118 return -1;
119
120 if (vector->v_list != (void **)(vector + 1) && index == vector->v_len) {
121 if (!(list = su_realloc(vector->v_home, vector->v_list, newsize)))
122 return 0;
123 }
124 else {
125 if (!(list = su_alloc(vector->v_home, newsize)))
126 return 0;
127
128 memcpy(list, vector->v_list, index * sizeof(vector->v_list[0]));
129 memcpy(list + index + 1, vector->v_list + index,
130 (vector->v_len - index) * sizeof(vector->v_list[0]));
131
132 if (vector->v_list != (void **)(vector + 1)) {
133 su_free(vector->v_home, vector->v_list);
134 }
135 }
136
137 vector->v_list = list;
138 vector->v_size *= 2;
139 }
140 else {
141 memmove(vector->v_list + index + 1, vector->v_list + index,
142 (vector->v_len - index) * sizeof(vector->v_list[0]));
143 }
144
145 vector->v_len++;
146
147 return 1;
148 }
149
150 /**Insert an item to vector.
151 *
152 * The function su_vector_insert() inserts an @a item to the @a vector.
153 * The items after the @a index will be moved further within the vector.
154 *
155 * @param vector pointer to a vector object
156 * @param item item to be appended
157 * @param index index for the new item
158 *
159 * @retval 0 when successful
160 * @retval -1 upon an error
161 */
su_vector_insert(su_vector_t * vector,usize_t index,void * item)162 int su_vector_insert(su_vector_t *vector, usize_t index, void *item)
163 {
164 if (vector &&
165 index <= vector->v_len &&
166 su_vector_make_place(vector, index) > 0) {
167 vector->v_list[index] = item;
168 return 0;
169 }
170 return -1;
171 }
172
173 /**Remove an item from vector.
174 *
175 * The function su_vector_remove() removes an item from the @a vector.
176 * The items after the @a index will be moved backwards within the vector.
177 *
178 * @param vector pointer to a vector object
179 * @param index index for the removed item
180 *
181 * @retval 0 when successful
182 * @retval -1 upon an error
183 */
su_vector_remove(su_vector_t * vector,usize_t index)184 int su_vector_remove(su_vector_t *vector, usize_t index)
185 {
186 if (vector && index < vector->v_len) {
187 if (vector->v_free_func)
188 (vector->v_free_func)(vector->v_list[index]);
189
190 memmove(vector->v_list + index,
191 vector->v_list + index + 1,
192 (vector->v_len - index - 1) * sizeof(vector->v_list[0]));
193 vector->v_len--;
194 return 0;
195 }
196
197 return -1;
198 }
199
200 /**Remove all items from vector.
201 *
202 * The function su_vector_empty() removes all items from the @a vector.
203 *
204 * @param vector pointer to a vector object
205 *
206 * @retval 0 if successful
207 * @retval -1 upon an error
208 */
su_vector_empty(su_vector_t * vector)209 int su_vector_empty(su_vector_t *vector)
210 {
211 size_t i;
212
213 if (vector) {
214 if (vector->v_free_func != NULL) {
215 for (i = 0; i < vector->v_len; i++) {
216 (vector->v_free_func)(vector->v_list[i]);
217 }
218 }
219
220 vector->v_len = 0;
221 return 0;
222 }
223
224 return -1;
225 }
226
227 /**Append an item to vector.
228 *
229 * The function su_vector_append() appends an @a item to the @a vector.
230 *
231 * @param vector pointer to a vector object
232 * @param item item to be appended
233 *
234 * @retval 0 if successful
235 * @retval -1 upon an error
236 */
su_vector_append(su_vector_t * vector,void * item)237 int su_vector_append(su_vector_t *vector, void *item)
238 {
239 size_t index;
240
241 if (vector == 0)
242 return -1;
243
244 index = vector->v_len;
245
246 if (su_vector_make_place(vector, index) <= 0)
247 return -1;
248
249 vector->v_list[index] = item;
250 return 0;
251 }
252
253 /**Get a numbered item from list.
254 *
255 * The function su_vector_item() returns a numbered item from vector. The
256 * numbering starts from 0.
257 *
258 * @param vector pointer to a vector object
259 * @param i index
260 *
261 * @return
262 * Pointer, if item exists, or NULL upon an error.
263 */
su_vector_item(su_vector_t const * vector,usize_t i)264 void *su_vector_item(su_vector_t const *vector, usize_t i)
265 {
266 if (vector && i < vector->v_len)
267 return vector->v_list[i];
268 else
269 return NULL;
270 }
271
272 /** Get number of items in list.
273 *
274 * The function su_vector_len() returns the number of items in the
275 * vector.
276 */
su_vector_len(su_vector_t const * l)277 usize_t su_vector_len(su_vector_t const *l)
278 {
279 return l ? l->v_len : 0;
280 }
281
su_vector_is_empty(su_vector_t const * vector)282 int su_vector_is_empty(su_vector_t const *vector)
283 {
284 return su_vector_len(vector) == 0;
285 }
286
287 /**Get a pointer array from list.
288 *
289 * The function su_vector_get_array() returns an array of pointer. The
290 * length of the array is always one longer than the length of the vector,
291 * and the last item in the returned array is always NULL.
292 *
293 * @param vector pointer to a vector object
294 *
295 * @return
296 * Pointer to array, or NULL if error occurred.
297 */
su_vector_get_array(su_vector_t * vector)298 void **su_vector_get_array(su_vector_t *vector)
299 {
300 if (vector) {
301 void **retval;
302 size_t newsize = sizeof(retval[0]) * (vector->v_len + 1);
303
304 retval = su_alloc(vector->v_home, newsize);
305
306 if (retval) {
307 retval[vector->v_len] = NULL;
308 return memcpy(retval, vector->v_list, sizeof(retval[0]) * vector->v_len);
309 }
310 }
311
312 return NULL;
313 }
314
315 /**Free a string array.
316 *
317 * The function su_vector_free_array() discards a string array allocated
318 * with su_vector_get_array().
319 *
320 * @param vector pointer to a vector object
321 * @param array string array to be freed
322 *
323 */
su_vector_free_array(su_vector_t * vector,void ** array)324 void su_vector_free_array(su_vector_t *vector, void **array)
325 {
326 su_free(vector->v_home, array);
327 }
328