From 7071af9d6a6284b604aea2d75504603eb0214b65 Mon Sep 17 00:00:00 2001 From: Bryan Jurish Date: Thu, 2 Feb 2006 12:40:31 +0000 Subject: + initial CVS import svn path=/trunk/externals/moocow/; revision=4534 --- deque/src/squeue.c | 216 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 216 insertions(+) create mode 100644 deque/src/squeue.c (limited to 'deque/src/squeue.c') diff --git a/deque/src/squeue.c b/deque/src/squeue.c new file mode 100644 index 0000000..0c24c93 --- /dev/null +++ b/deque/src/squeue.c @@ -0,0 +1,216 @@ +/* + * + * File: squeue.h + * Author: Bryan Jurish + * + * Copyright (c) 2003 Bryan Jurish. All Rights Reserved. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + */ + +#include +#include +#include "squeue.h" + +/*---------------------------------------------------------------------- + * Creation / Deletion + *----------------------------------------------------------------------*/ +squeue_ptr squeue_new(unsigned int size) { + squeue_ptr sq = (squeue_ptr)malloc(sizeof(squeue_t)); + if (!sq || !size) { + errno = ENOMEM; + return NULL; + } + sq->data = (void **)malloc(size*sizeof(void *)); + if (!sq->data) { + errno = ENOMEM; + return NULL; + } +# ifdef SQUEUE_DEBUG + memset(sq->data,0,size*sizeof(void *)); +# endif + sq->size = size-1; + sq->head = NULL; + sq->tail = NULL; + return sq; +} + +void squeue_destroy(squeue_ptr sq) { + squeue_clear(sq); + free(sq->data); + free(sq); +} + +/*---------------------------------------------------------------------- + * Predicates + *----------------------------------------------------------------------*/ +#ifdef SQUEUE_DEBUG + +char squeue_empty(squeue_ptr sq) { + return (!sq->head); +} + +char squeue_full(squeue_ptr sq) { + return (sq->head && sq->head == squeue_next(sq,sq->tail)); +} + +#endif + + +/*---------------------------------------------------------------------- + * utilities + *----------------------------------------------------------------------*/ +#ifdef SQUEUE_DEBUG + +void **squeue_prev(squeue_t *sq, void **p) { + //return (p && p > sq->data ? p-1 : p+sq->size); + return (p && p > sq->data ? p-1 : sq->data+sq->size); +} + +void **squeue_next(squeue_t *sq, void **p) { + return (p && p < sq->data+sq->size ? p+1 : sq->data); +} + +#endif + +/*---------------------------------------------------------------------- + * Manipulation + *----------------------------------------------------------------------*/ + +#ifdef SQUEUE_DEBUG + +void squeue_clear(squeue_ptr sq) { + sq->head = NULL; + sq->tail = NULL; +# ifdef SQUEUE_DEBUG + memset(sq->data,0,sq->size*sizeof(void *)); +# endif +} + +#endif + +void **squeue_prepend(squeue_ptr sq, void *data) { + sq->head = squeue_prev(sq,sq->head); + if (!sq->tail) { + // -- empty-queue + sq->tail = sq->head; + } else if (sq->head == sq->tail) { + // -- xrun (full queue) + sq->head = squeue_next(sq,sq->head); + return NULL; + // alternative: push the overwritten older pointer along a notch + //sq->tail = squeue_prev(sq,sq->tail); + } + // -- set the data + *(sq->head) = data; + return sq->head; +} + +void **squeue_append(squeue_ptr sq, void *data) { + sq->tail = squeue_next(sq,sq->tail); + if (!sq->head) { + // -- empty-queue check + sq->head = sq->tail; + } else if (sq->tail == sq->head) { + // -- xrun (full queue) + sq->tail = squeue_prev(sq,sq->tail); + return NULL; + // alternative: push the overwritten older pointer along a notch + //sq->head = squeue_next(sq,sq->head); + } + // -- set the data + *(sq->tail) = data; + return sq->tail; +} + + +/*---------------------------------------------------------------------- + * Access + *----------------------------------------------------------------------*/ + +void *squeue_shift(squeue_ptr sq) { + if (squeue_empty(sq)) return NULL; + else { + void *data = *(sq->head); + // -- empty queue check + if (sq->head == sq->tail) { + sq->head = NULL; + sq->tail = NULL; + } else { + sq->head = squeue_next(sq, sq->head); + } + return data; + } +} + +void *squeue_pop(squeue_ptr sq) { + if (squeue_empty(sq)) return NULL; + else { + void *data = *(sq->tail); + if (sq->head == sq->tail) { + sq->head = NULL; + sq->tail = NULL; + } else { + sq->tail = squeue_prev(sq, sq->tail); + } + return data; + } +} + +#ifdef SQUEUE_DEBUG + +// Returns the first datum in the queue, or NULL if queue is empty. +void *squeue_peek_head(squeue_ptr sq) { + return sq->head ? *(sq->head) : NULL; +} + +// Returns the final datum in the queue, or NULL if queue is empty. +void *squeue_peek_tail(squeue_ptr sq) { + return sq->tail ? *(sq->tail) : NULL; +} + +#endif + +/*---------------------------------------------------------------------- + * Iteration + *----------------------------------------------------------------------*/ +#ifdef SQUEUE_DEBUG + +// Returns a pointer-pointer to the first datum in the queue, +// or NULL if queue is empty. +squeue_iter_t squeue_iter_first(squeue_t *sq) { return sq->head; } + +// Returns a pointer-pointer to the final datum in the queue, +// or NULL if queue is empty. +squeue_iter_t squeue_iter_last(squeue_t *sq) { return sq->tail; } + + + +// Returns a pointer to the next datum in the queue, or +// NULL if queue is empty. +squeue_iter_t squeue_iter_next(squeue_t *sq, squeue_iter_t p) { + return p == sq->tail ? NULL : squeue_next(sq,p); +} + +// Returns a pointer-pointer to the final datum in the queue, +// or NULL if queue is empty. +extern squeue_iter_t squeue_iter_prev(squeue_t *sq, squeue_iter_t p) { + return p == sq->head ? NULL : squeue_prev(sq,p); +} + + +// Returns a true value if p is a valid iterator value, false otherwise. +// Warning: this is not even as paranoid as it ought to be! +extern char squeue_iter_valid(squeue_t *sq, squeue_iter_t p) { + return (p && p >= sq->data && p <= sq->data+sq->size); +} + +/// Get the datum from an iterator. +void *squeue_iter_data(squeue_iter_t p) { return *p; } + + +#endif -- cgit v1.2.1