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/COPYING | 290 +++++++++++++++++++++++++++++++++++++++++++ deque/Changes | 12 ++ deque/Makefile.am | 98 +++++++++++++++ deque/README.cvs | 16 +++ deque/README.pod | 154 +++++++++++++++++++++++ deque/autogen.sh | 48 +++++++ deque/config/Makefile.am | 66 ++++++++++ deque/configure.in | 201 ++++++++++++++++++++++++++++++ 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 ++ 17 files changed, 2328 insertions(+) create mode 100644 deque/COPYING create mode 100644 deque/Changes create mode 100644 deque/Makefile.am create mode 100644 deque/README.cvs create mode 100644 deque/README.pod create mode 100755 deque/autogen.sh create mode 100644 deque/config/Makefile.am create mode 100644 deque/configure.in 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 diff --git a/deque/COPYING b/deque/COPYING new file mode 100644 index 0000000..fa0bef4 --- /dev/null +++ b/deque/COPYING @@ -0,0 +1,290 @@ +GNU GENERAL PUBLIC LICENSE + +Version 2, June 1991 + +Copyright (C) 1989, 1991 Free Software Foundation, Inc. +59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + +Everyone is permitted to copy and distribute verbatim copies +of this license document, but changing it is not allowed. + +Preamble + +The licenses for most software are designed to take away your freedom +to share and change it. By contrast, the GNU General Public License is +intended to guarantee your freedom to share and change free +software--to make sure the software is free for all its users. This General +Public License applies to most of the Free Software Foundation's +software and to any other program whose authors commit to using it. +(Some other Free Software Foundation software is covered by the +GNU Library General Public License instead.) You can apply it to your +programs, too. + +When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new free +programs; and that you know you can do these things. + +To protect your rights, we need to make restrictions that forbid anyone +to deny you these rights or to ask you to surrender the rights. These +restrictions translate to certain responsibilities for you if you distribute +copies of the software, or if you modify it. + +For example, if you distribute copies of such a program, whether gratis +or for a fee, you must give the recipients all the rights that you have. You +must make sure that they, too, receive or can get the source code. And +you must show them these terms so they know their rights. + +We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + +Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, +we want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + +Finally, any free program is threatened constantly by software patents. +We wish to avoid the danger that redistributors of a free program will +individually obtain patent licenses, in effect making the program +proprietary. To prevent this, we have made it clear that any patent must +be licensed for everyone's free use or not licensed at all. + +The precise terms and conditions for copying, distribution and +modification follow. + +TERMS AND CONDITIONS FOR +COPYING, DISTRIBUTION AND +MODIFICATION + +0. This License applies to any program or other work which contains a +notice placed by the copyright holder saying it may be distributed under +the terms of this General Public License. The "Program", below, refers +to any such program or work, and a "work based on the Program" +means either the Program or any derivative work under copyright law: +that is to say, a work containing the Program or a portion of it, either +verbatim or with modifications and/or translated into another language. +(Hereinafter, translation is included without limitation in the term +"modification".) Each licensee is addressed as "you". + +Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of running +the Program is not restricted, and the output from the Program is +covered only if its contents constitute a work based on the Program +(independent of having been made by running the Program). Whether +that is true depends on what the Program does. + +1. You may copy and distribute verbatim copies of the Program's +source code as you receive it, in any medium, provided that you +conspicuously and appropriately publish on each copy an appropriate +copyright notice and disclaimer of warranty; keep intact all the notices +that refer to this License and to the absence of any warranty; and give +any other recipients of the Program a copy of this License along with the +Program. + +You may charge a fee for the physical act of transferring a copy, and +you may at your option offer warranty protection in exchange for a fee. + +2. You may modify your copy or copies of the Program or any portion +of it, thus forming a work based on the Program, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) You must cause the modified files to carry prominent notices + stating that you changed the files and the date of any change. + + b) You must cause any work that you distribute or publish, that in + whole or in part contains or is derived from the Program or any + part thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + + c) If the modified program normally reads commands interactively + when run, you must cause it, when started running for such + interactive use in the most ordinary way, to print or display an + announcement including an appropriate copyright notice and a + notice that there is no warranty (or else, saying that you provide a + warranty) and that users may redistribute the program under + these conditions, and telling the user how to view a copy of this + License. (Exception: if the Program itself is interactive but does + not normally print such an announcement, your work based on + the Program is not required to print an announcement.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Program, and +can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based on +the Program, the distribution of the whole must be on the terms of this +License, whose permissions for other licensees extend to the entire +whole, and thus to each and every part regardless of who wrote it. + +Thus, it is not the intent of this section to claim rights or contest your +rights to work written entirely by you; rather, the intent is to exercise the +right to control the distribution of derivative or collective works based +on the Program. + +In addition, mere aggregation of another work not based on the +Program with the Program (or with a work based on the Program) on a +volume of a storage or distribution medium does not bring the other +work under the scope of this License. + +3. You may copy and distribute the Program (or a work based on it, +under Section 2) in object code or executable form under the terms of +Sections 1 and 2 above provided that you also do one of the following: + + a) Accompany it with the complete corresponding + machine-readable source code, which must be distributed under + the terms of Sections 1 and 2 above on a medium customarily + used for software interchange; or, + + b) Accompany it with a written offer, valid for at least three + years, to give any third party, for a charge no more than your cost + of physically performing source distribution, a complete + machine-readable copy of the corresponding source code, to be + distributed under the terms of Sections 1 and 2 above on a + medium customarily used for software interchange; or, + + c) Accompany it with the information you received as to the offer + to distribute corresponding source code. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form with + such an offer, in accord with Subsection b above.) + +The source code for a work means the preferred form of the work for +making modifications to it. For an executable work, complete source +code means all the source code for all modules it contains, plus any +associated interface definition files, plus the scripts used to control +compilation and installation of the executable. However, as a special +exception, the source code distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies the +executable. + +If distribution of executable or object code is made by offering access to +copy from a designated place, then offering equivalent access to copy +the source code from the same place counts as distribution of the source +code, even though third parties are not compelled to copy the source +along with the object code. + +4. You may not copy, modify, sublicense, or distribute the Program +except as expressly provided under this License. Any attempt otherwise +to copy, modify, sublicense or distribute the Program is void, and will +automatically terminate your rights under this License. However, parties +who have received copies, or rights, from you under this License will not +have their licenses terminated so long as such parties remain in full +compliance. + +5. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Program or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Program (or any work based on the +Program), you indicate your acceptance of this License to do so, and all +its terms and conditions for copying, distributing or modifying the +Program or works based on it. + +6. Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the original +licensor to copy, distribute or modify the Program subject to these terms +and conditions. You may not impose any further restrictions on the +recipients' exercise of the rights granted herein. You are not responsible +for enforcing compliance by third parties to this License. + +7. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot distribute +so as to satisfy simultaneously your obligations under this License and +any other pertinent obligations, then as a consequence you may not +distribute the Program at all. For example, if a patent license would not +permit royalty-free redistribution of the Program by all those who +receive copies directly or indirectly through you, then the only way you +could satisfy both it and this License would be to refrain entirely from +distribution of the Program. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any patents +or other property right claims or to contest validity of any such claims; +this section has the sole purpose of protecting the integrity of the free +software distribution system, which is implemented by public license +practices. Many people have made generous contributions to the wide +range of software distributed through that system in reliance on +consistent application of that system; it is up to the author/donor to +decide if he or she is willing to distribute software through any other +system and a licensee cannot impose that choice. + +This section is intended to make thoroughly clear what is believed to be +a consequence of the rest of this License. + +8. If the distribution and/or use of the Program is restricted in certain +countries either by patents or by copyrighted interfaces, the original +copyright holder who places the Program under this License may add an +explicit geographical distribution limitation excluding those countries, so +that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + +9. The Free Software Foundation may publish revised and/or new +versions of the General Public License from time to time. Such new +versions will be similar in spirit to the present version, but may differ in +detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of this License which applies to it and "any +later version", you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number +of this License, you may choose any version ever published by the Free +Software Foundation. + +10. If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we +sometimes make exceptions for this. Our decision will be guided by the +two goals of preserving the free status of all derivatives of our free +software and of promoting the sharing and reuse of software generally. + +NO WARRANTY + +11. BECAUSE THE PROGRAM IS LICENSED FREE OF +CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, +TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT +WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE +PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, +EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND +PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD +THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE +COST OF ALL NECESSARY SERVICING, REPAIR OR +CORRECTION. + +12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW +OR AGREED TO IN WRITING WILL ANY COPYRIGHT +HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED +ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING +ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR +INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT +LIMITED TO LOSS OF DATA OR DATA BEING RENDERED +INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE +WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR +OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY +OF SUCH DAMAGES. + +END OF TERMS AND CONDITIONS diff --git a/deque/Changes b/deque/Changes new file mode 100644 index 0000000..ca28e80 --- /dev/null +++ b/deque/Changes @@ -0,0 +1,12 @@ +ChangeLog for Pd external 'deque' + +v0.03 Sat, 16 Oct 2004 13:17:14 +0200 + + added 'size' message to get length of stored queue + + fixed a bug in squeue_prev() for empty queues + +v0.02 Sat, 14 Feb 2004 15:55:13 +0100 + + fixed shift for single-element messages + +v0.01 ??? + + Initial revision + diff --git a/deque/Makefile.am b/deque/Makefile.am new file mode 100644 index 0000000..89efadc --- /dev/null +++ b/deque/Makefile.am @@ -0,0 +1,98 @@ +# File: ./Makefile.am +# Package: deque +# Description: +# + top-level automake file +# +# Process this file with Automake to create Makefile.in. +#----------------------------------------------------------------------- + +#----------------------------------------------------------------------- +# Options & Subdirectories +#----------------------------------------------------------------------- + +## --- automake options +#AUTOMAKE_OPTIONS = foreign dist-bzip2 dist-zip +AUTOMAKE_OPTIONS = foreign + +## --- recursion subdirectories +SUBDIRS = config src + +## --- pseudo-deps for '.SUFFIXES' +SUFFIXES = .pod .txt + +#----------------------------------------------------------------------- +# Variables: cleanup +#----------------------------------------------------------------------- +## --- mostlyclean: built by 'make' & commonly rebuilt +#MOSTLYCLEANFILES = + +## --- clean: built by 'make' +#CLEANFILES = + +## --- 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 + + +#----------------------------------------------------------------------- +# Additional Variables & Rules: PODS +#----------------------------------------------------------------------- +PODS = README.pod + +.pod.txt: + pod2text $< $@ + +all-local: $(PODS:.pod=.txt) + +#----------------------------------------------------------------------- +# Variables: distribution +#----------------------------------------------------------------------- + +## --- extra distribution files +EXTRA_DIST = \ + $(PODS:.pod=.txt) autogen.sh configure \ + README.cvs COPYING Changes + +## --- 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/README.cvs b/deque/README.cvs new file mode 100644 index 0000000..96b1253 --- /dev/null +++ b/deque/README.cvs @@ -0,0 +1,16 @@ +To build from cvs, do the following: + + ./autogen.sh + ./configure + make + make install + +You will need recent versions of GNU automake and +autoconf in order to build from the CVS tree. + +NOTE: The README.txt file in the distribution +is auto-generated from perl ".pod" format by +the "pod2text" included in most perl distributions. + +marmosets, + Bryan diff --git a/deque/README.pod b/deque/README.pod new file mode 100644 index 0000000..0fb180d --- /dev/null +++ b/deque/README.pod @@ -0,0 +1,154 @@ +=pod + +README for pd external 'deque' + +Last updated for version 0.03. + +=head1 DESCRIPTION + +Double-ended message-queue for pd. + + +=head1 PLATFORMS + +=over 4 + +=item * linux/x86 + +This is what I run, so things really ought to work here. + +=item * Other Platforms + +See REQUIREMENTS, below. + +=back + + +=head1 REQUIREMENTS + +In order to build the "deque" library, you will +need the following: + +=over 4 + + +=item * A C compiler + +Tested with gcc-3.3.3 under linux/x86 (Debian). + + +=item * /bin/sh , sed + +In order to run the 'configure' script. + + +=item * A make program + +Tested with GNU make v3.79.1 under linux/x86 (Debian). + + +=item * PD + +Tested with pd v0.37.1 under linux/x86 (Debian). +PD is available from: + + http://www.crca.ucsd.edu/~msp/software.html + + +=begin comment text + +=item * glib >= v2.0 + +For various buffer queues. +Available from http://www.gtk.org. + +=end comment text + + +=back + + +=head1 INSTALLATION + +Issue the following commands to the shell: + + cd PACKAGENAME-X.YY (or wherever you extracted the distribution) + ./configure + make + make install + + +=head1 BUILD OPTIONS + +The 'configure' script supports the following options, among others: + + +=over 4 + +=item * --with-pd-dir=DIR + +PD base directory. + + +=item * --with-pd-include=DIR + +Directory where the PD include files live. + + +=item * --with-pd-extdir=DIR + +Where to put the externals on 'make install'. + + +=begin comment text + +=item * --with-pkg-config=PATH + +Full path to the 'pkg-config' program (optional). + + +=item * --with-glib-include=DIR + +Directory where the glib >= 2.0 include files live. + + +=item * --with-glib-libs=DIR + +Linker flags for glib >= 2.0. + +=end comment text + + +=item * --enable-debug , --disable-debug + +Whether to enable verbose debugging messages and code. +Default=no. + +=back + + +=head1 ACKNOWLEDGEMENTS + +PD by Miller Puckette and others. + +Ideas, black magic, and other nuggets of information drawn +from code by Guenter Geiger, Larry Troxler, and +IOhannes m Zmoelnig. + + +=head1 KNOWN BUGS + +=over 4 + +=item * General + +Only tested under linux. + +=back + + + + +=head1 AUTHOR / MAINTAINER + +Bryan Jurish Emoocow@ling.uni-potsdam.deE diff --git a/deque/autogen.sh b/deque/autogen.sh new file mode 100755 index 0000000..845f276 --- /dev/null +++ b/deque/autogen.sh @@ -0,0 +1,48 @@ +#!/bin/sh + +#----------------------------------------------------------------------- +# File: autogen.sh +# Description: +# + wrapper for m4 black-magic +#----------------------------------------------------------------------- + +MY_ALDIRS="." +MY_AHDIRS="." +MY_AMDIRS="." +MY_ACDIRS="." + +test -z "$ACLOCAL" && ACLOCAL=aclocal +test -z "$AUTOHEADER" && AUTOHEADER=autoheader +test -z "$AUTOMAKE" && AUTOMAKE=automake +test -z "$AUTOCONF" && AUTOCONF=autoconf + +if test -n "$MY_ALDIRS"; then + for d in $MY_ALDIRS ; do + echo "(cd $d ; $ACLOCAL)" + (cd $d ; $ACLOCAL) + done +fi + +if test -n "$MY_AHDIRS"; then + for d in $MY_AHDIRS ; do + echo "(cd $d ; $AUTOHEADER)" + (cd $d ; $AUTOHEADER) + done +fi + +if test -n "$MY_AMDIRS"; then + for d in $MY_AMDIRS ; do + echo "(cd $d ; $AUTOMAKE -a)" + (cd $d ; $AUTOMAKE -a) + done +fi + +if test -n "$MY_ACDIRS"; then + for d in $MY_ACDIRS ; do + echo "(cd $d ; $AUTOCONF)" + (cd $d ; $AUTOCONF) + done +fi + +#echo "(./configure)" +#./configure $* diff --git a/deque/config/Makefile.am b/deque/config/Makefile.am new file mode 100644 index 0000000..3e097e9 --- /dev/null +++ b/deque/config/Makefile.am @@ -0,0 +1,66 @@ +## File: config/Makefile.am +## Package: +## Description: +## + automake file for 'config' package-subdir +## +## Process this file with Automake to create Makefile.in. +##----------------------------------------------------------------------- + +##----------------------------------------------------------------------- +## Variables: options +##----------------------------------------------------------------------- + +##----------------------------------------------------------------------- +## Variables: cleanup +##----------------------------------------------------------------------- + +## --- mostlyclean: built by 'make' & commonly rebuilt +#MOSTLYCLEANFILES = + +## --- clean: built by 'make' +#CLEANFILES = + +## --- distclean: built by 'configure' +#DISTCLEANFILES = + +## -- maintainerclean: built by maintainer / by hand +MAINTAINERCLEANFILES = \ + *~ .*~ \ + compile Makefile Makefile.in \ + config.guess \ + config.sub \ + depcomp \ + install-sh \ + ltmain.sh \ + missing \ + mkinstalldirs \ + texinfo.tex \ + ylwrap + + +##----------------------------------------------------------------------- +## Variables: distribution +##----------------------------------------------------------------------- + +## --- extra distribution files +EXTRA_DIST = \ + Makefile.in \ + depcomp \ + install-sh \ + mkinstalldirs \ + missing + +# config.guess +# config.sub +# ltmain.sh +# texinfo.tex + +## --- recursion subdirectories for 'make dist' +#DIST_SUBDIRS = $(SUBDIRS) + +#----------------------------------------------------------------------- +# Rules: cleanup +#----------------------------------------------------------------------- +.PHONY: cvsclean cvsclean-hook + +cvsclean: maintainer-clean ; diff --git a/deque/configure.in b/deque/configure.in new file mode 100644 index 0000000..008e991 --- /dev/null +++ b/deque/configure.in @@ -0,0 +1,201 @@ +dnl Process this file with autoconf to produce a configure script. +dnl -- for a clean build, run: aclocal && autoheader && automake -a && autoconf +AC_PREREQ(2.5) + +dnl Some handy macros +define([THE_PACKAGE_NAME], [pd-deque]) +define([THE_PACKAGE_VERSION], [0.03]) +define([THE_PACKAGE_AUTHOR], [moocow@ling.uni-potsdam.de]) + +AC_INIT(THE_PACKAGE_NAME, THE_PACKAGE_VERSION, THE_PACKAGE_AUTHOR) + +dnl +dnl source & aux +dnl +AC_CONFIG_AUX_DIR(config) + +dnl +dnl save user's CFLAGS,CPPFLAGS +dnl +UCPPFLAGS="$CPPFLAGS" +UCFLAGS="$CFLAGS" + +dnl +dnl use automake +dnl +AM_INIT_AUTOMAKE(THE_PACKAGE_NAME, THE_PACKAGE_VERSION) + +dnl +dnl use autoheader +dnl +AM_CONFIG_HEADER(src/config.h) + + +dnl +dnl Programs, prefix +dnl +AC_PROG_CC +AC_PROG_INSTALL +AC_PREFIX_DEFAULT(/usr/local) + +dnl +dnl Substitutions +dnl +AC_SUBST(DEFS) +AC_SUBST(AFLAGS) +AC_SUBST(DFLAGS) +AC_SUBST(IFLAGS) +AC_SUBST(LFLAGS) +AC_SUBST(OFLAGS) +AC_SUBST(WFLAGS) +AC_SUBST(LD) + +AC_SUBST(PDEXT) + +dnl version stuff (automatically exported?) +AC_SUBST(PACKAGE_VERSION) +AC_SUBST(PACKAGE_NAME) +AC_SUBST(BUGREPORT) + +dnl ----- begin imported rsynth configuration stuff + +dnl other flags +AC_ISC_POSIX + +dnl Checks for header files. +dnl AC_HEADER_STDC +AC_CHECK_HEADERS([stdlib.h errno.h], + [], + AC_MSG_WARN([-----------------------------------------------------------------]) + AC_MSG_WARN([could not find standard C headers -- things may get ugly]) + AC_MSG_WARN([-----------------------------------------------------------------]), + [/* nonempty includes: compile only */]) + + +dnl PD externals +PD_OBJECT_EXTERNALS="deque\$(EXEEXT)" +AC_SUBST(PD_OBJECT_EXTERNALS) + + +dnl +dnl pd-directory/ies +dnl +AC_ARG_WITH(pd-dir, + AC_HELP_STRING([--with-pd-dir=DIR], [PD base directory (default=PREFIX/pd)]), + [pddir="$withval"], + [pddir="\${prefix}/pd"]) +pddocdir="${pddir}/doc/5.reference" +AC_SUBST(pddir) +AC_SUBST(pddocdir) + + + +AC_ARG_WITH(pd-include, + AC_HELP_STRING([--with-pd-include=DIR], [PD include directory (default=NONE)]), + [pdincludedir="$withval"], + [pdincludedir=""]) +if test -n "$pdincludedir" ; then + IFLAGS="$IFLAGS -I$pdincludedir" +fi +AC_SUBST(pdincludedir) + +AC_ARG_WITH(pd-extdir, + AC_HELP_STRING([--with-pd-extdir=DIR], [Directory for PD externals (default=PDDIR/externs)]), + [pdexternsdir="$withval"], + [pdexternsdir="$pddir/externs"]) +AC_SUBST(pdexternsdir) + +dnl +dnl Check for m_pd.h +dnl +CPPFLAGS="$CPPFLAGS $IFLAGS" +AC_CHECK_HEADER(m_pd.h,[], + AC_MSG_WARN([-----------------------------------------------------------------]) + AC_MSG_WARN([could not find PD header file 'm_pd.h' -- things might get ugly.]) + AC_MSG_WARN([-----------------------------------------------------------------]), + [/* nonempty includes: compile only */]) + + +dnl +dnl debug version? +dnl +AC_MSG_CHECKING([whether we are building a debug version]) +AC_ARG_ENABLE([debug], + AC_HELP_STRING([--enable-debug],[build debug version (default=no)])) +if test "$enable_debug" == "yes" ; then + AC_MSG_RESULT(yes) + DEBUG="yes" + AC_DEFINE(DEQUE_DEBUG,1, + [Define this to include debugging code for the 'deque' external.]) + AC_DEFINE(SQUEUE_DEBUG,1, + [Define this to include debugging code for 'squeue' code.]) +else + AC_MSG_RESULT(no) + DEBUG="no" +fi +AC_SUBST(DEBUG) + + + +dnl +dnl machine-dependent variables +dnl +LD=ld +if test `uname -s` = Linux; +then + LFLAGS="-export_dynamic -shared" + if test "$DEBUG" == "no"; then + #OFLAGS="-O6 -funroll-loops -fomit-frame-pointer -finline-limit-10000000" + OFLAGS="-O6 -funroll-loops -fomit-frame-pointer" + else + OFLAGS="-g" + fi + PDEXT=pd_linux +fi + +if test `uname -m` = alpha; +then + AFLAGS="-mieee -mcpu=ev56"; + OFLAGS="$CFLAGS" +fi + +if test `uname -s` = IRIX64; +then + LFLAGS="-n32 -DUNIX -DIRIX -DN32 -woff 1080,1064,1185 \ + -OPT:roundoff=3 -OPT:IEEE_arithmetic=3 -OPT:cray_ivdep=true \ + -shared -rdata_shared" + OFLAGS="$CFLAGS" + PDEXT=pd_irix6 +fi + +if test `uname -s` = IRIX32; +then + LFLAGS="-o32 -DUNIX -DIRIX -O2 -shared -rdata_shared" + OFLAGS="$CFLAGS" + PDEXT=pd_irix5 +fi + +dnl +dnl Flags for MacOSX, borrowed from pd-0.35-test16 +dnl +if test `uname -s` = Darwin; +then + LD=cc + LFLAGS="-bundle -undefined suppress -flat_namespace" + PDEXT=pd_darwin + DFLAGS="$DFLAGS -DMACOSX" + + if test "$DEBUG" == "no"; then + OFLAGS="-O2" + else + OFLAGS="-g" + fi +fi + +dnl +dnl restore user's CFLAGS +dnl +CFLAGS="$UCFLAGS" +CPPFLAGS="$UCPPFLAGS" + +AC_OUTPUT(config/Makefile src/Makefile Makefile) 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