summaryrefslogtreecommitdiff
path: root/draft/mcastseed
diff options
context:
space:
mode:
authorLudovic Pouzenc <ludovic@pouzenc.fr>2017-05-05 11:28:51 +0200
committerLudovic Pouzenc <ludovic@pouzenc.fr>2017-05-05 11:28:51 +0200
commit604f3d64764270c052cfb43081ec522237bbdb75 (patch)
treeb3db80e35399412693c7a986b3021435b2914fe4 /draft/mcastseed
parentf7f175cb29192682f3ece9479f24a40672a3d74d (diff)
downloadeficast-604f3d64764270c052cfb43081ec522237bbdb75.tar.gz
eficast-604f3d64764270c052cfb43081ec522237bbdb75.tar.bz2
eficast-604f3d64764270c052cfb43081ec522237bbdb75.zip
Massive add for all draft stuff to keep it in sync
Diffstat (limited to 'draft/mcastseed')
-rw-r--r--draft/mcastseed/AUTHORS3
-rw-r--r--draft/mcastseed/COPYING340
-rw-r--r--draft/mcastseed/ChangeLog0
-rw-r--r--draft/mcastseed/Makefile.am5
-rw-r--r--draft/mcastseed/NEWS0
l---------draft/mcastseed/README1
-rw-r--r--draft/mcastseed/README.md9
-rw-r--r--draft/mcastseed/configure.ac69
-rw-r--r--draft/mcastseed/lib/Makefile.am93
-rw-r--r--draft/mcastseed/lib/gl_anyrbtree_list1.h76
-rw-r--r--draft/mcastseed/lib/gl_anyrbtree_list2.h1028
-rw-r--r--draft/mcastseed/lib/gl_anytree_list1.h41
-rw-r--r--draft/mcastseed/lib/gl_anytree_list2.h940
-rw-r--r--draft/mcastseed/lib/gl_list.c3
-rw-r--r--draft/mcastseed/lib/gl_list.h841
-rw-r--r--draft/mcastseed/lib/gl_rbtree_list.c102
-rw-r--r--draft/mcastseed/lib/gl_rbtree_list.h34
-rw-r--r--draft/mcastseed/lib/stdbool.in.h132
-rw-r--r--draft/mcastseed/m4/00gnulib.m446
-rw-r--r--draft/mcastseed/m4/extern-inline.m4102
-rw-r--r--draft/mcastseed/m4/gnulib-cache.m447
-rw-r--r--draft/mcastseed/m4/gnulib-common.m4462
-rw-r--r--draft/mcastseed/m4/gnulib-comp.m4221
-rw-r--r--draft/mcastseed/m4/gnulib-tool.m457
-rw-r--r--draft/mcastseed/m4/stdbool.m4104
-rw-r--r--draft/mcastseed/src/Makefile.am16
-rw-r--r--draft/mcastseed/src/dgrambuf.c583
-rw-r--r--draft/mcastseed/src/dgrambuf.h41
-rw-r--r--draft/mcastseed/src/dgrambuf_test.c50
-rw-r--r--draft/mcastseed/src/mcastleech.c408
-rw-r--r--draft/mcastseed/src/mcastseed.c472
-rw-r--r--draft/mcastseed/src/random_speed_dd.c36
-rw-r--r--draft/mcastseed/src/sockets.c303
-rw-r--r--draft/mcastseed/src/sockets.h27
34 files changed, 6692 insertions, 0 deletions
diff --git a/draft/mcastseed/AUTHORS b/draft/mcastseed/AUTHORS
new file mode 100644
index 0000000..c338cf6
--- /dev/null
+++ b/draft/mcastseed/AUTHORS
@@ -0,0 +1,3 @@
+Ludovic Pouzenc <ludovic@pouzenc.fr>
+Christian Beier <dontmind@freeshell.org>
+tmouse, http://cboard.cprogramming.com/showthread.php?t=67469
diff --git a/draft/mcastseed/COPYING b/draft/mcastseed/COPYING
new file mode 100644
index 0000000..d60c31a
--- /dev/null
+++ b/draft/mcastseed/COPYING
@@ -0,0 +1,340 @@
+ 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.
+
+ GNU GENERAL PUBLIC LICENSE
+ 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
+
+ How to Apply These Terms to Your New Programs
+
+ If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+
+ To do so, attach the following notices to the program. It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+ <one line to give the program's name and a brief idea of what it does.>
+ Copyright (C) <year> <name of author>
+
+ 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 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+ Gnomovision version 69, Copyright (C) year name of author
+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+ This is free software, and you are welcome to redistribute it
+ under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License. Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary. Here is a sample; alter the names:
+
+ Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+ `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+ <signature of Ty Coon>, 1 April 1989
+ Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program into
+proprietary programs. If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library. If this is what you want to do, use the GNU Library General
+Public License instead of this License.
diff --git a/draft/mcastseed/ChangeLog b/draft/mcastseed/ChangeLog
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/draft/mcastseed/ChangeLog
diff --git a/draft/mcastseed/Makefile.am b/draft/mcastseed/Makefile.am
new file mode 100644
index 0000000..b07663c
--- /dev/null
+++ b/draft/mcastseed/Makefile.am
@@ -0,0 +1,5 @@
+## Process this file with automake to produce Makefile.in
+SUBDIRS = lib src
+# For Gnulib
+ACLOCAL_AMFLAGS = -I m4
+EXTRA_DIST = m4/gnulib-cache.m4
diff --git a/draft/mcastseed/NEWS b/draft/mcastseed/NEWS
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/draft/mcastseed/NEWS
diff --git a/draft/mcastseed/README b/draft/mcastseed/README
new file mode 120000
index 0000000..42061c0
--- /dev/null
+++ b/draft/mcastseed/README
@@ -0,0 +1 @@
+README.md \ No newline at end of file
diff --git a/draft/mcastseed/README.md b/draft/mcastseed/README.md
new file mode 100644
index 0000000..98ddff0
--- /dev/null
+++ b/draft/mcastseed/README.md
@@ -0,0 +1,9 @@
+
+This is a simple multicast file transfer with TCP back-chat.
+Greatly inspired from https://github.com/bk138/Multicast-Client-Server-Example
+
+Tested on GNU/Linux Debian 8, may usable under other OS without big efforts (patches appreciated).
+
+# Building
+To compile, use
+ autoreconf -fi && ./configure && make
diff --git a/draft/mcastseed/configure.ac b/draft/mcastseed/configure.ac
new file mode 100644
index 0000000..e9e292f
--- /dev/null
+++ b/draft/mcastseed/configure.ac
@@ -0,0 +1,69 @@
+# -*- Autoconf -*-
+# Process this file with autoconf to produce a configure script.
+
+AC_PREREQ([2.69])
+AC_INIT(mcastseeder, 0.1, ludovic@pouzenc.fr)
+
+# Args deprecated http://www.gnu.org/software/automake/manual/automake.html#Modernize-AM_005fINIT_005fAUTOMAKE-invocation
+AM_INIT_AUTOMAKE #(AC_PACKAGE_NAME, AC_PACKAGE_VERSION)
+AM_CONFIG_HEADER(config.h)
+AM_MAINTAINER_MODE
+
+AC_CANONICAL_HOST
+case $host_os in
+ darwin*)
+ HOST_IS_DARWIN="yes"
+ ;;
+ *mingw32*)
+ HOST_IS_WINDOWS="yes"
+ ;;
+ *)
+ HOST_IS_DARWIN="no"
+ HOST_IS_WINDOWS="no"
+ ;;
+esac
+
+if test "$HOST_IS_WINDOWS" = "yes"; then
+ WSOCKLIB="-lws2_32"
+ AC_SUBST(WSOCKLIB)
+fi
+
+
+AM_CONDITIONAL(MINGW, [ test "$HOST_IS_WINDOWS" = "yes" ])
+AM_CONDITIONAL(DARWIN, [ test "$HOST_IS_DARWIN" = "yes" ])
+
+# Checks for programs.
+AC_ISC_POSIX
+AC_HEADER_STDC
+AC_PROG_CPP
+AC_PROG_CC
+# Gnulib
+gl_EARLY
+AM_PROG_CC_STDC
+AM_PROG_CC_C_O
+
+# Checks for libraries.
+
+# Checks for header files.
+AC_CHECK_HEADERS([OS.h fcntl.h limits.h netdb.h stddef.h stdint.h stdlib.h string.h sys/socket.h unistd.h])
+
+# Checks for typedefs, structures, and compiler characteristics.
+AC_CHECK_HEADER_STDBOOL
+AC_TYPE_SIZE_T
+AC_TYPE_SSIZE_T
+AC_TYPE_UINT32_T
+AC_TYPE_UINT64_T
+AC_TYPE_UINT8_T
+
+# Checks for library functions.
+AC_FUNC_MALLOC
+AC_CHECK_FUNCS([alarm memset select socket])
+
+AC_CONFIG_FILES([Makefile
+ lib/Makefile
+ src/Makefile])
+
+# Gnulib
+gl_INIT
+
+AC_OUTPUT
diff --git a/draft/mcastseed/lib/Makefile.am b/draft/mcastseed/lib/Makefile.am
new file mode 100644
index 0000000..38faabe
--- /dev/null
+++ b/draft/mcastseed/lib/Makefile.am
@@ -0,0 +1,93 @@
+## DO NOT EDIT! GENERATED AUTOMATICALLY!
+## Process this file with automake to produce Makefile.in.
+# Copyright (C) 2002-2016 Free Software Foundation, Inc.
+#
+# This file 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 3 of the License, or
+# (at your option) any later version.
+#
+# This file is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this file. If not, see <http://www.gnu.org/licenses/>.
+#
+# As a special exception to the GNU General Public License,
+# this file may be distributed as part of a program that
+# contains a configuration script generated by Autoconf, under
+# the same distribution terms as the rest of that program.
+#
+# Generated by gnulib-tool.
+# Reproduce by: gnulib-tool --import --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=. --no-conditional-dependencies --no-libtool --macro-prefix=gl rbtree-list
+
+AUTOMAKE_OPTIONS = 1.9.6 gnits
+
+SUBDIRS =
+noinst_HEADERS =
+noinst_LIBRARIES =
+noinst_LTLIBRARIES =
+EXTRA_DIST =
+BUILT_SOURCES =
+SUFFIXES =
+MOSTLYCLEANFILES = core *.stackdump
+MOSTLYCLEANDIRS =
+CLEANFILES =
+DISTCLEANFILES =
+MAINTAINERCLEANFILES =
+
+AM_CPPFLAGS =
+AM_CFLAGS =
+
+noinst_LIBRARIES += libgnu.a
+
+libgnu_a_SOURCES =
+libgnu_a_LIBADD = $(gl_LIBOBJS)
+libgnu_a_DEPENDENCIES = $(gl_LIBOBJS)
+EXTRA_libgnu_a_SOURCES =
+
+## begin gnulib module list
+
+libgnu_a_SOURCES += gl_list.h gl_list.c
+
+## end gnulib module list
+
+## begin gnulib module rbtree-list
+
+libgnu_a_SOURCES += gl_rbtree_list.h gl_rbtree_list.c gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h
+
+## end gnulib module rbtree-list
+
+## begin gnulib module stdbool
+
+BUILT_SOURCES += $(STDBOOL_H)
+
+# We need the following in order to create <stdbool.h> when the system
+# doesn't have one that works.
+if GL_GENERATE_STDBOOL_H
+stdbool.h: stdbool.in.h $(top_builddir)/config.status
+ $(AM_V_GEN)rm -f $@-t $@ && \
+ { echo '/* DO NOT EDIT! GENERATED AUTOMATICALLY! */'; \
+ sed -e 's/@''HAVE__BOOL''@/$(HAVE__BOOL)/g' < $(srcdir)/stdbool.in.h; \
+ } > $@-t && \
+ mv $@-t $@
+else
+stdbool.h: $(top_builddir)/config.status
+ rm -f $@
+endif
+MOSTLYCLEANFILES += stdbool.h stdbool.h-t
+
+EXTRA_DIST += stdbool.in.h
+
+## end gnulib module stdbool
+
+
+mostlyclean-local: mostlyclean-generic
+ @for dir in '' $(MOSTLYCLEANDIRS); do \
+ if test -n "$$dir" && test -d $$dir; then \
+ echo "rmdir $$dir"; rmdir $$dir; \
+ fi; \
+ done; \
+ :
diff --git a/draft/mcastseed/lib/gl_anyrbtree_list1.h b/draft/mcastseed/lib/gl_anyrbtree_list1.h
new file mode 100644
index 0000000..0ae0715
--- /dev/null
+++ b/draft/mcastseed/lib/gl_anyrbtree_list1.h
@@ -0,0 +1,76 @@
+/* Sequential list data type implemented by a binary tree.
+ Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
+
+/* A red-black tree is a binary tree where every node is colored black or
+ red such that
+ 1. The root is black.
+ 2. No red node has a red parent.
+ Or equivalently: No red node has a red child.
+ 3. All paths from the root down to any NULL endpoint contain the same
+ number of black nodes.
+ Let's call this the "black-height" bh of the tree. It follows that every
+ such path contains exactly bh black and between 0 and bh red nodes. (The
+ extreme cases are a path containing only black nodes, and a path colored
+ alternately black-red-black-red-...-black-red.) The height of the tree
+ therefore is >= bh, <= 2*bh.
+ */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Color of a node. */
+typedef enum color { BLACK, RED } color_t;
+
+/* Concrete list node implementation, valid for this file only. */
+struct gl_list_node_impl
+{
+#if WITH_HASHTABLE
+ struct gl_hash_entry h; /* hash table entry fields; must be first */
+#endif
+ struct gl_list_node_impl *left; /* left branch, or NULL */
+ struct gl_list_node_impl *right; /* right branch, or NULL */
+ /* Parent pointer, or NULL. The parent pointer is not needed for most
+ operations. It is needed so that a gl_list_node_t can be returned
+ without memory allocation, on which the functions gl_list_remove_node,
+ gl_list_add_before, gl_list_add_after can be implemented. */
+ struct gl_list_node_impl *parent;
+ color_t color; /* node's color */
+ size_t branch_size; /* number of nodes in this branch,
+ = branchsize(left)+branchsize(right)+1 */
+ const void *value;
+};
+
+/* Concrete gl_list_impl type, valid for this file only. */
+struct gl_list_impl
+{
+ struct gl_list_impl_base base;
+#if WITH_HASHTABLE
+ /* A hash table: managed as an array of collision lists. */
+ struct gl_hash_entry **table;
+ size_t table_size;
+#endif
+ struct gl_list_node_impl *root; /* root node or NULL */
+};
+
+/* A red-black tree of height h has a black-height bh >= ceil(h/2) and
+ therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
+ of height h >= 117 would have at least 2^59 - 1 elements, and because even
+ on 64-bit machines,
+ sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64
+ this would exceed the address space of the machine. */
+#define MAXHEIGHT 116
diff --git a/draft/mcastseed/lib/gl_anyrbtree_list2.h b/draft/mcastseed/lib/gl_anyrbtree_list2.h
new file mode 100644
index 0000000..a0e2e43
--- /dev/null
+++ b/draft/mcastseed/lib/gl_anyrbtree_list2.h
@@ -0,0 +1,1028 @@
+/* Sequential list data type implemented by a binary tree.
+ Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Create a subtree for count >= 1 elements.
+ Its black-height bh is passed as argument, with
+ 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1.
+ Its height is h where 2^(h-1) <= count <= 2^h - 1.
+ Return NULL upon out-of-memory. */
+static gl_list_node_t
+create_subtree_with_contents (unsigned int bh,
+ size_t count, const void **contents)
+{
+ size_t half1 = (count - 1) / 2;
+ size_t half2 = count / 2;
+ /* Note: half1 + half2 = count - 1. */
+ gl_list_node_t node =
+ (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+ if (node == NULL)
+ return NULL;
+
+ if (half1 > 0)
+ {
+ /* half1 > 0 implies count > 1, implies bh >= 1, implies
+ 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
+ node->left =
+ create_subtree_with_contents (bh - 1, half1, contents);
+ if (node->left == NULL)
+ goto fail1;
+ node->left->parent = node;
+ }
+ else
+ node->left = NULL;
+
+ node->value = contents[half1];
+
+ if (half2 > 0)
+ {
+ /* half2 > 0 implies count > 1, implies bh >= 1, implies
+ 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
+ node->right =
+ create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
+ if (node->right == NULL)
+ goto fail2;
+ node->right->parent = node;
+ }
+ else
+ node->right = NULL;
+
+ node->color = (bh == 0 ? RED : BLACK);
+
+ node->branch_size = count;
+
+ return node;
+
+ fail2:
+ if (node->left != NULL)
+ free_subtree (node->left);
+ fail1:
+ free (node);
+ return NULL;
+}
+
+static gl_list_t
+gl_tree_nx_create (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates,
+ size_t count, const void **contents)
+{
+ struct gl_list_impl *list =
+ (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+ if (list == NULL)
+ return NULL;
+
+ list->base.vtable = implementation;
+ list->base.equals_fn = equals_fn;
+ list->base.hashcode_fn = hashcode_fn;
+ list->base.dispose_fn = dispose_fn;
+ list->base.allow_duplicates = allow_duplicates;
+#if WITH_HASHTABLE
+ {
+ size_t estimate = xsum (count, count / 2); /* 1.5 * count */
+ if (estimate < 10)
+ estimate = 10;
+ list->table_size = next_prime (estimate);
+ if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
+ goto fail1;
+ list->table =
+ (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
+ if (list->table == NULL)
+ goto fail1;
+ }
+#endif
+ if (count > 0)
+ {
+ /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
+ upper bh levels are black, and only the partially present lowest
+ level is red. */
+ unsigned int bh;
+ {
+ size_t n;
+ for (n = count + 1, bh = 0; n > 1; n = n >> 1)
+ bh++;
+ }
+
+ list->root = create_subtree_with_contents (bh, count, contents);
+ if (list->root == NULL)
+ goto fail2;
+ list->root->parent = NULL;
+
+#if WITH_HASHTABLE
+ /* Now that the tree is built, node_position() works. Now we can
+ add the nodes to the hash table. */
+ if (add_nodes_to_buckets (list) < 0)
+ goto fail3;
+#endif
+ }
+ else
+ list->root = NULL;
+
+ return list;
+
+#if WITH_HASHTABLE
+ fail3:
+ free_subtree (list->root);
+#endif
+ fail2:
+#if WITH_HASHTABLE
+ free (list->table);
+ fail1:
+#endif
+ free (list);
+ return NULL;
+}
+
+/* Rotate left a subtree.
+
+ B D
+ / \ / \
+ A D --> B E
+ / \ / \
+ C E A C
+
+ Change the tree structure, update the branch sizes.
+ The caller must update the colors and register D as child of its parent. */
+static gl_list_node_t
+rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
+{
+ gl_list_node_t a_node = b_node->left;
+ gl_list_node_t c_node = d_node->left;
+ gl_list_node_t e_node = d_node->right;
+
+ b_node->right = c_node;
+ d_node->left = b_node;
+
+ d_node->parent = b_node->parent;
+ b_node->parent = d_node;
+ if (c_node != NULL)
+ c_node->parent = b_node;
+
+ b_node->branch_size =
+ (a_node != NULL ? a_node->branch_size : 0)
+ + 1 + (c_node != NULL ? c_node->branch_size : 0);
+ d_node->branch_size =
+ b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
+
+ return d_node;
+}
+
+/* Rotate right a subtree.
+
+ D B
+ / \ / \
+ B E --> A D
+ / \ / \
+ A C C E
+
+ Change the tree structure, update the branch sizes.
+ The caller must update the colors and register B as child of its parent. */
+static gl_list_node_t
+rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
+{
+ gl_list_node_t a_node = b_node->left;
+ gl_list_node_t c_node = b_node->right;
+ gl_list_node_t e_node = d_node->right;
+
+ d_node->left = c_node;
+ b_node->right = d_node;
+
+ b_node->parent = d_node->parent;
+ d_node->parent = b_node;
+ if (c_node != NULL)
+ c_node->parent = d_node;
+
+ d_node->branch_size =
+ (c_node != NULL ? c_node->branch_size : 0)
+ + 1 + (e_node != NULL ? e_node->branch_size : 0);
+ b_node->branch_size =
+ (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
+
+ return b_node;
+}
+
+/* Ensure the tree is balanced, after an insertion operation.
+ Also assigns node->color.
+ parent is the given node's parent, known to be non-NULL. */
+static void
+rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
+{
+ for (;;)
+ {
+ /* At this point, parent = node->parent != NULL.
+ Think of node->color being RED (although node->color is not yet
+ assigned.) */
+ gl_list_node_t grandparent;
+ gl_list_node_t uncle;
+
+ if (parent->color == BLACK)
+ {
+ /* A RED color for node is acceptable. */
+ node->color = RED;
+ return;
+ }
+
+ grandparent = parent->parent;
+ /* Since parent is RED, we know that
+ grandparent is != NULL and colored BLACK. */
+
+ if (grandparent->left == parent)
+ uncle = grandparent->right;
+ else if (grandparent->right == parent)
+ uncle = grandparent->left;
+ else
+ abort ();
+
+ if (uncle != NULL && uncle->color == RED)
+ {
+ /* Change grandparent from BLACK to RED, and
+ change parent and uncle from RED to BLACK.
+ This makes it acceptable for node to be RED. */
+ node->color = RED;
+ parent->color = uncle->color = BLACK;
+ node = grandparent;
+ }
+ else
+ {
+ /* grandparent and uncle are BLACK. parent is RED. node wants
+ to be RED too.
+ In this case, recoloring is not sufficient. Need to perform
+ one or two rotations. */
+ gl_list_node_t *grandparentp;
+
+ if (grandparent->parent == NULL)
+ grandparentp = &list->root;
+ else if (grandparent->parent->left == grandparent)
+ grandparentp = &grandparent->parent->left;
+ else if (grandparent->parent->right == grandparent)
+ grandparentp = &grandparent->parent->right;
+ else
+ abort ();
+
+ if (grandparent->left == parent)
+ {
+ if (parent->right == node)
+ {
+ /* Rotation between node and parent. */
+ grandparent->left = rotate_left (parent, node);
+ node = parent;
+ parent = grandparent->left;
+ }
+ /* grandparent and uncle are BLACK. parent and node want to be
+ RED. parent = grandparent->left. node = parent->left.
+
+ grandparent parent
+ bh+1 bh+1
+ / \ / \
+ parent uncle --> node grandparent
+ bh bh bh bh
+ / \ / \
+ node C C uncle
+ bh bh bh bh
+ */
+ *grandparentp = rotate_right (parent, grandparent);
+ parent->color = BLACK;
+ node->color = grandparent->color = RED;
+ }
+ else /* grandparent->right == parent */
+ {
+ if (parent->left == node)
+ {
+ /* Rotation between node and parent. */
+ grandparent->right = rotate_right (node, parent);
+ node = parent;
+ parent = grandparent->right;
+ }
+ /* grandparent and uncle are BLACK. parent and node want to be
+ RED. parent = grandparent->right. node = parent->right.
+
+ grandparent parent
+ bh+1 bh+1
+ / \ / \
+ uncle parent --> grandparent node
+ bh bh bh bh
+ / \ / \
+ C node uncle C
+ bh bh bh bh
+ */
+ *grandparentp = rotate_left (grandparent, parent);
+ parent->color = BLACK;
+ node->color = grandparent->color = RED;
+ }
+ return;
+ }
+
+ /* Start again with a new (node, parent) pair. */
+ parent = node->parent;
+
+ if (parent == NULL)
+ {
+ /* Change node's color from RED to BLACK. This increases the
+ tree's black-height. */
+ node->color = BLACK;
+ return;
+ }
+ }
+}
+
+/* Ensure the tree is balanced, after a deletion operation.
+ CHILD was a grandchild of PARENT and is now its child. Between them,
+ a black node was removed. CHILD is also black, or NULL.
+ (CHILD can also be NULL. But PARENT is non-NULL.) */
+static void
+rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
+{
+ for (;;)
+ {
+ /* At this point, we reduced the black-height of the CHILD subtree by 1.
+ To make up, either look for a possibility to turn a RED to a BLACK
+ node, or try to reduce the black-height tree of CHILD's sibling
+ subtree as well. */
+ gl_list_node_t *parentp;
+
+ if (parent->parent == NULL)
+ parentp = &list->root;
+ else if (parent->parent->left == parent)
+ parentp = &parent->parent->left;
+ else if (parent->parent->right == parent)
+ parentp = &parent->parent->right;
+ else
+ abort ();
+
+ if (parent->left == child)
+ {
+ gl_list_node_t sibling = parent->right;
+ /* sibling's black-height is >= 1. In particular,
+ sibling != NULL.
+
+ parent
+ / \
+ child sibling
+ bh bh+1
+ */
+
+ if (sibling->color == RED)
+ {
+ /* sibling is RED, hence parent is BLACK and sibling's children
+ are non-NULL and BLACK.
+
+ parent sibling
+ bh+2 bh+2
+ / \ / \
+ child sibling --> parent SR
+ bh bh+1 bh+1 bh+1
+ / \ / \
+ SL SR child SL
+ bh+1 bh+1 bh bh+1
+ */
+ *parentp = rotate_left (parent, sibling);
+ parent->color = RED;
+ sibling->color = BLACK;
+
+ /* Concentrate on the subtree of parent. The new sibling is
+ one of the old sibling's children, and known to be BLACK. */
+ parentp = &sibling->left;
+ sibling = parent->right;
+ }
+ /* Now we know that sibling is BLACK.
+
+ parent
+ / \
+ child sibling
+ bh bh+1
+ */
+ if (sibling->right != NULL && sibling->right->color == RED)
+ {
+ /*
+ parent sibling
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ child sibling --> parent SR
+ bh bh+1 bh+1 bh+1
+ / \ / \
+ SL SR child SL
+ bh bh bh bh
+ */
+ *parentp = rotate_left (parent, sibling);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->right->color = BLACK;
+ return;
+ }
+ else if (sibling->left != NULL && sibling->left->color == RED)
+ {
+ /*
+ parent parent
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ child sibling --> child SL
+ bh bh+1 bh bh+1
+ / \ / \
+ SL SR SLL sibling
+ bh bh bh bh
+ / \ / \
+ SLL SLR SLR SR
+ bh bh bh bh
+
+ where SLL, SLR, SR are all black.
+ */
+ parent->right = rotate_right (sibling->left, sibling);
+ /* Change sibling from BLACK to RED and SL from RED to BLACK. */
+ sibling->color = RED;
+ sibling = parent->right;
+ sibling->color = BLACK;
+
+ /* Now do as in the previous case. */
+ *parentp = rotate_left (parent, sibling);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->right->color = BLACK;
+ return;
+ }
+ else
+ {
+ if (parent->color == BLACK)
+ {
+ /* Change sibling from BLACK to RED. Then the entire
+ subtree at parent has decreased its black-height.
+ parent parent
+ bh+2 bh+1
+ / \ / \
+ child sibling --> child sibling
+ bh bh+1 bh bh
+ */
+ sibling->color = RED;
+
+ child = parent;
+ }
+ else
+ {
+ /* Change parent from RED to BLACK, but compensate by
+ changing sibling from BLACK to RED.
+ parent parent
+ bh+1 bh+1
+ / \ / \
+ child sibling --> child sibling
+ bh bh+1 bh bh
+ */
+ parent->color = BLACK;
+ sibling->color = RED;
+ return;
+ }
+ }
+ }
+ else if (parent->right == child)
+ {
+ gl_list_node_t sibling = parent->left;
+ /* sibling's black-height is >= 1. In particular,
+ sibling != NULL.
+
+ parent
+ / \
+ sibling child
+ bh+1 bh
+ */
+
+ if (sibling->color == RED)
+ {
+ /* sibling is RED, hence parent is BLACK and sibling's children
+ are non-NULL and BLACK.
+
+ parent sibling
+ bh+2 bh+2
+ / \ / \
+ sibling child --> SR parent
+ bh+1 ch bh+1 bh+1
+ / \ / \
+ SL SR SL child
+ bh+1 bh+1 bh+1 bh
+ */
+ *parentp = rotate_right (sibling, parent);
+ parent->color = RED;
+ sibling->color = BLACK;
+
+ /* Concentrate on the subtree of parent. The new sibling is
+ one of the old sibling's children, and known to be BLACK. */
+ parentp = &sibling->right;
+ sibling = parent->left;
+ }
+ /* Now we know that sibling is BLACK.
+
+ parent
+ / \
+ sibling child
+ bh+1 bh
+ */
+ if (sibling->left != NULL && sibling->left->color == RED)
+ {
+ /*
+ parent sibling
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ sibling child --> SL parent
+ bh+1 bh bh+1 bh+1
+ / \ / \
+ SL SR SR child
+ bh bh bh bh
+ */
+ *parentp = rotate_right (sibling, parent);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->left->color = BLACK;
+ return;
+ }
+ else if (sibling->right != NULL && sibling->right->color == RED)
+ {
+ /*
+ parent parent
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ sibling child --> SR child
+ bh+1 bh bh+1 bh
+ / \ / \
+ SL SR sibling SRR
+ bh bh bh bh
+ / \ / \
+ SRL SRR SL SRL
+ bh bh bh bh
+
+ where SL, SRL, SRR are all black.
+ */
+ parent->left = rotate_left (sibling, sibling->right);
+ /* Change sibling from BLACK to RED and SL from RED to BLACK. */
+ sibling->color = RED;
+ sibling = parent->left;
+ sibling->color = BLACK;
+
+ /* Now do as in the previous case. */
+ *parentp = rotate_right (sibling, parent);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->left->color = BLACK;
+ return;
+ }
+ else
+ {
+ if (parent->color == BLACK)
+ {
+ /* Change sibling from BLACK to RED. Then the entire
+ subtree at parent has decreased its black-height.
+ parent parent
+ bh+2 bh+1
+ / \ / \
+ sibling child --> sibling child
+ bh+1 bh bh bh
+ */
+ sibling->color = RED;
+
+ child = parent;
+ }
+ else
+ {
+ /* Change parent from RED to BLACK, but compensate by
+ changing sibling from BLACK to RED.
+ parent parent
+ bh+1 bh+1
+ / \ / \
+ sibling child --> sibling child
+ bh+1 bh bh bh
+ */
+ parent->color = BLACK;
+ sibling->color = RED;
+ return;
+ }
+ }
+ }
+ else
+ abort ();
+
+ /* Start again with a new (child, parent) pair. */
+ parent = child->parent;
+
+#if 0 /* Already handled. */
+ if (child != NULL && child->color == RED)
+ {
+ child->color = BLACK;
+ return;
+ }
+#endif
+
+ if (parent == NULL)
+ return;
+ }
+}
+
+static void
+gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
+{
+ gl_list_node_t parent = node->parent;
+
+ if (node->left == NULL)
+ {
+ /* Replace node with node->right. */
+ gl_list_node_t child = node->right;
+
+ if (child != NULL)
+ {
+ child->parent = parent;
+ /* Since node->left == NULL, child must be RED and of height 1,
+ hence node must have been BLACK. Recolor the child. */
+ child->color = BLACK;
+ }
+ if (parent == NULL)
+ list->root = child;
+ else
+ {
+ if (parent->left == node)
+ parent->left = child;
+ else /* parent->right == node */
+ parent->right = child;
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = parent; p != NULL; p = p->parent)
+ p->branch_size--;
+ }
+
+ if (child == NULL && node->color == BLACK)
+ rebalance_after_remove (list, child, parent);
+ }
+ }
+ else if (node->right == NULL)
+ {
+ /* It is not absolutely necessary to treat this case. But the more
+ general case below is more complicated, hence slower. */
+ /* Replace node with node->left. */
+ gl_list_node_t child = node->left;
+
+ child->parent = parent;
+ /* Since node->right == NULL, child must be RED and of height 1,
+ hence node must have been BLACK. Recolor the child. */
+ child->color = BLACK;
+ if (parent == NULL)
+ list->root = child;
+ else
+ {
+ if (parent->left == node)
+ parent->left = child;
+ else /* parent->right == node */
+ parent->right = child;
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = parent; p != NULL; p = p->parent)
+ p->branch_size--;
+ }
+ }
+ }
+ else
+ {
+ /* Replace node with the rightmost element of the node->left subtree. */
+ gl_list_node_t subst;
+ gl_list_node_t subst_parent;
+ gl_list_node_t child;
+ color_t removed_color;
+
+ for (subst = node->left; subst->right != NULL; )
+ subst = subst->right;
+
+ subst_parent = subst->parent;
+
+ child = subst->left;
+
+ removed_color = subst->color;
+
+ /* The case subst_parent == node is special: If we do nothing special,
+ we get confusion about node->left, subst->left and child->parent.
+ subst_parent == node
+ <==> The 'for' loop above terminated immediately.
+ <==> subst == subst_parent->left
+ [otherwise subst == subst_parent->right]
+ In this case, we would need to first set
+ child->parent = node; node->left = child;
+ and later - when we copy subst into node's position - again
+ child->parent = subst; subst->left = child;
+ Altogether a no-op. */
+ if (subst_parent != node)
+ {
+ if (child != NULL)
+ child->parent = subst_parent;
+ subst_parent->right = child;
+ }
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = subst_parent; p != NULL; p = p->parent)
+ p->branch_size--;
+ }
+
+ /* Copy subst into node's position.
+ (This is safer than to copy subst's value into node, keep node in
+ place, and free subst.) */
+ if (subst_parent != node)
+ {
+ subst->left = node->left;
+ subst->left->parent = subst;
+ }
+ subst->right = node->right;
+ subst->right->parent = subst;
+ subst->color = node->color;
+ subst->branch_size = node->branch_size;
+ subst->parent = parent;
+ if (parent == NULL)
+ list->root = subst;
+ else if (parent->left == node)
+ parent->left = subst;
+ else /* parent->right == node */
+ parent->right = subst;
+
+ if (removed_color == BLACK)
+ {
+ if (child != NULL && child->color == RED)
+ /* Recolor the child. */
+ child->color = BLACK;
+ else
+ /* Rebalancing starts at child's parent, that is subst_parent -
+ except when subst_parent == node. In this case, we need to use
+ its replacement, subst. */
+ rebalance_after_remove (list, child,
+ subst_parent != node ? subst_parent : subst);
+ }
+ }
+}
+
+static gl_list_node_t
+gl_tree_nx_add_first (gl_list_t list, const void *elt)
+{
+ /* Create new node. */
+ gl_list_node_t new_node =
+ (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+ if (new_node == NULL)
+ return NULL;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+ new_node->branch_size = 1;
+ new_node->value = elt;
+#if WITH_HASHTABLE
+ new_node->h.hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (new_node->value)
+ : (size_t)(uintptr_t) new_node->value);
+#endif
+
+ /* Add it to the tree. */
+ if (list->root == NULL)
+ {
+ new_node->color = BLACK;
+ list->root = new_node;
+ new_node->parent = NULL;
+ }
+ else
+ {
+ gl_list_node_t node;
+
+ for (node = list->root; node->left != NULL; )
+ node = node->left;
+
+ node->left = new_node;
+ new_node->parent = node;
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = node; p != NULL; p = p->parent)
+ p->branch_size++;
+ }
+
+ /* Color and rebalance. */
+ rebalance_after_add (list, new_node, node);
+ }
+
+#if WITH_HASHTABLE
+ /* Add node to the hash table.
+ Note that this is only possible _after_ the node has been added to the
+ tree structure, because add_to_bucket() uses node_position(). */
+ if (add_to_bucket (list, new_node) < 0)
+ {
+ gl_tree_remove_node_from_tree (list, new_node);
+ free (new_node);
+ return NULL;
+ }
+ hash_resize_after_add (list);
+#endif
+
+ return new_node;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_last (gl_list_t list, const void *elt)
+{
+ /* Create new node. */
+ gl_list_node_t new_node =
+ (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+ if (new_node == NULL)
+ return NULL;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+ new_node->branch_size = 1;
+ new_node->value = elt;
+#if WITH_HASHTABLE
+ new_node->h.hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (new_node->value)
+ : (size_t)(uintptr_t) new_node->value);
+#endif
+
+ /* Add it to the tree. */
+ if (list->root == NULL)
+ {
+ new_node->color = BLACK;
+ list->root = new_node;
+ new_node->parent = NULL;
+ }
+ else
+ {
+ gl_list_node_t node;
+
+ for (node = list->root; node->right != NULL; )
+ node = node->right;
+
+ node->right = new_node;
+ new_node->parent = node;
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = node; p != NULL; p = p->parent)
+ p->branch_size++;
+ }
+
+ /* Color and rebalance. */
+ rebalance_after_add (list, new_node, node);
+ }
+
+#if WITH_HASHTABLE
+ /* Add node to the hash table.
+ Note that this is only possible _after_ the node has been added to the
+ tree structure, because add_to_bucket() uses node_position(). */
+ if (add_to_bucket (list, new_node) < 0)
+ {
+ gl_tree_remove_node_from_tree (list, new_node);
+ free (new_node);
+ return NULL;
+ }
+ hash_resize_after_add (list);
+#endif
+
+ return new_node;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+ /* Create new node. */
+ gl_list_node_t new_node =
+ (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+ if (new_node == NULL)
+ return NULL;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+ new_node->branch_size = 1;
+ new_node->value = elt;
+#if WITH_HASHTABLE
+ new_node->h.hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (new_node->value)
+ : (size_t)(uintptr_t) new_node->value);
+#endif
+
+ /* Add it to the tree. */
+ if (node->left == NULL)
+ node->left = new_node;
+ else
+ {
+ for (node = node->left; node->right != NULL; )
+ node = node->right;
+ node->right = new_node;
+ }
+ new_node->parent = node;
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = node; p != NULL; p = p->parent)
+ p->branch_size++;
+ }
+
+ /* Color and rebalance. */
+ rebalance_after_add (list, new_node, node);
+
+#if WITH_HASHTABLE
+ /* Add node to the hash table.
+ Note that this is only possible _after_ the node has been added to the
+ tree structure, because add_to_bucket() uses node_position(). */
+ if (add_to_bucket (list, new_node) < 0)
+ {
+ gl_tree_remove_node_from_tree (list, new_node);
+ free (new_node);
+ return NULL;
+ }
+ hash_resize_after_add (list);
+#endif
+
+ return new_node;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+ /* Create new node. */
+ gl_list_node_t new_node =
+ (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+ if (new_node == NULL)
+ return NULL;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+ new_node->branch_size = 1;
+ new_node->value = elt;
+#if WITH_HASHTABLE
+ new_node->h.hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (new_node->value)
+ : (size_t)(uintptr_t) new_node->value);
+#endif
+
+ /* Add it to the tree. */
+ if (node->right == NULL)
+ node->right = new_node;
+ else
+ {
+ for (node = node->right; node->left != NULL; )
+ node = node->left;
+ node->left = new_node;
+ }
+ new_node->parent = node;
+
+ /* Update branch_size fields of the parent nodes. */
+ {
+ gl_list_node_t p;
+
+ for (p = node; p != NULL; p = p->parent)
+ p->branch_size++;
+ }
+
+ /* Color and rebalance. */
+ rebalance_after_add (list, new_node, node);
+
+#if WITH_HASHTABLE
+ /* Add node to the hash table.
+ Note that this is only possible _after_ the node has been added to the
+ tree structure, because add_to_bucket() uses node_position(). */
+ if (add_to_bucket (list, new_node) < 0)
+ {
+ gl_tree_remove_node_from_tree (list, new_node);
+ free (new_node);
+ return NULL;
+ }
+ hash_resize_after_add (list);
+#endif
+
+ return new_node;
+}
diff --git a/draft/mcastseed/lib/gl_anytree_list1.h b/draft/mcastseed/lib/gl_anytree_list1.h
new file mode 100644
index 0000000..675f107
--- /dev/null
+++ b/draft/mcastseed/lib/gl_anytree_list1.h
@@ -0,0 +1,41 @@
+/* Sequential list data type implemented by a binary tree.
+ Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
+ gl_avltreehash_list.c, gl_rbtreehash_list.c. */
+
+/* An item on the stack used for iterating across the elements. */
+typedef struct
+{
+ gl_list_node_t node;
+ size_t rightp;
+} iterstack_item_t;
+
+/* A stack used for iterating across the elements. */
+typedef iterstack_item_t iterstack_t[MAXHEIGHT];
+
+/* Free a non-empty subtree recursively.
+ This function is recursive and therefore not very fast. */
+static void
+free_subtree (gl_list_node_t node)
+{
+ if (node->left != NULL)
+ free_subtree (node->left);
+ if (node->right != NULL)
+ free_subtree (node->right);
+ free (node);
+}
diff --git a/draft/mcastseed/lib/gl_anytree_list2.h b/draft/mcastseed/lib/gl_anytree_list2.h
new file mode 100644
index 0000000..7e6fe45
--- /dev/null
+++ b/draft/mcastseed/lib/gl_anytree_list2.h
@@ -0,0 +1,940 @@
+/* Sequential list data type implemented by a binary tree.
+ Copyright (C) 2006-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
+ gl_avltreehash_list.c, gl_rbtreehash_list.c. */
+
+static gl_list_t
+gl_tree_nx_create_empty (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates)
+{
+ struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+ if (list == NULL)
+ return NULL;
+
+ list->base.vtable = implementation;
+ list->base.equals_fn = equals_fn;
+ list->base.hashcode_fn = hashcode_fn;
+ list->base.dispose_fn = dispose_fn;
+ list->base.allow_duplicates = allow_duplicates;
+#if WITH_HASHTABLE
+ list->table_size = 11;
+ list->table =
+ (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
+ if (list->table == NULL)
+ goto fail;
+#endif
+ list->root = NULL;
+
+ return list;
+
+#if WITH_HASHTABLE
+ fail:
+ free (list);
+ return NULL;
+#endif
+}
+
+static size_t
+gl_tree_size (gl_list_t list)
+{
+ return (list->root != NULL ? list->root->branch_size : 0);
+}
+
+static const void *
+gl_tree_node_value (gl_list_t list, gl_list_node_t node)
+{
+ return node->value;
+}
+
+static int
+gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+#if WITH_HASHTABLE
+ if (elt != node->value)
+ {
+ size_t new_hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+
+ if (new_hashcode != node->h.hashcode)
+ {
+ remove_from_bucket (list, node);
+ node->value = elt;
+ node->h.hashcode = new_hashcode;
+ if (add_to_bucket (list, node) < 0)
+ {
+ /* Out of memory. We removed node from a bucket but cannot add
+ it to another bucket. In order to avoid inconsistencies, we
+ must remove node entirely from the list. */
+ gl_tree_remove_node_from_tree (list, node);
+ free (node);
+ return -1;
+ }
+ }
+ else
+ node->value = elt;
+ }
+#else
+ node->value = elt;
+#endif
+ return 0;
+}
+
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_tree_next_node (gl_list_t list, gl_list_node_t node)
+{
+ if (node->right != NULL)
+ {
+ node = node->right;
+ while (node->left != NULL)
+ node = node->left;
+ }
+ else
+ {
+ while (node->parent != NULL && node->parent->right == node)
+ node = node->parent;
+ node = node->parent;
+ }
+ return node;
+}
+
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
+{
+ if (node->left != NULL)
+ {
+ node = node->left;
+ while (node->right != NULL)
+ node = node->right;
+ }
+ else
+ {
+ while (node->parent != NULL && node->parent->left == node)
+ node = node->parent;
+ node = node->parent;
+ }
+ return node;
+}
+
+/* Return the node at the given position < gl_tree_size (list). */
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+node_at (gl_list_node_t root, size_t position)
+{
+ /* Here we know that root != NULL. */
+ gl_list_node_t node = root;
+
+ for (;;)
+ {
+ if (node->left != NULL)
+ {
+ if (position < node->left->branch_size)
+ {
+ node = node->left;
+ continue;
+ }
+ position -= node->left->branch_size;
+ }
+ if (position == 0)
+ break;
+ position--;
+ node = node->right;
+ }
+ return node;
+}
+
+static const void * _GL_ATTRIBUTE_PURE
+gl_tree_get_at (gl_list_t list, size_t position)
+{
+ gl_list_node_t node = list->root;
+
+ if (!(node != NULL && position < node->branch_size))
+ /* Invalid argument. */
+ abort ();
+ node = node_at (node, position);
+ return node->value;
+}
+
+static gl_list_node_t
+gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt)
+{
+ gl_list_node_t node = list->root;
+
+ if (!(node != NULL && position < node->branch_size))
+ /* Invalid argument. */
+ abort ();
+ node = node_at (node, position);
+#if WITH_HASHTABLE
+ if (elt != node->value)
+ {
+ size_t new_hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+
+ if (new_hashcode != node->h.hashcode)
+ {
+ remove_from_bucket (list, node);
+ node->value = elt;
+ node->h.hashcode = new_hashcode;
+ if (add_to_bucket (list, node) < 0)
+ {
+ /* Out of memory. We removed node from a bucket but cannot add
+ it to another bucket. In order to avoid inconsistencies, we
+ must remove node entirely from the list. */
+ gl_tree_remove_node_from_tree (list, node);
+ free (node);
+ return NULL;
+ }
+ }
+ else
+ node->value = elt;
+ }
+#else
+ node->value = elt;
+#endif
+ return node;
+}
+
+#if !WITH_HASHTABLE
+
+static gl_list_node_t
+gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
+{
+ if (!(start_index <= end_index
+ && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+ {
+ gl_listelement_equals_fn equals = list->base.equals_fn;
+ /* Iterate across all elements. */
+ gl_list_node_t node = list->root;
+ iterstack_t stack;
+ iterstack_item_t *stack_ptr = &stack[0];
+ size_t index = 0;
+
+ if (start_index == 0)
+ {
+ /* Consider all elements. */
+ for (;;)
+ {
+ /* Descend on left branch. */
+ for (;;)
+ {
+ if (node == NULL)
+ break;
+ stack_ptr->node = node;
+ stack_ptr->rightp = 0;
+ node = node->left;
+ stack_ptr++;
+ }
+ /* Climb up again. */
+ for (;;)
+ {
+ if (stack_ptr == &stack[0])
+ return NULL;
+ stack_ptr--;
+ if (!stack_ptr->rightp)
+ break;
+ }
+ node = stack_ptr->node;
+ /* Test against current element. */
+ if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+ return node;
+ index++;
+ if (index >= end_index)
+ return NULL;
+ /* Descend on right branch. */
+ stack_ptr->rightp = 1;
+ node = node->right;
+ stack_ptr++;
+ }
+ }
+ else
+ {
+ /* Consider only elements at indices >= start_index.
+ In this case, rightp contains the difference between the start_index
+ for the parent node and the one for the child node (0 when the child
+ node is the parent's left child, > 0 when the child is the parent's
+ right child). */
+ for (;;)
+ {
+ /* Descend on left branch. */
+ for (;;)
+ {
+ if (node == NULL)
+ break;
+ if (node->branch_size <= start_index)
+ break;
+ stack_ptr->node = node;
+ stack_ptr->rightp = 0;
+ node = node->left;
+ stack_ptr++;
+ }
+ /* Climb up again. */
+ for (;;)
+ {
+ if (stack_ptr == &stack[0])
+ return NULL;
+ stack_ptr--;
+ if (!stack_ptr->rightp)
+ break;
+ start_index += stack_ptr->rightp;
+ }
+ node = stack_ptr->node;
+ {
+ size_t left_branch_size1 =
+ (node->left != NULL ? node->left->branch_size : 0) + 1;
+ if (start_index < left_branch_size1)
+ {
+ /* Test against current element. */
+ if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+ return node;
+ /* Now that we have considered all indices < left_branch_size1,
+ we can increment start_index. */
+ start_index = left_branch_size1;
+ }
+ index++;
+ if (index >= end_index)
+ return NULL;
+ /* Descend on right branch. */
+ start_index -= left_branch_size1;
+ stack_ptr->rightp = left_branch_size1;
+ }
+ node = node->right;
+ stack_ptr++;
+ }
+ }
+ }
+}
+
+static size_t
+gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
+{
+ if (!(start_index <= end_index
+ && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+ {
+ gl_listelement_equals_fn equals = list->base.equals_fn;
+ /* Iterate across all elements. */
+ gl_list_node_t node = list->root;
+ iterstack_t stack;
+ iterstack_item_t *stack_ptr = &stack[0];
+ size_t index = 0;
+
+ if (start_index == 0)
+ {
+ /* Consider all elements. */
+ for (;;)
+ {
+ /* Descend on left branch. */
+ for (;;)
+ {
+ if (node == NULL)
+ break;
+ stack_ptr->node = node;
+ stack_ptr->rightp = 0;
+ node = node->left;
+ stack_ptr++;
+ }
+ /* Climb up again. */
+ for (;;)
+ {
+ if (stack_ptr == &stack[0])
+ return (size_t)(-1);
+ stack_ptr--;
+ if (!stack_ptr->rightp)
+ break;
+ }
+ node = stack_ptr->node;
+ /* Test against current element. */
+ if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+ return index;
+ index++;
+ if (index >= end_index)
+ return (size_t)(-1);
+ /* Descend on right branch. */
+ stack_ptr->rightp = 1;
+ node = node->right;
+ stack_ptr++;
+ }
+ }
+ else
+ {
+ /* Consider only elements at indices >= start_index.
+ In this case, rightp contains the difference between the start_index
+ for the parent node and the one for the child node (0 when the child
+ node is the parent's left child, > 0 when the child is the parent's
+ right child). */
+ for (;;)
+ {
+ /* Descend on left branch. */
+ for (;;)
+ {
+ if (node == NULL)
+ break;
+ if (node->branch_size <= start_index)
+ break;
+ stack_ptr->node = node;
+ stack_ptr->rightp = 0;
+ node = node->left;
+ stack_ptr++;
+ }
+ /* Climb up again. */
+ for (;;)
+ {
+ if (stack_ptr == &stack[0])
+ return (size_t)(-1);
+ stack_ptr--;
+ if (!stack_ptr->rightp)
+ break;
+ start_index += stack_ptr->rightp;
+ }
+ node = stack_ptr->node;
+ {
+ size_t left_branch_size1 =
+ (node->left != NULL ? node->left->branch_size : 0) + 1;
+ if (start_index < left_branch_size1)
+ {
+ /* Test against current element. */
+ if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+ return index;
+ /* Now that we have considered all indices < left_branch_size1,
+ we can increment start_index. */
+ start_index = left_branch_size1;
+ }
+ index++;
+ if (index >= end_index)
+ return (size_t)(-1);
+ /* Descend on right branch. */
+ start_index -= left_branch_size1;
+ stack_ptr->rightp = left_branch_size1;
+ }
+ node = node->right;
+ stack_ptr++;
+ }
+ }
+ }
+}
+
+#endif
+
+static gl_list_node_t
+gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt)
+{
+ size_t count = (list->root != NULL ? list->root->branch_size : 0);
+
+ if (!(position <= count))
+ /* Invalid argument. */
+ abort ();
+ if (position == count)
+ return gl_tree_nx_add_last (list, elt);
+ else
+ return gl_tree_nx_add_before (list, node_at (list->root, position), elt);
+}
+
+static bool
+gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
+{
+#if WITH_HASHTABLE
+ /* Remove node from the hash table.
+ Note that this is only possible _before_ the node is removed from the
+ tree structure, because remove_from_bucket() uses node_position(). */
+ remove_from_bucket (list, node);
+#endif
+
+ gl_tree_remove_node_from_tree (list, node);
+
+ if (list->base.dispose_fn != NULL)
+ list->base.dispose_fn (node->value);
+ free (node);
+ return true;
+}
+
+static bool
+gl_tree_remove_at (gl_list_t list, size_t position)
+{
+ gl_list_node_t node = list->root;
+
+ if (!(node != NULL && position < node->branch_size))
+ /* Invalid argument. */
+ abort ();
+ node = node_at (node, position);
+ return gl_tree_remove_node (list, node);
+}
+
+static bool
+gl_tree_remove (gl_list_t list, const void *elt)
+{
+ if (list->root != NULL)
+ {
+ gl_list_node_t node =
+ gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
+
+ if (node != NULL)
+ return gl_tree_remove_node (list, node);
+ }
+ return false;
+}
+
+#if !WITH_HASHTABLE
+
+static void
+gl_tree_list_free (gl_list_t list)
+{
+ /* Iterate across all elements in post-order. */
+ gl_list_node_t node = list->root;
+ iterstack_t stack;
+ iterstack_item_t *stack_ptr = &stack[0];
+
+ for (;;)
+ {
+ /* Descend on left branch. */
+ for (;;)
+ {
+ if (node == NULL)
+ break;
+ stack_ptr->node = node;
+ stack_ptr->rightp = false;
+ node = node->left;
+ stack_ptr++;
+ }
+ /* Climb up again. */
+ for (;;)
+ {
+ if (stack_ptr == &stack[0])
+ goto done_iterate;
+ stack_ptr--;
+ node = stack_ptr->node;
+ if (!stack_ptr->rightp)
+ break;
+ /* Free the current node. */
+ if (list->base.dispose_fn != NULL)
+ list->base.dispose_fn (node->value);
+ free (node);
+ }
+ /* Descend on right branch. */
+ stack_ptr->rightp = true;
+ node = node->right;
+ stack_ptr++;
+ }
+ done_iterate:
+ free (list);
+}
+
+#endif
+
+/* --------------------- gl_list_iterator_t Data Type --------------------- */
+
+static gl_list_iterator_t
+gl_tree_iterator (gl_list_t list)
+{
+ gl_list_iterator_t result;
+ gl_list_node_t node;
+
+ result.vtable = list->base.vtable;
+ result.list = list;
+ /* Start node is the leftmost node. */
+ node = list->root;
+ if (node != NULL)
+ while (node->left != NULL)
+ node = node->left;
+ result.p = node;
+ /* End point is past the rightmost node. */
+ result.q = NULL;
+#if defined GCC_LINT || defined lint
+ result.i = 0;
+ result.j = 0;
+ result.count = 0;
+#endif
+
+ return result;
+}
+
+static gl_list_iterator_t
+gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
+{
+ size_t count = (list->root != NULL ? list->root->branch_size : 0);
+ gl_list_iterator_t result;
+
+ if (!(start_index <= end_index && end_index <= count))
+ /* Invalid arguments. */
+ abort ();
+ result.vtable = list->base.vtable;
+ result.list = list;
+ /* Start node is the node at position start_index. */
+ result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
+ /* End point is the node at position end_index. */
+ result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
+#if defined GCC_LINT || defined lint
+ result.i = 0;
+ result.j = 0;
+ result.count = 0;
+#endif
+
+ return result;
+}
+
+static bool
+gl_tree_iterator_next (gl_list_iterator_t *iterator,
+ const void **eltp, gl_list_node_t *nodep)
+{
+ if (iterator->p != iterator->q)
+ {
+ gl_list_node_t node = (gl_list_node_t) iterator->p;
+ *eltp = node->value;
+ if (nodep != NULL)
+ *nodep = node;
+ /* Advance to the next node. */
+ if (node->right != NULL)
+ {
+ node = node->right;
+ while (node->left != NULL)
+ node = node->left;
+ }
+ else
+ {
+ while (node->parent != NULL && node->parent->right == node)
+ node = node->parent;
+ node = node->parent;
+ }
+ iterator->p = node;
+ return true;
+ }
+ else
+ return false;
+}
+
+static void
+gl_tree_iterator_free (gl_list_iterator_t *iterator)
+{
+}
+
+/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
+
+static gl_list_node_t
+gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+{
+ gl_list_node_t node;
+
+ for (node = list->root; node != NULL; )
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ node = node->right;
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost such
+ element. */
+ gl_list_node_t found = node;
+ node = node->left;
+ for (; node != NULL; )
+ {
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ node = node->right;
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found = node;
+ node = node->left;
+ }
+ }
+ return found;
+ }
+ }
+ return NULL;
+}
+
+static gl_list_node_t
+gl_tree_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ gl_list_node_t node;
+
+ if (!(low <= high
+ && high <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+
+ for (node = list->root; node != NULL; )
+ {
+ size_t left_branch_size =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size)
+ {
+ low -= left_branch_size + 1;
+ high -= left_branch_size + 1;
+ node = node->right;
+ }
+ else if (high <= left_branch_size)
+ node = node->left;
+ else
+ {
+ /* Here low <= left_branch_size < high. */
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ low = 0;
+ high -= left_branch_size + 1;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost
+ such element. */
+ gl_list_node_t found = node;
+ node = node->left;
+ for (; node != NULL; )
+ {
+ size_t left_branch_size2 =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size2)
+ {
+ low -= left_branch_size2 + 1;
+ node = node->right;
+ }
+ else
+ {
+ /* Here low <= left_branch_size2. */
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ low = 0;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found = node;
+ node = node->left;
+ }
+ }
+ }
+ return found;
+ }
+ }
+ }
+ return NULL;
+}
+
+static size_t
+gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+{
+ gl_list_node_t node;
+ size_t position;
+
+ for (node = list->root, position = 0; node != NULL; )
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ if (node->left != NULL)
+ position += node->left->branch_size;
+ position++;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost such
+ element. */
+ size_t found_position =
+ position + (node->left != NULL ? node->left->branch_size : 0);
+ node = node->left;
+ for (; node != NULL; )
+ {
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ if (node->left != NULL)
+ position += node->left->branch_size;
+ position++;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found_position =
+ position
+ + (node->left != NULL ? node->left->branch_size : 0);
+ node = node->left;
+ }
+ }
+ return found_position;
+ }
+ }
+ return (size_t)(-1);
+}
+
+static size_t
+gl_tree_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ gl_list_node_t node;
+ size_t position;
+
+ if (!(low <= high
+ && high <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+
+ for (node = list->root, position = 0; node != NULL; )
+ {
+ size_t left_branch_size =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size)
+ {
+ low -= left_branch_size + 1;
+ high -= left_branch_size + 1;
+ position += left_branch_size + 1;
+ node = node->right;
+ }
+ else if (high <= left_branch_size)
+ node = node->left;
+ else
+ {
+ /* Here low <= left_branch_size < high. */
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ low = 0;
+ high -= left_branch_size + 1;
+ position += left_branch_size + 1;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost
+ such element. */
+ size_t found_position =
+ position + (node->left != NULL ? node->left->branch_size : 0);
+ node = node->left;
+ for (; node != NULL; )
+ {
+ size_t left_branch_size2 =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size2)
+ {
+ low -= left_branch_size2 + 1;
+ node = node->right;
+ }
+ else
+ {
+ /* Here low <= left_branch_size2. */
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ position += left_branch_size2 + 1;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found_position = position + left_branch_size2;
+ node = node->left;
+ }
+ }
+ }
+ return found_position;
+ }
+ }
+ }
+ return (size_t)(-1);
+}
+
+static gl_list_node_t
+gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+{
+ gl_list_node_t node = list->root;
+
+ if (node == NULL)
+ return gl_tree_nx_add_first (list, elt);
+
+ for (;;)
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ if (node->right == NULL)
+ return gl_tree_nx_add_after (list, node, elt);
+ node = node->right;
+ }
+ else if (cmp > 0)
+ {
+ if (node->left == NULL)
+ return gl_tree_nx_add_before (list, node, elt);
+ node = node->left;
+ }
+ else /* cmp == 0 */
+ return gl_tree_nx_add_before (list, node, elt);
+ }
+}
+
+static bool
+gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+{
+ gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
+ if (node != NULL)
+ return gl_tree_remove_node (list, node);
+ else
+ return false;
+}
diff --git a/draft/mcastseed/lib/gl_list.c b/draft/mcastseed/lib/gl_list.c
new file mode 100644
index 0000000..8793298
--- /dev/null
+++ b/draft/mcastseed/lib/gl_list.c
@@ -0,0 +1,3 @@
+#include <config.h>
+#define GL_LIST_INLINE _GL_EXTERN_INLINE
+#include "gl_list.h"
diff --git a/draft/mcastseed/lib/gl_list.h b/draft/mcastseed/lib/gl_list.h
new file mode 100644
index 0000000..c9d05b0
--- /dev/null
+++ b/draft/mcastseed/lib/gl_list.h
@@ -0,0 +1,841 @@
+/* Abstract sequential list data type. -*- coding: utf-8 -*-
+ Copyright (C) 2006-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _GL_LIST_H
+#define _GL_LIST_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#ifndef _GL_INLINE_HEADER_BEGIN
+ #error "Please include config.h first."
+#endif
+_GL_INLINE_HEADER_BEGIN
+#ifndef GL_LIST_INLINE
+# define GL_LIST_INLINE _GL_INLINE
+#endif
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/* gl_list is an abstract list data type. It can contain any number of
+ objects ('void *' or 'const void *' pointers) in any given order.
+ Duplicates are allowed, but can optionally be forbidden.
+
+ There are several implementations of this list datatype, optimized for
+ different operations or for memory. You can start using the simplest list
+ implementation, GL_ARRAY_LIST, and switch to a different implementation
+ later, when you realize which operations are performed the most frequently.
+ The API of the different implementations is exactly the same; when
+ switching to a different implementation, you only have to change the
+ gl_list_create call.
+
+ The implementations are:
+ GL_ARRAY_LIST a growable array
+ GL_CARRAY_LIST a growable circular array
+ GL_LINKED_LIST a linked list
+ GL_AVLTREE_LIST a binary tree (AVL tree)
+ GL_RBTREE_LIST a binary tree (red-black tree)
+ GL_LINKEDHASH_LIST a hash table with a linked list
+ GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree)
+ GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree)
+
+ The memory consumption is asymptotically the same: O(1) for every object
+ in the list. When looking more closely at the average memory consumed
+ for an object, GL_ARRAY_LIST is the most compact representation, and
+ GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.
+
+ The guaranteed average performance of the operations is, for a list of
+ n elements:
+
+ Operation ARRAY LINKED TREE LINKEDHASH TREEHASH
+ CARRAY with|without with|without
+ duplicates duplicates
+
+ gl_list_size O(1) O(1) O(1) O(1) O(1)
+ gl_list_node_value O(1) O(1) O(1) O(1) O(1)
+ gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1)
+ gl_list_next_node O(1) O(1) O(log n) O(1) O(log n)
+ gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n)
+ gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
+ gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
+ gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
+ gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
+ gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
+ gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
+ gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
+ gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
+ gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
+ gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
+ gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
+ gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
+ gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
+ gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
+ gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
+ gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
+ gl_list_iterator O(1) O(1) O(log n) O(1) O(log n)
+ gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
+ gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
+ gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
+ gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
+ */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Type of function used to compare two elements.
+ NULL denotes pointer comparison. */
+typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
+
+/* Type of function used to compute a hash code.
+ NULL denotes a function that depends only on the pointer itself. */
+typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
+
+/* Type of function used to dispose an element once it's removed from a list.
+ NULL denotes a no-op. */
+typedef void (*gl_listelement_dispose_fn) (const void *elt);
+
+struct gl_list_impl;
+/* Type representing an entire list. */
+typedef struct gl_list_impl * gl_list_t;
+
+struct gl_list_node_impl;
+/* Type representing the position of an element in the list, in a way that
+ is more adapted to the list implementation than a plain index.
+ Note: It is invalidated by insertions and removals! */
+typedef struct gl_list_node_impl * gl_list_node_t;
+
+struct gl_list_implementation;
+/* Type representing a list datatype implementation. */
+typedef const struct gl_list_implementation * gl_list_implementation_t;
+
+#if 0 /* Unless otherwise specified, these are defined inline below. */
+
+/* Create an empty list.
+ IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
+ GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
+ GL_RBTREEHASH_LIST.
+ EQUALS_FN is an element comparison function or NULL.
+ HASHCODE_FN is an element hash code function or NULL.
+ DISPOSE_FN is an element disposal function or NULL.
+ ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
+ the list. The implementation may verify this at runtime. */
+/* declared in gl_xlist.h */
+extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates);
+
+/* Create a list with given contents.
+ IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
+ GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
+ GL_RBTREEHASH_LIST.
+ EQUALS_FN is an element comparison function or NULL.
+ HASHCODE_FN is an element hash code function or NULL.
+ DISPOSE_FN is an element disposal function or NULL.
+ ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
+ the list. The implementation may verify this at runtime.
+ COUNT is the number of initial elements.
+ CONTENTS[0..COUNT-1] is the initial contents. */
+/* declared in gl_xlist.h */
+extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates,
+ size_t count, const void **contents);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates,
+ size_t count, const void **contents);
+
+/* Return the current number of elements in a list. */
+extern size_t gl_list_size (gl_list_t list);
+
+/* Return the element value represented by a list node. */
+extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
+
+/* Replace the element value represented by a list node. */
+/* declared in gl_xlist.h */
+extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
+ const void *elt);
+/* Likewise. Return 0 upon success, -1 upon out-of-memory. */
+extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
+ const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Return the node immediately after the given node in the list, or NULL
+ if the given node is the last (rightmost) one in the list. */
+extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
+
+/* Return the node immediately before the given node in the list, or NULL
+ if the given node is the first (leftmost) one in the list. */
+extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
+
+/* Return the element at a given position in the list.
+ POSITION must be >= 0 and < gl_list_size (list). */
+extern const void * gl_list_get_at (gl_list_t list, size_t position);
+
+/* Replace the element at a given position in the list.
+ POSITION must be >= 0 and < gl_list_size (list).
+ Return its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
+ const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
+ const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Search whether an element is already in the list.
+ Return its node if found, or NULL if not present in the list. */
+extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
+
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX.
+ Return its node if found, or NULL if not present in the list. */
+extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
+ const void *elt);
+
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX and < END_INDEX.
+ Return its node if found, or NULL if not present in the list. */
+extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
+/* Search whether an element is already in the list.
+ Return its position if found, or (size_t)(-1) if not present in the list. */
+extern size_t gl_list_indexof (gl_list_t list, const void *elt);
+
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX.
+ Return its position if found, or (size_t)(-1) if not present in the list. */
+extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
+ const void *elt);
+
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX and < END_INDEX.
+ Return its position if found, or (size_t)(-1) if not present in the list. */
+extern size_t gl_list_indexof_from_to (gl_list_t list,
+ size_t start_index, size_t end_index,
+ const void *elt);
+
+/* Add an element as the first element of the list.
+ Return its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Add an element as the last element of the list.
+ Return its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Add an element before a given element node of the list.
+ Return its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
+ const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
+ gl_list_node_t node,
+ const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Add an element after a given element node of the list.
+ Return its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
+ const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
+ const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Add an element at a given position in the list.
+ POSITION must be >= 0 and <= gl_list_size (list). */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
+ const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
+ const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Remove an element from the list.
+ Return true. */
+extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
+
+/* Remove an element at a given position from the list.
+ POSITION must be >= 0 and < gl_list_size (list).
+ Return true. */
+extern bool gl_list_remove_at (gl_list_t list, size_t position);
+
+/* Search and remove an element from the list.
+ Return true if it was found and removed. */
+extern bool gl_list_remove (gl_list_t list, const void *elt);
+
+/* Free an entire list.
+ (But this call does not free the elements of the list.) */
+extern void gl_list_free (gl_list_t list);
+
+#endif /* End of inline and gl_xlist.h-defined functions. */
+
+/* --------------------- gl_list_iterator_t Data Type --------------------- */
+
+/* Functions for iterating through a list. */
+
+/* Type of an iterator that traverses a list.
+ This is a fixed-size struct, so that creation of an iterator doesn't need
+ memory allocation on the heap. */
+typedef struct
+{
+ /* For fast dispatch of gl_list_iterator_next. */
+ const struct gl_list_implementation *vtable;
+ /* For detecting whether the last returned element was removed. */
+ gl_list_t list;
+ size_t count;
+ /* Other, implementation-private fields. */
+ void *p; void *q;
+ size_t i; size_t j;
+} gl_list_iterator_t;
+
+#if 0 /* These are defined inline below. */
+
+/* Create an iterator traversing a list.
+ The list contents must not be modified while the iterator is in use,
+ except for replacing or removing the last returned element. */
+extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
+
+/* Create an iterator traversing the element with indices i,
+ start_index <= i < end_index, of a list.
+ The list contents must not be modified while the iterator is in use,
+ except for replacing or removing the last returned element. */
+extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
+ size_t start_index,
+ size_t end_index);
+
+/* If there is a next element, store the next element in *ELTP, store its
+ node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
+ Otherwise, return false. */
+extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
+ const void **eltp, gl_list_node_t *nodep);
+
+/* Free an iterator. */
+extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
+
+#endif /* End of inline functions. */
+
+/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
+
+/* The following functions are for lists without duplicates where the
+ order is given by a sort criterion. */
+
+/* Type of function used to compare two elements. Same as for qsort().
+ NULL denotes pointer comparison. */
+typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
+
+#if 0 /* Unless otherwise specified, these are defined inline below. */
+
+/* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
+ Return its node if found, or NULL if not present in the list.
+ If the list contains several copies of ELT, the node of the leftmost one is
+ returned. */
+extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+
+/* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
+ Only list elements with indices >= START_INDEX and < END_INDEX are
+ considered; the implementation uses these bounds to minimize the number
+ of COMPAR invocations.
+ Return its node if found, or NULL if not present in the list.
+ If the list contains several copies of ELT, the node of the leftmost one is
+ returned. */
+extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
+/* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
+ Return its position if found, or (size_t)(-1) if not present in the list.
+ If the list contains several copies of ELT, the position of the leftmost one
+ is returned. */
+extern size_t gl_sortedlist_indexof (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+
+/* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
+ Only list elements with indices >= START_INDEX and < END_INDEX are
+ considered; the implementation uses these bounds to minimize the number
+ of COMPAR invocations.
+ Return its position if found, or (size_t)(-1) if not present in the list.
+ If the list contains several copies of ELT, the position of the leftmost one
+ is returned. */
+extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
+/* Add an element at the appropriate position in the list.
+ The list is assumed to be sorted with COMPAR.
+ Return its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+/* Likewise. Return NULL upon out-of-memory. */
+extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Search and remove an element from the list.
+ The list is assumed to be sorted with COMPAR.
+ Return true if it was found and removed.
+ If the list contains several copies of ELT, only the leftmost one is
+ removed. */
+extern bool gl_sortedlist_remove (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+
+#endif /* End of inline and gl_xlist.h-defined functions. */
+
+/* ------------------------ Implementation Details ------------------------ */
+
+struct gl_list_implementation
+{
+ /* gl_list_t functions. */
+ gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates);
+ gl_list_t (*nx_create) (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates,
+ size_t count, const void **contents);
+ size_t (*size) (gl_list_t list);
+ const void * (*node_value) (gl_list_t list, gl_list_node_t node);
+ int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
+ const void *elt);
+ gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
+ gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
+ const void * (*get_at) (gl_list_t list, size_t position);
+ gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
+ const void *elt);
+ gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
+ size_t end_index, const void *elt);
+ size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
+ size_t end_index, const void *elt);
+ gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
+ gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
+ gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
+ const void *elt);
+ gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
+ const void *elt);
+ gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
+ const void *elt);
+ bool (*remove_node) (gl_list_t list, gl_list_node_t node);
+ bool (*remove_at) (gl_list_t list, size_t position);
+ bool (*remove_elt) (gl_list_t list, const void *elt);
+ void (*list_free) (gl_list_t list);
+ /* gl_list_iterator_t functions. */
+ gl_list_iterator_t (*iterator) (gl_list_t list);
+ gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
+ size_t start_index,
+ size_t end_index);
+ bool (*iterator_next) (gl_list_iterator_t *iterator,
+ const void **eltp, gl_list_node_t *nodep);
+ void (*iterator_free) (gl_list_iterator_t *iterator);
+ /* Sorted gl_list_t functions. */
+ gl_list_node_t (*sortedlist_search) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+ gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+ size_t (*sortedlist_indexof) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+ size_t (*sortedlist_indexof_from_to) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index, size_t end_index,
+ const void *elt);
+ gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+ bool (*sortedlist_remove) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt);
+};
+
+struct gl_list_impl_base
+{
+ const struct gl_list_implementation *vtable;
+ gl_listelement_equals_fn equals_fn;
+ gl_listelement_hashcode_fn hashcode_fn;
+ gl_listelement_dispose_fn dispose_fn;
+ bool allow_duplicates;
+};
+
+/* Define all functions of this file as accesses to the
+ struct gl_list_implementation. */
+
+GL_LIST_INLINE gl_list_t
+gl_list_nx_create_empty (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates)
+{
+ return implementation->nx_create_empty (implementation, equals_fn,
+ hashcode_fn, dispose_fn,
+ allow_duplicates);
+}
+
+GL_LIST_INLINE gl_list_t
+gl_list_nx_create (gl_list_implementation_t implementation,
+ gl_listelement_equals_fn equals_fn,
+ gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
+ bool allow_duplicates,
+ size_t count, const void **contents)
+{
+ return implementation->nx_create (implementation, equals_fn, hashcode_fn,
+ dispose_fn, allow_duplicates, count,
+ contents);
+}
+
+GL_LIST_INLINE size_t
+gl_list_size (gl_list_t list)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->size (list);
+}
+
+GL_LIST_INLINE const void *
+gl_list_node_value (gl_list_t list, gl_list_node_t node)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->node_value (list, node);
+}
+
+GL_LIST_INLINE int
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
+ const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->node_nx_set_value (list, node, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_list_next_node (gl_list_t list, gl_list_node_t node)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->next_node (list, node);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_list_previous_node (gl_list_t list, gl_list_node_t node)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->previous_node (list, node);
+}
+
+GL_LIST_INLINE const void *
+gl_list_get_at (gl_list_t list, size_t position)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->get_at (list, position);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->nx_set_at (list, position, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_list_search (gl_list_t list, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, 0, size, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, start_index, size, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, start_index, end_index, elt);
+}
+
+GL_LIST_INLINE size_t
+gl_list_indexof (gl_list_t list, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, 0, size, elt);
+}
+
+GL_LIST_INLINE size_t
+gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, start_index, size, elt);
+}
+
+GL_LIST_INLINE size_t
+gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, start_index, end_index, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_add_first (gl_list_t list, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->nx_add_first (list, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_add_last (gl_list_t list, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->nx_add_last (list, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->nx_add_before (list, node, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->nx_add_after (list, node, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->nx_add_at (list, position, elt);
+}
+
+GL_LIST_INLINE bool
+gl_list_remove_node (gl_list_t list, gl_list_node_t node)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->remove_node (list, node);
+}
+
+GL_LIST_INLINE bool
+gl_list_remove_at (gl_list_t list, size_t position)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->remove_at (list, position);
+}
+
+GL_LIST_INLINE bool
+gl_list_remove (gl_list_t list, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->remove_elt (list, elt);
+}
+
+GL_LIST_INLINE void
+gl_list_free (gl_list_t list)
+{
+ ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
+}
+
+GL_LIST_INLINE gl_list_iterator_t
+gl_list_iterator (gl_list_t list)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->iterator (list);
+}
+
+GL_LIST_INLINE gl_list_iterator_t
+gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->iterator_from_to (list, start_index, end_index);
+}
+
+GL_LIST_INLINE bool
+gl_list_iterator_next (gl_list_iterator_t *iterator,
+ const void **eltp, gl_list_node_t *nodep)
+{
+ return iterator->vtable->iterator_next (iterator, eltp, nodep);
+}
+
+GL_LIST_INLINE void
+gl_list_iterator_free (gl_list_iterator_t *iterator)
+{
+ iterator->vtable->iterator_free (iterator);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_search (list, compar, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_search_from_to (list, compar, start_index, end_index,
+ elt);
+}
+
+GL_LIST_INLINE size_t
+gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_indexof (list, compar, elt);
+}
+
+GL_LIST_INLINE size_t
+gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+ elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_nx_add (list, compar, elt);
+}
+
+GL_LIST_INLINE bool
+gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_remove (list, compar, elt);
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* _GL_LIST_H */
diff --git a/draft/mcastseed/lib/gl_rbtree_list.c b/draft/mcastseed/lib/gl_rbtree_list.c
new file mode 100644
index 0000000..5d621f1
--- /dev/null
+++ b/draft/mcastseed/lib/gl_rbtree_list.c
@@ -0,0 +1,102 @@
+/* Sequential list data type implemented by a binary tree.
+ Copyright (C) 2006, 2008-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+/* Specification. */
+#include "gl_rbtree_list.h"
+
+#include <stdlib.h>
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Generic red-black tree code. */
+#include "gl_anyrbtree_list1.h"
+
+/* Generic binary tree code. */
+#include "gl_anytree_list1.h"
+
+/* Generic red-black tree code. */
+#include "gl_anyrbtree_list2.h"
+
+/* Generic binary tree code. */
+#include "gl_anytree_list2.h"
+
+/* For debugging. */
+static unsigned int
+check_invariants (gl_list_node_t node, gl_list_node_t parent)
+{
+ unsigned int left_blackheight =
+ (node->left != NULL ? check_invariants (node->left, node) : 0);
+ unsigned int right_blackheight =
+ (node->right != NULL ? check_invariants (node->right, node) : 0);
+
+ if (!(node->parent == parent))
+ abort ();
+ if (!(node->branch_size
+ == (node->left != NULL ? node->left->branch_size : 0)
+ + 1 + (node->right != NULL ? node->right->branch_size : 0)))
+ abort ();
+ if (!(node->color == BLACK || node->color == RED))
+ abort ();
+ if (parent == NULL && !(node->color == BLACK))
+ abort ();
+ if (!(left_blackheight == right_blackheight))
+ abort ();
+
+ return left_blackheight + (node->color == BLACK ? 1 : 0);
+}
+void
+gl_rbtree_list_check_invariants (gl_list_t list)
+{
+ if (list->root != NULL)
+ check_invariants (list->root, NULL);
+}
+
+const struct gl_list_implementation gl_rbtree_list_implementation =
+ {
+ gl_tree_nx_create_empty,
+ gl_tree_nx_create,
+ gl_tree_size,
+ gl_tree_node_value,
+ gl_tree_node_nx_set_value,
+ gl_tree_next_node,
+ gl_tree_previous_node,
+ gl_tree_get_at,
+ gl_tree_nx_set_at,
+ gl_tree_search_from_to,
+ gl_tree_indexof_from_to,
+ gl_tree_nx_add_first,
+ gl_tree_nx_add_last,
+ gl_tree_nx_add_before,
+ gl_tree_nx_add_after,
+ gl_tree_nx_add_at,
+ gl_tree_remove_node,
+ gl_tree_remove_at,
+ gl_tree_remove,
+ gl_tree_list_free,
+ gl_tree_iterator,
+ gl_tree_iterator_from_to,
+ gl_tree_iterator_next,
+ gl_tree_iterator_free,
+ gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
+ gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
+ gl_tree_sortedlist_nx_add,
+ gl_tree_sortedlist_remove
+ };
diff --git a/draft/mcastseed/lib/gl_rbtree_list.h b/draft/mcastseed/lib/gl_rbtree_list.h
new file mode 100644
index 0000000..8cb9d11
--- /dev/null
+++ b/draft/mcastseed/lib/gl_rbtree_list.h
@@ -0,0 +1,34 @@
+/* Sequential list data type implemented by a binary tree.
+ Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+ 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 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _GL_RBTREE_LIST_H
+#define _GL_RBTREE_LIST_H
+
+#include "gl_list.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_list_implementation gl_rbtree_list_implementation;
+#define GL_RBTREE_LIST &gl_rbtree_list_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_RBTREE_LIST_H */
diff --git a/draft/mcastseed/lib/stdbool.in.h b/draft/mcastseed/lib/stdbool.in.h
new file mode 100644
index 0000000..7ecf203
--- /dev/null
+++ b/draft/mcastseed/lib/stdbool.in.h
@@ -0,0 +1,132 @@
+/* Copyright (C) 2001-2003, 2006-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <haible@clisp.cons.org>, 2001.
+
+ 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 3, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _GL_STDBOOL_H
+#define _GL_STDBOOL_H
+
+/* ISO C 99 <stdbool.h> for platforms that lack it. */
+
+/* Usage suggestions:
+
+ Programs that use <stdbool.h> should be aware of some limitations
+ and standards compliance issues.
+
+ Standards compliance:
+
+ - <stdbool.h> must be #included before 'bool', 'false', 'true'
+ can be used.
+
+ - You cannot assume that sizeof (bool) == 1.
+
+ - Programs should not undefine the macros bool, true, and false,
+ as C99 lists that as an "obsolescent feature".
+
+ Limitations of this substitute, when used in a C89 environment:
+
+ - <stdbool.h> must be #included before the '_Bool' type can be used.
+
+ - You cannot assume that _Bool is a typedef; it might be a macro.
+
+ - Bit-fields of type 'bool' are not supported. Portable code
+ should use 'unsigned int foo : 1;' rather than 'bool foo : 1;'.
+
+ - In C99, casts and automatic conversions to '_Bool' or 'bool' are
+ performed in such a way that every nonzero value gets converted
+ to 'true', and zero gets converted to 'false'. This doesn't work
+ with this substitute. With this substitute, only the values 0 and 1
+ give the expected result when converted to _Bool' or 'bool'.
+
+ - C99 allows the use of (_Bool)0.0 in constant expressions, but
+ this substitute cannot always provide this property.
+
+ Also, it is suggested that programs use 'bool' rather than '_Bool';
+ this isn't required, but 'bool' is more common. */
+
+
+/* 7.16. Boolean type and values */
+
+/* BeOS <sys/socket.h> already #defines false 0, true 1. We use the same
+ definitions below, but temporarily we have to #undef them. */
+#if defined __BEOS__ && !defined __HAIKU__
+# include <OS.h> /* defines bool but not _Bool */
+# undef false
+# undef true
+#endif
+
+#ifdef __cplusplus
+# define _Bool bool
+# define bool bool
+#else
+# if defined __BEOS__ && !defined __HAIKU__
+ /* A compiler known to have 'bool'. */
+ /* If the compiler already has both 'bool' and '_Bool', we can assume they
+ are the same types. */
+# if !@HAVE__BOOL@
+typedef bool _Bool;
+# endif
+# else
+# if !defined __GNUC__
+ /* If @HAVE__BOOL@:
+ Some HP-UX cc and AIX IBM C compiler versions have compiler bugs when
+ the built-in _Bool type is used. See
+ http://gcc.gnu.org/ml/gcc-patches/2003-12/msg02303.html
+ http://lists.gnu.org/archive/html/bug-coreutils/2005-11/msg00161.html
+ http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html
+ Similar bugs are likely with other compilers as well; this file
+ wouldn't be used if <stdbool.h> was working.
+ So we override the _Bool type.
+ If !@HAVE__BOOL@:
+ Need to define _Bool ourselves. As 'signed char' or as an enum type?
+ Use of a typedef, with SunPRO C, leads to a stupid
+ "warning: _Bool is a keyword in ISO C99".
+ Use of an enum type, with IRIX cc, leads to a stupid
+ "warning(1185): enumerated type mixed with another type".
+ Even the existence of an enum type, without a typedef,
+ "Invalid enumerator. (badenum)" with HP-UX cc on Tru64.
+ The only benefit of the enum, debuggability, is not important
+ with these compilers. So use 'signed char' and no enum. */
+# define _Bool signed char
+# else
+ /* With this compiler, trust the _Bool type if the compiler has it. */
+# if !@HAVE__BOOL@
+ /* For the sake of symbolic names in gdb, define true and false as
+ enum constants, not only as macros.
+ It is tempting to write
+ typedef enum { false = 0, true = 1 } _Bool;
+ so that gdb prints values of type 'bool' symbolically. But then
+ values of type '_Bool' might promote to 'int' or 'unsigned int'
+ (see ISO C 99 6.7.2.2.(4)); however, '_Bool' must promote to 'int'
+ (see ISO C 99 6.3.1.1.(2)). So add a negative value to the
+ enum; this ensures that '_Bool' promotes to 'int'. */
+typedef enum { _Bool_must_promote_to_int = -1, false = 0, true = 1 } _Bool;
+# endif
+# endif
+# endif
+# define bool _Bool
+#endif
+
+/* The other macros must be usable in preprocessor directives. */
+#ifdef __cplusplus
+# define false false
+# define true true
+#else
+# define false 0
+# define true 1
+#endif
+
+#define __bool_true_false_are_defined 1
+
+#endif /* _GL_STDBOOL_H */
diff --git a/draft/mcastseed/m4/00gnulib.m4 b/draft/mcastseed/m4/00gnulib.m4
new file mode 100644
index 0000000..bb37e32
--- /dev/null
+++ b/draft/mcastseed/m4/00gnulib.m4
@@ -0,0 +1,46 @@
+# 00gnulib.m4 serial 3
+dnl Copyright (C) 2009-2016 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+dnl This file must be named something that sorts before all other
+dnl gnulib-provided .m4 files. It is needed until such time as we can
+dnl assume Autoconf 2.64, with its improved AC_DEFUN_ONCE and
+dnl m4_divert semantics.
+
+# Until autoconf 2.63, handling of the diversion stack required m4_init
+# to be called first; but this does not happen with aclocal. Wrapping
+# the entire execution in another layer of the diversion stack fixes this.
+# Worse, prior to autoconf 2.62, m4_wrap depended on the underlying m4
+# for whether it was FIFO or LIFO; in order to properly balance with
+# m4_init, we need to undo our push just before anything wrapped within
+# the m4_init body. The way to ensure this is to wrap both sides of
+# m4_init with a one-shot macro that does the pop at the right time.
+m4_ifndef([_m4_divert_diversion],
+[m4_divert_push([KILL])
+m4_define([gl_divert_fixup], [m4_divert_pop()m4_define([$0])])
+m4_define([m4_init],
+ [gl_divert_fixup()]m4_defn([m4_init])[gl_divert_fixup()])])
+
+
+# AC_DEFUN_ONCE([NAME], VALUE)
+# ----------------------------
+# Define NAME to expand to VALUE on the first use (whether by direct
+# expansion, or by AC_REQUIRE), and to nothing on all subsequent uses.
+# Avoid bugs in AC_REQUIRE in Autoconf 2.63 and earlier. This
+# definition is slower than the version in Autoconf 2.64, because it
+# can only use interfaces that existed since 2.59; but it achieves the
+# same effect. Quoting is necessary to avoid confusing Automake.
+m4_version_prereq([2.63.263], [],
+[m4_define([AC][_DEFUN_ONCE],
+ [AC][_DEFUN([$1],
+ [AC_REQUIRE([_gl_DEFUN_ONCE([$1])],
+ [m4_indir([_gl_DEFUN_ONCE([$1])])])])]dnl
+[AC][_DEFUN([_gl_DEFUN_ONCE([$1])], [$2])])])
+
+# gl_00GNULIB
+# -----------
+# Witness macro that this file has been included. Needed to force
+# Automake to include this file prior to all other gnulib .m4 files.
+AC_DEFUN([gl_00GNULIB])
diff --git a/draft/mcastseed/m4/extern-inline.m4 b/draft/mcastseed/m4/extern-inline.m4
new file mode 100644
index 0000000..1e578f3
--- /dev/null
+++ b/draft/mcastseed/m4/extern-inline.m4
@@ -0,0 +1,102 @@
+dnl 'extern inline' a la ISO C99.
+
+dnl Copyright 2012-2016 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_EXTERN_INLINE],
+[
+ AH_VERBATIM([extern_inline],
+[/* Please see the Gnulib manual for how to use these macros.
+
+ Suppress extern inline with HP-UX cc, as it appears to be broken; see
+ <http://lists.gnu.org/archive/html/bug-texinfo/2013-02/msg00030.html>.
+
+ Suppress extern inline with Sun C in standards-conformance mode, as it
+ mishandles inline functions that call each other. E.g., for 'inline void f
+ (void) { } inline void g (void) { f (); }', c99 incorrectly complains
+ 'reference to static identifier "f" in extern inline function'.
+ This bug was observed with Sun C 5.12 SunOS_i386 2011/11/16.
+
+ Suppress extern inline (with or without __attribute__ ((__gnu_inline__)))
+ on configurations that mistakenly use 'static inline' to implement
+ functions or macros in standard C headers like <ctype.h>. For example,
+ if isdigit is mistakenly implemented via a static inline function,
+ a program containing an extern inline function that calls isdigit
+ may not work since the C standard prohibits extern inline functions
+ from calling static functions. This bug is known to occur on:
+
+ OS X 10.8 and earlier; see:
+ http://lists.gnu.org/archive/html/bug-gnulib/2012-12/msg00023.html
+
+ DragonFly; see
+ http://muscles.dragonflybsd.org/bulk/bleeding-edge-potential/latest-per-pkg/ah-tty-0.3.12.log
+
+ FreeBSD; see:
+ http://lists.gnu.org/archive/html/bug-gnulib/2014-07/msg00104.html
+
+ OS X 10.9 has a macro __header_inline indicating the bug is fixed for C and
+ for clang but remains for g++; see <http://trac.macports.org/ticket/41033>.
+ Assume DragonFly and FreeBSD will be similar. */
+#if (((defined __APPLE__ && defined __MACH__) \
+ || defined __DragonFly__ || defined __FreeBSD__) \
+ && (defined __header_inline \
+ ? (defined __cplusplus && defined __GNUC_STDC_INLINE__ \
+ && ! defined __clang__) \
+ : ((! defined _DONT_USE_CTYPE_INLINE_ \
+ && (defined __GNUC__ || defined __cplusplus)) \
+ || (defined _FORTIFY_SOURCE && 0 < _FORTIFY_SOURCE \
+ && defined __GNUC__ && ! defined __cplusplus))))
+# define _GL_EXTERN_INLINE_STDHEADER_BUG
+#endif
+#if ((__GNUC__ \
+ ? defined __GNUC_STDC_INLINE__ && __GNUC_STDC_INLINE__ \
+ : (199901L <= __STDC_VERSION__ \
+ && !defined __HP_cc \
+ && !defined __PGI \
+ && !(defined __SUNPRO_C && __STDC__))) \
+ && !defined _GL_EXTERN_INLINE_STDHEADER_BUG)
+# define _GL_INLINE inline
+# define _GL_EXTERN_INLINE extern inline
+# define _GL_EXTERN_INLINE_IN_USE
+#elif (2 < __GNUC__ + (7 <= __GNUC_MINOR__) && !defined __STRICT_ANSI__ \
+ && !defined _GL_EXTERN_INLINE_STDHEADER_BUG)
+# if defined __GNUC_GNU_INLINE__ && __GNUC_GNU_INLINE__
+ /* __gnu_inline__ suppresses a GCC 4.2 diagnostic. */
+# define _GL_INLINE extern inline __attribute__ ((__gnu_inline__))
+# else
+# define _GL_INLINE extern inline
+# endif
+# define _GL_EXTERN_INLINE extern
+# define _GL_EXTERN_INLINE_IN_USE
+#else
+# define _GL_INLINE static _GL_UNUSED
+# define _GL_EXTERN_INLINE static _GL_UNUSED
+#endif
+
+/* In GCC 4.6 (inclusive) to 5.1 (exclusive),
+ suppress bogus "no previous prototype for 'FOO'"
+ and "no previous declaration for 'FOO'" diagnostics,
+ when FOO is an inline function in the header; see
+ <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54113> and
+ <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63877>. */
+#if __GNUC__ == 4 && 6 <= __GNUC_MINOR__
+# if defined __GNUC_STDC_INLINE__ && __GNUC_STDC_INLINE__
+# define _GL_INLINE_HEADER_CONST_PRAGMA
+# else
+# define _GL_INLINE_HEADER_CONST_PRAGMA \
+ _Pragma ("GCC diagnostic ignored \"-Wsuggest-attribute=const\"")
+# endif
+# define _GL_INLINE_HEADER_BEGIN \
+ _Pragma ("GCC diagnostic push") \
+ _Pragma ("GCC diagnostic ignored \"-Wmissing-prototypes\"") \
+ _Pragma ("GCC diagnostic ignored \"-Wmissing-declarations\"") \
+ _GL_INLINE_HEADER_CONST_PRAGMA
+# define _GL_INLINE_HEADER_END \
+ _Pragma ("GCC diagnostic pop")
+#else
+# define _GL_INLINE_HEADER_BEGIN
+# define _GL_INLINE_HEADER_END
+#endif])
+])
diff --git a/draft/mcastseed/m4/gnulib-cache.m4 b/draft/mcastseed/m4/gnulib-cache.m4
new file mode 100644
index 0000000..d75ad4f
--- /dev/null
+++ b/draft/mcastseed/m4/gnulib-cache.m4
@@ -0,0 +1,47 @@
+# Copyright (C) 2002-2016 Free Software Foundation, Inc.
+#
+# This file 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 3 of the License, or
+# (at your option) any later version.
+#
+# This file is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this file. If not, see <http://www.gnu.org/licenses/>.
+#
+# As a special exception to the GNU General Public License,
+# this file may be distributed as part of a program that
+# contains a configuration script generated by Autoconf, under
+# the same distribution terms as the rest of that program.
+#
+# Generated by gnulib-tool.
+#
+# This file represents the specification of how gnulib-tool is used.
+# It acts as a cache: It is written and read by gnulib-tool.
+# In projects that use version control, this file is meant to be put under
+# version control, like the configure.ac and various Makefile.am files.
+
+
+# Specification in the form of a command-line invocation:
+# gnulib-tool --import --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=. --no-conditional-dependencies --no-libtool --macro-prefix=gl rbtree-list
+
+# Specification in the form of a few gnulib-tool.m4 macro invocations:
+gl_LOCAL_DIR([])
+gl_MODULES([
+ rbtree-list
+])
+gl_AVOID([])
+gl_SOURCE_BASE([lib])
+gl_M4_BASE([m4])
+gl_PO_BASE([])
+gl_DOC_BASE([doc])
+gl_TESTS_BASE([tests])
+gl_LIB([libgnu])
+gl_MAKEFILE_NAME([])
+gl_MACRO_PREFIX([gl])
+gl_PO_DOMAIN([])
+gl_WITNESS_C_MACRO([])
diff --git a/draft/mcastseed/m4/gnulib-common.m4 b/draft/mcastseed/m4/gnulib-common.m4
new file mode 100644
index 0000000..f8454c8
--- /dev/null
+++ b/draft/mcastseed/m4/gnulib-common.m4
@@ -0,0 +1,462 @@
+# gnulib-common.m4 serial 36
+dnl Copyright (C) 2007-2016 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+# gl_COMMON
+# is expanded unconditionally through gnulib-tool magic.
+AC_DEFUN([gl_COMMON], [
+ dnl Use AC_REQUIRE here, so that the code is expanded once only.
+ AC_REQUIRE([gl_00GNULIB])
+ AC_REQUIRE([gl_COMMON_BODY])
+])
+AC_DEFUN([gl_COMMON_BODY], [
+ AH_VERBATIM([_Noreturn],
+[/* The _Noreturn keyword of C11. */
+#if ! (defined _Noreturn \
+ || (defined __STDC_VERSION__ && 201112 <= __STDC_VERSION__))
+# if (3 <= __GNUC__ || (__GNUC__ == 2 && 8 <= __GNUC_MINOR__) \
+ || 0x5110 <= __SUNPRO_C)
+# define _Noreturn __attribute__ ((__noreturn__))
+# elif defined _MSC_VER && 1200 <= _MSC_VER
+# define _Noreturn __declspec (noreturn)
+# else
+# define _Noreturn
+# endif
+#endif
+])
+ AH_VERBATIM([isoc99_inline],
+[/* Work around a bug in Apple GCC 4.0.1 build 5465: In C99 mode, it supports
+ the ISO C 99 semantics of 'extern inline' (unlike the GNU C semantics of
+ earlier versions), but does not display it by setting __GNUC_STDC_INLINE__.
+ __APPLE__ && __MACH__ test for Mac OS X.
+ __APPLE_CC__ tests for the Apple compiler and its version.
+ __STDC_VERSION__ tests for the C99 mode. */
+#if defined __APPLE__ && defined __MACH__ && __APPLE_CC__ >= 5465 && !defined __cplusplus && __STDC_VERSION__ >= 199901L && !defined __GNUC_STDC_INLINE__
+# define __GNUC_STDC_INLINE__ 1
+#endif])
+ AH_VERBATIM([unused_parameter],
+[/* Define as a marker that can be attached to declarations that might not
+ be used. This helps to reduce warnings, such as from
+ GCC -Wunused-parameter. */
+#if __GNUC__ >= 3 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 7)
+# define _GL_UNUSED __attribute__ ((__unused__))
+#else
+# define _GL_UNUSED
+#endif
+/* The name _UNUSED_PARAMETER_ is an earlier spelling, although the name
+ is a misnomer outside of parameter lists. */
+#define _UNUSED_PARAMETER_ _GL_UNUSED
+
+/* gcc supports the "unused" attribute on possibly unused labels, and
+ g++ has since version 4.5. Note to support C++ as well as C,
+ _GL_UNUSED_LABEL should be used with a trailing ; */
+#if !defined __cplusplus || __GNUC__ > 4 \
+ || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
+# define _GL_UNUSED_LABEL _GL_UNUSED
+#else
+# define _GL_UNUSED_LABEL
+#endif
+
+/* The __pure__ attribute was added in gcc 2.96. */
+#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 96)
+# define _GL_ATTRIBUTE_PURE __attribute__ ((__pure__))
+#else
+# define _GL_ATTRIBUTE_PURE /* empty */
+#endif
+
+/* The __const__ attribute was added in gcc 2.95. */
+#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 95)
+# define _GL_ATTRIBUTE_CONST __attribute__ ((__const__))
+#else
+# define _GL_ATTRIBUTE_CONST /* empty */
+#endif
+])
+ dnl Preparation for running test programs:
+ dnl Tell glibc to write diagnostics from -D_FORTIFY_SOURCE=2 to stderr, not
+ dnl to /dev/tty, so they can be redirected to log files. Such diagnostics
+ dnl arise e.g., in the macros gl_PRINTF_DIRECTIVE_N, gl_SNPRINTF_DIRECTIVE_N.
+ LIBC_FATAL_STDERR_=1
+ export LIBC_FATAL_STDERR_
+])
+
+# gl_MODULE_INDICATOR_CONDITION
+# expands to a C preprocessor expression that evaluates to 1 or 0, depending
+# whether a gnulib module that has been requested shall be considered present
+# or not.
+m4_define([gl_MODULE_INDICATOR_CONDITION], [1])
+
+# gl_MODULE_INDICATOR_SET_VARIABLE([modulename])
+# sets the shell variable that indicates the presence of the given module to
+# a C preprocessor expression that will evaluate to 1.
+AC_DEFUN([gl_MODULE_INDICATOR_SET_VARIABLE],
+[
+ gl_MODULE_INDICATOR_SET_VARIABLE_AUX(
+ [GNULIB_[]m4_translit([[$1]],
+ [abcdefghijklmnopqrstuvwxyz./-],
+ [ABCDEFGHIJKLMNOPQRSTUVWXYZ___])],
+ [gl_MODULE_INDICATOR_CONDITION])
+])
+
+# gl_MODULE_INDICATOR_SET_VARIABLE_AUX([variable])
+# modifies the shell variable to include the gl_MODULE_INDICATOR_CONDITION.
+# The shell variable's value is a C preprocessor expression that evaluates
+# to 0 or 1.
+AC_DEFUN([gl_MODULE_INDICATOR_SET_VARIABLE_AUX],
+[
+ m4_if(m4_defn([gl_MODULE_INDICATOR_CONDITION]), [1],
+ [
+ dnl Simplify the expression VALUE || 1 to 1.
+ $1=1
+ ],
+ [gl_MODULE_INDICATOR_SET_VARIABLE_AUX_OR([$1],
+ [gl_MODULE_INDICATOR_CONDITION])])
+])
+
+# gl_MODULE_INDICATOR_SET_VARIABLE_AUX_OR([variable], [condition])
+# modifies the shell variable to include the given condition. The shell
+# variable's value is a C preprocessor expression that evaluates to 0 or 1.
+AC_DEFUN([gl_MODULE_INDICATOR_SET_VARIABLE_AUX_OR],
+[
+ dnl Simplify the expression 1 || CONDITION to 1.
+ if test "$[]$1" != 1; then
+ dnl Simplify the expression 0 || CONDITION to CONDITION.
+ if test "$[]$1" = 0; then
+ $1=$2
+ else
+ $1="($[]$1 || $2)"
+ fi
+ fi
+])
+
+# gl_MODULE_INDICATOR([modulename])
+# defines a C macro indicating the presence of the given module
+# in a location where it can be used.
+# | Value | Value |
+# | in lib/ | in tests/ |
+# --------------------------------------------+---------+-----------+
+# Module present among main modules: | 1 | 1 |
+# --------------------------------------------+---------+-----------+
+# Module present among tests-related modules: | 0 | 1 |
+# --------------------------------------------+---------+-----------+
+# Module not present at all: | 0 | 0 |
+# --------------------------------------------+---------+-----------+
+AC_DEFUN([gl_MODULE_INDICATOR],
+[
+ AC_DEFINE_UNQUOTED([GNULIB_]m4_translit([[$1]],
+ [abcdefghijklmnopqrstuvwxyz./-],
+ [ABCDEFGHIJKLMNOPQRSTUVWXYZ___]),
+ [gl_MODULE_INDICATOR_CONDITION],
+ [Define to a C preprocessor expression that evaluates to 1 or 0,
+ depending whether the gnulib module $1 shall be considered present.])
+])
+
+# gl_MODULE_INDICATOR_FOR_TESTS([modulename])
+# defines a C macro indicating the presence of the given module
+# in lib or tests. This is useful to determine whether the module
+# should be tested.
+# | Value | Value |
+# | in lib/ | in tests/ |
+# --------------------------------------------+---------+-----------+
+# Module present among main modules: | 1 | 1 |
+# --------------------------------------------+---------+-----------+
+# Module present among tests-related modules: | 1 | 1 |
+# --------------------------------------------+---------+-----------+
+# Module not present at all: | 0 | 0 |
+# --------------------------------------------+---------+-----------+
+AC_DEFUN([gl_MODULE_INDICATOR_FOR_TESTS],
+[
+ AC_DEFINE([GNULIB_TEST_]m4_translit([[$1]],
+ [abcdefghijklmnopqrstuvwxyz./-],
+ [ABCDEFGHIJKLMNOPQRSTUVWXYZ___]), [1],
+ [Define to 1 when the gnulib module $1 should be tested.])
+])
+
+# gl_ASSERT_NO_GNULIB_POSIXCHECK
+# asserts that there will never be a need to #define GNULIB_POSIXCHECK.
+# and thereby enables an optimization of configure and config.h.
+# Used by Emacs.
+AC_DEFUN([gl_ASSERT_NO_GNULIB_POSIXCHECK],
+[
+ dnl Override gl_WARN_ON_USE_PREPARE.
+ dnl But hide this definition from 'aclocal'.
+ AC_DEFUN([gl_W][ARN_ON_USE_PREPARE], [])
+])
+
+# gl_ASSERT_NO_GNULIB_TESTS
+# asserts that there will be no gnulib tests in the scope of the configure.ac
+# and thereby enables an optimization of config.h.
+# Used by Emacs.
+AC_DEFUN([gl_ASSERT_NO_GNULIB_TESTS],
+[
+ dnl Override gl_MODULE_INDICATOR_FOR_TESTS.
+ AC_DEFUN([gl_MODULE_INDICATOR_FOR_TESTS], [])
+])
+
+# Test whether <features.h> exists.
+# Set HAVE_FEATURES_H.
+AC_DEFUN([gl_FEATURES_H],
+[
+ AC_CHECK_HEADERS_ONCE([features.h])
+ if test $ac_cv_header_features_h = yes; then
+ HAVE_FEATURES_H=1
+ else
+ HAVE_FEATURES_H=0
+ fi
+ AC_SUBST([HAVE_FEATURES_H])
+])
+
+# m4_foreach_w
+# is a backport of autoconf-2.59c's m4_foreach_w.
+# Remove this macro when we can assume autoconf >= 2.60.
+m4_ifndef([m4_foreach_w],
+ [m4_define([m4_foreach_w],
+ [m4_foreach([$1], m4_split(m4_normalize([$2]), [ ]), [$3])])])
+
+# AS_VAR_IF(VAR, VALUE, [IF-MATCH], [IF-NOT-MATCH])
+# ----------------------------------------------------
+# Backport of autoconf-2.63b's macro.
+# Remove this macro when we can assume autoconf >= 2.64.
+m4_ifndef([AS_VAR_IF],
+[m4_define([AS_VAR_IF],
+[AS_IF([test x"AS_VAR_GET([$1])" = x""$2], [$3], [$4])])])
+
+# gl_PROG_CC_C99
+# Modifies the value of the shell variable CC in an attempt to make $CC
+# understand ISO C99 source code.
+# This is like AC_PROG_CC_C99, except that
+# - AC_PROG_CC_C99 did not exist in Autoconf versions < 2.60,
+# - AC_PROG_CC_C99 does not mix well with AC_PROG_CC_STDC
+# <http://lists.gnu.org/archive/html/bug-gnulib/2011-09/msg00367.html>,
+# but many more packages use AC_PROG_CC_STDC than AC_PROG_CC_C99
+# <http://lists.gnu.org/archive/html/bug-gnulib/2011-09/msg00441.html>.
+# Remaining problems:
+# - When AC_PROG_CC_STDC is invoked twice, it adds the C99 enabling options
+# to CC twice
+# <http://lists.gnu.org/archive/html/bug-gnulib/2011-09/msg00431.html>.
+# - AC_PROG_CC_STDC is likely to change now that C11 is an ISO standard.
+AC_DEFUN([gl_PROG_CC_C99],
+[
+ dnl Change that version number to the minimum Autoconf version that supports
+ dnl mixing AC_PROG_CC_C99 calls with AC_PROG_CC_STDC calls.
+ m4_version_prereq([9.0],
+ [AC_REQUIRE([AC_PROG_CC_C99])],
+ [AC_REQUIRE([AC_PROG_CC_STDC])])
+])
+
+# gl_PROG_AR_RANLIB
+# Determines the values for AR, ARFLAGS, RANLIB that fit with the compiler.
+# The user can set the variables AR, ARFLAGS, RANLIB if he wants to override
+# the values.
+AC_DEFUN([gl_PROG_AR_RANLIB],
+[
+ dnl Minix 3 comes with two toolchains: The Amsterdam Compiler Kit compiler
+ dnl as "cc", and GCC as "gcc". They have different object file formats and
+ dnl library formats. In particular, the GNU binutils programs ar and ranlib
+ dnl produce libraries that work only with gcc, not with cc.
+ AC_REQUIRE([AC_PROG_CC])
+ AC_BEFORE([$0], [AM_PROG_AR])
+ AC_CACHE_CHECK([for Minix Amsterdam compiler], [gl_cv_c_amsterdam_compiler],
+ [
+ AC_EGREP_CPP([Amsterdam],
+ [
+#ifdef __ACK__
+Amsterdam
+#endif
+ ],
+ [gl_cv_c_amsterdam_compiler=yes],
+ [gl_cv_c_amsterdam_compiler=no])
+ ])
+
+ dnl Don't compete with AM_PROG_AR's decision about AR/ARFLAGS if we are not
+ dnl building with __ACK__.
+ if test $gl_cv_c_amsterdam_compiler = yes; then
+ if test -z "$AR"; then
+ AR='cc -c.a'
+ fi
+ if test -z "$ARFLAGS"; then
+ ARFLAGS='-o'
+ fi
+ else
+ dnl AM_PROG_AR was added in automake v1.11.2. AM_PROG_AR does not AC_SUBST
+ dnl ARFLAGS variable (it is filed into Makefile.in directly by automake
+ dnl script on-demand, if not specified by ./configure of course).
+ dnl Don't AC_REQUIRE the AM_PROG_AR otherwise the code for __ACK__ above
+ dnl will be ignored. Also, pay attention to call AM_PROG_AR in else block
+ dnl because AM_PROG_AR is written so it could re-set AR variable even for
+ dnl __ACK__. It may seem like its easier to avoid calling the macro here,
+ dnl but we need to AC_SUBST both AR/ARFLAGS (thus those must have some good
+ dnl default value and automake should usually know them).
+ m4_ifdef([AM_PROG_AR], [AM_PROG_AR], [:])
+ fi
+
+ dnl In case the code above has not helped with setting AR/ARFLAGS, use
+ dnl Automake-documented default values for AR and ARFLAGS, but prefer
+ dnl ${host}-ar over ar (useful for cross-compiling).
+ AC_CHECK_TOOL([AR], [ar], [ar])
+ if test -z "$ARFLAGS"; then
+ ARFLAGS='cr'
+ fi
+
+ AC_SUBST([AR])
+ AC_SUBST([ARFLAGS])
+ if test -z "$RANLIB"; then
+ if test $gl_cv_c_amsterdam_compiler = yes; then
+ RANLIB=':'
+ else
+ dnl Use the ranlib program if it is available.
+ AC_PROG_RANLIB
+ fi
+ fi
+ AC_SUBST([RANLIB])
+])
+
+# AC_PROG_MKDIR_P
+# is a backport of autoconf-2.60's AC_PROG_MKDIR_P, with a fix
+# for interoperability with automake-1.9.6 from autoconf-2.62.
+# Remove this macro when we can assume autoconf >= 2.62 or
+# autoconf >= 2.60 && automake >= 1.10.
+# AC_AUTOCONF_VERSION was introduced in 2.62, so use that as the witness.
+m4_ifndef([AC_AUTOCONF_VERSION],[
+m4_ifdef([AC_PROG_MKDIR_P], [
+ dnl For automake-1.9.6 && autoconf < 2.62: Ensure MKDIR_P is AC_SUBSTed.
+ m4_define([AC_PROG_MKDIR_P],
+ m4_defn([AC_PROG_MKDIR_P])[
+ AC_SUBST([MKDIR_P])])], [
+ dnl For autoconf < 2.60: Backport of AC_PROG_MKDIR_P.
+ AC_DEFUN_ONCE([AC_PROG_MKDIR_P],
+ [AC_REQUIRE([AM_PROG_MKDIR_P])dnl defined by automake
+ MKDIR_P='$(mkdir_p)'
+ AC_SUBST([MKDIR_P])])])
+])
+
+# AC_C_RESTRICT
+# This definition is copied from post-2.69 Autoconf and overrides the
+# AC_C_RESTRICT macro from autoconf 2.60..2.69. It can be removed
+# once autoconf >= 2.70 can be assumed. It's painful to check version
+# numbers, and in practice this macro is more up-to-date than Autoconf
+# is, so override Autoconf unconditionally.
+AC_DEFUN([AC_C_RESTRICT],
+[AC_CACHE_CHECK([for C/C++ restrict keyword], [ac_cv_c_restrict],
+ [ac_cv_c_restrict=no
+ # The order here caters to the fact that C++ does not require restrict.
+ for ac_kw in __restrict __restrict__ _Restrict restrict; do
+ AC_COMPILE_IFELSE(
+ [AC_LANG_PROGRAM(
+ [[typedef int *int_ptr;
+ int foo (int_ptr $ac_kw ip) { return ip[0]; }
+ int bar (int [$ac_kw]); /* Catch GCC bug 14050. */
+ int bar (int ip[$ac_kw]) { return ip[0]; }
+ ]],
+ [[int s[1];
+ int *$ac_kw t = s;
+ t[0] = 0;
+ return foo (t) + bar (t);
+ ]])],
+ [ac_cv_c_restrict=$ac_kw])
+ test "$ac_cv_c_restrict" != no && break
+ done
+ ])
+ AH_VERBATIM([restrict],
+[/* Define to the equivalent of the C99 'restrict' keyword, or to
+ nothing if this is not supported. Do not define if restrict is
+ supported directly. */
+#undef restrict
+/* Work around a bug in Sun C++: it does not support _Restrict or
+ __restrict__, even though the corresponding Sun C compiler ends up with
+ "#define restrict _Restrict" or "#define restrict __restrict__" in the
+ previous line. Perhaps some future version of Sun C++ will work with
+ restrict; if so, hopefully it defines __RESTRICT like Sun C does. */
+#if defined __SUNPRO_CC && !defined __RESTRICT
+# define _Restrict
+# define __restrict__
+#endif])
+ case $ac_cv_c_restrict in
+ restrict) ;;
+ no) AC_DEFINE([restrict], []) ;;
+ *) AC_DEFINE_UNQUOTED([restrict], [$ac_cv_c_restrict]) ;;
+ esac
+])# AC_C_RESTRICT
+
+# gl_BIGENDIAN
+# is like AC_C_BIGENDIAN, except that it can be AC_REQUIREd.
+# Note that AC_REQUIRE([AC_C_BIGENDIAN]) does not work reliably because some
+# macros invoke AC_C_BIGENDIAN with arguments.
+AC_DEFUN([gl_BIGENDIAN],
+[
+ AC_C_BIGENDIAN
+])
+
+# gl_CACHE_VAL_SILENT(cache-id, command-to-set-it)
+# is like AC_CACHE_VAL(cache-id, command-to-set-it), except that it does not
+# output a spurious "(cached)" mark in the midst of other configure output.
+# This macro should be used instead of AC_CACHE_VAL when it is not surrounded
+# by an AC_MSG_CHECKING/AC_MSG_RESULT pair.
+AC_DEFUN([gl_CACHE_VAL_SILENT],
+[
+ saved_as_echo_n="$as_echo_n"
+ as_echo_n=':'
+ AC_CACHE_VAL([$1], [$2])
+ as_echo_n="$saved_as_echo_n"
+])
+
+# AS_VAR_COPY was added in autoconf 2.63b
+m4_define_default([AS_VAR_COPY],
+[AS_LITERAL_IF([$1[]$2], [$1=$$2], [eval $1=\$$2])])
+
+# AC_PROG_SED was added in autoconf 2.59b
+m4_ifndef([AC_PROG_SED],
+[AC_DEFUN([AC_PROG_SED],
+[AC_CACHE_CHECK([for a sed that does not truncate output], ac_cv_path_SED,
+ [dnl ac_script should not contain more than 99 commands (for HP-UX sed),
+ dnl but more than about 7000 bytes, to catch a limit in Solaris 8 /usr/ucb/sed.
+ ac_script=s/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb/
+ for ac_i in 1 2 3 4 5 6 7; do
+ ac_script="$ac_script$as_nl$ac_script"
+ done
+ echo "$ac_script" 2>/dev/null | sed 99q >conftest.sed
+ AS_UNSET([ac_script])
+ if test -z "$SED"; then
+ ac_path_SED_found=false
+ _AS_PATH_WALK([], [
+ for ac_prog in sed gsed; do
+ for ac_exec_ext in '' $ac_executable_extensions; do
+ ac_path_SED="$as_dir/$ac_prog$ac_exec_ext"
+ AS_EXECUTABLE_P(["$ac_path_SED"]) || continue
+ case `"$ac_path_SED" --version 2>&1` in
+ *GNU*) ac_cv_path_SED=$ac_path_SED ac_path_SED_found=:;;
+ *)
+ ac_count=0
+ _AS_ECHO_N([0123456789]) >conftest.in
+ while :
+ do
+ cat conftest.in conftest.in >conftest.tmp
+ mv conftest.tmp conftest.in
+ cp conftest.in conftest.nl
+ echo >> conftest.nl
+ "$ac_path_SED" -f conftest.sed <conftest.nl >conftest.out 2>/dev/null || break
+ diff conftest.out conftest.nl >/dev/null 2>&1 || break
+ ac_count=`expr $ac_count + 1`
+ if test $ac_count -gt ${ac_path_SED_max-0}; then
+ # Best so far, but keep looking for better
+ ac_cv_path_SED=$ac_path_SED
+ ac_path_SED_max=$ac_count
+ fi
+ test $ac_count -gt 10 && break
+ done
+ rm -f conftest.in conftest.tmp conftest.nl conftest.out;;
+ esac
+ $ac_path_SED_found && break 3
+ done
+ done])
+ if test -z "$ac_cv_path_SED"; then
+ AC_ERROR([no acceptable sed could be found in \$PATH])
+ fi
+ else
+ ac_cv_path_SED=$SED
+ fi
+ SED="$ac_cv_path_SED"
+ AC_SUBST([SED])dnl
+ rm -f conftest.sed
+])])])
diff --git a/draft/mcastseed/m4/gnulib-comp.m4 b/draft/mcastseed/m4/gnulib-comp.m4
new file mode 100644
index 0000000..b809eea
--- /dev/null
+++ b/draft/mcastseed/m4/gnulib-comp.m4
@@ -0,0 +1,221 @@
+# DO NOT EDIT! GENERATED AUTOMATICALLY!
+# Copyright (C) 2002-2016 Free Software Foundation, Inc.
+#
+# This file 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 3 of the License, or
+# (at your option) any later version.
+#
+# This file is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this file. If not, see <http://www.gnu.org/licenses/>.
+#
+# As a special exception to the GNU General Public License,
+# this file may be distributed as part of a program that
+# contains a configuration script generated by Autoconf, under
+# the same distribution terms as the rest of that program.
+#
+# Generated by gnulib-tool.
+#
+# This file represents the compiled summary of the specification in
+# gnulib-cache.m4. It lists the computed macro invocations that need
+# to be invoked from configure.ac.
+# In projects that use version control, this file can be treated like
+# other built files.
+
+
+# This macro should be invoked from ./configure.ac, in the section
+# "Checks for programs", right after AC_PROG_CC, and certainly before
+# any checks for libraries, header files, types and library functions.
+AC_DEFUN([gl_EARLY],
+[
+ m4_pattern_forbid([^gl_[A-Z]])dnl the gnulib macro namespace
+ m4_pattern_allow([^gl_ES$])dnl a valid locale name
+ m4_pattern_allow([^gl_LIBOBJS$])dnl a variable
+ m4_pattern_allow([^gl_LTLIBOBJS$])dnl a variable
+
+ # Pre-early section.
+ AC_REQUIRE([gl_PROG_AR_RANLIB])
+
+ # Code from module extern-inline:
+ # Code from module list:
+ # Code from module rbtree-list:
+ # Code from module stdbool:
+])
+
+# This macro should be invoked from ./configure.ac, in the section
+# "Check for header files, types and library functions".
+AC_DEFUN([gl_INIT],
+[
+ AM_CONDITIONAL([GL_COND_LIBTOOL], [false])
+ gl_cond_libtool=false
+ gl_libdeps=
+ gl_ltlibdeps=
+ gl_m4_base='m4'
+ m4_pushdef([AC_LIBOBJ], m4_defn([gl_LIBOBJ]))
+ m4_pushdef([AC_REPLACE_FUNCS], m4_defn([gl_REPLACE_FUNCS]))
+ m4_pushdef([AC_LIBSOURCES], m4_defn([gl_LIBSOURCES]))
+ m4_pushdef([gl_LIBSOURCES_LIST], [])
+ m4_pushdef([gl_LIBSOURCES_DIR], [])
+ gl_COMMON
+ gl_source_base='lib'
+ AC_REQUIRE([gl_EXTERN_INLINE])
+ AM_STDBOOL_H
+ # End of code from modules
+ m4_ifval(gl_LIBSOURCES_LIST, [
+ m4_syscmd([test ! -d ]m4_defn([gl_LIBSOURCES_DIR])[ ||
+ for gl_file in ]gl_LIBSOURCES_LIST[ ; do
+ if test ! -r ]m4_defn([gl_LIBSOURCES_DIR])[/$gl_file ; then
+ echo "missing file ]m4_defn([gl_LIBSOURCES_DIR])[/$gl_file" >&2
+ exit 1
+ fi
+ done])dnl
+ m4_if(m4_sysval, [0], [],
+ [AC_FATAL([expected source file, required through AC_LIBSOURCES, not found])])
+ ])
+ m4_popdef([gl_LIBSOURCES_DIR])
+ m4_popdef([gl_LIBSOURCES_LIST])
+ m4_popdef([AC_LIBSOURCES])
+ m4_popdef([AC_REPLACE_FUNCS])
+ m4_popdef([AC_LIBOBJ])
+ AC_CONFIG_COMMANDS_PRE([
+ gl_libobjs=
+ gl_ltlibobjs=
+ if test -n "$gl_LIBOBJS"; then
+ # Remove the extension.
+ sed_drop_objext='s/\.o$//;s/\.obj$//'
+ for i in `for i in $gl_LIBOBJS; do echo "$i"; done | sed -e "$sed_drop_objext" | sort | uniq`; do
+ gl_libobjs="$gl_libobjs $i.$ac_objext"
+ gl_ltlibobjs="$gl_ltlibobjs $i.lo"
+ done
+ fi
+ AC_SUBST([gl_LIBOBJS], [$gl_libobjs])
+ AC_SUBST([gl_LTLIBOBJS], [$gl_ltlibobjs])
+ ])
+ gltests_libdeps=
+ gltests_ltlibdeps=
+ m4_pushdef([AC_LIBOBJ], m4_defn([gltests_LIBOBJ]))
+ m4_pushdef([AC_REPLACE_FUNCS], m4_defn([gltests_REPLACE_FUNCS]))
+ m4_pushdef([AC_LIBSOURCES], m4_defn([gltests_LIBSOURCES]))
+ m4_pushdef([gltests_LIBSOURCES_LIST], [])
+ m4_pushdef([gltests_LIBSOURCES_DIR], [])
+ gl_COMMON
+ gl_source_base='tests'
+changequote(,)dnl
+ gltests_WITNESS=IN_`echo "${PACKAGE-$PACKAGE_TARNAME}" | LC_ALL=C tr abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ | LC_ALL=C sed -e 's/[^A-Z0-9_]/_/g'`_GNULIB_TESTS
+changequote([, ])dnl
+ AC_SUBST([gltests_WITNESS])
+ gl_module_indicator_condition=$gltests_WITNESS
+ m4_pushdef([gl_MODULE_INDICATOR_CONDITION], [$gl_module_indicator_condition])
+ m4_popdef([gl_MODULE_INDICATOR_CONDITION])
+ m4_ifval(gltests_LIBSOURCES_LIST, [
+ m4_syscmd([test ! -d ]m4_defn([gltests_LIBSOURCES_DIR])[ ||
+ for gl_file in ]gltests_LIBSOURCES_LIST[ ; do
+ if test ! -r ]m4_defn([gltests_LIBSOURCES_DIR])[/$gl_file ; then
+ echo "missing file ]m4_defn([gltests_LIBSOURCES_DIR])[/$gl_file" >&2
+ exit 1
+ fi
+ done])dnl
+ m4_if(m4_sysval, [0], [],
+ [AC_FATAL([expected source file, required through AC_LIBSOURCES, not found])])
+ ])
+ m4_popdef([gltests_LIBSOURCES_DIR])
+ m4_popdef([gltests_LIBSOURCES_LIST])
+ m4_popdef([AC_LIBSOURCES])
+ m4_popdef([AC_REPLACE_FUNCS])
+ m4_popdef([AC_LIBOBJ])
+ AC_CONFIG_COMMANDS_PRE([
+ gltests_libobjs=
+ gltests_ltlibobjs=
+ if test -n "$gltests_LIBOBJS"; then
+ # Remove the extension.
+ sed_drop_objext='s/\.o$//;s/\.obj$//'
+ for i in `for i in $gltests_LIBOBJS; do echo "$i"; done | sed -e "$sed_drop_objext" | sort | uniq`; do
+ gltests_libobjs="$gltests_libobjs $i.$ac_objext"
+ gltests_ltlibobjs="$gltests_ltlibobjs $i.lo"
+ done
+ fi
+ AC_SUBST([gltests_LIBOBJS], [$gltests_libobjs])
+ AC_SUBST([gltests_LTLIBOBJS], [$gltests_ltlibobjs])
+ ])
+ LIBGNU_LIBDEPS="$gl_libdeps"
+ AC_SUBST([LIBGNU_LIBDEPS])
+ LIBGNU_LTLIBDEPS="$gl_ltlibdeps"
+ AC_SUBST([LIBGNU_LTLIBDEPS])
+])
+
+# Like AC_LIBOBJ, except that the module name goes
+# into gl_LIBOBJS instead of into LIBOBJS.
+AC_DEFUN([gl_LIBOBJ], [
+ AS_LITERAL_IF([$1], [gl_LIBSOURCES([$1.c])])dnl
+ gl_LIBOBJS="$gl_LIBOBJS $1.$ac_objext"
+])
+
+# Like AC_REPLACE_FUNCS, except that the module name goes
+# into gl_LIBOBJS instead of into LIBOBJS.
+AC_DEFUN([gl_REPLACE_FUNCS], [
+ m4_foreach_w([gl_NAME], [$1], [AC_LIBSOURCES(gl_NAME[.c])])dnl
+ AC_CHECK_FUNCS([$1], , [gl_LIBOBJ($ac_func)])
+])
+
+# Like AC_LIBSOURCES, except the directory where the source file is
+# expected is derived from the gnulib-tool parameterization,
+# and alloca is special cased (for the alloca-opt module).
+# We could also entirely rely on EXTRA_lib..._SOURCES.
+AC_DEFUN([gl_LIBSOURCES], [
+ m4_foreach([_gl_NAME], [$1], [
+ m4_if(_gl_NAME, [alloca.c], [], [
+ m4_define([gl_LIBSOURCES_DIR], [lib])
+ m4_append([gl_LIBSOURCES_LIST], _gl_NAME, [ ])
+ ])
+ ])
+])
+
+# Like AC_LIBOBJ, except that the module name goes
+# into gltests_LIBOBJS instead of into LIBOBJS.
+AC_DEFUN([gltests_LIBOBJ], [
+ AS_LITERAL_IF([$1], [gltests_LIBSOURCES([$1.c])])dnl
+ gltests_LIBOBJS="$gltests_LIBOBJS $1.$ac_objext"
+])
+
+# Like AC_REPLACE_FUNCS, except that the module name goes
+# into gltests_LIBOBJS instead of into LIBOBJS.
+AC_DEFUN([gltests_REPLACE_FUNCS], [
+ m4_foreach_w([gl_NAME], [$1], [AC_LIBSOURCES(gl_NAME[.c])])dnl
+ AC_CHECK_FUNCS([$1], , [gltests_LIBOBJ($ac_func)])
+])
+
+# Like AC_LIBSOURCES, except the directory where the source file is
+# expected is derived from the gnulib-tool parameterization,
+# and alloca is special cased (for the alloca-opt module).
+# We could also entirely rely on EXTRA_lib..._SOURCES.
+AC_DEFUN([gltests_LIBSOURCES], [
+ m4_foreach([_gl_NAME], [$1], [
+ m4_if(_gl_NAME, [alloca.c], [], [
+ m4_define([gltests_LIBSOURCES_DIR], [tests])
+ m4_append([gltests_LIBSOURCES_LIST], _gl_NAME, [ ])
+ ])
+ ])
+])
+
+# This macro records the list of files which have been installed by
+# gnulib-tool and may be removed by future gnulib-tool invocations.
+AC_DEFUN([gl_FILE_LIST], [
+ lib/gl_anyrbtree_list1.h
+ lib/gl_anyrbtree_list2.h
+ lib/gl_anytree_list1.h
+ lib/gl_anytree_list2.h
+ lib/gl_list.c
+ lib/gl_list.h
+ lib/gl_rbtree_list.c
+ lib/gl_rbtree_list.h
+ lib/stdbool.in.h
+ m4/00gnulib.m4
+ m4/extern-inline.m4
+ m4/gnulib-common.m4
+ m4/stdbool.m4
+])
diff --git a/draft/mcastseed/m4/gnulib-tool.m4 b/draft/mcastseed/m4/gnulib-tool.m4
new file mode 100644
index 0000000..0d2ee44
--- /dev/null
+++ b/draft/mcastseed/m4/gnulib-tool.m4
@@ -0,0 +1,57 @@
+# gnulib-tool.m4 serial 2
+dnl Copyright (C) 2004-2005, 2009-2016 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+dnl The following macros need not be invoked explicitly.
+dnl Invoking them does nothing except to declare default arguments
+dnl for "gnulib-tool --import".
+
+dnl Usage: gl_LOCAL_DIR([DIR])
+AC_DEFUN([gl_LOCAL_DIR], [])
+
+dnl Usage: gl_MODULES([module1 module2 ...])
+AC_DEFUN([gl_MODULES], [])
+
+dnl Usage: gl_AVOID([module1 module2 ...])
+AC_DEFUN([gl_AVOID], [])
+
+dnl Usage: gl_SOURCE_BASE([DIR])
+AC_DEFUN([gl_SOURCE_BASE], [])
+
+dnl Usage: gl_M4_BASE([DIR])
+AC_DEFUN([gl_M4_BASE], [])
+
+dnl Usage: gl_PO_BASE([DIR])
+AC_DEFUN([gl_PO_BASE], [])
+
+dnl Usage: gl_DOC_BASE([DIR])
+AC_DEFUN([gl_DOC_BASE], [])
+
+dnl Usage: gl_TESTS_BASE([DIR])
+AC_DEFUN([gl_TESTS_BASE], [])
+
+dnl Usage: gl_WITH_TESTS
+AC_DEFUN([gl_WITH_TESTS], [])
+
+dnl Usage: gl_LIB([LIBNAME])
+AC_DEFUN([gl_LIB], [])
+
+dnl Usage: gl_LGPL or gl_LGPL([VERSION])
+AC_DEFUN([gl_LGPL], [])
+
+dnl Usage: gl_MAKEFILE_NAME([FILENAME])
+AC_DEFUN([gl_MAKEFILE_NAME], [])
+
+dnl Usage: gl_LIBTOOL
+AC_DEFUN([gl_LIBTOOL], [])
+
+dnl Usage: gl_MACRO_PREFIX([PREFIX])
+AC_DEFUN([gl_MACRO_PREFIX], [])
+
+dnl Usage: gl_PO_DOMAIN([DOMAIN])
+AC_DEFUN([gl_PO_DOMAIN], [])
+
+dnl Usage: gl_VC_FILES([BOOLEAN])
+AC_DEFUN([gl_VC_FILES], [])
diff --git a/draft/mcastseed/m4/stdbool.m4 b/draft/mcastseed/m4/stdbool.m4
new file mode 100644
index 0000000..a556153
--- /dev/null
+++ b/draft/mcastseed/m4/stdbool.m4
@@ -0,0 +1,104 @@
+# Check for stdbool.h that conforms to C99.
+
+dnl Copyright (C) 2002-2006, 2009-2016 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+#serial 6
+
+# Prepare for substituting <stdbool.h> if it is not supported.
+
+AC_DEFUN([AM_STDBOOL_H],
+[
+ AC_REQUIRE([AC_CHECK_HEADER_STDBOOL])
+
+ # Define two additional variables used in the Makefile substitution.
+
+ if test "$ac_cv_header_stdbool_h" = yes; then
+ STDBOOL_H=''
+ else
+ STDBOOL_H='stdbool.h'
+ fi
+ AC_SUBST([STDBOOL_H])
+ AM_CONDITIONAL([GL_GENERATE_STDBOOL_H], [test -n "$STDBOOL_H"])
+
+ if test "$ac_cv_type__Bool" = yes; then
+ HAVE__BOOL=1
+ else
+ HAVE__BOOL=0
+ fi
+ AC_SUBST([HAVE__BOOL])
+])
+
+# AM_STDBOOL_H will be renamed to gl_STDBOOL_H in the future.
+AC_DEFUN([gl_STDBOOL_H], [AM_STDBOOL_H])
+
+# This version of the macro is needed in autoconf <= 2.68.
+
+AC_DEFUN([AC_CHECK_HEADER_STDBOOL],
+ [AC_CACHE_CHECK([for stdbool.h that conforms to C99],
+ [ac_cv_header_stdbool_h],
+ [AC_COMPILE_IFELSE(
+ [AC_LANG_PROGRAM(
+ [[
+ #include <stdbool.h>
+
+ #if __cplusplus < 201103
+ #ifndef bool
+ "error: bool is not defined"
+ #endif
+ #ifndef false
+ "error: false is not defined"
+ #endif
+ #if false
+ "error: false is not 0"
+ #endif
+ #ifndef true
+ "error: true is not defined"
+ #endif
+ #if true != 1
+ "error: true is not 1"
+ #endif
+ #endif
+
+ #ifndef __bool_true_false_are_defined
+ "error: __bool_true_false_are_defined is not defined"
+ #endif
+
+ struct s { _Bool s: 1; _Bool t; } s;
+
+ char a[true == 1 ? 1 : -1];
+ char b[false == 0 ? 1 : -1];
+ char c[__bool_true_false_are_defined == 1 ? 1 : -1];
+ char d[(bool) 0.5 == true ? 1 : -1];
+ /* See body of main program for 'e'. */
+ char f[(_Bool) 0.0 == false ? 1 : -1];
+ char g[true];
+ char h[sizeof (_Bool)];
+ char i[sizeof s.t];
+ enum { j = false, k = true, l = false * true, m = true * 256 };
+ /* The following fails for
+ HP aC++/ANSI C B3910B A.05.55 [Dec 04 2003]. */
+ _Bool n[m];
+ char o[sizeof n == m * sizeof n[0] ? 1 : -1];
+ char p[-1 - (_Bool) 0 < 0 && -1 - (bool) 0 < 0 ? 1 : -1];
+ /* Catch a bug in an HP-UX C compiler. See
+ http://gcc.gnu.org/ml/gcc-patches/2003-12/msg02303.html
+ http://lists.gnu.org/archive/html/bug-coreutils/2005-11/msg00161.html
+ */
+ _Bool q = true;
+ _Bool *pq = &q;
+ ]],
+ [[
+ bool e = &s;
+ *pq |= q;
+ *pq |= ! q;
+ /* Refer to every declared value, to avoid compiler optimizations. */
+ return (!a + !b + !c + !d + !e + !f + !g + !h + !i + !!j + !k + !!l
+ + !m + !n + !o + !p + !q + !pq);
+ ]])],
+ [ac_cv_header_stdbool_h=yes],
+ [ac_cv_header_stdbool_h=no])])
+ AC_CHECK_TYPES([_Bool])
+])
diff --git a/draft/mcastseed/src/Makefile.am b/draft/mcastseed/src/Makefile.am
new file mode 100644
index 0000000..2f2a735
--- /dev/null
+++ b/draft/mcastseed/src/Makefile.am
@@ -0,0 +1,16 @@
+## Process this file with automake to produce Makefile.in
+
+AM_CPPFLAGS = -I $(top_srcdir)/lib
+AM_CFLAGS =\
+ -Wall \
+ -Wextra \
+ -pedantic \
+ -Wno-format
+
+bin_PROGRAMS = mcastseed mcastleech random_speed_dd
+
+mcastseed_SOURCES = mcastseed.c sockets.c
+mcastleech_SOURCES = mcastleech.c sockets.c dgrambuf.c
+mcastleech_LDADD = $(top_builddir)/lib/libgnu.a
+random_speed_dd_SOURCES = random_speed_dd.c
+
diff --git a/draft/mcastseed/src/dgrambuf.c b/draft/mcastseed/src/dgrambuf.c
new file mode 100644
index 0000000..5d4c302
--- /dev/null
+++ b/draft/mcastseed/src/dgrambuf.c
@@ -0,0 +1,583 @@
+/*
+ * dgrambuf.c - C datagrams buffer.
+ *
+ * Copyright 2016 by Ludovic Pouzenc <ludovic@pouzenc.fr>
+ */
+#define _GNU_SOURCE /* See feature_test_macros(7) */
+#include "dgrambuf.h"
+
+#include "config.h"
+
+#include <sys/socket.h> /* recvmmsg() _GNU_SOURCE */
+#include <stdlib.h> /* calloc(), free() */
+#include <stdio.h> /* perror() */
+#include <errno.h> /* errno */
+#include <string.h> /* memset() */
+#include <sys/uio.h> /* writev() */
+#include <stdint.h> /* uint8_t, uint64_t */
+#include <signal.h> /* sigaction() */
+#include <unistd.h> /* alarm() */
+#include <limits.h> /* SSIZE_MAX */
+#include "gl_rbtree_list.h" /* Red-Black Tree backed Sorted list, gnulib-tool --import rbtree-list */
+
+struct indexed_uint {
+ size_t index;
+ unsigned int value;
+};
+
+struct dgrambuf_stats_t {
+ uint64_t dgrambuf_read_on_full;
+ uint64_t recvmmsg_calls, recv_dgrams, recv_byte;
+ uint64_t dgram_invalid, dgram_past, dgram_future, dgram_dup, dgram_end_marker;
+ uint64_t writev_calls, write_partial, write_byte;
+};
+
+struct dgrambuf_t {
+ /* dgram validation after receive, takes dgram len and a pointer to the start of dgram data
+ Must returns dgram seq number or 0 if invalid dgram */
+ int (*validate_func)(unsigned int, void *, unsigned int*);
+
+ struct dgrambuf_stats_t stats;
+ struct sigaction sa_sigalrm;
+
+ size_t dgram_slots;
+ size_t dgram_max_size;
+ size_t dgram_header_size;
+
+ size_t iovec_slots;
+ struct mmsghdr *msgs;
+ struct iovec *iov_recv;
+ struct iovec *iov_write; /* malloc'ed array */
+
+ struct iovec *partial_write_iov; /* Pointer to an item of iov_write[] */
+ size_t partial_write_remaining_iovcnt;
+ size_t partial_write_remaining_bytes;
+
+ unsigned int dgram_seq_last;
+ unsigned int dgram_seq_base;
+ unsigned int *dgram_len;
+
+ struct indexed_uint *dgram_slot_seq; /* malloc'ed array */
+ struct indexed_uint **dgram_read_active_slots; /* malloc'd array of pointers to items of dgram_slot_seq[] */
+ size_t dgram_read_active_slots_count;
+ struct indexed_uint **dgram_write_active_slots; /* malloc'd array of pointers to items of dgram_slot_seq[] */
+ size_t dgram_write_active_slots_count;
+
+ gl_list_t dgram_empty_slots;
+ gl_list_t dgram_used_slots;
+
+ uint8_t *buf; /* malloc-ed 2d byte array : buf[dgram_slots][dgram_max_size] */
+};
+
+void _sigalrm_handler(int signum);
+int _compare_indexed_uint(const void *pa, const void *pb);
+bool _equals_indexed_uint(const void *pa, const void *pb);
+void _update_ordered_seq_numbers(dgrambuf_t dbuf);
+
+#ifndef HAVE_MIN_SIZE_T
+size_t min_size_t(size_t a, size_t b) { return (a<b)?a:b; }
+#endif /*HAVE_MIN_SIZE_T*/
+
+void dgrambuf_set_validate_func(dgrambuf_t dbuf, int (*validate_func)(unsigned int, void *, unsigned int *)) {
+ dbuf->validate_func = validate_func;
+}
+
+size_t dgrambuf_get_free_count(const dgrambuf_t dbuf) {
+ return gl_list_size(dbuf->dgram_empty_slots);
+}
+
+size_t dgrambuf_get_used_count(const dgrambuf_t dbuf) {
+ return gl_list_size(dbuf->dgram_used_slots);
+}
+
+ssize_t dgrambuf_recvmmsg(dgrambuf_t dbuf, int sockfd, int timeout, int *info) {
+ uint8_t *dgram_base;
+ ssize_t recv_byte;
+ size_t i, dgram_index, recv_msg_count, free_count;
+ int res;
+ unsigned int seq, dgram_len;
+ struct sigaction sa_old;
+ struct indexed_uint *active_slot;
+ gl_list_node_t pos;
+
+
+ /* Info ptr is mandatory */
+ *info = 0;
+
+ /* Validate function is mandatory */
+ if ( !dbuf->validate_func ) {
+ return -3;
+ }
+
+ /* Buffer is full, can't receive */
+ free_count = dgrambuf_get_free_count(dbuf);
+ if ( free_count == 0 ) {
+ dbuf->stats.dgrambuf_read_on_full++;
+ *info |= DGRAMBUF_RECV_OVERWRITE;
+ /*FIXME : this locks everything if buf full + next seq missing*/
+ return 0;
+ }
+
+ /* Initialize recvmmsg() syscall arguments and keep track of active slots */
+ for (i=0; i < dbuf->iovec_slots && i < free_count; i++) {
+ /* Pop a free slot, ignoring const modifier from gl_list_get_at() */
+ dbuf->dgram_read_active_slots[i] = (struct indexed_uint *) gl_list_get_at(dbuf->dgram_empty_slots, 0);
+ gl_sortedlist_remove(dbuf->dgram_empty_slots, _compare_indexed_uint, dbuf->dgram_read_active_slots[i]);
+
+ dgram_index = dbuf->dgram_read_active_slots[i]->index;
+ dbuf->iov_recv[i].iov_base = dbuf->buf + dgram_index * dbuf->dgram_max_size;
+ dbuf->iov_recv[i].iov_len = dbuf->dgram_max_size;
+
+ memset(dbuf->msgs + i, 0, sizeof(struct mmsghdr));
+ dbuf->msgs[i].msg_hdr.msg_iov = dbuf->iov_recv + i;
+ dbuf->msgs[i].msg_hdr.msg_iovlen = 1;
+ }
+ dbuf->dgram_read_active_slots_count = i;
+
+ /* Do the syscall with alarm() to circumvent bad behavior in recvmmsg(2) timeout */
+ if (timeout) {
+ sigaction(SIGALRM, &(dbuf->sa_sigalrm), &sa_old);
+ alarm(timeout);
+ }
+ res = recvmmsg(sockfd, dbuf->msgs, dbuf->dgram_read_active_slots_count, MSG_WAITFORONE, NULL);
+ if (timeout) {
+ alarm(0);
+ sigaction(SIGALRM, &sa_old, NULL);
+ }
+ dbuf->stats.recvmmsg_calls++;
+
+ if (res < 0) {
+ if ( errno == EINTR ) {
+ recv_msg_count = 0;
+ *info |= DGRAMBUF_RECV_EINTR;
+ } else {
+ perror("recvmmsg()");
+ return -1;
+ }
+ } else {
+ recv_msg_count = res;
+ }
+
+ if (recv_msg_count > 0) {
+ dbuf->stats.recv_dgrams += recv_msg_count;
+ if ( recv_msg_count == dbuf->dgram_read_active_slots_count ) {
+ *info |= DGRAMBUF_RECV_IOVEC_FULL;
+ }
+ }
+
+ /* Check all received messages */
+ for (i=0, recv_byte=0; i<recv_msg_count; i++) {
+ active_slot = dbuf->dgram_read_active_slots[i];
+ dgram_base = dbuf->iov_recv[i].iov_base;
+ dgram_len = dbuf->msgs[i].msg_len;
+
+ /* dgrambuf_new() adjust iovec_len to prevent overflows on ssize_t*/
+ recv_byte += dgram_len;
+
+ res = dbuf->validate_func(dgram_len, dgram_base, &seq);
+ switch (res) {
+ case 1:
+ if ( seq < dbuf->dgram_seq_base ) {
+ fprintf(stderr, "dgrambuf_recvmmsg(): #%zu past (%u)\n", i, seq);
+ dbuf->stats.dgram_past++;
+ } else if ( seq >= dbuf->dgram_seq_base + dbuf->dgram_slots ) {
+ fprintf(stderr, "dgrambuf_recvmmsg(): #%zu future (%u)\n", i, seq);
+ dbuf->stats.dgram_future++;
+ *info |= DGRAMBUF_RECV_FUTURE_DGRAM;
+ } else {
+ active_slot->value = seq;
+ pos = gl_sortedlist_search(dbuf->dgram_used_slots, _compare_indexed_uint, active_slot);
+ if ( pos != NULL ) {
+ fprintf(stderr, "dgrambuf_recvmmsg(): #%zu duplicate (%u)\n", i, seq);
+ dbuf->stats.dgram_dup++;
+ *info |= DGRAMBUF_RECV_DUPLICATE_DGRAM;
+ } else {
+ /*fprintf(stderr, "dgrambuf_recvmmsg(): #%zu valid (%u)\n", i, seq);*/
+ pos = gl_sortedlist_nx_add(dbuf->dgram_used_slots, _compare_indexed_uint, active_slot);
+ if ( pos == NULL ) /*TODO: better oom handling */
+ return -4;
+ dbuf->dgram_len[active_slot->index] = dgram_len;
+ *info |= DGRAMBUF_RECV_VALID_DGRAM;
+ continue;
+ }
+ }
+ break;
+ case 2:
+ fprintf(stderr, "dgrambuf_recvmmsg(): #%zu finalize (%u)\n", i, seq);
+ dbuf->stats.dgram_end_marker++;
+ dbuf->dgram_seq_last = seq;
+ *info |= DGRAMBUF_RECV_FINALIZE;
+ break;
+ default:
+ fprintf(stderr, "dgrambuf_recvmmsg(): #%zu invalid\n", i);
+ dbuf->stats.dgram_invalid++;
+ break;
+ }
+ /* In all invalid dgram cases, put back active_slot in dgram_free_slots */
+ pos = gl_sortedlist_nx_add(dbuf->dgram_empty_slots, _compare_indexed_uint, active_slot);
+ if ( !pos ) /*TODO: better oom handling */
+ return -4;
+ }
+
+ /* Push remaining active slots in dgram_empty_slots */
+ for (/*next i*/; i < dbuf->dgram_read_active_slots_count; i++) {
+ active_slot = dbuf->dgram_read_active_slots[i];
+ pos = gl_sortedlist_nx_add(dbuf->dgram_empty_slots, _compare_indexed_uint, active_slot);
+ if ( !pos ) /*TODO: better oom handling */
+ return -4;
+ }
+
+ dbuf->dgram_read_active_slots_count = 0;
+ dbuf->stats.recv_byte += recv_byte;
+
+ return recv_byte;
+}
+
+int dgrambuf_have_data_ready_to_write(dgrambuf_t dbuf) {
+ unsigned int next_dgram_seq;
+
+ /* Last write was partial, so there is more to write */
+ if ( dbuf->partial_write_remaining_bytes ) {
+ return 1;
+ }
+
+ /* dgram_used_slots is empty, nothing to write */
+ if ( dgrambuf_get_used_count(dbuf) == 0 ) {
+ return 0;
+ }
+
+ /* Nothing to write if next dgram is not in buffer at all */
+ next_dgram_seq = ((struct indexed_uint *) gl_list_get_at(dbuf->dgram_used_slots, 0))->value;
+ /*fprintf(stderr, "DEBUG : dgram_seq_base==%u next_dgram_seq == %u\n", dbuf->dgram_seq_base, next_dgram_seq);*/
+ if ( next_dgram_seq != dbuf->dgram_seq_base ) {
+ return 0;
+ }
+ /* At least some data of one dgram is availble for writing out */
+ return 1;
+}
+
+int dgrambuf_have_received_everything(dgrambuf_t dbuf) {
+ /*FIXME : Really implement this */
+ return dbuf->dgram_seq_last && ( dbuf->dgram_seq_base - 1 == dbuf->dgram_seq_last );
+}
+
+ssize_t dgrambuf_write(dgrambuf_t dbuf, int fd, int *info) {
+ size_t dgram_index, i, vlen, total, len, remain, used_count;
+ unsigned int curr_seq, prev_seq, dgram_len;
+ ssize_t nwrite;
+ struct iovec *iov;
+ struct indexed_uint *active_slot;
+ bool pos;
+
+ /* FIXME Info ptr is mandatory */
+ *info = 0;
+
+ if ( dbuf->partial_write_remaining_bytes ) {
+ /* Previous writev() was partial, continue it */
+ iov = dbuf->partial_write_iov;
+ vlen = dbuf->partial_write_remaining_iovcnt;
+ total = dbuf->partial_write_remaining_bytes;
+ } else if ( ! dgrambuf_have_data_ready_to_write(dbuf) ) {
+ return 0; /* XXX Inline code ? */
+ } else {
+ /* Prepare a write batch, buffer state is in dgram_seq_numbers */
+ iov = dbuf->iov_write;
+ total = 0;
+
+ /* Initialize iovecs for writev, take dgram payloads following the sequence numbers */
+ prev_seq = 0;
+ used_count = dgrambuf_get_used_count(dbuf);
+ for (i = 0; i < dbuf->iovec_slots && i < used_count; i++) {
+ /* Pop a used slot */
+ dbuf->dgram_write_active_slots[i] = (struct indexed_uint *) gl_list_get_at(dbuf->dgram_used_slots, 0);
+ gl_sortedlist_remove(dbuf->dgram_used_slots, _compare_indexed_uint, dbuf->dgram_write_active_slots[i]);
+ dbuf->dgram_write_active_slots_count++;
+
+ curr_seq = dbuf->dgram_write_active_slots[i]->value;
+
+ /* Skip empty dgram slot */
+ if ( curr_seq == 0 ) {
+ fprintf(stderr, "Oops : found empty slot (i==%zu)\n", i);
+ continue;
+ }
+ /* Skip if current dgram is a dup of the previous */
+ if ( curr_seq == prev_seq ) {
+ fprintf(stderr, "Oops : found duplicated dgram in buffer (%u)\n", curr_seq);
+ continue;
+ }
+ /* Skip dgram comming from the past */
+ if ( curr_seq < dbuf->dgram_seq_base ) {
+ fprintf(stderr, "Oops : found dgram from past in buffer (%u)\n", curr_seq);
+ continue;
+ }
+ /* Stop if current seq dgram is missing */
+ if ( ( i > 0 ) && (curr_seq > prev_seq+1 ) ) {
+ break;
+ }
+ /* Stop if first dgram to write is not in buffer at all */
+ if ( ( i == 0 ) && (curr_seq != dbuf->dgram_seq_base) ) {
+ fprintf(stderr, "Oops : nothing to write, missing %u seq\n", dbuf->dgram_seq_base);
+ break;
+ }
+
+ /* Normal case : curr_seq is the next dgram to write */
+ dgram_index = dbuf->dgram_write_active_slots[i]->index;
+ dgram_len = dbuf->dgram_len[dgram_index] - dbuf->dgram_header_size;
+
+ /* Setup iovecs */
+ dbuf->iov_write[i].iov_len = dgram_len;
+ dbuf->iov_write[i].iov_base = dbuf->buf
+ + dgram_index*dbuf->dgram_max_size + dbuf->dgram_header_size;
+
+ /* Update counters */
+ total += dgram_len;
+ prev_seq = curr_seq;
+ dbuf->dgram_seq_base = curr_seq + 1;
+ }
+ vlen = i;
+
+ /* Nothing valid to write out (but buffer not empty, missing the next dgram) */
+ if ( vlen == 0 ) {
+ fprintf(stderr, "Oops : nothing to write at all\n");
+ return -2;
+ }
+
+ if ( vlen == dbuf->iovec_slots ) {
+ *info |= DGRAMBUF_WRITE_IOVEC_FULL;
+ }
+ }
+
+ nwrite = writev(fd, iov, vlen);
+ dbuf->stats.writev_calls++;
+ if ( nwrite < 0 ) {
+ /* Treat non fatal errors */
+ if ( errno == EAGAIN || errno == EWOULDBLOCK || errno == EINTR) {
+ /* Keeps some state informations for retry */
+ dbuf->partial_write_remaining_bytes = total;
+ dbuf->partial_write_remaining_iovcnt = vlen;
+ dbuf->partial_write_iov = iov;
+ *info |= DGRAMBUF_WRITE_EWOULDBLOCK_OR_EINTR;
+ return 0;
+ }
+ /* Print fatal errors and bail out */
+ perror("writev()");
+ return -1;
+ }
+
+ dbuf->partial_write_remaining_bytes = total - nwrite;
+ if ( nwrite > 0 ) {
+ dbuf->stats.write_byte += nwrite;
+ *info |= DGRAMBUF_WRITE_SUCCESS;
+
+ if ( dbuf->partial_write_remaining_bytes ) {
+ /* If the write was partially done */
+ *info |= DGRAMBUF_WRITE_PARTIAL;
+ dbuf->stats.write_partial++;
+ /* Find the partially written iov and update it */
+ remain = nwrite;
+ for (i=0; i<vlen; i++) {
+ len = dbuf->iov_write[i].iov_len;
+ if ( remain < len ) {
+ dbuf->partial_write_remaining_iovcnt = vlen - i;
+ if ( dbuf->partial_write_iov ) {
+ dbuf->partial_write_iov += i;
+ } else {
+ dbuf->partial_write_iov = dbuf->iov_write + i;
+ }
+
+ dbuf->iov_write[i].iov_base =
+ (uint8_t *) dbuf->iov_write[i].iov_base + remain;
+ dbuf->iov_write[i].iov_len -= remain;
+ break;
+ }
+ remain -= len;
+ }
+ if ( i == vlen ) {
+ fprintf(stderr, "Fatal : failed to find partial iov after partial write\n");
+ return -3;
+ }
+
+ } else {
+ /* Full write has happened */
+ for (i=0; i<dbuf->dgram_write_active_slots_count; i++) {
+ active_slot = (struct indexed_uint *) dbuf->dgram_write_active_slots[i];
+ active_slot->value = 0;
+ pos = gl_sortedlist_nx_add(dbuf->dgram_empty_slots, _compare_indexed_uint, active_slot);
+ if ( !pos ) /*TODO: better oom handling ? */
+ return -4;
+ }
+ dbuf->dgram_write_active_slots_count = 0;
+ /* Wipe outdated partial_* values */
+ dbuf->partial_write_iov = NULL;
+ dbuf->partial_write_remaining_iovcnt = 0;
+ }
+ }
+
+ return nwrite;
+}
+
+int dgrambuf_stats(dgrambuf_t dbuf, char **allocated_string) {
+ uint64_t dgram_pending = dgrambuf_get_used_count(dbuf);
+ uint64_t dgram_missing = 0;
+ if ( dbuf->dgram_seq_last ) {
+ dgram_missing = dbuf->dgram_seq_last - (dbuf->dgram_seq_base - 1) - dgram_pending;
+ }
+
+ return asprintf(allocated_string,
+ "dgrambuf_read_on_full==%d "
+ "recvmmsg_calls==%d, recv_dgrams==%d, recv_byte==%d, "
+ "dgram_invalid==%d, dgram_past==%d, dgram_future==%d, dgram_dup==%d, dgram_end_marker==%d, "
+ "writev_calls==%d, write_partial==%d, write_byte==%d "
+ "dgram_pending==%d, dgram_missing==%d",
+ dbuf->stats.dgrambuf_read_on_full,
+ dbuf->stats.recvmmsg_calls, dbuf->stats.recv_dgrams, dbuf->stats.recv_byte,
+ dbuf->stats.dgram_invalid, dbuf->stats.dgram_past, dbuf->stats.dgram_future, dbuf->stats.dgram_dup, dbuf->stats.dgram_end_marker,
+ dbuf->stats.writev_calls, dbuf->stats.write_partial, dbuf->stats.write_byte,
+ dgram_pending, dgram_missing
+ );
+}
+
+dgrambuf_t dgrambuf_new(size_t dgram_slots, size_t dgram_max_size, size_t dgram_header_size, size_t iovec_slots) {
+
+ const void **dgram_slot_seq_ptrs = NULL;
+ dgrambuf_t dbuf;
+ size_t i;
+
+ dbuf = calloc(1, sizeof(struct dgrambuf_t));
+ if (!dbuf) goto fail0;
+
+ dbuf->validate_func = NULL;
+ /* Implicit with dbuf = calloc(...)
+ memset(&(dbuf->stats), 0, sizeof(struct dgrambuf_stats_t));
+ memset(&(dbuf->sa_sigalrm), 0, sizeof(struct sigaction));
+ */
+ dbuf->sa_sigalrm.sa_handler = _sigalrm_handler;
+
+ dbuf->dgram_slots = dgram_slots;
+ dbuf->dgram_max_size = dgram_max_size;
+ dbuf->dgram_header_size = dgram_header_size;
+
+ /* writev() and dgrambuf_recvmmsg accumulates read/write bytes in ssize_t */
+ iovec_slots = min_size_t(iovec_slots, SSIZE_MAX/dgram_max_size);
+ dbuf->iovec_slots = iovec_slots;
+
+ dbuf->msgs = calloc(iovec_slots, sizeof(struct mmsghdr));
+ if (!dbuf->msgs) goto fail1;
+
+ dbuf->iov_recv = calloc(iovec_slots, sizeof(struct iovec));
+ if (!dbuf->iov_recv) goto fail2;
+
+ dbuf->iov_write = calloc(iovec_slots, sizeof(struct iovec));
+ if (!dbuf->iov_write) goto fail3;
+
+ /* Implicit with dbuf = calloc(...)
+ dbuf->partial_write_iov = NULL;
+ dbuf->partial_write_remaining_iovcnt = 0;
+ dbuf->partial_write_remaining_bytes = 0;
+
+ dbuf->dgram_seq_last = 0;
+ */
+ dbuf->dgram_seq_base = 1;
+ dbuf->dgram_len = calloc(dgram_slots, sizeof(unsigned int));
+ if (!dbuf->dgram_len) goto fail4;
+
+ dbuf->dgram_slot_seq = calloc(dgram_slots, sizeof(struct indexed_uint));
+ if (!dbuf->dgram_slot_seq) goto fail5;
+ for (i=0; i<dgram_slots; i++) {
+ dbuf->dgram_slot_seq[i].index = i;
+ }
+
+ /* Implicit with dbuf = calloc(...)
+ dbuf->dgram_read_active_slots_count = 0;
+ */
+ dbuf->dgram_read_active_slots = calloc(iovec_slots, sizeof(struct indexed_uint *));
+ if (!dbuf->dgram_read_active_slots) goto fail6;
+
+ /* Implicit with dbuf = calloc(...)
+ dbuf->dgram_write_active_slots_count = 0;
+ */
+ dbuf->dgram_write_active_slots = calloc(iovec_slots, sizeof(struct indexed_uint *));
+ if (!dbuf->dgram_write_active_slots) goto fail7;
+
+ dgram_slot_seq_ptrs = calloc(dgram_slots, sizeof(void *));
+ for (i=0; i<dgram_slots; i++) {
+ dbuf->dgram_slot_seq[i].index = i;
+ dgram_slot_seq_ptrs[i] = &(dbuf->dgram_slot_seq[i]);
+ }
+ if (!dgram_slot_seq_ptrs) goto fail7;
+
+ dbuf->dgram_empty_slots = gl_list_nx_create(GL_RBTREE_LIST, _equals_indexed_uint,
+ NULL, NULL, false, dgram_slots, dgram_slot_seq_ptrs);
+ if (!dbuf->dgram_empty_slots) goto fail8;
+
+ free(dgram_slot_seq_ptrs);
+ dgram_slot_seq_ptrs=NULL;
+
+ dbuf->dgram_used_slots = gl_list_nx_create_empty(GL_RBTREE_LIST, _equals_indexed_uint,
+ NULL, NULL, false);
+ if (!dbuf->dgram_used_slots) goto fail9;
+
+ dbuf->buf = calloc(dgram_slots, dgram_max_size);
+ if (!dbuf->buf) goto fail10;
+
+ return dbuf;
+
+fail10: gl_list_free(dbuf->dgram_used_slots);
+fail9: gl_list_free(dbuf->dgram_empty_slots);
+fail8: free(dbuf->dgram_write_active_slots);
+fail7: free(dbuf->dgram_read_active_slots);
+fail6: free(dbuf->dgram_slot_seq);
+fail5: free(dbuf->dgram_len);
+fail4: free(dbuf->iov_write);
+fail3: free(dbuf->iov_recv);
+fail2: free(dbuf->msgs);
+fail1: free(dbuf);
+fail0: return NULL;
+}
+
+void dgrambuf_free(dgrambuf_t *dbuf) {
+ if (dbuf && *dbuf) {
+ free((*dbuf)->buf);
+ gl_list_free((*dbuf)->dgram_used_slots);
+ gl_list_free((*dbuf)->dgram_empty_slots);
+ free((*dbuf)->dgram_write_active_slots);
+ free((*dbuf)->dgram_read_active_slots);
+ free((*dbuf)->dgram_slot_seq);
+ free((*dbuf)->dgram_len);
+ free((*dbuf)->iov_write);
+ free((*dbuf)->iov_recv);
+ free((*dbuf)->msgs);
+ free(*dbuf);
+ *dbuf = NULL;
+ }
+}
+
+void _sigalrm_handler(int signum) {
+ /* Nothing to do except interrupting the pending syscall */
+ if (signum) {} /* Avoid compiler warning */
+}
+
+int _compare_indexed_uint(const void *pa, const void *pb) {
+ const struct indexed_uint *a = pa;
+ const struct indexed_uint *b = pb;
+ if (a->value < b->value)
+ return -1;
+ else if ( a->value > b->value )
+ return 1;
+ else
+ return 0;
+/*
+ if (a->index < b->index)
+ return -1;
+ else if (a->index > b->index)
+ return 1;
+ else
+ return 0;
+*/
+}
+
+bool _equals_indexed_uint(const void *pa, const void *pb) {
+ const struct indexed_uint *a = pa;
+ const struct indexed_uint *b = pb;
+ return (a->value == b->value) /*&& (a->index == b->index)*/;
+}
diff --git a/draft/mcastseed/src/dgrambuf.h b/draft/mcastseed/src/dgrambuf.h
new file mode 100644
index 0000000..a83647b
--- /dev/null
+++ b/draft/mcastseed/src/dgrambuf.h
@@ -0,0 +1,41 @@
+#ifndef DGRAMBUF_H
+#define DGRAMBUF_H
+/*
+ * dgrambuf.c - C datagrams buffer.
+ *
+ * Copyright 2016 by Ludovic Pouzenc <ludovic@pouzenc.fr>
+ */
+#include <stdlib.h> /* size_t */
+
+#define DGRAMBUF_RECV_OVERWRITE 1 << 1
+#define DGRAMBUF_RECV_EINTR 1 << 2
+#define DGRAMBUF_RECV_IOVEC_FULL 1 << 3
+#define DGRAMBUF_RECV_FINALIZE 1 << 4
+#define DGRAMBUF_RECV_FUTURE_DGRAM 1 << 5
+#define DGRAMBUF_RECV_DUPLICATE_DGRAM 1 << 6
+#define DGRAMBUF_RECV_VALID_DGRAM 1 << 6
+
+#define DGRAMBUF_WRITE_PARTIAL 1 << 1
+#define DGRAMBUF_WRITE_EWOULDBLOCK_OR_EINTR 1 << 2
+#define DGRAMBUF_WRITE_IOVEC_FULL 1 << 3
+#define DGRAMBUF_WRITE_SUCCESS 1 << 4
+
+typedef struct dgrambuf_t *dgrambuf_t;
+
+dgrambuf_t dgrambuf_new(size_t dgram_slots, size_t dgram_max_size, size_t dgram_header_size, size_t iovec_slots);
+void dgrambuf_free(dgrambuf_t *);
+
+void dgrambuf_set_validate_func(dgrambuf_t dbuf, int (*validate_func)(unsigned int, void *, unsigned int *));
+
+size_t dgrambuf_get_free_count(const dgrambuf_t);
+size_t dgrambuf_get_used_count(const dgrambuf_t);
+int dgrambuf_have_data_ready_to_write(const dgrambuf_t);
+int dgrambuf_have_received_everything(const dgrambuf_t);
+
+int dgrambuf_stats(dgrambuf_t dbuf, char **allocated_string);
+
+/* Warning : dgrambuf_recvmmsg sets and restore SIGALRM handler if timeout != 0 */
+ssize_t dgrambuf_recvmmsg(dgrambuf_t dbuf, int sockfd, int timeout, int *info);
+ssize_t dgrambuf_write(dgrambuf_t dbuf, int fd, int *info);
+
+#endif /* DGRAMBUF_H */
diff --git a/draft/mcastseed/src/dgrambuf_test.c b/draft/mcastseed/src/dgrambuf_test.c
new file mode 100644
index 0000000..6f9ef22
--- /dev/null
+++ b/draft/mcastseed/src/dgrambuf_test.c
@@ -0,0 +1,50 @@
+#include "dgrambuf.h"
+
+#define _GNU_SOURCE
+#include <netinet/ip.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/socket.h>
+
+int open_test_socket();
+
+/*
+ * Quick'n'dirty bash udp sender
+ * while true; do echo $RANDOM > /dev/udp/127.0.0.1/1234; sleep 0.25; done
+ */
+
+int main() {
+ int res, sockfd, info;
+ dgrambuf_t dgb;
+
+ sockfd = open_test_socket();
+ dgb = dgrambuf_new(3, 50, 8, 8);
+
+ do {
+ res = dgrambuf_recvmmsg(dgb, sockfd, 1, &info);
+ printf("dgrambuf_recvmmsg() => %i\n", res);
+ printf("dgrambuf_free_count => %zu\n", dgrambuf_get_free_count(dgb));
+ } while ( res > 0 );
+ return 0;
+}
+
+int open_test_socket() {
+ int sockfd;
+ struct sockaddr_in sa;
+ sockfd = socket(AF_INET, SOCK_DGRAM, 0);
+ if (sockfd == -1) {
+ perror("socket()");
+ exit(EXIT_FAILURE);
+ }
+
+ sa.sin_family = AF_INET;
+ sa.sin_addr.s_addr = htonl(INADDR_LOOPBACK);
+ sa.sin_port = htons(1234);
+ if (bind(sockfd, (struct sockaddr *) &sa, sizeof(sa)) == -1) {
+ perror("bind()");
+ exit(EXIT_FAILURE);
+ }
+
+ return sockfd;
+}
diff --git a/draft/mcastseed/src/mcastleech.c b/draft/mcastseed/src/mcastleech.c
new file mode 100644
index 0000000..3345665
--- /dev/null
+++ b/draft/mcastseed/src/mcastleech.c
@@ -0,0 +1,408 @@
+/*
+ * mcastleech.c - Multicast client for huge streams to be piped to other programs (partitions cloning)
+ *
+ * Copyright 2016 by Ludovic Pouzenc <ludovic@pouzenc.fr>
+ *
+ * Greatly inspired from examples written by tmouse, July 2005
+ * http://cboard.cprogramming.com/showthread.php?t=67469
+ */
+#define _GNU_SOURCE /* See feature_test_macros(7) */
+#include "config.h"
+
+#include <unistd.h> /* close() */
+#include <stdio.h> /* fprintf(), stderr */
+#include <stdlib.h> /* EXIT_SUCCESS */
+#include <string.h> /* strncmp() */
+#include <fcntl.h> /* fcntl() */
+#include "sockets.h"
+#include "dgrambuf.h"
+
+#define MTU 1500
+#define MULTICAST_RECV_BUF (MTU-20-8)
+#define MULTICAST_SO_RCVBUF_WANTED 425984
+#define MAX_IOVEC (MULTICAST_SO_RCVBUF_WANTED / MULTICAST_RECV_BUF)
+#define DGRAM_HEADER_SIZE 8
+
+#define DEFAULT_MCAST_IP_STR "ff02::114"
+#define DEFAULT_PORT_STR "9000"
+
+/* Cmdline Arguments */
+char *prog_name = NULL;
+char *mcast_ip = NULL;
+char *port = NULL;
+
+/* Sockets as global, used everywhere, even in die() */
+int mcast_sock = -1; /* Multicast socket for receiving data */
+int ucast_sock = -1; /* Unicast socket for give feedback to server */
+
+/* Buffer used for earch recvfrom() */
+char recvbuf[MULTICAST_RECV_BUF];
+/* Huge ring buffer to absorb consumer speed variations without loosing datagrams */
+dgrambuf_t dgrambuf;
+
+/* Strings to print out representation of various states of the program */
+const char * const state_str[] = {
+ "start",
+ "wait_hello_and_connect_back",
+ "wait_start_and_start_job",
+ "receive_data",
+ "finalize_job",
+ "is_there_more_job"
+};
+
+/* Some boring funcs you didn't want to read now */
+void die(char* msg);
+void usage(char *msg);
+void arg_parse(int argc, char* argv[]);
+void fsm_trace(int state);
+int get_available_mem_kb();
+void set_O_NONBLOCK(int fd, int set);
+void dgrambuf_init();
+int validate_data_dgram(unsigned int nread, void *recvbuf, unsigned int *seq);
+int send_status(int state, int info_r, int info_w);
+
+/* Parts of the "protocol", definitions are after main() */
+int wait_hello_and_connect_back();
+int wait_start_and_start_job();
+int receive_data();
+int finalize_job();
+int is_there_more_job();
+
+int main(int argc, char* argv[]) {
+ int state = 1; /* state of the "protocol" state machine */
+ int res;
+
+ arg_parse(argc, argv);
+ dgrambuf_init();
+
+ /*XXX Maybe elsewhere, when popen'ing target program */
+ set_O_NONBLOCK(1, 1);
+
+/* XXX Dummy */
+ fcntl(1, F_SETPIPE_SZ, 4096);
+ fprintf(stderr, "pipe_size==%i\n", fcntl(1, F_GETPIPE_SZ));
+ /* Finite state machine */
+ while ( state > 0 ) {
+ fsm_trace(state);
+ switch ( state ) {
+ case 1: state = (wait_hello_and_connect_back() == 0)?2:1; break;
+ case 2: state = (wait_start_and_start_job() == 0)?2:3; break;
+ case 3:
+ res = receive_data();
+ if (res==0) state = 4;
+ else if (res==1) state=3;
+ else state = -1;
+ break;
+ case 4: state = (finalize_job() == 0)?5:-2; break;
+ case 5: state = (is_there_more_job() == 0)?2:0; break; /* XXX Should retry recv ? */
+ }
+ }
+ fsm_trace(state);
+
+ if ( mcast_sock > 0 ) {
+ close(mcast_sock);
+ mcast_sock = -1;
+ }
+
+ dgrambuf_free(&dgrambuf);
+
+ if ( state < 0 ) {
+ return -state;
+ }
+
+ return EXIT_SUCCESS;
+}
+
+
+int wait_hello_and_connect_back() {
+ /* Buffers for host and service strings after resolve */
+ char hbuf[NI_MAXHOST], sbuf[NI_MAXSERV];
+ /* Server address, filled by system after first recvfrom */
+ struct sockaddr_storage peer_addr;
+ socklen_t peer_addr_len;
+ /* Various needed variables */
+ ssize_t nread;
+ int res;
+
+ /* Setup mcast_sock */
+ if ( mcast_sock > 0 ) {
+ close(mcast_sock);
+ mcast_sock = -1;
+ }
+ mcast_sock = mcast_recv_socket(mcast_ip, port, MULTICAST_SO_RCVBUF_WANTED);
+ if(mcast_sock < 0) {
+ usage("Could not setup multicast socket. Wrong args given ?");
+ }
+
+ /* Wait for a single datagram from the server (for sync, no check on contain) */
+ peer_addr_len = sizeof(struct sockaddr_storage);
+ nread = recvfrom(mcast_sock, recvbuf, MULTICAST_RECV_BUF, 0, (struct sockaddr *) &peer_addr, &peer_addr_len);
+ if (nread < 0 ) {
+ perror("recvfrom() failed");
+ return -1;
+ }
+ /* Get peer informations as strings from peer_addr */
+ res = getnameinfo((struct sockaddr *) &peer_addr, peer_addr_len,
+ hbuf, NI_MAXHOST, sbuf, NI_MAXSERV, NI_NUMERICSERV);
+ if ( res != 0 ) {
+ fprintf(stderr, "getnameinfo: %s\n", gai_strerror(res));
+ return -2;
+ }
+ /* Connect back to the server, with reliable unicast */
+ if ( ucast_sock > 0 ) {
+ close(ucast_sock);
+ }
+ /* FIXME : ucast_client_socket() use DNS resolver and could block */
+ ucast_sock = ucast_client_socket(hbuf,port);
+ if(ucast_sock < 0) {
+ fprintf(stderr, "Could not setup unicast socket or connect to %s:%s\n", hbuf, port);
+ return -3;
+ }
+
+ return 0;
+}
+
+int wait_start_and_start_job() {
+ ssize_t nread, nwrite;
+
+ /* Wait for a "start" datagram from the server */
+ nread = recvfrom(mcast_sock, recvbuf, MULTICAST_RECV_BUF, 0, NULL, 0);
+ if (nread < 0 ) {
+ perror("recvfrom() failed");
+ return -1;
+ }
+ if ( nread >= 5 && strncmp("start", recvbuf, 5) == 0 ) {
+ /* Reply "ready" through unicast stream socket */
+ nwrite = write(ucast_sock, "ready", 5);
+ if ( nwrite < 0 ) {
+ fprintf(stderr, "write() failed\n");
+ return -2;
+ }
+ if (nwrite != 5) {
+ fprintf(stderr, "write() short\n");
+ return -3;
+ }
+
+ return 1;
+ }
+
+ return 0;
+}
+
+/*
+#define DGRAMBUF_RECV_OVERWRITE 1 << 1
+#define DGRAMBUF_RECV_EINTR 1 << 2
+#define DGRAMBUF_RECV_IOVEC_FULL 1 << 3
+#define DGRAMBUF_RECV_FINALIZE 1 << 4
+#define DGRAMBUF_RECV_VALID_DGRAM 1 << 5
+
+#define DGRAMBUF_WRITE_PARTIAL 1 << 1
+#define DGRAMBUF_WRITE_EWOULDBLOCK_OR_EINTR 1 << 2
+#define DGRAMBUF_WRITE_IOVEC_FULL 1 << 3
+#define DGRAMBUF_WRITE_SUCCESS 1 << 4
+*/
+int receive_data() {
+ int info_r, info_w, res;
+ ssize_t nread, nwrite;
+ static int noop_calls_count = 0;
+
+ /* Read (blocking, timeout = 1 sec) */
+ nread = dgrambuf_recvmmsg(dgrambuf, mcast_sock, 1, &info_r);
+ if ( nread < 0 ) {
+ return nread;
+ }
+
+ /* Write (non-blocking) */
+ nwrite = dgrambuf_write(dgrambuf, 1, &info_w);
+ if ( nwrite < 0 ) {
+ return nwrite;
+ }
+
+ /*fprintf(stderr, "receive_data(): nread == %zi, nwrite == %zi\n", nread, nwrite);*/
+
+ /* XXX Crapy dead state detection */
+ if ( nread == 0 /* TEST && nwrite == 0 */ ) {
+ if ( noop_calls_count > 10 ) {
+ return 0;
+ }
+ noop_calls_count++;
+ } else {
+ noop_calls_count = 0;
+ }
+
+ /* Consider sending status back to seeder */
+ res = send_status(1, info_r, info_w);
+ if ( res < 0 ) {
+ return res;
+ }
+
+ if ( dgrambuf_have_received_everything(dgrambuf) ) {
+ return 0;
+ }
+ return 1;
+}
+
+
+int finalize_job() {
+ ssize_t nwrite;
+ int info_w, res;
+ char *stats;
+
+ /* Don't eat reources in a pooling fashion, blocking IO is fine when no more recv to do */
+ set_O_NONBLOCK(1, 0);
+
+ /* Flush the whole buffer */
+ do {
+ nwrite = dgrambuf_write(dgrambuf, 1, &info_w);
+ if ( nwrite < 0 ) {
+ return nwrite;
+ }
+ fprintf(stderr, "finalize_job(): nwrite == %zi\n", nwrite);
+ } while ( nwrite > 0);
+
+ /* Inform the seeder that have have finished */
+ res = send_status(2, 0, info_w);
+ if ( res < 0 ) {
+ return res;
+ }
+
+ res = dgrambuf_stats(dgrambuf, &stats);
+ if ( res != - 1 ) {
+ fprintf(stderr, "finalize_job(): dgrambuf_stats : %s\n",stats);
+ free(stats);
+ }
+ return 0;
+}
+
+int is_there_more_job() {
+ return 1;
+}
+
+
+
+
+void die(char* msg) {
+ fprintf(stderr, "%s\n", msg);
+ if (mcast_sock > 0)
+ close(mcast_sock);
+ if (ucast_sock > 0)
+ close(ucast_sock);
+ exit(EXIT_FAILURE);
+}
+
+void usage(char *msg) {
+ char ubuf[256];
+ if ( msg != NULL )
+ fprintf(stderr, "%s\n", msg);
+ ubuf[0] = '\0';
+ snprintf(ubuf, 255, "Usage: %s [port] [mcast_ip]\n", prog_name);
+ die(ubuf);
+}
+
+void arg_parse(int argc, char* argv[]) {
+ prog_name = argv[0];
+ if ( argc > 3 )
+ usage("Too many arguments");
+ port = (argc >= 2)?argv[1]:DEFAULT_PORT_STR;
+ mcast_ip = (argc >= 3)?argv[2]:DEFAULT_MCAST_IP_STR;
+}
+
+void fsm_trace(int state) {
+ static int prev_state = 0;
+
+ if ( state < 0 ) {
+ fprintf(stderr, "Abnormal exit condition %i (from %s)\n", state, state_str[prev_state]);
+ } else if ( prev_state != state) {
+ if ( state == 0 ) {
+ fprintf(stderr, "Normal exit (from %s)\n", state_str[prev_state]);
+ } else {
+ fprintf(stderr, "Now in %s (from %s)\n", state_str[state], state_str[prev_state]);
+ }
+ prev_state = state;
+ }
+}
+
+int get_available_mem_kb() {
+ char key[64];
+ int res, value, found=0;
+ FILE * fh = fopen("/proc/meminfo", "r");
+ if ( fh ) {
+ while (!found && !feof(fh)) {
+ res = fscanf(fh, "%63s %i kB\n", key, &value);
+ if ( res < 0 )
+ break;
+ found = ( strncmp("MemAvailable:", key, 12) == 0 );
+ }
+ fclose(fh);
+ }
+
+ if ( found && value > 0 ) {
+ return value;
+ }
+
+ return 0;
+}
+
+void set_O_NONBLOCK(int fd, int set) {
+ int res, flags;
+
+ flags = fcntl(fd, F_GETFL);
+ if ( flags == -1 ) {
+ perror("fcntl(1, F_GETFL)");
+ }
+ if ( set ) {
+ res = fcntl(fd, F_SETFL, flags | O_NONBLOCK);
+ } else {
+ res = fcntl(fd, F_SETFL, flags & !O_NONBLOCK);
+ }
+ if ( res == -1 ) {
+ perror("fcntl(1, F_SETFL)");
+ }
+}
+
+void dgrambuf_init() {
+ /* Guess dgrambuf size from global free memory */
+ size_t dgram_count;
+ int avail_mem = get_available_mem_kb();
+
+ if ( avail_mem < MULTICAST_SO_RCVBUF_WANTED ) {
+ dgram_count = MULTICAST_SO_RCVBUF_WANTED / MULTICAST_RECV_BUF;
+ } else {
+ dgram_count = avail_mem / MULTICAST_RECV_BUF / 2 * 1024;
+ }
+ /* XXX Dummy
+ dgram_count = 5;
+ */
+
+ /* Allocate dgrambuf */
+ dgrambuf = dgrambuf_new(dgram_count, MULTICAST_RECV_BUF, DGRAM_HEADER_SIZE, MAX_IOVEC);
+ if ( dgrambuf == NULL ) {
+ perror("dgrambuf_new/malloc");
+ exit(EXIT_FAILURE);
+ }
+
+ fprintf(stderr, "dgrambuf_get_free_count() => %zu\n", dgrambuf_get_free_count(dgrambuf));
+ dgrambuf_set_validate_func(dgrambuf, validate_data_dgram);
+}
+
+int validate_data_dgram(unsigned int nread, void *recvbuf, unsigned int *seq) {
+
+ if ( nread < DGRAM_HEADER_SIZE ) {
+ return 0;
+ }
+ if ( strncmp("data", recvbuf, 4) == 0 ) {
+ *seq = ntohl( *( (uint32_t *) recvbuf+1 ) );
+ return 1;
+ }
+ if ( strncmp("end:", recvbuf, 4) == 0 ) {
+ *seq = ntohl( *( (uint32_t *) recvbuf+1 ) );
+ return 2;
+ }
+ return 0;
+}
+
+int send_status(int state, int info_r, int info_w) {
+ if ( state && info_r && info_w ) {}
+ /* TODO Implement it */
+ return 0;
+}
diff --git a/draft/mcastseed/src/mcastseed.c b/draft/mcastseed/src/mcastseed.c
new file mode 100644
index 0000000..48f8869
--- /dev/null
+++ b/draft/mcastseed/src/mcastseed.c
@@ -0,0 +1,472 @@
+/*
+ * mcastseed.c - Multicast sender for huge streams to be piped to other programs (partitions cloning)
+ *
+ * Copyright 2016 by Ludovic Pouzenc <ludovic@pouzenc.fr>
+ *
+ * Greatly inspired from examples written by tmouse, July 2005
+ * http://cboard.cprogramming.com/showthread.php?t=67469
+ */
+#define _GNU_SOURCE /* See feature_test_macros(7) */
+#include "config.h"
+
+#include <unistd.h> /* close() */
+#include <stdio.h> /* fprintf(), stderr */
+#include <stdlib.h> /* atoi(), EXIT_SUCCESS */
+#include <string.h> /* strlen() */
+#include <sys/select.h> /* select(), FD_ZERO(), FD_SET() */
+#include "sockets.h"
+
+#define READ_BUF_LEN 256
+#define MAX_PENDING_CONNECTIONS 256
+#define MAX_CLIENTS 256
+#define MTU 1500
+/* Linux IPv6 fragmentation don't output ethernet frames larger than 1470 when MTU==1500 */
+#define MULTICAST_MAX_PAYLOAD_SIZE (MTU-40-8-(14+30))
+
+#define DEFAULT_MCAST_IP_STR "ff02::114"
+#define DEFAULT_PORT_STR "9000"
+#define DEFAULT_MCAST_TTL 1
+
+/* Cmdline Arguments */
+char *prog_name = NULL;
+char *mcast_ip = NULL;
+char *port = NULL;
+int mcast_ttl = 0;
+
+/* Sockets as global, used everywhere, even in die() */
+int mcast_sock = -1; /* Multicast socket for sending data */
+int ucast_sock = -1; /* Unicast socket for havee feedback from clients */
+
+/* Socket related data */
+struct addrinfo *mcast_addr = NULL;
+struct client {
+ int sock;
+ struct sockaddr addr;
+ int state;
+} clients[MAX_CLIENTS];
+int clients_next = 0;
+
+/* Buffer used for earch read() */
+char readbuf[READ_BUF_LEN];
+
+/* Strings to print out representation of various states of the program */
+const char * const state_str[] = {
+ "start",
+ "send_hello",
+ "accept_pending_clients_or_wait_a_bit",
+ "start_job",
+ "send_data",
+ "wait_all_finalize_job",
+ "is_there_more_job"
+};
+
+/* Some boring funcs you didn't want to read now */
+void die(char* msg);
+void usage(char *msg);
+void arg_parse(int argc, char* argv[]);
+void fsm_trace(int state);
+void setup_sockets();
+void unsetup_sockets();
+
+/* Parts of the "protocol", definitions are after main() */
+int send_hello();
+int accept_pending_clients_or_wait_a_bit();
+int start_job();
+int send_data();
+int wait_all_finalize_job();
+int is_there_more_job();
+
+int main(int argc, char *argv[]) {
+ int state = 1; /* state of the "protocol" state machine */
+ int res;
+ arg_parse(argc, argv);
+ setup_sockets();
+
+ /* Finite state machine */
+ while ( state > 0 ) {
+ fsm_trace(state);
+ switch ( state ) {
+ case 1: res = send_hello(); state = (res==0)?2:-1; break;
+ case 2: res = accept_pending_clients_or_wait_a_bit();
+ if (res==0) state = 2; /* Some clients has just come in, try to get more */
+ else if (res==1) state = 1; /* Nothing new. Keep accepting clients after another hello */
+ else if (res==2) state = 3; /* Wanted clients are accepted */
+ else state = -2;
+ break;
+ case 3: res = start_job();
+ if (res==0) state = 3; /* Keep trying to convince every client to start */
+ else if (res==1) state = 4; /* All clients have started the job pipe */
+ else if (res==2) state = 4; /* There is dead clients but all alive are ready to go */
+ else state = -3;
+ break;
+ case 4: res = send_data();
+ if (res==0) state = 4;
+ else if (res==1) state = 5; /* All data sent */
+ else state = -4;
+ break;
+ case 5: res = wait_all_finalize_job();
+ if (res==0) state = 5;
+ else if (res==1) state = 6;
+ else state = -5;
+ case 6: res = is_there_more_job();
+ if (res==0) state = 0;
+ else if (res==1) state = 3;
+ else state = -6;
+ break;
+ }
+ }
+ fsm_trace(state);
+
+ unsetup_sockets();
+
+ if ( state < 0 )
+ return -state;
+
+ return EXIT_SUCCESS;
+}
+
+int send_hello() {
+ ssize_t nwrite;
+ const char *payload = "hello";
+ int paylen = strlen(payload);
+
+ nwrite = sendto(mcast_sock, payload, paylen, 0, mcast_addr->ai_addr, mcast_addr->ai_addrlen);
+ if ( nwrite < 0 ) {
+ perror("sendto() failed");
+ return -1;
+ }
+ if ( nwrite < paylen ) {
+ fprintf(stderr, "%s", "Short packet sent");
+ }
+
+ return 0;
+}
+
+int accept_pending_clients_or_wait_a_bit() {
+ struct timeval timeout;
+ fd_set readfds, exceptfds;
+ ssize_t nread;
+ int res;
+
+ FD_ZERO(&readfds);
+ FD_ZERO(&exceptfds);
+ FD_SET(0,&readfds);
+ FD_SET(ucast_sock,&readfds);
+ FD_SET(ucast_sock,&exceptfds);
+ timeout.tv_sec = 2;
+ timeout.tv_usec = 0;
+
+ res = select(ucast_sock+1, &readfds, NULL, &exceptfds, &timeout);
+ if ( res < 0 ) {
+ perror("select() failed");
+ return -1;
+ }
+
+ if ( res > 0 ) {
+ if (FD_ISSET(ucast_sock, &readfds)) {
+ /*TODO : this assumes that the event is an accept() while ones could be send data there */
+ if ( clients_next >= MAX_CLIENTS ) {
+ fprintf(stderr, "%s\n", "Bouncing client, MAX_CLIENTS reached");
+ close(accept(ucast_sock, NULL, 0));
+ } else {
+ socklen_t addrlen = sizeof(struct sockaddr);
+ clients[clients_next].sock = accept(ucast_sock, &(clients[clients_next].addr), &addrlen);
+ clients[clients_next].state = 0;
+ printf("Connected client on fd %i\n", clients[clients_next].sock);
+ clients_next++;
+ }
+ }
+ /*TODO : drop this keybord read with accept(), this is not portable */
+ if ( FD_ISSET(0, &readfds)) {
+ nread = read(0, readbuf, READ_BUF_LEN);
+ if ( nread <= 0 ) {
+ fprintf(stderr, "%s\n", "lost stdin");
+ }
+ /* User wants to go now */
+ return 2;
+ }
+ if (FD_ISSET(ucast_sock, &exceptfds)) {
+ fprintf(stderr, "%s\n", "unhandled except on ucast_sock");
+ return -2;
+ }
+ }
+ if (res == 0 ) {
+ /* Nothing happened before timeout */
+ return 1;
+ }
+ return 0;
+}
+
+int start_job() {
+ struct timeval timeout;
+ fd_set readfds, exceptfds;
+ ssize_t nread, nwrite;
+ int all_ready, all_non_dead_ready;
+ int i, res;
+ int client_sock;
+ const char *payload = "start";
+ int paylen = strlen(payload);
+
+ nwrite = sendto(mcast_sock, payload, paylen, 0, mcast_addr->ai_addr, mcast_addr->ai_addrlen);
+ if ( nwrite < 0 ) {
+ perror("sendto() failed");
+ return -1;
+ }
+ if ( nwrite < paylen ) {
+ fprintf(stderr, "%s", "Short packet sent");
+ }
+
+ all_ready = 1;
+ all_non_dead_ready = 1;
+
+ FD_ZERO(&readfds);
+ FD_ZERO(&exceptfds);
+ for ( i=0; i<clients_next; i++) {
+ FD_SET(clients[i].sock,&readfds);
+ FD_SET(clients[i].sock,&exceptfds);
+ }
+ timeout.tv_sec = 2;
+ timeout.tv_usec = 0;
+ res = select(clients_next, &readfds, NULL, &exceptfds, &timeout);
+ if ( res < 0 ) {
+ perror("select() failed");
+ return -1;
+ }
+
+ if ( res > 0 ) {
+ for ( i=0; i<clients_next; i++) {
+ client_sock = clients[i].sock;
+ if (FD_ISSET(client_sock, &readfds)) {
+ printf("todo info from client %i\n", i);
+ nread = read(client_sock, readbuf, 5);
+ if ( nread <= 0 ) {
+ fprintf(stderr, "lost client %i\n", i);
+ clients[i].state = 2;
+ } else if ( nread < 5 ) {
+ fprintf(stderr, "short data from %i\n", i);
+ clients[i].state = 2;
+ } else if ( strncmp("ready", readbuf, 5) != 0 ) {
+ fprintf(stderr, "unexpected data from %i\n", i);
+ clients[i].state = 2;
+ } else {
+ /* Received "ready" ack from client */
+ clients[i].state = 1;
+ }
+ }
+ if (FD_ISSET(clients[i].sock, &exceptfds)) {
+ fprintf(stderr, "unhandled except on client %i\n", i);
+ clients[i].state = 2;
+ }
+ all_ready &= (clients[i].state == 1);
+ if ( clients[i].state != 2)
+ all_non_dead_ready &= (clients[i].state == 1);
+ }
+ }
+ /* (res == 0 ) nothing happened before timeout */
+
+ if ( all_ready )
+ return 1;
+ if ( all_non_dead_ready )
+ return 2;
+
+ return 0;
+}
+
+void send_fake(char buf[], int paylen, int i) {
+ *( (uint32_t *) buf+1 ) = htonl(i);
+ snprintf(buf+28, 6, "%05i", i);
+ *( (char *) buf+33 ) = ')';
+ sendto(mcast_sock, buf, paylen, 0, mcast_addr->ai_addr, mcast_addr->ai_addrlen);
+}
+
+int send_data() {
+ ssize_t nwrite;
+ char buf[MULTICAST_MAX_PAYLOAD_SIZE];
+ int paylen = MULTICAST_MAX_PAYLOAD_SIZE;
+ int i;
+
+ /* XXX Dummy */
+ memset(buf, '.', MULTICAST_MAX_PAYLOAD_SIZE-1);
+ buf[MULTICAST_MAX_PAYLOAD_SIZE-1]='\n';
+ strcpy(buf, "dataXXXXJe suis a la plage (XXXXX)");
+
+ send_fake(buf, paylen, 5);
+ send_fake(buf, paylen, 4);
+ send_fake(buf, paylen, 3);
+
+ for (i=6; i<=100000; i+=2) {
+ send_fake(buf, paylen, i);
+ }
+ for (i=7; i<=100000; i+=2) {
+ send_fake(buf, paylen, i);
+ }
+
+ send_fake(buf, paylen, 1);
+ send_fake(buf, paylen, 1);
+ send_fake(buf, paylen, 2);
+
+ *( (uint32_t *) buf+1 ) = htonl(3);
+ buf[21]='m', buf[22]='e', buf[23]='r'; buf[24]='.'; buf[25]='\n'; paylen = 26;
+ nwrite = sendto(mcast_sock, buf, paylen, 0, mcast_addr->ai_addr, mcast_addr->ai_addrlen);
+ if ( nwrite < 0 ) {
+ perror("sendto() failed");
+ return -1;
+ }
+ if ( nwrite < paylen ) {
+ fprintf(stderr, "%s", "Short packet sent");
+ }
+
+ return 1;
+}
+
+
+int wait_all_finalize_job() {
+ struct timeval timeout;
+ fd_set readfds, exceptfds;
+ ssize_t nread, nwrite;
+ int all_non_dead_done;
+ int i, res;
+ int client_sock;
+ char buf[] = "end:XXXX";
+ int paylen = strlen(buf);
+
+ *( (uint32_t *) buf+1 ) = htonl(100000);
+ nwrite = sendto(mcast_sock, buf, paylen, 0, mcast_addr->ai_addr, mcast_addr->ai_addrlen);
+ if ( nwrite < 0 ) {
+ perror("sendto() failed");
+ return -1;
+ }
+ if ( nwrite < paylen ) {
+ fprintf(stderr, "%s", "Short packet sent");
+ }
+
+ all_non_dead_done = 1;
+
+ FD_ZERO(&readfds);
+ FD_ZERO(&exceptfds);
+ for ( i=0; i<clients_next; i++) {
+ FD_SET(clients[i].sock,&readfds);
+ FD_SET(clients[i].sock,&exceptfds);
+ }
+ timeout.tv_sec = 2;
+ timeout.tv_usec = 0;
+ res = select(clients_next, &readfds, NULL, &exceptfds, &timeout);
+ if ( res < 0 ) {
+ perror("select() failed");
+ return -1;
+ }
+
+ if ( res > 0 ) {
+ for ( i=0; i<clients_next; i++) {
+ client_sock = clients[i].sock;
+ if (FD_ISSET(client_sock, &readfds)) {
+ printf("todo info from client %i\n", i);
+ nread = read(client_sock, readbuf, 5);
+ if ( nread <= 0 ) {
+ fprintf(stderr, "lost client %i\n", i);
+ clients[i].state = 2;
+ } else if ( nread < 5 ) {
+ fprintf(stderr, "short data from %i\n", i);
+ clients[i].state = 2;
+ } else if ( strncmp("done.", readbuf, 5) != 0 ) {
+ fprintf(stderr, "unexpected data from %i\n", i);
+ clients[i].state = 2;
+ } else {
+ /* Received "done." ack from client */
+ clients[i].state = 3;
+ }
+ }
+ if (FD_ISSET(clients[i].sock, &exceptfds)) {
+ fprintf(stderr, "unhandled except on client %i\n", i);
+ clients[i].state = 2;
+ }
+ if ( clients[i].state != 2)
+ all_non_dead_done &= (clients[i].state == 3);
+ }
+ }
+ /* (res == 0 ) nothing happened before timeout */
+
+ if ( all_non_dead_done )
+ return 1;
+
+ return 0;
+}
+
+
+int is_there_more_job() {
+ return 0;
+}
+
+
+void die(char* msg) {
+ fprintf(stderr, "%s\n", msg);
+ if (mcast_sock > 0)
+ close(mcast_sock);
+ if (ucast_sock > 0)
+ close(ucast_sock);
+ exit(EXIT_FAILURE);
+}
+
+void usage(char *msg) {
+ char ubuf[256];
+ if ( msg != NULL )
+ fprintf(stderr, "%s\n", msg);
+ ubuf[0] = '\0';
+ snprintf(ubuf, 255, "Usage: %s [port] [mcast_ip] [mcast_ttl]\n", prog_name);
+ die(ubuf);
+}
+
+void arg_parse(int argc, char* argv[]) {
+ prog_name = argv[0];
+ if ( argc > 3 )
+ usage("Too many arguments");
+ port = (argc >= 2)?argv[1]:DEFAULT_PORT_STR;
+ mcast_ip = (argc >= 3)?argv[2]:DEFAULT_MCAST_IP_STR;
+ mcast_ttl = (argc >= 4)?atoi(argv[3]):DEFAULT_MCAST_TTL;
+ if ( mcast_ttl < 1 || mcast_ttl > 64 )
+ mcast_ttl = 1;
+}
+
+void fsm_trace(int state) {
+ static int prev_state = 0;
+
+ if ( state < 0 ) {
+ fprintf(stderr, "Abnormal exit condition %i (from %s)\n", state, state_str[prev_state]);
+ } else if ( prev_state != state) {
+ if ( state == 0 ) {
+ fprintf(stderr, "Normal exit (from %s)\n", state_str[prev_state]);
+ } else {
+ fprintf(stderr, "Now in %s (from %s)\n", state_str[state], state_str[prev_state]);
+ }
+ prev_state = state;
+ }
+}
+
+void setup_sockets() {
+ /* Setup ucast_sock */
+ ucast_sock = ucast_server_socket(port, MAX_PENDING_CONNECTIONS);
+ if(ucast_sock < 0)
+ usage("Could not setup unicast socket. Wrong args given ?");
+
+ /* Setup mcast_sock */
+ mcast_sock = mcast_send_socket(mcast_ip, port, mcast_ttl, &mcast_addr);
+ if(mcast_sock < 0)
+ usage("Could not setup multicast socket. Wrong args given ?");
+}
+
+void unsetup_sockets() {
+ if ( ucast_sock > 0 ) {
+ close(ucast_sock);
+ ucast_sock = 0;
+ }
+
+ if ( mcast_sock > 0 ) {
+ close(mcast_sock);
+ mcast_sock = 0;
+ if ( mcast_addr ) {
+ freeaddrinfo(mcast_addr);
+ mcast_addr = 0;
+ }
+ }
+}
+
diff --git a/draft/mcastseed/src/random_speed_dd.c b/draft/mcastseed/src/random_speed_dd.c
new file mode 100644
index 0000000..4d94bc0
--- /dev/null
+++ b/draft/mcastseed/src/random_speed_dd.c
@@ -0,0 +1,36 @@
+#include <unistd.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+
+char buf[0xffff];
+
+int main() {
+ ssize_t nread, nwrite, remains;
+
+ srandom(1); /* Always the same pseudo-random sequence */
+
+ while ( (nread=read(0, buf, 0xfff & rand())) > 0 ) {
+ remains = nread;
+ while ( remains ) {
+ nwrite=write(1, buf, nread);
+ if ( nwrite < 0 ) {
+ if ( !(errno == EAGAIN || errno == EWOULDBLOCK || errno == EINTR) ) {
+ perror("write");
+ return nwrite;
+ }
+ } else {
+ remains -= nwrite;
+ }
+ }
+ /*fprintf(stderr, "nread==%zu, nwrite==%zu\n", nread, nwrite);*/
+ usleep( 0xffff & rand() );
+ }
+ if ( nread < 0 ) {
+ perror("read");
+ return nread;
+ }
+
+ return 0;
+}
+
diff --git a/draft/mcastseed/src/sockets.c b/draft/mcastseed/src/sockets.c
new file mode 100644
index 0000000..6aea016
--- /dev/null
+++ b/draft/mcastseed/src/sockets.c
@@ -0,0 +1,303 @@
+/*
+ * Copyright 2016 by Ludovic Pouzenc <ludovic@pouzenc.fr>
+ *
+ * Greatly inspired from msock.h written by Christian Beier <dontmind@sdf.org>
+ */
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include "sockets.h"
+
+int mcast_recv_socket(char *mcast_ip, char *port, int wanted_so_rcvbuf) {
+
+ int sock;
+ struct addrinfo hints = { 0 }; /* Hints for name lookup */
+ struct addrinfo *ai_local = NULL; /* Local address to bind to */
+ struct addrinfo *mcast_ai = NULL; /* Multicast Address */
+ int yes=1;
+ int status, optval;
+ socklen_t optval_len;
+ int dfltrcvbuf;
+
+ /* Resolve the multicast group address */
+ hints.ai_family = PF_UNSPEC;
+ hints.ai_flags = AI_NUMERICHOST;
+ if ((status = getaddrinfo(mcast_ip, NULL, &hints, &mcast_ai)) != 0) {
+ fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));
+ goto error;
+ }
+
+ /*
+ * Get a local address with the same family (IPv4 or IPv6) as our multicast group
+ * This is for receiving on a certain port.
+ */
+ hints.ai_family = mcast_ai->ai_family;
+ hints.ai_socktype = SOCK_DGRAM;
+ hints.ai_flags = AI_PASSIVE; /* Return an address we can bind to */
+ if ( getaddrinfo(NULL, port, &hints, &ai_local) != 0 ) {
+ fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));
+ goto error;
+ }
+
+ /* Create socket for receiving datagrams */
+ if ( (sock = socket(ai_local->ai_family, ai_local->ai_socktype, 0)) < 0 ) {
+ perror("socket() failed");
+ goto error;
+ }
+
+ /*
+ * Enable SO_REUSEADDR to allow multiple instances of this
+ * application to receive copies of the multicast datagrams.
+ */
+ if (setsockopt(sock,SOL_SOCKET,SO_REUSEADDR,(char*)&yes,sizeof(int)) == -1) {
+ perror("setsockopt");
+ goto error;
+ }
+
+ /* Bind the local address to the multicast port */
+ if ( bind(sock, ai_local->ai_addr, ai_local->ai_addrlen) != 0 ) {
+ perror("bind() failed");
+ goto error;
+ }
+
+ /* get/set socket receive buffer */
+ optval=0;
+ optval_len = sizeof(optval);
+ if(getsockopt(sock, SOL_SOCKET, SO_RCVBUF,(char*)&optval, &optval_len) !=0) {
+ perror("getsockopt");
+ goto error;
+ }
+ dfltrcvbuf = optval;
+ optval = wanted_so_rcvbuf;
+ if(setsockopt(sock,SOL_SOCKET,SO_RCVBUF,(char*)&optval,sizeof(optval)) != 0) {
+ perror("setsockopt");
+ goto error;
+ }
+ if(getsockopt(sock, SOL_SOCKET, SO_RCVBUF,(char*)&optval, &optval_len) != 0) {
+ perror("getsockopt");
+ goto error;
+ }
+ fprintf(stderr, "tried to set socket receive buffer from %d to %d, got %d\n",
+ dfltrcvbuf, wanted_so_rcvbuf, optval);
+
+
+ /* Join the multicast group. We do this seperately depending on whether we
+ * are using IPv4 or IPv6.
+ */
+ if ( mcast_ai->ai_family == PF_INET &&
+ mcast_ai->ai_addrlen == sizeof(struct sockaddr_in) ) /* IPv4 */
+ {
+ struct ip_mreq multicastRequest; /* Multicast address join structure */
+
+ /* Specify the multicast group */
+ memcpy(&multicastRequest.imr_multiaddr,
+ &((struct sockaddr_in*)(mcast_ai->ai_addr))->sin_addr,
+ sizeof(multicastRequest.imr_multiaddr));
+
+ /* Accept multicast from any interface */
+ multicastRequest.imr_interface.s_addr = htonl(INADDR_ANY);
+
+ /* Join the multicast address */
+ if ( setsockopt(sock, IPPROTO_IP, IP_ADD_MEMBERSHIP, (char*) &multicastRequest, sizeof(multicastRequest)) != 0 ) {
+ perror("setsockopt() failed");
+ goto error;
+ }
+ }
+ else if ( mcast_ai->ai_family == PF_INET6 &&
+ mcast_ai->ai_addrlen == sizeof(struct sockaddr_in6) ) /* IPv6 */
+ {
+ struct ipv6_mreq multicastRequest; /* Multicast address join structure */
+
+ /* Specify the multicast group */
+ memcpy(&multicastRequest.ipv6mr_multiaddr,
+ &((struct sockaddr_in6*)(mcast_ai->ai_addr))->sin6_addr,
+ sizeof(multicastRequest.ipv6mr_multiaddr));
+
+ /* Accept multicast from any interface */
+ multicastRequest.ipv6mr_interface = 0;
+
+ /* Join the multicast address */
+ if ( setsockopt(sock, IPPROTO_IPV6, IPV6_ADD_MEMBERSHIP, (char*) &multicastRequest, sizeof(multicastRequest)) != 0 ) {
+ perror("setsockopt() failed");
+ goto error;
+ }
+ }
+ else {
+ perror("Neither IPv4 or IPv6");
+ goto error;
+ }
+
+
+ if(ai_local)
+ freeaddrinfo(ai_local);
+ if(mcast_ai)
+ freeaddrinfo(mcast_ai);
+
+ return sock;
+
+error:
+ if(ai_local)
+ freeaddrinfo(ai_local);
+ if(mcast_ai)
+ freeaddrinfo(mcast_ai);
+
+ return -1;
+}
+
+
+int mcast_send_socket(char* mcast_ip, char* port, int multicastTTL, struct addrinfo **mcast_ai) {
+
+ int sock;
+ struct addrinfo hints = { 0 }; /* Hints for name lookup */
+ int status;
+
+
+ /* Resolve destination address for multicast datagrams */
+ hints.ai_family = PF_UNSPEC;
+ hints.ai_socktype = SOCK_DGRAM;
+ hints.ai_flags = AI_NUMERICHOST;
+ if ((status = getaddrinfo(mcast_ip, port, &hints, mcast_ai)) != 0 )
+ {
+ fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));
+ return -1;
+ }
+
+ /* Create socket for sending multicast datagrams */
+ if ( (sock = socket((*mcast_ai)->ai_family, (*mcast_ai)->ai_socktype, 0)) < 0 ) {
+ perror("socket() failed");
+ freeaddrinfo(*mcast_ai);
+ return -1;
+ }
+
+ /* Set TTL of multicast packet */
+ if ( setsockopt(sock,
+ (*mcast_ai)->ai_family == PF_INET6 ? IPPROTO_IPV6 : IPPROTO_IP,
+ (*mcast_ai)->ai_family == PF_INET6 ? IPV6_MULTICAST_HOPS : IP_MULTICAST_TTL,
+ (char*) &multicastTTL, sizeof(multicastTTL)) != 0 ) {
+ perror("setsockopt() failed");
+ freeaddrinfo(*mcast_ai);
+ return -1;
+ }
+
+ /* set the sending interface */
+ if((*mcast_ai)->ai_family == PF_INET) {
+ in_addr_t iface = INADDR_ANY; /* well, yeah, any */
+ if(setsockopt (sock,
+ IPPROTO_IP,
+ IP_MULTICAST_IF,
+ (char*)&iface, sizeof(iface)) != 0) {
+ perror("interface setsockopt() sending interface");
+ freeaddrinfo(*mcast_ai);
+ return -1;
+ }
+
+ }
+ if((*mcast_ai)->ai_family == PF_INET6) {
+ unsigned int ifindex = 0; /* 0 means 'default interface'*/
+ if(setsockopt (sock,
+ IPPROTO_IPV6,
+ IPV6_MULTICAST_IF,
+ (char*)&ifindex, sizeof(ifindex)) != 0) {
+ perror("interface setsockopt() sending interface");
+ freeaddrinfo(*mcast_ai);
+ return -1;
+ }
+
+ }
+
+ return sock;
+}
+
+
+int ucast_server_socket(char* port, int max_pending_conn) {
+
+ int sock;
+ struct addrinfo *serverAddr;
+ struct addrinfo hints = { 0 }; /* Hints for name lookup */
+ int status;
+
+
+ /* Prepare an addrinfo struct for a local socket */
+ hints.ai_family = PF_INET6;
+ hints.ai_socktype = SOCK_STREAM;
+ hints.ai_flags = AI_PASSIVE;
+ if ((status = getaddrinfo(NULL, port, &hints, &serverAddr)) != 0 )
+ {
+ fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));
+ return -1;
+ }
+ /* Create socket */
+ if ( (sock = socket(serverAddr->ai_family, serverAddr->ai_socktype, serverAddr->ai_protocol)) < 0 ) {
+ perror("socket() failed");
+ freeaddrinfo(serverAddr);
+ return -1;
+ }
+
+ /* Accepts also IPv4 traffic if the socket is INET6 */
+ if(serverAddr->ai_family == PF_INET6) {
+ unsigned int no = 0;
+ if(setsockopt (sock,
+ IPPROTO_IPV6,
+ IPV6_V6ONLY,
+ (char*)&no, sizeof(no)) != 0) {
+ perror("setsockopt() !IPV6_V6ONLY failed");
+ freeaddrinfo(serverAddr);
+ return -1;
+ }
+ }
+
+ /* Bind socket to local address/port */
+ if ( bind(sock, serverAddr->ai_addr, serverAddr->ai_addrlen) < 0 ) {
+ perror("bind() failed");
+ close(sock);
+ freeaddrinfo(serverAddr);
+ return -1;
+ }
+
+ freeaddrinfo(serverAddr);
+
+ /* Start listening incoming connections */
+ if ( listen(sock, max_pending_conn) < 0 ) {
+ perror("listen() failed");
+ close(sock);
+ }
+
+ return sock;
+}
+
+int ucast_client_socket(char* server_ip, char* port) {
+
+ int sock;
+ struct addrinfo *serverAddr;
+ struct addrinfo hints = { 0 }; /* Hints for name lookup */
+ int status;
+
+ /* Resolve destination address */
+ hints.ai_family = PF_UNSPEC;
+ hints.ai_socktype = SOCK_STREAM;
+ hints.ai_flags = AI_NUMERICHOST;
+ if ((status = getaddrinfo(server_ip, port, &hints, &serverAddr)) != 0 )
+ {
+ fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));
+ return -1;
+ }
+
+ /* Create socket */
+ if ( (sock = socket(serverAddr->ai_family, serverAddr->ai_socktype, 0)) < 0 ) {
+ perror("socket() failed");
+ freeaddrinfo(serverAddr);
+ return -1;
+ }
+
+ /* Connect it to the remote server */
+ if ( connect(sock, serverAddr->ai_addr, serverAddr->ai_addrlen) < 0 ) {
+ perror("connect() failed");
+ close(sock);
+ freeaddrinfo(serverAddr);
+ return -1;
+ }
+
+ freeaddrinfo(serverAddr);
+ return sock;
+}
+
diff --git a/draft/mcastseed/src/sockets.h b/draft/mcastseed/src/sockets.h
new file mode 100644
index 0000000..86f7c5b
--- /dev/null
+++ b/draft/mcastseed/src/sockets.h
@@ -0,0 +1,27 @@
+/*
+ * Copyright 2016 by Ludovic Pouzenc <ludovic@pouzenc.fr>
+ *
+ * Greatly inspired from msock.h written by Christian Beier <dontmind@sdf.org>
+ */
+
+#ifndef SOCKETS_H
+#define SOCKETS_H
+
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netdb.h>
+/*
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <sys/un.h>
+#include <netinet/tcp.h>
+#include <arpa/inet.h>
+#include <netdb.h>
+*/
+int mcast_recv_socket(char *mcast_ip, char *port, int wanted_so_rcvbuf);
+int mcast_send_socket(char *mcast_ip, char *port, int mcast_ttl, struct addrinfo **mcast_ai);
+
+int ucast_server_socket(char *port, int max_pending_conn);
+int ucast_client_socket(char *server_ip, char *port);
+
+#endif /*SOCKETS_H*/