Update of /cvsroot/pure-data/externals/moocow/deque/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv21741/src
Added Files: Makefile.am deque-help.pd deque-test.pd deque.c dsqueue.c dsqueue.h squeue.c squeue.h testme.c Log Message: + initial CVS import
--- NEW FILE: dsqueue.c --- /* * File: dsqueue.c * Author: Bryan Jurish moocow@ling.uni-potsdam.de * * 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 <stdlib.h> #include <errno.h>
#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; } }
--- NEW FILE: deque.c --- /* -*- Mode: C -*- */ /*=============================================================================*\ * File: deque.c * Author: Bryan Jurish moocow@ling.uni-potsdam.de * 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 <m_pd.h> # 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 moocow@ling.uni-potsdam.de", 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")); }
--- NEW FILE: squeue.c --- /* * * File: squeue.h * Author: Bryan Jurish moocow@ling.uni-potsdam.de * * 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 <stdlib.h> #include <errno.h> #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
--- NEW FILE: testme.c --- #include <stdio.h>
#define FOO 42 #define BAR(x) x + FOO
int main (void) { printf("BAR(1) = %d\n", BAR(1)); return 0; }
--- NEW FILE: deque-test.pd --- #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;
--- NEW FILE: dsqueue.h --- /* -*- Mode: C -*- */ /* * File: dsqueue.h * Author: Bryan Jurish moocow@ling.uni-potsdam.de * * 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 */
--- NEW FILE: squeue.h --- /* -*- Mode: C -*- */ /* * File: squeue.h * Author: Bryan Jurish moocow@ling.uni-potsdam.de * * 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 */
--- NEW FILE: Makefile.am --- # 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 ;
--- NEW FILE: deque-help.pd --- #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 moocow@ling.uni-potsdam.de; #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;