diff options
| -rw-r--r-- | src/libstrongswan/Android.mk | 2 | ||||
| -rw-r--r-- | src/libstrongswan/Makefile.am | 3 | ||||
| -rw-r--r-- | src/libstrongswan/collections/array.c | 416 | ||||
| -rw-r--r-- | src/libstrongswan/collections/array.h | 194 |
4 files changed, 613 insertions, 2 deletions
diff --git a/src/libstrongswan/Android.mk b/src/libstrongswan/Android.mk index 75b501fdd..dc533a38b 100644 --- a/src/libstrongswan/Android.mk +++ b/src/libstrongswan/Android.mk @@ -6,6 +6,7 @@ LOCAL_SRC_FILES := \ library.c \ asn1/asn1.c asn1/asn1_parser.c asn1/oid.c bio/bio_reader.c bio/bio_writer.c \ collections/blocking_queue.c collections/enumerator.c collections/hashtable.c \ +collections/array.c \ collections/linked_list.c crypto/crypters/crypter.c crypto/hashers/hasher.c \ crypto/proposal/proposal_keywords.c crypto/proposal/proposal_keywords_static.c \ crypto/prfs/prf.c crypto/prfs/mac_prf.c crypto/pkcs5.c \ @@ -110,4 +111,3 @@ LOCAL_PRELINK_MODULE := false LOCAL_SHARED_LIBRARIES += libdl libvstr include $(BUILD_SHARED_LIBRARY) - diff --git a/src/libstrongswan/Makefile.am b/src/libstrongswan/Makefile.am index 567bdfe6f..bde5f710a 100644 --- a/src/libstrongswan/Makefile.am +++ b/src/libstrongswan/Makefile.am @@ -4,6 +4,7 @@ libstrongswan_la_SOURCES = \ library.c \ asn1/asn1.c asn1/asn1_parser.c asn1/oid.c bio/bio_reader.c bio/bio_writer.c \ collections/blocking_queue.c collections/enumerator.c collections/hashtable.c \ +collections/array.c \ collections/linked_list.c crypto/crypters/crypter.c crypto/hashers/hasher.c \ crypto/proposal/proposal_keywords.c crypto/proposal/proposal_keywords_static.c \ crypto/prfs/prf.c crypto/prfs/mac_prf.c crypto/pkcs5.c \ @@ -39,7 +40,7 @@ nobase_strongswan_include_HEADERS = \ library.h \ asn1/asn1.h asn1/asn1_parser.h asn1/oid.h bio/bio_reader.h bio/bio_writer.h \ collections/blocking_queue.h collections/enumerator.h collections/hashtable.h \ -collections/linked_list.h \ +collections/linked_list.h collections/array.h \ crypto/crypters/crypter.h crypto/hashers/hasher.h crypto/mac.h \ crypto/proposal/proposal_keywords.h crypto/proposal/proposal_keywords_static.h \ crypto/prfs/prf.h crypto/prfs/mac_prf.h crypto/rngs/rng.h crypto/nonce_gen.h \ diff --git a/src/libstrongswan/collections/array.c b/src/libstrongswan/collections/array.c new file mode 100644 index 000000000..d92eaacfe --- /dev/null +++ b/src/libstrongswan/collections/array.c @@ -0,0 +1,416 @@ +/* + * Copyright (C) 2013 Martin Willi + * Copyright (C) 2013 revosec AG + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2 of the License, or (at your + * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>. + * + * This program 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 General Public License + * for more details. + */ + +#include "array.h" + +/** + * Data is an allocated block, with potentially unused head and tail: + * + * "esize" each (or sizeof(void*) if esize = 0) + * /-\ /-\ /-\ /-\ /-\ /-\ + * + * +---------------+-------------------------------+---------------+ + * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l | + * +---------------+-------------------------------+---------------+ + * + * \--------------/ \-----------------------------/ \-------------/ + * unused used unused + * "head" "count" "tail" + * + */ +struct array_t { + /** number of elements currently in array (not counting head/tail) */ + u_int32_t count; + /** size of each element, 0 for a pointer based array */ + u_int16_t esize; + /** allocated but unused elements at array front */ + u_int8_t head; + /** allocated but unused elements at array end */ + u_int8_t tail; + /** array elements */ + void *data; +}; + +/** maximum number of unused head/tail elements before cleanup */ +#define ARRAY_MAX_UNUSED 32 + +/** + * Get the actual size of a number of elements + */ +static size_t get_size(array_t *array, int num) +{ + if (array->esize) + { + return array->esize * num; + } + return sizeof(void*) * num; +} + +/** + * Increase allocated but unused tail room to at least "room" + */ +static void make_tail_room(array_t *array, u_int8_t room) +{ + if (array->tail < room) + { + array->data = realloc(array->data, + get_size(array, array->count + array->head + room)); + array->tail = room; + } +} + +/** + * Increase allocated but unused head room to at least "room" + */ +static void make_head_room(array_t *array, u_int8_t room) +{ + if (array->head < room) + { + u_int8_t increase = room - array->head; + + array->data = realloc(array->data, + get_size(array, array->count + array->tail + room)); + memmove(array->data + get_size(array, increase), array->data, + get_size(array, array->count + array->tail + array->head)); + array->head = room; + } +} + +/** + * Make space for an item at index using tail room + */ +static void insert_tail(array_t *array, int idx) +{ + make_tail_room(array, 1); + /* move up all elements after idx by one */ + memmove(array->data + get_size(array, array->head + idx + 1), + array->data + get_size(array, array->head + idx), + get_size(array, array->count - idx)); + + array->tail--; + array->count++; +} + +/** + * Make space for an item at index using head room + */ +static void insert_head(array_t *array, int idx) +{ + make_head_room(array, 1); + /* move down all elements before idx by one */ + memmove(array->data + get_size(array, array->head - 1), + array->data + get_size(array, array->head), + get_size(array, idx)); + + array->head--; + array->count++; +} + +/** + * Remove an item, increase tail + */ +static void remove_tail(array_t *array, int idx) +{ + /* move all items after idx one down */ + memmove(array->data + get_size(array, idx + array->head), + array->data + get_size(array, idx + array->head + 1), + get_size(array, array->count - idx)); + array->count--; + array->tail++; +} + +/** + * Remove an item, increase head + */ +static void remove_head(array_t *array, int idx) +{ + /* move all items before idx one up */ + memmove(array->data + get_size(array, array->head + 1), + array->data + get_size(array, array->head), get_size(array, idx)); + array->count--; + array->head++; +} + +array_t *array_create(u_int esize, u_int8_t reserve) +{ + array_t *array; + + INIT(array, + .esize = esize, + .tail = reserve, + ); + if (array->tail) + { + array->data = malloc(array->tail * array->esize); + } + return array; +} + +int array_count(array_t *array) +{ + if (array) + { + return array->count; + } + return 0; +} + +void array_compress(array_t *array) +{ + if (array) + { + u_int32_t tail; + + tail = array->tail; + if (array->head) + { + memmove(array->data, array->data + get_size(array, array->head), + get_size(array, array->count + array->tail)); + tail += array->head; + array->head = 0; + } + if (tail) + { + array->data = realloc(array->data, get_size(array, array->count)); + array->tail = 0; + } + } +} + +typedef struct { + /** public enumerator interface */ + enumerator_t public; + /** enumerated array */ + array_t *array; + /** current index +1, initialized at 0 */ + int idx; +} array_enumerator_t; + +METHOD(enumerator_t, enumerate, bool, + array_enumerator_t *this, void **out) +{ + void *pos; + + if (this->idx >= this->array->count) + { + return FALSE; + } + + pos = this->array->data + + get_size(this->array, this->idx + this->array->head); + if (this->array->esize) + { + /* for element based arrays we return a pointer to the element */ + *out = pos; + } + else + { + /* for pointer based arrays we return the pointer directly */ + *out = *(void**)pos; + } + this->idx++; + return TRUE; +} + +enumerator_t* array_create_enumerator(array_t *array) +{ + array_enumerator_t *enumerator; + + if (!array) + { + return enumerator_create_empty(); + } + + INIT(enumerator, + .public = { + .enumerate = (void*)_enumerate, + .destroy = (void*)free, + }, + .array = array, + ); + return &enumerator->public; +} + +void array_remove_at(array_t *array, enumerator_t *public) +{ + array_enumerator_t *enumerator = (array_enumerator_t*)public; + + if (enumerator->idx) + { + array_remove(array, --enumerator->idx, NULL); + } +} + +void array_insert_create(array_t **array, int idx, void *ptr) +{ + if (*array == NULL) + { + *array = array_create(0, 0); + } + array_insert(*array, idx, ptr); +} + +void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator) +{ + void *ptr; + + while (enumerator->enumerate(enumerator, &ptr)) + { + array_insert(array, idx, ptr); + } + enumerator->destroy(enumerator); +} + +void array_insert(array_t *array, int idx, void *data) +{ + if (idx < 0 || idx <= array_count(array)) + { + void *pos; + + if (idx < 0) + { + idx = array_count(array); + } + + if (array->head && !array->tail) + { + insert_head(array, idx); + } + else if (array->tail && !array->head) + { + insert_tail(array, idx); + } + else if (idx > array_count(array) / 2) + { + insert_tail(array, idx); + } + else + { + insert_head(array, idx); + } + + pos = array->data + get_size(array, array->head + idx); + if (array->esize) + { + memcpy(pos, data, get_size(array, 1)); + } + else + { + /* pointer based array, copy pointer value */ + *(void**)pos = data; + } + } +} + +bool array_remove(array_t *array, int idx, void *data) +{ + if (!array) + { + return FALSE; + } + if (idx >= 0 && idx >= array_count(array)) + { + return FALSE; + } + if (idx < 0) + { + if (array_count(array) == 0) + { + return FALSE; + } + idx = array_count(array) - 1; + } + if (data) + { + memcpy(data, array->data + get_size(array, array->head + idx), + get_size(array, 1)); + } + if (idx > array_count(array) / 2) + { + remove_tail(array, idx); + } + else + { + remove_head(array, idx); + } + if (array->head + array->tail > ARRAY_MAX_UNUSED) + { + array_compress(array); + } + return TRUE; +} + +void array_invoke(array_t *array, array_callback_t cb, void *user) +{ + if (array) + { + void *obj; + int i; + + for (i = array->head; i < array->count + array->head; i++) + { + obj = array->data + get_size(array, i); + if (!array->esize) + { + /* dereference if we store store pointers */ + obj = *(void**)obj; + } + cb(obj, i - array->head, user); + } + } +} + +void array_invoke_offset(array_t *array, size_t offset) +{ + if (array) + { + void (*method)(void *data); + void *obj; + int i; + + for (i = array->head; i < array->count + array->head; i++) + { + obj = array->data + get_size(array, i); + if (!array->esize) + { + /* dereference if we store store pointers */ + obj = *(void**)obj; + } + method = *(void**)(obj + offset); + method(obj); + } + } +} + +void array_destroy(array_t *array) +{ + if (array) + { + free(array->data); + free(array); + } +} + +void array_destroy_function(array_t *array, array_callback_t cb, void *user) +{ + array_invoke(array, cb, user); + array_destroy(array); +} + +void array_destroy_offset(array_t *array, size_t offset) +{ + array_invoke_offset(array, offset); + array_destroy(array); +} diff --git a/src/libstrongswan/collections/array.h b/src/libstrongswan/collections/array.h new file mode 100644 index 000000000..3e6180b54 --- /dev/null +++ b/src/libstrongswan/collections/array.h @@ -0,0 +1,194 @@ +/* + * Copyright (C) 2013 Martin Willi + * Copyright (C) 2013 revosec AG + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2 of the License, or (at your + * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>. + * + * This program 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 General Public License + * for more details. + */ + +/** + * @defgroup array array + * @{ @ingroup collections + */ + +#ifndef ARRAY_H_ +#define ARRAY_H_ + +#include <collections/enumerator.h> + +/** + * Variable sized array with fixed size elements. + * + * An array is a primitive object with associated functions to avoid the + * overhead of an object with methods. It is efficient in memory usage, but + * less effecient than a linked list in manipulating elements. + */ +typedef struct array_t array_t; + +typedef enum array_idx_t array_idx_t; + +/** + * Special array index values for insert/remove. + */ +enum array_idx_t { + ARRAY_HEAD = 0, + ARRAY_TAIL = -1, +}; + +/** + * Callback function invoked for each array element. + * + * Data is a pointer to the array element. If this is a pointer based array, + * (esize is zero), data is the pointer itself. + * + * @param data pointer to array data, or the pointer itself + * @param idx array index + * @param user user data passed with callback + */ +typedef void (*array_callback_t)(void *data, int idx, void *user); + +/** + * Create a array instance. + * + * Elements get tight packed to each other. If any alignment is required, pass + * appropriate padding to each element. The reserved space does not affect + * array_count(), but just preallocates buffer space. + * + * @param esize element size for this array, use 0 for a pointer array + * @param reserve number of items to allocate space for + * @return array instance + */ +array_t *array_create(u_int esize, u_int8_t reserve); + +/** + * Get the number of elements currently in the array. + * + * @return number of elements + */ +int array_count(array_t *array); + +/** + * Compress an array, remove unused head/tail space. + * + * @param array array to compress, or NULL + */ +void array_compress(array_t *array); + +/** + * Create an enumerator over an array. + * + * The enumerater enumerates directly over the array element (pass a pointer to + * element types), unless the array is pointer based. If zero is passed as + * element size during construction, the enumerator enumerates over the + * deferenced pointer values. + * + * @param array array to create enumerator for, or NULL + * @return enumerator, over elements or pointers + */ +enumerator_t* array_create_enumerator(array_t *array); + +/** + * Remove an element at enumerator position. + * + * @param array array to remove element in + * @param enumerator enumerator position, from array_create_enumerator() + */ +void array_remove_at(array_t *array, enumerator_t *enumerator); + +/** + * Insert an element to an array. + * + * If the array is pointer based (esize = 0), the pointer itself is appended. + * Otherwise the element gets copied from the pointer. + * The idx must be either within array_count() or one above to append the item. + * Passing -1 has the same effect as passing array_count(), i.e. appends the + * item. It is always valid to pass idx 0 to prepend the item. + * + * @param array array to append element to + * @param idx index to insert item at + * @param data pointer to array element to copy + */ +void array_insert(array_t *array, int idx, void *data); + +/** + * Create an pointer based array if it does not exist, insert pointer. + * + * This is a convenience function for insert a pointer and implicitly + * create a pointer based array if array is NULL. Array is set the the newly + * created array, if any. + * + * @param array pointer to array reference, potentially NULL + * @param idx index to insert item at + * @param ptr pointer to append + */ +void array_insert_create(array_t **array, int idx, void *ptr); + +/** + * Insert all items from an enumerator to an array. + * + * @param array array to add items to + * @param idx index to insert each item with + * @param enumerator enumerator over void*, gets destroyed + */ +void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator); + +/** + * Remove an element from the array end. + * + * If data is given, the element is copied to that position. + * + * @param array array to remove element from, or NULL + * @param data data to copy element to, or NULL + * @return TRUE if idx existed and item removed + */ +bool array_remove(array_t *array, int idx, void *data); + +/** + * Invoke a callback for all array members. + * + * @param array array to traverse, or NULL + * @param cb callback function to invoke each element with + * @param user user data to pass to callback + */ +void array_invoke(array_t *array, array_callback_t cb, void *user); + +/** + * Invoke a method of each element defined with offset. + * + * @param array array to traverse, or NULL + * @param offset offset of element method, use offsetof() + */ +void array_invoke_offset(array_t *array, size_t offset); + +/** + * Destroy an array. + * + * @param array array to destroy, or NULL + */ +void array_destroy(array_t *array); + +/** + * Destroy an array, call a function to clean up all elements. + * + * @param array array to destroy, or NULL + * @param cb callback function to free element data + * @param user user data to pass to callback + */ +void array_destroy_function(array_t *array, array_callback_t cb, void *user); + +/** + * Destroy an array, call element method defined with offset. + * + * @param array array to destroy, or NULL + * @param offset offset of element method, use offsetof() + */ +void array_destroy_offset(array_t *array, size_t offset); + +#endif /** ARRAY_H_ @}*/ |