diff options
Diffstat (limited to 'src/libstrongswan/collections')
| -rw-r--r-- | src/libstrongswan/collections/blocking_queue.c | 129 | ||||
| -rw-r--r-- | src/libstrongswan/collections/blocking_queue.h | 97 | ||||
| -rw-r--r-- | src/libstrongswan/collections/enumerator.c | 560 | ||||
| -rw-r--r-- | src/libstrongswan/collections/enumerator.h | 159 | ||||
| -rw-r--r-- | src/libstrongswan/collections/hashtable.c | 444 | ||||
| -rw-r--r-- | src/libstrongswan/collections/hashtable.h | 138 | ||||
| -rw-r--r-- | src/libstrongswan/collections/linked_list.c | 615 | ||||
| -rw-r--r-- | src/libstrongswan/collections/linked_list.h | 319 |
8 files changed, 2461 insertions, 0 deletions
diff --git a/src/libstrongswan/collections/blocking_queue.c b/src/libstrongswan/collections/blocking_queue.c new file mode 100644 index 000000000..da3356970 --- /dev/null +++ b/src/libstrongswan/collections/blocking_queue.c @@ -0,0 +1,129 @@ +/* + * Copyright (C) 2012 Tobias Brunner + * Copyright (C) 2012 Giuliano Grassi + * Copyright (C) 2012 Ralf Sager + * Hochschule fuer Technik Rapperswil + * + * 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 "blocking_queue.h" + +#include <threading/mutex.h> +#include <threading/thread.h> +#include <threading/condvar.h> +#include <collections/linked_list.h> + +typedef struct private_blocking_queue_t private_blocking_queue_t; + +/** + * Private data of a blocking_queue_t object. + */ +struct private_blocking_queue_t { + + /** + * Public part + */ + blocking_queue_t public; + + /** + * Linked list containing all items in the queue + */ + linked_list_t *list; + + /** + * Mutex used to synchronize access to the queue + */ + mutex_t *mutex; + + /** + * Condvar used to wait for items + */ + condvar_t *condvar; + +}; + +METHOD(blocking_queue_t, enqueue, void, + private_blocking_queue_t *this, void *item) +{ + this->mutex->lock(this->mutex); + this->list->insert_first(this->list, item); + this->condvar->signal(this->condvar); + this->mutex->unlock(this->mutex); +} + +METHOD(blocking_queue_t, dequeue, void*, + private_blocking_queue_t *this) +{ + bool oldstate; + void *item; + + + this->mutex->lock(this->mutex); + thread_cleanup_push((thread_cleanup_t)this->mutex->unlock, this->mutex); + /* ensure that a canceled thread does not dequeue any items */ + thread_cancellation_point(); + while (this->list->remove_last(this->list, &item) != SUCCESS) + { + oldstate = thread_cancelability(TRUE); + this->condvar->wait(this->condvar, this->mutex); + thread_cancelability(oldstate); + } + thread_cleanup_pop(TRUE); + return item; +} + +METHOD(blocking_queue_t, destroy, void, + private_blocking_queue_t *this) +{ + this->list->destroy(this->list); + this->condvar->destroy(this->condvar); + this->mutex->destroy(this->mutex); + free(this); +} + +METHOD(blocking_queue_t, destroy_offset, void, + private_blocking_queue_t *this, size_t offset) +{ + this->list->invoke_offset(this->list, offset); + destroy(this); +} + +METHOD(blocking_queue_t, destroy_function, void, + private_blocking_queue_t *this, void (*fn)(void*)) +{ + this->list->invoke_function(this->list, (linked_list_invoke_t)fn); + destroy(this); +} + +/* + * Described in header. + */ +blocking_queue_t *blocking_queue_create() +{ + private_blocking_queue_t *this; + + INIT(this, + .public = { + .enqueue = _enqueue, + .dequeue = _dequeue, + .destroy = _destroy, + .destroy_offset = _destroy_offset, + .destroy_function = _destroy_function, + }, + .list = linked_list_create(), + .mutex = mutex_create(MUTEX_TYPE_DEFAULT), + .condvar = condvar_create(CONDVAR_TYPE_DEFAULT), + ); + + return &this->public; +} + diff --git a/src/libstrongswan/collections/blocking_queue.h b/src/libstrongswan/collections/blocking_queue.h new file mode 100644 index 000000000..9b014f719 --- /dev/null +++ b/src/libstrongswan/collections/blocking_queue.h @@ -0,0 +1,97 @@ +/* + * Copyright (C) 2012 Tobias Brunner + * Copyright (C) 2012 Giuliano Grassi + * Copyright (C) 2012 Ralf Sager + * Hochschule fuer Technik Rapperswil + * + * 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 blocking_queue blocking_queue + * @{ @ingroup collections + */ + +#ifndef BLOCKING_QUEUE_H_ +#define BLOCKING_QUEUE_H_ + +typedef struct blocking_queue_t blocking_queue_t; + +#include <library.h> + +/** + * Class implementing a synchronized blocking queue based on linked_list_t + */ +struct blocking_queue_t { + + /** + * Inserts a new item at the tail of the queue + * + * @param item item to insert in queue + */ + void (*enqueue)(blocking_queue_t *this, void *item); + + /** + * Removes the first item in the queue and returns its value. + * If the queue is empty, this call blocks until a new item is inserted. + * + * @note This is a thread cancellation point + * + * @return removed item + */ + void *(*dequeue)(blocking_queue_t *this); + + /** + * Destroys a blocking_queue_t object. + * + * @note No thread must wait in dequeue() when this function is called + */ + void (*destroy)(blocking_queue_t *this); + + /** + * Destroys a queue and its objects using the given destructor. + * + * If a queue and the contained objects should be destroyed, use + * destroy_offset. The supplied offset specifies the destructor to + * call on each object. The offset may be calculated using the offsetof + * macro, e.g.: queue->destroy_offset(queue, offsetof(object_t, destroy)); + * + * @note No thread must wait in dequeue() when this function is called + * + * @param offset offset of the objects destructor + */ + void (*destroy_offset)(blocking_queue_t *this, size_t offset); + + /** + * Destroys a queue and its objects using a cleanup function. + * + * If a queue and its contents should get destroyed using a specific + * cleanup function, use destroy_function. This is useful when the + * list contains malloc()-ed blocks which should get freed, + * e.g.: queue->destroy_function(queue, free); + * + * @note No thread must wait in dequeue() when this function is called + * + * @param function function to call on each object + */ + void (*destroy_function)(blocking_queue_t *this, void (*)(void*)); + +}; + +/** + * Creates an empty queue object. + * + * @return blocking_queue_t object. + */ +blocking_queue_t *blocking_queue_create(); + +#endif /** BLOCKING_QUEUE_H_ @}*/ + diff --git a/src/libstrongswan/collections/enumerator.c b/src/libstrongswan/collections/enumerator.c new file mode 100644 index 000000000..f80cdabd2 --- /dev/null +++ b/src/libstrongswan/collections/enumerator.c @@ -0,0 +1,560 @@ +/* + * Copyright (C) 2008 Tobias Brunner + * Copyright (C) 2007 Martin Willi + * Hochschule fuer Technik Rapperswil + * + * 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 "enumerator.h" + +#include <sys/types.h> +#include <sys/stat.h> +#include <unistd.h> +#include <limits.h> +#include <stdio.h> +#include <dirent.h> +#include <errno.h> +#include <string.h> + +#include <utils/debug.h> + +/** + * Implementation of enumerator_create_empty().enumerate + */ +static bool enumerate_empty(enumerator_t *enumerator, ...) +{ + return FALSE; +} + +/** + * See header + */ +enumerator_t* enumerator_create_empty() +{ + enumerator_t *this = malloc_thing(enumerator_t); + this->enumerate = enumerate_empty; + this->destroy = (void*)free; + return this; +} + +/** + * Enumerator implementation for directory enumerator + */ +typedef struct { + /** implements enumerator_t */ + enumerator_t public; + /** directory handle */ + DIR *dir; + /** absolute path of current file */ + char full[PATH_MAX]; + /** where directory part of full ends and relative file gets written */ + char *full_end; +} dir_enum_t; + +/** + * Implementation of enumerator_create_directory().destroy + */ +static void destroy_dir_enum(dir_enum_t *this) +{ + closedir(this->dir); + free(this); +} + +/** + * Implementation of enumerator_create_directory().enumerate + */ +static bool enumerate_dir_enum(dir_enum_t *this, char **relative, + char **absolute, struct stat *st) +{ + struct dirent *entry = readdir(this->dir); + size_t remaining; + int len; + + if (!entry) + { + return FALSE; + } + if (streq(entry->d_name, ".") || streq(entry->d_name, "..")) + { + return enumerate_dir_enum(this, relative, absolute, st); + } + if (relative) + { + *relative = entry->d_name; + } + if (absolute || st) + { + remaining = sizeof(this->full) - (this->full_end - this->full); + len = snprintf(this->full_end, remaining, "%s", entry->d_name); + if (len < 0 || len >= remaining) + { + DBG1(DBG_LIB, "buffer too small to enumerate file '%s'", + entry->d_name); + return FALSE; + } + if (absolute) + { + *absolute = this->full; + } + if (st) + { + if (stat(this->full, st)) + { + DBG1(DBG_LIB, "stat() on '%s' failed: %s", this->full, + strerror(errno)); + return FALSE; + } + } + } + return TRUE; +} + +/** + * See header + */ +enumerator_t* enumerator_create_directory(const char *path) +{ + int len; + dir_enum_t *this = malloc_thing(dir_enum_t); + this->public.enumerate = (void*)enumerate_dir_enum; + this->public.destroy = (void*)destroy_dir_enum; + + if (*path == '\0') + { + path = "./"; + } + len = snprintf(this->full, sizeof(this->full)-1, "%s", path); + if (len < 0 || len >= sizeof(this->full)-1) + { + DBG1(DBG_LIB, "path string '%s' too long", path); + free(this); + return NULL; + } + /* append a '/' if not already done */ + if (this->full[len-1] != '/') + { + this->full[len++] = '/'; + this->full[len] = '\0'; + } + this->full_end = &this->full[len]; + + this->dir = opendir(path); + if (this->dir == NULL) + { + DBG1(DBG_LIB, "opening directory '%s' failed: %s", path, strerror(errno)); + free(this); + return NULL; + } + return &this->public; +} + +/** + * Enumerator implementation for directory enumerator + */ +typedef struct { + /** implements enumerator_t */ + enumerator_t public; + /** string to parse */ + char *string; + /** current position */ + char *pos; + /** separater chars */ + const char *sep; + /** trim chars */ + const char *trim; +} token_enum_t; + +/** + * Implementation of enumerator_create_token().destroy + */ +static void destroy_token_enum(token_enum_t *this) +{ + free(this->string); + free(this); +} + +/** + * Implementation of enumerator_create_token().enumerate + */ +static bool enumerate_token_enum(token_enum_t *this, char **token) +{ + const char *sep, *trim; + char *pos = NULL, *tmp; + bool last = FALSE; + + /* trim leading characters/separators */ + while (*this->pos) + { + trim = this->trim; + while (*trim) + { + if (*trim == *this->pos) + { + this->pos++; + break; + } + trim++; + } + sep = this->sep; + while (*sep) + { + if (*sep == *this->pos) + { + this->pos++; + break; + } + sep++; + } + if (!*trim && !*sep) + { + break; + } + } + + switch (*this->pos) + { + case '"': + case '\'': + { + /* read quoted token */ + tmp = strchr(this->pos + 1, *this->pos); + if (tmp) + { + *token = this->pos + 1; + *tmp = '\0'; + this->pos = tmp + 1; + return TRUE; + } + /* unterminated string, FALL-THROUGH */ + } + default: + { + /* find nearest separator */ + sep = this->sep; + while (*sep) + { + tmp = strchr(this->pos, *sep); + if (tmp && (pos == NULL || tmp < pos)) + { + pos = tmp; + } + sep++; + } + *token = this->pos; + if (pos) + { + *pos = '\0'; + this->pos = pos + 1; + } + else + { + last = TRUE; + pos = this->pos = strchr(this->pos, '\0'); + } + break; + } + } + + /* trim trailing characters/separators */ + pos--; + while (pos >= *token) + { + trim = this->trim; + while (*trim) + { + if (*trim == *pos) + { + *(pos--) = '\0'; + break; + } + trim++; + } + sep = this->sep; + while (*sep) + { + if (*sep == *pos) + { + *(pos--) = '\0'; + break; + } + sep++; + } + if (!*trim && !*sep) + { + break; + } + } + + if (!last || pos >= *token) + { + return TRUE; + } + return FALSE; +} + +/** + * See header + */ +enumerator_t* enumerator_create_token(const char *string, const char *sep, + const char *trim) +{ + token_enum_t *enumerator = malloc_thing(token_enum_t); + + enumerator->public.enumerate = (void*)enumerate_token_enum; + enumerator->public.destroy = (void*)destroy_token_enum; + enumerator->string = strdup(string); + enumerator->pos = enumerator->string; + enumerator->sep = sep; + enumerator->trim = trim; + + return &enumerator->public; +} + +/** + * enumerator for nested enumerations + */ +typedef struct { + /* implements enumerator_t */ + enumerator_t public; + /* outer enumerator */ + enumerator_t *outer; + /* inner enumerator */ + enumerator_t *inner; + /* constructor for inner enumerator */ + enumerator_t *(*create_inner)(void *outer, void *data); + /* data to pass to constructor above */ + void *data; + /* destructor for data */ + void (*destroy_data)(void *data); +} nested_enumerator_t; + + +/** + * Implementation of enumerator_create_nested().enumerate() + */ +static bool enumerate_nested(nested_enumerator_t *this, void *v1, void *v2, + void *v3, void *v4, void *v5) +{ + while (TRUE) + { + while (this->inner == NULL) + { + void *outer; + + if (!this->outer->enumerate(this->outer, &outer)) + { + return FALSE; + } + this->inner = this->create_inner(outer, this->data); + } + if (this->inner->enumerate(this->inner, v1, v2, v3, v4, v5)) + { + return TRUE; + } + this->inner->destroy(this->inner); + this->inner = NULL; + } +} + +/** + * Implementation of enumerator_create_nested().destroy() + **/ +static void destroy_nested(nested_enumerator_t *this) +{ + if (this->destroy_data) + { + this->destroy_data(this->data); + } + DESTROY_IF(this->inner); + this->outer->destroy(this->outer); + free(this); +} + +/** + * See header + */ +enumerator_t *enumerator_create_nested(enumerator_t *outer, + enumerator_t *(inner_constructor)(void *outer, void *data), + void *data, void (*destroy_data)(void *data)) +{ + nested_enumerator_t *enumerator = malloc_thing(nested_enumerator_t); + + enumerator->public.enumerate = (void*)enumerate_nested; + enumerator->public.destroy = (void*)destroy_nested; + enumerator->outer = outer; + enumerator->inner = NULL; + enumerator->create_inner = (void*)inner_constructor; + enumerator->data = data; + enumerator->destroy_data = destroy_data; + + return &enumerator->public; +} + +/** + * enumerator for filtered enumerator + */ +typedef struct { + enumerator_t public; + enumerator_t *unfiltered; + void *data; + bool (*filter)(void *data, ...); + void (*destructor)(void *data); +} filter_enumerator_t; + +/** + * Implementation of enumerator_create_filter().destroy + */ +static void destroy_filter(filter_enumerator_t *this) +{ + if (this->destructor) + { + this->destructor(this->data); + } + this->unfiltered->destroy(this->unfiltered); + free(this); +} + +/** + * Implementation of enumerator_create_filter().enumerate + */ +static bool enumerate_filter(filter_enumerator_t *this, void *o1, void *o2, + void *o3, void *o4, void *o5) +{ + void *i1, *i2, *i3, *i4, *i5; + + while (this->unfiltered->enumerate(this->unfiltered, &i1, &i2, &i3, &i4, &i5)) + { + if (this->filter(this->data, &i1, o1, &i2, o2, &i3, o3, &i4, o4, &i5, o5)) + { + return TRUE; + } + } + return FALSE; +} + +/** + * see header + */ +enumerator_t *enumerator_create_filter(enumerator_t *unfiltered, + bool (*filter)(void *data, ...), + void *data, void (*destructor)(void *data)) +{ + filter_enumerator_t *this = malloc_thing(filter_enumerator_t); + + this->public.enumerate = (void*)enumerate_filter; + this->public.destroy = (void*)destroy_filter; + this->unfiltered = unfiltered; + this->filter = filter; + this->data = data; + this->destructor = destructor; + + return &this->public; +} + +/** + * enumerator for cleaner enumerator + */ +typedef struct { + enumerator_t public; + enumerator_t *wrapped; + void (*cleanup)(void *data); + void *data; +} cleaner_enumerator_t; + +/** + * Implementation of enumerator_create_cleanup().destroy + */ +static void destroy_cleaner(cleaner_enumerator_t *this) +{ + this->cleanup(this->data); + this->wrapped->destroy(this->wrapped); + free(this); +} + +/** + * Implementation of enumerator_create_cleaner().enumerate + */ +static bool enumerate_cleaner(cleaner_enumerator_t *this, void *v1, void *v2, + void *v3, void *v4, void *v5) +{ + return this->wrapped->enumerate(this->wrapped, v1, v2, v3, v4, v5); +} + +/** + * see header + */ +enumerator_t *enumerator_create_cleaner(enumerator_t *wrapped, + void (*cleanup)(void *data), void *data) +{ + cleaner_enumerator_t *this = malloc_thing(cleaner_enumerator_t); + + this->public.enumerate = (void*)enumerate_cleaner; + this->public.destroy = (void*)destroy_cleaner; + this->wrapped = wrapped; + this->cleanup = cleanup; + this->data = data; + + return &this->public; +} + +/** + * enumerator for single enumerator + */ +typedef struct { + enumerator_t public; + void *item; + void (*cleanup)(void *item); + bool done; +} single_enumerator_t; + +/** + * Implementation of enumerator_create_single().destroy + */ +static void destroy_single(single_enumerator_t *this) +{ + if (this->cleanup) + { + this->cleanup(this->item); + } + free(this); +} + +/** + * Implementation of enumerator_create_single().enumerate + */ +static bool enumerate_single(single_enumerator_t *this, void **item) +{ + if (this->done) + { + return FALSE; + } + *item = this->item; + this->done = TRUE; + return TRUE; +} + +/** + * see header + */ +enumerator_t *enumerator_create_single(void *item, void (*cleanup)(void *item)) +{ + single_enumerator_t *this = malloc_thing(single_enumerator_t); + + this->public.enumerate = (void*)enumerate_single; + this->public.destroy = (void*)destroy_single; + this->item = item; + this->cleanup = cleanup; + this->done = FALSE; + + return &this->public; +} + diff --git a/src/libstrongswan/collections/enumerator.h b/src/libstrongswan/collections/enumerator.h new file mode 100644 index 000000000..299373a3e --- /dev/null +++ b/src/libstrongswan/collections/enumerator.h @@ -0,0 +1,159 @@ +/* + * Copyright (C) 2007 Martin Willi + * Hochschule fuer Technik Rapperswil + * + * 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 enumerator enumerator + * @{ @ingroup collections + */ + +#ifndef ENUMERATOR_H_ +#define ENUMERATOR_H_ + +typedef struct enumerator_t enumerator_t; + +#include <utils/utils.h> + +/** + * Enumerator interface, allows enumeration over collections. + */ +struct enumerator_t { + + /** + * Enumerate collection. + * + * The enumerate function takes a variable argument list containing + * pointers where the enumerated values get written. + * + * @param ... variable list of enumerated items, implementation dependent + * @return TRUE if pointers returned + */ + bool (*enumerate)(enumerator_t *this, ...); + + /** + * Destroy a enumerator instance. + */ + void (*destroy)(enumerator_t *this); +}; + +/** + * Create an enumerator which enumerates over nothing + * + * @return an enumerator over no values + */ +enumerator_t* enumerator_create_empty(); + +/** + * Create an enumerator which enumerates over a single item + * + * @param item item to enumerate + * @param cleanup cleanup function called on destroy with the item + * @return an enumerator over a single value + */ +enumerator_t *enumerator_create_single(void *item, void (*cleanup)(void *item)); + +/** + * Create an enumerator over files/subdirectories in a directory. + * + * This enumerator_t.enumerate() function returns a (to the directory) relative + * filename (as a char*), an absolute filename (as a char*) and a file status + * (to a struct stat), which all may be NULL. "." and ".." entries are + * skipped. Example: + * + * @code + char *rel, *abs; + struct stat st; + enumerator_t *e; + + e = enumerator_create_directory("/tmp"); + if (e) + { + while (e->enumerate(e, &rel, &abs, &st)) + { + if (S_ISDIR(st.st_mode) && *rel != '.') + { + printf("%s\n", abs); + } + } + e->destroy(e); + } + @endcode + * + * @param path path of the directory + * @return the directory enumerator, NULL on failure + */ +enumerator_t* enumerator_create_directory(const char *path); + +/** + * Create an enumerator over tokens of a string. + * + * Tokens are separated by one of the characters in sep and trimmed by the + * characters in trim. + * + * @param string string to parse + * @param sep separator characters + * @param trim characters to trim from tokens + * @return enumerator over char* tokens + */ +enumerator_t* enumerator_create_token(const char *string, const char *sep, + const char *trim); + +/** + * Creates an enumerator which enumerates over enumerated enumerators :-). + * + * The variable argument list of enumeration values is limit to 5. + * + * @param outer outer enumerator + * @param inner_constructor constructor to inner enumerator + * @param data data to pass to each inner_constructor call + * @param destroy_data destructor to pass to data + * @return the nested enumerator + */ +enumerator_t *enumerator_create_nested(enumerator_t *outer, + enumerator_t *(*inner_constructor)(void *outer, void *data), + void *data, void (*destroy_data)(void *data)); + +/** + * Creates an enumerator which filters output of another enumerator. + * + * The filter function receives the user supplied "data" followed by a + * unfiltered enumeration item, followed by an output pointer where to write + * the filtered data. Then the next input/output pair follows. + * It returns TRUE to deliver the + * values to the caller of enumerate(), FALSE to filter this enumeration. + * + * The variable argument list of enumeration values is limit to 5. + * + * @param unfiltered unfiltered enumerator to wrap, gets destroyed + * @param filter filter function + * @param data user data to supply to filter + * @param destructor destructor function to clean up data after use + * @return the filtered enumerator + */ +enumerator_t *enumerator_create_filter(enumerator_t *unfiltered, + bool (*filter)(void *data, ...), + void *data, void (*destructor)(void *data)); + +/** + * Create an enumerator wrapper which does a cleanup on destroy. + * + * @param wrapped wrapped enumerator + * @param cleanup cleanup function called on destroy + * @param data user data to supply to cleanup + * @return the enumerator with cleanup + */ +enumerator_t *enumerator_create_cleaner(enumerator_t *wrapped, + void (*cleanup)(void *data), void *data); + +#endif /** ENUMERATOR_H_ @}*/ diff --git a/src/libstrongswan/collections/hashtable.c b/src/libstrongswan/collections/hashtable.c new file mode 100644 index 000000000..d181d8ec8 --- /dev/null +++ b/src/libstrongswan/collections/hashtable.c @@ -0,0 +1,444 @@ +/* + * Copyright (C) 2008-2012 Tobias Brunner + * Hochschule fuer Technik Rapperswil + * + * 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 "hashtable.h" + +/** The maximum capacity of the hash table (MUST be a power of 2) */ +#define MAX_CAPACITY (1 << 30) + +typedef struct pair_t pair_t; + +/** + * This pair holds a pointer to the key and value it represents. + */ +struct pair_t { + /** + * Key of a hash table item. + */ + void *key; + + /** + * Value of a hash table item. + */ + void *value; + + /** + * Cached hash (used in case of a resize). + */ + u_int hash; + + /** + * Next pair in an overflow list. + */ + pair_t *next; +}; + +/** + * Creates an empty pair object. + */ +static inline pair_t *pair_create(void *key, void *value, u_int hash) +{ + pair_t *this; + + INIT(this, + .key = key, + .value = value, + .hash = hash, + ); + + return this; +} + +typedef struct private_hashtable_t private_hashtable_t; + +/** + * Private data of a hashtable_t object. + * + */ +struct private_hashtable_t { + /** + * Public part of hash table. + */ + hashtable_t public; + + /** + * The number of items in the hash table. + */ + u_int count; + + /** + * The current capacity of the hash table (always a power of 2). + */ + u_int capacity; + + /** + * The current mask to calculate the row index (capacity - 1). + */ + u_int mask; + + /** + * The load factor. + */ + float load_factor; + + /** + * The actual table. + */ + pair_t **table; + + /** + * The hashing function. + */ + hashtable_hash_t hash; + + /** + * The equality function. + */ + hashtable_equals_t equals; +}; + +typedef struct private_enumerator_t private_enumerator_t; + +/** + * hash table enumerator implementation + */ +struct private_enumerator_t { + + /** + * implements enumerator interface + */ + enumerator_t enumerator; + + /** + * associated hash table + */ + private_hashtable_t *table; + + /** + * current row index + */ + u_int row; + + /** + * number of remaining items in hashtable + */ + u_int count; + + /** + * current pair + */ + pair_t *current; + + /** + * previous pair (used by remove_at) + */ + pair_t *prev; + +}; + +/** + * This function returns the next-highest power of two for the given number. + * The algorithm works by setting all bits on the right-hand side of the most + * significant 1 to 1 and then increments the whole number so it rolls over + * to the nearest power of two. Note: returns 0 for n == 0 + */ +static u_int get_nearest_powerof2(u_int n) +{ + u_int i; + + --n; + for (i = 1; i < sizeof(u_int) * 8; i <<= 1) + { + n |= n >> i; + } + return ++n; +} + +/** + * Init hash table parameters + */ +static void init_hashtable(private_hashtable_t *this, u_int capacity) +{ + capacity = max(1, min(capacity, MAX_CAPACITY)); + this->capacity = get_nearest_powerof2(capacity); + this->mask = this->capacity - 1; + this->load_factor = 0.75; + + this->table = calloc(this->capacity, sizeof(pair_t*)); +} + +/** + * Double the size of the hash table and rehash all the elements. + */ +static void rehash(private_hashtable_t *this) +{ + pair_t **old_table; + u_int row, old_capacity; + + if (this->capacity >= MAX_CAPACITY) + { + return; + } + + old_capacity = this->capacity; + old_table = this->table; + + init_hashtable(this, old_capacity << 1); + + for (row = 0; row < old_capacity; row++) + { + pair_t *pair, *next; + u_int new_row; + + pair = old_table[row]; + while (pair) + { /* insert pair at the front of new bucket*/ + next = pair->next; + new_row = pair->hash & this->mask; + pair->next = this->table[new_row]; + this->table[new_row] = pair; + pair = next; + } + } + free(old_table); +} + +METHOD(hashtable_t, put, void*, + private_hashtable_t *this, void *key, void *value) +{ + void *old_value = NULL; + pair_t *pair; + u_int hash, row; + + hash = this->hash(key); + row = hash & this->mask; + pair = this->table[row]; + while (pair) + { /* search existing bucket for key */ + if (this->equals(key, pair->key)) + { + old_value = pair->value; + pair->value = value; + pair->key = key; + break; + } + pair = pair->next; + } + if (!pair) + { /* insert at the front of bucket */ + pair = pair_create(key, value, hash); + pair->next = this->table[row]; + this->table[row] = pair; + this->count++; + } + if (this->count >= this->capacity * this->load_factor) + { + rehash(this); + } + return old_value; +} + +static void *get_internal(private_hashtable_t *this, void *key, + hashtable_equals_t equals) +{ + void *value = NULL; + pair_t *pair; + + if (!this->count) + { /* no need to calculate the hash */ + return NULL; + } + + pair = this->table[this->hash(key) & this->mask]; + while (pair) + { + if (equals(key, pair->key)) + { + value = pair->value; + break; + } + pair = pair->next; + } + return value; +} + +METHOD(hashtable_t, get, void*, + private_hashtable_t *this, void *key) +{ + return get_internal(this, key, this->equals); +} + +METHOD(hashtable_t, get_match, void*, + private_hashtable_t *this, void *key, hashtable_equals_t match) +{ + return get_internal(this, key, match); +} + +METHOD(hashtable_t, remove_, void*, + private_hashtable_t *this, void *key) +{ + void *value = NULL; + pair_t *pair, *prev = NULL; + u_int row; + + row = this->hash(key) & this->mask; + pair = this->table[row]; + while (pair) + { + if (this->equals(key, pair->key)) + { + if (prev) + { + prev->next = pair->next; + } + else + { + this->table[row] = pair->next; + } + value = pair->value; + this->count--; + free(pair); + break; + } + prev = pair; + pair = pair->next; + } + return value; +} + +METHOD(hashtable_t, remove_at, void, + private_hashtable_t *this, private_enumerator_t *enumerator) +{ + if (enumerator->table == this && enumerator->current) + { + pair_t *current = enumerator->current; + if (enumerator->prev) + { + enumerator->prev->next = current->next; + } + else + { + this->table[enumerator->row] = current->next; + } + enumerator->current = enumerator->prev; + free(current); + this->count--; + } +} + +METHOD(hashtable_t, get_count, u_int, + private_hashtable_t *this) +{ + return this->count; +} + +METHOD(enumerator_t, enumerate, bool, + private_enumerator_t *this, void **key, void **value) +{ + while (this->count && this->row < this->table->capacity) + { + this->prev = this->current; + if (this->current) + { + this->current = this->current->next; + } + else + { + this->current = this->table->table[this->row]; + } + if (this->current) + { + if (key) + { + *key = this->current->key; + } + if (value) + { + *value = this->current->value; + } + this->count--; + return TRUE; + } + this->row++; + } + return FALSE; +} + +METHOD(hashtable_t, create_enumerator, enumerator_t*, + private_hashtable_t *this) +{ + private_enumerator_t *enumerator; + + INIT(enumerator, + .enumerator = { + .enumerate = (void*)_enumerate, + .destroy = (void*)free, + }, + .table = this, + .count = this->count, + ); + + return &enumerator->enumerator; +} + +METHOD(hashtable_t, destroy, void, + private_hashtable_t *this) +{ + pair_t *pair, *next; + u_int row; + + for (row = 0; row < this->capacity; row++) + { + pair = this->table[row]; + while (pair) + { + next = pair->next; + free(pair); + pair = next; + } + } + free(this->table); + free(this); +} + +/* + * Described in header. + */ +hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals, + u_int capacity) +{ + private_hashtable_t *this; + + INIT(this, + .public = { + .put = _put, + .get = _get, + .get_match = _get_match, + .remove = _remove_, + .remove_at = (void*)_remove_at, + .get_count = _get_count, + .create_enumerator = _create_enumerator, + .destroy = _destroy, + }, + .hash = hash, + .equals = equals, + ); + + init_hashtable(this, capacity); + + return &this->public; +} + diff --git a/src/libstrongswan/collections/hashtable.h b/src/libstrongswan/collections/hashtable.h new file mode 100644 index 000000000..e38850ded --- /dev/null +++ b/src/libstrongswan/collections/hashtable.h @@ -0,0 +1,138 @@ +/* + * Copyright (C) 2008-2012 Tobias Brunner + * Hochschule fuer Technik Rapperswil + * + * 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 hashtable hashtable + * @{ @ingroup collections + */ + +#ifndef HASHTABLE_H_ +#define HASHTABLE_H_ + +#include <collections/enumerator.h> + +typedef struct hashtable_t hashtable_t; + +/** + * Prototype for a function that computes the hash code from the given key. + * + * @param key key to hash + * @return hash code + */ +typedef u_int (*hashtable_hash_t)(void *key); + +/** + * Prototype for a function that compares the two keys for equality. + * + * @param key first key (the one we are looking for) + * @param other_key second key + * @return TRUE if the keys are equal + */ +typedef bool (*hashtable_equals_t)(void *key, void *other_key); + +/** + * Class implementing a hash table. + * + * General purpose hash table. This hash table is not synchronized. + */ +struct hashtable_t { + + /** + * Create an enumerator over the hash table key/value pairs. + * + * @return enumerator over (void *key, void *value) + */ + enumerator_t *(*create_enumerator) (hashtable_t *this); + + /** + * Adds the given value with the given key to the hash table, if there + * exists no entry with that key. NULL is returned in this case. + * Otherwise the existing value is replaced and the function returns the + * old value. + * + * @param key the key to store + * @param value the value to store + * @return NULL if no item was replaced, the old value otherwise + */ + void *(*put) (hashtable_t *this, void *key, void *value); + + /** + * Returns the value with the given key, if the hash table contains such an + * entry, otherwise NULL is returned. + * + * @param key the key of the requested value + * @return the value, NULL if not found + */ + void *(*get) (hashtable_t *this, void *key); + + /** + * Returns the value with a matching key, if the hash table contains such an + * entry, otherwise NULL is returned. + * + * Compared to get() the given match function is used to compare the keys + * for equality. The hash function does have to be deviced properly in + * order to make this work if the match function compares keys differently + * than the equals function provided to the constructor. This basically + * allows to enumerate all entries with the same hash value. + * + * @param key the key to match against + * @param match match function to be used when comparing keys + * @return the value, NULL if not found + */ + void *(*get_match) (hashtable_t *this, void *key, hashtable_equals_t match); + + /** + * Removes the value with the given key from the hash table and returns the + * removed value (or NULL if no such value existed). + * + * @param key the key of the value to remove + * @return the removed value, NULL if not found + */ + void *(*remove) (hashtable_t *this, void *key); + + /** + * Removes the key and value pair from the hash table at which the given + * enumerator currently points. + * + * @param enumerator enumerator, from create_enumerator + */ + void (*remove_at) (hashtable_t *this, enumerator_t *enumerator); + + /** + * Gets the number of items in the hash table. + * + * @return number of items + */ + u_int (*get_count) (hashtable_t *this); + + /** + * Destroys a hash table object. + */ + void (*destroy) (hashtable_t *this); + +}; + +/** + * Creates an empty hash table object. + * + * @param hash hash function + * @param equals equals function + * @param capacity initial capacity + * @return hashtable_t object. + */ +hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals, + u_int capacity); + +#endif /** HASHTABLE_H_ @}*/ diff --git a/src/libstrongswan/collections/linked_list.c b/src/libstrongswan/collections/linked_list.c new file mode 100644 index 000000000..1ff80999b --- /dev/null +++ b/src/libstrongswan/collections/linked_list.c @@ -0,0 +1,615 @@ +/* + * Copyright (C) 2007-2011 Tobias Brunner + * Copyright (C) 2005-2006 Martin Willi + * Copyright (C) 2005 Jan Hutter + * Hochschule fuer Technik Rapperswil + * + * 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 <stdlib.h> +#include <stdarg.h> + +#include "linked_list.h" + +typedef struct element_t element_t; + +/** + * This element holds a pointer to the value it represents. + */ +struct element_t { + + /** + * Value of a list item. + */ + void *value; + + /** + * Previous list element. + * + * NULL if first element in list. + */ + element_t *previous; + + /** + * Next list element. + * + * NULL if last element in list. + */ + element_t *next; +}; + +/** + * Creates an empty linked list object. + */ +element_t *element_create(void *value) +{ + element_t *this; + INIT(this, + .value = value, + ); + return this; +} + + +typedef struct private_linked_list_t private_linked_list_t; + +/** + * Private data of a linked_list_t object. + * + */ +struct private_linked_list_t { + /** + * Public part of linked list. + */ + linked_list_t public; + + /** + * Number of items in the list. + */ + int count; + + /** + * First element in list. + * NULL if no elements in list. + */ + element_t *first; + + /** + * Last element in list. + * NULL if no elements in list. + */ + element_t *last; +}; + +typedef struct private_enumerator_t private_enumerator_t; + +/** + * linked lists enumerator implementation + */ +struct private_enumerator_t { + + /** + * implements enumerator interface + */ + enumerator_t enumerator; + + /** + * associated linked list + */ + private_linked_list_t *list; + + /** + * current item + */ + element_t *current; + + /** + * enumerator has enumerated all items + */ + bool finished; +}; + +METHOD(enumerator_t, enumerate, bool, + private_enumerator_t *this, void **item) +{ + if (this->finished) + { + return FALSE; + } + if (!this->current) + { + this->current = this->list->first; + } + else + { + this->current = this->current->next; + } + if (!this->current) + { + this->finished = TRUE; + return FALSE; + } + *item = this->current->value; + return TRUE; +} + +METHOD(linked_list_t, create_enumerator, enumerator_t*, + private_linked_list_t *this) +{ + private_enumerator_t *enumerator; + + INIT(enumerator, + .enumerator = { + .enumerate = (void*)_enumerate, + .destroy = (void*)free, + }, + .list = this, + ); + + return &enumerator->enumerator; +} + +METHOD(linked_list_t, reset_enumerator, void, + private_linked_list_t *this, private_enumerator_t *enumerator) +{ + enumerator->current = NULL; + enumerator->finished = FALSE; +} + +METHOD(linked_list_t, has_more, bool, + private_linked_list_t *this, private_enumerator_t *enumerator) +{ + if (enumerator->current) + { + return enumerator->current->next != NULL; + } + return !enumerator->finished && this->first != NULL; +} + +METHOD(linked_list_t, get_count, int, + private_linked_list_t *this) +{ + return this->count; +} + +METHOD(linked_list_t, insert_first, void, + private_linked_list_t *this, void *item) +{ + element_t *element; + + element = element_create(item); + if (this->count == 0) + { + /* first entry in list */ + this->first = element; + this->last = element; + } + else + { + element->next = this->first; + this->first->previous = element; + this->first = element; + } + this->count++; +} + +/** + * unlink an element form the list, returns following element + */ +static element_t* remove_element(private_linked_list_t *this, + element_t *element) +{ + element_t *next, *previous; + + next = element->next; + previous = element->previous; + free(element); + if (next) + { + next->previous = previous; + } + else + { + this->last = previous; + } + if (previous) + { + previous->next = next; + } + else + { + this->first = next; + } + if (--this->count == 0) + { + this->first = NULL; + this->last = NULL; + } + return next; +} + +METHOD(linked_list_t, get_first, status_t, + private_linked_list_t *this, void **item) +{ + if (this->count == 0) + { + return NOT_FOUND; + } + *item = this->first->value; + return SUCCESS; +} + +METHOD(linked_list_t, remove_first, status_t, + private_linked_list_t *this, void **item) +{ + if (get_first(this, item) == SUCCESS) + { + remove_element(this, this->first); + return SUCCESS; + } + return NOT_FOUND; +} + +METHOD(linked_list_t, insert_last, void, + private_linked_list_t *this, void *item) +{ + element_t *element; + + element = element_create(item); + if (this->count == 0) + { + /* first entry in list */ + this->first = element; + this->last = element; + } + else + { + element->previous = this->last; + this->last->next = element; + this->last = element; + } + this->count++; +} + +METHOD(linked_list_t, insert_before, void, + private_linked_list_t *this, private_enumerator_t *enumerator, + void *item) +{ + element_t *current, *element; + + current = enumerator->current; + if (!current) + { + if (enumerator->finished) + { + this->public.insert_last(&this->public, item); + } + else + { + this->public.insert_first(&this->public, item); + } + return; + } + element = element_create(item); + if (current->previous) + { + current->previous->next = element; + element->previous = current->previous; + current->previous = element; + element->next = current; + } + else + { + current->previous = element; + element->next = current; + this->first = element; + } + this->count++; +} + +METHOD(linked_list_t, replace, void*, + private_linked_list_t *this, private_enumerator_t *enumerator, + void *item) +{ + void *old = NULL; + + if (enumerator->current) + { + old = enumerator->current->value; + enumerator->current->value = item; + } + return old; +} + +METHOD(linked_list_t, get_last, status_t, + private_linked_list_t *this, void **item) +{ + if (this->count == 0) + { + return NOT_FOUND; + } + *item = this->last->value; + return SUCCESS; +} + +METHOD(linked_list_t, remove_last, status_t, + private_linked_list_t *this, void **item) +{ + if (get_last(this, item) == SUCCESS) + { + remove_element(this, this->last); + return SUCCESS; + } + return NOT_FOUND; +} + +METHOD(linked_list_t, remove_, int, + private_linked_list_t *this, void *item, bool (*compare)(void*,void*)) +{ + element_t *current = this->first; + int removed = 0; + + while (current) + { + if ((compare && compare(current->value, item)) || + (!compare && current->value == item)) + { + removed++; + current = remove_element(this, current); + } + else + { + current = current->next; + } + } + return removed; +} + +METHOD(linked_list_t, remove_at, void, + private_linked_list_t *this, private_enumerator_t *enumerator) +{ + element_t *current; + + if (enumerator->current) + { + current = enumerator->current; + enumerator->current = current->previous; + remove_element(this, current); + } +} + +METHOD(linked_list_t, find_first, status_t, + private_linked_list_t *this, linked_list_match_t match, + void **item, void *d1, void *d2, void *d3, void *d4, void *d5) +{ + element_t *current = this->first; + + while (current) + { + if ((match && match(current->value, d1, d2, d3, d4, d5)) || + (!match && item && current->value == *item)) + { + if (item != NULL) + { + *item = current->value; + } + return SUCCESS; + } + current = current->next; + } + return NOT_FOUND; +} + +METHOD(linked_list_t, find_last, status_t, + private_linked_list_t *this, linked_list_match_t match, + void **item, void *d1, void *d2, void *d3, void *d4, void *d5) +{ + element_t *current = this->last; + + while (current) + { + if ((match && match(current->value, d1, d2, d3, d4, d5)) || + (!match && item && current->value == *item)) + { + if (item != NULL) + { + *item = current->value; + } + return SUCCESS; + } + current = current->previous; + } + return NOT_FOUND; +} + +METHOD(linked_list_t, invoke_offset, void, + private_linked_list_t *this, size_t offset, + void *d1, void *d2, void *d3, void *d4, void *d5) +{ + element_t *current = this->first; + linked_list_invoke_t *method; + + while (current) + { + method = current->value + offset; + (*method)(current->value, d1, d2, d3, d4, d5); + current = current->next; + } +} + +METHOD(linked_list_t, invoke_function, void, + private_linked_list_t *this, linked_list_invoke_t fn, + void *d1, void *d2, void *d3, void *d4, void *d5) +{ + element_t *current = this->first; + + while (current) + { + fn(current->value, d1, d2, d3, d4, d5); + current = current->next; + } +} + +METHOD(linked_list_t, clone_offset, linked_list_t*, + private_linked_list_t *this, size_t offset) +{ + element_t *current = this->first; + linked_list_t *clone; + + clone = linked_list_create(); + while (current) + { + void* (**method)(void*) = current->value + offset; + clone->insert_last(clone, (*method)(current->value)); + current = current->next; + } + + return clone; +} + +METHOD(linked_list_t, clone_function, linked_list_t*, + private_linked_list_t *this, void* (*fn)(void*)) +{ + element_t *current = this->first; + linked_list_t *clone; + + clone = linked_list_create(); + while (current) + { + clone->insert_last(clone, fn(current->value)); + current = current->next; + } + return clone; +} + +METHOD(linked_list_t, destroy, void, + private_linked_list_t *this) +{ + void *value; + + /* Remove all list items before destroying list */ + while (remove_first(this, &value) == SUCCESS) + { + /* values are not destroyed so memory leaks are possible + * if list is not empty when deleting */ + } + free(this); +} + +METHOD(linked_list_t, destroy_offset, void, + private_linked_list_t *this, size_t offset) +{ + element_t *current = this->first, *next; + + while (current) + { + void (**method)(void*) = current->value + offset; + (*method)(current->value); + next = current->next; + free(current); + current = next; + } + free(this); +} + +METHOD(linked_list_t, destroy_function, void, + private_linked_list_t *this, void (*fn)(void*)) +{ + element_t *current = this->first, *next; + + while (current) + { + fn(current->value); + next = current->next; + free(current); + current = next; + } + free(this); +} + +/* + * Described in header. + */ +linked_list_t *linked_list_create() +{ + private_linked_list_t *this; + + INIT(this, + .public = { + .get_count = _get_count, + .create_enumerator = _create_enumerator, + .reset_enumerator = (void*)_reset_enumerator, + .has_more = (void*)_has_more, + .get_first = _get_first, + .get_last = _get_last, + .find_first = (void*)_find_first, + .find_last = (void*)_find_last, + .insert_first = _insert_first, + .insert_last = _insert_last, + .insert_before = (void*)_insert_before, + .replace = (void*)_replace, + .remove_first = _remove_first, + .remove_last = _remove_last, + .remove = _remove_, + .remove_at = (void*)_remove_at, + .invoke_offset = (void*)_invoke_offset, + .invoke_function = (void*)_invoke_function, + .clone_offset = _clone_offset, + .clone_function = _clone_function, + .destroy = _destroy, + .destroy_offset = _destroy_offset, + .destroy_function = _destroy_function, + }, + ); + + return &this->public; +} + +/* + * See header. + */ +linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator) +{ + linked_list_t *list; + void *item; + + list = linked_list_create(); + + while (enumerator->enumerate(enumerator, &item)) + { + list->insert_last(list, item); + } + enumerator->destroy(enumerator); + + return list; +} + +/* + * See header. + */ +linked_list_t *linked_list_create_with_items(void *item, ...) +{ + linked_list_t *list; + va_list args; + + list = linked_list_create(); + + va_start(args, item); + while (item) + { + list->insert_last(list, item); + item = va_arg(args, void*); + } + va_end(args); + + return list; +} diff --git a/src/libstrongswan/collections/linked_list.h b/src/libstrongswan/collections/linked_list.h new file mode 100644 index 000000000..da539a231 --- /dev/null +++ b/src/libstrongswan/collections/linked_list.h @@ -0,0 +1,319 @@ +/* + * Copyright (C) 2007-2011 Tobias Brunner + * Copyright (C) 2005-2008 Martin Willi + * Copyright (C) 2005 Jan Hutter + * Hochschule fuer Technik Rapperswil + * + * 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 linked_list linked_list + * @{ @ingroup collections + */ + +#ifndef LINKED_LIST_H_ +#define LINKED_LIST_H_ + +typedef struct linked_list_t linked_list_t; + +#include <collections/enumerator.h> + +/** + * Method to match elements in a linked list (used in find_* functions) + * + * @param item current list item + * @param ... user supplied data (only pointers, at most 5) + * @return + * - TRUE, if the item matched + * - FALSE, otherwise + */ +typedef bool (*linked_list_match_t)(void *item, ...); + +/** + * Method to be invoked on elements in a linked list (used in invoke_* functions) + * + * @param item current list item + * @param ... user supplied data (only pointers, at most 5) + */ +typedef void (*linked_list_invoke_t)(void *item, ...); + +/** + * Class implementing a double linked list. + * + * General purpose linked list. This list is not synchronized. + */ +struct linked_list_t { + + /** + * Gets the count of items in the list. + * + * @return number of items in list + */ + int (*get_count) (linked_list_t *this); + + /** + * Create an enumerator over the list. + * + * @note The enumerator's position is invalid before the first call + * to enumerate(). + * + * @return enumerator over list items + */ + enumerator_t* (*create_enumerator)(linked_list_t *this); + + /** + * Resets the enumerator's current position to the beginning of the list. + * + * @param enumerator enumerator to reset + */ + void (*reset_enumerator)(linked_list_t *this, enumerator_t *enumerator); + + /** + * Checks if there are more elements following after the enumerator's + * current position. + * + * @param enumerator enumerator to check + */ + bool (*has_more)(linked_list_t *this, enumerator_t *enumerator); + + /** + * Inserts a new item at the beginning of the list. + * + * @param item item value to insert in list + */ + void (*insert_first) (linked_list_t *this, void *item); + + /** + * Removes the first item in the list and returns its value. + * + * @param item returned value of first item, or NULL + * @return SUCCESS, or NOT_FOUND if list is empty + */ + status_t (*remove_first) (linked_list_t *this, void **item); + + /** + * Inserts a new item before the item the enumerator currently points to. + * + * If this method is called before starting the enumeration the item is + * inserted first. If it is called after all items have been enumerated + * the item is inserted last. This is helpful when inserting items into + * a sorted list. + * + * @note The position of the enumerator is not changed. + * + * @param enumerator enumerator with position + * @param item item value to insert in list + */ + void (*insert_before)(linked_list_t *this, enumerator_t *enumerator, + void *item); + + /** + * Replaces the item the enumerator currently points to with the given item. + * + * @param enumerator enumerator with position + * @param item item value to replace current item with + * @return current item or NULL if the enumerator is at an + * invalid position + */ + void *(*replace)(linked_list_t *this, enumerator_t *enumerator, void *item); + + /** + * Remove an item from the list where the enumerator points to. + * + * @param enumerator enumerator with position + */ + void (*remove_at)(linked_list_t *this, enumerator_t *enumerator); + + /** + * Remove items from the list matching the given item. + * + * If a compare function is given, it is called for each item, with the + * first parameter being the current list item and the second parameter + * being the supplied item. Return TRUE from the compare function to remove + * the item, return FALSE to keep it in the list. + * + * If compare is NULL, comparison is done by pointers. + * + * @param item item to remove/pass to comparator + * @param compare compare function, or NULL + * @return number of removed items + */ + int (*remove)(linked_list_t *this, void *item, bool (*compare)(void*,void*)); + + /** + * Returns the value of the first list item without removing it. + * + * @param item returned value of first item + * @return SUCCESS, NOT_FOUND if list is empty + */ + status_t (*get_first) (linked_list_t *this, void **item); + + /** + * Inserts a new item at the end of the list. + * + * @param item value to insert into list + */ + void (*insert_last) (linked_list_t *this, void *item); + + /** + * Removes the last item in the list and returns its value. + * + * @param item returned value of last item, or NULL + * @return SUCCESS, NOT_FOUND if list is empty + */ + status_t (*remove_last) (linked_list_t *this, void **item); + + /** + * Returns the value of the last list item without removing it. + * + * @param item returned value of last item + * @return SUCCESS, NOT_FOUND if list is empty + */ + status_t (*get_last) (linked_list_t *this, void **item); + + /** Find the first matching element in the list. + * + * The first object passed to the match function is the current list item, + * followed by the user supplied data. + * If the supplied function returns TRUE this function returns SUCCESS, and + * the current object is returned in the third parameter, otherwise, + * the next item is checked. + * + * If match is NULL, *item and the current object are compared. + * + * @warning Only use pointers as user supplied data. + * + * @param match comparison function to call on each object, or NULL + * @param item the list item, if found + * @param ... user data to supply to match function (limited to 5 arguments) + * @return SUCCESS if found, NOT_FOUND otherwise + */ + status_t (*find_first) (linked_list_t *this, linked_list_match_t match, + void **item, ...); + + /** Find the last matching element in the list. + * + * The first object passed to the match function is the current list item, + * followed by the user supplied data. + * If the supplied function returns TRUE this function returns SUCCESS, and + * the current object is returned in the third parameter, otherwise, + * the next item is checked. + * + * If match is NULL, *item and the current object are compared. + * + * @warning Only use pointers as user supplied data. + * + * @param match comparison function to call on each object, or NULL + * @param item the list item, if found + * @param ... user data to supply to match function (limited to 5 arguments) + * @return SUCCESS if found, NOT_FOUND otherwise + */ + status_t (*find_last) (linked_list_t *this, linked_list_match_t match, + void **item, ...); + + /** + * Invoke a method on all of the contained objects. + * + * If a linked list contains objects with function pointers, + * invoke() can call a method on each of the objects. The + * method is specified by an offset of the function pointer, + * which can be evalutated at compile time using the offsetof + * macro, e.g.: list->invoke(list, offsetof(object_t, method)); + * + * @warning Only use pointers as user supplied data. + * + * @param offset offset of the method to invoke on objects + * @param ... user data to supply to called function (limited to 5 arguments) + */ + void (*invoke_offset) (linked_list_t *this, size_t offset, ...); + + /** + * Invoke a function on all of the contained objects. + * + * @warning Only use pointers as user supplied data. + * + * @param function offset of the method to invoke on objects + * @param ... user data to supply to called function (limited to 5 arguments) + */ + void (*invoke_function) (linked_list_t *this, linked_list_invoke_t function, ...); + + /** + * Clones a list and its objects using the objects' clone method. + * + * @param offset offset ot the objects clone function + * @return cloned list + */ + linked_list_t *(*clone_offset) (linked_list_t *this, size_t offset); + + /** + * Clones a list and its objects using a given function. + * + * @param function function that clones an object + * @return cloned list + */ + linked_list_t *(*clone_function) (linked_list_t *this, void*(*)(void*)); + + /** + * Destroys a linked_list object. + */ + void (*destroy) (linked_list_t *this); + + /** + * Destroys a list and its objects using the destructor. + * + * If a linked list and the contained objects should be destroyed, use + * destroy_offset. The supplied offset specifies the destructor to + * call on each object. The offset may be calculated using the offsetof + * macro, e.g.: list->destroy_offset(list, offsetof(object_t, destroy)); + * + * @param offset offset of the objects destructor + */ + void (*destroy_offset) (linked_list_t *this, size_t offset); + + /** + * Destroys a list and its contents using a a cleanup function. + * + * If a linked list and its contents should get destroyed using a specific + * cleanup function, use destroy_function. This is useful when the + * list contains malloc()-ed blocks which should get freed, + * e.g.: list->destroy_function(list, free); + * + * @param function function to call on each object + */ + void (*destroy_function) (linked_list_t *this, void (*)(void*)); +}; + +/** + * Creates an empty linked list object. + * + * @return linked_list_t object. + */ +linked_list_t *linked_list_create(void); + +/** + * Creates a linked list from an enumerator. + * + * @param enumerator enumerator over void*, gets destroyed + * @return linked_list_t object, containing enumerated values + */ +linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator); + +/** + * Creates a linked list from a NULL terminated vararg list of items. + * + * @param first first item + * @param ... subsequent items, terminated by NULL + * @return linked_list_t object, containing passed items + */ +linked_list_t *linked_list_create_with_items(void *first, ...); + +#endif /** LINKED_LIST_H_ @}*/ |