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/Makefile.am | 137 +++++++++++++++++++++ deque/src/deque-help.pd | 45 +++++++ deque/src/deque-test.pd | 66 ++++++++++ deque/src/deque.c | 316 ++++++++++++++++++++++++++++++++++++++++++++++++ deque/src/dsqueue.c | 283 +++++++++++++++++++++++++++++++++++++++++++ deque/src/dsqueue.h | 171 ++++++++++++++++++++++++++ deque/src/squeue.c | 216 +++++++++++++++++++++++++++++++++ deque/src/squeue.h | 199 ++++++++++++++++++++++++++++++ deque/src/testme.c | 10 ++ 9 files changed, 1443 insertions(+) create mode 100644 deque/src/Makefile.am create mode 100644 deque/src/deque-help.pd create mode 100644 deque/src/deque-test.pd create mode 100644 deque/src/deque.c create mode 100644 deque/src/dsqueue.c create mode 100644 deque/src/dsqueue.h create mode 100644 deque/src/squeue.c create mode 100644 deque/src/squeue.h create mode 100644 deque/src/testme.c (limited to 'deque/src') diff --git a/deque/src/Makefile.am b/deque/src/Makefile.am new file mode 100644 index 0000000..28579d0 --- /dev/null +++ b/deque/src/Makefile.am @@ -0,0 +1,137 @@ +# File: ./src/Makefile.am +# Package: deque +# Description: +# + src-level automake file +# +# Process this file with Automake to create Makefile.in. +#----------------------------------------------------------------------- + +#----------------------------------------------------------------------- +# Options & Subdirectories +#----------------------------------------------------------------------- + +## --- recursion subdirectories +#SUBDIRS = + +## --- pseudo-deps for '.SUFFIXES' +SUFFIXES = .@PDEXT@ + +#----------------------------------------------------------------------- +# Flags and variables +#----------------------------------------------------------------------- +PDEXT = @PDEXT@ +EXEEXT = .@PDEXT@ + +#----------------------------------------------------------------------- +# pd externals (hacked _PROGRAMS target) +#----------------------------------------------------------------------- + +## --- externals +pdexterns_PROGRAMS = @PD_OBJECT_EXTERNALS@ + +## --- possible externals +EXTRA_PROGRAMS = \ + deque + +## --- patches +pdexterns_DATA = + +## --- documentation +pddoc_DATA = deque-help.pd + + +#----------------------------------------------------------------------- +# sources +#----------------------------------------------------------------------- + +deque_SOURCES = \ + squeue.c squeue.h \ + dsqueue.c dsqueue.h \ + deque.c + +#----------------------------------------------------------------------- +# external compilation : flags +#----------------------------------------------------------------------- +DEFS = @DEFS@ +AFLAGS = @AFLAGS@ +DFLAGS = @DFLAGS@ +IFLAGS = @IFLAGS@ +LFLAGS = @LFLAGS@ +OFLAGS = @OFLAGS@ +WFLAGS = -Wall -Winline + +#GLIB_IFLAGS = @GLIB_IFLAGS@ +#GLIB_LFLAGS = @GLIB_LFLAGS@ + +AM_CPPFLAGS = $(IFLAGS) $(GLIB_IFLAGS) $(DFLAGS) +AM_CFLAGS = $(OFLAGS) $(WFLAGS) $(AFLAGS) + +deque_LDFLAGS = $(LFLAGS) +deque_LDADD = $(GLIB_LFLAGS) + +#----------------------------------------------------------------------- +# Variables: cleanup +#----------------------------------------------------------------------- +## --- mostlyclean: built by 'make' & commonly rebuilt +#MOSTLYCLEANFILES = + +## --- clean: built by 'make' +CLEANFILES = *$(EXEEXT) + +## --- distclean: built by 'configure' +DISTCLEANFILES = \ + config.log \ + config.cache \ + config.status + +## -- maintainerclean: built by maintainer / by hand +MAINTAINERCLEANFILES = *~ \ + $(PODS:.pod=.txt) \ + Makefile Makefile.in \ + aclocal.m4 \ + configure \ + install-sh \ + stamp-h.in \ + config.h.in + +maintainer-clean-local: + rm -rf autom4te.cache + +#CVSCLEAN_SUBDIRS = $(SUBDIRS) + +#CVSCLEANFILES = Makefile.in Makefile + + +#----------------------------------------------------------------------- +# Variables: distribution +#----------------------------------------------------------------------- + +## --- extra distribution files +EXTRA_DIST = \ + $(pddoc_DATA) \ + $(pdexterns_DATA) + +## --- recursion subdirectories for 'make dist' +DIST_SUBDIRS = $(SUBDIRS) + +## --- dist-hook: when another 'Makefile.am' is overkill +#DISTHOOK_DIRS = foo +#DISTHOOK_FILES = foo/bar.txt foo/baz.txt +#dist-hook: +# for d in $(DISTHOOK_DIRS); do\ +# mkdir -p $(distdir)/$$d ;\ +# done +# for f in $(DISTHOOK_FILES); do\ +# cp -p $(srcdir)/$$f $(distdir)/$$f ;\ +# done + +#dist-bz2: dist-bzip2 ; + + +#----------------------------------------------------------------------- +# Rules: cleanup +#----------------------------------------------------------------------- +.PHONY: cvsclean cvsclean-hook + +cvsclean: maintainer-clean ; + diff --git a/deque/src/deque-help.pd b/deque/src/deque-help.pd new file mode 100644 index 0000000..e9b4b85 --- /dev/null +++ b/deque/src/deque-help.pd @@ -0,0 +1,45 @@ +#N canvas 62 30 512 484 10; +#X text 89 3 deque : double-ended message queue; +#X text 47 27 INLETS:; +#X text 58 40 1 - control messages; +#X text 58 53 2 - unshift (list); +#X text 57 67 3 - push (list); +#X text 253 28 OUTLETS:; +#X text 267 41 1 - dequeued messages; +#X text 198 455 Bryan Jurish ; +#X obj 51 391 deque; +#X msg 51 103 push foo bar; +#X msg 57 125 unshift baz bonk; +#X msg 77 180 pop; +#X text 241 177 "pop" : remove & outlet from end; +#X text 226 200 "shift" : remove & outlet from front; +#X msg 80 201 shift; +#X text 208 102 "push MSG" : add MSG to end; +#X text 187 125 "unshift MSG" : add MSG to front; +#X msg 86 223 bang; +#X text 232 222 "bang" : alias for "shift"; +#X msg 92 261 clear; +#X msg 93 284 flush; +#X text 225 256 "clear" : clear all elements; +#X msg 97 328 list bink bop; +#X msg 106 351 list fink fop; +#X text 216 328 LIST (inlet-2) : like "unshift LIST"; +#X text 216 352 LIST (inlet-3) : like "push LIST"; +#X text 225 278 "flush" : output front-to-back & clear; +#X msg 70 157 size; +#X text 233 156 "size" : get number of stored messages; +#X obj 81 414 print deque-status; +#X obj 51 438 print deque-content; +#X text 266 55 2 - status messages; +#X connect 8 0 30 0; +#X connect 8 1 29 0; +#X connect 9 0 8 0; +#X connect 10 0 8 0; +#X connect 11 0 8 0; +#X connect 14 0 8 0; +#X connect 17 0 8 0; +#X connect 19 0 8 0; +#X connect 20 0 8 0; +#X connect 22 0 8 1; +#X connect 23 0 8 2; +#X connect 27 0 8 0; diff --git a/deque/src/deque-test.pd b/deque/src/deque-test.pd new file mode 100644 index 0000000..e7a0cf5 --- /dev/null +++ b/deque/src/deque-test.pd @@ -0,0 +1,66 @@ +#N canvas 180 20 689 473 10; +#X obj 187 129 deque; +#X obj 128 163 print dq-elt; +#X obj 221 164 print dq-eoq; +#X msg 93 28 shift; +#X msg 95 49 pop; +#X msg 14 28 clear; +#X msg 15 52 flush; +#X msg 28 207 ------; +#X obj 27 232 print -------; +#X msg 172 27 push foo bar; +#X msg 174 50 push baz bonk; +#X msg 275 29 push list foo bar; +#X msg 280 50 push list baz bonk; +#X msg 265 88 list a b; +#X msg 330 89 list c d; +#X obj 446 256 deque; +#X floatatom 449 160 5 0 0 0 - - -; +#X msg 383 213 shift; +#X floatatom 441 288 5 0 0 0 - - -; +#X obj 441 306 bng 15 250 50 0 empty empty empty 0 -6 0 8 -262144 -1 +-1; +#X obj 490 288 bng 15 250 50 0 empty empty empty 0 -6 0 8 -262144 -1 +-1; +#X msg 383 194 clear; +#X msg 448 180 push \$1; +#X floatatom 519 161 5 0 0 0 - - -; +#X msg 518 181 push float \$1; +#X floatatom 22 102 5 0 0 0 - - -; +#X msg 20 119 push \$1; +#X floatatom 399 90 5 0 0 0 - - -; +#X msg 11 6 size; +#X msg 10 83 1; +#X msg 39 83 2; +#X msg 364 233 flush; +#X msg 401 106 list \$1; +#X connect 0 0 1 0; +#X connect 0 1 2 0; +#X connect 3 0 0 0; +#X connect 4 0 0 0; +#X connect 5 0 0 0; +#X connect 6 0 0 0; +#X connect 7 0 8 0; +#X connect 9 0 0 0; +#X connect 10 0 0 0; +#X connect 11 0 0 0; +#X connect 12 0 0 0; +#X connect 13 0 0 2; +#X connect 14 0 0 2; +#X connect 15 0 18 0; +#X connect 15 1 20 0; +#X connect 16 0 22 0; +#X connect 17 0 15 0; +#X connect 18 0 19 0; +#X connect 21 0 15 0; +#X connect 22 0 15 0; +#X connect 23 0 24 0; +#X connect 24 0 15 0; +#X connect 25 0 26 0; +#X connect 26 0 0 0; +#X connect 27 0 32 0; +#X connect 28 0 0 0; +#X connect 29 0 25 0; +#X connect 30 0 25 0; +#X connect 31 0 15 0; +#X connect 32 0 0 2; diff --git a/deque/src/deque.c b/deque/src/deque.c new file mode 100644 index 0000000..fd12b53 --- /dev/null +++ b/deque/src/deque.c @@ -0,0 +1,316 @@ +/* -*- Mode: C -*- */ +/*=============================================================================*\ + * File: deque.c + * Author: Bryan Jurish + * Description: double-ended message queue for pd + * + * Copyright (c) 2003,2004 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. + *=============================================================================*/ + + +/* black magic */ +#ifdef NT +#pragma warning( disable : 4244 ) +#pragma warning( disable : 4305 ) +#endif + +#ifndef _M_PD_H +# include +# define _M_PD_H +#endif + +#include "dsqueue.h" + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#ifndef PACKAGE_VERSION +# define PACKAGE_VERSION "(unknown)" +#endif + +/*-------------------------------------------------------------------- + * DEBUG + *--------------------------------------------------------------------*/ +//#define DEQUE_DEBUG 1 +//#undef DEQUE_DEBUG + +/*-------------------------------------------------------------------- + * Globals + *--------------------------------------------------------------------*/ +#define DEQUE_DEFAULT_BLOCKSIZE 32 + +/*===================================================================== + * pd_deque_elt + * + element class + *=====================================================================*/ +typedef struct pd_deque_elt +{ + //t_symbol *sel; // message selector + int argc; // number of message arguments + t_atom *argv; // message arguments +} t_pd_deque_elt; + +/*-------------------------------------------------------------------- + * pd_deque_elt_new() + * + create a new deque element + * + arg 'sel' currently ignored + */ +static t_pd_deque_elt *pd_deque_elt_new(t_symbol *sel, int argc, t_atom *argv) +{ + t_pd_deque_elt *elt = (t_pd_deque_elt *)getbytes(sizeof(t_pd_deque_elt)); + +#ifdef DEQUE_DEBUG + post("pd_deque_elt_new: got message with argc=%d", argc); +#endif + + //elt->sel = sel; + elt->argc = argc; + if (argc>0) { + elt->argv = (t_atom *)copybytes(argv, argc*sizeof(t_atom)); + } else { + elt->argv = NULL; + } + return elt; +} + +static void pd_deque_elt_free(t_pd_deque_elt *elt) +{ + if (elt->argc > 0) { + freebytes(elt->argv, elt->argc*sizeof(t_atom)); + } + elt->argv = NULL; + freebytes(elt, sizeof(t_pd_deque_elt)); +} + +/*===================================================================== + * pd_deque_class + *=====================================================================*/ +static t_class *pd_deque_class; +typedef struct _pd_deque_class +{ + t_object x_obj; // black magic + dsqueue_ptr x_deque; // ye olde guts + t_pd_deque_elt *x_cur; // current element + unsigned int x_size; // number of stored messages + t_outlet *elt_out; // data outlet + t_outlet *eoq_out; // end-of-queue bang-outlet / other data +} t_pd_deque; + + +/*===================================================================== + * pd methods + *=====================================================================*/ + +/*-------------------------------------------------------------------- + * push_front + * + push to the front of the queue + */ +static void pd_deque_push_front(t_pd_deque *x, t_symbol *sel, int argc, t_atom *argv) +{ + t_pd_deque_elt *elt = pd_deque_elt_new(sel,argc,argv); + +#ifdef DEQUE_DEBUG + post("pd_deque_push_back: got sel='%s', argc=%d", sel->s_name, argc); +#endif + + dsqueue_prepend(x->x_deque, elt); + ++x->x_size; +} + +/*-------------------------------------------------------------------- + * push_back + * + push to the back of the queue + */ +static void pd_deque_push_back(t_pd_deque *x, t_symbol *sel, int argc, t_atom *argv) +{ + t_pd_deque_elt *elt = pd_deque_elt_new(sel,argc,argv); + +#ifdef DEQUE_DEBUG + post("pd_deque_push_back: got sel='%s', argc=%d", sel->s_name, argc); +#endif + + dsqueue_append(x->x_deque, elt); + ++x->x_size; +} + +/*-------------------------------------------------------------------- + * outlet_cur + * + outlets current element to outlet-1, if non-NULL + * + otherwise, bangs to outlet-2 + */ +static void pd_deque_outlet_cur(t_pd_deque *x) +{ + if (x->x_cur) { + --x->x_size; + if (x->x_cur->argc == 1) { + switch (x->x_cur->argv->a_type) { + case A_FLOAT: + outlet_float(x->elt_out, x->x_cur->argv->a_w.w_float); + return; + case A_SYMBOL: + outlet_symbol(x->elt_out, x->x_cur->argv->a_w.w_symbol); + return; + case A_POINTER: + outlet_pointer(x->elt_out, x->x_cur->argv->a_w.w_gpointer); + return; + default: + error("Error: deque: unrecognized atom type '%d' defaults to 'bang'.", + x->x_cur->argv->a_type); + outlet_bang(x->elt_out); + } + } else { + outlet_anything(x->elt_out, + atom_getsymbol(x->x_cur->argv), + x->x_cur->argc-1, + x->x_cur->argv+1 + ); + } + } else { + outlet_bang(x->eoq_out); + } +} + +/*-------------------------------------------------------------------- + * pop_front + * + pop from the front of the queue + */ +static void pd_deque_pop_front(t_pd_deque *x) +{ + if (x->x_cur) { + pd_deque_elt_free(x->x_cur); + } + x->x_cur = (t_pd_deque_elt *)dsqueue_shift(x->x_deque); + pd_deque_outlet_cur(x); +} + +/*-------------------------------------------------------------------- + * pop_back + * + pop from the back of the queue + */ +static void pd_deque_pop_back(t_pd_deque *x) +{ + if (x->x_cur) { + pd_deque_elt_free(x->x_cur); + } + x->x_cur = (t_pd_deque_elt *)dsqueue_pop(x->x_deque); + pd_deque_outlet_cur(x); +} + + +/*-------------------------------------------------------------------- + * clear + * + clear the queue + */ +static void pd_deque_clear(t_pd_deque *x) +{ + if (x->x_cur) pd_deque_elt_free(x->x_cur); + while ( (x->x_cur = (t_pd_deque_elt *)dsqueue_shift(x->x_deque)) ) + pd_deque_elt_free(x->x_cur); + x->x_size = 0; +} + +/*-------------------------------------------------------------------- + * flush + * + flush queue contents (front-to-back) + * + probably dangerous + */ +static void pd_deque_flush(t_pd_deque *x) +{ + if (x->x_cur) pd_deque_elt_free(x->x_cur); + while ( (x->x_cur = (t_pd_deque_elt *)dsqueue_shift(x->x_deque)) ) { + pd_deque_outlet_cur(x); + pd_deque_elt_free(x->x_cur); + } + x->x_size = 0; +} + +/*-------------------------------------------------------------------- + * size + * + get number of stored messages + */ +static void pd_deque_size(t_pd_deque *x) +{ + t_atom sizeatom; + SETFLOAT(&sizeatom, x->x_size); + outlet_anything(x->eoq_out, gensym("size"), 1, &sizeatom); +} + +/*-------------------------------------------------------------------- + * newmethod, freemethod + */ +static void *pd_deque_new(t_floatarg f) +{ + t_pd_deque *x; + x = (t_pd_deque *)pd_new(pd_deque_class); + + /* -- queue -- */ + if (!f) f = DEQUE_DEFAULT_BLOCKSIZE; // 0: use default value + if (f < 1) { // specified but goofy: complain + error("deque: bad blocksize %g", f); + f = DEQUE_DEFAULT_BLOCKSIZE; + } + x->x_deque = dsqueue_new((unsigned)f); + + /* -- defaults --- */ + x->x_cur = NULL; + x->x_size = 0; + + /* --- extra inlet(s) --- */ + inlet_new(&x->x_obj, &x->x_obj.ob_pd, &s_list, gensym("unshift")); + inlet_new(&x->x_obj, &x->x_obj.ob_pd, &s_list, gensym("push")); + + /* -- outlets -- */ + x->elt_out = outlet_new(&x->x_obj, &s_anything); + x->eoq_out = outlet_new(&x->x_obj, &s_bang); + + return (void *)x; +} + +static void pd_deque_free(t_pd_deque *x) { + pd_deque_clear(x); + dsqueue_destroy(x->x_deque); +} + + +/*-------------------------------------------------------------------- + * setup + *--------------------------------------------------------------------*/ +void deque_setup(void) { + /* banner */ + post("\ndeque version %s by Bryan Jurish ", + PACKAGE_VERSION); + + /* register class */ + pd_deque_class = class_new(gensym("deque"), // name + (t_newmethod)pd_deque_new, // newmethod + (t_method)pd_deque_free, // freemethod + sizeof(t_pd_deque), // size + CLASS_DEFAULT, // flags + A_DEFFLOAT, // args + 0); + + /* --- methods: primary inlet --- */ + class_addmethod(pd_deque_class, (t_method)pd_deque_push_front, gensym("unshift"), A_GIMME, 0); + class_addmethod(pd_deque_class, (t_method)pd_deque_pop_front, gensym("bang"), 0); + class_addmethod(pd_deque_class, (t_method)pd_deque_pop_front, gensym("shift"), 0); + + class_addmethod(pd_deque_class, (t_method)pd_deque_push_back, gensym("push"), A_GIMME, 0); + class_addmethod(pd_deque_class, (t_method)pd_deque_pop_back, gensym("pop"), 0); + + class_addmethod(pd_deque_class, (t_method)pd_deque_clear, gensym("clear"), 0); + class_addmethod(pd_deque_class, (t_method)pd_deque_flush, gensym("flush"), 0); + + class_addmethod(pd_deque_class, (t_method)pd_deque_size, gensym("size"), 0); + + class_addanything(pd_deque_class, (t_method)pd_deque_push_back); // default: push_back + + /* --- help --- */ + class_sethelpsymbol(pd_deque_class, gensym("deque-help.pd")); +} + 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; + } +} 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 */ 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 diff --git a/deque/src/squeue.h b/deque/src/squeue.h new file mode 100644 index 0000000..9a963c2 --- /dev/null +++ b/deque/src/squeue.h @@ -0,0 +1,199 @@ +/* -*- Mode: C -*- */ +/* + * 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. + * + */ + +#ifndef SQUEUE_H +#define SQUEUE_H + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +/** + * \file squeue.h + * \brief Headers for static queues. + */ + +/// Queue structure. +typedef struct { + void **data; // data array + unsigned size; // number of allocated elements - 1 (index-max) + void **head; // head of queue + void **tail; // tail of queue +} squeue_t, *squeue_ptr; + +typedef void **squeue_iter_t; + +/*---------------------------------------------------------------------- + * Creation / Deletion + *----------------------------------------------------------------------*/ + +/// Create and initialize a new squeue. Returns NULL on failure. +extern squeue_ptr squeue_new(unsigned int size); + +/// Destroy an squeue -- implicitly calls clear(). +extern void squeue_destroy(squeue_ptr sq); + +/*---------------------------------------------------------------------- + * Predicates + *----------------------------------------------------------------------*/ + +#ifdef SQUEUE_DEBUG + +/// Returns true if the squeue has no elements. +extern char squeue_empty(squeue_ptr sq); + +/// Returns true if the squeue has no empty slots remaining. +extern char squeue_full(squeue_ptr sq); + +#else + +/// Returns true if the squeue has no elements. +# define squeue_empty(sq) (!sq->head) + +/// Returns true if the squeue has no empty slots remaining. +# define squeue_full(sq) (sq->head && sq->head == squeue_next(sq,sq->tail)) + +#endif + + +/*---------------------------------------------------------------------- + * Manipulation + *----------------------------------------------------------------------*/ + +#ifdef SQUEUE_DEBUG + +/// Clear all elements from an squeue. User data is not freed. +extern void squeue_clear(squeue_ptr sq); + +#else + +/// Clear all elements from an squeue. User data will not be freed. +# define squeue_clear(sq) sq->head = sq->tail = NULL + +#endif + +/// Prepend data to the front of an squeue. +/// Returns new head or NULL if queue is full. +extern void **squeue_prepend(squeue_ptr sq, void *data); + +/// Append data to the end of an squeue. +/// Returns new tail or NULL if queue is full. +extern void **squeue_append(squeue_ptr sq, void *data); + +/*---------------------------------------------------------------------- + * Access + *----------------------------------------------------------------------*/ + +/// Shift an element off the front of an squeue. +/// Returns a pointer to the element's data, or NULL if queue is empty. +extern void *squeue_shift(squeue_ptr sq); + +/// Pop an element off the back of an squeue. +/// Returns a pointer to the element's data, or NULL if queue is empty. +extern void *squeue_pop(squeue_ptr sq); + +#ifdef SQUEUE_DEBUG + +/// Returns the first datum in the queue, or NULL if queue is empty. +extern void *squeue_peek_head(squeue_ptr sq); + +/// Returns the final datum in the queue, or NULL if queue is empty. +extern void *squeue_peek_tail(squeue_ptr sq); + +#else + +/// Returns the first datum in the queue, or NULL if queue is empty. +# define squeue_peek_head(sq) (sq->head ? *(sq->head) : NULL) + +/// Returns the final datum in the queue, or NULL if queue is empty. +# define squeue_peek_tail(sq) (sq->tail ? *(sq->tail) : NULL) + +#endif /* SQUEUE_DEBUG */ + +/*---------------------------------------------------------------------- + * Utilities + *----------------------------------------------------------------------*/ +#ifdef SQUEUE_DEBUG + +/// Returns the index immediately preceeding 'p' (wrapped) +extern void **squeue_prev(squeue_t *sq, void **p); + +/// Returns the index immediately follwoing 'p' (wrapped) +extern void **squeue_next(squeue_t *sq, void **p); + +#else + +/// Returns the index immediately preceeding 'p' (wrapped) +# define squeue_prev(sq,p) (p && p > sq->data ? p-1 : sq->data+sq->size) + +/// Returns the index immediately follwoing 'p' (wrapped) +# define squeue_next(sq,p) (p && p < sq->data+sq->size ? p+1 : sq->data) + +#endif /* SQUEUE_DEBUG */ + + +/*---------------------------------------------------------------------- + * Iteration + *----------------------------------------------------------------------*/ +#ifdef SQUEUE_DEBUG + +/// Returns an iterator (pointer-pointer) for the first datum in the queue, +/// or NULL if queue is empty. +extern squeue_iter_t squeue_iter_first(squeue_t *sq); + +/// Returns an iterator for the next datum in the queue, or +/// NULL if already at end-of-queue. +extern squeue_iter_t squeue_iter_next(squeue_t *sq, squeue_iter_t sqi); + +/// Returns an iterator (pointer-pointer) for the final datum in the queue, +/// or NULL if queue is empty. +extern squeue_iter_t squeue_iter_last(squeue_t *sq); + +/// Returns an iterator for the previous datum in the queue, +/// or NULL if already at beginning-of-queue. +extern squeue_iter_t squeue_iter_prev(squeue_t *sq, squeue_iter_t sqi); + + +/// Returns a true value if p is a valid iterator value, false otherwise. +/// If you have initialized an incremented your iterator with the +/// squeue_iter() functions, a simple 'p != NULL' will suffice. +extern char squeue_iter_valid(squeue_t *sq, squeue_iter_t sqi); + + +/// Get the datum from an iterator or NULL if the iterator is invalid. +extern void *squeue_iter_data(squeue_iter_t sqi); + + +#else + +# define squeue_iter_first(sq) (sq->head) + +# define squeue_iter_last(sq) (sq->tail) + +# define squeue_iter_next(sq,sqi) \ + (sqi == sq->tail ? NULL : (sqi && sqi < sq->data+sq->size ? sqi+1 : sq->data)) + +# define squeue_iter_prev(sq,sqi) \ + (sqi == sq->head ? NULL : (sqi && sqi > sq->data ? sqi-1 : sqi+sq->size)) + +# define squeue_iter_valid(sq,sqi) \ + (sqi && sqi >= sq->data && sqi <= sq->data+sq->size) + +# define squeue_iter_data(sqi) (sqi ? *sqi : NULL) + +#endif /* SQUEUE_DEBUG */ + + + +#endif /* SQUEUE_H */ diff --git a/deque/src/testme.c b/deque/src/testme.c new file mode 100644 index 0000000..ebd9a10 --- /dev/null +++ b/deque/src/testme.c @@ -0,0 +1,10 @@ +#include + +#define FOO 42 +#define BAR(x) x + FOO + +int main (void) { + printf("BAR(1) = %d\n", BAR(1)); + return 0; +} + -- cgit v1.2.1