From da16febcd7e453e26fc7eba5c33afe27f00d1134 Mon Sep 17 00:00:00 2001 From: John Mark Bell Date: Wed, 30 Jul 2008 19:59:38 +0000 Subject: Make parserutils_dict_entry public. Add basic implementations of a stack and a vector. svn path=/trunk/libparserutils/; revision=4824 --- src/utils/Makefile | 2 +- src/utils/dict.c | 9 --- src/utils/stack.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++ src/utils/vector.c | 201 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 381 insertions(+), 10 deletions(-) create mode 100644 src/utils/stack.c create mode 100644 src/utils/vector.c (limited to 'src') 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 @@ -13,15 +13,6 @@ #include "utils/rbtree.h" #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 */ 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 + */ + +#include +#include + +#include + +/** + * 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 + +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 + */ + +#include +#include + +#include + +/** + * 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 + +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 + -- cgit v1.2.3