123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283 |
- /** @file vec.c
- * Implementation of variable length vector of arbitrary structures.
- */
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #include <ctype.h>
- #include <stdio.h>
- #include "private.h"
- /** @brief Allocates and initalizes new vector.
- *
- * Callback function matchFn can be used later to find item by user specified
- * key. Function can compare key and item's data.
- *
- * @param [in] item_size Size of single vector's item.
- * @param [in] matchFn Callback function to compare user key and item's data.
- * @return Allocated and initialized vector or NULL on error.
- */
- faux_vec_t *faux_vec_new(size_t item_size, faux_vec_kcmp_fn matchFn)
- {
- faux_vec_t *faux_vec = NULL;
- faux_vec = faux_zmalloc(sizeof(*faux_vec));
- assert(faux_vec);
- if (!faux_vec)
- return NULL;
- if (0 == item_size)
- return NULL;
- // Init
- faux_vec->data = NULL;
- faux_vec->item_size = item_size;
- faux_vec->len = 0;
- faux_vec->kcmpFn = matchFn;
- return faux_vec;
- }
- /** @brief Frees previously allocated vector object.
- *
- * @param [in] faux_vec Allocated vector object.
- */
- void faux_vec_free(faux_vec_t *faux_vec)
- {
- if (!faux_vec)
- return;
- faux_free(faux_vec->data);
- faux_free(faux_vec);
- }
- /** @brief Gets vector length in items.
- *
- * @param [in] faux_vec Allocated vector object.
- * @return Number of items.
- */
- size_t faux_vec_len(const faux_vec_t *faux_vec)
- {
- assert(faux_vec);
- if (!faux_vec)
- return 0;
- return faux_vec->len;
- }
- /** @brief Gets size of item.
- *
- * @param [in] faux_vec Allocated vector object.
- * @return Size of item in bytes.
- */
- size_t faux_vec_item_size(const faux_vec_t *faux_vec)
- {
- assert(faux_vec);
- if (!faux_vec)
- return 0;
- return faux_vec->item_size;
- }
- /** @brief Gets item by index.
- *
- * Gets pointer to item's data.
- *
- * @param [in] faux_vec Allocated vector object.
- * @return Pointer to item or NULL on error.
- */
- void *faux_vec_item(const faux_vec_t *faux_vec, unsigned int index)
- {
- assert(faux_vec);
- if (!faux_vec)
- return NULL;
- if ((index + 1) > faux_vec_len(faux_vec))
- return NULL;
- return (char *)faux_vec->data + index * faux_vec_item_size(faux_vec);
- }
- /** @brief Gets pointer to whole vector.
- *
- * @param [in] faux_vec Allocated vector object.
- * @return Pointer to vector or NULL on error.
- */
- void *faux_vec_data(const faux_vec_t *faux_vec)
- {
- assert(faux_vec);
- if (!faux_vec)
- return NULL;
- return faux_vec->data;
- }
- /** @brief Adds item to vector and gets pointer to newly created item.
- *
- * @param [in] faux_vec Allocated vector object.
- * @return Newly created item or NULL on error.
- */
- void *faux_vec_add(faux_vec_t *faux_vec)
- {
- void *new_vector = NULL;
- size_t new_data_len = 0;
- void *new_item = NULL;
- assert(faux_vec);
- if (!faux_vec)
- return NULL;
- // Allocate space to hold new vector
- new_data_len = (faux_vec_len(faux_vec) + 1) * faux_vec_item_size(faux_vec);
- new_vector = realloc(faux_vec->data, new_data_len);
- assert(new_vector);
- if (!new_vector)
- return NULL;
- faux_vec->len++;
- faux_vec->data = new_vector;
- // Newly created item (it's last one)
- new_item = faux_vec_item(faux_vec, faux_vec_len(faux_vec) - 1);
- faux_bzero(new_item, faux_vec_item_size(faux_vec));
- return new_item;
- }
- /** @brief Removes item from vector by index.
- *
- * Function removes item by index and then fill hole with the following items.
- * It saves items sequence and frees vector memory.
- *
- * @param [in] faux_vec Allocated vector object.
- * @param [in] index Index of item to remove.
- * @return New number of items within vector after removing or < 0 on error.
- */
- ssize_t faux_vec_del(faux_vec_t *faux_vec, unsigned int index)
- {
- void *new_vector = NULL;
- size_t new_data_len = 0;
- assert(faux_vec);
- if (!faux_vec)
- return -1;
- if ((index + 1) > faux_vec_len(faux_vec))
- return -1;
- // It's special case when the only one item left within vector. In this
- // case we don't need to realloc() but free() the vector.
- if (faux_vec_len(faux_vec) == 1) {
- free(faux_vec->data);
- faux_vec->data = NULL;
- faux_vec->len = 0;
- return 0;
- }
- // Move following items to fill the space of deleted item
- if (index != (faux_vec_len(faux_vec) - 1)) { // Is it last item?
- void *item_to_del = faux_vec_item(faux_vec, index);
- void *next_item = faux_vec_item(faux_vec, index + 1);
- unsigned int items_to_move =
- faux_vec_len(faux_vec) - (index + 1);
- memmove(item_to_del, next_item,
- items_to_move * faux_vec_item_size(faux_vec));
- }
- // Re-allocate space to hold new vector
- faux_vec->len--;
- new_data_len = faux_vec_len(faux_vec) * faux_vec_item_size(faux_vec);
- new_vector = realloc(faux_vec->data, new_data_len);
- assert(new_vector);
- if (!new_vector)
- return -1;
- faux_vec->data = new_vector;
- return faux_vec_len(faux_vec);
- }
- /** @brief Finds item by user defined key using specified callback function.
- *
- * It iterates through the vector and try to find item with the specified key
- * value. It starts searching with specified item index and returns index of
- * found item. So it can be used to iterate all the vector with duplicate keys.
- *
- * @param [in] faux_vec Allocated vector object.
- * @param [in] matchFn Callback function to compare user key and item's data.
- * @param [in] userkey User defined key to compare item to.
- * @param [in] start_index Item's index to start searching from.
- * @return Index of found item or < 0 on error or "not found" case.
- */
- int faux_vec_find_fn(const faux_vec_t *faux_vec, faux_vec_kcmp_fn matchFn,
- const void *userkey, unsigned int start_index)
- {
- unsigned int i = 0;
- assert(faux_vec);
- if (!faux_vec)
- return -1;
- assert(userkey);
- if (!userkey)
- return -1;
- assert(matchFn);
- if (!matchFn)
- return -1;
- for (i = start_index; i < faux_vec_len(faux_vec); i++) {
- if (matchFn(userkey, faux_vec_item(faux_vec, i)) == 0)
- return i;
- }
- return -1;
- }
- /** @brief Finds item by user defined key.
- *
- * It acts like a faux_vec_find_fn() function but uses callback function
- * specified while faux_vec_new() call.
- *
- * @sa faux_vec_find_fn()
- * @sa faux_vec_new()
- * @param [in] faux_vec Allocated vector object.
- * @param [in] userkey User defined key to compare item to.
- * @param [in] start_index Item's index to start searching from.
- * @return Index of found item or < 0 on error or "not found" case.
- */
- int faux_vec_find(const faux_vec_t *faux_vec, const void *userkey,
- unsigned int start_index)
- {
- assert(faux_vec);
- if (!faux_vec)
- return -1;
- assert(faux_vec->kcmpFn);
- if (!faux_vec->kcmpFn)
- return -1;
- return faux_vec_find_fn(faux_vec, faux_vec->kcmpFn,
- userkey, start_index);
- }
- /** @brief Deletes all vector's items.
- *
- * @param [in] faux_vec Allocated vector object.
- */
- void faux_vec_del_all(faux_vec_t *faux_vec)
- {
- if (!faux_vec)
- return;
- faux_free(faux_vec->data);
- faux_vec->data = NULL;
- faux_vec->len = 0;
- }
|