00001 /** 00002 * @file 00003 * Contains the API for a generic vector. Note that vector functions 00004 * are not thread-safe. 00005 * 00006 * @author Jeremy A. Mowery jmowery@tresys.com 00007 * @author Jason Tang jtang@tresys.com 00008 * 00009 * Copyright (C) 2006-2007 Tresys Technology, LLC 00010 * 00011 * This library is free software; you can redistribute it and/or 00012 * modify it under the terms of the GNU Lesser General Public 00013 * License as published by the Free Software Foundation; either 00014 * version 2.1 of the License, or (at your option) any later version. 00015 * 00016 * This library is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00019 * Lesser General Public License for more details. 00020 * 00021 * You should have received a copy of the GNU Lesser General Public 00022 * License along with this library; if not, write to the Free Software 00023 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00024 */ 00025 00026 #ifndef APOL_VECTOR_H 00027 #define APOL_VECTOR_H 00028 00029 #ifdef __cplusplus 00030 extern "C" 00031 { 00032 #endif 00033 00034 #include <stdlib.h> 00035 #include <qpol/iterator.h> 00036 00037 typedef struct apol_vector apol_vector_t; 00038 00039 typedef int (apol_vector_comp_func) (const void *a, const void *b, void *data); 00040 typedef void (apol_vector_free_func) (void *elem); 00041 typedef void *(apol_vector_dup_func) (const void *elem, void *data); 00042 00043 /** 00044 * Allocate and initialize an empty vector with default 00045 * capacity. 00046 * 00047 * @param fr Function to call when destroying the vector. Each 00048 * element of the vector will be passed into this function; it should 00049 * free the memory used by that element. If this parameter is NULL, 00050 * the elements will not be freed. 00051 * 00052 * @return A pointer to a newly created vector on success and NULL on 00053 * failure. If the call fails, errno will be set. The caller is 00054 * responsible for calling apol_vector_destroy() to free memory used. 00055 */ 00056 extern apol_vector_t *apol_vector_create(apol_vector_free_func * fr); 00057 00058 /** 00059 * Allocate and initialize an empty vector with starting capacity of 00060 * cap. 00061 * 00062 * @param cap The starting capacity to allocate for the internal 00063 * array. 00064 * @param fr Function to call when destroying the vector. Each 00065 * element of the vector will be passed into this function; it should 00066 * free the memory used by that element. If this parameter is NULL, 00067 * the elements will not be freed. 00068 * 00069 * @return A pointer to a newly created vector on success and NULL on 00070 * failure. If the call fails, errno will be set. The caller is 00071 * responsible for calling apol_vector_destroy() to free memory used. 00072 */ 00073 extern apol_vector_t *apol_vector_create_with_capacity(size_t cap, apol_vector_free_func * fr); 00074 00075 /** 00076 * Allocate and return a vector that has been initialized with the 00077 * contents of a qpol iterator. <b>This function merely makes a 00078 * shallow copy of the iterator's contents</b>; any memory ownership 00079 * restrictions imposed by the iterator apply to this vector as well. 00080 * Also note that this function begins copying from the iterator's 00081 * current position, leaving the iterator at its end position 00082 * afterwards. 00083 * 00084 * @param iter qpol iterator from which to obtain vector's contents. 00085 * @param fr Function to call when destroying the vector. Each 00086 * element of the vector will be passed into this function; it should 00087 * free the memory used by that element. If this parameter is NULL, 00088 * the elements will not be freed. 00089 * 00090 * @return A pointer to a newly created vector on success and NULL on 00091 * failure. If the call fails, errno will be set. The caller is 00092 * responsible for calling apol_vector_destroy() to free memory used. 00093 */ 00094 extern apol_vector_t *apol_vector_create_from_iter(qpol_iterator_t * iter, apol_vector_free_func * fr); 00095 00096 /** 00097 * Allocate and return a vector that has been initialized with the 00098 * contents of another vector. 00099 * 00100 * @param v Vector from which to copy. 00101 * @param dup If NULL, then make a shallow copy of the original 00102 * vector's contents. Otherwise this function will be called upon 00103 * for each element from the original vector; the return value will 00104 * be the value stored in the new vector. 00105 * @param data Arbitrary data to pass as dup's second parameter. 00106 * @param fr Function to call when destroying the new vector. Each 00107 * element of the vector will be passed into this function; it should 00108 * free the memory used by that element. If this parameter is NULL, 00109 * the elements will not be freed. 00110 * 00111 * @return A pointer to a newly created vector on success and NULL on 00112 * failure. If the call fails, errno will be set. The caller is 00113 * responsible for calling apol_vector_destroy() to free memory used. 00114 */ 00115 extern apol_vector_t *apol_vector_create_from_vector(const apol_vector_t * v, apol_vector_dup_func * dup, void *data, 00116 apol_vector_free_func * fr); 00117 00118 /** 00119 * Allocate and return a vector that has been initialized with the 00120 * contents common to two other vectors. <b>This function merely 00121 * makes a shallow copy of the vectors' contents</b>; any memory 00122 * ownership restrictions imposed by the original vectors apply to 00123 * this new vector as well. Note that if a source vector contains 00124 * duplicate elements the returned vector may (or may not) have 00125 * duplicates as well. If the caller does not want duplicate entries 00126 * then apol_vector_sort_uniquify() should be called afterwards. 00127 * 00128 * @param v1 First vector from which to compute the intersection. 00129 * @param v2 Other vector to compute intersection. 00130 * @param cmp A comparison call back for the type of element stored 00131 * in the vector. The expected return value from this function is 00132 * less than, equal to, or greater than 0 if the first argument is 00133 * less than, equal to, or greater than the second respectively. If 00134 * this is NULL then do pointer address comparison. 00135 * @param data Arbitrary data to pass as the comparison function's 00136 * third paramater. 00137 * 00138 * @return A pointer to a newly created vector on success and NULL on 00139 * failure. If the call fails, errno will be set. The caller is 00140 * responsible for calling apol_vector_destroy() to free memory used. 00141 */ 00142 extern apol_vector_t *apol_vector_create_from_intersection(const apol_vector_t * v1, 00143 const apol_vector_t * v2, apol_vector_comp_func * cmp, 00144 void *data); 00145 00146 /** 00147 * Free a vector and any memory used by it. This will recursively 00148 * invoke the free function that was stored within the vector when it 00149 * was created. 00150 * 00151 * @param v Pointer to the vector to free. The pointer will be set 00152 * to NULL afterwards. If already NULL then this function does 00153 * nothing. 00154 */ 00155 extern void apol_vector_destroy(apol_vector_t ** v); 00156 00157 /** 00158 * Get the number of elements in the vector. 00159 * 00160 * @param v The vector from which to get the number of elements. 00161 * Must be non-NULL. 00162 * 00163 * @return The number of elements in the vector; if v is NULL, 00164 * returns 0. 00165 */ 00166 extern size_t apol_vector_get_size(const apol_vector_t * v); 00167 00168 /** 00169 * Get the current capacity of the vector. 00170 * 00171 * @param v The vector from which to get the current capacity. Must 00172 * be non-NULL. 00173 * 00174 * @return The capacity of the vector; this value will be greater or 00175 * equal to the number of elements in the vector. If v is NULL, 00176 * returns 0. 00177 */ 00178 extern size_t apol_vector_get_capacity(const apol_vector_t * v); 00179 00180 /** 00181 * Get the element at the requested index. 00182 * 00183 * @param v The vector from which to get the element. 00184 * @param idx The index of the desired element. 00185 * 00186 * @return A pointer to the element requested. If v is NULL or idx is 00187 * out of range, returns NULL and sets errno. 00188 */ 00189 extern void *apol_vector_get_element(const apol_vector_t * v, size_t idx); 00190 00191 /** 00192 * Find an element within a vector, returning its index within the vector. 00193 * 00194 * @param v The vector from which to get the element. 00195 * @param elem The element to find. 00196 * @param cmp A comparison call back for the type of element stored 00197 * in the vector. The first parameter will be an existing element 00198 * from the vector; next will be elem and then data. The expected 00199 * return value from this function is less than, equal to, or greater 00200 * than 0 if the first argument is less than, equal to, or greater 00201 * than the second respectively. For use in this function the return 00202 * value is only checked for 0 or non-zero return. If this is NULL 00203 * then do pointer address comparison. 00204 * @param data Arbitrary data to pass as the comparison function's 00205 * third paramater. 00206 * @param i Index into vector where element was found. This value is 00207 * undefined if the element was not found. 00208 * 00209 * @return 0 if element was found, or < 0 if not found. 00210 */ 00211 extern int apol_vector_get_index(const apol_vector_t * v, const void *elem, apol_vector_comp_func * cmp, void *data, 00212 size_t * i); 00213 00214 /** 00215 * Add an element to the end of a vector. 00216 * 00217 * @param v The vector to which to add the element. 00218 * @param elem The element to add. Once added the element will be 00219 * the last element in the vector. 00220 * 00221 * @return 0 on success and < 0 on failure. If the call fails, errno 00222 * will be set and v will be unchanged. 00223 */ 00224 extern int apol_vector_append(apol_vector_t * v, void *elem); 00225 00226 /** 00227 * Add an element to the end of a vector unless that element is equal 00228 * to an existing element. 00229 * 00230 * @param v The vector to which to add the element. 00231 * @param elem The element to add; must be non-NULL. 00232 * @param cmp A comparison call back for the type of element stored 00233 * in the vector. The expected return value from this function is 00234 * less than, equal to, or greater than 0 if the first argument is 00235 * less than, equal to, or greater than the second respectively. For 00236 * use in this function the return value is only checked for 0 or 00237 * non-zero return. If this is NULL then do pointer address 00238 * comparison. 00239 * @param data Arbitrary data to pass as the comparison function's 00240 * third paramater. 00241 * 00242 * @return 0 on success, < 0 on failure, and > 0 if the element 00243 * already exists in the vector. If the call fails or the element 00244 * already exists errno will be set. 00245 */ 00246 extern int apol_vector_append_unique(apol_vector_t * v, void *elem, apol_vector_comp_func * cmp, void *data); 00247 00248 /** 00249 * Concatenate two vectors. Appends all elements of src to dest. 00250 * <b>NOTE: No type checking is done for elements in the two 00251 * vectors.</b> Elements are not deep copies. 00252 * @param dest Vector to which to append elements. 00253 * @param src Vector containing elements to append. 00254 * @return 0 on success and < 0 on failure; if the call fails, 00255 * errno will be set and dest's contents will be reverted. 00256 */ 00257 extern int apol_vector_cat(apol_vector_t * dest, const apol_vector_t * src); 00258 00259 /** 00260 * Remove an element from a vector, and renumber all subsequent 00261 * elements. <b>This does not free memory that was used by the 00262 * removed element</b>; the caller is responsible for doing that. 00263 * 00264 * @param v Vector containing element. 00265 * @param idx Index to the element to remove. 00266 * @return 0 on success and < 0 on failure; if the call fails, 00267 * errno will be set and v's contents will be reverted. 00268 */ 00269 extern int apol_vector_remove(apol_vector_t * v, const size_t idx); 00270 00271 /** 00272 * Compare two vectors, determining if one is different than the 00273 * other. This uses a callback to compare elements across the 00274 * vectors. 00275 * 00276 * @param a First vector to compare. 00277 * @param b Second vector to compare. 00278 * @param cmp A comparison call back for the type of element stored 00279 * in the vector. The expected return value from this function is 00280 * less than, equal to, or greater than 0 if the first argument is 00281 * less than, equal to, or greater than the second respectively. If 00282 * this is NULL then do pointer address comparison. 00283 * @param data Arbitrary data to pass as the comparison function's 00284 * third paramater. 00285 * @param i Reference to where to store the index of the first 00286 * detected difference. The value is undefined if vectors are 00287 * equivalent (return value of 0). Note that the index may be 00288 * greater than a vector's size if the vectors are of unequal 00289 * lengths. 00290 * 00291 * @return < 0 if vector A is less than B, > 0 if A is greater than 00292 * B, or 0 if equivalent. 00293 */ 00294 extern int apol_vector_compare(const apol_vector_t * a, const apol_vector_t * b, apol_vector_comp_func * cmp, void *data, 00295 size_t * i); 00296 00297 /** 00298 * Sort the vector's elements within place, using an unstable sorting 00299 * algorithm. 00300 * 00301 * @param v The vector to sort. 00302 * @param cmp A comparison call back for the type of element stored 00303 * in the vector. The expected return value from this function is 00304 * less than, equal to, or greater than 0 if the first argument is 00305 * less than, equal to, or greater than the second respectively. If 00306 * this is NULL then treat the vector's contents as unsigned integers 00307 * and sort in increasing order. 00308 * @param data Arbitrary data to pass as the comparison function's 00309 * third paramater. 00310 */ 00311 extern void apol_vector_sort(apol_vector_t * v, apol_vector_comp_func * cmp, void *data); 00312 00313 /** 00314 * Sort the vector's elements within place (see apol_vector_sort()), 00315 * and then compact vector by removing duplicate entries. The 00316 * vector's free function will be used to free the memory used by 00317 * non-unique elements. 00318 * 00319 * @param v The vector to sort. 00320 * @param cmp A comparison call back for the type of element stored 00321 * in the vector. The expected return value from this function is 00322 * less than, equal to, or greater than 0 if the first argument is 00323 * less than, equal to, or greater than the second respectively. If 00324 * this is NULL then treat the vector's contents as unsigned integers 00325 * and sort in increasing order. 00326 * @param data Arbitrary data to pass as the comparison function's 00327 * third paramater. 00328 */ 00329 extern void apol_vector_sort_uniquify(apol_vector_t * v, apol_vector_comp_func * cmp, void *data); 00330 00331 #ifdef __cplusplus 00332 } 00333 #endif 00334 00335 #endif /* APOL_VECTOR_H */
