diff options
Diffstat (limited to 'libapol/include/apol/vector.h')
| -rw-r--r-- | libapol/include/apol/vector.h | 335 |
1 files changed, 335 insertions, 0 deletions
diff --git a/libapol/include/apol/vector.h b/libapol/include/apol/vector.h new file mode 100644 index 0000000..f690bf0 --- /dev/null +++ b/libapol/include/apol/vector.h @@ -0,0 +1,335 @@ +/** + * @file + * Contains the API for a generic vector. Note that vector functions + * are not thread-safe. + * + * @author Jeremy A. Mowery jmowery@tresys.com + * @author Jason Tang jtang@tresys.com + * + * Copyright (C) 2006-2007 Tresys Technology, LLC + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef APOL_VECTOR_H +#define APOL_VECTOR_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include <stdlib.h> +#include <qpol/iterator.h> + + typedef struct apol_vector apol_vector_t; + + typedef int (apol_vector_comp_func) (const void *a, const void *b, void *data); + typedef void (apol_vector_free_func) (void *elem); + typedef void *(apol_vector_dup_func) (const void *elem, void *data); + +/** + * Allocate and initialize an empty vector with default + * capacity. + * + * @param fr Function to call when destroying the vector. Each + * element of the vector will be passed into this function; it should + * free the memory used by that element. If this parameter is NULL, + * the elements will not be freed. + * + * @return A pointer to a newly created vector on success and NULL on + * failure. If the call fails, errno will be set. The caller is + * responsible for calling apol_vector_destroy() to free memory used. + */ + extern apol_vector_t *apol_vector_create(apol_vector_free_func * fr); + +/** + * Allocate and initialize an empty vector with starting capacity of + * cap. + * + * @param cap The starting capacity to allocate for the internal + * array. + * @param fr Function to call when destroying the vector. Each + * element of the vector will be passed into this function; it should + * free the memory used by that element. If this parameter is NULL, + * the elements will not be freed. + * + * @return A pointer to a newly created vector on success and NULL on + * failure. If the call fails, errno will be set. The caller is + * responsible for calling apol_vector_destroy() to free memory used. + */ + extern apol_vector_t *apol_vector_create_with_capacity(size_t cap, apol_vector_free_func * fr); + +/** + * Allocate and return a vector that has been initialized with the + * contents of a qpol iterator. <b>This function merely makes a + * shallow copy of the iterator's contents</b>; any memory ownership + * restrictions imposed by the iterator apply to this vector as well. + * Also note that this function begins copying from the iterator's + * current position, leaving the iterator at its end position + * afterwards. + * + * @param iter qpol iterator from which to obtain vector's contents. + * @param fr Function to call when destroying the vector. Each + * element of the vector will be passed into this function; it should + * free the memory used by that element. If this parameter is NULL, + * the elements will not be freed. + * + * @return A pointer to a newly created vector on success and NULL on + * failure. If the call fails, errno will be set. The caller is + * responsible for calling apol_vector_destroy() to free memory used. + */ + extern apol_vector_t *apol_vector_create_from_iter(qpol_iterator_t * iter, apol_vector_free_func * fr); + +/** + * Allocate and return a vector that has been initialized with the + * contents of another vector. + * + * @param v Vector from which to copy. + * @param dup If NULL, then make a shallow copy of the original + * vector's contents. Otherwise this function will be called upon + * for each element from the original vector; the return value will + * be the value stored in the new vector. + * @param data Arbitrary data to pass as dup's second parameter. + * @param fr Function to call when destroying the new vector. Each + * element of the vector will be passed into this function; it should + * free the memory used by that element. If this parameter is NULL, + * the elements will not be freed. + * + * @return A pointer to a newly created vector on success and NULL on + * failure. If the call fails, errno will be set. The caller is + * responsible for calling apol_vector_destroy() to free memory used. + */ + extern apol_vector_t *apol_vector_create_from_vector(const apol_vector_t * v, apol_vector_dup_func * dup, void *data, + apol_vector_free_func * fr); + +/** + * Allocate and return a vector that has been initialized with the + * contents common to two other vectors. <b>This function merely + * makes a shallow copy of the vectors' contents</b>; any memory + * ownership restrictions imposed by the original vectors apply to + * this new vector as well. Note that if a source vector contains + * duplicate elements the returned vector may (or may not) have + * duplicates as well. If the caller does not want duplicate entries + * then apol_vector_sort_uniquify() should be called afterwards. + * + * @param v1 First vector from which to compute the intersection. + * @param v2 Other vector to compute intersection. + * @param cmp A comparison call back for the type of element stored + * in the vector. The expected return value from this function is + * less than, equal to, or greater than 0 if the first argument is + * less than, equal to, or greater than the second respectively. If + * this is NULL then do pointer address comparison. + * @param data Arbitrary data to pass as the comparison function's + * third paramater. + * + * @return A pointer to a newly created vector on success and NULL on + * failure. If the call fails, errno will be set. The caller is + * responsible for calling apol_vector_destroy() to free memory used. + */ + extern apol_vector_t *apol_vector_create_from_intersection(const apol_vector_t * v1, + const apol_vector_t * v2, apol_vector_comp_func * cmp, + void *data); + +/** + * Free a vector and any memory used by it. This will recursively + * invoke the free function that was stored within the vector when it + * was created. + * + * @param v Pointer to the vector to free. The pointer will be set + * to NULL afterwards. If already NULL then this function does + * nothing. + */ + extern void apol_vector_destroy(apol_vector_t ** v); + +/** + * Get the number of elements in the vector. + * + * @param v The vector from which to get the number of elements. + * Must be non-NULL. + * + * @return The number of elements in the vector; if v is NULL, + * returns 0. + */ + extern size_t apol_vector_get_size(const apol_vector_t * v); + +/** + * Get the current capacity of the vector. + * + * @param v The vector from which to get the current capacity. Must + * be non-NULL. + * + * @return The capacity of the vector; this value will be greater or + * equal to the number of elements in the vector. If v is NULL, + * returns 0. + */ + extern size_t apol_vector_get_capacity(const apol_vector_t * v); + +/** + * Get the element at the requested index. + * + * @param v The vector from which to get the element. + * @param idx The index of the desired element. + * + * @return A pointer to the element requested. If v is NULL or idx is + * out of range, returns NULL and sets errno. + */ + extern void *apol_vector_get_element(const apol_vector_t * v, size_t idx); + +/** + * Find an element within a vector, returning its index within the vector. + * + * @param v The vector from which to get the element. + * @param elem The element to find. + * @param cmp A comparison call back for the type of element stored + * in the vector. The first parameter will be an existing element + * from the vector; next will be elem and then data. The expected + * return value from this function is less than, equal to, or greater + * than 0 if the first argument is less than, equal to, or greater + * than the second respectively. For use in this function the return + * value is only checked for 0 or non-zero return. If this is NULL + * then do pointer address comparison. + * @param data Arbitrary data to pass as the comparison function's + * third paramater. + * @param i Index into vector where element was found. This value is + * undefined if the element was not found. + * + * @return 0 if element was found, or < 0 if not found. + */ + extern int apol_vector_get_index(const apol_vector_t * v, const void *elem, apol_vector_comp_func * cmp, void *data, + size_t * i); + +/** + * Add an element to the end of a vector. + * + * @param v The vector to which to add the element. + * @param elem The element to add. Once added the element will be + * the last element in the vector. + * + * @return 0 on success and < 0 on failure. If the call fails, errno + * will be set and v will be unchanged. + */ + extern int apol_vector_append(apol_vector_t * v, void *elem); + +/** + * Add an element to the end of a vector unless that element is equal + * to an existing element. + * + * @param v The vector to which to add the element. + * @param elem The element to add; must be non-NULL. + * @param cmp A comparison call back for the type of element stored + * in the vector. The expected return value from this function is + * less than, equal to, or greater than 0 if the first argument is + * less than, equal to, or greater than the second respectively. For + * use in this function the return value is only checked for 0 or + * non-zero return. If this is NULL then do pointer address + * comparison. + * @param data Arbitrary data to pass as the comparison function's + * third paramater. + * + * @return 0 on success, < 0 on failure, and > 0 if the element + * already exists in the vector. If the call fails or the element + * already exists errno will be set. + */ + extern int apol_vector_append_unique(apol_vector_t * v, void *elem, apol_vector_comp_func * cmp, void *data); + +/** + * Concatenate two vectors. Appends all elements of src to dest. + * <b>NOTE: No type checking is done for elements in the two + * vectors.</b> Elements are not deep copies. + * @param dest Vector to which to append elements. + * @param src Vector containing elements to append. + * @return 0 on success and < 0 on failure; if the call fails, + * errno will be set and dest's contents will be reverted. + */ + extern int apol_vector_cat(apol_vector_t * dest, const apol_vector_t * src); + +/** + * Remove an element from a vector, and renumber all subsequent + * elements. <b>This does not free memory that was used by the + * removed element</b>; the caller is responsible for doing that. + * + * @param v Vector containing element. + * @param idx Index to the element to remove. + * @return 0 on success and < 0 on failure; if the call fails, + * errno will be set and v's contents will be reverted. + */ + extern int apol_vector_remove(apol_vector_t * v, const size_t idx); + +/** + * Compare two vectors, determining if one is different than the + * other. This uses a callback to compare elements across the + * vectors. + * + * @param a First vector to compare. + * @param b Second vector to compare. + * @param cmp A comparison call back for the type of element stored + * in the vector. The expected return value from this function is + * less than, equal to, or greater than 0 if the first argument is + * less than, equal to, or greater than the second respectively. If + * this is NULL then do pointer address comparison. + * @param data Arbitrary data to pass as the comparison function's + * third paramater. + * @param i Reference to where to store the index of the first + * detected difference. The value is undefined if vectors are + * equivalent (return value of 0). Note that the index may be + * greater than a vector's size if the vectors are of unequal + * lengths. + * + * @return < 0 if vector A is less than B, > 0 if A is greater than + * B, or 0 if equivalent. + */ + extern int apol_vector_compare(const apol_vector_t * a, const apol_vector_t * b, apol_vector_comp_func * cmp, void *data, + size_t * i); + +/** + * Sort the vector's elements within place, using an unstable sorting + * algorithm. + * + * @param v The vector to sort. + * @param cmp A comparison call back for the type of element stored + * in the vector. The expected return value from this function is + * less than, equal to, or greater than 0 if the first argument is + * less than, equal to, or greater than the second respectively. If + * this is NULL then treat the vector's contents as unsigned integers + * and sort in increasing order. + * @param data Arbitrary data to pass as the comparison function's + * third paramater. + */ + extern void apol_vector_sort(apol_vector_t * v, apol_vector_comp_func * cmp, void *data); + +/** + * Sort the vector's elements within place (see apol_vector_sort()), + * and then compact vector by removing duplicate entries. The + * vector's free function will be used to free the memory used by + * non-unique elements. + * + * @param v The vector to sort. + * @param cmp A comparison call back for the type of element stored + * in the vector. The expected return value from this function is + * less than, equal to, or greater than 0 if the first argument is + * less than, equal to, or greater than the second respectively. If + * this is NULL then treat the vector's contents as unsigned integers + * and sort in increasing order. + * @param data Arbitrary data to pass as the comparison function's + * third paramater. + */ + extern void apol_vector_sort_uniquify(apol_vector_t * v, apol_vector_comp_func * cmp, void *data); + +#ifdef __cplusplus +} +#endif + +#endif /* APOL_VECTOR_H */ |