diff options
Diffstat (limited to 'src/libmowgli')
68 files changed, 8027 insertions, 0 deletions
diff --git a/src/libmowgli/Makefile b/src/libmowgli/Makefile new file mode 100644 index 0000000..d25902e --- /dev/null +++ b/src/libmowgli/Makefile @@ -0,0 +1,77 @@ +include ../../extra.mk + +LIB = ${LIB_PREFIX}mowgli${LIB_SUFFIX} +LIB_MAJOR = 2 +LIB_MINOR = 0 +DISTCLEAN = mowgli_config.h + +SRCS = mowgli_alloc.c \ + mowgli_allocation_policy.c \ + mowgli_allocator.c \ + mowgli_argstack.c \ + mowgli_bitvector.c \ + mowgli_dictionary.c \ + mowgli_error_backtrace.c \ + mowgli_formatter.c \ + mowgli_global_storage.c \ + mowgli_hash.c \ + mowgli_heap.c \ + mowgli_hook.c \ + mowgli_index.c \ + mowgli_init.c \ + mowgli_ioevent.c \ + mowgli_list.c \ + mowgli_logger.c \ + mowgli_mempool.c \ + $(MOWGLI_MODULE) \ + mowgli_object.c \ + mowgli_object_class.c \ + mowgli_object_messaging.c \ + mowgli_object_metadata.c \ + mowgli_patricia.c \ + mowgli_queue.c \ + mowgli_random.c \ + mowgli_signal.c \ + mowgli_spinlock.c \ + mowgli_string.c \ + +INCLUDES = mowgli.h \ + mowgli_alloc.h \ + mowgli_allocation_policy.h \ + mowgli_allocator.h \ + mowgli_argstack.h \ + mowgli_assert.h \ + mowgli_bitvector.h \ + mowgli_config.h \ + mowgli_dictionary.h \ + mowgli_error_backtrace.h \ + mowgli_exception.h \ + mowgli_formatter.h \ + mowgli_global_storage.h \ + mowgli_hash.h \ + mowgli_heap.h \ + mowgli_hook.h \ + mowgli_index.h \ + mowgli_init.h \ + mowgli_ioevent.h \ + mowgli_iterator.h \ + mowgli_list.h \ + mowgli_logger.h \ + mowgli_mempool.h \ + mowgli_module.h \ + mowgli_object.h \ + mowgli_object_class.h \ + mowgli_object_messaging.h \ + mowgli_object_metadata.h \ + mowgli_patricia.h \ + mowgli_queue.h \ + mowgli_random.h \ + mowgli_signal.h \ + mowgli_spinlock.h \ + mowgli_stdinc.h \ + mowgli_string.h + +include ../../buildsys.mk + +CPPFLAGS += ${LIB_CPPFLAGS} -I. -I.. -DMOWGLI_CORE +CFLAGS += ${LIB_CFLAGS} diff --git a/src/libmowgli/mowgli.h b/src/libmowgli/mowgli.h new file mode 100644 index 0000000..fe494b2 --- /dev/null +++ b/src/libmowgli/mowgli.h @@ -0,0 +1,81 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli.h: Base header for libmowgli. Includes everything. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_STAND_H__ +#define __MOWGLI_STAND_H__ + +#ifdef __cplusplus +# define MOWGLI_DECLS_START extern "C" { +# define MOWGLI_DECLS_END } +#else +# define MOWGLI_DECLS_START +# define MOWGLI_DECLS_END +#endif + +#ifdef MOWGLI_CORE +# include "win32_support.h" +# include "mowgli_config.h" +#endif + +#include "mowgli_stdinc.h" + +MOWGLI_DECLS_START + +#include "mowgli_logger.h" +#include "mowgli_assert.h" +#include "mowgli_exception.h" +#include "mowgli_iterator.h" + +#include "mowgli_alloc.h" +#include "mowgli_spinlock.h" +#include "mowgli_list.h" +#include "mowgli_object_class.h" +#include "mowgli_object.h" +#include "mowgli_allocation_policy.h" +#include "mowgli_dictionary.h" +#include "mowgli_patricia.h" +#include "mowgli_mempool.h" +#include "mowgli_module.h" +#include "mowgli_queue.h" +#include "mowgli_hash.h" +#include "mowgli_heap.h" +#include "mowgli_init.h" +#include "mowgli_bitvector.h" +#include "mowgli_hook.h" +#include "mowgli_signal.h" +#include "mowgli_error_backtrace.h" +#include "mowgli_random.h" +#include "mowgli_ioevent.h" +#include "mowgli_argstack.h" +#include "mowgli_object_messaging.h" +#include "mowgli_object_metadata.h" +#include "mowgli_global_storage.h" +#include "mowgli_string.h" +#include "mowgli_allocator.h" +#include "mowgli_formatter.h" +#include "mowgli_index.h" + +MOWGLI_DECLS_END + +#endif + diff --git a/src/libmowgli/mowgli_alloc.c b/src/libmowgli/mowgli_alloc.c new file mode 100644 index 0000000..c7d3c4f --- /dev/null +++ b/src/libmowgli/mowgli_alloc.c @@ -0,0 +1,133 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_alloc.c: Safe, portable implementations of malloc, calloc, and free. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +/* + * bootstrapped allocators so that we can initialise without blowing up + */ + +static void * +_mowgli_bootstrap_alloc(int size) +{ + return calloc(size, 1); +} + +static void +_mowgli_bootstrap_free(void *ptr) +{ + if (ptr) + free(ptr); +} + +static mowgli_allocation_policy_t _mowgli_allocator_bootstrap = { + { 0 }, + _mowgli_bootstrap_alloc, + _mowgli_bootstrap_free +}; + +static mowgli_allocation_policy_t *_mowgli_allocator = &_mowgli_allocator_bootstrap; + +/* + * \brief Allocates an array of data that contains "count" objects, + * of "size" size. + * + * Usually, this wraps calloc(). + * + * \param size size of objects to allocate. + * \param count amount of objects to allocate. + * + * \return A pointer to a memory buffer. + */ +void * +mowgli_alloc_array(size_t size, size_t count) +{ + return_val_if_fail(_mowgli_allocator != NULL, NULL); + + return _mowgli_allocator->allocate(size * count); +} + +/* + * \brief Allocates an object of "size" size. + * + * This is the equivilant of calling mowgli_alloc_array(size, 1). + * + * \param size size of object to allocate. + * + * \return A pointer to a memory buffer. + */ +void * +mowgli_alloc(size_t size) +{ + return mowgli_alloc_array(size, 1); +} + +/* + * \brief Frees an object back to the system memory pool. + * + * Wraps free protecting against common mistakes (reports an error instead). + * + * \param ptr pointer to object to free. + */ +void +mowgli_free(void *ptr) +{ + return_if_fail(_mowgli_allocator != NULL); + return_if_fail(ptr != NULL); + + _mowgli_allocator->deallocate(ptr); +} + +/* + * \brief Sets the mowgli.allocation_policy used by the allocation primitives. + * + * \param policy The mowgli_allocation_policy_t object to use. + */ +void +mowgli_allocator_set_policy(mowgli_allocation_policy_t *policy) +{ + return_if_fail(policy != NULL); + + _mowgli_allocator = policy; +} + +/* + * \brief Sets the mowgli.allocation_policy used by the allocation primitives, + * when given a name. + * + * \param name The name of the policy to use. + */ +void +mowgli_allocator_set_policy_by_name(const char *name) +{ + mowgli_allocation_policy_t *policy; + + return_if_fail(name != NULL); + + policy = mowgli_allocation_policy_lookup(name); + + if (policy == NULL) + return; + + mowgli_allocator_set_policy(policy); +} diff --git a/src/libmowgli/mowgli_alloc.h b/src/libmowgli/mowgli_alloc.h new file mode 100644 index 0000000..16bd674 --- /dev/null +++ b/src/libmowgli/mowgli_alloc.h @@ -0,0 +1,31 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_alloc.h: Safe, portable implementations of malloc, calloc, and free. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ALLOC_H__ +#define __MOWGLI_ALLOC_H__ + +extern void * mowgli_alloc_array(size_t size, size_t count); +extern void * mowgli_alloc(size_t size); +extern void mowgli_free(void *ptr); + +#endif diff --git a/src/libmowgli/mowgli_allocation_policy.c b/src/libmowgli/mowgli_allocation_policy.c new file mode 100644 index 0000000..8f390d1 --- /dev/null +++ b/src/libmowgli/mowgli_allocation_policy.c @@ -0,0 +1,70 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_allocation_policy.h: Allocation policy management. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_object_class_t klass; +static mowgli_patricia_t *mowgli_allocation_policy_dict = NULL; + +static void _allocation_policy_key_canon(char *str) +{ + +} + +void +mowgli_allocation_policy_init(void) +{ + mowgli_allocation_policy_dict = mowgli_patricia_create(_allocation_policy_key_canon); + + mowgli_object_class_init(&klass, "mowgli.allocation_policy", NULL, FALSE); +} + +mowgli_allocation_policy_t * +mowgli_allocation_policy_create(const char *name, mowgli_allocation_func_t allocator, + mowgli_deallocation_func_t deallocator) +{ + mowgli_allocation_policy_t *policy; + + if (mowgli_allocation_policy_dict == NULL) + mowgli_allocation_policy_dict = mowgli_patricia_create(_allocation_policy_key_canon); + + if ((policy = mowgli_patricia_retrieve(mowgli_allocation_policy_dict, name))) + return policy; + + policy = mowgli_alloc(sizeof(mowgli_allocation_policy_t)); + mowgli_object_init_from_class(mowgli_object(policy), name, &klass); + + policy->allocate = allocator; + policy->deallocate = deallocator; + + return policy; +} + +mowgli_allocation_policy_t * +mowgli_allocation_policy_lookup(const char *name) +{ + if (mowgli_allocation_policy_dict == NULL) + mowgli_allocation_policy_dict = mowgli_patricia_create(_allocation_policy_key_canon); + + return mowgli_patricia_retrieve(mowgli_allocation_policy_dict, name); +} diff --git a/src/libmowgli/mowgli_allocation_policy.h b/src/libmowgli/mowgli_allocation_policy.h new file mode 100644 index 0000000..037b8f9 --- /dev/null +++ b/src/libmowgli/mowgli_allocation_policy.h @@ -0,0 +1,45 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_allocation_policy.h: Allocation policy management. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ALLOCATION_POLICY_H__ +#define __MOWGLI_ALLOCATION_POLICY_H__ + +typedef void *(*mowgli_allocation_func_t)(int size); +typedef void (*mowgli_deallocation_func_t)(void *ptr); + +typedef struct { + mowgli_object_t parent; + mowgli_allocation_func_t allocate; + mowgli_deallocation_func_t deallocate; +} mowgli_allocation_policy_t; + +void mowgli_allocation_policy_init(void); +mowgli_allocation_policy_t *mowgli_allocation_policy_create(const char *name, + mowgli_allocation_func_t allocator, mowgli_deallocation_func_t deallocator); +mowgli_allocation_policy_t *mowgli_allocation_policy_lookup(const char *name); + +/* for mowgli_alloc, et. al */ +void mowgli_allocator_set_policy(mowgli_allocation_policy_t *policy); +void mowgli_allocator_set_policy_by_name(const char *name); + +#endif diff --git a/src/libmowgli/mowgli_allocator.c b/src/libmowgli/mowgli_allocator.c new file mode 100644 index 0000000..8c4bd69 --- /dev/null +++ b/src/libmowgli/mowgli_allocator.c @@ -0,0 +1,46 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_allocator.h: Builtin allocation policies (mmap/malloc). + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +mowgli_allocation_policy_t *mowgli_allocator_malloc = NULL; + +static void * +mowgli_allocator_func_malloc(int size) +{ + return calloc(size, 1); +} + +static void +mowgli_allocator_func_free(void *ptr) +{ + if (ptr) + free(ptr); +} + +void +mowgli_allocator_init(void) +{ + mowgli_allocator_malloc = mowgli_allocation_policy_create("malloc", mowgli_allocator_func_malloc, + mowgli_allocator_func_free); +} diff --git a/src/libmowgli/mowgli_allocator.h b/src/libmowgli/mowgli_allocator.h new file mode 100644 index 0000000..1e2b703 --- /dev/null +++ b/src/libmowgli/mowgli_allocator.h @@ -0,0 +1,31 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_allocator.h: Builtin allocation policies (mmap/malloc). + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ALLOCATOR_H__ +#define __MOWGLI_ALLOCATOR_H__ + +void mowgli_allocator_init(void) MOWGLI_DEPRECATED; +extern mowgli_allocation_policy_t *mowgli_allocator_malloc MOWGLI_DEPRECATED; + +#endif + diff --git a/src/libmowgli/mowgli_argstack.c b/src/libmowgli/mowgli_argstack.c new file mode 100644 index 0000000..0ad5c91 --- /dev/null +++ b/src/libmowgli/mowgli_argstack.c @@ -0,0 +1,247 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_argstack.c: Argument stacks. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_object_class_t klass; + +/* + * \brief Private destructor for the mowgli_argstack_t object. + * + * \param vptr pointer to mowgli_argstack_t to destroy. + */ +static void mowgli_argstack_destroy(void *vptr) +{ + mowgli_argstack_t *self = (mowgli_argstack_t *) vptr; + mowgli_node_t *n, *tn; + + MOWGLI_LIST_FOREACH_SAFE(n, tn, self->stack.head) + { + mowgli_free(n->data); + + mowgli_node_delete(n, &self->stack); + mowgli_node_free(n); + } + + mowgli_free(self); +} + +/* + * \brief Initialization code for the mowgli.argstack library. + * + * Side Effects: + * - the mowgli_argstack_t object class is registered. + */ +void mowgli_argstack_init(void) +{ + mowgli_object_class_init(&klass, "mowgli_argstack_t", mowgli_argstack_destroy, FALSE); +} + +/* + * \brief Creates an argument stack from a va_list and an appropriate + * description schema. + * + * \param descstr a description string which describes the argument stack, where: + * + the character 's' means that the value for that slot is a string + * + the character 'd' means that the value for that slot is a numeric + * + the character 'p' means that the value for that slot is a generic pointer + * + the character 'b' means that the value for that slot is a boolean + * \param va a va_list containing data to populate the argument stack with. + * + * \return a mowgli_argstack_t (mowgli.argstack) object. + */ +mowgli_argstack_t *mowgli_argstack_create_from_va_list(const char *descstr, va_list va) +{ + const char *cp = descstr; + mowgli_argstack_t *out = mowgli_alloc(sizeof(mowgli_argstack_t)); + mowgli_object_init(mowgli_object(out), descstr, &klass, NULL); + + if (descstr == NULL) + mowgli_throw_exception_val(mowgli.argstack.invalid_description, NULL); + + while (*cp) + { + mowgli_argstack_element_t *e = mowgli_alloc(sizeof(mowgli_argstack_element_t)); + + switch(*cp) + { + case 's': + e->data.string = va_arg(va, char *); + e->type = MOWGLI_ARG_STRING; + break; + case 'd': + e->data.numeric = va_arg(va, int); + e->type = MOWGLI_ARG_NUMERIC; + break; + case 'p': + e->data.pointer = va_arg(va, void *); + e->type = MOWGLI_ARG_POINTER; + break; + case 'b': + e->data.boolean = va_arg(va, mowgli_boolean_t); + e->type = MOWGLI_ARG_BOOLEAN; + break; + default: + va_end(va); + mowgli_object_unref(out); + mowgli_throw_exception_val(mowgli.argstack.invalid_description, NULL); + break; + } + + mowgli_node_add(e, mowgli_node_create(), &out->stack); + cp++; + } + + return out; +} + +/* + * \brief Creates an argument stack. + * + * \param descstr a description string which describes the argument stack, where: + * + the character 's' means that the value for that slot is a string + * + the character 'd' means that the value for that slot is a numeric + * + the character 'p' means that the value for that slot is a generic pointer + * + the character 'b' means that the value for that slot is a boolean + * \param va a va_list containing data to populate the argument stack with. + * + * \return a mowgli_argstack_t (mowgli.argstack) object. + */ +mowgli_argstack_t *mowgli_argstack_create(const char *descstr, ...) +{ + va_list va; + mowgli_argstack_t *out; + + if (descstr == NULL) + mowgli_throw_exception_val(mowgli.argstack.invalid_description, NULL); + + va_start(va, descstr); + out = mowgli_argstack_create_from_va_list(descstr, va); + va_end(va); + + return out; +} + +/* + * \brief Convenience function to pop a string value off of an argument stack. + * + * \param self A mowgli_argstack_t object to pop a string off of. + * + * \return On success, a string. + * + * Side Effects: + * - the argument is removed from the argstack. + */ +const char *mowgli_argstack_pop_string(mowgli_argstack_t *self) +{ + mowgli_node_t *n; + mowgli_argstack_element_t *e; + + if (self == NULL) + mowgli_throw_exception_val(mowgli.null_pointer_exception, NULL); + + n = self->stack.head; + mowgli_node_delete(n, &self->stack); + e = n->data; + mowgli_node_free(n); + + return e->data.string; +} + +/* + * \brief Convenience function to pop a numeric value off of an argument stack. + * + * \param self A mowgli_argstack_t object to pop a numeric off of. + * + * \return On success, a numeric. + * + * Side Effects: + * - the argument is removed from the argstack. + */ +int mowgli_argstack_pop_numeric(mowgli_argstack_t *self) +{ + mowgli_node_t *n; + mowgli_argstack_element_t *e; + + if (self == NULL) + mowgli_throw_exception_val(mowgli.null_pointer_exception, 0); + + n = self->stack.head; + mowgli_node_delete(n, &self->stack); + e = n->data; + mowgli_node_free(n); + + return e->data.numeric; +} + +/* + * Convenience function to pop a boolean value off of an argument stack. + * + * \param self A mowgli_argstack_t object to pop a boolean off of. + * + * \return On success, a boolean value. + * + * Side Effects: + * - the argument is removed from the argstack. + */ +mowgli_boolean_t mowgli_argstack_pop_boolean(mowgli_argstack_t *self) +{ + mowgli_node_t *n; + mowgli_argstack_element_t *e; + + if (self == NULL) + mowgli_throw_exception_val(mowgli.null_pointer_exception, FALSE); + + n = self->stack.head; + mowgli_node_delete(n, &self->stack); + e = n->data; + mowgli_node_free(n); + + return e->data.boolean; +} + +/* + * \brief Convenience function to pop a pointer value off of an argument stack. + * + * \param self A mowgli_argstack_t object to pop a pointer off of. + * + * \return On success, a pointer. + * + * Side Effects: + * - the argument is removed from the argstack. + */ +void *mowgli_argstack_pop_pointer(mowgli_argstack_t *self) +{ + mowgli_node_t *n; + mowgli_argstack_element_t *e; + + if (self == NULL) + mowgli_throw_exception_val(mowgli.null_pointer_exception, NULL); + + n = self->stack.head; + mowgli_node_delete(n, &self->stack); + e = n->data; + mowgli_node_free(n); + + return e->data.pointer; +} diff --git a/src/libmowgli/mowgli_argstack.h b/src/libmowgli/mowgli_argstack.h new file mode 100644 index 0000000..8e7428c --- /dev/null +++ b/src/libmowgli/mowgli_argstack.h @@ -0,0 +1,57 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_argstack.h: Argument stacks. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ARGSTACK_H__ +#define __MOWGLI_ARGSTACK_H__ + +typedef enum { + MOWGLI_ARG_NUMERIC, + MOWGLI_ARG_POINTER, + MOWGLI_ARG_STRING, + MOWGLI_ARG_BOOLEAN +} mowgli_argstack_element_type_t; + +typedef struct { + union { + int numeric; + void *pointer; + char *string; + mowgli_boolean_t boolean; + } data; + mowgli_argstack_element_type_t type; +} mowgli_argstack_element_t; + +typedef struct { + mowgli_object_t parent; + mowgli_list_t stack; +} mowgli_argstack_t; + +extern mowgli_argstack_t *mowgli_argstack_create(const char *descstr, ...); +extern mowgli_argstack_t *mowgli_argstack_create_from_va_list(const char *descstr, va_list va); +extern void mowgli_argstack_init(void); +extern const char *mowgli_argstack_pop_string(mowgli_argstack_t *); +extern int mowgli_argstack_pop_numeric(mowgli_argstack_t *); +extern mowgli_boolean_t mowgli_argstack_pop_boolean(mowgli_argstack_t *); +extern void *mowgli_argstack_pop_pointer(mowgli_argstack_t *); + +#endif diff --git a/src/libmowgli/mowgli_assert.h b/src/libmowgli/mowgli_assert.h new file mode 100644 index 0000000..8ee2c4f --- /dev/null +++ b/src/libmowgli/mowgli_assert.h @@ -0,0 +1,105 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_assert.h: Assertions. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ASSERT_H__ +#define __MOWGLI_ASSERT_H__ + +extern void mowgli_soft_assert_log(const char *asrt, const char *file, int line, const char *function); + +#ifdef __GNUC__ + +/* + * Performs a soft assertion. If the assertion fails, we log it. + */ +#define soft_assert(x) \ + if (!(x)) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __PRETTY_FUNCTION__); \ + } + +/* + * Same as soft_assert, but returns if an assertion fails. + */ +#define return_if_fail(x) \ + if (!(x)) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __PRETTY_FUNCTION__); \ + return; \ + } + +/* + * Same as soft_assert, but returns a given value if an assertion fails. + */ +#define return_val_if_fail(x, y) \ + if (!(x)) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __PRETTY_FUNCTION__); \ + return (y); \ + } + +/* + * Same as soft_assert, but returns NULL if the value is NULL. + */ +#define return_if_null(x) \ + if (x == NULL) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __PRETTY_FUNCTION__); \ + return (NULL); \ + } + +#else + +/* + * Performs a soft assertion. If the assertion fails, we log it. + */ +#define soft_assert(x) \ + if (!(x)) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __FUNCTION__); \ + } + +/* + * Same as soft_assert, but returns if an assertion fails. + */ +#define return_if_fail(x) \ + if (!(x)) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __FUNCTION__); \ + return; \ + } + +/* + * Same as soft_assert, but returns a given value if an assertion fails. + */ +#define return_val_if_fail(x, y) \ + if (!(x)) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __FUNCTION__); \ + return (y); \ + } + +/* + * Same as soft_assert, but returns NULL if the value is NULL. + */ +#define return_if_null(x) \ + if (x == NULL) { \ + mowgli_soft_assert_log(#x, __FILE__, __LINE__, __FUNCTION__); \ + return (NULL); \ + } + +#endif + +#endif diff --git a/src/libmowgli/mowgli_bitvector.c b/src/libmowgli/mowgli_bitvector.c new file mode 100644 index 0000000..8186c16 --- /dev/null +++ b/src/libmowgli/mowgli_bitvector.c @@ -0,0 +1,238 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_bitvector.c: Bitvectors. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_object_class_t klass; + +/* + * mowgli_bitvector_init(void) + * + * Initialization code for the mowgli.bitvector library. + * + * Inputs: + * - none + * + * Outputs: + * - none + * + * Side Effects: + * - the mowgli_bitvector_t object class is registered. + */ +void mowgli_bitvector_init(void) +{ + mowgli_object_class_init(&klass, "mowgli_bitvector_t", mowgli_free, FALSE); +} + +/* + * mowgli_bitvector_create(int bits) + * + * Creates a bitvector. + * + * Inputs: + * - amount of bits that the bitvector should store + * + * Outputs: + * - a mowgli.bitvector object + * + * Side Effects: + * - none + */ +mowgli_bitvector_t *mowgli_bitvector_create(int bits) +{ + mowgli_bitvector_t *bv = (mowgli_bitvector_t *) mowgli_alloc(sizeof(mowgli_bitvector_t)); + mowgli_object_init(mowgli_object(bv), "mowgli_bitvector_t", &klass, NULL); + + bv->bits = bits; + bv->divisor = sizeof(int); + bv->vector = (unsigned int *) mowgli_alloc_array(bv->divisor, bv->bits / bv->divisor); + + return bv; +} + +/* + * mowgli_bitvector_set(mowgli_bitvector_t *bv, int slot, mowgli_boolean_t val) + * + * Sets a bit either ON or OFF in the bitvector. + * + * Inputs: + * - a mowgli bitvector object + * - a slot + * - the value for that slot + * + * Outputs: + * - nothing + * + * Side Effects: + * - a bit is either set ON or OFF in the bitvector. + */ +void mowgli_bitvector_set(mowgli_bitvector_t *bv, int slot, mowgli_boolean_t val) +{ + int value = 1 << slot; + + switch(val) + { + case FALSE: + bv->vector[bv->bits / bv->divisor] &= ~value; + break; + default: + case TRUE: + bv->vector[bv->bits / bv->divisor] |= value; + break; + } +} + +/* + * mowgli_bitvector_get(mowgli_bitvector_t *bv, int slot) + * + * Returns whether the bit in a given slot is ON or OFF. + * + * Inputs: + * - a mowgli.bitvector object + * - a slot to lookup + * + * Outputs: + * - TRUE if the bit is on + * - FALSE otherwise + * + * Side Effects: + * - none + */ +mowgli_boolean_t mowgli_bitvector_get(mowgli_bitvector_t *bv, int slot) +{ + int mask = 1 << slot; + + return ((bv->vector[bv->bits / bv->divisor] & mask) != 0) ? TRUE : FALSE; +} + +/* + * mowgli_bitvector_combine(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2) + * + * Combines two bitvectors together. + * + * Inputs: + * - two bitvectors to be combined + * + * Outputs: + * - a new bitvector containing the combined result. + * + * Side Effects: + * - none + */ +mowgli_bitvector_t *mowgli_bitvector_combine(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2) +{ + int bits, iter, bs; + mowgli_bitvector_t *out; + + return_val_if_fail(bv1 != NULL, NULL); + return_val_if_fail(bv2 != NULL, NULL); + + /* choose the larger bitwidth */ + bits = bv1->bits > bv2->bits ? bv1->bits : bv2->bits; + + /* create the third bitvector. */ + out = mowgli_bitvector_create(bits); + + /* cache the size of the bitvector in memory. */ + bs = out->bits / out->divisor; + + for (iter = 0; iter < bs; iter++) + { + out->vector[iter] |= bv1->vector[iter]; + out->vector[iter] |= bv2->vector[iter]; + } + + return out; +} + +/* + * mowgli_bitvector_xor(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2) + * + * XORs two bitvectors together. + * + * Inputs: + * - two bitvectors to be XORed + * + * Outputs: + * - a new bitvector containing the XORed result. + * + * Side Effects: + * - none + */ +mowgli_bitvector_t *mowgli_bitvector_xor(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2) +{ + int bits, iter, bs; + mowgli_bitvector_t *out; + + return_val_if_fail(bv1 != NULL, NULL); + return_val_if_fail(bv2 != NULL, NULL); + + /* choose the larger bitwidth */ + bits = bv1->bits > bv2->bits ? bv1->bits : bv2->bits; + + /* create the third bitvector. */ + out = mowgli_bitvector_create(bits); + + /* cache the size of the bitvector in memory. */ + bs = out->bits / out->divisor; + + for (iter = 0; iter < bs; iter++) + { + out->vector[iter] = bv1->vector[iter]; + out->vector[iter] &= ~bv2->vector[iter]; + } + + return out; +} + +/* + * mowgli_bitvector_compare(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2) + * + * Compares two bitvectors to each other. + * + * Inputs: + * - two bitvectors to be compared + * + * Outputs: + * - TRUE if the bitvector is equal + * - FALSE otherwise + * + * Side Effects: + * - none + */ +mowgli_boolean_t mowgli_bitvector_compare(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2) +{ + int iter, bs; + mowgli_boolean_t ret = TRUE; + + /* cache the size of the bitvector in memory. */ + bs = bv1->bits / bv1->divisor; + + for (iter = 0; iter < bs; iter++) + { + if (!(bv1->vector[iter] & bv2->vector[iter])) + ret = FALSE; + } + + return ret; +} diff --git a/src/libmowgli/mowgli_bitvector.h b/src/libmowgli/mowgli_bitvector.h new file mode 100644 index 0000000..195d8d9 --- /dev/null +++ b/src/libmowgli/mowgli_bitvector.h @@ -0,0 +1,41 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_bitvector.h: Bitvectors. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_BITVECTOR_H__ +#define __MOWGLI_BITVECTOR_H__ + +typedef struct { + unsigned int bits; + unsigned int divisor; + unsigned int *vector; +} mowgli_bitvector_t; + +extern void mowgli_bitvector_init(void); +extern mowgli_bitvector_t *mowgli_bitvector_create(int bits); +extern void mowgli_bitvector_set(mowgli_bitvector_t *bv, int slot, mowgli_boolean_t val); +extern mowgli_boolean_t mowgli_bitvector_get(mowgli_bitvector_t *bv, int slot); +extern mowgli_bitvector_t *mowgli_bitvector_combine(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2); +extern mowgli_bitvector_t *mowgli_bitvector_xor(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2); +extern mowgli_boolean_t mowgli_bitvector_compare(mowgli_bitvector_t *bv1, mowgli_bitvector_t *bv2); + +#endif diff --git a/src/libmowgli/mowgli_config.h.in b/src/libmowgli/mowgli_config.h.in new file mode 100644 index 0000000..c43e92c --- /dev/null +++ b/src/libmowgli/mowgli_config.h.in @@ -0,0 +1,147 @@ +/* src/libmowgli/mowgli_config.h.in. Generated from configure.ac by autoheader. */ + +/* Define to 1 if the `closedir' function returns void instead of `int'. */ +#undef CLOSEDIR_VOID + +/* Define to 1 if you have the <dirent.h> header file, and it defines `DIR'. + */ +#undef HAVE_DIRENT_H + +/* Define to 1 if you have the `epoll_ctl' function. */ +#undef HAVE_EPOLL_CTL + +/* Define to 1 if you have the <errno.h> header file. */ +#undef HAVE_ERRNO_H + +/* Define to 1 if you have the `gettimeofday' function. */ +#undef HAVE_GETTIMEOFDAY + +/* Define to 1 if you have the <inttypes.h> header file. */ +#undef HAVE_INTTYPES_H + +/* Define to 1 if you have the <limits.h> header file. */ +#undef HAVE_LIMITS_H + +/* Define to 1 if you have the <locale.h> header file. */ +#undef HAVE_LOCALE_H + +/* Define to 1 if you have the <memory.h> header file. */ +#undef HAVE_MEMORY_H + +/* Define to 1 if you have the `memset' function. */ +#undef HAVE_MEMSET + +/* Define to 1 if you have the `mmap' function. */ +#undef HAVE_MMAP + +/* Define to 1 if you have the <ndir.h> header file, and it defines `DIR'. */ +#undef HAVE_NDIR_H + +/* Define to 1 if you have the `port_create' function. */ +#undef HAVE_PORT_CREATE + +/* Define to 1 if you have the `printf' function. */ +#undef HAVE_PRINTF + +/* Define to 1 if you have the `setlocale' function. */ +#undef HAVE_SETLOCALE + +/* Define to 1 if you have the `snprintf' function. */ +#undef HAVE_SNPRINTF + +/* Define to 1 if you have the `sprintf' function. */ +#undef HAVE_SPRINTF + +/* Define to 1 if `stat' has the bug that it succeeds when given the + zero-length file name argument. */ +#undef HAVE_STAT_EMPTY_STRING_BUG + +/* Define to 1 if you have the <stdarg.h> header file. */ +#undef HAVE_STDARG_H + +/* Define to 1 if you have the <stdint.h> header file. */ +#undef HAVE_STDINT_H + +/* Define to 1 if you have the <stdlib.h> header file. */ +#undef HAVE_STDLIB_H + +/* Define to 1 if you have the `strcasecmp' function. */ +#undef HAVE_STRCASECMP + +/* Define to 1 if you have the `strchr' function. */ +#undef HAVE_STRCHR + +/* Define to 1 if you have the `strdup' function. */ +#undef HAVE_STRDUP + +/* Define to 1 if you have the `strerror' function. */ +#undef HAVE_STRERROR + +/* Define to 1 if you have the <strings.h> header file. */ +#undef HAVE_STRINGS_H + +/* Define to 1 if you have the <string.h> header file. */ +#undef HAVE_STRING_H + +/* Define to 1 if you have the `strlcat' function. */ +#undef HAVE_STRLCAT + +/* Define to 1 if you have the `strlcpy' function. */ +#undef HAVE_STRLCPY + +/* Define to 1 if you have the `strndup' function. */ +#undef HAVE_STRNDUP + +/* Define to 1 if you have the `strtod' function. */ +#undef HAVE_STRTOD + +/* Define to 1 if you have the `strtol' function. */ +#undef HAVE_STRTOL + +/* Define to 1 if you have the <sys/dir.h> header file, and it defines `DIR'. + */ +#undef HAVE_SYS_DIR_H + +/* Define to 1 if you have the <sys/ndir.h> header file, and it defines `DIR'. + */ +#undef HAVE_SYS_NDIR_H + +/* Define to 1 if you have the <sys/stat.h> header file. */ +#undef HAVE_SYS_STAT_H + +/* Define to 1 if you have the <sys/types.h> header file. */ +#undef HAVE_SYS_TYPES_H + +/* Define to 1 if you have the <unistd.h> header file. */ +#undef HAVE_UNISTD_H + +/* Define to 1 if you have the `vsnprintf' function. */ +#undef HAVE_VSNPRINTF + +/* Define to 1 if `lstat' dereferences a symlink specified with a trailing + slash. */ +#undef LSTAT_FOLLOWS_SLASHED_SYMLINK + +/* Define to the address where bug reports for this package should be sent. */ +#undef PACKAGE_BUGREPORT + +/* Define to the full name of this package. */ +#undef PACKAGE_NAME + +/* Define to the full name and version of this package. */ +#undef PACKAGE_STRING + +/* Define to the one symbol short name of this package. */ +#undef PACKAGE_TARNAME + +/* Define to the home page for this package. */ +#undef PACKAGE_URL + +/* Define to the version of this package. */ +#undef PACKAGE_VERSION + +/* Define to 1 if you have the ANSI C header files. */ +#undef STDC_HEADERS + +/* Define to empty if `const' does not conform to ANSI C. */ +#undef const diff --git a/src/libmowgli/mowgli_dictionary.c b/src/libmowgli/mowgli_dictionary.c new file mode 100644 index 0000000..abcb2f9 --- /dev/null +++ b/src/libmowgli/mowgli_dictionary.c @@ -0,0 +1,914 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_dictionary.c: Dictionary-based information storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *elem_heap = NULL; + +struct mowgli_dictionary_ +{ + mowgli_dictionary_comparator_func_t compare_cb; + mowgli_dictionary_elem_t *root, *head, *tail; + unsigned int count; + char *id; + mowgli_boolean_t dirty; +}; + +static void warn_deprecated (void) +{ + static char warned = 0; + if (warned) + return; + + printf("mowgli_dictionary is deprecated and pending removal in Mowgli 1.0 " + "series.\nPlease use mowgli_patricia instead.\n"); + warned = 1; +} + +/* + * mowgli_dictionary_create(mowgli_dictionary_comparator_func_t compare_cb) + * + * Dictionary object factory. + * + * Inputs: + * - function to use for comparing two entries in the dtree + * + * Outputs: + * - on success, a new dictionary object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_dictionary_t *mowgli_dictionary_create(mowgli_dictionary_comparator_func_t compare_cb) +{ + mowgli_dictionary_t *dtree = (mowgli_dictionary_t *) mowgli_alloc(sizeof(mowgli_dictionary_t)); + + dtree->compare_cb = compare_cb; + + if (!elem_heap) + elem_heap = mowgli_heap_create(sizeof(mowgli_dictionary_elem_t), 1024, BH_NOW); + + warn_deprecated(); + return dtree; +} + +/* + * mowgli_dictionary_create_named(const char *name, + * mowgli_dictionary_comparator_func_t compare_cb) + * + * Dictionary object factory. + * + * Inputs: + * - dictionary name + * - function to use for comparing two entries in the dtree + * + * Outputs: + * - on success, a new dictionary object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_dictionary_t *mowgli_dictionary_create_named(const char *name, + mowgli_dictionary_comparator_func_t compare_cb) +{ + mowgli_dictionary_t *dtree = (mowgli_dictionary_t *) mowgli_alloc(sizeof(mowgli_dictionary_t)); + + dtree->compare_cb = compare_cb; + dtree->id = strdup(name); + + if (!elem_heap) + elem_heap = mowgli_heap_create(sizeof(mowgli_dictionary_elem_t), 1024, BH_NOW); + + warn_deprecated(); + return dtree; +} + +/* + * mowgli_dictionary_set_comparator_func(mowgli_dictionary_t *dict, + * mowgli_dictionary_comparator_func_t compare_cb) + * + * Resets the comparator function used by the dictionary code for + * updating the DTree structure. + * + * Inputs: + * - dictionary object + * - new comparator function (passed as functor) + * + * Outputs: + * - nothing + * + * Side Effects: + * - the dictionary comparator function is reset. + */ +void mowgli_dictionary_set_comparator_func(mowgli_dictionary_t *dict, + mowgli_dictionary_comparator_func_t compare_cb) +{ + return_if_fail(dict != NULL); + return_if_fail(compare_cb != NULL); + + dict->compare_cb = compare_cb; +} + +/* + * mowgli_dictionary_get_comparator_func(mowgli_dictionary_t *dict) + * + * Returns the current comparator function used by the dictionary. + * + * Inputs: + * - dictionary object + * + * Outputs: + * - comparator function (returned as functor) + * + * Side Effects: + * - none + */ +mowgli_dictionary_comparator_func_t +mowgli_dictionary_get_comparator_func(mowgli_dictionary_t *dict) +{ + return_val_if_fail(dict != NULL, NULL); + + return dict->compare_cb; +} + +/* + * mowgli_dictionary_get_linear_index(mowgli_dictionary_t *dict, + * const char *key) + * + * Gets a linear index number for key. + * + * Inputs: + * - dictionary tree object + * - pointer to data + * + * Outputs: + * - position, from zero. + * + * Side Effects: + * - rebuilds the linear index if the tree is marked as dirty. + */ +int +mowgli_dictionary_get_linear_index(mowgli_dictionary_t *dict, const char *key) +{ + mowgli_dictionary_elem_t *elem; + + return_val_if_fail(dict != NULL, 0); + return_val_if_fail(key != NULL, 0); + + elem = mowgli_dictionary_find(dict, key); + if (elem == NULL) + return -1; + + if (!dict->dirty) + return elem->position; + else + { + mowgli_dictionary_elem_t *delem; + int i; + + for (delem = dict->head, i = 0; delem != NULL; delem = delem->next, i++) + delem->position = i; + + dict->dirty = FALSE; + } + + return elem->position; +} + +/* + * mowgli_dictionary_retune(mowgli_dictionary_t *dict, const char *key) + * + * Retunes the tree, self-optimizing for the element which belongs to key. + * + * Tuning the tree structure is a very complex operation. Unlike + * 2-3-4 trees and BTree/BTree+ structures, this structure is a + * constantly evolving algorithm. + * + * Instead of maintaining a balanced tree, we constantly adapt the + * tree by nominating a new root nearby the most recently looked up + * or added data. We are constantly retuning ourselves instead of + * doing massive O(n) rebalance operations as seen in BTrees, + * and the level of data stored in a tree is dynamic, instead of being + * held to a restricted design like other trees. + * + * Moreover, we are different than a radix/patricia tree, because we + * don't statically allocate positions. Radix trees have the advantage + * of not requiring tuning or balancing operations while having the + * disadvantage of requiring a large amount of memory to store + * large trees. Our efficiency as far as speed goes is not as + * fast as a radix tree; but is close to it. + * + * The retuning algorithm uses the comparison callback that is + * passed in the initialization of the tree container. If the + * comparator returns a value which is less than zero, we push the + * losing node out of the way, causing it to later be reparented + * with another node. The winning child of this comparison is always + * the right-most node. + * + * Once we have reached the key which has been targeted, or have reached + * a deadend, we nominate the nearest node as the new root of the tree. + * If an exact match has been found, the new root becomes the node which + * represents key. + * + * This results in a tree which can self-optimize for both critical + * conditions: nodes which are distant and similar and trees which + * have ordered lookups. + * + * Inputs: + * - node to begin search from + * + * Outputs: + * - none + * + * Side Effects: + * - a new root node is nominated. + */ +void +mowgli_dictionary_retune(mowgli_dictionary_t *dict, const char *key) +{ + mowgli_dictionary_elem_t n, *tn, *left, *right, *node; + int ret; + + return_if_fail(dict != NULL); + + if (dict->root == NULL) + return; + + /* + * we initialize n with known values, since it's on stack + * memory. otherwise the dict would become corrupted. + * + * n is used for temporary storage while the tree is retuned. + * -nenolod + */ + n.left = n.right = NULL; + left = right = &n; + + /* this for(;;) loop is the main workhorse of the rebalancing */ + for (node = dict->root; ; ) + { + if ((ret = dict->compare_cb(key, node->key)) == 0) + break; + + if (ret < 0) + { + if (node->left == NULL) + break; + + if ((ret = dict->compare_cb(key, node->left->key)) < 0) + { + tn = node->left; + node->left = tn->right; + tn->right = node; + node = tn; + + if (node->left == NULL) + break; + } + + right->left = node; + right = node; + node = node->left; + } + else + { + if (node->right == NULL) + break; + + if ((ret = dict->compare_cb(key, node->right->key)) > 0) + { + tn = node->right; + node->right = tn->left; + tn->left = node; + node = tn; + + if (node->right == NULL) + break; + } + + left->right = node; + left = node; + node = node->right; + } + } + + left->right = node->left; + right->left = node->right; + + node->left = n.right; + node->right = n.left; + + dict->root = node; +} + +/* + * mowgli_dictionary_link(mowgli_dictionary_t *dict, + * mowgli_dictionary_elem_t *delem) + * + * Links a dictionary tree element to the dictionary. + * + * When we add new nodes to the tree, it becomes the + * next nominated root. This is perhaps not a wise + * optimization because of automatic retuning, but + * it keeps the code simple. + * + * Inputs: + * - dictionary tree + * - dictionary tree element + * + * Outputs: + * - nothing + * + * Side Effects: + * - a node is linked to the dictionary tree + */ +void +mowgli_dictionary_link(mowgli_dictionary_t *dict, + mowgli_dictionary_elem_t *delem) +{ + return_if_fail(dict != NULL); + return_if_fail(delem != NULL); + + dict->dirty = TRUE; + + dict->count++; + + if (dict->root == NULL) + { + delem->left = delem->right = NULL; + delem->next = delem->prev = NULL; + dict->head = dict->tail = dict->root = delem; + } + else + { + int ret; + + mowgli_dictionary_retune(dict, delem->key); + + if ((ret = dict->compare_cb(delem->key, dict->root->key)) < 0) + { + delem->left = dict->root->left; + delem->right = dict->root; + dict->root->left = NULL; + + if (dict->root->prev) + dict->root->prev->next = delem; + else + dict->head = delem; + + delem->prev = dict->root->prev; + delem->next = dict->root; + dict->root->prev = delem; + dict->root = delem; + } + else if (ret > 0) + { + delem->right = dict->root->right; + delem->left = dict->root; + dict->root->right = NULL; + + if (dict->root->next) + dict->root->next->prev = delem; + else + dict->tail = delem; + + delem->next = dict->root->next; + delem->prev = dict->root; + dict->root->next = delem; + dict->root = delem; + } + else + { + dict->root->key = delem->key; + dict->root->data = delem->data; + dict->count--; + + mowgli_heap_free(elem_heap, delem); + } + } +} + +/* + * mowgli_dictionary_unlink_root(mowgli_dictionary_t *dict) + * + * Unlinks the root dictionary tree element from the dictionary. + * + * Inputs: + * - dictionary tree + * + * Outputs: + * - nothing + * + * Side Effects: + * - the root node is unlinked from the dictionary tree + */ +void +mowgli_dictionary_unlink_root(mowgli_dictionary_t *dict) +{ + mowgli_dictionary_elem_t *delem, *nextnode, *parentofnext; + + dict->dirty = TRUE; + + delem = dict->root; + if (delem == NULL) + return; + + if (dict->root->left == NULL) + dict->root = dict->root->right; + else if (dict->root->right == NULL) + dict->root = dict->root->left; + else + { + /* Make the node with the next highest key the new root. + * This node has a NULL left pointer. */ + nextnode = delem->next; + soft_assert(nextnode->left == NULL); + if (nextnode == delem->right) + { + dict->root = nextnode; + dict->root->left = delem->left; + } + else + { + parentofnext = delem->right; + while (parentofnext->left != NULL && parentofnext->left != nextnode) + parentofnext = parentofnext->left; + soft_assert(parentofnext->left == nextnode); + parentofnext->left = nextnode->right; + dict->root = nextnode; + dict->root->left = delem->left; + dict->root->right = delem->right; + } + } + + /* linked list */ + if (delem->prev != NULL) + delem->prev->next = delem->next; + + if (dict->head == delem) + dict->head = delem->next; + + if (delem->next) + delem->next->prev = delem->prev; + + if (dict->tail == delem) + dict->tail = delem->prev; + + dict->count--; +} + +/* + * mowgli_dictionary_destroy(mowgli_dictionary_t *dtree, + * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), + * void *privdata); + * + * Recursively destroys all nodes in a dictionary tree. + * + * Inputs: + * - dictionary tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree and optionally it's children are destroyed. + * + * Notes: + * - if this is called without a callback, the objects bound to the + * DTree will not be destroyed. + */ +void mowgli_dictionary_destroy(mowgli_dictionary_t *dtree, + void (*destroy_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) +{ + mowgli_dictionary_elem_t *n, *tn; + + return_if_fail(dtree != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, dtree->head) + { + if (destroy_cb != NULL) + (*destroy_cb)(n, privdata); + + mowgli_free(n->key); + mowgli_heap_free(elem_heap, n); + } + + mowgli_free(dtree); +} + +/* + * mowgli_dictionary_foreach(mowgli_dictionary_t *dtree, + * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), + * void *privdata); + * + * Iterates over all entries in a DTree. + * + * Inputs: + * - dictionary tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree is iterated + */ +void mowgli_dictionary_foreach(mowgli_dictionary_t *dtree, + int (*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) +{ + mowgli_dictionary_elem_t *n, *tn; + + return_if_fail(dtree != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, dtree->head) + { + /* delem_t is a subclass of node_t. */ + mowgli_dictionary_elem_t *delem = (mowgli_dictionary_elem_t *) n; + + if (foreach_cb != NULL) + (*foreach_cb)(delem, privdata); + } +} + +/* + * mowgli_dictionary_search(mowgli_dictionary_t *dtree, + * void (*destroy_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + * void *privdata); + * + * Searches all entries in a DTree using a custom callback. + * + * Inputs: + * - dictionary tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - on success, the requested object + * - on failure, NULL. + * + * Side Effects: + * - a dtree is iterated until the requested conditions are met + */ +void *mowgli_dictionary_search(mowgli_dictionary_t *dtree, + void *(*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) +{ + mowgli_dictionary_elem_t *n, *tn; + void *ret = NULL; + + return_val_if_fail(dtree != NULL, NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, dtree->head) + { + /* delem_t is a subclass of node_t. */ + mowgli_dictionary_elem_t *delem = (mowgli_dictionary_elem_t *) n; + + if (foreach_cb != NULL) + ret = (*foreach_cb)(delem, privdata); + + if (ret) + break; + } + + return ret; +} + +/* + * mowgli_dictionary_foreach_start(mowgli_dictionary_t *dtree, + * mowgli_dictionary_iteration_state_t *state); + * + * Initializes a static DTree iterator. + * + * Inputs: + * - dictionary tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is initialized. + */ +void mowgli_dictionary_foreach_start(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) +{ + return_if_fail(dtree != NULL); + return_if_fail(state != NULL); + + state->cur = NULL; + state->next = NULL; + + /* find first item */ + state->cur = dtree->head; + + if (state->cur == NULL) + return; + + /* make state->cur point to first item and state->next point to + * second item */ + state->next = state->cur; + mowgli_dictionary_foreach_next(dtree, state); +} + +/* + * mowgli_dictionary_foreach_cur(mowgli_dictionary_t *dtree, + * mowgli_dictionary_iteration_state_t *state); + * + * Returns the data from the current node being iterated by the + * static iterator. + * + * Inputs: + * - dictionary tree object + * - static DTree iterator + * + * Outputs: + * - reference to data in the current dtree node being iterated + * + * Side Effects: + * - none + */ +void *mowgli_dictionary_foreach_cur(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) +{ + return_val_if_fail(dtree != NULL, NULL); + return_val_if_fail(state != NULL, NULL); + + return state->cur != NULL ? state->cur->data : NULL; +} + +/* + * mowgli_dictionary_foreach_next(mowgli_dictionary_t *dtree, + * mowgli_dictionary_iteration_state_t *state); + * + * Advances a static DTree iterator. + * + * Inputs: + * - dictionary tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is advanced to a new DTree node. + */ +void mowgli_dictionary_foreach_next(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) +{ + return_if_fail(dtree != NULL); + return_if_fail(state != NULL); + + if (state->cur == NULL) + { + mowgli_log("mowgli_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", dtree); + return; + } + + state->cur = state->next; + + if (state->next == NULL) + return; + + state->next = state->next->next; +} + +/* + * mowgli_dictionary_find(mowgli_dictionary_t *dtree, const char *key) + * + * Looks up a DTree node by name. + * + * Inputs: + * - dictionary tree object + * - name of node to lookup + * + * Outputs: + * - on success, the dtree node requested + * - on failure, NULL + * + * Side Effects: + * - none + */ +mowgli_dictionary_elem_t *mowgli_dictionary_find(mowgli_dictionary_t *dict, const char *key) +{ + return_val_if_fail(dict != NULL, NULL); + return_val_if_fail(key != NULL, NULL); + + /* retune for key, key will be the tree's root if it's available */ + mowgli_dictionary_retune(dict, key); + + if (dict->root && !dict->compare_cb(key, dict->root->key)) + return dict->root; + + return NULL; +} + +/* + * mowgli_dictionary_add(mowgli_dictionary_t *dtree, const char *key, void *data) + * + * Creates a new DTree node and binds data to it. + * + * Inputs: + * - dictionary tree object + * - name for new DTree node + * - data to bind to the new DTree node + * + * Outputs: + * - on success, a new DTree node + * - on failure, NULL + * + * Side Effects: + * - data is inserted into the DTree. + */ +mowgli_dictionary_elem_t *mowgli_dictionary_add(mowgli_dictionary_t *dict, const char *key, void *data) +{ + mowgli_dictionary_elem_t *delem; + + return_val_if_fail(dict != NULL, NULL); + return_val_if_fail(key != NULL, NULL); + return_val_if_fail(data != NULL, NULL); + return_val_if_fail(mowgli_dictionary_find(dict, key) == NULL, NULL); + + delem = mowgli_heap_alloc(elem_heap); + delem->key = strdup(key); + delem->data = data; + + if (delem->key == NULL) + { + mowgli_log("major WTF: delem->key is NULL, not adding node.", key); + mowgli_heap_free(elem_heap, delem); + return NULL; + } + + mowgli_dictionary_link(dict, delem); + + return delem; +} + +/* + * mowgli_dictionary_delete(mowgli_dictionary_t *dtree, const char *key) + * + * Deletes data from a dictionary tree. + * + * Inputs: + * - dictionary tree object + * - name of DTree node to delete + * + * Outputs: + * - on success, the remaining data that needs to be mowgli_freed + * - on failure, NULL + * + * Side Effects: + * - data is removed from the DTree. + * + * Notes: + * - the returned data needs to be mowgli_freed/released manually! + */ +void *mowgli_dictionary_delete(mowgli_dictionary_t *dtree, const char *key) +{ + mowgli_dictionary_elem_t *delem = mowgli_dictionary_find(dtree, key); + void *data; + + if (delem == NULL) + return NULL; + + data = delem->data; + + mowgli_free(delem->key); + mowgli_dictionary_unlink_root(dtree); + mowgli_heap_free(elem_heap, delem); + + return data; +} + +/* + * mowgli_dictionary_retrieve(mowgli_dictionary_t *dtree, const char *key) + * + * Retrieves data from a dictionary. + * + * Inputs: + * - dictionary tree object + * - name of node to lookup + * + * Outputs: + * - on success, the data bound to the DTree node. + * - on failure, NULL + * + * Side Effects: + * - none + */ +void *mowgli_dictionary_retrieve(mowgli_dictionary_t *dtree, const char *key) +{ + mowgli_dictionary_elem_t *delem = mowgli_dictionary_find(dtree, key); + + if (delem != NULL) + return delem->data; + + return NULL; +} + +/* + * mowgli_dictionary_size(mowgli_dictionary_t *dict) + * + * Returns the size of a dictionary. + * + * Inputs: + * - dictionary tree object + * + * Outputs: + * - size of dictionary + * + * Side Effects: + * - none + */ +unsigned int mowgli_dictionary_size(mowgli_dictionary_t *dict) +{ + return_val_if_fail(dict != NULL, 0); + + return dict->count; +} + +/* returns the sum of the depths of the subtree rooted in delem at depth depth */ +static int +stats_recurse(mowgli_dictionary_elem_t *delem, int depth, int *pmaxdepth) +{ + int result; + + if (depth > *pmaxdepth) + *pmaxdepth = depth; + result = depth; + if (delem->left) + result += stats_recurse(delem->left, depth + 1, pmaxdepth); + if (delem->right) + result += stats_recurse(delem->right, depth + 1, pmaxdepth); + return result; +} + +/* + * mowgli_dictionary_stats(mowgli_dictionary_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) + * + * Returns the size of a dictionary. + * + * Inputs: + * - dictionary tree object + * - callback + * - data for callback + * + * Outputs: + * - none + * + * Side Effects: + * - callback called with stats text + */ +void mowgli_dictionary_stats(mowgli_dictionary_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) +{ + char str[256]; + int sum, maxdepth; + + return_if_fail(dict != NULL); + + if (dict->id != NULL) + snprintf(str, sizeof str, "Dictionary stats for %s (%d)", + dict->id, dict->count); + else + snprintf(str, sizeof str, "Dictionary stats for <%p> (%d)", + dict, dict->count); + cb(str, privdata); + maxdepth = 0; + if (dict->root != NULL) + { + sum = stats_recurse(dict->root, 0, &maxdepth); + snprintf(str, sizeof str, "Depth sum %d Avg depth %d Max depth %d", sum, sum / dict->count, maxdepth); + } + else + snprintf(str, sizeof str, "Depth sum 0 Avg depth 0 Max depth 0"); + cb(str, privdata); + return; +} diff --git a/src/libmowgli/mowgli_dictionary.h b/src/libmowgli/mowgli_dictionary.h new file mode 100644 index 0000000..884cde4 --- /dev/null +++ b/src/libmowgli/mowgli_dictionary.h @@ -0,0 +1,166 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_dictionary.h: Dictionary-based storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_DICTIONARY_H__ +#define __MOWGLI_DICTIONARY_H__ + +struct mowgli_dictionary_; /* defined in src/dictionary.c */ + +typedef struct mowgli_dictionary_ mowgli_dictionary_t; + +typedef struct mowgli_dictionary_elem_ mowgli_dictionary_elem_t; + +typedef int (*mowgli_dictionary_comparator_func_t)(const char *a, const char *b); + +struct mowgli_dictionary_elem_ +{ + mowgli_dictionary_elem_t *left, *right, *prev, *next; + void *data; + char *key; + int position; +}; + +/* + * mowgli_dictionary_iteration_state_t, private. + */ +struct mowgli_dictionary_iteration_state_ +{ + mowgli_dictionary_elem_t *cur, *next; + void *pspare[4]; + int ispare[4]; +}; + +typedef struct mowgli_dictionary_iteration_state_ mowgli_dictionary_iteration_state_t; + +/* + * this is a convenience macro for inlining iteration of dictionaries. + */ +#define MOWGLI_DICTIONARY_FOREACH(element, state, dict) for (mowgli_dictionary_foreach_start((dict), (state)); (element = mowgli_dictionary_foreach_cur((dict), (state))); mowgli_dictionary_foreach_next((dict), (state))) + +/* + * mowgli_dictionary_create() creates a new dictionary tree. + * compare_cb is the comparison function, typically strcmp, strcasecmp or + * irccasecmp. + */ +extern mowgli_dictionary_t *mowgli_dictionary_create(mowgli_dictionary_comparator_func_t compare_cb) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_create_named() creates a new dictionary tree which has a name. + * name is the name, compare_cb is the comparator. + */ +extern mowgli_dictionary_t *mowgli_dictionary_create_named(const char *name, mowgli_dictionary_comparator_func_t compare_cb) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_set_comparator_func() resets the comparator used for lookups and + * insertions in the DTree structure. + */ +extern void mowgli_dictionary_set_comparator_func(mowgli_dictionary_t *dict, + mowgli_dictionary_comparator_func_t compare_cb) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_get_comparator_func() returns the comparator used for lookups and + * insertions in the DTree structure. + */ +extern mowgli_dictionary_comparator_func_t mowgli_dictionary_get_comparator_func(mowgli_dictionary_t *dict) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_get_linear_index() returns the linear index of an object in the + * DTree structure. + */ +extern int mowgli_dictionary_get_linear_index(mowgli_dictionary_t *dict, const char *key) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_destroy() destroys all entries in a dtree, and also optionally calls + * a defined callback function to destroy any data attached to it. + */ +extern void mowgli_dictionary_destroy(mowgli_dictionary_t *dtree, + void (*destroy_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_foreach() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * To shortcircuit iteration, return non-zero from the callback function. + */ +extern void mowgli_dictionary_foreach(mowgli_dictionary_t *dtree, + int (*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_search() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * When the object is found, a non-NULL is returned from the callback, which results + * in that object being returned to the user. + */ +extern void *mowgli_dictionary_search(mowgli_dictionary_t *dtree, + void *(*foreach_cb)(mowgli_dictionary_elem_t *delem, void *privdata), + void *privdata) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_foreach_start() begins an iteration over all items + * keeping state in the given struct. If there is only one iteration + * in progress at a time, it is permitted to remove the current element + * of the iteration (but not any other element). + */ +extern void mowgli_dictionary_foreach_start(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_foreach_cur() returns the current element of the iteration, + * or NULL if there are no more elements. + */ +extern void *mowgli_dictionary_foreach_cur(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_foreach_next() moves to the next element. + */ +extern void mowgli_dictionary_foreach_next(mowgli_dictionary_t *dtree, + mowgli_dictionary_iteration_state_t *state) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_add() adds a key->value entry to the dictionary tree. + */ +extern mowgli_dictionary_elem_t *mowgli_dictionary_add(mowgli_dictionary_t *dtree, const char *key, void *data) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_find() returns a mowgli_dictionary_elem_t container from a dtree for key 'key'. + */ +extern mowgli_dictionary_elem_t *mowgli_dictionary_find(mowgli_dictionary_t *dtree, const char *key) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_find() returns data from a dtree for key 'key'. + */ +extern void *mowgli_dictionary_retrieve(mowgli_dictionary_t *dtree, const char *key) MOWGLI_DEPRECATED; + +/* + * mowgli_dictionary_delete() deletes a key->value entry from the dictionary tree. + */ +extern void *mowgli_dictionary_delete(mowgli_dictionary_t *dtree, const char *key) MOWGLI_DEPRECATED; + +void mowgli_dictionary_stats(mowgli_dictionary_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) MOWGLI_DEPRECATED; + +#endif diff --git a/src/libmowgli/mowgli_error_backtrace.c b/src/libmowgli/mowgli_error_backtrace.c new file mode 100644 index 0000000..02b7b4e --- /dev/null +++ b/src/libmowgli/mowgli_error_backtrace.c @@ -0,0 +1,109 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_error_backtrace.c: Print errors and explain how they were reached. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +void +mowgli_error_context_display(mowgli_error_context_t *e, const char *delim) +{ + mowgli_node_t *n; + char *bt_msg; + + return_if_fail(e != NULL); + return_if_fail(delim != NULL); + + if (MOWGLI_LIST_LENGTH(&e->bt) == 0) + mowgli_throw_exception(mowgli.error_backtrace.no_backtrace); + + MOWGLI_LIST_FOREACH(n, e->bt.head) + { + bt_msg = (char *) n->data; + + printf("%s%s", bt_msg, n->next != NULL ? delim : "\n"); + } +} + +void +mowgli_error_context_destroy(mowgli_error_context_t *e) +{ + mowgli_node_t *n, *tn; + + return_if_fail(e != NULL); + + if (MOWGLI_LIST_LENGTH(&e->bt) == 0) + { + mowgli_free(e); + return; + } + + MOWGLI_LIST_FOREACH_SAFE(n, tn, e->bt.head) + { + mowgli_free(n->data); + + mowgli_node_delete(n, &e->bt); + mowgli_node_free(n); + } + + mowgli_free(e); +} + +void +mowgli_error_context_display_with_error(mowgli_error_context_t *e, const char *delim, const char *error) +{ + mowgli_error_context_display(e, delim); + printf("Error: %s\n", error); + + exit(EXIT_FAILURE); +} + +void +mowgli_error_context_push(mowgli_error_context_t *e, const char *msg, ...) +{ + char buf[65535]; + va_list va; + + return_if_fail(e != NULL); + return_if_fail(msg != NULL); + + va_start(va, msg); + vsnprintf(buf, 65535, msg, va); + va_end(va); + + mowgli_node_add(strdup(buf), mowgli_node_create(), &e->bt); +} + +void +mowgli_error_context_pop(mowgli_error_context_t *e) +{ + return_if_fail(e != NULL); + + mowgli_node_delete(e->bt.tail, &e->bt); +} + +mowgli_error_context_t * +mowgli_error_context_create(void) +{ + mowgli_error_context_t *out = (mowgli_error_context_t *) mowgli_alloc(sizeof(mowgli_error_context_t)); + + return out; +} diff --git a/src/libmowgli/mowgli_error_backtrace.h b/src/libmowgli/mowgli_error_backtrace.h new file mode 100644 index 0000000..57970b0 --- /dev/null +++ b/src/libmowgli/mowgli_error_backtrace.h @@ -0,0 +1,38 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_error_backtrace.h: Print errors and explain how they were reached. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ERROR_BACKTRACE_H__ +#define __MOWGLI_ERROR_BACKTRACE_H__ + +typedef struct mowgli_error_context_ { + mowgli_list_t bt; +} mowgli_error_context_t; + +extern void mowgli_error_context_display(mowgli_error_context_t *e, const char *delim); +extern void mowgli_error_context_display_with_error(mowgli_error_context_t *e, const char *delim, const char *error); +extern void mowgli_error_context_destroy(mowgli_error_context_t *e); +extern void mowgli_error_context_push(mowgli_error_context_t *e, const char *msg, ...); +extern void mowgli_error_context_pop(mowgli_error_context_t *e); +extern mowgli_error_context_t *mowgli_error_context_create(void); + +#endif diff --git a/src/libmowgli/mowgli_exception.h b/src/libmowgli/mowgli_exception.h new file mode 100644 index 0000000..c919bcb --- /dev/null +++ b/src/libmowgli/mowgli_exception.h @@ -0,0 +1,37 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_exception.h: Exceptions. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_EXCEPTION_H__ +#define __MOWGLI_EXCEPTION_H__ + +#define mowgli_throw_exception(x) do { mowgli_log("exception %s thrown", #x); return; } while(0) + +#define mowgli_throw_exception_val(x, y) do { mowgli_log("exception %s thrown", #x); return (y); } while(0) + +#define mowgli_throw_exception_fatal(x) \ + do { \ + mowgli_log("exception %s thrown", #x); \ + exit(EXIT_FAILURE); \ + } while (0) + +#endif diff --git a/src/libmowgli/mowgli_formatter.c b/src/libmowgli/mowgli_formatter.c new file mode 100644 index 0000000..b6aa1cc --- /dev/null +++ b/src/libmowgli/mowgli_formatter.c @@ -0,0 +1,119 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_formatter.c: Reusable formatting. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +void mowgli_formatter_format_from_argstack(char *buf, size_t bufstr, const char *fmtstr, const char *descstr, mowgli_argstack_t *stack) +{ + size_t pos = 0; + char *i = buf; + const char *fiter = fmtstr; + + return_if_fail(buf != NULL); + return_if_fail(fmtstr != NULL); + return_if_fail(descstr != NULL); + + *i = '\0'; + + while (*fiter && pos <= bufstr) + { + int arg; + mowgli_argstack_element_t *e; + + pos = strlen(buf); + + switch(*fiter) + { + case '%': + fiter++; + arg = atoi(fiter); + e = mowgli_node_nth_data(&stack->stack, arg - 1); + + while (isdigit(*fiter)) fiter++; + + if (e == NULL) + { + arg = snprintf(i, bufstr - (i - buf), "(unknown)"); + i += arg; + continue; + } + + switch(e->type) + { + case MOWGLI_ARG_STRING: + arg = snprintf(i, bufstr - (i - buf), "%s", e->data.string); + i += arg; + break; + case MOWGLI_ARG_NUMERIC: + arg = snprintf(i, bufstr - (i - buf), "%d", e->data.numeric); + i += arg; + break; + case MOWGLI_ARG_POINTER: + arg = snprintf(i, bufstr - (i - buf), "%p", e->data.pointer); + i += arg; + break; + case MOWGLI_ARG_BOOLEAN: + arg = snprintf(i, bufstr - (i - buf), "%s", e->data.boolean ? "TRUE" : "FALSE"); + i += arg; + break; + default: + mowgli_throw_exception(mowgli.formatter.unhandled_type_exception); + break; + } + + continue; + break; + default: + *i = *fiter; + } + + i++; + fiter++; + } +} + +void mowgli_formatter_format(char *buf, size_t bufstr, const char *fmtstr, const char *descstr, ...) +{ + va_list va; + mowgli_argstack_t *stack; + + va_start(va, descstr); + stack = mowgli_argstack_create_from_va_list(descstr, va); + va_end(va); + + mowgli_formatter_format_from_argstack(buf, bufstr, fmtstr, descstr, stack); +} + +void mowgli_formatter_print(const char *fmtstr, const char *descstr, ...) +{ + va_list va; + char buf[65535]; + mowgli_argstack_t *stack; + + va_start(va, descstr); + stack = mowgli_argstack_create_from_va_list(descstr, va); + va_end(va); + + mowgli_formatter_format_from_argstack(buf, 65535, fmtstr, descstr, stack); + printf("%s", buf); +} diff --git a/src/libmowgli/mowgli_formatter.h b/src/libmowgli/mowgli_formatter.h new file mode 100644 index 0000000..2631ad6 --- /dev/null +++ b/src/libmowgli/mowgli_formatter.h @@ -0,0 +1,31 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_formatter.h: Reusable formatting. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_FORMATTER_H__ +#define __MOWGLI_FORMATTER_H__ + +extern void mowgli_formatter_format(char *buf, size_t bufstr, const char *fmtstr, const char *descstr, ...); +extern void mowgli_formatter_print(const char *fmtstr, const char *descstr, ...); +extern void mowgli_formatter_format_from_argstack(char *buf, size_t bufstr, const char *fmtstr, const char *descstr, mowgli_argstack_t *stack); + +#endif diff --git a/src/libmowgli/mowgli_global_storage.c b/src/libmowgli/mowgli_global_storage.c new file mode 100644 index 0000000..c74c6cb --- /dev/null +++ b/src/libmowgli/mowgli_global_storage.c @@ -0,0 +1,68 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_global_storage.c: Simple key->value global storage tool. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_patricia_t *mowgli_global_storage_dict = NULL; +static mowgli_spinlock_t *mowgli_global_storage_lock = NULL; + +static void _storage_key_canon(char *key) +{ + +} + +void +mowgli_global_storage_init(void) +{ + mowgli_global_storage_dict = mowgli_patricia_create(_storage_key_canon); + mowgli_global_storage_lock = mowgli_spinlock_create(); +} + +void * +mowgli_global_storage_get(char *name) +{ + void *ret; + + /* name serves as lock token */ + mowgli_spinlock_lock(mowgli_global_storage_lock, name, NULL); + ret = mowgli_patricia_retrieve(mowgli_global_storage_dict, name); + mowgli_spinlock_unlock(mowgli_global_storage_lock, name, NULL); + + return ret; +} + +void +mowgli_global_storage_put(char *name, void *value) +{ + mowgli_spinlock_lock(mowgli_global_storage_lock, NULL, name); + mowgli_patricia_add(mowgli_global_storage_dict, name, value); + mowgli_spinlock_unlock(mowgli_global_storage_lock, NULL, name); +} + +void +mowgli_global_storage_free(char *name) +{ + mowgli_spinlock_lock(mowgli_global_storage_lock, name, name); + mowgli_patricia_delete(mowgli_global_storage_dict, name); + mowgli_spinlock_unlock(mowgli_global_storage_lock, name, name); +} diff --git a/src/libmowgli/mowgli_global_storage.h b/src/libmowgli/mowgli_global_storage.h new file mode 100644 index 0000000..aa60c03 --- /dev/null +++ b/src/libmowgli/mowgli_global_storage.h @@ -0,0 +1,32 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_global_storage.h: Simple key->value global storage tool. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef MOWGLI_GLOBAL_STORAGE_H +#define MOWGLI_GLOBAL_STORAGE_H + +extern void mowgli_global_storage_init(void); +extern void *mowgli_global_storage_get(char *name); +extern void mowgli_global_storage_put(char *name, void *value); +extern void mowgli_global_storage_free(char *name); + +#endif diff --git a/src/libmowgli/mowgli_hash.c b/src/libmowgli/mowgli_hash.c new file mode 100644 index 0000000..3f331e4 --- /dev/null +++ b/src/libmowgli/mowgli_hash.c @@ -0,0 +1,66 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_hash.c: FNV-1 hashing implementation. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +#define HASHINIT 0x811c9dc5 +#define HASHBITS 16 +#define HASHSIZE (1 << HASHBITS) /* 2^16 = 65536 */ + +int mowgli_fnv_hash_string(const char *p) +{ + static int htoast = 0; + unsigned int hval = HASHINIT; + + if (htoast == 0) + htoast = rand(); + + if (!p) + return (0); + for (; *p != '\0'; ++p) + { + hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); + hval ^= (tolower(*p) ^ htoast); + } + + return ((hval >> HASHBITS) ^ (hval & ((1 << HASHBITS) - 1)) % HASHSIZE); +} + +int mowgli_fnv_hash(unsigned int *p) +{ + static int htoast = 0; + unsigned int hval = HASHINIT; + + if (htoast == 0) + htoast = rand(); + + if (!p) + return (0); + for (; *p != '\0'; ++p) + { + hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); + hval ^= (tolower(*p) ^ htoast); + } + + return ((hval >> HASHBITS) ^ (hval & ((1 << HASHBITS) - 1)) % HASHSIZE); +} diff --git a/src/libmowgli/mowgli_hash.h b/src/libmowgli/mowgli_hash.h new file mode 100644 index 0000000..e8e04cd --- /dev/null +++ b/src/libmowgli/mowgli_hash.h @@ -0,0 +1,30 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_hash.h: FNV-1 hashing implementation. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_HASH_H__ +#define __MOWGLI_HASH_H__ + +extern int mowgli_fnv_hash_string(const char *data); +extern int mowgli_fnv_hash(unsigned int *data); + +#endif diff --git a/src/libmowgli/mowgli_heap.c b/src/libmowgli/mowgli_heap.c new file mode 100644 index 0000000..532517a --- /dev/null +++ b/src/libmowgli/mowgli_heap.c @@ -0,0 +1,323 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_heap.c: Heap allocation. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2005-2006 Theo Julienne <terminal -at- atheme.org> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + * Legal note: code devised from claro.base.block module r288 (Pre MPL) + */ + +#include "mowgli.h" + +#ifdef HAVE_MMAP +# include <sys/mman.h> +# if !defined(MAP_ANON) && defined(MAP_ANONYMOUS) +# define MAP_ANON MAP_ANONYMOUS +# endif +#endif + +/* A block of memory allocated to the allocator */ +struct mowgli_block_ +{ + mowgli_node_t node; + + /* link back to our heap */ + mowgli_heap_t *heap; + + /* pointer to the first item */ + void *data; + + /* singly linked list of free items */ + void *first_free; + + int num_allocated; +}; + +/* A pile of blocks */ +struct mowgli_heap_ +{ + mowgli_node_t node; + + unsigned int elem_size; + unsigned int mowgli_heap_elems; + unsigned int free_elems; + + unsigned int alloc_size; + + unsigned int flags; + + mowgli_list_t blocks; /* list of non-empty blocks */ + + mowgli_allocation_policy_t *allocator; + mowgli_boolean_t use_mmap; + + mowgli_block_t *empty_block; /* a single entirely free block, or NULL */ +}; + +typedef struct mowgli_heap_elem_header_ mowgli_heap_elem_header_t; + +struct mowgli_heap_elem_header_ +{ + union + { + mowgli_block_t *block; /* for allocated elems: block ptr */ + mowgli_heap_elem_header_t *next; /* for free elems: next free */ + } un; +}; + +/* expands a mowgli_heap_t by 1 block */ +static void +mowgli_heap_expand(mowgli_heap_t *bh) +{ + mowgli_block_t *block = NULL; + void *blp = NULL; + mowgli_heap_elem_header_t *node, *prev; + char *offset; + unsigned int a; + + size_t blp_size = sizeof(mowgli_block_t) + (bh->alloc_size * bh->mowgli_heap_elems); + + return_if_fail(bh->empty_block == NULL); + +#if defined(HAVE_MMAP) && defined(MAP_ANON) + if (bh->use_mmap) + blp = mmap(NULL, sizeof(mowgli_block_t) + (bh->alloc_size * bh->mowgli_heap_elems), + PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0); + else +#endif + { + if (bh->allocator) + blp = bh->allocator->allocate(blp_size); + else + blp = mowgli_alloc(blp_size); + } + + block = (mowgli_block_t *)blp; + + offset = (char*)blp + sizeof(mowgli_block_t); + block->data = offset; + block->heap = bh; + + prev = NULL; + + for (a = 0; a < bh->mowgli_heap_elems; a++) + { + node = (mowgli_heap_elem_header_t *)offset; + node->un.next = prev; + offset += bh->alloc_size; + prev = node; + } + + block->first_free = prev; + + bh->empty_block = block; + bh->free_elems += bh->mowgli_heap_elems; +} + +/* shrinks a mowgli_heap_t by 1 block. */ +static void +mowgli_heap_shrink(mowgli_heap_t *heap, mowgli_block_t *b) +{ + return_if_fail(b != NULL); + + if (b == heap->empty_block) + heap->empty_block = NULL; + else + mowgli_node_delete(&b->node, &heap->blocks); + +#ifdef HAVE_MMAP + if (heap->use_mmap) + munmap(b, sizeof(mowgli_block_t) + (heap->alloc_size * heap->mowgli_heap_elems)); + else +#endif + if (heap->allocator) + heap->allocator->deallocate(b); + else + mowgli_free(b); + + heap->free_elems -= heap->mowgli_heap_elems; +} + +/* creates a new mowgli_heap_t */ +mowgli_heap_t * +mowgli_heap_create_full(size_t elem_size, size_t mowgli_heap_elems, unsigned int flags, + mowgli_allocation_policy_t *allocator) +{ + mowgli_heap_t *bh = mowgli_alloc(sizeof(mowgli_heap_t)); + int numpages, pagesize; + + bh->elem_size = elem_size; + bh->mowgli_heap_elems = mowgli_heap_elems; + /* at least 2, this avoids some silly special cases */ + if (bh->mowgli_heap_elems < 2) + bh->mowgli_heap_elems = 2; + bh->free_elems = 0; + + bh->alloc_size = bh->elem_size + sizeof(mowgli_heap_elem_header_t); + + /* don't waste part of a page */ + if (allocator == NULL) + { +#ifdef HAVE_MMAP + pagesize = getpagesize(); +#else + pagesize = 4096; +#endif + numpages = (sizeof(mowgli_block_t) + (bh->alloc_size * bh->mowgli_heap_elems) + pagesize - 1) / pagesize; + bh->mowgli_heap_elems = (numpages * pagesize - sizeof(mowgli_block_t)) / bh->alloc_size; + } + + bh->flags = flags; + + bh->allocator = allocator ? allocator : mowgli_allocator_malloc; + +#ifdef HAVE_MMAP + bh->use_mmap = allocator != NULL ? FALSE : TRUE; +#endif + + if (flags & BH_NOW) + mowgli_heap_expand(bh); + + return bh; +} + +mowgli_heap_t * +mowgli_heap_create(size_t elem_size, size_t mowgli_heap_elems, unsigned int flags) +{ + return mowgli_heap_create_full(elem_size, mowgli_heap_elems, flags, NULL); +} + +/* completely frees a mowgli_heap_t and all blocks */ +void +mowgli_heap_destroy(mowgli_heap_t *heap) +{ + mowgli_node_t *n, *tn; + + MOWGLI_LIST_FOREACH_SAFE(n, tn, heap->blocks.head) + { + mowgli_heap_shrink(heap, n->data); + } + if (heap->empty_block) + mowgli_heap_shrink(heap, heap->empty_block); + + /* everything related to heap has gone, time for itself */ + mowgli_free(heap); +} + +/* allocates a new item from a mowgli_heap_t */ +void * +mowgli_heap_alloc(mowgli_heap_t *heap) +{ + mowgli_node_t *n; + mowgli_block_t *b; + mowgli_heap_elem_header_t *h; + + /* no free space? */ + if (heap->free_elems == 0) + { + mowgli_heap_expand(heap); + + return_val_if_fail(heap->free_elems != 0, NULL); + } + + /* try a partially used block before using a fully free block */ + n = heap->blocks.head; + b = n != NULL ? n->data : NULL; + if (b == NULL || b->first_free == NULL) + b = heap->empty_block; + /* due to above check */ + return_val_if_fail(b != NULL, NULL); + + /* pull the first free node from the list */ + h = b->first_free; + return_val_if_fail(h != NULL, NULL); + + /* mark it as used */ + b->first_free = h->un.next; + h->un.block = b; + + /* keep count */ + heap->free_elems--; + b->num_allocated++; + + /* move it between the lists if needed */ + /* note that a block has at least two items in it, so these cases + * cannot both occur in the same allocation */ + if (b->num_allocated == 1) + { + heap->empty_block = NULL; + mowgli_node_add_head(b, &b->node, &heap->blocks); + } + else if (b->first_free == NULL) + { + /* move full blocks to the end of the list */ + mowgli_node_delete(&b->node, &heap->blocks); + mowgli_node_add(b, &b->node, &heap->blocks); + } + +#ifdef HEAP_DEBUG + /* debug */ + mowgli_log("mowgli_heap_alloc(heap = @%p) -> %p", heap, fn->data); +#endif + /* return pointer to it */ + return (char *)h + sizeof(mowgli_heap_elem_header_t); +} + +/* frees an item back to the mowgli_heap_t */ +void +mowgli_heap_free(mowgli_heap_t *heap, void *data) +{ + mowgli_block_t *b; + mowgli_heap_elem_header_t *h; + + h = (mowgli_heap_elem_header_t *)((char *)data - sizeof(mowgli_heap_elem_header_t)); + b = h->un.block; + + return_if_fail(b->heap == heap); + return_if_fail(b->num_allocated > 0); + + /* memset the element before returning it to the heap. */ + memset(data, 0, b->heap->elem_size); + + /* mark it as free */ + h->un.next = b->first_free; + b->first_free = h; + + /* keep count */ + heap->free_elems++; + b->num_allocated--; +#ifdef HEAP_DEBUG + /* debug */ + mowgli_log("mowgli_heap_free(heap = @%p, data = %p)", heap, data); +#endif + /* move it between the lists if needed */ + if (b->num_allocated == 0) + { + if (heap->empty_block != NULL) + mowgli_heap_shrink(heap, heap->empty_block); + mowgli_node_delete(&b->node, &heap->blocks); + heap->empty_block = b; + } + else if (b->num_allocated == heap->mowgli_heap_elems - 1) + { + mowgli_node_delete(&b->node, &heap->blocks); + mowgli_node_add_head(b, &b->node, &heap->blocks); + } +} diff --git a/src/libmowgli/mowgli_heap.h b/src/libmowgli/mowgli_heap.h new file mode 100644 index 0000000..8a38f55 --- /dev/null +++ b/src/libmowgli/mowgli_heap.h @@ -0,0 +1,50 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_heap.h: Heap allocation. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2005-2006 Theo Julienne <terminal -at- atheme.org> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + * Legal note: code devised from claro.base.block module r288 (Pre MPL) + */ + +#ifndef __MOWGLI_HEAP_H__ +#define __MOWGLI_HEAP_H__ + +typedef struct mowgli_heap_ mowgli_heap_t; +typedef struct mowgli_block_ mowgli_block_t; + +/* Flag for mowgli_heap_create */ +#define BH_DONTCARE 0 + +#define BH_NOW 1 +#define BH_LAZY 0 + +/* Functions for heaps */ +extern mowgli_heap_t *mowgli_heap_create(size_t elem_size, size_t mowgli_heap_elems, unsigned int flags); +extern mowgli_heap_t *mowgli_heap_create_full(size_t elem_size, size_t mowgli_heap_elems, unsigned int flags, + mowgli_allocation_policy_t *allocator); +extern void mowgli_heap_destroy(mowgli_heap_t *heap); + +/* Functions for blocks */ +extern void *mowgli_heap_alloc(mowgli_heap_t *heap); +extern void mowgli_heap_free(mowgli_heap_t *heap, void *data); + +#endif + diff --git a/src/libmowgli/mowgli_hook.c b/src/libmowgli/mowgli_hook.c new file mode 100644 index 0000000..8527a6b --- /dev/null +++ b/src/libmowgli/mowgli_hook.c @@ -0,0 +1,146 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_hook.c: Hooks. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Giacomo Lozito <james -at- develia.org> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_patricia_t *mowgli_hooks = NULL; +static mowgli_heap_t *mowgli_hook_item_heap; + +static void _hook_key_canon(char *str) +{ + while (*str) + { + *str = toupper(*str); + str++; + } +} + +void +mowgli_hook_init(void) +{ + mowgli_hooks = mowgli_patricia_create(_hook_key_canon); + mowgli_hook_item_heap = mowgli_heap_create(sizeof(mowgli_hook_item_t), 64, BH_NOW); +} + +static mowgli_hook_t * +mowgli_hook_find(const char *name) +{ + return mowgli_patricia_retrieve(mowgli_hooks, name); +} + +void +mowgli_hook_register(const char *name) +{ + mowgli_hook_t *hook; + + return_if_fail(name != NULL); + return_if_fail((hook = mowgli_hook_find(name)) == NULL); + + hook = mowgli_alloc(sizeof(mowgli_hook_t)); + hook->name = strdup(name); + + mowgli_patricia_add(mowgli_hooks, hook->name, hook); +} + +int +mowgli_hook_associate(const char *name, mowgli_hook_function_t func, void *user_data) +{ + mowgli_hook_t *hook; + mowgli_hook_item_t *hookitem; + + return_val_if_fail(name != NULL, -1); + return_val_if_fail(func != NULL, -1); + + hook = mowgli_hook_find(name); + + if (hook == NULL) + { + mowgli_hook_register(name); + hook = mowgli_hook_find(name); + } + + /* this *cant* happen */ + return_val_if_fail(hook != NULL, -1); + + hookitem = mowgli_heap_alloc(mowgli_hook_item_heap); + hookitem->func = func; + hookitem->user_data = user_data; + + mowgli_node_add(hookitem, &hookitem->node, &hook->items); + + return 0; +} + +int +mowgli_hook_dissociate(const char *name, mowgli_hook_function_t func) +{ + mowgli_hook_t *hook; + mowgli_node_t *n, *tn; + + return_val_if_fail(name != NULL, -1); + return_val_if_fail(func != NULL, -1); + + hook = mowgli_hook_find(name); + + if (hook == NULL) + return -1; + + MOWGLI_LIST_FOREACH_SAFE(n, tn, hook->items.head) + { + mowgli_hook_item_t *hookitem = n->data; + + if (hookitem->func == func) + { + mowgli_node_delete(&hookitem->node, &hook->items); + mowgli_heap_free(mowgli_hook_item_heap, hookitem); + + return 0; + } + } + + return -1; +} + +void +mowgli_hook_call(const char *name, void *hook_data) +{ + mowgli_hook_t *hook; + mowgli_node_t *n; + + return_if_fail(name != NULL); + + hook = mowgli_hook_find(name); + + if (hook == NULL) + return; + + MOWGLI_LIST_FOREACH(n, hook->items.head) + { + mowgli_hook_item_t *hookitem = n->data; + + return_if_fail(hookitem->func != NULL); + + hookitem->func(hook_data, hookitem->user_data); + } +} diff --git a/src/libmowgli/mowgli_hook.h b/src/libmowgli/mowgli_hook.h new file mode 100644 index 0000000..2e79086 --- /dev/null +++ b/src/libmowgli/mowgli_hook.h @@ -0,0 +1,47 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_hook.h: Hooks. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Giacomo Lozito <james -at- develia.org> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_HOOK_H__ +#define __MOWGLI_HOOK_H__ + +typedef void (*mowgli_hook_function_t)(void *hook_data, void *user_data); + +typedef struct { + mowgli_hook_function_t func; + void *user_data; + mowgli_node_t node; +} mowgli_hook_item_t; + +typedef struct { + const char *name; + mowgli_list_t items; +} mowgli_hook_t; + +extern void mowgli_hook_init(void); +extern void mowgli_hook_register(const char *name); +extern int mowgli_hook_associate(const char *name, mowgli_hook_function_t func, void * user_data); +extern int mowgli_hook_dissociate(const char *name, mowgli_hook_function_t func); +extern void mowgli_hook_call(const char *name, void * hook_data); + +#endif diff --git a/src/libmowgli/mowgli_index.c b/src/libmowgli/mowgli_index.c new file mode 100644 index 0000000..b96b45e --- /dev/null +++ b/src/libmowgli/mowgli_index.c @@ -0,0 +1,175 @@ +/* + * Copyright 2009-2011 John Lindgren + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <stdlib.h> +#include <string.h> +#include <mowgli.h> + +struct mowgli_index_ +{ + void * * data; + int count, size; + int (* compare) (const void * a, const void * b, void * data); + void * compare_data; +}; + +static mowgli_heap_t *index_heap = NULL; + +void mowgli_index_init (void) +{ + index_heap = mowgli_heap_create(sizeof(mowgli_index_t), 32, BH_NOW); +} + +mowgli_index_t * mowgli_index_create (void) +{ + mowgli_index_t * index = mowgli_heap_alloc(index_heap); + + index->data = NULL; + index->count = 0; + index->size = 0; + index->compare = NULL; + index->compare_data = NULL; + + return index; +} + +void mowgli_index_destroy (mowgli_index_t * index) +{ + mowgli_free (index->data); + mowgli_heap_free (index_heap, index); +} + +int mowgli_index_count (mowgli_index_t * index) +{ + return index->count; +} + +void mowgli_index_allocate (mowgli_index_t * index, int size) +{ + if (size <= index->size) + return; + + if (! index->size) + index->size = 64; + + while (size > index->size) + index->size <<= 1; + + index->data = realloc (index->data, sizeof (void *) * index->size); +} + +void mowgli_index_set (mowgli_index_t * index, int at, void * value) +{ + index->data[at] = value; +} + +void * mowgli_index_get (mowgli_index_t * index, int at) +{ + return index->data[at]; +} + +static void make_room (mowgli_index_t * index, int at, int count) +{ + mowgli_index_allocate (index, index->count + count); + + if (at < index->count) + memmove (index->data + at + count, index->data + at, sizeof (void *) * + (index->count - at)); + + index->count += count; +} + +void mowgli_index_insert (mowgli_index_t * index, int at, void * value) +{ + make_room (index, at, 1); + index->data[at] = value; +} + +void mowgli_index_append (mowgli_index_t * index, void * value) +{ + mowgli_index_insert (index, index->count, value); +} + +void mowgli_index_copy_set (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count) +{ + memcpy (target->data + to, source->data + from, sizeof (void *) * count); +} + +void mowgli_index_copy_insert (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count) +{ + make_room (target, to, count); + memcpy (target->data + to, source->data + from, sizeof (void *) * count); +} + +void mowgli_index_copy_append (mowgli_index_t * source, int from, mowgli_index_t * target, + int count) +{ + mowgli_index_copy_insert (source, from, target, target->count, count); +} + +void mowgli_index_merge_insert (mowgli_index_t * first, int at, mowgli_index_t * second) +{ + mowgli_index_copy_insert (second, 0, first, at, second->count); +} + +void mowgli_index_merge_append (mowgli_index_t * first, mowgli_index_t * second) +{ + mowgli_index_copy_insert (second, 0, first, first->count, second->count); +} + +void mowgli_index_move (mowgli_index_t * index, int from, int to, int count) +{ + memmove (index->data + to, index->data + from, sizeof (void *) * count); +} + +void mowgli_index_delete (mowgli_index_t * index, int at, int count) +{ + index->count -= count; + memmove (index->data + at, index->data + at + count, sizeof (void *) * + (index->count - at)); +} + +void mowgli_index_sort (mowgli_index_t * index, int (* compare) (const void *, const void *)) +{ + qsort(index->data, index->count, sizeof (void *), compare); +} + +#ifdef NOTYET +static int mowgli_index_compare_with_data (const void * a, const void * b, void * _index) +{ + mowgli_index_t * index = _index; + + return index->compare (* (const void * *) a, * (const void * *) b, + index->compare_data); +} + +void mowgli_index_sort_with_data (mowgli_index_t * index, int (* compare) + (const void * a, const void * b, void * data), void * data) +{ + index->compare = compare; + index->compare_data = data; + g_qsort_with_data (index->data, index->count, sizeof (void *), + mowgli_index_compare_with_data, index); + index->compare = NULL; + index->compare_data = NULL; +} +#endif diff --git a/src/libmowgli/mowgli_index.h b/src/libmowgli/mowgli_index.h new file mode 100644 index 0000000..85e9e72 --- /dev/null +++ b/src/libmowgli/mowgli_index.h @@ -0,0 +1,51 @@ +/* + * Copyright 2009-2011 John Lindgren + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_INDEX_H__ +#define __MOWGLI_INDEX_H__ + +struct mowgli_index_; + +typedef struct mowgli_index_ mowgli_index_t; + +mowgli_index_t * mowgli_index_create (void); +void mowgli_index_destroy (mowgli_index_t * index); +int mowgli_index_count (mowgli_index_t * index); +void mowgli_index_allocate (mowgli_index_t * index, int size); +void mowgli_index_set (mowgli_index_t * index, int at, void * value); +void * mowgli_index_get (mowgli_index_t * index, int at); +void mowgli_index_insert (mowgli_index_t * index, int at, void * value); +void mowgli_index_append (mowgli_index_t * index, void * value); +void mowgli_index_copy_set (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count); +void mowgli_index_copy_insert (mowgli_index_t * source, int from, mowgli_index_t * target, + int to, int count); +void mowgli_index_copy_append (mowgli_index_t * source, int from, mowgli_index_t * target, + int count); +void mowgli_index_merge_insert (mowgli_index_t * first, int at, mowgli_index_t * second); +void mowgli_index_merge_append (mowgli_index_t * first, mowgli_index_t * second); +void mowgli_index_move (mowgli_index_t * index, int from, int to, int count); +void mowgli_index_delete (mowgli_index_t * index, int at, int count); +void mowgli_index_sort (mowgli_index_t * index, int (* compare) (const void * a, + const void * b)); +void mowgli_index_sort_with_data (mowgli_index_t * index, int (* compare) + (const void * a, const void * b, void * data), void * data); + +#endif diff --git a/src/libmowgli/mowgli_init.c b/src/libmowgli/mowgli_init.c new file mode 100644 index 0000000..5b15aa0 --- /dev/null +++ b/src/libmowgli/mowgli_init.c @@ -0,0 +1,49 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_init.c: Initialization of libmowgli. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +void mowgli_init(void) +{ + static int mowgli_initted_ = 0; + + if (mowgli_initted_) + return; + + /* initial bootstrap */ + mowgli_node_init(); + mowgli_queue_init(); + mowgli_argstack_init(); + mowgli_bitvector_init(); + mowgli_global_storage_init(); + mowgli_hook_init(); + mowgli_random_init(); + mowgli_allocation_policy_init(); + mowgli_allocator_init(); + + /* now that we're bootstrapped, we can use a more optimised allocator + if one is available. */ + mowgli_allocator_set_policy(mowgli_allocator_malloc); + + mowgli_initted_++; +} diff --git a/src/libmowgli/mowgli_init.h b/src/libmowgli/mowgli_init.h new file mode 100644 index 0000000..3ebc7e3 --- /dev/null +++ b/src/libmowgli/mowgli_init.h @@ -0,0 +1,29 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_init.c: Initialization of libmowgli. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_INIT_H__ +#define __MOWGLI_INIT_H__ + +extern void mowgli_init(void); + +#endif diff --git a/src/libmowgli/mowgli_ioevent.c b/src/libmowgli/mowgli_ioevent.c new file mode 100644 index 0000000..ed08cb9 --- /dev/null +++ b/src/libmowgli/mowgli_ioevent.c @@ -0,0 +1,195 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_ioevent.c: Portable I/O event layer. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +#ifdef HAVE_EPOLL_CTL +# include <sys/epoll.h> +#endif + +#ifdef HAVE_PORT_CREATE +# include <port.h> +#endif + +mowgli_ioevent_handle_t *mowgli_ioevent_create(void) +{ + mowgli_ioevent_handle_t *self = mowgli_alloc(sizeof(mowgli_ioevent_handle_t)); + +#ifdef HAVE_EPOLL_CTL + self->impldata = epoll_create(FD_SETSIZE); +#endif + +#ifdef HAVE_PORT_CREATE + self->impldata = port_create(); +#endif + + return self; +} + +void mowgli_ioevent_destroy(mowgli_ioevent_handle_t *self) +{ + return_if_fail(self != NULL); + +#if defined(HAVE_EPOLL_CTL) || defined(HAVE_PORT_CREATE) + close(self->impldata); +#endif + + mowgli_free(self); +} + +int mowgli_ioevent_get(mowgli_ioevent_handle_t *self, mowgli_ioevent_t *buf, size_t bufsize, unsigned int delay) +{ +#if defined HAVE_EPOLL_CTL || defined HAVE_PORT_CREATE + int ret, iter; +#else + int ret = -1; +#endif + +#ifdef HAVE_EPOLL_CTL + struct epoll_event events[bufsize]; + + ret = epoll_wait(self->impldata, events, bufsize, delay); + + if (ret == -1) + return ret; + + for (iter = 0; iter < ret; iter++) + { + buf[iter].ev_status = 0; + buf[iter].ev_object = events[iter].data.fd; + buf[iter].ev_opaque = events[iter].data.ptr; + buf[iter].ev_source = MOWGLI_SOURCE_FD; + + if (events[iter].events & EPOLLIN) + buf[iter].ev_status |= MOWGLI_POLLRDNORM; + + if (events[iter].events & EPOLLOUT) + buf[iter].ev_status |= MOWGLI_POLLWRNORM; + + if (events[iter].events & EPOLLHUP) + buf[iter].ev_status = MOWGLI_POLLHUP; + + if (events[iter].events & EPOLLERR) + buf[iter].ev_status = MOWGLI_POLLERR; + } +#endif + +#ifdef HAVE_PORT_CREATE + port_event_t events[bufsize]; + unsigned int nget = 1; + struct timespec poll_time; + + poll_time.tv_sec = delay / 1000; + poll_time.tv_nsec = (delay % 1000) * 1000000; + + ret = port_getn(self->impldata, events, bufsize, &nget, &poll_time); + + if (ret == -1) + return ret; + + for (iter = 0; iter < nget; iter++) + { + buf[iter].ev_status = 0; + buf[iter].ev_object = events[iter].portev_object; + buf[iter].ev_opaque = events[iter].portev_user; + buf[iter].ev_source = MOWGLI_SOURCE_FD; + + if (events[iter].portev_events & POLLRDNORM) + buf[iter].ev_status |= MOWGLI_POLLRDNORM; + + if (events[iter].portev_events & POLLWRNORM) + buf[iter].ev_status |= MOWGLI_POLLWRNORM; + + if (events[iter].portev_events & POLLHUP) + buf[iter].ev_status = MOWGLI_POLLHUP; + + if (events[iter].portev_events & POLLERR) + buf[iter].ev_status = MOWGLI_POLLERR; + } + + ret = nget; +#endif + + return ret; +} + +void mowgli_ioevent_associate(mowgli_ioevent_handle_t *self, mowgli_ioevent_source_t source, int object, unsigned int flags, void *opaque) +{ +#if defined HAVE_EPOLL_CTL || defined HAVE_PORT_CREATE + int events = 0; +#endif + + if (source != MOWGLI_SOURCE_FD) + return; + +#ifdef HAVE_EPOLL_CTL + { + struct epoll_event ep_event = {}; + events = EPOLLONESHOT; + + if (flags & MOWGLI_POLLRDNORM) + events |= EPOLLIN; + + if (flags & MOWGLI_POLLWRNORM) + events |= EPOLLOUT; + + ep_event.events = events; + ep_event.data.ptr = opaque; + + epoll_ctl(self->impldata, EPOLL_CTL_ADD, object, &ep_event); + } +#endif + +#ifdef HAVE_PORT_CREATE +#ifdef POLLRDNORM + if (flags & MOWGLI_POLLRDNORM) + events |= POLLRDNORM; +#endif + +#ifdef EPOLLWRNORM + if (flags & MOWGLI_POLLWRNORM) + events |= EPOLLWRNORM; +#endif + + port_associate(self->impldata, PORT_SOURCE_FD, object, events, opaque); +#endif +} + +void mowgli_ioevent_dissociate(mowgli_ioevent_handle_t *self, mowgli_ioevent_source_t source, int object) +{ + if (source != MOWGLI_SOURCE_FD) + return; + +#ifdef HAVE_EPOLL_CTL + { + struct epoll_event ep_event = {}; + + epoll_ctl(self->impldata, EPOLL_CTL_DEL, object, &ep_event); + } +#endif + +#ifdef HAVE_PORT_CREATE + port_dissociate(self->impldata, PORT_SOURCE_FD, object); +#endif +} + diff --git a/src/libmowgli/mowgli_ioevent.h b/src/libmowgli/mowgli_ioevent.h new file mode 100644 index 0000000..17007b6 --- /dev/null +++ b/src/libmowgli/mowgli_ioevent.h @@ -0,0 +1,55 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_ioevent.h: Portable I/O event layer. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_IOEVENT_H__ +#define __MOWGLI_IOEVENT_H__ + +typedef struct { + int impldata; /* implementation-specific data: this is almost always an FD */ +} mowgli_ioevent_handle_t; + +typedef enum { + MOWGLI_SOURCE_FD = 1 +} mowgli_ioevent_source_t; + +typedef struct { + mowgli_ioevent_source_t ev_source; + unsigned int ev_status; + int ev_object; + void *ev_opaque; +} mowgli_ioevent_t; + +#define MOWGLI_POLLRDNORM 0x01 +#define MOWGLI_POLLWRNORM 0x02 +#define MOWGLI_POLLHUP 0x04 +#define MOWGLI_POLLERR 0x08 + +extern mowgli_ioevent_handle_t *mowgli_ioevent_create(void) MOWGLI_DEPRECATED; +extern void mowgli_ioevent_destroy(mowgli_ioevent_handle_t *self) MOWGLI_DEPRECATED; + +extern int mowgli_ioevent_get(mowgli_ioevent_handle_t *self, mowgli_ioevent_t *buf, size_t bufsize, unsigned int delay) MOWGLI_DEPRECATED; + +extern void mowgli_ioevent_associate(mowgli_ioevent_handle_t *self, mowgli_ioevent_source_t source, int object, unsigned int flags, void *opaque) MOWGLI_DEPRECATED; +extern void mowgli_ioevent_dissociate(mowgli_ioevent_handle_t *self, mowgli_ioevent_source_t source, int object) MOWGLI_DEPRECATED; + +#endif diff --git a/src/libmowgli/mowgli_iterator.h b/src/libmowgli/mowgli_iterator.h new file mode 100644 index 0000000..f99412b --- /dev/null +++ b/src/libmowgli/mowgli_iterator.h @@ -0,0 +1,38 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_iterator.h: Iterators. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_ITERATOR_H__ +#define __MOWGLI_ITERATOR_H__ + +typedef struct _mowgli_iterator { + struct _mowgli_iterator *prev, *next; + void *data; +} mowgli_iterator_t; + +/* The following are macros which can be used with iterators. */ +#define MOWGLI_ITER_FOREACH(n, head) for (n = (head); n; n = n->next) +#define MOWGLI_ITER_FOREACH_NEXT(n, head) for (n = (head); n->next; n = n->next) +#define MOWGLI_ITER_FOREACH_PREV(n, tail) for (n = (tail); n; n = n->prev) +#define MOWGLI_ITER_FOREACH_SAFE(n, tn, head) for (n = (head), tn = n ? n->next : NULL; n != NULL; n = tn, tn = n ? n->next : NULL) + +#endif diff --git a/src/libmowgli/mowgli_list.c b/src/libmowgli/mowgli_list.c new file mode 100644 index 0000000..0e33103 --- /dev/null +++ b/src/libmowgli/mowgli_list.c @@ -0,0 +1,386 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_list.c: Linked lists. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *mowgli_node_heap; +static mowgli_heap_t *mowgli_list_heap; + +void mowgli_node_init(void) +{ + mowgli_node_heap = mowgli_heap_create(sizeof(mowgli_node_t), 1024, BH_NOW); + mowgli_list_heap = mowgli_heap_create(sizeof(mowgli_list_t), 64, BH_NOW); + + if (mowgli_node_heap == NULL || mowgli_list_heap == NULL) + { + mowgli_log("heap allocator failure."); + abort(); + } +} + +/* creates a new node */ +mowgli_node_t *mowgli_node_create(void) +{ + mowgli_node_t *n; + + /* allocate it */ + n = mowgli_heap_alloc(mowgli_node_heap); + + /* initialize */ + n->next = n->prev = n->data = NULL; + + /* return a pointer to the new node */ + return n; +} + +/* frees a node */ +void mowgli_node_free(mowgli_node_t *n) +{ + return_if_fail(n != NULL); + + /* free it */ + mowgli_heap_free(mowgli_node_heap, n); +} + +/* adds a node to the end of a list */ +void mowgli_node_add(void *data, mowgli_node_t *n, mowgli_list_t *l) +{ + mowgli_node_t *tn; + + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + n->next = n->prev = NULL; + n->data = data; + + /* first node? */ + if (l->head == NULL) + { + l->head = n; + l->tail = n; + l->count++; + return; + } + + /* use the cached tail. */ + tn = l->tail; + + /* set the our `prev' to the last node */ + n->prev = tn; + + /* set the last node's `next' to us */ + n->prev->next = n; + + /* set the list's `tail' to us */ + l->tail = n; + + /* up the count */ + l->count++; +} + +/* adds a node to the head of a list */ +void mowgli_node_add_head(void *data, mowgli_node_t *n, mowgli_list_t *l) +{ + mowgli_node_t *tn; + + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + n->next = n->prev = NULL; + n->data = data; + + /* first node? */ + if (!l->head) + { + l->head = n; + l->tail = n; + l->count++; + return; + } + + tn = l->head; + n->next = tn; + tn->prev = n; + l->head = n; + l->count++; +} + +/* adds a node to a list before another node, or to the end */ +void mowgli_node_add_before(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before) +{ + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + if (before == NULL) + mowgli_node_add(data, n, l); + else if (before == l->head) + mowgli_node_add_head(data, n, l); + else + { + n->data = data; + n->prev = before->prev; + n->next = before; + before->prev = n; + n->prev->next = n; + l->count++; + } +} + +/* adds a node to a list after another node, or to the end */ +void mowgli_node_add_after(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before) +{ + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + if (before == NULL || before->next == NULL) + mowgli_node_add(data, n, l); + else + { + n->data = data; + n->prev = before; + n->next = before->next; + before->next = n; + n->next->prev = n; + l->count++; + } +} + +/* retrieves a node at `position` position. */ +mowgli_node_t *mowgli_node_nth(mowgli_list_t *l, int pos) +{ + int iter; + mowgli_node_t *n; + + return_val_if_fail(l != NULL, NULL); + + if (pos < 0) + return NULL; + + /* locate the proper position. */ + if (pos < MOWGLI_LIST_LENGTH(l) / 2) + for (iter = 0, n = l->head; iter != pos && n != NULL; iter++, n = n->next); + else + for (iter = MOWGLI_LIST_LENGTH(l) - 1, n = l->tail; + iter != pos && n != NULL; iter--, n = n->prev); + + return n; +} + +/* returns the data from node at `position` position, or NULL. */ +void *mowgli_node_nth_data(mowgli_list_t *l, int pos) +{ + mowgli_node_t *n; + + return_val_if_fail(l != NULL, NULL); + + n = mowgli_node_nth(l, pos); + + if (n == NULL) + return NULL; + + return n->data; +} + +/* inserts a node at `position` position. */ +void mowgli_node_insert(void *data, mowgli_node_t *n, mowgli_list_t *l, int pos) +{ + mowgli_node_t *tn; + + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + /* locate the proper position. */ + tn = mowgli_node_nth(l, pos); + + mowgli_node_add_before(data, n, l, tn); +} + +/* retrieves the index position of a node in a list. */ +int mowgli_node_index(mowgli_node_t *n, mowgli_list_t *l) +{ + int iter; + mowgli_node_t *tn; + + return_val_if_fail(n != NULL, -1); + return_val_if_fail(l != NULL, -1); + + /* locate the proper position. */ + for (iter = 0, tn = l->head; tn != n && tn != NULL; iter++, tn = tn->next); + + return iter < MOWGLI_LIST_LENGTH(l) ? iter : -1; +} + +/* deletes a link between a node and a list. */ +void mowgli_node_delete(mowgli_node_t *n, mowgli_list_t *l) +{ + return_if_fail(n != NULL); + return_if_fail(l != NULL); + + /* are we the head? */ + if (!n->prev) + l->head = n->next; + else + n->prev->next = n->next; + + /* are we the tail? */ + if (!n->next) + l->tail = n->prev; + else + n->next->prev = n->prev; + + /* down the count */ + l->count--; +} + +/* finds a node by `data' */ +mowgli_node_t *mowgli_node_find(void *data, mowgli_list_t *l) +{ + mowgli_node_t *n; + + return_val_if_fail(l != NULL, NULL); + + MOWGLI_LIST_FOREACH(n, l->head) if (n->data == data) + return n; + + return NULL; +} + +/* moves a node from one list to another. */ +void mowgli_node_move(mowgli_node_t *m, mowgli_list_t *oldlist, mowgli_list_t *newlist) +{ + return_if_fail(m != NULL); + return_if_fail(oldlist != NULL); + return_if_fail(newlist != NULL); + + /* Assumption: If m->next == NULL, then list->tail == m + * and: If m->prev == NULL, then list->head == m + */ + if (m->next != NULL) + m->next->prev = m->prev; + else + oldlist->tail = m->prev; + + if (m->prev != NULL) + m->prev->next = m->next; + else + oldlist->head = m->next; + + m->prev = NULL; + m->next = newlist->head; + + if (newlist->head != NULL) + newlist->head->prev = m; + else if (newlist->tail == NULL) + newlist->tail = m; + + newlist->head = m; + + oldlist->count--; + newlist->count++; +} + +/* creates a new list. */ +mowgli_list_t *mowgli_list_create(void) +{ + mowgli_list_t *out = mowgli_heap_alloc(mowgli_list_heap); + + return out; +} + +/* frees a created list. */ +void mowgli_list_free(mowgli_list_t *l) +{ + mowgli_heap_free(mowgli_list_heap, l); +} + +/* concatenates two lists together. */ +void mowgli_list_concat(mowgli_list_t *l, mowgli_list_t *l2) +{ + return_if_fail(l != NULL); + return_if_fail(l2 != NULL); + + l->tail->next = l2->head; + l->tail->next->prev = l->tail; + l->tail = l2->tail; + l->count += l2->count; + + /* clear out l2 as it is no longer needed. */ + l2->head = l2->tail = NULL; + l2->count = 0; +} + +/* reverse a list -- O(n)! */ +void mowgli_list_reverse(mowgli_list_t *l) +{ + mowgli_node_t *n, *tn; + + return_if_fail(l != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, l->head) + { + mowgli_node_t *tn2 = n->next; + n->next = n->prev; + n->prev = tn2; + } + + tn = l->head; + l->head = l->tail; + l->tail = tn; +} + +/* sorts a list -- O(n ^ 2) most likely, i don't want to think about it. --nenolod */ +void mowgli_list_sort(mowgli_list_t *l, mowgli_list_comparator_t comp, void *opaque) +{ + mowgli_node_t *n, *tn, *n2, *tn2; + + return_if_fail(l != NULL); + return_if_fail(comp != NULL); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, l->head) + { + MOWGLI_LIST_FOREACH_SAFE(n2, tn2, l->head) + { + int result; + int i, i2; + + if (n == n2) + continue; + + i = mowgli_node_index(n, l); + i2 = mowgli_node_index(n2, l); + + if ((result = comp(n, n2, opaque)) == 0) + continue; + else if (result < 0 && i > i2) + { + mowgli_node_delete(n, l); + mowgli_node_add_before(n->data, n, l, n2); + } + else if (result > 0 && i < i2) + { + mowgli_node_delete(n, l); + mowgli_node_add_after(n->data, n, l, n2); + } + } + } +} diff --git a/src/libmowgli/mowgli_list.h b/src/libmowgli/mowgli_list.h new file mode 100644 index 0000000..2699686 --- /dev/null +++ b/src/libmowgli/mowgli_list.h @@ -0,0 +1,76 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_list.c: Linked lists. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_LIST_H__ +#define __MOWGLI_LIST_H__ + +/* macros for linked lists */ +#define MOWGLI_LIST_FOREACH(n, head) for (n = (head); n; n = n->next) +#define MOWGLI_LIST_FOREACH_NEXT(n, head) for (n = (head); n->next; n = n->next) +#define MOWGLI_LIST_FOREACH_PREV(n, tail) for (n = (tail); n; n = n->prev) + +#define MOWGLI_LIST_LENGTH(list) (list)->count + +#define MOWGLI_LIST_FOREACH_SAFE(n, tn, head) for (n = (head), tn = n ? n->next : NULL; n != NULL; n = tn, tn = n ? n->next : NULL) + +/* list node struct */ +typedef struct mowgli_node_ mowgli_node_t; +typedef struct mowgli_list_ mowgli_list_t; + +struct mowgli_node_ +{ + struct mowgli_node_ *next, *prev; + void *data; /* pointer to real structure */ +}; + +/* node list struct */ +struct mowgli_list_ +{ + mowgli_node_t *head, *tail; + size_t count; /* how many entries in the list */ +}; + +extern void mowgli_node_init(void); +extern mowgli_node_t *mowgli_node_create(void); +extern void mowgli_node_free(mowgli_node_t *n); +extern void mowgli_node_add(void *data, mowgli_node_t *n, mowgli_list_t *l); +extern void mowgli_node_add_head(void *data, mowgli_node_t *n, mowgli_list_t *l); +extern void mowgli_node_add_before(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before); +extern void mowgli_node_add_after(void *data, mowgli_node_t *n, mowgli_list_t *l, mowgli_node_t *before); +extern void mowgli_node_insert(void *data, mowgli_node_t *n, mowgli_list_t *l, int position); +extern int mowgli_node_index(mowgli_node_t *n, mowgli_list_t *l); +extern void mowgli_node_delete(mowgli_node_t *n, mowgli_list_t *l); +extern mowgli_node_t *mowgli_node_find(void *data, mowgli_list_t *l); +extern void mowgli_node_move(mowgli_node_t *m, mowgli_list_t *oldlist, mowgli_list_t *newlist); +extern mowgli_node_t *mowgli_node_nth(mowgli_list_t *l, int pos); +extern void *mowgli_node_nth_data(mowgli_list_t *l, int pos); + +typedef int (*mowgli_list_comparator_t)(mowgli_node_t *n, mowgli_node_t *n2, void *opaque); + +extern mowgli_list_t *mowgli_list_create(void); +extern void mowgli_list_free(mowgli_list_t *l); +extern void mowgli_list_concat(mowgli_list_t *l, mowgli_list_t *l2); +extern void mowgli_list_reverse(mowgli_list_t *l); +extern void mowgli_list_sort(mowgli_list_t *l, mowgli_list_comparator_t comp, void *opaque); + +#endif diff --git a/src/libmowgli/mowgli_logger.c b/src/libmowgli/mowgli_logger.c new file mode 100644 index 0000000..e3c13ea --- /dev/null +++ b/src/libmowgli/mowgli_logger.c @@ -0,0 +1,62 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_logger.c: Event and debugging message logging. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +void mowgli_log_cb_default(const char *buf) +{ + fprintf(stderr, "%s\n", buf); +} + +static mowgli_log_cb_t mowgli_log_cb = mowgli_log_cb_default; + +void mowgli_log_real(const char *file, int line, const char *func, const char *fmt, ...) +{ + char buf[65535]; + char snbuf[65535]; + va_list va; + + va_start(va, fmt); + vsnprintf(snbuf, 65535, fmt, va); + va_end(va); + + snprintf(buf, 65535, "(%s:%d) [%s]: %s", file, line, func, snbuf); + + mowgli_log_cb(buf); +} + +void mowgli_log_set_cb(mowgli_log_cb_t callback) +{ + return_if_fail(callback != NULL); + + mowgli_log_cb = callback; +} + +void mowgli_soft_assert_log(const char *asrt, const char *file, int line, const char *function) +{ + char buf[65535]; + + snprintf(buf, sizeof buf, "(%s:%d) [%s]: critical: Assertion '%s' failed.", file, line, function, asrt); + + mowgli_log_cb(buf); +} diff --git a/src/libmowgli/mowgli_logger.h b/src/libmowgli/mowgli_logger.h new file mode 100644 index 0000000..730383a --- /dev/null +++ b/src/libmowgli/mowgli_logger.h @@ -0,0 +1,45 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_logger.h: Event and debugging message logging. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_LOGGER_H__ +#define __MOWGLI_LOGGER_H__ + +typedef void (*mowgli_log_cb_t)(const char *); + +#ifdef __GNUC__ +# define mowgli_log(...) mowgli_log_real(__FILE__, __LINE__, __PRETTY_FUNCTION__, __VA_ARGS__) +#elif defined _MSC_VER +# if _MSC_VER <= 1200 + static __inline void mowgli_log(char *fmt, ...) { /* TODO/UNSUPPORTED */ } +# else +# define mowgli_log(...) mowgli_log_real(__FILE__, __LINE__, __FUNCTION__, __VA_ARGS__) +# endif +#else +# define mowgli_log(...) mowgli_log_real(__FILE__, __LINE__, __func__, __VA_ARGS__) +#endif + +extern void mowgli_log_real(const char *file, int line, const char *func, const char *buf, ...); + +extern void mowgli_log_set_cb(mowgli_log_cb_t callback); + +#endif diff --git a/src/libmowgli/mowgli_mempool.c b/src/libmowgli/mowgli_mempool.c new file mode 100644 index 0000000..c41436c --- /dev/null +++ b/src/libmowgli/mowgli_mempool.c @@ -0,0 +1,199 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_mempool.c: Memory pooling. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +/* visibility of this object is not available to the outside */ +struct mowgli_mempool_t_ { + mowgli_list_t stack; + mowgli_destructor_t destructor; +#ifdef NOTYET + mowgli_mutex_t *mutex; +#endif +}; + +typedef struct { + void *addr; + int refcount; + mowgli_node_t node; +} mowgli_mempool_elem_t; + +mowgli_mempool_t *mowgli_mempool_with_custom_destructor(mowgli_destructor_t destructor) +{ + mowgli_mempool_t *pool; + + pool = mowgli_alloc(sizeof(mowgli_mempool_t)); + pool->destructor = destructor; +#ifdef NOTYET + pool->mutex = mowgli_mutex_create(); +#endif + return pool; +} + +mowgli_mempool_t *mowgli_mempool_create(void) +{ + return mowgli_mempool_with_custom_destructor(mowgli_free); +} + +void *mowgli_mempool_add(mowgli_mempool_t * pool, void * ptr) +{ + mowgli_mempool_elem_t *e = mowgli_alloc(sizeof(mowgli_mempool_elem_t)); + + e->addr = ptr; + e->refcount = 1; + +#ifdef NOTYET + mowgli_mutex_lock(pool->mutex); +#endif + mowgli_node_add(e, &e->node, &pool->stack); +#ifdef NOTYET + mowgli_mutex_unlock(pool->mutex); +#endif + return ptr; +} + +void * +mowgli_mempool_allocate(mowgli_mempool_t * pool, size_t sz) +{ + void * addr; + +#ifdef NOTYET + mowgli_mutex_lock(pool->mutex); +#endif + addr = mowgli_alloc(sz); + mowgli_node_add(addr, mowgli_node_create(), &pool->stack); +#ifdef NOTYET + mowgli_mutex_unlock(pool->mutex); +#endif + return addr; +} + +void +mowgli_mempool_sustain(mowgli_mempool_t * pool, void * addr) +{ + mowgli_node_t *n, *tn; + mowgli_mempool_elem_t *e; + +#ifdef NOTYET + mowgli_mutex_lock(pool->mutex); +#endif + + MOWGLI_LIST_FOREACH_SAFE(n, tn, pool->stack.head) + { + e = (mowgli_mempool_elem_t *) n->data; + + if (e->addr == addr) + ++e->refcount; + } + +#ifdef NOTYET + mowgli_mutex_unlock(pool->mutex); +#endif +} + +void +mowgli_mempool_release(mowgli_mempool_t * pool, void * addr) +{ + mowgli_node_t *n, *tn; + mowgli_mempool_elem_t *e; + +#ifdef NOTYET + mowgli_mutex_lock(pool->mutex); +#endif + + MOWGLI_LIST_FOREACH_SAFE(n, tn, pool->stack.head) + { + e = (mowgli_mempool_elem_t *) n->data; + + if (e->addr == addr && --e->refcount == 0) + { + mowgli_node_delete(n, &pool->stack); + pool->destructor(addr); + mowgli_free(e); + } + } + +#ifdef NOTYET + mowgli_mutex_unlock(pool->mutex); +#endif +} + +static void +mowgli_mempool_cleanup_nolock(mowgli_mempool_t * pool) +{ + mowgli_node_t *n, *tn; + + MOWGLI_LIST_FOREACH_SAFE(n, tn, pool->stack.head) + { + mowgli_mempool_elem_t *e = (mowgli_mempool_elem_t *) n->data; + + /* don't care about refcounting here. we're killing the entire pool. */ + mowgli_log("mowgli_mempool_t<%p> element at %p was not released until cleanup (refcount: %d)", pool, e->addr, e->refcount); + pool->destructor(e->addr); + mowgli_free(e); + + mowgli_node_delete(n, &pool->stack); + } +} + +void +mowgli_mempool_cleanup(mowgli_mempool_t * pool) +{ +#ifdef NOTYET + mowgli_mutex_lock(pool->mutex); +#endif + mowgli_mempool_cleanup_nolock(pool); +#ifdef NOTYET + mowgli_mutex_unlock(pool->mutex); +#endif +} + +void +mowgli_mempool_destroy(mowgli_mempool_t * pool) +{ +#ifdef NOTYET + mowgli_mutex_lock(pool->mutex); +#endif + + mowgli_mempool_cleanup_nolock(pool); + +#ifdef NOTYET + mowgli_mutex_unlock(pool->mutex); + + mowgli_mutex_free(pool->mutex); +#endif + + mowgli_free(pool); +} + +char * +mowgli_mempool_strdup(mowgli_mempool_t * pool, char * src) +{ + char *out; + size_t sz = strlen(src) + 1; + + out = mowgli_mempool_allocate(pool, sz); + mowgli_strlcpy(out, src, sz); + + return out; +} diff --git a/src/libmowgli/mowgli_mempool.h b/src/libmowgli/mowgli_mempool.h new file mode 100644 index 0000000..14d5911 --- /dev/null +++ b/src/libmowgli/mowgli_mempool.h @@ -0,0 +1,45 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_mempool.h: Memory pooling. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_MEMPOOL_H__ +#define __MOWGLI_MEMPOOL_H__ + +typedef struct mowgli_mempool_t_ mowgli_mempool_t; + +mowgli_mempool_t * mowgli_mempool_create(void); +mowgli_mempool_t * mowgli_mempool_with_custom_destructor(mowgli_destructor_t destructor); + +void * mowgli_mempool_add(mowgli_mempool_t * pool, void * ptr); +void * mowgli_mempool_allocate(mowgli_mempool_t * pool, size_t sz); +void mowgli_mempool_release(mowgli_mempool_t * pool, void * addr); + +void mowgli_mempool_cleanup(mowgli_mempool_t * pool); + +void mowgli_mempool_destroy(mowgli_mempool_t * pool); + +char * mowgli_mempool_strdup(mowgli_mempool_t * pool, char * src); + +#define mowgli_mempool_alloc_object(pool, obj) \ + mowgli_mempool_allocate(pool, sizeof(obj)) + +#endif diff --git a/src/libmowgli/mowgli_module.h b/src/libmowgli/mowgli_module.h new file mode 100644 index 0000000..1ef89b4 --- /dev/null +++ b/src/libmowgli/mowgli_module.h @@ -0,0 +1,33 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_module.h: Loadable modules. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_MODULE_H__ +#define __MOWGLI_MODULE_H__ + +typedef void * mowgli_module_t; + +extern mowgli_module_t mowgli_module_open(const char *path); +extern void * mowgli_module_symbol(mowgli_module_t module, const char *symbol); +extern void mowgli_module_close(mowgli_module_t module); + +#endif diff --git a/src/libmowgli/mowgli_module_posix.c b/src/libmowgli/mowgli_module_posix.c new file mode 100644 index 0000000..dd4a25c --- /dev/null +++ b/src/libmowgli/mowgli_module_posix.c @@ -0,0 +1,69 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_module.c: Loadable modules for POSIX systems. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +#include <dlfcn.h> + +#ifdef __OpenBSD__ +# define RTLD_NOW RTLD_LAZY +#endif + +#ifndef RTLD_LOCAL +#define RTLD_LOCAL 0 +#endif + +mowgli_module_t mowgli_module_open(const char *path) +{ + void *handle = dlopen(path, RTLD_NOW | RTLD_LOCAL); + + /* make sure we have something. make this an assertion so that + * there is feedback if something happens. (poor programming practice). + */ + return_val_if_fail(handle != NULL, NULL); + + return handle; +} + +void * mowgli_module_symbol(mowgli_module_t module, const char *symbol) +{ + void *handle; + + return_val_if_fail(module != NULL, NULL); + + handle = dlsym(module, symbol); + + /* make sure we have something. make this an assertion so that + * there is feedback if something happens. (poor programming practice). + */ + return_val_if_fail(handle != NULL, NULL); + + return handle; +} + +void mowgli_module_close(mowgli_module_t module) +{ + return_if_fail(module != NULL); + + dlclose(module); +} diff --git a/src/libmowgli/mowgli_module_win32.c b/src/libmowgli/mowgli_module_win32.c new file mode 100644 index 0000000..e4b7428 --- /dev/null +++ b/src/libmowgli/mowgli_module_win32.c @@ -0,0 +1,62 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_module_win32.c: Loadable modules under Microsoft Windows. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +#define WIN32_LEAN_AND_MEAN
+#include <windows.h> + +mowgli_module_t mowgli_module_open(const char *path) +{ + HANDLE handle = LoadLibraryA(path); + + /* make sure we have something. make this an assertion so that + * there is feedback if something happens. (poor programming practice). + */ + return_val_if_fail(handle != NULL, NULL); + + return (mowgli_module_t)handle; +} + +void * mowgli_module_symbol(mowgli_module_t module, const char *symbol) +{ + void *handle; + + return_val_if_fail(module != NULL, NULL); + + handle = GetProcAddress((HANDLE)module, symbol); + + /* make sure we have something. make this an assertion so that + * there is feedback if something happens. (poor programming practice). + */ + return_val_if_fail(handle != NULL, NULL); + + return handle; +} + +void mowgli_module_close(mowgli_module_t module) +{ + return_if_fail(module != NULL); + + FreeLibrary((HANDLE)module); +} diff --git a/src/libmowgli/mowgli_object.c b/src/libmowgli/mowgli_object.c new file mode 100644 index 0000000..731f1c5 --- /dev/null +++ b/src/libmowgli/mowgli_object.c @@ -0,0 +1,164 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object.c: Object management. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +/* + * mowgli_object_init + * + * Populates the object manager part of an object. + * + * Inputs: + * - pointer to object manager area + * - (optional) name of object + * - (optional) class of object + * - (optional) custom destructor + * + * Outputs: + * - none + * + * Side Effects: + * - none + */ +void mowgli_object_init(mowgli_object_t *obj, const char *name, mowgli_object_class_t *klass, mowgli_destructor_t des) +{ + return_if_fail(obj != NULL); + + if (name != NULL) + obj->name = strdup(name); + + if (klass != NULL) + obj->klass = klass; + else + { + mowgli_object_class_t *tmp = mowgli_alloc(sizeof(mowgli_object_class_t)); + mowgli_object_class_init(tmp, name, des, TRUE); + obj->klass = tmp; + } + + obj->refcount = 1; + + obj->message_handlers.head = NULL; + obj->message_handlers.tail = NULL; + obj->message_handlers.count = 0; + + obj->metadata.head = NULL; + obj->metadata.tail = NULL; + obj->metadata.count = 0; + + mowgli_object_message_broadcast(obj, "create"); +} + +/* + * mowgli_object_init_from_class + * + * Populates the object manager part of an object from an object class. + * + * Inputs: + * - pointer to object manager area + * - class of object + * + * Outputs: + * - none + * + * Side Effects: + * - none + */ +void +mowgli_object_init_from_class(mowgli_object_t *obj, const char *name, + mowgli_object_class_t *klass) +{ + return_if_fail(obj != NULL); + return_if_fail(klass != NULL); + + mowgli_object_init(obj, name, klass, NULL); +} + +/* + * mowgli_object_ref + * + * Increment the reference counter on an object. + * + * Inputs: + * - the object to refcount + * + * Outputs: + * - none + * + * Side Effects: + * - none + */ +void * mowgli_object_ref(void *object) +{ + return_val_if_fail(object != NULL, NULL); + + mowgli_object(object)->refcount++; + + return object; +} + +/* + * mowgli_object_unref + * + * Decrement the reference counter on an object. + * + * Inputs: + * - the object to refcount + * + * Outputs: + * - none + * + * Side Effects: + * - if the refcount is 0, the object is destroyed. + */ +void mowgli_object_unref(void *object) +{ + mowgli_object_t *obj = mowgli_object(object); + + return_if_fail(object != NULL); + + obj->refcount--; + + if (obj->refcount <= 0) + { + mowgli_object_message_broadcast(obj, "destroy"); + + if (obj->name != NULL) + free(obj->name); + + if (obj->klass != NULL) + { + mowgli_destructor_t destructor = obj->klass->destructor; + + if (obj->klass->dynamic == TRUE) + mowgli_object_class_destroy(obj->klass); + + if (destructor != NULL) + destructor(obj); + else + free(obj); + } + else + mowgli_throw_exception(mowgli.object.invalid_object_class_exception); + } +} diff --git a/src/libmowgli/mowgli_object.h b/src/libmowgli/mowgli_object.h new file mode 100644 index 0000000..5bcee2a --- /dev/null +++ b/src/libmowgli/mowgli_object.h @@ -0,0 +1,42 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object.h: Object management. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_OBJECT_H__ +#define __MOWGLI_OBJECT_H__ + +typedef struct { + char *name; + int refcount; + mowgli_object_class_t *klass; + mowgli_list_t message_handlers; + mowgli_list_t metadata; +} mowgli_object_t; + +extern void mowgli_object_init(mowgli_object_t *, const char *name, mowgli_object_class_t *klass, mowgli_destructor_t destructor); +extern void mowgli_object_init_from_class(mowgli_object_t *, const char *, mowgli_object_class_t *klass); +extern void *mowgli_object_ref(void *); +extern void mowgli_object_unref(void *); + +#define mowgli_object(x) ((mowgli_object_t *) x) + +#endif diff --git a/src/libmowgli/mowgli_object_class.c b/src/libmowgli/mowgli_object_class.c new file mode 100644 index 0000000..8dc2b83 --- /dev/null +++ b/src/libmowgli/mowgli_object_class.c @@ -0,0 +1,132 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object_class.c: Object class and type management, + * cast checking. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_patricia_t *mowgli_object_class_dict = NULL; + +static void _object_key_canon(char *str) +{ + while (*str) + { + *str = toupper(*str); + str++; + } +} + +void mowgli_object_class_init(mowgli_object_class_t *klass, const char *name, mowgli_destructor_t des, mowgli_boolean_t dynamic) +{ + /* if the object_class dictionary has not yet been initialized, we will want to do that. */ + if (mowgli_object_class_dict == NULL) + mowgli_object_class_dict = mowgli_patricia_create(_object_key_canon); + + if (klass == NULL) + mowgli_throw_exception_fatal(mowgli.object_class.invalid_object_class_exception); + + if (mowgli_object_class_find_by_name(name) != NULL) + mowgli_throw_exception_fatal(mowgli.object_class.duplicate_object_class_exception); + + /* initialize object_class::name */ + klass->name = strdup(name); + + /* initialize object_class::derivitives */ + klass->derivitives.head = NULL; + klass->derivitives.tail = NULL; + klass->derivitives.count = 0; + + /* initialize object_class::destructor */ + klass->destructor = des != NULL ? des : mowgli_free; + + /* initialize object_class::dynamic */ + klass->dynamic = dynamic; + + /* add to the object_class index */ + mowgli_patricia_add(mowgli_object_class_dict, klass->name, klass); +} + +int mowgli_object_class_check_cast(mowgli_object_class_t *klass1, mowgli_object_class_t *klass2) +{ + mowgli_node_t *n; + + if (klass1 == NULL || klass2 == NULL) + mowgli_throw_exception_val(mowgli.object_class.invalid_object_class_exception, 0); + + MOWGLI_LIST_FOREACH(n, klass1->derivitives.head) + { + mowgli_object_class_t *tklass = (mowgli_object_class_t *) n->data; + + if (tklass == klass2) + return 1; + } + + return 0; +} + +void mowgli_object_class_set_derivitive(mowgli_object_class_t *klass, mowgli_object_class_t *parent) +{ + if (klass == NULL || parent == NULL) + mowgli_throw_exception_fatal(mowgli.object_class.invalid_object_class_exception); + + mowgli_node_add(klass, mowgli_node_create(), &parent->derivitives); +} + +void *mowgli_object_class_reinterpret_impl(/* mowgli_object_t */ void *opdata, mowgli_object_class_t *klass) +{ + mowgli_object_t *object = mowgli_object(opdata); + + /* this can possibly happen at runtime .. lets not make it a fatal exception. */ + return_val_if_fail(object != NULL, NULL); + return_val_if_fail(klass != NULL, NULL); + + if (mowgli_object_class_check_cast(object->klass, klass)) + return object; + + mowgli_log("Invalid reinterpreted cast from %s<%p> to %s", object->klass->name, klass->name); + return NULL; +} + +mowgli_object_class_t *mowgli_object_class_find_by_name(const char *name) +{ + return mowgli_patricia_retrieve(mowgli_object_class_dict, name); +} + +void mowgli_object_class_destroy(mowgli_object_class_t *klass) +{ + mowgli_node_t *n, *tn; + + if (klass == NULL) + mowgli_throw_exception_fatal(mowgli.object_class.invalid_object_class_exception); + + if (klass->dynamic != TRUE) + mowgli_throw_exception_fatal(mowgli.object_class.nondynamic_object_class_exception); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, klass->derivitives.head) + { + mowgli_node_delete(n, &klass->derivitives); + mowgli_node_free(n); + } + + mowgli_free(klass->name); + mowgli_free(klass); +} diff --git a/src/libmowgli/mowgli_object_class.h b/src/libmowgli/mowgli_object_class.h new file mode 100644 index 0000000..03cfd4b --- /dev/null +++ b/src/libmowgli/mowgli_object_class.h @@ -0,0 +1,61 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object_class.h: Object class and type management, + * cast checking. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_OBJECT_CLASS_H__ +#define __MOWGLI_OBJECT_CLASS_H__ + +typedef void (*mowgli_destructor_t)(void *); + +typedef struct { + char *name; + mowgli_list_t derivitives; + mowgli_destructor_t destructor; + mowgli_boolean_t dynamic; + mowgli_list_t message_handlers; +} mowgli_object_class_t; + +extern void mowgli_object_class_init(mowgli_object_class_t *klass, const char *name, mowgli_destructor_t des, mowgli_boolean_t dynamic); +extern int mowgli_object_class_check_cast(mowgli_object_class_t *klass1, mowgli_object_class_t *klass2); +extern void mowgli_object_class_set_derivitive(mowgli_object_class_t *klass, mowgli_object_class_t *parent); +extern void *mowgli_object_class_reinterpret_impl(/* mowgli_object_t */ void *object, mowgli_object_class_t *klass); +extern mowgli_object_class_t *mowgli_object_class_find_by_name(const char *name); +extern void mowgli_object_class_destroy(mowgli_object_class_t *klass); + +#define MOWGLI_REINTERPRET_CAST(object, klass) (klass *) mowgli_object_class_reinterpret_impl(object, mowgli_object_class_find_by_name( # klass )); + +#define mowgli_forced_cast(from_type, to_type, from, to)\ +do { \ + union cast_union \ + { \ + to_type out; \ + from_type in; \ + } u; \ + typedef int cant_use_union_cast[ \ + sizeof (from_type) == sizeof (u) \ + && sizeof (from_type) == sizeof (to_type) ? 1 : -1];\ + u.in = from; \ + to = u.out; \ +} while (0) + +#endif diff --git a/src/libmowgli/mowgli_object_messaging.c b/src/libmowgli/mowgli_object_messaging.c new file mode 100644 index 0000000..b61a16d --- /dev/null +++ b/src/libmowgli/mowgli_object_messaging.c @@ -0,0 +1,142 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object_messaging.c: Object event notification and message passing. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +void mowgli_object_class_message_handler_attach(mowgli_object_class_t *klass, mowgli_object_message_handler_t *sig) +{ + if (klass == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_object_class_exception); + + if (sig == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_signal_exception); + + mowgli_node_add(sig, mowgli_node_create(), &klass->message_handlers); +} + +void mowgli_object_class_message_handler_detach(mowgli_object_class_t *klass, mowgli_object_message_handler_t *sig) +{ + mowgli_node_t *n; + + if (klass == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_object_class_exception); + + if (sig == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_signal_exception); + + n = mowgli_node_find(sig, &klass->message_handlers); + mowgli_node_delete(n, &klass->message_handlers); + mowgli_node_free(n); +} + +void mowgli_object_message_handler_attach(mowgli_object_t *self, mowgli_object_message_handler_t *sig) +{ + if (self == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_object_exception); + + if (sig == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_signal_exception); + + mowgli_node_add(sig, mowgli_node_create(), &self->message_handlers); +} + +void mowgli_object_message_handler_detach(mowgli_object_t *self, mowgli_object_message_handler_t *sig) +{ + mowgli_node_t *n; + + if (self == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_object_exception); + + if (sig == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_signal_exception); + + n = mowgli_node_find(sig, &self->message_handlers); + mowgli_node_delete(n, &self->message_handlers); + mowgli_node_free(n); +} + +void mowgli_object_message_broadcast(mowgli_object_t *self, const char *name, ...) +{ + mowgli_argstack_t *stack; + mowgli_object_message_handler_t *sig = NULL; + mowgli_node_t *n; + va_list va; + + if (self == NULL) + mowgli_throw_exception(mowgli.object_messaging.invalid_object_exception); + + if (name == NULL) + mowgli_throw_exception(mowgli.null_pointer_exception); + + /* try to find a signal to compile the argument stack from, we start with self::klass first. */ + MOWGLI_LIST_FOREACH(n, self->klass->message_handlers.head) + { + mowgli_object_message_handler_t *sig2 = (mowgli_object_message_handler_t *) n->data; + + if (!strcasecmp(sig2->name, name)) + { + sig = sig2; + break; + } + } + + if (sig == NULL) + { + MOWGLI_LIST_FOREACH(n, self->klass->message_handlers.head) + { + mowgli_object_message_handler_t *sig2 = (mowgli_object_message_handler_t *) n->data; + + if (!strcasecmp(sig2->name, name)) + { + sig = sig2; + break; + } + } + } + + /* return if no signals found, else compile the argstack */ + if (sig == NULL) + return; + + va_start(va, name); + stack = mowgli_argstack_create_from_va_list(sig->descstr, va); + va_end(va); + + MOWGLI_LIST_FOREACH(n, self->klass->message_handlers.head) + { + sig = (mowgli_object_message_handler_t *) n->data; + + if (!strcasecmp(sig->name, name) && sig->handler != NULL) + sig->handler(self, sig, stack); + } + + MOWGLI_LIST_FOREACH(n, self->message_handlers.head) + { + sig = (mowgli_object_message_handler_t *) n->data; + + if (!strcasecmp(sig->name, name) && sig->handler != NULL) + sig->handler(self, sig, stack); + } + + mowgli_object_unref(stack); +} diff --git a/src/libmowgli/mowgli_object_messaging.h b/src/libmowgli/mowgli_object_messaging.h new file mode 100644 index 0000000..8fc1f95 --- /dev/null +++ b/src/libmowgli/mowgli_object_messaging.h @@ -0,0 +1,42 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object_messaging.h: Object event notification and message passing. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_OBJECT_MESSAGING_H__ +#define __MOWGLI_OBJECT_MESSAGING_H__ + +typedef struct mowgli_object_message_handler_ mowgli_object_message_handler_t; +typedef void (*mowgli_object_messaging_func_t)(mowgli_object_t *self, mowgli_object_message_handler_t *sig, mowgli_argstack_t *argstack); + +struct mowgli_object_message_handler_ { + char *name; + char *descstr; + mowgli_object_messaging_func_t handler; +}; + +extern void mowgli_object_class_message_handler_attach(mowgli_object_class_t *klass, mowgli_object_message_handler_t *sig); +extern void mowgli_object_class_message_handler_detach(mowgli_object_class_t *klass, mowgli_object_message_handler_t *sig); +extern void mowgli_object_message_handler_attach(mowgli_object_t *self, mowgli_object_message_handler_t *sig); +extern void mowgli_object_message_handler_detach(mowgli_object_t *self, mowgli_object_message_handler_t *sig); +extern void mowgli_object_message_broadcast(mowgli_object_t *self, const char *name, ...); + +#endif diff --git a/src/libmowgli/mowgli_object_metadata.c b/src/libmowgli/mowgli_object_metadata.c new file mode 100644 index 0000000..9cfece5 --- /dev/null +++ b/src/libmowgli/mowgli_object_metadata.c @@ -0,0 +1,104 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object_metadata.c: Object metadata. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +void mowgli_object_metadata_associate(mowgli_object_t *self, const char *key, void *value) +{ + mowgli_object_metadata_entry_t *e = NULL; + mowgli_node_t *n; + + if (self == NULL) + mowgli_throw_exception(mowgli.object_metadata.invalid_object_exception); + + if (key == NULL) + mowgli_throw_exception(mowgli.null_pointer_exception); + + MOWGLI_LIST_FOREACH(n, self->metadata.head) + { + e = (mowgli_object_metadata_entry_t *) n->data; + + if (!strcasecmp(e->name, key)) + break; + } + + if (e != NULL) + { + e->data = value; + return; + } + + e = mowgli_alloc(sizeof(mowgli_object_metadata_entry_t)); + e->name = strdup(key); + e->data = value; + + mowgli_node_add(e, mowgli_node_create(), &self->metadata); +} + +void mowgli_object_metadata_dissociate(mowgli_object_t *self, const char *key) +{ + mowgli_object_metadata_entry_t *e; + mowgli_node_t *n, *tn; + + if (self == NULL) + mowgli_throw_exception(mowgli.object_metadata.invalid_object_exception); + + if (key == NULL) + mowgli_throw_exception(mowgli.null_pointer_exception); + + MOWGLI_LIST_FOREACH_SAFE(n, tn, self->metadata.head) + { + e = (mowgli_object_metadata_entry_t *) n->data; + + if (!strcasecmp(e->name, key)) + { + mowgli_node_delete(n, &self->metadata); + mowgli_node_free(n); + + mowgli_free(e->name); + mowgli_free(e); + } + } +} + +void *mowgli_object_metadata_retrieve(mowgli_object_t *self, const char *key) +{ + mowgli_object_metadata_entry_t *e; + mowgli_node_t *n; + + if (self == NULL) + mowgli_throw_exception_val(mowgli.object_metadata.invalid_object_exception, NULL); + + if (key == NULL) + mowgli_throw_exception_val(mowgli.null_pointer_exception, NULL); + + MOWGLI_LIST_FOREACH(n, self->metadata.head) + { + e = (mowgli_object_metadata_entry_t *) n->data; + + if (!strcasecmp(e->name, key)) + return e->data; + } + + return NULL; +} diff --git a/src/libmowgli/mowgli_object_metadata.h b/src/libmowgli/mowgli_object_metadata.h new file mode 100644 index 0000000..5f93b8e --- /dev/null +++ b/src/libmowgli/mowgli_object_metadata.h @@ -0,0 +1,36 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_object_metadata.h: Object metadata. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_OBJECT_METADATA_H__ +#define __MOWGLI_OBJECT_METADATA_H__ + +typedef struct { + char *name; + void *data; +} mowgli_object_metadata_entry_t; + +extern void mowgli_object_metadata_associate(mowgli_object_t *self, const char *key, void *value); +extern void mowgli_object_metadata_dissociate(mowgli_object_t *self, const char *key); +extern void *mowgli_object_metadata_retrieve(mowgli_object_t *self, const char *key); + +#endif diff --git a/src/libmowgli/mowgli_patricia.c b/src/libmowgli/mowgli_patricia.c new file mode 100644 index 0000000..cf9af5c --- /dev/null +++ b/src/libmowgli/mowgli_patricia.c @@ -0,0 +1,1000 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_patricia.c: Dictionary-based information storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007-2010 Jilles Tjoelker <jilles -at- stack.nl> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *leaf_heap = NULL; +static mowgli_heap_t *node_heap = NULL; + +/* + * Patricia tree. + * + * A radix trie that avoids one-way branching and redundant nodes. + * + * To find a node, the tree is traversed starting from the root. The + * nibnum in each node indicates which nibble of the key needs to be + * tested, and the appropriate branch is taken. + * + * The nibnum values are strictly increasing while going down the tree. + * + * -- jilles + */ + +union patricia_elem; + +struct mowgli_patricia_ +{ + void (*canonize_cb)(char *key); + union patricia_elem *root; + unsigned int count; + char *id; +}; + +#define POINTERS_PER_NODE 16 +#define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> ((nibnum) & 1 ? 0 : 4)) & 0xF) + +struct patricia_node +{ + /* nibble to test (nibble NUM%2 of byte NUM/2) */ + int nibnum; + /* branches of the tree */ + union patricia_elem *down[POINTERS_PER_NODE]; + union patricia_elem *parent; + char parent_val; +}; + +/* mowgli_patricia_elem_ is the name used in mowgli_patricia.h. + * patricia_leaf is the name historically used here. */ +#define patricia_leaf mowgli_patricia_elem_ + +struct patricia_leaf +{ + /* -1 to indicate this is a leaf, not a node */ + int nibnum; + /* data associated with the key */ + void *data; + /* key (canonized copy) */ + char *key; + union patricia_elem *parent; + char parent_val; +}; + +union patricia_elem +{ + int nibnum; + struct patricia_node node; + struct patricia_leaf leaf; +}; + +#define IS_LEAF(elem) ((elem)->nibnum == -1) + +/* Preserve compatibility with the old mowgli_patricia.h */ +#define STATE_CUR(state) ((state)->pspare[0]) +#define STATE_NEXT(state) ((state)->pspare[1]) + +/* + * first_leaf() + * + * Find the smallest leaf hanging off a subtree. + * + * Inputs: + * - element (may be leaf or node) heading subtree + * + * Outputs: + * - lowest leaf in subtree + * + * Side Effects: + * - none + */ +static union patricia_elem *first_leaf(union patricia_elem *delem) +{ + int val; + + while (!IS_LEAF(delem)) + { + for (val = 0; val < POINTERS_PER_NODE; val++) + { + if (delem->node.down[val] != NULL) + { + delem = delem->node.down[val]; + break; + } + } + } + return delem; +} + +/* + * mowgli_patricia_create(void (*canonize_cb)(char *key)) + * + * Dictionary object factory. + * + * Inputs: + * - function to use for canonizing keys (for example, use + * a function that makes the string upper case to create + * a patricia with case-insensitive matching) + * + * Outputs: + * - on success, a new patricia object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_patricia_t *mowgli_patricia_create(void (*canonize_cb)(char *key)) +{ + mowgli_patricia_t *dtree = (mowgli_patricia_t *) mowgli_alloc(sizeof(mowgli_patricia_t)); + + dtree->canonize_cb = canonize_cb; + + if (!leaf_heap) + leaf_heap = mowgli_heap_create(sizeof(struct patricia_leaf), 1024, BH_NOW); + if (!node_heap) + node_heap = mowgli_heap_create(sizeof(struct patricia_node), 128, BH_NOW); + + dtree->root = NULL; + + return dtree; +} + +/* + * mowgli_patricia_create_named(const char *name, + * void (*canonize_cb)(char *key)) + * + * Dictionary object factory. + * + * Inputs: + * - patricia name + * - function to use for canonizing keys (for example, use + * a function that makes the string upper case to create + * a patricia with case-insensitive matching) + * + * Outputs: + * - on success, a new patricia object. + * + * Side Effects: + * - if services runs out of memory and cannot allocate the object, + * the program will abort. + */ +mowgli_patricia_t *mowgli_patricia_create_named(const char *name, + void (*canonize_cb)(char *key)) +{ + mowgli_patricia_t *dtree = (mowgli_patricia_t *) mowgli_alloc(sizeof(mowgli_patricia_t)); + + dtree->canonize_cb = canonize_cb; + dtree->id = strdup(name); + + if (!leaf_heap) + leaf_heap = mowgli_heap_create(sizeof(struct patricia_leaf), 1024, BH_NOW); + if (!node_heap) + node_heap = mowgli_heap_create(sizeof(struct patricia_node), 128, BH_NOW); + + dtree->root = NULL; + + return dtree; +} + +/* + * mowgli_patricia_destroy(mowgli_patricia_t *dtree, + * void (*destroy_cb)(const char *key, void *data, void *privdata), + * void *privdata); + * + * Recursively destroys all nodes in a patricia tree. + * + * Inputs: + * - patricia tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree and optionally it's children are destroyed. + * + * Notes: + * - if this is called without a callback, the objects bound to the + * DTree will not be destroyed. + */ +void mowgli_patricia_destroy(mowgli_patricia_t *dtree, + void (*destroy_cb)(const char *key, void *data, void *privdata), + void *privdata) +{ + mowgli_patricia_iteration_state_t state; + union patricia_elem *delem; + void *entry; + + return_if_fail(dtree != NULL); + + MOWGLI_PATRICIA_FOREACH(entry, &state, dtree) + { + delem = STATE_CUR(&state); + if (destroy_cb != NULL) + (*destroy_cb)(delem->leaf.key, delem->leaf.data, + privdata); + mowgli_patricia_delete(dtree, delem->leaf.key); + } + + mowgli_free(dtree); +} + +/* + * mowgli_patricia_foreach(mowgli_patricia_t *dtree, + * int (*foreach_cb)(const char *key, void *data, void *privdata), + * void *privdata); + * + * Iterates over all entries in a DTree. + * + * Inputs: + * - patricia tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - nothing + * + * Side Effects: + * - on success, a dtree is iterated + */ +void mowgli_patricia_foreach(mowgli_patricia_t *dtree, + int (*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata) +{ + union patricia_elem *delem, *next; + int val; + + return_if_fail(dtree != NULL); + + delem = dtree->root; + if (delem == NULL) + return; + /* Only one element in the tree */ + if (IS_LEAF(delem)) + { + if (foreach_cb != NULL) + (*foreach_cb)(delem->leaf.key, delem->leaf.data, privdata); + return; + } + val = 0; + do + { + do + next = delem->node.down[val++]; + while (next == NULL && val < POINTERS_PER_NODE); + if (next != NULL) + { + if (IS_LEAF(next)) + { + if (foreach_cb != NULL) + (*foreach_cb)(next->leaf.key, next->leaf.data, privdata); + } + else + { + delem = next; + val = 0; + } + } + while (val >= POINTERS_PER_NODE) + { + val = delem->node.parent_val; + delem = delem->node.parent; + if (delem == NULL) + break; + val++; + } + } while (delem != NULL); +} + +/* + * mowgli_patricia_search(mowgli_patricia_t *dtree, + * void *(*foreach_cb)(const char *key, void *data, void *privdata), + * void *privdata); + * + * Searches all entries in a DTree using a custom callback. + * + * Inputs: + * - patricia tree object + * - optional iteration callback + * - optional opaque/private data to pass to callback + * + * Outputs: + * - on success, the requested object + * - on failure, NULL. + * + * Side Effects: + * - a dtree is iterated until the requested conditions are met + */ +void *mowgli_patricia_search(mowgli_patricia_t *dtree, + void *(*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata) +{ + union patricia_elem *delem, *next; + int val; + void *ret = NULL; + + return_val_if_fail(dtree != NULL, NULL); + + delem = dtree->root; + if (delem == NULL) + return NULL; + /* Only one element in the tree */ + if (IS_LEAF(delem)) + { + if (foreach_cb != NULL) + return (*foreach_cb)(delem->leaf.key, delem->leaf.data, privdata); + return NULL; + } + val = 0; + for (;;) + { + do + next = delem->node.down[val++]; + while (next == NULL && val < POINTERS_PER_NODE); + if (next != NULL) + { + if (IS_LEAF(next)) + { + if (foreach_cb != NULL) + ret = (*foreach_cb)(next->leaf.key, next->leaf.data, privdata); + if (ret != NULL) + break; + } + else + { + delem = next; + val = 0; + } + } + while (val >= POINTERS_PER_NODE) + { + val = delem->node.parent_val; + delem = delem->node.parent; + if (delem == NULL) + break; + val++; + } + } + return ret; +} + +/* + * mowgli_patricia_foreach_start(mowgli_patricia_t *dtree, + * mowgli_patricia_iteration_state_t *state); + * + * Initializes a static DTree iterator. + * + * Inputs: + * - patricia tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is initialized. + */ +void mowgli_patricia_foreach_start(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state) +{ + if (dtree == NULL) + return; + + return_if_fail(state != NULL); + + if (dtree->root != NULL) + STATE_NEXT(state) = first_leaf(dtree->root); + else + STATE_NEXT(state) = NULL; + STATE_CUR(state) = STATE_NEXT(state); + + if (STATE_NEXT(state) == NULL) + return; + + /* make STATE_CUR point to first item and STATE_NEXT point to + * second item */ + mowgli_patricia_foreach_next(dtree, state); +} + +/* + * mowgli_patricia_foreach_cur(mowgli_patricia_t *dtree, + * mowgli_patricia_iteration_state_t *state); + * + * Returns the data from the current node being iterated by the + * static iterator. + * + * Inputs: + * - patricia tree object + * - static DTree iterator + * + * Outputs: + * - reference to data in the current dtree node being iterated + * + * Side Effects: + * - none + */ +void *mowgli_patricia_foreach_cur(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state) +{ + if (dtree == NULL) + return NULL; + + return_val_if_fail(state != NULL, NULL); + + return STATE_CUR(state) != NULL ? + ((struct patricia_leaf *)STATE_CUR(state))->data : NULL; +} + +/* + * mowgli_patricia_foreach_next(mowgli_patricia_t *dtree, + * mowgli_patricia_iteration_state_t *state); + * + * Advances a static DTree iterator. + * + * Inputs: + * - patricia tree object + * - static DTree iterator + * + * Outputs: + * - nothing + * + * Side Effects: + * - the static iterator, &state, is advanced to a new DTree node. + */ +void mowgli_patricia_foreach_next(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state) +{ + struct patricia_leaf *leaf; + union patricia_elem *delem, *next; + int val; + + if (dtree == NULL) + return; + + return_if_fail(state != NULL); + + if (STATE_CUR(state) == NULL) + { + mowgli_log("mowgli_patricia_foreach_next(): called again after iteration finished on dtree<%p>", dtree); + return; + } + + STATE_CUR(state) = STATE_NEXT(state); + + if (STATE_NEXT(state) == NULL) + return; + + leaf = STATE_NEXT(state); + delem = leaf->parent; + val = leaf->parent_val; + + while (delem != NULL) + { + do + next = delem->node.down[val++]; + while (next == NULL && val < POINTERS_PER_NODE); + if (next != NULL) + { + if (IS_LEAF(next)) + { + /* We will find the original leaf first. */ + if (&next->leaf != leaf) + { + if (strcmp(next->leaf.key, leaf->key) < 0) + { + mowgli_log("mowgli_patricia_foreach_next(): iteration went backwards (libmowgli bug) on dtree<%p>", dtree); + STATE_NEXT(state) = NULL; + return; + } + STATE_NEXT(state) = next; + return; + } + } + else + { + delem = next; + val = 0; + } + } + while (val >= POINTERS_PER_NODE) + { + val = delem->node.parent_val; + delem = delem->node.parent; + if (delem == NULL) + break; + val++; + } + } + STATE_NEXT(state) = NULL; +} + +/* + * mowgli_patricia_elem_find(mowgli_patricia_t *dtree, const char *key) + * + * Looks up a DTree node by name. + * + * Inputs: + * - patricia tree object + * - name of node to lookup + * + * Outputs: + * - on success, the dtree node requested + * - on failure, NULL + * + * Side Effects: + * - none + */ +struct patricia_leaf *mowgli_patricia_elem_find(mowgli_patricia_t *dict, const char *key) +{ + char ckey_store[256]; + char *ckey_buf = NULL; + const char *ckey; + union patricia_elem *delem; + int val, keylen; + + return_val_if_fail(dict != NULL, NULL); + return_val_if_fail(key != NULL, NULL); + + keylen = strlen(key); + + if (dict->canonize_cb == NULL) + ckey = key; + else + { + if (keylen >= sizeof ckey_store) + { + ckey_buf = strdup(key); + dict->canonize_cb(ckey_buf); + ckey = ckey_buf; + } + else + { + mowgli_strlcpy(ckey_store, key, sizeof ckey_store); + dict->canonize_cb(ckey_store); + ckey = ckey_store; + } + } + + delem = dict->root; + while (delem != NULL && !IS_LEAF(delem)) + { + if (delem->nibnum / 2 < keylen) + val = NIBBLE_VAL(ckey, delem->nibnum); + else + val = 0; + delem = delem->node.down[val]; + } + /* Now, if the key is in the tree, delem contains it. */ + if (delem != NULL && strcmp(delem->leaf.key, ckey)) + delem = NULL; + + if (ckey_buf != NULL) + free(ckey_buf); + + return &delem->leaf; +} + +/* + * mowgli_patricia_add(mowgli_patricia_t *dtree, const char *key, void *data) + * + * Creates a new DTree node and binds data to it. + * + * Inputs: + * - patricia tree object + * - name for new DTree node + * - data to bind to the new DTree node + * + * Outputs: + * - on success, TRUE + * - on failure, FALSE + * + * Side Effects: + * - data is inserted into the DTree. + */ +struct patricia_leaf *mowgli_patricia_elem_add(mowgli_patricia_t *dict, const char *key, void *data) +{ + char *ckey; + union patricia_elem *delem, *prev, *newnode; + union patricia_elem **place1; + int val, keylen; + int i, j; + + return_val_if_fail(dict != NULL, FALSE); + return_val_if_fail(key != NULL, FALSE); + return_val_if_fail(data != NULL, FALSE); + + keylen = strlen(key); + ckey = strdup(key); + if (ckey == NULL) + { + mowgli_log("major WTF: ckey is NULL, not adding node."); + return NULL; + } + if (dict->canonize_cb != NULL) + dict->canonize_cb(ckey); + + prev = NULL; + val = POINTERS_PER_NODE + 2; /* trap value */ + delem = dict->root; + while (delem != NULL && !IS_LEAF(delem)) + { + prev = delem; + if (delem->nibnum / 2 < keylen) + val = NIBBLE_VAL(ckey, delem->nibnum); + else + val = 0; + delem = delem->node.down[val]; + } + /* Now, if the key is in the tree, delem contains it. */ + if (delem != NULL && !strcmp(delem->leaf.key, ckey)) + { + mowgli_log("Key is already in dict, ignoring duplicate"); + free(ckey); + return NULL; + } + + if (delem == NULL && prev != NULL) + { + /* Get a leaf to compare with. */ + delem = first_leaf(prev); + } + + if (delem == NULL) + { + soft_assert(prev == NULL); + soft_assert(dict->count == 0); + place1 = &dict->root; + *place1 = mowgli_heap_alloc(leaf_heap); + (*place1)->nibnum = -1; + (*place1)->leaf.data = data; + (*place1)->leaf.key = ckey; + (*place1)->leaf.parent = prev; + (*place1)->leaf.parent_val = val; + dict->count++; + return &(*place1)->leaf; + } + + /* Find the first nibble where they differ. */ + for (i = 0; NIBBLE_VAL(ckey, i) == NIBBLE_VAL(delem->leaf.key, i); i++) + ; + /* Find where to insert the new node. */ + while (prev != NULL && prev->nibnum > i) + { + val = prev->node.parent_val; + prev = prev->node.parent; + } + if (prev == NULL || prev->nibnum < i) + { + /* Insert new node below prev */ + newnode = mowgli_heap_alloc(node_heap); + newnode->nibnum = i; + newnode->node.parent = prev; + newnode->node.parent_val = val; + for (j = 0; j < POINTERS_PER_NODE; j++) + newnode->node.down[j] = NULL; + if (prev == NULL) + { + newnode->node.down[NIBBLE_VAL(delem->leaf.key, i)] = dict->root; + if (IS_LEAF(dict->root)) + { + dict->root->leaf.parent = newnode; + dict->root->leaf.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + else + { + soft_assert(dict->root->nibnum > i); + dict->root->node.parent = newnode; + dict->root->node.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + dict->root = newnode; + } + else + { + newnode->node.down[NIBBLE_VAL(delem->leaf.key, i)] = prev->node.down[val]; + if (IS_LEAF(prev->node.down[val])) + { + prev->node.down[val]->leaf.parent = newnode; + prev->node.down[val]->leaf.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + else + { + prev->node.down[val]->node.parent = newnode; + prev->node.down[val]->node.parent_val = NIBBLE_VAL(delem->leaf.key, i); + } + prev->node.down[val] = newnode; + } + } + else + { + /* This nibble is already checked. */ + soft_assert(prev->nibnum == i); + newnode = prev; + } + val = NIBBLE_VAL(ckey, i); + place1 = &newnode->node.down[val]; + soft_assert(*place1 == NULL); + *place1 = mowgli_heap_alloc(leaf_heap); + (*place1)->nibnum = -1; + (*place1)->leaf.data = data; + (*place1)->leaf.key = ckey; + (*place1)->leaf.parent = newnode; + (*place1)->leaf.parent_val = val; + dict->count++; + return &(*place1)->leaf; +} + +mowgli_boolean_t mowgli_patricia_add(mowgli_patricia_t *dict, const char *key, void *data) +{ + return (mowgli_patricia_elem_add(dict, key, data) != NULL) ? TRUE : FALSE; +} + +/* + * mowgli_patricia_delete(mowgli_patricia_t *dtree, const char *key) + * + * Deletes data from a patricia tree. + * + * Inputs: + * - patricia tree object + * - name of DTree node to delete + * + * Outputs: + * - on success, the remaining data that needs to be mowgli_freed + * - on failure, NULL + * + * Side Effects: + * - data is removed from the DTree. + * + * Notes: + * - the returned data needs to be mowgli_freed/released manually! + */ +void *mowgli_patricia_delete(mowgli_patricia_t *dict, const char *key) +{ + void *data; + struct patricia_leaf *leaf; + + leaf = mowgli_patricia_elem_find(dict, key); + if (leaf == NULL) + return NULL; + + data = leaf->data; + mowgli_patricia_elem_delete(dict, leaf); + return data; +} + +void mowgli_patricia_elem_delete(mowgli_patricia_t *dict, struct patricia_leaf *leaf) +{ + union patricia_elem *delem, *prev, *next; + int val, i, used; + + delem = (union patricia_elem *)leaf; + + val = delem->leaf.parent_val; + prev = delem->leaf.parent; + + mowgli_free(delem->leaf.key); + mowgli_heap_free(leaf_heap, delem); + + if (prev != NULL) + { + prev->node.down[val] = NULL; + + /* Leaf is gone, now consider the node it was in. */ + delem = prev; + + used = -1; + for (i = 0; i < POINTERS_PER_NODE; i++) + if (delem->node.down[i] != NULL) + used = used == -1 ? i : -2; + soft_assert(used == -2 || used >= 0); + if (used >= 0) + { + /* Only one pointer in this node, remove it. + * Replace the pointer that pointed to it by + * the sole pointer in it. + */ + next = delem->node.down[used]; + val = delem->node.parent_val; + prev = delem->node.parent; + if (prev != NULL) + prev->node.down[val] = next; + else + dict->root = next; + if (IS_LEAF(next)) + next->leaf.parent = prev, next->leaf.parent_val = val; + else + next->node.parent = prev, next->node.parent_val = val; + mowgli_heap_free(node_heap, delem); + } + } + else + { + /* This was the last leaf. */ + dict->root = NULL; + } + + dict->count--; + if (dict->count == 0) + { + soft_assert(dict->root == NULL); + dict->root = NULL; + } +} + +/* + * mowgli_patricia_retrieve(mowgli_patricia_t *dtree, const char *key) + * + * Retrieves data from a patricia. + * + * Inputs: + * - patricia tree object + * - name of node to lookup + * + * Outputs: + * - on success, the data bound to the DTree node. + * - on failure, NULL + * + * Side Effects: + * - none + */ +void *mowgli_patricia_retrieve(mowgli_patricia_t *dtree, const char *key) +{ + struct patricia_leaf *delem = mowgli_patricia_elem_find(dtree, key); + + if (delem != NULL) + return delem->data; + + return NULL; +} + +const char *mowgli_patricia_elem_get_key(struct patricia_leaf *leaf) +{ + return leaf->key; +} + +void mowgli_patricia_elem_set_data(struct patricia_leaf *leaf, void *data) +{ + leaf->data = data; +} + +void *mowgli_patricia_elem_get_data(struct patricia_leaf *leaf) +{ + return leaf->data; +} + +/* + * mowgli_patricia_size(mowgli_patricia_t *dict) + * + * Returns the size of a patricia. + * + * Inputs: + * - patricia tree object + * + * Outputs: + * - size of patricia + * + * Side Effects: + * - none + */ +unsigned int mowgli_patricia_size(mowgli_patricia_t *dict) +{ + return_val_if_fail(dict != NULL, 0); + + return dict->count; +} + +/* returns the sum of the depths of the subtree rooted in delem at depth depth */ +/* there is no need for this to be recursive, but it is easier... */ +static int +stats_recurse(union patricia_elem *delem, int depth, int *pmaxdepth) +{ + int result = 0; + int val; + union patricia_elem *next; + + if (depth > *pmaxdepth) + *pmaxdepth = depth; + if (depth == 0) + { + if (IS_LEAF(delem)) + { + soft_assert(delem->leaf.parent == NULL); + } + else + { + soft_assert(delem->node.parent == NULL); + } + } + if (IS_LEAF(delem)) + return depth; + for (val = 0; val < POINTERS_PER_NODE; val++) + { + next = delem->node.down[val]; + if (next == NULL) + continue; + result += stats_recurse(next, depth + 1, pmaxdepth); + if (IS_LEAF(next)) + { + soft_assert(next->leaf.parent == delem); + soft_assert(next->leaf.parent_val == val); + } + else + { + soft_assert(next->node.parent == delem); + soft_assert(next->node.parent_val == val); + soft_assert(next->node.nibnum > delem->node.nibnum); + } + } + return result; +} + +/* + * mowgli_patricia_stats(mowgli_patricia_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) + * + * Returns the size of a patricia. + * + * Inputs: + * - patricia tree object + * - callback + * - data for callback + * + * Outputs: + * - none + * + * Side Effects: + * - callback called with stats text + */ +void mowgli_patricia_stats(mowgli_patricia_t *dict, void (*cb)(const char *line, void *privdata), void *privdata) +{ + char str[256]; + int sum, maxdepth; + + return_if_fail(dict != NULL); + + if (dict->id != NULL) + snprintf(str, sizeof str, "Dictionary stats for %s (%d)", + dict->id, dict->count); + else + snprintf(str, sizeof str, "Dictionary stats for <%p> (%d)", + dict, dict->count); + cb(str, privdata); + maxdepth = 0; + if (dict->count > 0) + { + sum = stats_recurse(dict->root, 0, &maxdepth); + snprintf(str, sizeof str, "Depth sum %d Avg depth %d Max depth %d", sum, sum / dict->count, maxdepth); + } + else + snprintf(str, sizeof str, "Depth sum 0 Avg depth 0 Max depth 0"); + cb(str, privdata); + return; +} diff --git a/src/libmowgli/mowgli_patricia.h b/src/libmowgli/mowgli_patricia.h new file mode 100644 index 0000000..6c2c669 --- /dev/null +++ b/src/libmowgli/mowgli_patricia.h @@ -0,0 +1,148 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_patricia.h: Dictionary-based storage. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007-2008 Jilles Tjoelker <jilles -at- stack.nl> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_PATRICIA_H__ +#define __MOWGLI_PATRICIA_H__ + +struct mowgli_patricia_; /* defined in src/patricia.c */ +struct mowgli_patricia_elem_; /* defined in src/patricia.c */ + +typedef struct mowgli_patricia_ mowgli_patricia_t; +typedef struct mowgli_patricia_elem_ mowgli_patricia_elem_t; + +/* + * mowgli_patricia_iteration_state_t, private. + */ +struct mowgli_patricia_iteration_state_ +{ + mowgli_patricia_elem_t *cur, *next; + void *pspare[4]; + int ispare[4]; +}; + +typedef struct mowgli_patricia_iteration_state_ mowgli_patricia_iteration_state_t; + +/* + * this is a convenience macro for inlining iteration of dictionaries. + */ +#define MOWGLI_PATRICIA_FOREACH(element, state, dict) for (mowgli_patricia_foreach_start((dict), (state)); (element = mowgli_patricia_foreach_cur((dict), (state))); mowgli_patricia_foreach_next((dict), (state))) + +/* + * mowgli_patricia_create() creates a new patricia tree of the defined resolution. + * compare_cb is the canonizing function. + */ + +/* defined if this version of Mowgli allows canonize_cb to be NULL */ +#define MOWGLI_PATRICIA_ALLOWS_NULL_CANONIZE + +extern mowgli_patricia_t *mowgli_patricia_create(void (*canonize_cb)(char *key)); + +/* + * mowgli_patricia_destroy() destroys all entries in a dtree, and also optionally calls + * a defined callback function to destroy any data attached to it. + */ +extern void mowgli_patricia_destroy(mowgli_patricia_t *dtree, + void (*destroy_cb)(const char *key, void *data, void *privdata), + void *privdata); + +/* + * mowgli_patricia_foreach() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * To shortcircuit iteration, return non-zero from the callback function. + */ +extern void mowgli_patricia_foreach(mowgli_patricia_t *dtree, + int (*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata); + +/* + * mowgli_patricia_search() iterates all entries in a dtree, and also optionally calls + * a defined callback function to use any data attached to it. + * + * When the object is found, a non-NULL is returned from the callback, which results + * in that object being returned to the user. + */ +extern void *mowgli_patricia_search(mowgli_patricia_t *dtree, + void *(*foreach_cb)(const char *key, void *data, void *privdata), + void *privdata); + +/* + * mowgli_patricia_foreach_start() begins an iteration over all items + * keeping state in the given struct. If there is only one iteration + * in progress at a time, it is permitted to remove the current element + * of the iteration (but not any other element). + */ +extern void mowgli_patricia_foreach_start(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state); + +/* + * mowgli_patricia_foreach_cur() returns the current element of the iteration, + * or NULL if there are no more elements. + */ +extern void *mowgli_patricia_foreach_cur(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state); + +/* + * mowgli_patricia_foreach_next() moves to the next element. + */ +extern void mowgli_patricia_foreach_next(mowgli_patricia_t *dtree, + mowgli_patricia_iteration_state_t *state); + +/* + * mowgli_patricia_add() adds a key->value entry to the patricia tree. + */ +extern mowgli_boolean_t mowgli_patricia_add(mowgli_patricia_t *dtree, const char *key, void *data); + +/* + * mowgli_patricia_find() returns data from a dtree for key 'key'. + */ +extern void *mowgli_patricia_retrieve(mowgli_patricia_t *dtree, const char *key); + +/* + * mowgli_patricia_delete() deletes a key->value entry from the patricia tree. + */ +extern void *mowgli_patricia_delete(mowgli_patricia_t *dtree, const char *key); + +/* Low-level functions */ +mowgli_patricia_elem_t *mowgli_patricia_elem_add(mowgli_patricia_t *dtree, const char *key, void *data); +mowgli_patricia_elem_t *mowgli_patricia_elem_find(mowgli_patricia_t *dtree, const char *key); +void mowgli_patricia_elem_delete(mowgli_patricia_t *dtree, mowgli_patricia_elem_t *elem); +const char *mowgli_patricia_elem_get_key(mowgli_patricia_elem_t *elem); +void mowgli_patricia_elem_set_data(mowgli_patricia_elem_t *elem, void *data); +void *mowgli_patricia_elem_get_data(mowgli_patricia_elem_t *elem); + +unsigned int mowgli_patricia_size(mowgli_patricia_t *dict); +void mowgli_patricia_stats(mowgli_patricia_t *dict, void (*cb)(const char *line, void *privdata), void *privdata); + +#endif diff --git a/src/libmowgli/mowgli_queue.c b/src/libmowgli/mowgli_queue.c new file mode 100644 index 0000000..f27ff50 --- /dev/null +++ b/src/libmowgli/mowgli_queue.c @@ -0,0 +1,209 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_queue.c: Double-ended queues, also known as deque. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *mowgli_queue_heap = NULL; + +void +mowgli_queue_init(void) +{ + mowgli_queue_heap = mowgli_heap_create(sizeof(mowgli_queue_t), 256, BH_NOW); + + if (mowgli_queue_heap == NULL) + mowgli_log("mowgli_queue_heap was not created, expect problems."); +} + +mowgli_queue_t * +mowgli_queue_shift(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *out = mowgli_heap_alloc(mowgli_queue_heap); + + out->next = head; + out->data = data; + + if (head != NULL) + { + out->prev = head->prev; + + if (out->prev != NULL) + out->prev->next = out; + + head->prev = out; + } + + return out; +} + +mowgli_queue_t * +mowgli_queue_push(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *out = mowgli_heap_alloc(mowgli_queue_heap); + + out->prev = head; + out->data = data; + + if (head != NULL) + head->next = out; + + return out; +} + +mowgli_queue_t * +mowgli_queue_remove(mowgli_queue_t *head) +{ + mowgli_queue_t *out; + + if (head->prev != NULL) + head->prev->next = head->next; + + if (head->next != NULL) + head->next->prev = head->prev; + + out = head->prev != NULL ? head->prev : head->next; + + mowgli_heap_free(mowgli_queue_heap, head); + + return out; +} + +mowgli_queue_t * +mowgli_queue_find(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *n; + + for (n = head; n != NULL; n = n->next) + if (n->data == data) + return n; + + return NULL; +} + +mowgli_queue_t * +mowgli_queue_remove_data(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *n = mowgli_queue_find(head, data); + + if (n != NULL) + return mowgli_queue_remove(n); + + return NULL; +} + +void +mowgli_queue_destroy(mowgli_queue_t *head) +{ + mowgli_queue_t *n, *n2; + + for (n = head, n2 = n ? n->next : NULL; n != NULL; n = n2, n2 = n ? n->next : NULL) + mowgli_queue_remove(n); +} + +mowgli_queue_t * +mowgli_queue_skip(mowgli_queue_t *head, int nodes) +{ + mowgli_queue_t *n; + int iter; + + for (iter = 0, n = head; n != NULL && iter < nodes; n = n->next, iter++); + + return n; +} + +mowgli_queue_t * +mowgli_queue_rewind(mowgli_queue_t *head, int nodes) +{ + mowgli_queue_t *n; + int iter; + + for (iter = 0, n = head; n != NULL && iter < nodes; n = n->prev, iter++); + + return n; +} + +mowgli_queue_t * +mowgli_queue_head(mowgli_queue_t *n) +{ + mowgli_queue_t *tn; + + for (tn = n; tn != NULL && tn->prev != NULL; tn = tn->prev); + + return tn; +} + +mowgli_queue_t * +mowgli_queue_tail(mowgli_queue_t *n) +{ + mowgli_queue_t *tn; + + for (tn = n; tn != NULL && tn->next != NULL; tn = tn->next); + + return tn; +} + +void * +mowgli_queue_pop_head(mowgli_queue_t **n) +{ + mowgli_queue_t *tn; + void *out; + + return_val_if_fail(n != NULL, NULL); + return_val_if_fail(*n != NULL, NULL); + + tn = *n; + out = tn->data; + *n = tn->next; + + mowgli_queue_remove(tn); + + return out; +} + +void * +mowgli_queue_pop_tail(mowgli_queue_t **n) +{ + mowgli_queue_t *tn; + void *out; + + return_val_if_fail(n != NULL, NULL); + return_val_if_fail(*n != NULL, NULL); + + tn = *n; + out = tn->data; + *n = tn->prev; + + mowgli_queue_remove(tn); + + return out; +} + +int +mowgli_queue_length(mowgli_queue_t *head) +{ + int iter; + mowgli_queue_t *n; + + for (n = head, iter = 0; n != NULL; n = n->next, iter++); + + return iter; +} diff --git a/src/libmowgli/mowgli_queue.h b/src/libmowgli/mowgli_queue.h new file mode 100644 index 0000000..2d3b16b --- /dev/null +++ b/src/libmowgli/mowgli_queue.h @@ -0,0 +1,44 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_queue.h: Double-ended queues, also known as deque. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_QUEUE_H__ +#define __MOWGLI_QUEUE_H__ + +typedef mowgli_iterator_t mowgli_queue_t; + +extern void mowgli_queue_init(void); +extern mowgli_queue_t *mowgli_queue_push(mowgli_queue_t *head, void *data); +extern mowgli_queue_t *mowgli_queue_shift(mowgli_queue_t *head, void *data); +extern mowgli_queue_t *mowgli_queue_remove(mowgli_queue_t *head); +extern mowgli_queue_t *mowgli_queue_find(mowgli_queue_t *head, void *data); +extern mowgli_queue_t *mowgli_queue_remove_data(mowgli_queue_t *head, void *data); +extern void mowgli_queue_destroy(mowgli_queue_t *head); +extern mowgli_queue_t *mowgli_queue_skip(mowgli_queue_t *head, int amt); +extern mowgli_queue_t *mowgli_queue_rewind(mowgli_queue_t *head, int amt); +extern mowgli_queue_t *mowgli_queue_head(mowgli_queue_t *n); +extern mowgli_queue_t *mowgli_queue_tail(mowgli_queue_t *n); +extern void *mowgli_queue_pop_head(mowgli_queue_t **n); +extern void *mowgli_queue_pop_tail(mowgli_queue_t **n); +extern int mowgli_queue_length(mowgli_queue_t *head); + +#endif diff --git a/src/libmowgli/mowgli_random.c b/src/libmowgli/mowgli_random.c new file mode 100644 index 0000000..cd6d03e --- /dev/null +++ b/src/libmowgli/mowgli_random.c @@ -0,0 +1,143 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_random.c: Portable mersinne-twister based psuedo-random number generator. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Algorithm copyright (c) 1999-2007 Takuji Nishimura and Makoto Matsumoto + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +/* period parameters */ +#define N 624 +#define M 397 +#define MATRIX_A 0x9908b0dfUL /* constant vector a */ +#define UPPER_MASK 0x80000000UL /* most significant w-r bits */ +#define LOWER_MASK 0x7fffffffUL /* least significant r bits */ + +/* mowgli_random_t contains state data which is private */ +struct mowgli_random_ +{ + mowgli_object_t object; + unsigned int mt[N]; + size_t mti; +}; + +static mowgli_object_class_t klass; + +/* initialization */ +void mowgli_random_init(void) +{ + mowgli_object_class_init(&klass, "mowgli_random_t", NULL, FALSE); +} + +/* construction and destruction. */ +mowgli_random_t *mowgli_random_create(void) +{ + return mowgli_random_create_with_seed(time(NULL)); +} + +mowgli_random_t *mowgli_random_create_with_seed(unsigned int seed) +{ + mowgli_random_t *out = mowgli_alloc(sizeof(mowgli_random_t)); + mowgli_object_init(mowgli_object(out), NULL, &klass, NULL); + + mowgli_random_reseed(out, seed); + + return out; +} + +/* reset seed */ +void mowgli_random_reseed(mowgli_random_t *self, unsigned int seed) +{ + return_if_fail(self != NULL); + + self->mt[0] = seed & 0xffffffffUL; + for (self->mti = 1; self->mti < N; self->mti++) + { + self->mt[self->mti] = (1812433253UL * (self->mt[self->mti - 1] ^ (self->mt[self->mti - 1] >> 30)) + self->mti); + self->mt[self->mti] &= 0xffffffffUL; + } +} + +/* number retrieval */ +unsigned int mowgli_random_int(mowgli_random_t *self) +{ + unsigned int y; + static unsigned int mag01[2] = { 0x0UL, MATRIX_A }; + + return_val_if_fail(self != NULL, 0); + + if (self->mti >= N) + { + int t; + + for (t = 0; t < N - M; t++) + { + y = (self->mt[t] & UPPER_MASK) | (self->mt[t + 1] & LOWER_MASK); + self->mt[t] = self->mt[t + M] ^ (y >> 1) ^ mag01[y & 0x1U]; + } + + for (; t < N - 1; t++) + { + y = (self->mt[t] & UPPER_MASK) | (self->mt[t + 1] & LOWER_MASK); + self->mt[t] = self->mt[t + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1U]; + } + + y = (self->mt[N - 1] & UPPER_MASK) | (self->mt[0] & LOWER_MASK); + self->mt[N - 1] = self->mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1U]; + self->mti = 0; + } + + y = self->mt[self->mti++]; + + /* tempering */ + y ^= (y >> 11); + y ^= (y >> 7) & 0x9d2c5680U; + y ^= (y >> 15) & 0xefc60000U; + y ^= (y >> 18); + + return y; +} + +int mowgli_random_int_ranged(mowgli_random_t *self, int begin, int end) +{ + int dist = end - begin; + unsigned int max, ret; + + if (dist <= 0x80000000U) + { + unsigned int remain = (0x80000000U % dist) * 2; + + if (remain >= dist) + remain -= dist; + + max = 0xFFFFFFFFU - remain; + } else + max = dist - 1; + + do + { + ret = mowgli_random_int(self); + } while (ret > max); + + ret %= dist; + + return begin + ret; +} diff --git a/src/libmowgli/mowgli_random.h b/src/libmowgli/mowgli_random.h new file mode 100644 index 0000000..6fb0e61 --- /dev/null +++ b/src/libmowgli/mowgli_random.h @@ -0,0 +1,45 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_random.h: Portable mersinne-twister based psuedo-random number generator. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_RANDOM_H__ +#define __MOWGLI_RANDOM_H__ + +/* mowgli_random_t contains state data which is private */ +struct mowgli_random_; +typedef struct mowgli_random_ mowgli_random_t; + +/* object class initialization. */ +extern void mowgli_random_init(void); + +/* construction and destruction. */ +extern mowgli_random_t *mowgli_random_create(void); +extern mowgli_random_t *mowgli_random_create_with_seed(unsigned int seed); + +/* reset seed */ +extern void mowgli_random_reseed(mowgli_random_t *self, unsigned int seed); + +/* number retrieval */ +extern unsigned int mowgli_random_int(mowgli_random_t *self); +extern int mowgli_random_int_ranged(mowgli_random_t *self, int begin, int end); + +#endif diff --git a/src/libmowgli/mowgli_signal.c b/src/libmowgli/mowgli_signal.c new file mode 100644 index 0000000..3fdd708 --- /dev/null +++ b/src/libmowgli/mowgli_signal.c @@ -0,0 +1,65 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_signal.c: Safe signal handling. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _WIN32 + +#include "mowgli.h" + +static mowgli_signal_handler_t +mowgli_signal_install_handler_full(int signum, mowgli_signal_handler_t handler, + int *sigtoblock, size_t sigtoblocksize) +{ + struct sigaction action, old_action; + size_t i; + + action.sa_handler = handler; + action.sa_flags = SA_RESTART; + + sigemptyset(&action.sa_mask); + + for (i = 0; i < sigtoblocksize; i++) + sigaddset(&action.sa_mask, sigtoblock[i]); + + if (sigaction(signum, &action, &old_action) == -1) + { + mowgli_log("Failed to install signal handler for signal %d", signum); + return NULL; + } + + return old_action.sa_handler; +} + +/* + * A version of signal(2) that works more reliably across different + * platforms. + * + * It restarts interrupted system calls, does not reset the handler, + * and blocks the same signal from within the handler. + */ +mowgli_signal_handler_t +mowgli_signal_install_handler(int signum, mowgli_signal_handler_t handler) +{ + return mowgli_signal_install_handler_full(signum, handler, NULL, 0); +} + +#endif diff --git a/src/libmowgli/mowgli_signal.h b/src/libmowgli/mowgli_signal.h new file mode 100644 index 0000000..cc3db11 --- /dev/null +++ b/src/libmowgli/mowgli_signal.h @@ -0,0 +1,31 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_signal.c: Safe signal handling. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_SIGNAL_H__ +#define __MOWGLI_SIGNAL_H__ + +typedef void (*mowgli_signal_handler_t) (int); + +extern mowgli_signal_handler_t mowgli_signal_install_handler(int signum, mowgli_signal_handler_t handler); + +#endif diff --git a/src/libmowgli/mowgli_spinlock.c b/src/libmowgli/mowgli_spinlock.c new file mode 100644 index 0000000..47c1166 --- /dev/null +++ b/src/libmowgli/mowgli_spinlock.c @@ -0,0 +1,105 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_spinlock.c: Spinlocks. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +mowgli_spinlock_t *mowgli_spinlock_create(void) +{ + mowgli_spinlock_t *out = mowgli_alloc(sizeof(mowgli_spinlock_t)); + + return out; +} + +void mowgli_spinlock_lock(mowgli_spinlock_t *self, void *r, void *w) +{ + return_if_fail(self != NULL); + + if (r) + mowgli_spinlock_wait(self, MOWGLI_SPINLOCK_READ); + + if (w) + mowgli_spinlock_wait(self, MOWGLI_SPINLOCK_WRITE); + + if (r && (self->read_owner == NULL || self->read_owner == r)) + self->read_owner = r; + + if (w && (self->write_owner == NULL || self->write_owner == w)) + self->write_owner = w; +} + +void mowgli_spinlock_unlock(mowgli_spinlock_t *self, void *r, void *w) +{ + return_if_fail(self != NULL); + + if (r && self->read_owner == r) + self->read_owner = NULL; + + if (w && self->write_owner == w) + self->write_owner = NULL; +} + +void mowgli_spinlock_wait(mowgli_spinlock_t *self, mowgli_spinlock_lock_param_t param) +{ + return_if_fail(self != NULL) + + if (param == MOWGLI_SPINLOCK_READ) + while (self->read_owner != NULL) + usleep(1000); /* XXX: we'll want a more threadsafe function eventually. */ + + if (param == MOWGLI_SPINLOCK_WRITE) + while (self->write_owner != NULL) + usleep(1000); + + if (param == MOWGLI_SPINLOCK_READWRITE) + while (self->write_owner != NULL || self->read_owner != NULL) + usleep(1000); +} + +void mowgli_spinlock_timed_wait(mowgli_spinlock_t *self, mowgli_spinlock_lock_param_t param, struct timeval *tv) +{ + struct timeval iter = {0}; + + return_if_fail(self != NULL) + return_if_fail(tv != NULL) + + if (param == MOWGLI_SPINLOCK_READ) + while (self->read_owner != NULL && iter.tv_sec < tv->tv_sec && iter.tv_usec < tv->tv_usec) + { + gettimeofday(&iter, NULL); + usleep(1000); /* XXX: we'll want a more threadsafe function eventually. */ + } + + if (param == MOWGLI_SPINLOCK_WRITE) + while (self->write_owner != NULL && iter.tv_sec < tv->tv_sec && iter.tv_usec < tv->tv_usec) + { + gettimeofday(&iter, NULL); + usleep(1000); + } + + if (param == MOWGLI_SPINLOCK_READWRITE) + while ((self->write_owner != NULL || self->read_owner != NULL) && iter.tv_sec < tv->tv_sec && iter.tv_usec < tv->tv_usec) + { + gettimeofday(&iter, NULL); + usleep(1000); + } +} diff --git a/src/libmowgli/mowgli_spinlock.h b/src/libmowgli/mowgli_spinlock.h new file mode 100644 index 0000000..6742e13 --- /dev/null +++ b/src/libmowgli/mowgli_spinlock.h @@ -0,0 +1,44 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_spinlock.h: Spinlocks. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_SPINLOCK_H__ +#define __MOWGLI_SPINLOCK_H__ + +typedef struct { + void *read_owner; /* opaque data representing a spinlock's owner */ + void *write_owner; /* opaque data representing a spinlock's owner */ +} mowgli_spinlock_t; + +typedef enum { + MOWGLI_SPINLOCK_READ, + MOWGLI_SPINLOCK_WRITE, + MOWGLI_SPINLOCK_READWRITE +} mowgli_spinlock_lock_param_t; + +extern mowgli_spinlock_t *mowgli_spinlock_create(void); +extern void mowgli_spinlock_lock(mowgli_spinlock_t *self, void *r, void *w); +extern void mowgli_spinlock_unlock(mowgli_spinlock_t *self, void *r, void *w); +extern void mowgli_spinlock_wait(mowgli_spinlock_t *self, mowgli_spinlock_lock_param_t param); +extern void mowgli_spinlock_timed_wait(mowgli_spinlock_t *self, mowgli_spinlock_lock_param_t param, struct timeval *tv); + +#endif diff --git a/src/libmowgli/mowgli_stdinc.h b/src/libmowgli/mowgli_stdinc.h new file mode 100644 index 0000000..ae64a22 --- /dev/null +++ b/src/libmowgli/mowgli_stdinc.h @@ -0,0 +1,96 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_stdinc.h: Pulls in the base system includes for libmowgli. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_STDINC_H__ +#define __MOWGLI_STDINC_H__ + +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <signal.h> +#include <time.h> +#include <errno.h> +#include <setjmp.h> +#include <sys/stat.h> +#include <ctype.h> + +/* socket stuff */ +#ifndef _WIN32 +# include <netdb.h> +# include <netinet/in.h> +# include <unistd.h> +# include <grp.h> +# include <sys/time.h> +# include <sys/wait.h> +# include <sys/resource.h> +# include <sys/socket.h> +# include <fcntl.h> +# include <arpa/inet.h> +# include <libgen.h> +# include <dirent.h> +#else +# include <windows.h> +# include <winsock.h> +# include <sys/timeb.h> +# include <direct.h> +# include <io.h> +# include <fcntl.h> +#endif + +#include <sys/types.h> + +#ifdef _MSC_VER +# pragma warning (disable: 4996) +#endif + +#ifdef FALSE +# undef FALSE +#endif + +#ifdef TRUE +# undef TRUE +#endif + +typedef enum { FALSE, TRUE } mowgli_boolean_t; + +/* Macros for min/max. */ +#ifndef MIN +# define MIN(a,b) (((a)<(b))?(a):(b)) +#endif + +#ifndef MAX +# define MAX(a,b) (((a)>(b))?(a):(b)) +#endif + +#if defined(__GNUC__) || defined(_INTEL_COMPILER) +#define MOWGLI_DEPRECATED \ + __attribute__((deprecated)) +#elif defined(_MSC_VER) +#define MOWGLI_DEPRECATED \ + __declspec(deprecated) +#else +#define MOWGLI_DEPRECATED +#endif + +#endif diff --git a/src/libmowgli/mowgli_string.c b/src/libmowgli/mowgli_string.c new file mode 100644 index 0000000..9c9d5c2 --- /dev/null +++ b/src/libmowgli/mowgli_string.c @@ -0,0 +1,121 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_string.c: Immutable string buffers with cheap manipulation. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Pippijn van Steenhoven <pippijn -at- one09.net> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +mowgli_string_t *mowgli_string_create(void) +{ + mowgli_string_t *self = mowgli_alloc(sizeof(mowgli_string_t)); + + self->size = 64; + self->pos = 0; + self->str = mowgli_alloc(self->size); + + self->append = &mowgli_string_append; + self->append_char = &mowgli_string_append_char; + self->reset = &mowgli_string_reset; + self->destroy = &mowgli_string_destroy; + + return self; +} + +void mowgli_string_reset(mowgli_string_t *self) +{ + return_if_fail(self != NULL); + + self->str[0] = self->pos = 0; +} + +void mowgli_string_destroy(mowgli_string_t *self) +{ + return_if_fail(self != NULL); + + mowgli_free(self->str); + mowgli_free(self); +} + +void mowgli_string_append(mowgli_string_t *self, const char *src, size_t n) +{ + if (self->size - self->pos <= n) + { + char *new; + + self->size = MAX(self->size * 2, self->pos + n + 8); + new = realloc(self->str, self->size); + self->str = new; + } + + memcpy(self->str + self->pos, src, n); + self->pos += n; + self->str[self->pos] = 0; +} + +void mowgli_string_append_char(mowgli_string_t *self, const char c) +{ + if (self->size - self->pos <= 1) + { + char *new; + + self->size = MAX(self->size * 2, self->pos + 9); + new = realloc(self->str, self->size); + self->str = new; + } + + self->str[self->pos++] = c; + self->str[self->pos] = 0; +} + +/* These functions are taken from Linux. */ +size_t mowgli_strlcat(char *dest, const char *src, size_t count) +{ + size_t dsize = strlen(dest); + size_t len = strlen(src); + size_t res = dsize + len; + + dest += dsize; + count -= dsize; + + if (len >= count) + len = count - 1; + + memcpy(dest, src, len); + + dest[len] = 0; + + return res; +} + +size_t mowgli_strlcpy(char *dest, const char *src, size_t size) +{ + size_t ret = strlen(src); + + if (size) + { + size_t len = (ret >= size) ? size - 1 : ret; + memcpy(dest, src, len); + dest[len] = '\0'; + } + + return ret; +} diff --git a/src/libmowgli/mowgli_string.h b/src/libmowgli/mowgli_string.h new file mode 100644 index 0000000..b815451 --- /dev/null +++ b/src/libmowgli/mowgli_string.h @@ -0,0 +1,48 @@ +/* + * libmowgli: A collection of useful routines for programming. + * mowgli_string.h: Immutable string buffers with cheap manipulation. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * Copyright (c) 2007 Pippijn van Steenhoven <pippijn -at- one09.net> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __MOWGLI_STRING_H__ +#define __MOWGLI_STRING_H__ + +typedef struct mowgli_string_ { + char *str; + size_t pos; + size_t size; + + void (*reset)(struct mowgli_string_ *self); + void (*append)(struct mowgli_string_ *self, const char *src, size_t n); + void (*append_char)(struct mowgli_string_ *self, const char c); + void (*destroy)(struct mowgli_string_ *self); +} mowgli_string_t; + +extern mowgli_string_t *mowgli_string_create(void); +extern void mowgli_string_reset(mowgli_string_t *self); +extern void mowgli_string_destroy(mowgli_string_t *self); +extern void mowgli_string_append(mowgli_string_t *self, const char *src, size_t n); +extern void mowgli_string_append_char(mowgli_string_t *self, const char c); + +extern size_t mowgli_strlcat(char *dest, const char *src, size_t count); +extern size_t mowgli_strlcpy(char *dest, const char *src, size_t count); + +#endif diff --git a/src/libmowgli/win32_support.c b/src/libmowgli/win32_support.c new file mode 100644 index 0000000..da6344f --- /dev/null +++ b/src/libmowgli/win32_support.c @@ -0,0 +1,64 @@ +/* + * libmowgli: A collection of useful routines for programming. + * win32_support.c: Support functions and values for Win32 platform. + * + * Copyright (c) 2009 SystemInPlace, Inc. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +#ifdef _MSC_VER +# define EPOCH_TIME_IN_MICROSECS 11644473600000000Ui64 +#else +# define EPOCH_TIME_IN_MICROSECS 11644473600000000ULL +#endif + +int gettimeofday(struct timeval *tv, struct timezone *tz) +{ + FILETIME ft; + ULARGE_INTEGER tmpres = { 0 }; + static mowgli_boolean_t tz_init_done = FALSE; + + if (tv != NULL) + { + GetSystemTimeAsFileTime(&ft); + + tmpres.u.HighPart = ft.dwHighDateTime; + tmpres.u.LowPart = ft.dwLowDateTime; + + tmpres.QuadPart /= 10; + tmpres.QuadPart -= EPOCH_TIME_IN_MICROSECS; + tv->tv_sec = (long) (tmpres.QuadPart / 1000000UL); + tv->tv_usec = (long) (tmpres.QuadPart % 1000000UL); + } + + if (tz != NULL) + { + if (!tz_init_done) + { + _tzset(); + tz_init_done = TRUE; + } + + tz->tz_minuteswest = _timezone / 60; + tz->tz_dsttime = _daylight; + } + + return 0; +} diff --git a/src/libmowgli/win32_support.h b/src/libmowgli/win32_support.h new file mode 100644 index 0000000..c87c643 --- /dev/null +++ b/src/libmowgli/win32_support.h @@ -0,0 +1,47 @@ +/* + * libmowgli: A collection of useful routines for programming. + * win32_support.h: Support functions and values for Win32 platform. + * + * Copyright (c) 2009 SystemInPlace, Inc. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __LIBMOWGLI_SRC_LIBMOWGLI_WIN32_SUPPORT_H__GUARD +#define __LIBMOWGLI_SRC_LIBMOWGLI_WIN32_SUPPORT_H__GUARD + +#ifdef _WIN32 + +#include <winsock.h> // just for struct timeval declaration +#include <time.h> + +#define strcasecmp _stricmp +#define strdup _strdup +#define usleep(_usecs) Sleep((_usecs)/1000L) +#define snprintf _snprintf +#define vsnprintf _vsnprintf + +struct timezone { + int tz_minuteswest; + int tz_dsttime; +}; + +extern int gettimeofday(struct timeval *tv, struct timezone *tz); + +#endif + +#endif |