Mercurial > code
annotate array.c @ 65:b2cd1fd33bb0
Remove useless macros
| author | David Demelier <markand@malikania.fr> |
|---|---|
| date | Wed, 09 Nov 2011 20:12:24 +0100 |
| parents | 9cc5d6d0563e |
| children | cff6869fbc94 |
| rev | line source |
|---|---|
| 62 | 1 /* |
| 2 * array.c -- manipulate dynamic arrays | |
| 3 * | |
| 4 * Copyright (c) 2011, David Demelier <markand@malikania.fr> | |
| 5 * | |
| 6 * Permission to use, copy, modify, and/or distribute this software for any | |
| 7 * purpose with or without fee is hereby granted, provided that the above | |
| 8 * copyright notice and this permission notice appear in all copies. | |
| 9 * | |
| 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |
| 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |
| 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |
| 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
| 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
| 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
| 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
| 17 */ | |
| 18 | |
| 19 #include <stdio.h> | |
| 20 #include <stdlib.h> | |
| 21 #include <string.h> | |
| 22 | |
| 23 #include "array.h" | |
| 24 | |
| 25 #define OFFSET(x) (arr->unit * (x)) | |
| 26 | |
| 27 static int array_grow(struct array *); | |
| 28 | |
| 29 struct array * | |
| 30 array_new(enum array_type type, size_t unit, int length) | |
| 31 { | |
| 32 struct array *arr; | |
| 33 | |
| 34 if (unit == 0 || (arr = malloc(sizeof (struct array))) == NULL) | |
| 35 return NULL; | |
| 36 | |
| 37 memset(arr, 0, sizeof (struct array)); | |
| 38 arr->type = type; | |
| 39 arr->bsize = (length == 0) ? ARRAY_DEFAULT_BSIZE : length; | |
| 40 arr->unit = unit; | |
| 41 arr->size = OFFSET(arr->bsize); | |
| 42 | |
| 43 if ((arr->data = malloc(arr->size)) == NULL) { | |
| 44 free(arr); | |
| 45 return NULL; | |
| 46 } | |
| 47 | |
| 48 return arr; | |
| 49 } | |
| 50 | |
| 51 /* | |
| 52 * Add to the head of array. NOTE: this may be very slow when adding a lot | |
| 53 * of object (about 100000). If you need to add a lot of data please consider | |
| 54 * using linked list instead. | |
| 55 */ | |
| 56 | |
| 57 int | |
| 58 array_push(struct array *arr, const void *data) | |
| 59 { | |
| 60 if (array_grow(arr) < 0) | |
| 61 return -1; | |
| 62 | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
63 memmove((char *)arr->data + arr->unit, arr->data, OFFSET(arr->length++)); |
|
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
64 memcpy((char *)arr->data, data, arr->unit); |
| 62 | 65 |
| 66 return 0; | |
| 67 } | |
| 68 | |
| 69 /* | |
| 70 * Insert the data at the specified index. The function returns -1 on | |
| 71 * allocation failure or when the index is outof bounds otherwise 0 is returned. | |
| 72 */ | |
| 73 | |
| 74 int | |
| 75 array_insert(struct array *arr, const void *data, int index) | |
| 76 { | |
| 77 if (index > arr->length - 1 || index < 0 || array_grow(arr) < 0) | |
| 78 return -1; | |
| 79 | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
80 memmove((char *)arr->data + OFFSET(index + 1), |
|
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
81 (char *)arr->data + OFFSET(index), OFFSET(arr->length++ - index)); |
|
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
82 memcpy((char *)arr->data + OFFSET(index), data, arr->unit); |
| 62 | 83 |
| 84 return 0; | |
| 85 } | |
| 86 | |
| 87 /* | |
| 88 * Append the data to the end of array. | |
| 89 */ | |
| 90 | |
| 91 int | |
| 92 array_append(struct array *arr, const void *data) | |
| 93 { | |
| 94 if (array_grow(arr) < 0) | |
| 95 return -1; | |
| 96 | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
97 memcpy((char *)arr->data + OFFSET(arr->length++), data, arr->unit); |
| 62 | 98 |
| 99 return 0; | |
| 100 } | |
| 101 | |
| 102 /* | |
| 103 * Remove the array's head. | |
| 104 */ | |
| 105 | |
| 106 void | |
| 107 array_pop(struct array *arr) | |
| 108 { | |
| 109 if (arr->length > 0) { | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
110 memmove((char *)arr->data, (char *)arr->data + OFFSET(1), |
| 62 | 111 OFFSET(--arr->length)); |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
112 memset((char *)arr->data + OFFSET(arr->length), 0, arr->unit); |
| 62 | 113 } |
| 114 } | |
| 115 | |
| 116 /* | |
| 117 * Remove the array's tail. | |
| 118 */ | |
| 119 | |
| 120 void | |
| 121 array_unqueue(struct array *arr) | |
| 122 { | |
| 123 if (arr->length > 0) | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
124 memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit); |
| 62 | 125 } |
| 126 | |
| 127 /* | |
| 128 * Remove the data at the specified index. Bounds are checked. | |
| 129 */ | |
| 130 | |
| 131 void | |
| 132 array_remove(struct array *arr, int index) | |
| 133 { | |
| 134 if (arr->length > 0 && index >= 0 && index < arr->length) { | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
135 memmove((char *)arr->data + OFFSET(index), |
|
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
136 (char *)arr->data + OFFSET(index + 1), |
| 62 | 137 OFFSET(arr->length - index - 1)); |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
138 memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit); |
| 62 | 139 } |
| 140 } | |
| 141 | |
| 142 /* | |
| 143 * Remove the object referenced by the `data' argument. Useful when you | |
| 144 * don't know the index. | |
| 145 */ | |
| 146 | |
| 147 void | |
| 148 array_unref(struct array *arr, const void *data) | |
| 149 { | |
| 150 void *elm; | |
| 151 int i; | |
| 152 | |
| 153 for (i = 0; i < arr->length; ++i) { | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
154 elm = (char *)arr->data + OFFSET(i); |
| 62 | 155 |
| 156 if (memcmp(elm, data, arr->unit) == 0) | |
| 157 array_remove(arr, i); | |
| 158 } | |
| 159 } | |
| 160 | |
| 161 /* | |
| 162 * Swap the two elements referenced by index `i1' and `i2'. This function needs | |
| 163 * to allocate data to swap elements thus if the functions fails it returns -1 | |
| 164 * otherwise 0 is returned. | |
| 165 */ | |
| 166 | |
| 167 int | |
| 168 array_iswap(struct array *arr, int i1, int i2) | |
| 169 { | |
| 170 void *tmp; | |
| 171 | |
| 172 /* Out of bounds */ | |
| 173 if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0) | |
| 174 return -1; | |
| 175 | |
| 176 /* | |
| 177 * Only allocate at this time, the user may do not want to use this | |
| 178 * function. | |
| 179 */ | |
| 180 | |
| 181 if ((tmp = malloc(arr->unit)) == NULL) | |
| 182 return -1; | |
| 183 | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
184 memcpy((char *)tmp, (char *)arr->data + OFFSET(i1), arr->unit); |
|
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
185 memcpy((char *)arr->data + OFFSET(i1), (char *)arr->data + OFFSET(i2), |
| 62 | 186 arr->unit); |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
187 memcpy((char *)arr->data + OFFSET(i2), (char *)tmp, arr->unit); |
| 62 | 188 |
| 189 /* | |
| 190 * Clear bytes for safety you probably don't want a password or | |
| 191 * secure data to be left somewhere in the memory. | |
| 192 */ | |
| 193 | |
| 194 memset(tmp, 0, arr->unit); | |
| 195 free(tmp); | |
| 196 | |
| 197 return 0; | |
| 198 } | |
| 199 | |
| 200 /* | |
| 201 * Swap the two elements referenced by data `o1' and `o2'. This function | |
| 202 * may be slow on large arrays since it must travel all the object | |
| 203 * to find the indexes. | |
| 204 */ | |
| 205 | |
| 206 int | |
| 207 array_pswap(struct array *arr, const void *o1, const void *o2) | |
| 208 { | |
| 209 int found, i1, i2; | |
| 210 | |
| 211 for (i1 = found = 0; !found && i1 < arr->length; ++i1) | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
212 found = memcmp((char *)arr->data + OFFSET(i1), o1, arr->unit) == 0; |
| 62 | 213 |
| 214 if (!found) | |
| 215 return -1; | |
| 216 | |
| 217 for (i2 = found = 0; !found && i2 < arr->length; ++i2) | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
218 found = memcmp((char *)arr->data + OFFSET(i2), o2, arr->unit) == 0; |
| 62 | 219 |
| 220 if (!found) | |
| 221 return -1; | |
| 222 | |
| 223 return array_iswap(arr, --i1, --i2); | |
| 224 } | |
| 225 | |
| 226 /* | |
| 227 * Apply the function `fn' on each object and give the optional `udata' | |
| 228 * argument to the function too. | |
| 229 */ | |
| 230 | |
| 231 void | |
| 232 array_map(const struct array *arr, void (*fn)(void *, void *), void *udata) | |
| 233 { | |
| 234 int i; | |
| 235 | |
| 236 for (i = 0; i < arr->length; ++i) | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
237 fn((char *)arr->data + OFFSET(i), udata); |
| 62 | 238 } |
| 239 | |
| 240 /* | |
| 241 * Compare each object with the user supplied function. If the `fn' function | |
| 242 * returns 1 then the data is returned. Optional idx argument can be set to | |
| 243 * indicate the data position. If the data was not found the function returns | |
| 244 * NULL. | |
| 245 */ | |
| 246 | |
| 247 void * | |
| 248 array_find(const struct array *arr, int (*fn)(void *, void *), int *ix, void *u) | |
| 249 { | |
| 250 int st, i; | |
| 251 void *data; | |
| 252 | |
| 253 for (i = st = 0; i < arr->length && st != 1; ++i) | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
254 st = fn((char *)arr->data + OFFSET(i), u); |
| 62 | 255 |
| 256 if (st) { | |
|
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
257 data = (char *)arr->data + OFFSET(--i); |
| 62 | 258 if (ix) |
| 259 *ix = i; | |
| 260 } else | |
| 261 data = NULL; | |
| 262 | |
| 263 return data; | |
| 264 } | |
| 265 | |
| 266 /* | |
| 267 * Erase every bytes and set the length to 0. | |
| 268 */ | |
| 269 | |
| 270 void | |
| 271 array_clear(struct array *arr) | |
| 272 { | |
| 273 memset(arr->data, 0, arr->size); | |
| 274 arr->length = 0; | |
| 275 } | |
| 276 | |
| 277 /* | |
| 278 * Same as array_clear except it also free the array object. | |
| 279 */ | |
| 280 | |
| 281 void | |
| 282 array_free(struct array *arr) | |
| 283 { | |
| 284 array_clear(arr); | |
| 285 | |
| 286 if (arr->data) | |
| 287 free(arr->data); | |
| 288 | |
| 289 free(arr); | |
| 290 } | |
| 291 | |
| 292 /* | |
| 293 * Increate the array storage when it is full. If the buffer is fixed size | |
| 294 * it returns -1 on full buffer otherwise 0 is returned if allocation | |
| 295 * succeeded. | |
| 296 */ | |
| 297 | |
| 298 static int | |
| 299 array_grow(struct array *arr) | |
| 300 { | |
| 301 if ((arr->size / arr->unit) > (size_t) arr->length) | |
| 302 return 0; | |
| 303 | |
| 304 if (arr->type == ARRAY_AUTO) { | |
| 305 if ((arr->data = realloc(arr->data, arr->size + | |
| 306 OFFSET(arr->bsize))) == NULL) | |
| 307 return -1; | |
| 308 | |
| 309 arr->size += OFFSET(arr->bsize); | |
| 310 } else | |
| 311 return -1; | |
| 312 | |
| 313 return 0; | |
| 314 } |