[PD-cvs] externals/moocow/deque/src Makefile.am, NONE, 1.1 deque-help.pd, NONE, 1.1 deque-test.pd, NONE, 1.1 deque.c, NONE, 1.1 dsqueue.c, NONE, 1.1 dsqueue.h, NONE, 1.1 squeue.c, NONE, 1.1 squeue.h, NONE, 1.1 testme.c, NONE, 1.1
Bryan Jurish
mukau at users.sourceforge.net
Thu Feb 2 13:40:33 CET 2006
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 at 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 at 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 at 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 at 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 at 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 at 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 = . at PDEXT@
#-----------------------------------------------------------------------
# Flags and variables
#-----------------------------------------------------------------------
PDEXT = @PDEXT@
EXEEXT = . at 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 at 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;
More information about the Pd-cvs
mailing list