diff options
Diffstat (limited to 'draft/mcastseed')
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*/ |