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.h | 171 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 171 insertions(+) create mode 100644 deque/src/dsqueue.h (limited to 'deque/src/dsqueue.h') diff --git a/deque/src/dsqueue.h b/deque/src/dsqueue.h new file mode 100644 index 0000000..b0fae20 --- /dev/null +++ b/deque/src/dsqueue.h @@ -0,0 +1,171 @@ +/* -*- Mode: C -*- */ +/* + * File: dsqueue.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. + * + */ + +#ifndef DSQUEUE_H +#define DSQUEUE_H + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include "squeue.h" + + +/** + * \file dsqueue.h + * \brief Headers for linked-list queues. + */ + +/// Queue block structure. +typedef struct dsqueue_block { + squeue_t *sq; + struct dsqueue_block *next; + struct dsqueue_block *prev; +} dsqueue_block_t, *dsqueue_block_ptr; + +/// Queue structure. +typedef struct { + dsqueue_block_t *head; // head of the queue + dsqueue_block_t *tail; // tail of the queue + dsqueue_block_t *trash; // recycling bin + unsigned blocksize; +} dsqueue_t, *dsqueue_ptr; + + +/// Queue iterator structure +typedef struct { + dsqueue_block_t *block; + squeue_iter_t sqi; +} dsqueue_iter_t; + +/*---------------------------------------------------------------------- + * Creation / Deletion + *----------------------------------------------------------------------*/ + +/// Create and initialize a new dsqueue. Returns NULL on failure. +extern dsqueue_ptr dsqueue_new(unsigned blocksize); + +/// Destroy an dsqueue -- implicitly calls clear(). +extern void dsqueue_destroy(dsqueue_ptr dsq); + +/*---------------------------------------------------------------------- + * Predicates + *----------------------------------------------------------------------*/ + +/// True if the dsqueue has no blocks. +extern char dsqueue_is_empty(dsqueue_ptr dsq); + +#define dsqueue_empty(dsq) (!dsq->head || dsqueue_is_empty(dsq)) + +/*---------------------------------------------------------------------- + * Manipulation + *----------------------------------------------------------------------*/ + +/// Clear all blocks from an dsqueue. 'data' members will not be freed. +extern void dsqueue_clear(dsqueue_ptr dsq); + +/// Prepend data to the front of an dsqueue. +extern dsqueue_block_t *dsqueue_prepend(dsqueue_ptr dsq, void *data); + +/// Append data to the end of an dsqueue. +extern dsqueue_block_t *dsqueue_append(dsqueue_ptr dsq, void *data); + +/*---------------------------------------------------------------------- + * Access + *----------------------------------------------------------------------*/ + +/// Shift an block off the front of an dsqueue. +/// Returns a pointer to the block's data, or NULL if dsqueue is empty. +extern void *dsqueue_shift(dsqueue_ptr dsq); + +/// Pop an block off the back of an dsqueue. +/// Returns a pointer to the block's data, or NULL if dsqueue is empty. +extern void *dsqueue_pop(dsqueue_ptr dsq); + + +/*---------------------------------------------------------------------- + * Iteration + *----------------------------------------------------------------------*/ +/// Returns an iterator for the first datum in the queue, +/// or NULL if queue is empty. +extern dsqueue_iter_t dsqueue_iter_first(dsqueue_t *dsq); + +/// Returns an iterator for the next datum in the queue, or +/// NULL if already at end-of-queue. +extern dsqueue_iter_t dsqueue_iter_next(dsqueue_t *dsq, dsqueue_iter_t dsqi); + +/// Returns an iterator for the final datum in the queue, +/// or NULL if queue is empty. +extern dsqueue_iter_t dsqueue_iter_last(dsqueue_t *dsq); + +/// Returns an iterator for the previous datum in the queue, +/// or NULL if already at beginning-of-queue. +extern dsqueue_iter_t dsqueue_iter_prev(dsqueue_t *dsq, dsqueue_iter_t dsqi); + +/// Returns a true value if p is a valid iterator value, false otherwise. +extern char dsqueue_iter_valid(dsqueue_t *dsq, dsqueue_iter_t dsqi); + +/// Get the datum from an iterator. +extern void *dsqueue_iter_data(dsqueue_iter_t dsqi); + +/*---------------------------------------------------------------------- + * Utilities + *----------------------------------------------------------------------*/ + +/// Allocate and return a new block (try trashbin first) +extern dsqueue_block_t *dsqueue_block_new(dsqueue_t *dsq); + +#ifdef DSQUEUE_DEBUG + +/// Prepend a block +extern dsqueue_block_t *dsqueue_block_prepend(dsqueue_t *dsq, dsqueue_block_t *e); + +/// Append a block +extern dsqueue_block_t *dsqueue_block_append(dsqueue_t *dsq, dsqueue_block_t *e); + +#else + +#define dsqueue_block_prepend(dsq,e) \ + if (e) { \ + if (dsq->head) dsq->head->prev = e; \ + else dsq->tail = e; \ + e->next = dsq->head; \ + dsq->head = e; \ + } + + +#define dsqueue_block_append(dsq,e) \ + if (e) { \ + if (dsq->tail) dsq->tail->next = e; \ + else dsq->head = e; \ + e->prev = dsq->tail; \ + dsq->tail = e; \ + } + +#endif + + +/// Shift a block from the front (trashing it) +extern dsqueue_block_t *dsqueue_block_shift(dsqueue_t *dsq); + +/// Pop a block from the end (trashing it) +extern dsqueue_block_t *dsqueue_block_pop(dsqueue_t *dsq); + +/// Trim empty blocks off the front of the queue. +extern void dsqueue_trim_front(dsqueue_t *dsq); + +/// Trim empty blocks off the back of the queue. +extern void dsqueue_trim_back(dsqueue_t *dsq); + +#endif /* DSQUEUE_H */ -- cgit v1.2.1