vector.c

00001 /**
00002  *  @file
00003  *  Contains the implementation of a generic vector.
00004  *
00005  *  @author Jeremy A. Mowery jmowery@tresys.com
00006  *  @author Jason Tang jtang@tresys.com
00007  *
00008  *  Copyright (C) 2006-2007 Tresys Technology, LLC
00009  *
00010  *  This library is free software; you can redistribute it and/or
00011  *  modify it under the terms of the GNU Lesser General Public
00012  *  License as published by the Free Software Foundation; either
00013  *  version 2.1 of the License, or (at your option) any later version.
00014  *
00015  *  This library is distributed in the hope that it will be useful,
00016  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00017  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018  *  Lesser General Public License for more details.
00019  *
00020  *  You should have received a copy of the GNU Lesser General Public
00021  *  License along with this library; if not, write to the Free Software
00022  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00023  */
00024 
00025 #include <apol/vector.h>
00026 #include "vector-internal.h"
00027 #include <stdlib.h>
00028 #include <string.h>
00029 #include <errno.h>
00030 
00031 /** The default initial capacity of a vector; must be a positive integer */
00032 #define APOL_VECTOR_DFLT_INIT_CAP 10
00033 
00034 /**
00035  *  Generic vector structure. Stores elements as void*.
00036  */
00037 struct apol_vector
00038 {
00039         /** The array of element pointers, which will be resized as needed. */
00040         void **array;
00041         /** The number of elements currently stored in array. */
00042         size_t size;
00043         /** The actual amount of space in array. This amount will always
00044          *  be >= size and will grow exponentially as needed. */
00045         size_t capacity;
00046         apol_vector_free_func *fr;
00047 };
00048 
00049 apol_vector_t *apol_vector_create(apol_vector_free_func * fr)
00050 {
00051         return apol_vector_create_with_capacity(APOL_VECTOR_DFLT_INIT_CAP, fr);
00052 }
00053 
00054 apol_vector_t *apol_vector_create_with_capacity(size_t cap, apol_vector_free_func * fr)
00055 {
00056         apol_vector_t *v = NULL;
00057         int error;
00058 
00059         if (cap < 1) {
00060                 cap = 1;
00061         }
00062         v = calloc(1, sizeof(apol_vector_t));
00063         if (!v)
00064                 return NULL;
00065         v->array = calloc((v->capacity = cap), sizeof(void *));
00066         if (!(v->array)) {
00067                 error = errno;
00068                 free(v);
00069                 errno = error;
00070                 return NULL;
00071         }
00072         v->fr = fr;
00073         return v;
00074 }
00075 
00076 apol_vector_t *apol_vector_create_from_iter(qpol_iterator_t * iter, apol_vector_free_func * fr)
00077 {
00078         size_t iter_size;
00079         apol_vector_t *v;
00080         void *item;
00081         int error;
00082         if (qpol_iterator_get_size(iter, &iter_size) < 0 || (v = apol_vector_create_with_capacity(iter_size, fr)) == NULL) {
00083                 return NULL;
00084         }
00085         for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
00086                 if (qpol_iterator_get_item(iter, &item)) {
00087                         error = errno;
00088                         free(v);
00089                         errno = error;
00090                         return NULL;
00091                 }
00092                 apol_vector_append(v, item);
00093         }
00094         return v;
00095 }
00096 
00097 apol_vector_t *apol_vector_create_from_vector(const apol_vector_t * v, apol_vector_dup_func * dup, void *data,
00098                                               apol_vector_free_func * fr)
00099 {
00100         apol_vector_t *new_v;
00101         size_t i;
00102         if (v == NULL) {
00103                 errno = EINVAL;
00104                 return NULL;
00105         }
00106         if ((new_v = apol_vector_create_with_capacity(v->capacity, fr)) == NULL) {
00107                 return NULL;
00108         }
00109         if (dup == NULL) {
00110                 memcpy(new_v->array, v->array, v->size * sizeof(void *));
00111         } else {
00112                 for (i = 0; i < v->size; i++) {
00113                         new_v->array[i] = dup(v->array[i], data);
00114                 }
00115         }
00116         new_v->size = v->size;
00117         return new_v;
00118 }
00119 
00120 apol_vector_t *apol_vector_create_from_intersection(const apol_vector_t * v1,
00121                                                     const apol_vector_t * v2, apol_vector_comp_func * cmp, void *data)
00122 {
00123         apol_vector_t *new_v;
00124         size_t i, j;
00125         if (v1 == NULL || v2 == NULL) {
00126                 errno = EINVAL;
00127                 return NULL;
00128         }
00129         if ((new_v = apol_vector_create(NULL)) == NULL) {
00130                 return NULL;
00131         }
00132         for (i = 0; i < v1->size; i++) {
00133                 for (j = 0; j < v2->size; j++) {
00134                         if ((cmp != NULL && cmp(v1->array[i], v2->array[j], data) == 0) ||
00135                             (cmp == NULL && v1->array[i] == v2->array[j])) {
00136                                 if (apol_vector_append(new_v, v1->array[i]) < 0) {
00137                                         apol_vector_destroy(&new_v);
00138                                         return NULL;
00139                                 }
00140                                 break;
00141                         }
00142                 }
00143         }
00144         return new_v;
00145 }
00146 
00147 void apol_vector_destroy(apol_vector_t ** v)
00148 {
00149         size_t i = 0;
00150 
00151         if (!v || !(*v))
00152                 return;
00153 
00154         if ((*v)->fr) {
00155                 for (i = 0; i < (*v)->size; i++) {
00156                         (*v)->fr((*v)->array[i]);
00157                 }
00158         }
00159         free((*v)->array);
00160         (*v)->array = NULL;
00161         free(*v);
00162         *v = NULL;
00163 }
00164 
00165 size_t apol_vector_get_size(const apol_vector_t * v)
00166 {
00167         if (!v) {
00168                 errno = EINVAL;
00169                 return 0;
00170         } else {
00171                 return v->size;
00172         }
00173 }
00174 
00175 size_t apol_vector_get_capacity(const apol_vector_t * v)
00176 {
00177         if (!v) {
00178                 errno = EINVAL;
00179                 return 0;
00180         } else {
00181                 return v->capacity;
00182         }
00183 }
00184 
00185 void *apol_vector_get_element(const apol_vector_t * v, size_t idx)
00186 {
00187         if (!v || !(v->array)) {
00188                 errno = EINVAL;
00189                 return NULL;
00190         }
00191 
00192         if (idx >= v->size) {
00193                 errno = ERANGE;
00194                 return NULL;
00195         }
00196 
00197         return v->array[idx];
00198 }
00199 
00200 /**
00201  * Grows a vector, by reallocating additional space for it.
00202  *
00203  * @param v Vector to which increase its size.
00204  *
00205  * @return 0 on success, -1 on error.
00206  */
00207 static int apol_vector_grow(apol_vector_t * v)
00208 {
00209         void **tmp;
00210         size_t new_capacity = v->capacity;
00211         if (new_capacity >= 128) {
00212                 new_capacity += 128;
00213         } else {
00214                 new_capacity *= 2;
00215         }
00216         tmp = realloc(v->array, new_capacity * sizeof(void *));
00217         if (!tmp) {
00218                 return -1;
00219         }
00220         v->capacity = new_capacity;
00221         v->array = tmp;
00222         return 0;
00223 }
00224 
00225 int apol_vector_get_index(const apol_vector_t * v, const void *elem, apol_vector_comp_func * cmp, void *data, size_t * i)
00226 {
00227         if (!v || !i) {
00228                 errno = EINVAL;
00229                 return -1;
00230         }
00231 
00232         for (*i = 0; *i < v->size; (*i)++) {
00233                 if ((cmp != NULL && cmp(v->array[*i], elem, data) == 0) || (cmp == NULL && elem == v->array[*i])) {
00234                         return 0;
00235                 }
00236         }
00237         return -1;
00238 }
00239 
00240 int apol_vector_append(apol_vector_t * v, void *elem)
00241 {
00242         if (!v) {
00243                 errno = EINVAL;
00244                 return -1;
00245         }
00246 
00247         if (v->size >= v->capacity && apol_vector_grow(v)) {
00248                 return -1;
00249         }
00250 
00251         v->array[v->size] = elem;
00252         v->size++;
00253 
00254         return 0;
00255 }
00256 
00257 int apol_vector_append_unique(apol_vector_t * v, void *elem, apol_vector_comp_func * cmp, void *data)
00258 {
00259         size_t i;
00260         if (apol_vector_get_index(v, elem, cmp, data, &i) < 0) {
00261                 return apol_vector_append(v, elem);
00262         }
00263         errno = EEXIST;
00264         return 1;
00265 }
00266 
00267 int apol_vector_compare(const apol_vector_t * a, const apol_vector_t * b, apol_vector_comp_func * cmp, void *data, size_t * i)
00268 {
00269         int compval;
00270         if (a == NULL || b == NULL || i == NULL) {
00271                 errno = EINVAL;
00272                 return 0;
00273         }
00274         size_t a_len = apol_vector_get_size(a);
00275         size_t b_len = apol_vector_get_size(b);
00276         for (*i = 0; *i < a_len && *i < b_len; (*i)++) {
00277                 if (cmp != NULL) {
00278                         compval = cmp(a->array[*i], b->array[*i], data);
00279                 } else {
00280                         compval = (int)((char *)a->array[*i] - (char *)b->array[*i]);
00281                 }
00282                 if (compval != 0) {
00283                         return compval;
00284                 }
00285         }
00286         if (a_len == b_len) {
00287                 return 0;
00288         } else if (a_len < b_len) {
00289                 return -1;
00290         } else {
00291                 return 1;
00292         }
00293 }
00294 
00295 static size_t vector_qsort_partition(void **data, size_t first, size_t last, apol_vector_comp_func * cmp, void *arg)
00296 {
00297         void *pivot = data[last];
00298         size_t i = first, j = last;
00299         while (i < j) {
00300                 if (cmp(data[i], pivot, arg) <= 0) {
00301                         i++;
00302                 } else {
00303                         data[j] = data[i];
00304                         data[i] = data[j - 1];
00305                         j--;
00306                 }
00307         }
00308         data[j] = pivot;
00309         return j;
00310 }
00311 
00312 static void vector_qsort(void **data, size_t first, size_t last, apol_vector_comp_func * cmp, void *arg)
00313 {
00314         if (first < last) {
00315                 size_t i = vector_qsort_partition(data, first, last, cmp, arg);
00316                 /* need this explicit check here, because i is an
00317                  * unsigned integer, and subtracting 1 from 0 is
00318                  * bad */
00319                 if (i > 0) {
00320                         vector_qsort(data, first, i - 1, cmp, arg);
00321                 }
00322                 vector_qsort(data, i + 1, last, cmp, arg);
00323         }
00324 }
00325 
00326 /**
00327  * Generic comparison function, which treats elements of the vector as
00328  * unsigned integers.
00329  */
00330 static int vector_int_comp(const void *a, const void *b, void *data __attribute__ ((unused)))
00331 {
00332         char *i = (char *)a;
00333         char *j = (char *)b;
00334         if (i < j) {
00335                 return -1;
00336         } else if (i > j) {
00337                 return 1;
00338         }
00339         return 0;
00340 }
00341 
00342 /* implemented as an in-place quicksort */
00343 void apol_vector_sort(apol_vector_t * v, apol_vector_comp_func * cmp, void *data)
00344 {
00345         if (!v) {
00346                 errno = EINVAL;
00347                 return;
00348         }
00349         if (cmp == NULL) {
00350                 cmp = vector_int_comp;
00351         }
00352         if (v->size > 1) {
00353                 vector_qsort(v->array, 0, v->size - 1, cmp, data);
00354         }
00355 }
00356 
00357 void apol_vector_sort_uniquify(apol_vector_t * v, apol_vector_comp_func * cmp, void *data)
00358 {
00359         if (!v) {
00360                 errno = EINVAL;
00361                 return;
00362         }
00363         if (cmp == NULL) {
00364                 cmp = vector_int_comp;
00365         }
00366         if (v->size > 1) {
00367                 size_t i, j = 0;
00368                 void **new_array;
00369                 /* sweep through the array, do a quick compaction,
00370                  * then sort */
00371                 for (i = 1; i < v->size; i++) {
00372                         if (cmp(v->array[i], v->array[j], data) != 0) {
00373                                 /* found a unique element */
00374                                 j++;
00375                                 v->array[j] = v->array[i];
00376                         } else {
00377                                 /* found a non-unique element */
00378                                 if (v->fr != NULL) {
00379                                         v->fr(v->array[i]);
00380                                 }
00381                         }
00382                 }
00383                 v->size = j + 1;
00384 
00385                 apol_vector_sort(v, cmp, data);
00386                 j = 0;
00387                 for (i = 1; i < v->size; i++) {
00388                         if (cmp(v->array[i], v->array[j], data) != 0) {
00389                                 /* found a unique element */
00390                                 j++;
00391                                 v->array[j] = v->array[i];
00392                         } else {
00393                                 /* found a non-unique element */
00394                                 if (v->fr != NULL) {
00395                                         v->fr(v->array[i]);
00396                                 }
00397                         }
00398                 }
00399                 /* try to realloc vector to save space */
00400                 v->size = j + 1;
00401                 if ((new_array = realloc(v->array, v->size * sizeof(void *))) != NULL) {
00402                         v->array = new_array;
00403                         v->capacity = v->size;
00404                 }
00405         }
00406 }
00407 
00408 int apol_vector_cat(apol_vector_t * dest, const apol_vector_t * src)
00409 {
00410         size_t i, orig_size, cap;
00411         void **a;
00412         if (!src || !apol_vector_get_size(src)) {
00413                 return 0;              /* nothing to append */
00414         }
00415 
00416         if (!dest) {
00417                 errno = EINVAL;
00418                 return -1;
00419         }
00420         orig_size = apol_vector_get_size(dest);
00421         for (i = 0; i < apol_vector_get_size(src); i++)
00422                 if (apol_vector_append(dest, apol_vector_get_element(src, i))) {
00423                         /* revert if possible */
00424                         if (orig_size == 0) {
00425                                 cap = 1;
00426                         } else {
00427                                 cap = orig_size;
00428                         }
00429                         a = realloc(dest->array, cap * sizeof(*a));
00430                         if (a != NULL) {
00431                                 dest->array = a;
00432                         }
00433                         dest->size = orig_size;
00434                         dest->capacity = cap;
00435                         return -1;
00436                 }
00437 
00438         return 0;
00439 }
00440 
00441 int apol_vector_remove(apol_vector_t * v, const size_t idx)
00442 {
00443         if (v == NULL || idx >= v->size) {
00444                 errno = EINVAL;
00445                 return -1;
00446         }
00447         memmove(v->array + idx, v->array + idx + 1, sizeof(v->array[0]) * (v->size - idx - 1));
00448         v->size--;
00449         return 0;
00450 }
00451 
00452 /******************** friend function below ********************/
00453 
00454 void vector_set_free_func(apol_vector_t * v, apol_vector_free_func * fr)
00455 {
00456         v->fr = fr;
00457 }