diff options
-rw-r--r-- | include/parserutils/utils/dict.h | 9 | ||||
-rw-r--r-- | include/parserutils/utils/stack.h | 29 | ||||
-rw-r--r-- | include/parserutils/utils/vector.h | 31 | ||||
-rw-r--r-- | src/utils/Makefile | 2 | ||||
-rw-r--r-- | src/utils/dict.c | 9 | ||||
-rw-r--r-- | src/utils/stack.c | 179 | ||||
-rw-r--r-- | src/utils/vector.c | 201 |
7 files changed, 449 insertions, 11 deletions
diff --git a/include/parserutils/utils/dict.h b/include/parserutils/utils/dict.h index 43c96cb..7c24a2f 100644 --- a/include/parserutils/utils/dict.h +++ b/include/parserutils/utils/dict.h @@ -11,7 +11,14 @@ #include <parserutils/errors.h> #include <parserutils/functypes.h> -struct parserutils_dict_entry; +/** + * A dictionary entry + */ +struct parserutils_dict_entry +{ + size_t len; /**< Length of data, in bytes */ + uint8_t *data; /**< Entry data */ +}; typedef struct parserutils_dict_entry parserutils_dict_entry; struct parserutils_dict; diff --git a/include/parserutils/utils/stack.h b/include/parserutils/utils/stack.h new file mode 100644 index 0000000..e9fad5a --- /dev/null +++ b/include/parserutils/utils/stack.h @@ -0,0 +1,29 @@ +/* + * This file is part of LibParserUtils. + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org> + */ + +#ifndef parserutils_utils_stack_h_ +#define parserutils_utils_stack_h_ + +#include <stddef.h> + +#include <parserutils/errors.h> +#include <parserutils/functypes.h> + +struct parserutils_stack; +typedef struct parserutils_stack parserutils_stack; + +parserutils_stack *parserutils_stack_create(size_t item_size, size_t chunk_size, + parserutils_alloc alloc, void *pw); +void parserutils_stack_destroy(parserutils_stack *stack); + +parserutils_error parserutils_stack_push(parserutils_stack *stack, void *item); +parserutils_error parserutils_stack_pop(parserutils_stack *stack, void *item); + +void *parserutils_stack_get_current(parserutils_stack *stack); + +#endif + diff --git a/include/parserutils/utils/vector.h b/include/parserutils/utils/vector.h new file mode 100644 index 0000000..934ebcd --- /dev/null +++ b/include/parserutils/utils/vector.h @@ -0,0 +1,31 @@ +/* + * This file is part of LibParserUtils. + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org> + */ + +#ifndef parserutils_utils_vector_h_ +#define parserutils_utils_vector_h_ + +#include <stddef.h> + +#include <parserutils/errors.h> +#include <parserutils/functypes.h> + +struct parserutils_vector; +typedef struct parserutils_vector parserutils_vector; + +parserutils_vector *parserutils_vector_create(size_t item_size, + size_t chunk_size, parserutils_alloc alloc, void *pw); +void parserutils_vector_destroy(parserutils_vector *vector); + +parserutils_error parserutils_vector_append(parserutils_vector *vector, + void *item); +parserutils_error parserutils_vector_clear(parserutils_vector *vector); +parserutils_error parserutils_vector_remove_last(parserutils_vector *vector); + +void *parserutils_vector_iterate(parserutils_vector *vector, int32_t *ctx); + +#endif + diff --git a/src/utils/Makefile b/src/utils/Makefile index 2ea94f2..93a8db5 100644 --- a/src/utils/Makefile +++ b/src/utils/Makefile @@ -35,7 +35,7 @@ d := $(DIR) override CFLAGS := $(CFLAGS) -I$(d) # Sources -SRCS_$(d) := buffer.c dict.c errors.c rbtree.c +SRCS_$(d) := buffer.c dict.c errors.c rbtree.c stack.c vector.c # Append to sources for component SOURCES += $(addprefix $(d), $(SRCS_$(d))) diff --git a/src/utils/dict.c b/src/utils/dict.c index bd9bc1a..e84b9b9 100644 --- a/src/utils/dict.c +++ b/src/utils/dict.c @@ -14,15 +14,6 @@ #include "utils/utils.h" /** - * A dictionary entry - */ -struct parserutils_dict_entry -{ - size_t len; /**< Length of data, in bytes */ - uint8_t *data; /**< Entry data */ -}; - -/** * Dictionary object */ struct parserutils_dict diff --git a/src/utils/stack.c b/src/utils/stack.c new file mode 100644 index 0000000..2751ec4 --- /dev/null +++ b/src/utils/stack.c @@ -0,0 +1,179 @@ +/* + * This file is part of LibParserUtils. + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org> + */ + +#include <inttypes.h> +#include <string.h> + +#include <parserutils/utils/stack.h> + +/** + * Stack object + */ +struct parserutils_stack +{ + size_t item_size; /**< Size of an item in the stack */ + size_t chunk_size; /**< Size of a stack chunk */ + size_t items_allocated; /**< Number of slots allocated */ + int32_t current_item; /**< Index of current item */ + void *items; /**< Items in stack */ + + parserutils_alloc alloc; /**< Memory (de)allocation function */ + void *pw; /**< Client-specific data */ +}; + +/** + * Create a stack + * + * \param item_size Length, in bytes, of an item in the stack + * \param chunk_size Number of stack slots in a chunk + * \param alloc Memory (de)allocation function + * \param pw Pointer to client-specific private data + * \return Pointer to stack instance, or NULL on memory exhaustion + */ +parserutils_stack *parserutils_stack_create(size_t item_size, size_t chunk_size, + parserutils_alloc alloc, void *pw) +{ + parserutils_stack *stack; + + if (item_size == 0 || chunk_size == 0 || alloc == NULL) + return NULL; + + stack = alloc(NULL, sizeof(parserutils_stack), pw); + if (stack == NULL) + return NULL; + + stack->items = alloc(NULL, item_size * chunk_size, pw); + if (stack->items == NULL) { + alloc(stack, 0, pw); + return NULL; + } + + stack->item_size = item_size; + stack->chunk_size = chunk_size; + stack->items_allocated = chunk_size; + stack->current_item = -1; + + stack->alloc = alloc; + stack->pw = pw; + + return stack; +} + +/** + * Destroy a stack instance + * + * \param stack The stack to destroy + */ +void parserutils_stack_destroy(parserutils_stack *stack) +{ + if (stack == NULL) + return; + + stack->alloc(stack->items, 0, stack->pw); + stack->alloc(stack, 0, stack->pw); +} + +/** + * Push an item onto the stack + * + * \param stack The stack to push onto + * \param item The item to push + * \return PARSERUTILS_OK on success, appropriate error otherwise + */ +parserutils_error parserutils_stack_push(parserutils_stack *stack, void *item) +{ + int32_t slot; + + if (stack == NULL || item == NULL) + return PARSERUTILS_BADPARM; + + /* Ensure we'll get a valid slot */ + if (stack->current_item < -1 || stack->current_item == INT32_MAX) + return PARSERUTILS_INVALID; + + slot = stack->current_item + 1; + + if ((size_t) slot >= stack->items_allocated) { + void *temp = stack->alloc(stack->items, + (stack->items_allocated + stack->chunk_size) * + stack->item_size, stack->pw); + if (temp == NULL) + return PARSERUTILS_NOMEM; + + stack->items = temp; + stack->items_allocated += stack->chunk_size; + } + + memcpy((uint8_t *) stack->items + (slot * stack->item_size), + item, stack->item_size); + stack->current_item = slot; + + return PARSERUTILS_OK; +} + +/** + * Pop an item off a stack + * + * \param stack The stack to pop from + * \param item Pointer to location to receive popped item, or NULL + * \return PARSERUTILS_OK on success, appropriate error otherwise. + */ +parserutils_error parserutils_stack_pop(parserutils_stack *stack, void *item) +{ + if (stack == NULL) + return PARSERUTILS_BADPARM; + + if (stack->current_item < 0) + return PARSERUTILS_INVALID; + + if (item != NULL) { + memcpy(item, (uint8_t *) stack->items + + (stack->current_item * stack->item_size), + stack->item_size); + } + + stack->current_item -= 1; + + return PARSERUTILS_OK; +} + +/** + * Retrieve a pointer to the current item on the stack + * + * \param stack The stack to inspect + * \return Pointer to item on stack, or NULL if none + */ +void *parserutils_stack_get_current(parserutils_stack *stack) +{ + if (stack == NULL || stack->current_item < 0) + return NULL; + + return (uint8_t *) stack->items + + (stack->current_item * stack->item_size); +} + +#ifndef NDEBUG +#include <stdio.h> + +extern void parserutils_stack_dump(parserutils_stack *stack, const char *prefix, + void (*printer)(void *item)); + +void parserutils_stack_dump(parserutils_stack *stack, const char *prefix, + void (*printer)(void *item)) +{ + if (stack == NULL || printer == NULL) + return; + + for (int32_t i = 0; i <= stack->current_item; i++) { + printf("%s %d: ", prefix != NULL ? prefix : "", i); + printer((uint8_t *) stack->items + (i * stack->item_size)); + printf("\n"); + } +} + +#endif + diff --git a/src/utils/vector.c b/src/utils/vector.c new file mode 100644 index 0000000..b3ec8a4 --- /dev/null +++ b/src/utils/vector.c @@ -0,0 +1,201 @@ +/* + * This file is part of LibParserUtils. + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org> + */ + +#include <inttypes.h> +#include <string.h> + +#include <parserutils/utils/vector.h> + +/** + * Vector object + */ +struct parserutils_vector +{ + size_t item_size; /**< Size of an item in the vector */ + size_t chunk_size; /**< Size of a vector chunk */ + size_t items_allocated; /**< Number of slots allocated */ + int32_t current_item; /**< Index of current item */ + void *items; /**< Items in vector */ + + parserutils_alloc alloc; /**< Memory (de)allocation function */ + void *pw; /**< Client-specific data */ +}; + +/** + * Create a vector + * + * \param item_size Length, in bytes, of an item in the vector + * \param chunk_size Number of vector slots in a chunk + * \param alloc Memory (de)allocation function + * \param pw Pointer to client-specific private data + * \return Pointer to vector instance, or NULL on memory exhaustion + */ +parserutils_vector *parserutils_vector_create(size_t item_size, + size_t chunk_size, parserutils_alloc alloc, void *pw) +{ + parserutils_vector *vector; + + if (item_size == 0 || chunk_size == 0 || alloc == NULL) + return NULL; + + vector = alloc(NULL, sizeof(parserutils_vector), pw); + if (vector == NULL) + return NULL; + + vector->items = alloc(NULL, item_size * chunk_size, pw); + if (vector->items == NULL) { + alloc(vector, 0, pw); + return NULL; + } + + vector->item_size = item_size; + vector->chunk_size = chunk_size; + vector->items_allocated = chunk_size; + vector->current_item = -1; + + vector->alloc = alloc; + vector->pw = pw; + + return vector; +} + +/** + * Destroy a vector instance + * + * \param vector The vector to destroy + */ +void parserutils_vector_destroy(parserutils_vector *vector) +{ + if (vector == NULL) + return; + + vector->alloc(vector->items, 0, vector->pw); + vector->alloc(vector, 0, vector->pw); +} + +/** + * Append an item to the vector + * + * \param vector The vector to append to + * \param item The item to append + * \return PARSERUTILS_OK on success, appropriate error otherwise + */ +parserutils_error parserutils_vector_append(parserutils_vector *vector, + void *item) +{ + int32_t slot; + + if (vector == NULL || item == NULL) + return PARSERUTILS_BADPARM; + + /* Ensure we'll get a valid slot */ + if (vector->current_item < -1 || vector->current_item == INT32_MAX) + return PARSERUTILS_INVALID; + + slot = vector->current_item + 1; + + if ((size_t) slot >= vector->items_allocated) { + void *temp = vector->alloc(vector->items, + (vector->items_allocated + vector->chunk_size) * + vector->item_size, vector->pw); + if (temp == NULL) + return PARSERUTILS_NOMEM; + + vector->items = temp; + vector->items_allocated += vector->chunk_size; + } + + memcpy((uint8_t *) vector->items + (slot * vector->item_size), + item, vector->item_size); + vector->current_item = slot; + + return PARSERUTILS_OK; +} + +/** + * Clear a vector + * + * \param vector The vector to clear + * \return PARSERUTILS_OK on success, appropriate error otherwise. + */ +parserutils_error parserutils_vector_clear(parserutils_vector *vector) +{ + if (vector == NULL) + return PARSERUTILS_BADPARM; + + if (vector->current_item < 0) + return PARSERUTILS_INVALID; + + vector->current_item = -1; + + return PARSERUTILS_OK; +} + +/** + * Remove the last item from a vector + * + * \param vector The vector to remove from + * \return PARSERUTILS_OK on success, appropriate error otherwise + */ +parserutils_error parserutils_vector_remove_last(parserutils_vector *vector) +{ + if (vector == NULL) + return PARSERUTILS_BADPARM; + + if (vector->current_item < 0) + return PARSERUTILS_INVALID; + + vector->current_item--; + + return PARSERUTILS_OK; +} + +/** + * Iterate over a vector + * + * \param vector The vector to iterate over + * \param ctx Pointer to an integer for the iterator to use as context. + * \return Pointer to current item, or NULL if no more + */ +void *parserutils_vector_iterate(parserutils_vector *vector, int32_t *ctx) +{ + void *item; + + if (vector == NULL || ctx == NULL || vector->current_item < 0) + return NULL; + + if ((*ctx) > vector->current_item) + return NULL; + + item = (uint8_t *) vector->items + ((*ctx) * vector->item_size); + + (*ctx)++; + + return item; +} + +#ifndef NDEBUG +#include <stdio.h> + +extern void parserutils_vector_dump(parserutils_vector *vector, + const char *prefix, void (*printer)(void *item)); + +void parserutils_vector_dump(parserutils_vector *vector, const char *prefix, + void (*printer)(void *item)) +{ + if (vector == NULL || printer == NULL) + return; + + for (int32_t i = 0; i <= vector->current_item; i++) { + printf("%s %d: ", prefix != NULL ? prefix : "", i); + printer((uint8_t *) vector->items + (i * vector->item_size)); + printf("\n"); + } +} + +#endif + |