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/dsqueue.c | 283 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 283 insertions(+) create mode 100644 deque/src/dsqueue.c (limited to 'deque/src/dsqueue.c') diff --git a/deque/src/dsqueue.c b/deque/src/dsqueue.c new file mode 100644 index 0000000..e328af0 --- /dev/null +++ b/deque/src/dsqueue.c @@ -0,0 +1,283 @@ +/* + * File: dsqueue.c + * 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 "dsqueue.h" +#include "squeue.h" + +/*---------------------------------------------------------------------- + * Creation / Deletion + *----------------------------------------------------------------------*/ +dsqueue_ptr dsqueue_new(unsigned blocksize) { + dsqueue_ptr dsq = (dsqueue_ptr)malloc(sizeof(dsqueue_t)); + if (!dsq) { + errno = ENOMEM; + return NULL; + } + dsq->blocksize = blocksize; + dsq->trash = NULL; + dsq->head = NULL; + dsq->tail = NULL; + return dsq; +} + +void dsqueue_destroy(dsqueue_ptr dsq) { + dsqueue_block_t *dsqe, *dsqe_next; + dsqueue_clear(dsq); + for (dsqe = dsq->head; dsqe != NULL; dsqe = dsqe_next) { + squeue_destroy(dsqe->sq); + dsqe_next = dsqe->next; + free(dsqe); + } + for (dsqe = dsq->trash; dsqe != NULL; dsqe = dsqe_next) { + squeue_destroy(dsqe->sq); + dsqe_next = dsqe->next; + free(dsqe); + } + free(dsq); +} + +/*---------------------------------------------------------------------- + * Predicates + *----------------------------------------------------------------------*/ +char dsqueue_is_empty(dsqueue_ptr dsq) { + while (dsq->head && squeue_empty(dsq->head->sq)) { + dsqueue_block_t *dsqe = dsqueue_block_shift(dsq); + dsqe->next = dsq->trash; + if (dsq->trash) dsq->trash->prev = dsqe; + dsq->trash = dsqe; + } + return dsq->head ? 0 : 1; +} + +/*---------------------------------------------------------------------- + * Manipulation + *----------------------------------------------------------------------*/ + +void dsqueue_clear(dsqueue_ptr dsq) { + if (dsq->head && dsq->tail) { + dsq->tail->next = dsq->trash; + if (dsq->trash) dsq->trash->prev = dsq->tail; + dsq->trash = dsq->head; + } + dsq->head = NULL; + dsq->tail = NULL; +} + +dsqueue_block_t *dsqueue_prepend(dsqueue_ptr dsq, void *data) { + dsqueue_block_t *dsqe = dsq->head; + while (!dsqe || squeue_full(dsqe->sq)) { + dsqe = dsqueue_block_new(dsq); + if (!dsqe) { + errno = ENOMEM; + return NULL; + } + dsqueue_block_prepend(dsq,dsqe); + } + squeue_prepend(dsqe->sq,data); + return dsqe; +} + +dsqueue_block_t *dsqueue_append(dsqueue_ptr dsq, void *data) { + dsqueue_block_t *dsqe = dsq->tail; + while (!dsqe || squeue_full(dsqe->sq)) { + dsqe = dsqueue_block_new(dsq); + if (!dsqe) { + errno = ENOMEM; + return NULL; + } + dsqueue_block_append(dsq,dsqe); + } + squeue_append(dsqe->sq,data); + return dsqe; +} + + + +/*---------------------------------------------------------------------- + * Access + *----------------------------------------------------------------------*/ + +void *dsqueue_shift(dsqueue_ptr dsq) { + dsqueue_trim_front(dsq); + return dsq->head ? squeue_shift(dsq->head->sq) : NULL; +} + +void *dsqueue_pop(dsqueue_ptr dsq) { + dsqueue_trim_back(dsq); + return dsq->tail ? squeue_pop(dsq->tail->sq) : NULL; +} + + +/*---------------------------------------------------------------------- + * Iterators + *----------------------------------------------------------------------*/ + +// Returns an iterator for the first datum in the queue, +// or NULL if queue is empty. +dsqueue_iter_t dsqueue_iter_first(dsqueue_t *dsq) { + dsqueue_iter_t dsqi = {NULL,NULL}; + dsqueue_trim_front(dsq); + if (dsq->head) { + dsqi.block = dsq->head; + dsqi.sqi = squeue_iter_first(dsqi.block->sq); + } + return dsqi; +} + +/// Returns an iterator for the final datum in the queue, +/// or NULL if queue is empty. +dsqueue_iter_t dsqueue_iter_last(dsqueue_t *dsq) { + dsqueue_iter_t dsqi = {NULL,NULL}; + dsqueue_trim_back(dsq); + if (dsq->tail) { + dsqi.block = dsq->tail; + dsqi.sqi = squeue_iter_last(dsqi.block->sq); + } + return dsqi; +} + + +/// Returns an iterator for the next datum in the queue, or +/// NULL if already at end-of-queue. +dsqueue_iter_t dsqueue_iter_next(dsqueue_t *dsq, dsqueue_iter_t dsqi) { + while (dsqi.block) { + dsqi.sqi = squeue_iter_next(dsqi.block->sq, dsqi.sqi); + if (dsqi.sqi) break; + dsqi.block = dsqi.block->next; + } + return dsqi; +} + +/// Returns an iterator for the previous datum in the queue, +/// or NULL if already at beginning-of-queue. +dsqueue_iter_t dsqueue_iter_prev(dsqueue_t *dsq, dsqueue_iter_t dsqi) { + while (dsqi.block) { + dsqi.sqi = squeue_iter_prev(dsqi.block->sq, dsqi.sqi); + if (dsqi.sqi) break; + dsqi.block = dsqi.block->prev; + } + return dsqi; +} + +/// Returns a true value if p is a valid iterator value, false otherwise. +char dsqueue_iter_valid(dsqueue_t *dsq, dsqueue_iter_t dsqi) { + return (dsqi.block && dsqi.sqi && + squeue_iter_valid(dsqi.block->sq, dsqi.sqi)); +} + +/// Get the datum from an iterator. +void *dsqueue_iter_data(dsqueue_iter_t dsqi) { + return (dsqi.block && dsqi.sqi ? squeue_iter_data(dsqi.sqi) : NULL); +} + + + +/*---------------------------------------------------------------------- + * Utilities + *----------------------------------------------------------------------*/ + +// Allocate and return a new block. +dsqueue_block_t *dsqueue_block_new(dsqueue_t *dsq) { + // -- first try trashbin + dsqueue_block_t *dsqe = dsq->trash; + if (dsqe) { + dsq->trash = dsqe->next; + if (dsq->trash) dsq->trash->prev = NULL; + } else { + dsqe = (dsqueue_block_t *)malloc(sizeof(dsqueue_block_t)); + if (!dsqe) { + errno = ENOMEM; + return NULL; + } + dsqe->sq = squeue_new(dsq->blocksize); + if (!dsqe->sq) { + errno = ENOMEM; + free(dsqe); + return NULL; + } + } + // -- initialize + dsqe->prev = NULL; + dsqe->next = NULL; + return dsqe; +} + + +#ifdef DSQUEUE_DEBUG + +dsqueue_block_t *dsqueue_block_prepend(dsqueue_t *dsq, dsqueue_block_t *e) { + if (!e) return NULL; + else if (dsq->head) dsq->head->prev = e; + else dsq->tail = e; + e->next = dsq->head; + dsq->head = e; + return dsq->head; +} + +dsqueue_block_t *dsqueue_block_append(dsqueue_t *dsq, dsqueue_block_t *e) { + if (!e) return NULL; + else if (dsq->tail) dsq->tail->next = e; + else dsq->head = e; + e->prev = dsq->tail; + dsq->tail = e; + return dsq->tail; +} + +#endif + + +dsqueue_block_t *dsqueue_block_shift(dsqueue_t *dsq) { + dsqueue_block_t *dsqe = dsq->head; + if (!dsqe) return dsqe; + dsq->head = dsqe->next; + if (dsq->head) { + dsq->head->prev = NULL; + } else { + dsq->tail = NULL; + } + dsqe->next = NULL; + return dsqe; +} +dsqueue_block_t *dsqueue_block_pop(dsqueue_t *dsq) { + dsqueue_block_t *dsqe = dsq->tail; + if (!dsqe) return dsqe; + dsq->tail = dsqe->prev; + if (dsq->tail) { + dsq->tail->next = NULL; + } else { + dsq->head = NULL; + } + dsqe->prev = NULL; + return dsqe; +} + + +void dsqueue_trim_front(dsqueue_t *dsq) { + while (dsq->head && squeue_empty(dsq->head->sq)) { + dsqueue_block_t *dsqe = dsqueue_block_shift(dsq); + if (dsq->trash) dsq->trash->prev = dsqe; + dsqe->next = dsq->trash; + dsq->trash = dsqe; + } +} + +void dsqueue_trim_back(dsqueue_t *dsq) { + while (dsq->tail && squeue_empty(dsq->tail->sq)) { + dsqueue_block_t *dsqe = dsqueue_block_pop(dsq); + if (dsq->trash) dsq->trash->prev = dsqe; + dsqe->next = dsq->trash; + dsq->trash = dsqe; + } +} -- cgit v1.2.1