commit 2037fe5694a4821f3029e051d5a667de85b42037
parent bf9ffb63bd8b24fb37e9c3d0ea8e547602fd3b5e
Author: Ellenor Bjornsdottir <ellenor@umbrellix.net>
Date: Sat, 15 Oct 2022 21:41:29 +0000
Major import of various different, disjoint sources.
Diffstat:
38 files changed, 3969 insertions(+), 1 deletion(-)
diff --git a/README.md b/README.md
@@ -1 +1,5 @@
-# The `/pkg/umbrellix.net/prog/suitcase` package - package structure
+# Programmer's Suitcase
+
+## The `/pkg/umbrellix.net/prog/suitcase` package - package structure
+
+Under every src/ directory, to which a head/ directory must correspond, there will be a file named either QUELLE or SOURCE. Its meaning is the same thing: describing the provenance of the code enclosed in the src/ and head/ directories of the same name.
diff --git a/doc/npthread/README.md b/doc/npthread/README.md
@@ -0,0 +1,13 @@
+# The npthread library - notes
+
+npthread.html was retrieved Sat 21 Jun 2003 00:03:18 UTC (Epoch +1056153798)
+
+This npthread aims to be capable of exact conformance with the Bernstein documented npthreads by default. If you define NPTHREAD_VPTR, this compliance is lost, but the 'n' your f(n) is called with is expected to be a void pointer instead of an int64. I believe this use to be much more likely to be useful for most users.
+
+If you include sc_npthread.h as well as npthread.h, you would gain access to additional thread call conditions to be determined. In thread-safe sc_npthread, those call conditions may involve pthread trylock successes, or data (from another true thread) in the rendezvous area.
+
+Your threads should have a mechanism for saving their state, so if they choose to cut mid-procedure (e.g. starving of data from a fildes or the rendezvous area, or of a locked resource, or buffered I/O needs to drain before continuing), they can resume processing. In 2000, Simon Tatham designed a header capable of helping you do this. It is available under the MIT licence. <https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html>
+
+User-defined lights (npthread_watchflag and npthread_waveflag) could be used to implement the message and trylock notes.
+
+This package requires tai support, which can be had from many different places.
diff --git a/doc/npthread/npthread.html b/doc/npthread/npthread.html
@@ -0,0 +1,388 @@
+<html>
+<body>
+<a href="../djb.html">D. J. Bernstein</a>
+<h1>The npthread library interface</h1>
+The npthread library manages a collection of <b>threads</b>:
+pointers to functions that should be called when specified conditions occur.
+<p>
+For example,
+you can tell npthread
+to call the handle0() function
+whenever data is available to be read on descriptor 0,
+and to call the handle6() function
+whenever data is available to be read on descriptor 6.
+If neither descriptor has data,
+npthread will wait until data arrives.
+<p>
+The npthread library allows the following seven types of threads:
+<ul>
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+as soon as possible.
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+if the current time is past <tt><i>t</i></tt>.
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+if UNIX signal <tt><i>s</i></tt> has just arrived.
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+if child process <tt><i>p</i></tt> has just exited.
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+if user-defined flag <tt><i>p</i></tt> has just been waved.
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+when file descriptor <tt><i>d</i></tt> is readable.
+<li>Call <tt><i>f</i>(<i>n</i>)</tt>
+when file descriptor <tt><i>d</i></tt> is writable.
+</ul>
+<h2><a name="preempt">Preemptive threads versus non-preemptive threads</a></h2>
+Some thread libraries provide <b>preemptive threads</b>:
+a function can be called even while another function is active.
+<p>
+The npthread library provides <b>non-preemptive threads</b>:
+specifically, a function must return
+before npthread calls another function.
+For example,
+say you've told npthread
+to call the handle0() function
+whenever data is available to be read on descriptor 0,
+and to call the handle6() function
+whenever data is available to be read on descriptor 6.
+If descriptors 0 and 6 both have data,
+npthread will call handle0() and then handle6(),
+or it might instead call handle6() and then handle0();
+but it will not overlap handle0() and handle6().
+<p>
+Other thread libraries provide <b>semi-preemptive threads</b>:
+a function does not need to return
+before another function is called,
+but it does need to take some explicit action,
+such as calling a yield() function.
+(Semi-preemptive threads
+are sometimes confusingly called non-preemptive threads.
+The word <b>coroutines</b> can refer to either semi-preemptive threads
+or non-preemptive threads.)
+<p>
+Basic issues to consider in deciding whether to use
+a preemptive thread library,
+a semi-preemptive thread library,
+or a non-preemptive thread library:
+<ul>
+<li>With preemptive threads,
+you have to go to extra effort whenever you read or write a global variable
+(a variable that can interact with another thread).
+If you fail to do this,
+you may sporadically corrupt data.
+<li>With non-preemptive and semi-preemptive threads,
+you have to go to extra effort whenever you perform an operation
+that can take lots of time,
+such as calling the UNIX read() function.
+If you fail to do this,
+your program may freeze.
+<li>Preemptive threads and semi-preemptive threads
+tend to chew up much more memory than non-preemptive threads.
+In theory, the <b>continuation</b> (stack and saved registers)
+of a semi-preemptive thread should take the same space
+as the equivalent structure in a non-preemptive thread;
+in practice, it is inconvenient to allocate fewer than 4096 bytes for a stack,
+while a non-preemptive thread typically fits into 64 bytes.
+For similar reasons,
+many preemptive thread systems do not allow more than 512 threads per process.
+<li>With non-preemptive threads,
+variables that might naturally be stored in a continuation
+have to be stored somewhere else.
+<li>Non-preemptive and semi-preemptive threads compete for one CPU,
+even if the computer has another CPU available.
+Two preemptive threads can run on two separate CPUs.
+</ul>
+Separate UNIX processes are always preemptive
+and will take advantage of separate CPUs.
+A common approach is to split tasks across several UNIX processes,
+with non-preemptive threads inside each process.
+<p>
+The npthread library replaces my old sigsched library.
+Other non-preemptive thread libraries:
+Niels Provos's
+<a href="http://www.monkey.org/~provos/libevent/">libevent</a>,
+Dan Egnor's
+<a href="http://liboop.org">liboop</a>,
+libwww's
+<a href="http://www.w3.org/Library/src/HTEvent.html">HTEvent</a>,
+and
+GLib's
+<a href="http://developer.gnome.org/doc/API/glib/glib-the-main-event-loop.html">Main Event Loop</a>.
+Some semi-preemptive thread libraries:
+Keld Helsgaun's
+<a href="http://www.dat.ruc.dk/~keld/research/COROUTINE/">COROUTINE</a>,
+Ralf Engelschall's
+<a href="http://www.gnu.org/software/pth/">Pth</a>
+(formerly NPS),
+and
+Netscape's
+<a href="http://state-threads.sourceforge.net">State Threads</a>.
+The most common preemptive-thread interface
+is the POSIX thread (Pthread) interface
+supported by various libraries.
+<hr>
+<h2><a name="start">Starting threads</a></h2>
+<pre>
+ #include "npthread.h"
+ int (*<i>f</i>)(int64);
+ int64 <i>n</i>;
+ npthread_add(<i>f</i>,<i>n</i>);
+</pre>
+<tt>npthread_add</tt> creates a new ``important'' thread
+that will call <tt><i>f</i>(<i>n</i>)</tt> as soon as possible
+(after <tt>npthread_start</tt> is called).
+It returns 1 to indicate success.
+<p>
+If <tt>npthread_add</tt> runs out of memory, it returns 0
+without changing the list of threads.
+<hr>
+<pre>
+ #include "npthread.h"
+ int (*<i>f</i>)(int64);
+ int64 <i>n</i>;
+ int <i>s</i>;
+ npthread_addsignal(<i>f</i>,<i>n</i>,<i>s</i>);
+</pre>
+<tt>npthread_addsignal</tt> creates a new ``unimportant'' thread
+that will call <tt><i>f</i>(<i>n</i>)</tt>
+when UNIX signal <tt><i>s</i></tt> is received
+(after <tt>npthread_start</tt> is called).
+It returns 1 to indicate success.
+<p>
+If <tt>npthread_addsignal</tt> runs out of memory, it returns 0
+without changing the list of threads.
+<p>
+UNIX signals handled by npthread
+are <i>not</i> an exception to the rule
+that one thread does not preempt another.
+For example, after
+<pre>
+ npthread_add(compute,0);
+ npthread_addsignal(cleanup,0,SIGTERM);
+ npthread_start();
+</pre>
+the function <tt>compute(0)</tt> will be called.
+If a SIGTERM signal arrives while <tt>compute(0)</tt> is running,
+it has no immediate effect;
+<tt>cleanup(0)</tt> will be called <i>after</i> <tt>compute(0)</tt> returns.
+<p>
+Do not attempt to use UNIX signals as counters.
+Two occurrences of a signal in quick succession
+will be combined into a single occurrence of the signal;
+a thread watching the signal will be called once, not twice.
+<hr>
+<pre>
+ #include "npthread.h"
+ npthread_start(void);
+</pre>
+<tt>npthread_start</tt>
+looks for a thread whose call condition is satisfied,
+calls the thread function,
+and repeats,
+as long as there is at least one ``important'' thread left.
+It then returns 1.
+<p>
+A thread function is required to return one of the following numbers:
+<ul>
+<li>1: Continue this thread.
+The thread will be called again later
+if its call condition is again satisfied.
+<li>0: Exit this thread.
+<tt>npthread_start</tt> eliminates the thread.
+<li>-1: Abort.
+<tt>npthread_start</tt> immediately returns -1.
+</ul>
+<p>
+If <tt>npthread_start</tt> has trouble preparing internal resources,
+it returns 0, setting <tt>errno</tt> to indicate the error.
+A failure of this type cannot happen once <tt>npthread_start</tt>
+begins running threads.
+<p>
+<tt>npthread_start</tt>
+does not check every call condition
+every time it calls a thread function.
+Its main loop checks many call conditions
+and then calls many threads.
+Specifically:
+<ol>
+<li>Top of the loop:
+<tt>npthread_start</tt> checks whether any ``important'' threads are left.
+It returns if not.
+<li><tt>npthread_start</tt> checks which descriptors are readable and writable.
+It marks as ``ready''
+every thread waiting for those descriptors.
+<li><tt>npthread_start</tt> checks the current time.
+It marks as ``ready''
+every thread to be called before this time.
+It also marks as ``ready''
+every thread to be called as soon as possible.
+<li><tt>npthread_start</tt> checks which UNIX signals have been received.
+It marks as ``ready''
+every thread waiting for those signals.
+<li><tt>npthread_start</tt> checks for newly exited children.
+It marks as ``ready''
+every thread waiting for those children.
+<li><tt>npthread_start</tt>
+marks as ``run now'' each of the ``ready'' threads,
+and removes all the ``ready'' marks.
+<li>For each of the ``run now'' threads, in some order,
+<tt>npthread_start</tt> calls the thread function.
+User-defined flags may be waved at this time;
+whenever a user-defined flag is waved,
+every thread waiting for that flag is marked as ``ready.''
+<li><tt>npthread_start</tt> goes back to the top of the loop.
+</ol>
+Do not assume that UNIX signals, flag waves, readable descriptors, etc.
+take effect immediately.
+For example, if thread 1 waves a flag that thread 2 is watching,
+it is possible for thread 1 to be called again before thread 2 is called.
+</ul>
+<hr>
+<h2><a name="modify">Modifying threads</a></h2>
+The following functions modify the current thread.
+These functions cannot fail;
+all necessary storage is preallocated by <tt>npthread_add</tt>.
+<p>
+These functions are for use solely in thread functions.
+They must not be called outside <tt>npthread_start</tt>.
+<hr>
+<pre>
+ #include "npthread.h"
+ int (*<i>f</i>)(int64);
+ int64 <i>n</i>;
+ npthread_jump(<i>f</i>,<i>n</i>);
+</pre>
+<tt>npthread_jump</tt> tells the npthread library
+that <tt><i>f</i>(<i>n</i>)</tt>
+is the function to be called by the current thread.
+<tt>npthread_jump</tt> is a jump, not a subroutine call:
+it wipes out the previous function pointer.
+<hr>
+<pre>
+ #include "npthread.h"
+ npthread_unimportant(void);
+ npthread_important(void);
+</pre>
+<tt>npthread_unimportant</tt> changes the current thread
+from ``important'' to ``unimportant.''
+If the thread is already ``unimportant,''
+<tt>npthread_unimportant</tt> leaves it alone.
+<p>
+<tt>npthread_important</tt> makes the opposite change.
+<hr>
+<pre>
+ #include "npthread.h"
+ tai6464 <i>t</i>;
+ npthread_sleepuntil(<i>t</i>);
+</pre>
+<tt>npthread_sleepuntil</tt> tells the npthread library
+to call the current thread when the current time has passed <tt><i>t</i></tt>.
+Any previous call conditions for the current thread are wiped out.
+<hr>
+<pre>
+ #include "npthread.h"
+ int64 <i>p</i>;
+ int <i>status</i>;
+ npthread_child(<i>p</i>);
+ <i>status</i> = npthread_childstatus();
+</pre>
+<tt>npthread_child</tt> tells the npthread library
+to call the current thread if child process <tt><i>p</i></tt> has just exited.
+Any previous call conditions for the current thread are wiped out.
+<p>
+Once that call happens,
+<tt>npthread_childstatus()</tt>
+returns the child's exit status, in the following form:
+<ul>
+<li>If the child exited normally:
+its exit code, between 0 and 255.
+<li>If the child was terminated by a signal and didn't dump core
+(or wasn't reported by the system to have dumped core):
+1024 plus the signal, between 1024 and 1024+255.
+<li>If the child was terminated by a signal and dumped core:
+2048 plus the signal, between 2048 and 2048+255.
+</ul>
+<hr>
+<pre>
+ #include "npthread.h"
+ int64 <i>p</i>;
+ npthread_watchflag(<i>p</i>);
+ npthread_waveflag(<i>p</i>);
+ <i>p</i> = npthread_newflag();
+</pre>
+<tt>npthread_watchflag</tt> tells the npthread library
+to call the current thread if user-defined flag number <tt><i>p</i></tt>
+has just been waved.
+Any previous call conditions for the current thread are wiped out.
+<p>
+<tt>npthread_waveflag</tt> waves user-defined flag number <tt><i>p</i></tt>.
+<p>
+<tt>npthread_newflag</tt> returns a new flag number each time it is called:
+1, 2, 3, etc.
+Libraries should use <tt>npthread_newflag</tt> to obtain their flag numbers
+so that independent libraries do not bump into each other.
+<p>
+Do not attempt to use user-defined flag waves as counters.
+If a thread is watching a flag,
+and the flag is waved twice in quick succession
+before the thread has a chance to wake up,
+the thread will be called once, not twice.
+<hr>
+<pre>
+ #include "npthread.h"
+ int64 <i>d</i>;
+ npthread_read(<i>d</i>);
+ npthread_write(<i>d</i>);
+</pre>
+<tt>npthread_read</tt> tells the npthread library
+to call the current thread
+when file descriptor <tt><i>d</i></tt> is readable.
+<tt>npthread_write</tt> tells the npthread library
+to call the current thread
+when file descriptor <tt><i>d</i></tt> is writable.
+<p>
+The descriptor must already be open
+and known to the <a href="io.html">io library</a>;
+you must use io_fd() to register descriptors not obtained from io_pipe() etc.
+The descriptor must remain open until the call condition is changed.
+<p>
+Any previous call conditions for the current thread are wiped out.
+For example, the <tt>npthread_sleepnutil</tt> in
+<pre>
+ npthread_sleepuntil(tai6464_add(tai6464_now(),networktimeout));
+ npthread_read(6);
+ return 1;
+</pre>
+has no effect.
+If descriptor 6 is not readable,
+the thread will not be called again,
+even after <tt>networktimeout</tt> expires.
+In contrast,
+<pre>
+ io_timeout(6,tai6464_add(tai6464_now(),networktimeout));
+ npthread_read(6);
+ return 1;
+</pre>
+will impose a time limit on the readability of descriptor 6.
+<p>
+Do not assume that data can actually be read or written
+merely because of a previous <tt>npthread_read</tt> or <tt>npthread_write</tt>.
+Data that is readable when <tt>npthread_start</tt> decides to call this thread
+might be read a moment later by another process.
+Buffer space available for writing when <tt>npthread_start</tt> decides to call this thread might be used a moment later by another process.
+<p>
+Do not assume that data has ever been readable or writable
+merely because of a previous <tt>npthread_read</tt> or <tt>npthread_write</tt>.
+The low-level UNIX routines used by
+<tt>io_wait</tt> could have failed to allocate memory;
+in this case, <tt>npthread_start</tt> has no
+choice but to call all threads waiting for descriptors.
+<hr>
+<pre>
+ #include "npthread.h"
+ npthread_asap();
+</pre>
+<tt>npthread_asap</tt> tells the npthread library
+to call the current thread whenever possible.
+This is how the thread starts out after <tt>npthread_add</tt>.
+</body>
+</html>
diff --git a/doc/tcl/3tcl/opts.3tcl b/doc/tcl/3tcl/opts.3tcl
@@ -0,0 +1,24 @@
+.Dd Oct 13, 2022
+.Dt opts 3tcl
+.Os
+.Sh Name
+.Nm opts
+.Nd pseudo-getopts routine ripped from UmbrellixSSG
+.Sh Synopsis
+[list [list [list len=1+]] [list string]]
+.Nm opts
+\fIlist options\fR
+\fIlist argv\fR
+
+Both arguments are mandatory.
+.Sh Description
+The
+.Nm
+routine takes two arguments, both lists, and returns a list of: a list of lists of 1 or more strings, and a list of strings.
+
+The first argument is a list containing the letter or name of a flag, optionally followed by one or more colons. A letter can then be flagged up with a single dash, followed by the letter (or multiple letters), in the argv input. A name flag can be flagged up with two dashes, followed by the name. Each flag will consume a non-option argument per colon, unless it was preceded with a backslash that was correctly quoted into the string, in which case, the colon becomes part of the option and doesn't consume an element. Two dashes terminates further option parsing. I don't know if that is consumed by a flag with a colon, but I assume it would be. A flag that consumes a non-option argument must consume a non-option argument.
+
+The first list in the return value is a list of lists each containing one or more strings. These represent arguments which were consumed by the function. The first value is the flag, and the second and onward values, if any, are the non-option arguments that were consumed.
+
+The second list is non-option arguments that weren't consumed, and single-letter flags that were consumed but weren't recognised. I am open to comments as to whether this behavior is a bug - see link below - but I happen to believe it is not a bug. I will change it if I get enough (friendly, please!) hatemail.
+.Lk https://umbrellix.net./contact.html
diff --git a/doc/typealloc/3typealloc/typealloc.3 b/doc/typealloc/3typealloc/typealloc.3
@@ -0,0 +1,23 @@
+.Dd Oct 13, 2022
+.Dt typealloc 3
+.Os
+.Sh NAME
+.Nm typealloc
+.Nd a framework for building dynamically-allocated lists of objects represented by data types in C
+.Sh SYNOPSIS
+.In typealloc/typealloc.h
+.Fn TypeAlloc_typedef ta type field len a
+
+In headers (generate separate headers to save object code duplication):
+.In typealloc/typeallocdefs.h
+
+In source (auto-generate libraries for manipulating your TypeAllocs):
+.In typealloc/typealloclib.h
+
+.Fn TypeAlloc_readyplus ta type field len a base ta_rplus
+.Fn TypeAlloc_ready ta type field len a base ta_ready
+.Fn TypeAlloc_append ta type field len a base ta_rplus ta_append
+.Fn TypeAlloc_copy ta type field len a base ta_ready ta_copy
+.Fn TypeAlloc_free ta type field len a base ta_free
+.Sh Description
+TODO: describe all these \fBmacros\fR.
diff --git a/doc/typealloc/example-typeallocs.c b/doc/typealloc/example-typeallocs.c
@@ -0,0 +1,26 @@
+#ifndef TYPEALLOCS_H
+#define TYPEALLOCS_H
+// ugly hack required to avoid redefining
+#include <typealloc.h>
+#include <typealloclib.h>
+//#include <typeallocs.h>
+#include <mxf-remote.h>
+
+TypeAlloc_readyplus(protoAlloc,protocol_t,pt,len,a,10,protoalloc_readyplus)
+TypeAlloc_append(protoAlloc,protocol_t,pt,len,a,10,protoalloc_readyplus,protoalloc_catp)
+
+TypeAlloc_readyplus(saAlloc,stralloc,sa,len,a,10,saalloc_readyplus)
+TypeAlloc_append(saAlloc,stralloc,sa,len,a,10,saalloc_readyplus,saalloc_catsa)
+
+TypeAlloc_readyplus(pfdAlloc,struct pollfd,pfd,len,a,10,pfdalloc_readyplus)
+TypeAlloc_append(pfdAlloc,struct pollfd,pfd,len,a,10,pfdalloc_readyplus,pfdalloc_catpfd)
+
+//TypeAlloc_readyplus(dnslAlloc,dnsl_t,dnsl,len,a,10,dnslalloc_readyplus)
+//TypeAlloc_append(dnslAlloc,dnsl_t,dnsl,len,a,10,dnslalloc_readyplus,dnslalloc_catdnsl)
+
+TypeAlloc_readyplus(ipmxAlloc,ipmx_t,ipmx,len,a,10,ipmxalloc_readyplus)
+TypeAlloc_append(ipmxAlloc,ipmx_t,ipmx,len,a,10,ipmxalloc_readyplus,ipmxalloc_catip)
+
+TypeAlloc_readyplus(mxrAlloc,mxresult_t,mxr,len,a,10,mxralloc_readyplus)
+TypeAlloc_append(mxrAlloc,mxresult_t,mxr,len,a,10,mxralloc_readyplus,mxralloc_catmxr)
+#endif
diff --git a/doc/typealloc/example-typeallocs.h b/doc/typealloc/example-typeallocs.h
@@ -0,0 +1,24 @@
+#ifndef TYPEALLOCS_H
+#define TYPEALLOCS_H
+#include <typealloc.h>
+#include <typeallocdefs.h>
+#include <mxf-remote.h>
+
+TypeAlloc_readyplus(protoAlloc,protocol_t,pt,len,a,10,protoalloc_readyplus)
+TypeAlloc_append(protoAlloc,protocol_t,pt,len,a,10,protoalloc_readyplus,protoalloc_catp)
+
+TypeAlloc_readyplus(saAlloc,stralloc,sa,len,a,10,saalloc_readyplus)
+TypeAlloc_append(saAlloc,stralloc,sa,len,a,10,saalloc_readyplus,saalloc_catsa)
+
+TypeAlloc_readyplus(pfdAlloc,struct pollfd,pfd,len,a,10,pfdalloc_readyplus)
+TypeAlloc_append(pfdAlloc,struct pollfd,pfd,len,a,10,pfdalloc_readyplus,pfdalloc_catpfd)
+
+//TypeAlloc_readyplus(dnslAlloc,dnsl_t,dnsl,len,a,10,dnslalloc_readyplus)
+//TypeAlloc_append(dnslAlloc,dnsl_t,dnsl,len,a,10,dnslalloc_readyplus,dnslalloc_catdnsl)
+
+TypeAlloc_readyplus(ipmxAlloc,ipmx_t,ipmx,len,a,10,ipmxalloc_readyplus)
+TypeAlloc_append(ipmxAlloc,ipmx_t,ipmx,len,a,10,ipmxalloc_readyplus,ipmxalloc_catip)
+
+TypeAlloc_readyplus(mxrAlloc,mxresult_t,mxr,len,a,10,mxralloc_readyplus)
+TypeAlloc_append(mxrAlloc,mxresult_t,mxr,len,a,10,mxralloc_readyplus,mxralloc_catmxr)
+#endif
diff --git a/head/METHODOLOGY b/head/METHODOLOGY
@@ -0,0 +1,5 @@
+/pkg/umbrellix.net/prog/lsuitcase/head to include methodology
+
+This package's headers install to itself/include/libsuitcase. If that's on the filesystem, it may be as simple as a hard link. In the source tree, they are just in head/, which is a directory that upkg-install(8) is perfectly in its rights to obliterate.
+
+It also exports a global path, which must be presented to the administrator for disambiguation if there are any other identically named paths on the system. That path is /include/libsuitcase. On BSDs and Debian, global paths should be installed to /usr/local, except for /cmd (packages/command - for legacy reasons, /command is restricted to names approved by Daniel Bernstein and Paul Jarc) which should be installed directly at / . Custom installations could install them directly at /usr, or directly at / with /usr being symlinked to / .
diff --git a/head/eloop/sc_eloop.h b/head/eloop/sc_eloop.h
@@ -0,0 +1,6 @@
+#ifndef SC_ELOOP_H
+#define SC_ELOOP_H
+
+
+
+#endif // SC_ELOOP_H
diff --git a/head/eloop/sc_eloop_desc.h b/head/eloop/sc_eloop_desc.h
@@ -0,0 +1,17 @@
+#ifndef SC_ELOOP_DESC_H
+#define SC_ELOOP_DESC_H
+
+#include <libsuitcase/uthash/uthash.h>
+#include <poll.h>
+
+typedef struct sc_polldes_t_s sc_polldes_t;
+
+struct sc_polldes_t_s {
+ struct pollfd fd; // stored directly in this struct; used solely as an index for the uthash
+ void* opaque; // a WEAK pointer to an opaque; may be anything or NULL
+ int (*fdcb) (sc_polldes_t *, short, void *);
+ UT_hash_handle hh;
+};
+
+
+#endif // SC_ELOOP_DESC_H
diff --git a/head/eloop/sc_eloop_pid.h b/head/eloop/sc_eloop_pid.h
@@ -0,0 +1,14 @@
+#ifndef SC_ELOOP_PID_H
+#define SC_ELOOP_PID_H
+
+struct sc_proc_t_s;
+typedef struct sc_proc_t_s sc_proc_t;
+
+struct sc_proc_t_s {
+ pid_t pid;
+ void* opaque; // a WEAK pointer to an opaque
+ int (*pdiecb) (sc_proc_t *, int, void *);
+ UT_hash_handle hh;
+}; // callback when a protegé reports ("child dies")
+
+#endif // SC_ELOOP_PID_H
diff --git a/head/ta_stralloc/stralloc.h b/head/ta_stralloc/stralloc.h
@@ -0,0 +1,23 @@
+#ifndef STRALLOC_H
+#define STRALLOC_H
+
+#include "typealloc.h"
+
+GEN_ALLOC_typedef(stralloc,char,s,len,a)
+#define STRALLOC_ZERO {0, 0, 0}
+
+extern int stralloc_starts(stralloc *sa, char *s);
+extern int stralloc_copy(stralloc *sato, stralloc *safrom);
+extern int stralloc_cat(stralloc *sato, stralloc *safrom);
+extern int stralloc_copys(stralloc *sa, char *s);
+extern int stralloc_cats(stralloc *sa, char *s);
+extern int stralloc_copyb(stralloc *sa, char *s, unsigned int n);
+extern int stralloc_catb(stralloc *sa, char *s, unsigned int n);
+
+extern int stralloc_ready();
+extern int stralloc_readyplus();
+extern int stralloc_append(); /* beware: this takes a pointer to 1 char */
+
+#define stralloc_0(sa) stralloc_append(sa,"")
+
+#endif
diff --git a/head/uthash/QUELLE b/head/uthash/QUELLE
@@ -0,0 +1,5 @@
+/pkg/umbrellix.net/prog/suitcase/head/uthash Statement of Origin
+
+These headers were retrieved from, and ultimately originate from, src/*.h, in the project https://github.com/troydhanson/uthash, version @1a53f304aa2db47e8584ddcb16a6587578e245f3 (shortly after v2.3.0).
+
+This portion does not require skalibs. (Why would it?)
diff --git a/head/uthash/utarray.h b/head/uthash/utarray.h
@@ -0,0 +1,248 @@
+/*
+Copyright (c) 2008-2022, Troy D. Hanson https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a dynamic array implementation using macros
+ */
+#ifndef UTARRAY_H
+#define UTARRAY_H
+
+#define UTARRAY_VERSION 2.3.0
+
+#include <stddef.h> /* size_t */
+#include <string.h> /* memset, etc */
+#include <stdlib.h> /* exit */
+
+#ifdef __GNUC__
+#define UTARRAY_UNUSED __attribute__((__unused__))
+#else
+#define UTARRAY_UNUSED
+#endif
+
+#ifdef oom
+#error "The name of macro 'oom' has been changed to 'utarray_oom'. Please update your code."
+#define utarray_oom() oom()
+#endif
+
+#ifndef utarray_oom
+#define utarray_oom() exit(-1)
+#endif
+
+typedef void (ctor_f)(void *dst, const void *src);
+typedef void (dtor_f)(void *elt);
+typedef void (init_f)(void *elt);
+typedef struct {
+ size_t sz;
+ init_f *init;
+ ctor_f *copy;
+ dtor_f *dtor;
+} UT_icd;
+
+typedef struct {
+ unsigned i,n;/* i: index of next available slot, n: num slots */
+ UT_icd icd; /* initializer, copy and destructor functions */
+ char *d; /* n slots of size icd->sz*/
+} UT_array;
+
+#define utarray_init(a,_icd) do { \
+ memset(a,0,sizeof(UT_array)); \
+ (a)->icd = *(_icd); \
+} while(0)
+
+#define utarray_done(a) do { \
+ if ((a)->n) { \
+ if ((a)->icd.dtor) { \
+ unsigned _ut_i; \
+ for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
+ (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \
+ } \
+ } \
+ free((a)->d); \
+ } \
+ (a)->n=0; \
+} while(0)
+
+#define utarray_new(a,_icd) do { \
+ (a) = (UT_array*)malloc(sizeof(UT_array)); \
+ if ((a) == NULL) { \
+ utarray_oom(); \
+ } \
+ utarray_init(a,_icd); \
+} while(0)
+
+#define utarray_free(a) do { \
+ utarray_done(a); \
+ free(a); \
+} while(0)
+
+#define utarray_reserve(a,by) do { \
+ if (((a)->i+(by)) > (a)->n) { \
+ char *utarray_tmp; \
+ while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \
+ utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \
+ if (utarray_tmp == NULL) { \
+ utarray_oom(); \
+ } \
+ (a)->d=utarray_tmp; \
+ } \
+} while(0)
+
+#define utarray_push_back(a,p) do { \
+ utarray_reserve(a,1); \
+ if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \
+ else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \
+} while(0)
+
+#define utarray_pop_back(a) do { \
+ if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \
+ else { (a)->i--; } \
+} while(0)
+
+#define utarray_extend_back(a) do { \
+ utarray_reserve(a,1); \
+ if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \
+ else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \
+ (a)->i++; \
+} while(0)
+
+#define utarray_len(a) ((a)->i)
+
+#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)
+#define _utarray_eltptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j))))
+
+#define utarray_insert(a,p,j) do { \
+ if ((j) > (a)->i) utarray_resize(a,j); \
+ utarray_reserve(a,1); \
+ if ((j) < (a)->i) { \
+ memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \
+ ((a)->i - (j))*((a)->icd.sz)); \
+ } \
+ if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \
+ else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \
+ (a)->i++; \
+} while(0)
+
+#define utarray_inserta(a,w,j) do { \
+ if (utarray_len(w) == 0) break; \
+ if ((j) > (a)->i) utarray_resize(a,j); \
+ utarray_reserve(a,utarray_len(w)); \
+ if ((j) < (a)->i) { \
+ memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \
+ _utarray_eltptr(a,j), \
+ ((a)->i - (j))*((a)->icd.sz)); \
+ } \
+ if ((a)->icd.copy) { \
+ unsigned _ut_i; \
+ for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \
+ (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \
+ } \
+ } else { \
+ memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \
+ utarray_len(w)*((a)->icd.sz)); \
+ } \
+ (a)->i += utarray_len(w); \
+} while(0)
+
+#define utarray_resize(dst,num) do { \
+ unsigned _ut_i; \
+ if ((dst)->i > (unsigned)(num)) { \
+ if ((dst)->icd.dtor) { \
+ for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) { \
+ (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i)); \
+ } \
+ } \
+ } else if ((dst)->i < (unsigned)(num)) { \
+ utarray_reserve(dst, (num) - (dst)->i); \
+ if ((dst)->icd.init) { \
+ for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) { \
+ (dst)->icd.init(_utarray_eltptr(dst, _ut_i)); \
+ } \
+ } else { \
+ memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \
+ } \
+ } \
+ (dst)->i = (num); \
+} while(0)
+
+#define utarray_concat(dst,src) do { \
+ utarray_inserta(dst, src, utarray_len(dst)); \
+} while(0)
+
+#define utarray_erase(a,pos,len) do { \
+ if ((a)->icd.dtor) { \
+ unsigned _ut_i; \
+ for (_ut_i = 0; _ut_i < (len); _ut_i++) { \
+ (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i)); \
+ } \
+ } \
+ if ((a)->i > ((pos) + (len))) { \
+ memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)), \
+ ((a)->i - ((pos) + (len))) * (a)->icd.sz); \
+ } \
+ (a)->i -= (len); \
+} while(0)
+
+#define utarray_renew(a,u) do { \
+ if (a) utarray_clear(a); \
+ else utarray_new(a, u); \
+} while(0)
+
+#define utarray_clear(a) do { \
+ if ((a)->i > 0) { \
+ if ((a)->icd.dtor) { \
+ unsigned _ut_i; \
+ for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
+ (a)->icd.dtor(_utarray_eltptr(a, _ut_i)); \
+ } \
+ } \
+ (a)->i = 0; \
+ } \
+} while(0)
+
+#define utarray_sort(a,cmp) do { \
+ qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \
+} while(0)
+
+#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)
+
+#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)
+#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : (((a)->i != utarray_eltidx(a,e)+1) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL))
+#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) != 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))
+#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)
+#define utarray_eltidx(a,e) (((char*)(e) - (a)->d) / (a)->icd.sz)
+
+/* last we pre-define a few icd for common utarrays of ints and strings */
+static void utarray_str_cpy(void *dst, const void *src) {
+ char *const *srcc = (char *const *)src;
+ char **dstc = (char**)dst;
+ *dstc = (*srcc == NULL) ? NULL : strdup(*srcc);
+}
+static void utarray_str_dtor(void *elt) {
+ char **eltc = (char**)elt;
+ if (*eltc != NULL) free(*eltc);
+}
+static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
+static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL};
+static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL};
+
+
+#endif /* UTARRAY_H */
diff --git a/head/uthash/uthash.h b/head/uthash/uthash.h
@@ -0,0 +1,1140 @@
+/*
+Copyright (c) 2003-2022, Troy D. Hanson https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef UTHASH_H
+#define UTHASH_H
+
+#define UTHASH_VERSION 2.3.0
+
+#include <string.h> /* memcmp, memset, strlen */
+#include <stddef.h> /* ptrdiff_t */
+#include <stdlib.h> /* exit */
+
+#if defined(HASH_DEFINE_OWN_STDINT) && HASH_DEFINE_OWN_STDINT
+/* This codepath is provided for backward compatibility, but I plan to remove it. */
+#warning "HASH_DEFINE_OWN_STDINT is deprecated; please use HASH_NO_STDINT instead"
+typedef unsigned int uint32_t;
+typedef unsigned char uint8_t;
+#elif defined(HASH_NO_STDINT) && HASH_NO_STDINT
+#else
+#include <stdint.h> /* uint8_t, uint32_t */
+#endif
+
+/* These macros use decltype or the earlier __typeof GNU extension.
+ As decltype is only available in newer compilers (VS2010 or gcc 4.3+
+ when compiling c++ source) this code uses whatever method is needed
+ or, for VS2008 where neither is available, uses casting workarounds. */
+#if !defined(DECLTYPE) && !defined(NO_DECLTYPE)
+#if defined(_MSC_VER) /* MS compiler */
+#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
+#define DECLTYPE(x) (decltype(x))
+#else /* VS2008 or older (or VS2010 in C mode) */
+#define NO_DECLTYPE
+#endif
+#elif defined(__MCST__) /* Elbrus C Compiler */
+#define DECLTYPE(x) (__typeof(x))
+#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__)
+#define NO_DECLTYPE
+#else /* GNU, Sun and other compilers */
+#define DECLTYPE(x) (__typeof(x))
+#endif
+#endif
+
+#ifdef NO_DECLTYPE
+#define DECLTYPE(x)
+#define DECLTYPE_ASSIGN(dst,src) \
+do { \
+ char **_da_dst = (char**)(&(dst)); \
+ *_da_dst = (char*)(src); \
+} while (0)
+#else
+#define DECLTYPE_ASSIGN(dst,src) \
+do { \
+ (dst) = DECLTYPE(dst)(src); \
+} while (0)
+#endif
+
+#ifndef uthash_malloc
+#define uthash_malloc(sz) malloc(sz) /* malloc fcn */
+#endif
+#ifndef uthash_free
+#define uthash_free(ptr,sz) free(ptr) /* free fcn */
+#endif
+#ifndef uthash_bzero
+#define uthash_bzero(a,n) memset(a,'\0',n)
+#endif
+#ifndef uthash_strlen
+#define uthash_strlen(s) strlen(s)
+#endif
+
+#ifndef HASH_FUNCTION
+#define HASH_FUNCTION(keyptr,keylen,hashv) HASH_JEN(keyptr, keylen, hashv)
+#endif
+
+#ifndef HASH_KEYCMP
+#define HASH_KEYCMP(a,b,n) memcmp(a,b,n)
+#endif
+
+#ifndef uthash_noexpand_fyi
+#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */
+#endif
+#ifndef uthash_expand_fyi
+#define uthash_expand_fyi(tbl) /* can be defined to log expands */
+#endif
+
+#ifndef HASH_NONFATAL_OOM
+#define HASH_NONFATAL_OOM 0
+#endif
+
+#if HASH_NONFATAL_OOM
+/* malloc failures can be recovered from */
+
+#ifndef uthash_nonfatal_oom
+#define uthash_nonfatal_oom(obj) do {} while (0) /* non-fatal OOM error */
+#endif
+
+#define HASH_RECORD_OOM(oomed) do { (oomed) = 1; } while (0)
+#define IF_HASH_NONFATAL_OOM(x) x
+
+#else
+/* malloc failures result in lost memory, hash tables are unusable */
+
+#ifndef uthash_fatal
+#define uthash_fatal(msg) exit(-1) /* fatal OOM error */
+#endif
+
+#define HASH_RECORD_OOM(oomed) uthash_fatal("out of memory")
+#define IF_HASH_NONFATAL_OOM(x)
+
+#endif
+
+/* initial number of buckets */
+#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */
+#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */
+#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */
+
+/* calculate the element whose hash handle address is hhp */
+#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
+/* calculate the hash handle from element address elp */
+#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle*)(void*)(((char*)(elp)) + ((tbl)->hho)))
+
+#define HASH_ROLLBACK_BKT(hh, head, itemptrhh) \
+do { \
+ struct UT_hash_handle *_hd_hh_item = (itemptrhh); \
+ unsigned _hd_bkt; \
+ HASH_TO_BKT(_hd_hh_item->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
+ (head)->hh.tbl->buckets[_hd_bkt].count++; \
+ _hd_hh_item->hh_next = NULL; \
+ _hd_hh_item->hh_prev = NULL; \
+} while (0)
+
+#define HASH_VALUE(keyptr,keylen,hashv) \
+do { \
+ HASH_FUNCTION(keyptr, keylen, hashv); \
+} while (0)
+
+#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \
+do { \
+ (out) = NULL; \
+ if (head) { \
+ unsigned _hf_bkt; \
+ HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \
+ if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \
+ HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \
+ } \
+ } \
+} while (0)
+
+#define HASH_FIND(hh,head,keyptr,keylen,out) \
+do { \
+ (out) = NULL; \
+ if (head) { \
+ unsigned _hf_hashv; \
+ HASH_VALUE(keyptr, keylen, _hf_hashv); \
+ HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \
+ } \
+} while (0)
+
+#ifdef HASH_BLOOM
+#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM)
+#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL)
+#define HASH_BLOOM_MAKE(tbl,oomed) \
+do { \
+ (tbl)->bloom_nbits = HASH_BLOOM; \
+ (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \
+ if (!(tbl)->bloom_bv) { \
+ HASH_RECORD_OOM(oomed); \
+ } else { \
+ uthash_bzero((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \
+ (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \
+ } \
+} while (0)
+
+#define HASH_BLOOM_FREE(tbl) \
+do { \
+ uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \
+} while (0)
+
+#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U)))
+#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U)))
+
+#define HASH_BLOOM_ADD(tbl,hashv) \
+ HASH_BLOOM_BITSET((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U)))
+
+#define HASH_BLOOM_TEST(tbl,hashv) \
+ HASH_BLOOM_BITTEST((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U)))
+
+#else
+#define HASH_BLOOM_MAKE(tbl,oomed)
+#define HASH_BLOOM_FREE(tbl)
+#define HASH_BLOOM_ADD(tbl,hashv)
+#define HASH_BLOOM_TEST(tbl,hashv) (1)
+#define HASH_BLOOM_BYTELEN 0U
+#endif
+
+#define HASH_MAKE_TABLE(hh,head,oomed) \
+do { \
+ (head)->hh.tbl = (UT_hash_table*)uthash_malloc(sizeof(UT_hash_table)); \
+ if (!(head)->hh.tbl) { \
+ HASH_RECORD_OOM(oomed); \
+ } else { \
+ uthash_bzero((head)->hh.tbl, sizeof(UT_hash_table)); \
+ (head)->hh.tbl->tail = &((head)->hh); \
+ (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \
+ (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \
+ (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \
+ (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \
+ HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \
+ (head)->hh.tbl->signature = HASH_SIGNATURE; \
+ if (!(head)->hh.tbl->buckets) { \
+ HASH_RECORD_OOM(oomed); \
+ uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
+ } else { \
+ uthash_bzero((head)->hh.tbl->buckets, \
+ HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \
+ HASH_BLOOM_MAKE((head)->hh.tbl, oomed); \
+ IF_HASH_NONFATAL_OOM( \
+ if (oomed) { \
+ uthash_free((head)->hh.tbl->buckets, \
+ HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
+ uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
+ } \
+ ) \
+ } \
+ } \
+} while (0)
+
+#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \
+do { \
+ (replaced) = NULL; \
+ HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \
+ if (replaced) { \
+ HASH_DELETE(hh, head, replaced); \
+ } \
+ HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \
+} while (0)
+
+#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \
+do { \
+ (replaced) = NULL; \
+ HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \
+ if (replaced) { \
+ HASH_DELETE(hh, head, replaced); \
+ } \
+ HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \
+} while (0)
+
+#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \
+do { \
+ unsigned _hr_hashv; \
+ HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \
+ HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \
+} while (0)
+
+#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \
+do { \
+ unsigned _hr_hashv; \
+ HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \
+ HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \
+} while (0)
+
+#define HASH_APPEND_LIST(hh, head, add) \
+do { \
+ (add)->hh.next = NULL; \
+ (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \
+ (head)->hh.tbl->tail->next = (add); \
+ (head)->hh.tbl->tail = &((add)->hh); \
+} while (0)
+
+#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \
+do { \
+ do { \
+ if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) { \
+ break; \
+ } \
+ } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \
+} while (0)
+
+#ifdef NO_DECLTYPE
+#undef HASH_AKBI_INNER_LOOP
+#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \
+do { \
+ char *_hs_saved_head = (char*)(head); \
+ do { \
+ DECLTYPE_ASSIGN(head, _hs_iter); \
+ if (cmpfcn(head, add) > 0) { \
+ DECLTYPE_ASSIGN(head, _hs_saved_head); \
+ break; \
+ } \
+ DECLTYPE_ASSIGN(head, _hs_saved_head); \
+ } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \
+} while (0)
+#endif
+
+#if HASH_NONFATAL_OOM
+
+#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \
+do { \
+ if (!(oomed)) { \
+ unsigned _ha_bkt; \
+ (head)->hh.tbl->num_items++; \
+ HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \
+ HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \
+ if (oomed) { \
+ HASH_ROLLBACK_BKT(hh, head, &(add)->hh); \
+ HASH_DELETE_HH(hh, head, &(add)->hh); \
+ (add)->hh.tbl = NULL; \
+ uthash_nonfatal_oom(add); \
+ } else { \
+ HASH_BLOOM_ADD((head)->hh.tbl, hashval); \
+ HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \
+ } \
+ } else { \
+ (add)->hh.tbl = NULL; \
+ uthash_nonfatal_oom(add); \
+ } \
+} while (0)
+
+#else
+
+#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \
+do { \
+ unsigned _ha_bkt; \
+ (head)->hh.tbl->num_items++; \
+ HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \
+ HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \
+ HASH_BLOOM_ADD((head)->hh.tbl, hashval); \
+ HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \
+} while (0)
+
+#endif
+
+
+#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \
+do { \
+ IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \
+ (add)->hh.hashv = (hashval); \
+ (add)->hh.key = (char*) (keyptr); \
+ (add)->hh.keylen = (unsigned) (keylen_in); \
+ if (!(head)) { \
+ (add)->hh.next = NULL; \
+ (add)->hh.prev = NULL; \
+ HASH_MAKE_TABLE(hh, add, _ha_oomed); \
+ IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \
+ (head) = (add); \
+ IF_HASH_NONFATAL_OOM( } ) \
+ } else { \
+ void *_hs_iter = (head); \
+ (add)->hh.tbl = (head)->hh.tbl; \
+ HASH_AKBI_INNER_LOOP(hh, head, add, cmpfcn); \
+ if (_hs_iter) { \
+ (add)->hh.next = _hs_iter; \
+ if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \
+ HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \
+ } else { \
+ (head) = (add); \
+ } \
+ HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add); \
+ } else { \
+ HASH_APPEND_LIST(hh, head, add); \
+ } \
+ } \
+ HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \
+ HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE_INORDER"); \
+} while (0)
+
+#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \
+do { \
+ unsigned _hs_hashv; \
+ HASH_VALUE(keyptr, keylen_in, _hs_hashv); \
+ HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \
+} while (0)
+
+#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \
+ HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn)
+
+#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \
+ HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn)
+
+#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \
+do { \
+ IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \
+ (add)->hh.hashv = (hashval); \
+ (add)->hh.key = (const void*) (keyptr); \
+ (add)->hh.keylen = (unsigned) (keylen_in); \
+ if (!(head)) { \
+ (add)->hh.next = NULL; \
+ (add)->hh.prev = NULL; \
+ HASH_MAKE_TABLE(hh, add, _ha_oomed); \
+ IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \
+ (head) = (add); \
+ IF_HASH_NONFATAL_OOM( } ) \
+ } else { \
+ (add)->hh.tbl = (head)->hh.tbl; \
+ HASH_APPEND_LIST(hh, head, add); \
+ } \
+ HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \
+ HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE"); \
+} while (0)
+
+#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \
+do { \
+ unsigned _ha_hashv; \
+ HASH_VALUE(keyptr, keylen_in, _ha_hashv); \
+ HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \
+} while (0)
+
+#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \
+ HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add)
+
+#define HASH_ADD(hh,head,fieldname,keylen_in,add) \
+ HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add)
+
+#define HASH_TO_BKT(hashv,num_bkts,bkt) \
+do { \
+ bkt = ((hashv) & ((num_bkts) - 1U)); \
+} while (0)
+
+/* delete "delptr" from the hash table.
+ * "the usual" patch-up process for the app-order doubly-linked-list.
+ * The use of _hd_hh_del below deserves special explanation.
+ * These used to be expressed using (delptr) but that led to a bug
+ * if someone used the same symbol for the head and deletee, like
+ * HASH_DELETE(hh,users,users);
+ * We want that to work, but by changing the head (users) below
+ * we were forfeiting our ability to further refer to the deletee (users)
+ * in the patch-up process. Solution: use scratch space to
+ * copy the deletee pointer, then the latter references are via that
+ * scratch pointer rather than through the repointed (users) symbol.
+ */
+#define HASH_DELETE(hh,head,delptr) \
+ HASH_DELETE_HH(hh, head, &(delptr)->hh)
+
+#define HASH_DELETE_HH(hh,head,delptrhh) \
+do { \
+ struct UT_hash_handle *_hd_hh_del = (delptrhh); \
+ if ((_hd_hh_del->prev == NULL) && (_hd_hh_del->next == NULL)) { \
+ HASH_BLOOM_FREE((head)->hh.tbl); \
+ uthash_free((head)->hh.tbl->buckets, \
+ (head)->hh.tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
+ uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
+ (head) = NULL; \
+ } else { \
+ unsigned _hd_bkt; \
+ if (_hd_hh_del == (head)->hh.tbl->tail) { \
+ (head)->hh.tbl->tail = HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev); \
+ } \
+ if (_hd_hh_del->prev != NULL) { \
+ HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev)->next = _hd_hh_del->next; \
+ } else { \
+ DECLTYPE_ASSIGN(head, _hd_hh_del->next); \
+ } \
+ if (_hd_hh_del->next != NULL) { \
+ HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->next)->prev = _hd_hh_del->prev; \
+ } \
+ HASH_TO_BKT(_hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
+ HASH_DEL_IN_BKT((head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \
+ (head)->hh.tbl->num_items--; \
+ } \
+ HASH_FSCK(hh, head, "HASH_DELETE_HH"); \
+} while (0)
+
+/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */
+#define HASH_FIND_STR(head,findstr,out) \
+do { \
+ unsigned _uthash_hfstr_keylen = (unsigned)uthash_strlen(findstr); \
+ HASH_FIND(hh, head, findstr, _uthash_hfstr_keylen, out); \
+} while (0)
+#define HASH_ADD_STR(head,strfield,add) \
+do { \
+ unsigned _uthash_hastr_keylen = (unsigned)uthash_strlen((add)->strfield); \
+ HASH_ADD(hh, head, strfield[0], _uthash_hastr_keylen, add); \
+} while (0)
+#define HASH_REPLACE_STR(head,strfield,add,replaced) \
+do { \
+ unsigned _uthash_hrstr_keylen = (unsigned)uthash_strlen((add)->strfield); \
+ HASH_REPLACE(hh, head, strfield[0], _uthash_hrstr_keylen, add, replaced); \
+} while (0)
+#define HASH_FIND_INT(head,findint,out) \
+ HASH_FIND(hh,head,findint,sizeof(int),out)
+#define HASH_ADD_INT(head,intfield,add) \
+ HASH_ADD(hh,head,intfield,sizeof(int),add)
+#define HASH_REPLACE_INT(head,intfield,add,replaced) \
+ HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced)
+#define HASH_FIND_PTR(head,findptr,out) \
+ HASH_FIND(hh,head,findptr,sizeof(void *),out)
+#define HASH_ADD_PTR(head,ptrfield,add) \
+ HASH_ADD(hh,head,ptrfield,sizeof(void *),add)
+#define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \
+ HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced)
+#define HASH_DEL(head,delptr) \
+ HASH_DELETE(hh,head,delptr)
+
+/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
+ * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined.
+ */
+#ifdef HASH_DEBUG
+#include <stdio.h> /* fprintf, stderr */
+#define HASH_OOPS(...) do { fprintf(stderr, __VA_ARGS__); exit(-1); } while (0)
+#define HASH_FSCK(hh,head,where) \
+do { \
+ struct UT_hash_handle *_thh; \
+ if (head) { \
+ unsigned _bkt_i; \
+ unsigned _count = 0; \
+ char *_prev; \
+ for (_bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; ++_bkt_i) { \
+ unsigned _bkt_count = 0; \
+ _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \
+ _prev = NULL; \
+ while (_thh) { \
+ if (_prev != (char*)(_thh->hh_prev)) { \
+ HASH_OOPS("%s: invalid hh_prev %p, actual %p\n", \
+ (where), (void*)_thh->hh_prev, (void*)_prev); \
+ } \
+ _bkt_count++; \
+ _prev = (char*)(_thh); \
+ _thh = _thh->hh_next; \
+ } \
+ _count += _bkt_count; \
+ if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \
+ HASH_OOPS("%s: invalid bucket count %u, actual %u\n", \
+ (where), (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \
+ } \
+ } \
+ if (_count != (head)->hh.tbl->num_items) { \
+ HASH_OOPS("%s: invalid hh item count %u, actual %u\n", \
+ (where), (head)->hh.tbl->num_items, _count); \
+ } \
+ _count = 0; \
+ _prev = NULL; \
+ _thh = &(head)->hh; \
+ while (_thh) { \
+ _count++; \
+ if (_prev != (char*)_thh->prev) { \
+ HASH_OOPS("%s: invalid prev %p, actual %p\n", \
+ (where), (void*)_thh->prev, (void*)_prev); \
+ } \
+ _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \
+ _thh = (_thh->next ? HH_FROM_ELMT((head)->hh.tbl, _thh->next) : NULL); \
+ } \
+ if (_count != (head)->hh.tbl->num_items) { \
+ HASH_OOPS("%s: invalid app item count %u, actual %u\n", \
+ (where), (head)->hh.tbl->num_items, _count); \
+ } \
+ } \
+} while (0)
+#else
+#define HASH_FSCK(hh,head,where)
+#endif
+
+/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to
+ * the descriptor to which this macro is defined for tuning the hash function.
+ * The app can #include <unistd.h> to get the prototype for write(2). */
+#ifdef HASH_EMIT_KEYS
+#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
+do { \
+ unsigned _klen = fieldlen; \
+ write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \
+ write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \
+} while (0)
+#else
+#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
+#endif
+
+/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
+#define HASH_BER(key,keylen,hashv) \
+do { \
+ unsigned _hb_keylen = (unsigned)keylen; \
+ const unsigned char *_hb_key = (const unsigned char*)(key); \
+ (hashv) = 0; \
+ while (_hb_keylen-- != 0U) { \
+ (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \
+ } \
+} while (0)
+
+
+/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
+ * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
+ * (archive link: https://archive.is/Ivcan )
+ */
+#define HASH_SAX(key,keylen,hashv) \
+do { \
+ unsigned _sx_i; \
+ const unsigned char *_hs_key = (const unsigned char*)(key); \
+ hashv = 0; \
+ for (_sx_i=0; _sx_i < keylen; _sx_i++) { \
+ hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
+ } \
+} while (0)
+/* FNV-1a variation */
+#define HASH_FNV(key,keylen,hashv) \
+do { \
+ unsigned _fn_i; \
+ const unsigned char *_hf_key = (const unsigned char*)(key); \
+ (hashv) = 2166136261U; \
+ for (_fn_i=0; _fn_i < keylen; _fn_i++) { \
+ hashv = hashv ^ _hf_key[_fn_i]; \
+ hashv = hashv * 16777619U; \
+ } \
+} while (0)
+
+#define HASH_OAT(key,keylen,hashv) \
+do { \
+ unsigned _ho_i; \
+ const unsigned char *_ho_key=(const unsigned char*)(key); \
+ hashv = 0; \
+ for(_ho_i=0; _ho_i < keylen; _ho_i++) { \
+ hashv += _ho_key[_ho_i]; \
+ hashv += (hashv << 10); \
+ hashv ^= (hashv >> 6); \
+ } \
+ hashv += (hashv << 3); \
+ hashv ^= (hashv >> 11); \
+ hashv += (hashv << 15); \
+} while (0)
+
+#define HASH_JEN_MIX(a,b,c) \
+do { \
+ a -= b; a -= c; a ^= ( c >> 13 ); \
+ b -= c; b -= a; b ^= ( a << 8 ); \
+ c -= a; c -= b; c ^= ( b >> 13 ); \
+ a -= b; a -= c; a ^= ( c >> 12 ); \
+ b -= c; b -= a; b ^= ( a << 16 ); \
+ c -= a; c -= b; c ^= ( b >> 5 ); \
+ a -= b; a -= c; a ^= ( c >> 3 ); \
+ b -= c; b -= a; b ^= ( a << 10 ); \
+ c -= a; c -= b; c ^= ( b >> 15 ); \
+} while (0)
+
+#define HASH_JEN(key,keylen,hashv) \
+do { \
+ unsigned _hj_i,_hj_j,_hj_k; \
+ unsigned const char *_hj_key=(unsigned const char*)(key); \
+ hashv = 0xfeedbeefu; \
+ _hj_i = _hj_j = 0x9e3779b9u; \
+ _hj_k = (unsigned)(keylen); \
+ while (_hj_k >= 12U) { \
+ _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \
+ + ( (unsigned)_hj_key[2] << 16 ) \
+ + ( (unsigned)_hj_key[3] << 24 ) ); \
+ _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \
+ + ( (unsigned)_hj_key[6] << 16 ) \
+ + ( (unsigned)_hj_key[7] << 24 ) ); \
+ hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \
+ + ( (unsigned)_hj_key[10] << 16 ) \
+ + ( (unsigned)_hj_key[11] << 24 ) ); \
+ \
+ HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
+ \
+ _hj_key += 12; \
+ _hj_k -= 12U; \
+ } \
+ hashv += (unsigned)(keylen); \
+ switch ( _hj_k ) { \
+ case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \
+ case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \
+ case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \
+ case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \
+ case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \
+ case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \
+ case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \
+ case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \
+ case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \
+ case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \
+ case 1: _hj_i += _hj_key[0]; /* FALLTHROUGH */ \
+ default: ; \
+ } \
+ HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
+} while (0)
+
+/* The Paul Hsieh hash function */
+#undef get16bits
+#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
+ || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
+#define get16bits(d) (*((const uint16_t *) (d)))
+#endif
+
+#if !defined (get16bits)
+#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
+ +(uint32_t)(((const uint8_t *)(d))[0]) )
+#endif
+#define HASH_SFH(key,keylen,hashv) \
+do { \
+ unsigned const char *_sfh_key=(unsigned const char*)(key); \
+ uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \
+ \
+ unsigned _sfh_rem = _sfh_len & 3U; \
+ _sfh_len >>= 2; \
+ hashv = 0xcafebabeu; \
+ \
+ /* Main loop */ \
+ for (;_sfh_len > 0U; _sfh_len--) { \
+ hashv += get16bits (_sfh_key); \
+ _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \
+ hashv = (hashv << 16) ^ _sfh_tmp; \
+ _sfh_key += 2U*sizeof (uint16_t); \
+ hashv += hashv >> 11; \
+ } \
+ \
+ /* Handle end cases */ \
+ switch (_sfh_rem) { \
+ case 3: hashv += get16bits (_sfh_key); \
+ hashv ^= hashv << 16; \
+ hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \
+ hashv += hashv >> 11; \
+ break; \
+ case 2: hashv += get16bits (_sfh_key); \
+ hashv ^= hashv << 11; \
+ hashv += hashv >> 17; \
+ break; \
+ case 1: hashv += *_sfh_key; \
+ hashv ^= hashv << 10; \
+ hashv += hashv >> 1; \
+ break; \
+ default: ; \
+ } \
+ \
+ /* Force "avalanching" of final 127 bits */ \
+ hashv ^= hashv << 3; \
+ hashv += hashv >> 5; \
+ hashv ^= hashv << 4; \
+ hashv += hashv >> 17; \
+ hashv ^= hashv << 25; \
+ hashv += hashv >> 6; \
+} while (0)
+
+/* iterate over items in a known bucket to find desired item */
+#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \
+do { \
+ if ((head).hh_head != NULL) { \
+ DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \
+ } else { \
+ (out) = NULL; \
+ } \
+ while ((out) != NULL) { \
+ if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \
+ if (HASH_KEYCMP((out)->hh.key, keyptr, keylen_in) == 0) { \
+ break; \
+ } \
+ } \
+ if ((out)->hh.hh_next != NULL) { \
+ DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \
+ } else { \
+ (out) = NULL; \
+ } \
+ } \
+} while (0)
+
+/* add an item to a bucket */
+#define HASH_ADD_TO_BKT(head,hh,addhh,oomed) \
+do { \
+ UT_hash_bucket *_ha_head = &(head); \
+ _ha_head->count++; \
+ (addhh)->hh_next = _ha_head->hh_head; \
+ (addhh)->hh_prev = NULL; \
+ if (_ha_head->hh_head != NULL) { \
+ _ha_head->hh_head->hh_prev = (addhh); \
+ } \
+ _ha_head->hh_head = (addhh); \
+ if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \
+ && !(addhh)->tbl->noexpand) { \
+ HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed); \
+ IF_HASH_NONFATAL_OOM( \
+ if (oomed) { \
+ HASH_DEL_IN_BKT(head,addhh); \
+ } \
+ ) \
+ } \
+} while (0)
+
+/* remove an item from a given bucket */
+#define HASH_DEL_IN_BKT(head,delhh) \
+do { \
+ UT_hash_bucket *_hd_head = &(head); \
+ _hd_head->count--; \
+ if (_hd_head->hh_head == (delhh)) { \
+ _hd_head->hh_head = (delhh)->hh_next; \
+ } \
+ if ((delhh)->hh_prev) { \
+ (delhh)->hh_prev->hh_next = (delhh)->hh_next; \
+ } \
+ if ((delhh)->hh_next) { \
+ (delhh)->hh_next->hh_prev = (delhh)->hh_prev; \
+ } \
+} while (0)
+
+/* Bucket expansion has the effect of doubling the number of buckets
+ * and redistributing the items into the new buckets. Ideally the
+ * items will distribute more or less evenly into the new buckets
+ * (the extent to which this is true is a measure of the quality of
+ * the hash function as it applies to the key domain).
+ *
+ * With the items distributed into more buckets, the chain length
+ * (item count) in each bucket is reduced. Thus by expanding buckets
+ * the hash keeps a bound on the chain length. This bounded chain
+ * length is the essence of how a hash provides constant time lookup.
+ *
+ * The calculation of tbl->ideal_chain_maxlen below deserves some
+ * explanation. First, keep in mind that we're calculating the ideal
+ * maximum chain length based on the *new* (doubled) bucket count.
+ * In fractions this is just n/b (n=number of items,b=new num buckets).
+ * Since the ideal chain length is an integer, we want to calculate
+ * ceil(n/b). We don't depend on floating point arithmetic in this
+ * hash, so to calculate ceil(n/b) with integers we could write
+ *
+ * ceil(n/b) = (n/b) + ((n%b)?1:0)
+ *
+ * and in fact a previous version of this hash did just that.
+ * But now we have improved things a bit by recognizing that b is
+ * always a power of two. We keep its base 2 log handy (call it lb),
+ * so now we can write this with a bit shift and logical AND:
+ *
+ * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
+ *
+ */
+#define HASH_EXPAND_BUCKETS(hh,tbl,oomed) \
+do { \
+ unsigned _he_bkt; \
+ unsigned _he_bkt_i; \
+ struct UT_hash_handle *_he_thh, *_he_hh_nxt; \
+ UT_hash_bucket *_he_new_buckets, *_he_newbkt; \
+ _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \
+ sizeof(struct UT_hash_bucket) * (tbl)->num_buckets * 2U); \
+ if (!_he_new_buckets) { \
+ HASH_RECORD_OOM(oomed); \
+ } else { \
+ uthash_bzero(_he_new_buckets, \
+ sizeof(struct UT_hash_bucket) * (tbl)->num_buckets * 2U); \
+ (tbl)->ideal_chain_maxlen = \
+ ((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) + \
+ ((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \
+ (tbl)->nonideal_items = 0; \
+ for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) { \
+ _he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head; \
+ while (_he_thh != NULL) { \
+ _he_hh_nxt = _he_thh->hh_next; \
+ HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt); \
+ _he_newbkt = &(_he_new_buckets[_he_bkt]); \
+ if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) { \
+ (tbl)->nonideal_items++; \
+ if (_he_newbkt->count > _he_newbkt->expand_mult * (tbl)->ideal_chain_maxlen) { \
+ _he_newbkt->expand_mult++; \
+ } \
+ } \
+ _he_thh->hh_prev = NULL; \
+ _he_thh->hh_next = _he_newbkt->hh_head; \
+ if (_he_newbkt->hh_head != NULL) { \
+ _he_newbkt->hh_head->hh_prev = _he_thh; \
+ } \
+ _he_newbkt->hh_head = _he_thh; \
+ _he_thh = _he_hh_nxt; \
+ } \
+ } \
+ uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \
+ (tbl)->num_buckets *= 2U; \
+ (tbl)->log2_num_buckets++; \
+ (tbl)->buckets = _he_new_buckets; \
+ (tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ? \
+ ((tbl)->ineff_expands+1U) : 0U; \
+ if ((tbl)->ineff_expands > 1U) { \
+ (tbl)->noexpand = 1; \
+ uthash_noexpand_fyi(tbl); \
+ } \
+ uthash_expand_fyi(tbl); \
+ } \
+} while (0)
+
+
+/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
+/* Note that HASH_SORT assumes the hash handle name to be hh.
+ * HASH_SRT was added to allow the hash handle name to be passed in. */
+#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
+#define HASH_SRT(hh,head,cmpfcn) \
+do { \
+ unsigned _hs_i; \
+ unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \
+ struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \
+ if (head != NULL) { \
+ _hs_insize = 1; \
+ _hs_looping = 1; \
+ _hs_list = &((head)->hh); \
+ while (_hs_looping != 0U) { \
+ _hs_p = _hs_list; \
+ _hs_list = NULL; \
+ _hs_tail = NULL; \
+ _hs_nmerges = 0; \
+ while (_hs_p != NULL) { \
+ _hs_nmerges++; \
+ _hs_q = _hs_p; \
+ _hs_psize = 0; \
+ for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) { \
+ _hs_psize++; \
+ _hs_q = ((_hs_q->next != NULL) ? \
+ HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \
+ if (_hs_q == NULL) { \
+ break; \
+ } \
+ } \
+ _hs_qsize = _hs_insize; \
+ while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) { \
+ if (_hs_psize == 0U) { \
+ _hs_e = _hs_q; \
+ _hs_q = ((_hs_q->next != NULL) ? \
+ HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \
+ _hs_qsize--; \
+ } else if ((_hs_qsize == 0U) || (_hs_q == NULL)) { \
+ _hs_e = _hs_p; \
+ if (_hs_p != NULL) { \
+ _hs_p = ((_hs_p->next != NULL) ? \
+ HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \
+ } \
+ _hs_psize--; \
+ } else if ((cmpfcn( \
+ DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)), \
+ DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q)) \
+ )) <= 0) { \
+ _hs_e = _hs_p; \
+ if (_hs_p != NULL) { \
+ _hs_p = ((_hs_p->next != NULL) ? \
+ HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \
+ } \
+ _hs_psize--; \
+ } else { \
+ _hs_e = _hs_q; \
+ _hs_q = ((_hs_q->next != NULL) ? \
+ HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \
+ _hs_qsize--; \
+ } \
+ if ( _hs_tail != NULL ) { \
+ _hs_tail->next = ((_hs_e != NULL) ? \
+ ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL); \
+ } else { \
+ _hs_list = _hs_e; \
+ } \
+ if (_hs_e != NULL) { \
+ _hs_e->prev = ((_hs_tail != NULL) ? \
+ ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL); \
+ } \
+ _hs_tail = _hs_e; \
+ } \
+ _hs_p = _hs_q; \
+ } \
+ if (_hs_tail != NULL) { \
+ _hs_tail->next = NULL; \
+ } \
+ if (_hs_nmerges <= 1U) { \
+ _hs_looping = 0; \
+ (head)->hh.tbl->tail = _hs_tail; \
+ DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \
+ } \
+ _hs_insize *= 2U; \
+ } \
+ HASH_FSCK(hh, head, "HASH_SRT"); \
+ } \
+} while (0)
+
+/* This function selects items from one hash into another hash.
+ * The end result is that the selected items have dual presence
+ * in both hashes. There is no copy of the items made; rather
+ * they are added into the new hash through a secondary hash
+ * hash handle that must be present in the structure. */
+#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \
+do { \
+ unsigned _src_bkt, _dst_bkt; \
+ void *_last_elt = NULL, *_elt; \
+ UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \
+ ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \
+ if ((src) != NULL) { \
+ for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \
+ for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \
+ _src_hh != NULL; \
+ _src_hh = _src_hh->hh_next) { \
+ _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \
+ if (cond(_elt)) { \
+ IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; ) \
+ _dst_hh = (UT_hash_handle*)(void*)(((char*)_elt) + _dst_hho); \
+ _dst_hh->key = _src_hh->key; \
+ _dst_hh->keylen = _src_hh->keylen; \
+ _dst_hh->hashv = _src_hh->hashv; \
+ _dst_hh->prev = _last_elt; \
+ _dst_hh->next = NULL; \
+ if (_last_elt_hh != NULL) { \
+ _last_elt_hh->next = _elt; \
+ } \
+ if ((dst) == NULL) { \
+ DECLTYPE_ASSIGN(dst, _elt); \
+ HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed); \
+ IF_HASH_NONFATAL_OOM( \
+ if (_hs_oomed) { \
+ uthash_nonfatal_oom(_elt); \
+ (dst) = NULL; \
+ continue; \
+ } \
+ ) \
+ } else { \
+ _dst_hh->tbl = (dst)->hh_dst.tbl; \
+ } \
+ HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \
+ HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \
+ (dst)->hh_dst.tbl->num_items++; \
+ IF_HASH_NONFATAL_OOM( \
+ if (_hs_oomed) { \
+ HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh); \
+ HASH_DELETE_HH(hh_dst, dst, _dst_hh); \
+ _dst_hh->tbl = NULL; \
+ uthash_nonfatal_oom(_elt); \
+ continue; \
+ } \
+ ) \
+ HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv); \
+ _last_elt = _elt; \
+ _last_elt_hh = _dst_hh; \
+ } \
+ } \
+ } \
+ } \
+ HASH_FSCK(hh_dst, dst, "HASH_SELECT"); \
+} while (0)
+
+#define HASH_CLEAR(hh,head) \
+do { \
+ if ((head) != NULL) { \
+ HASH_BLOOM_FREE((head)->hh.tbl); \
+ uthash_free((head)->hh.tbl->buckets, \
+ (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \
+ uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
+ (head) = NULL; \
+ } \
+} while (0)
+
+#define HASH_OVERHEAD(hh,head) \
+ (((head) != NULL) ? ( \
+ (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \
+ ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \
+ sizeof(UT_hash_table) + \
+ (HASH_BLOOM_BYTELEN))) : 0U)
+
+#ifdef NO_DECLTYPE
+#define HASH_ITER(hh,head,el,tmp) \
+for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \
+ (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL)))
+#else
+#define HASH_ITER(hh,head,el,tmp) \
+for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \
+ (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))
+#endif
+
+/* obtain a count of items in the hash */
+#define HASH_COUNT(head) HASH_CNT(hh,head)
+#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)
+
+typedef struct UT_hash_bucket {
+ struct UT_hash_handle *hh_head;
+ unsigned count;
+
+ /* expand_mult is normally set to 0. In this situation, the max chain length
+ * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If
+ * the bucket's chain exceeds this length, bucket expansion is triggered).
+ * However, setting expand_mult to a non-zero value delays bucket expansion
+ * (that would be triggered by additions to this particular bucket)
+ * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH.
+ * (The multiplier is simply expand_mult+1). The whole idea of this
+ * multiplier is to reduce bucket expansions, since they are expensive, in
+ * situations where we know that a particular bucket tends to be overused.
+ * It is better to let its chain length grow to a longer yet-still-bounded
+ * value, than to do an O(n) bucket expansion too often.
+ */
+ unsigned expand_mult;
+
+} UT_hash_bucket;
+
+/* random signature used only to find hash tables in external analysis */
+#define HASH_SIGNATURE 0xa0111fe1u
+#define HASH_BLOOM_SIGNATURE 0xb12220f2u
+
+typedef struct UT_hash_table {
+ UT_hash_bucket *buckets;
+ unsigned num_buckets, log2_num_buckets;
+ unsigned num_items;
+ struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
+ ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
+
+ /* in an ideal situation (all buckets used equally), no bucket would have
+ * more than ceil(#items/#buckets) items. that's the ideal chain length. */
+ unsigned ideal_chain_maxlen;
+
+ /* nonideal_items is the number of items in the hash whose chain position
+ * exceeds the ideal chain maxlen. these items pay the penalty for an uneven
+ * hash distribution; reaching them in a chain traversal takes >ideal steps */
+ unsigned nonideal_items;
+
+ /* ineffective expands occur when a bucket doubling was performed, but
+ * afterward, more than half the items in the hash had nonideal chain
+ * positions. If this happens on two consecutive expansions we inhibit any
+ * further expansion, as it's not helping; this happens when the hash
+ * function isn't a good fit for the key domain. When expansion is inhibited
+ * the hash will still work, albeit no longer in constant time. */
+ unsigned ineff_expands, noexpand;
+
+ uint32_t signature; /* used only to find hash tables in external analysis */
+#ifdef HASH_BLOOM
+ uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
+ uint8_t *bloom_bv;
+ uint8_t bloom_nbits;
+#endif
+
+} UT_hash_table;
+
+typedef struct UT_hash_handle {
+ struct UT_hash_table *tbl;
+ void *prev; /* prev element in app order */
+ void *next; /* next element in app order */
+ struct UT_hash_handle *hh_prev; /* previous hh in bucket order */
+ struct UT_hash_handle *hh_next; /* next hh in bucket order */
+ const void *key; /* ptr to enclosing struct's key */
+ unsigned keylen; /* enclosing struct's key len */
+ unsigned hashv; /* result of hash-fcn(key) */
+} UT_hash_handle;
+
+#endif /* UTHASH_H */
diff --git a/head/uthash/utlist.h b/head/uthash/utlist.h
@@ -0,0 +1,1075 @@
+/*
+Copyright (c) 2007-2022, Troy D. Hanson https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef UTLIST_H
+#define UTLIST_H
+
+#define UTLIST_VERSION 2.3.0
+
+#include <assert.h>
+
+/*
+ * This file contains macros to manipulate singly and doubly-linked lists.
+ *
+ * 1. LL_ macros: singly-linked lists.
+ * 2. DL_ macros: doubly-linked lists.
+ * 3. CDL_ macros: circular doubly-linked lists.
+ *
+ * To use singly-linked lists, your structure must have a "next" pointer.
+ * To use doubly-linked lists, your structure must "prev" and "next" pointers.
+ * Either way, the pointer to the head of the list must be initialized to NULL.
+ *
+ * ----------------.EXAMPLE -------------------------
+ * struct item {
+ * int id;
+ * struct item *prev, *next;
+ * }
+ *
+ * struct item *list = NULL:
+ *
+ * int main() {
+ * struct item *item;
+ * ... allocate and populate item ...
+ * DL_APPEND(list, item);
+ * }
+ * --------------------------------------------------
+ *
+ * For doubly-linked lists, the append and delete macros are O(1)
+ * For singly-linked lists, append and delete are O(n) but prepend is O(1)
+ * The sort macro is O(n log(n)) for all types of single/double/circular lists.
+ */
+
+/* These macros use decltype or the earlier __typeof GNU extension.
+ As decltype is only available in newer compilers (VS2010 or gcc 4.3+
+ when compiling c++ source) this code uses whatever method is needed
+ or, for VS2008 where neither is available, uses casting workarounds. */
+#if !defined(LDECLTYPE) && !defined(NO_DECLTYPE)
+#if defined(_MSC_VER) /* MS compiler */
+#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
+#define LDECLTYPE(x) decltype(x)
+#else /* VS2008 or older (or VS2010 in C mode) */
+#define NO_DECLTYPE
+#endif
+#elif defined(__MCST__) /* Elbrus C Compiler */
+#define LDECLTYPE(x) __typeof(x)
+#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__)
+#define NO_DECLTYPE
+#else /* GNU, Sun and other compilers */
+#define LDECLTYPE(x) __typeof(x)
+#endif
+#endif
+
+/* for VS2008 we use some workarounds to get around the lack of decltype,
+ * namely, we always reassign our tmp variable to the list head if we need
+ * to dereference its prev/next pointers, and save/restore the real head.*/
+#ifdef NO_DECLTYPE
+#define IF_NO_DECLTYPE(x) x
+#define LDECLTYPE(x) char*
+#define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
+#define UTLIST_NEXT(elt,list,next) ((char*)((list)->next))
+#define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
+/* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */
+#define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
+#define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
+#define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
+#else
+#define IF_NO_DECLTYPE(x)
+#define UTLIST_SV(elt,list)
+#define UTLIST_NEXT(elt,list,next) ((elt)->next)
+#define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
+/* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */
+#define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
+#define UTLIST_RS(list)
+#define UTLIST_CASTASGN(a,b) (a)=(b)
+#endif
+
+/******************************************************************************
+ * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
+ * Unwieldy variable names used here to avoid shadowing passed-in variables. *
+ *****************************************************************************/
+#define LL_SORT(list, cmp) \
+ LL_SORT2(list, cmp, next)
+
+#define LL_SORT2(list, cmp, next) \
+do { \
+ LDECLTYPE(list) _ls_p; \
+ LDECLTYPE(list) _ls_q; \
+ LDECLTYPE(list) _ls_e; \
+ LDECLTYPE(list) _ls_tail; \
+ IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \
+ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
+ if (list) { \
+ _ls_insize = 1; \
+ _ls_looping = 1; \
+ while (_ls_looping) { \
+ UTLIST_CASTASGN(_ls_p,list); \
+ (list) = NULL; \
+ _ls_tail = NULL; \
+ _ls_nmerges = 0; \
+ while (_ls_p) { \
+ _ls_nmerges++; \
+ _ls_q = _ls_p; \
+ _ls_psize = 0; \
+ for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
+ _ls_psize++; \
+ UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \
+ if (!_ls_q) break; \
+ } \
+ _ls_qsize = _ls_insize; \
+ while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
+ if (_ls_psize == 0) { \
+ _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
+ UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
+ } else if (_ls_qsize == 0 || !_ls_q) { \
+ _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
+ UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
+ } else if (cmp(_ls_p,_ls_q) <= 0) { \
+ _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
+ UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
+ } else { \
+ _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
+ UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
+ } \
+ if (_ls_tail) { \
+ UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
+ } else { \
+ UTLIST_CASTASGN(list,_ls_e); \
+ } \
+ _ls_tail = _ls_e; \
+ } \
+ _ls_p = _ls_q; \
+ } \
+ if (_ls_tail) { \
+ UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \
+ } \
+ if (_ls_nmerges <= 1) { \
+ _ls_looping=0; \
+ } \
+ _ls_insize *= 2; \
+ } \
+ } \
+} while (0)
+
+
+#define DL_SORT(list, cmp) \
+ DL_SORT2(list, cmp, prev, next)
+
+#define DL_SORT2(list, cmp, prev, next) \
+do { \
+ LDECLTYPE(list) _ls_p; \
+ LDECLTYPE(list) _ls_q; \
+ LDECLTYPE(list) _ls_e; \
+ LDECLTYPE(list) _ls_tail; \
+ IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \
+ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
+ if (list) { \
+ _ls_insize = 1; \
+ _ls_looping = 1; \
+ while (_ls_looping) { \
+ UTLIST_CASTASGN(_ls_p,list); \
+ (list) = NULL; \
+ _ls_tail = NULL; \
+ _ls_nmerges = 0; \
+ while (_ls_p) { \
+ _ls_nmerges++; \
+ _ls_q = _ls_p; \
+ _ls_psize = 0; \
+ for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
+ _ls_psize++; \
+ UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \
+ if (!_ls_q) break; \
+ } \
+ _ls_qsize = _ls_insize; \
+ while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \
+ if (_ls_psize == 0) { \
+ _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
+ UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
+ } else if ((_ls_qsize == 0) || (!_ls_q)) { \
+ _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
+ UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
+ } else if (cmp(_ls_p,_ls_q) <= 0) { \
+ _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
+ UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
+ } else { \
+ _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
+ UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
+ } \
+ if (_ls_tail) { \
+ UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
+ } else { \
+ UTLIST_CASTASGN(list,_ls_e); \
+ } \
+ UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \
+ _ls_tail = _ls_e; \
+ } \
+ _ls_p = _ls_q; \
+ } \
+ UTLIST_CASTASGN((list)->prev, _ls_tail); \
+ UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \
+ if (_ls_nmerges <= 1) { \
+ _ls_looping=0; \
+ } \
+ _ls_insize *= 2; \
+ } \
+ } \
+} while (0)
+
+#define CDL_SORT(list, cmp) \
+ CDL_SORT2(list, cmp, prev, next)
+
+#define CDL_SORT2(list, cmp, prev, next) \
+do { \
+ LDECLTYPE(list) _ls_p; \
+ LDECLTYPE(list) _ls_q; \
+ LDECLTYPE(list) _ls_e; \
+ LDECLTYPE(list) _ls_tail; \
+ LDECLTYPE(list) _ls_oldhead; \
+ LDECLTYPE(list) _tmp; \
+ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
+ if (list) { \
+ _ls_insize = 1; \
+ _ls_looping = 1; \
+ while (_ls_looping) { \
+ UTLIST_CASTASGN(_ls_p,list); \
+ UTLIST_CASTASGN(_ls_oldhead,list); \
+ (list) = NULL; \
+ _ls_tail = NULL; \
+ _ls_nmerges = 0; \
+ while (_ls_p) { \
+ _ls_nmerges++; \
+ _ls_q = _ls_p; \
+ _ls_psize = 0; \
+ for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
+ _ls_psize++; \
+ UTLIST_SV(_ls_q,list); \
+ if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) { \
+ _ls_q = NULL; \
+ } else { \
+ _ls_q = UTLIST_NEXT(_ls_q,list,next); \
+ } \
+ UTLIST_RS(list); \
+ if (!_ls_q) break; \
+ } \
+ _ls_qsize = _ls_insize; \
+ while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
+ if (_ls_psize == 0) { \
+ _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
+ UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
+ if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
+ } else if (_ls_qsize == 0 || !_ls_q) { \
+ _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
+ UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
+ if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
+ } else if (cmp(_ls_p,_ls_q) <= 0) { \
+ _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
+ UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
+ if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
+ } else { \
+ _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
+ UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
+ if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
+ } \
+ if (_ls_tail) { \
+ UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
+ } else { \
+ UTLIST_CASTASGN(list,_ls_e); \
+ } \
+ UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \
+ _ls_tail = _ls_e; \
+ } \
+ _ls_p = _ls_q; \
+ } \
+ UTLIST_CASTASGN((list)->prev,_ls_tail); \
+ UTLIST_CASTASGN(_tmp,list); \
+ UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list); \
+ if (_ls_nmerges <= 1) { \
+ _ls_looping=0; \
+ } \
+ _ls_insize *= 2; \
+ } \
+ } \
+} while (0)
+
+/******************************************************************************
+ * singly linked list macros (non-circular) *
+ *****************************************************************************/
+#define LL_PREPEND(head,add) \
+ LL_PREPEND2(head,add,next)
+
+#define LL_PREPEND2(head,add,next) \
+do { \
+ (add)->next = (head); \
+ (head) = (add); \
+} while (0)
+
+#define LL_CONCAT(head1,head2) \
+ LL_CONCAT2(head1,head2,next)
+
+#define LL_CONCAT2(head1,head2,next) \
+do { \
+ LDECLTYPE(head1) _tmp; \
+ if (head1) { \
+ _tmp = (head1); \
+ while (_tmp->next) { _tmp = _tmp->next; } \
+ _tmp->next=(head2); \
+ } else { \
+ (head1)=(head2); \
+ } \
+} while (0)
+
+#define LL_APPEND(head,add) \
+ LL_APPEND2(head,add,next)
+
+#define LL_APPEND2(head,add,next) \
+do { \
+ LDECLTYPE(head) _tmp; \
+ (add)->next=NULL; \
+ if (head) { \
+ _tmp = (head); \
+ while (_tmp->next) { _tmp = _tmp->next; } \
+ _tmp->next=(add); \
+ } else { \
+ (head)=(add); \
+ } \
+} while (0)
+
+#define LL_INSERT_INORDER(head,add,cmp) \
+ LL_INSERT_INORDER2(head,add,cmp,next)
+
+#define LL_INSERT_INORDER2(head,add,cmp,next) \
+do { \
+ LDECLTYPE(head) _tmp; \
+ if (head) { \
+ LL_LOWER_BOUND2(head, _tmp, add, cmp, next); \
+ LL_APPEND_ELEM2(head, _tmp, add, next); \
+ } else { \
+ (head) = (add); \
+ (head)->next = NULL; \
+ } \
+} while (0)
+
+#define LL_LOWER_BOUND(head,elt,like,cmp) \
+ LL_LOWER_BOUND2(head,elt,like,cmp,next)
+
+#define LL_LOWER_BOUND2(head,elt,like,cmp,next) \
+ do { \
+ if ((head) == NULL || (cmp(head, like)) >= 0) { \
+ (elt) = NULL; \
+ } else { \
+ for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \
+ if (cmp((elt)->next, like) >= 0) { \
+ break; \
+ } \
+ } \
+ } \
+ } while (0)
+
+#define LL_DELETE(head,del) \
+ LL_DELETE2(head,del,next)
+
+#define LL_DELETE2(head,del,next) \
+do { \
+ LDECLTYPE(head) _tmp; \
+ if ((head) == (del)) { \
+ (head)=(head)->next; \
+ } else { \
+ _tmp = (head); \
+ while (_tmp->next && (_tmp->next != (del))) { \
+ _tmp = _tmp->next; \
+ } \
+ if (_tmp->next) { \
+ _tmp->next = (del)->next; \
+ } \
+ } \
+} while (0)
+
+#define LL_COUNT(head,el,counter) \
+ LL_COUNT2(head,el,counter,next) \
+
+#define LL_COUNT2(head,el,counter,next) \
+do { \
+ (counter) = 0; \
+ LL_FOREACH2(head,el,next) { ++(counter); } \
+} while (0)
+
+#define LL_FOREACH(head,el) \
+ LL_FOREACH2(head,el,next)
+
+#define LL_FOREACH2(head,el,next) \
+ for ((el) = (head); el; (el) = (el)->next)
+
+#define LL_FOREACH_SAFE(head,el,tmp) \
+ LL_FOREACH_SAFE2(head,el,tmp,next)
+
+#define LL_FOREACH_SAFE2(head,el,tmp,next) \
+ for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
+
+#define LL_SEARCH_SCALAR(head,out,field,val) \
+ LL_SEARCH_SCALAR2(head,out,field,val,next)
+
+#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
+do { \
+ LL_FOREACH2(head,out,next) { \
+ if ((out)->field == (val)) break; \
+ } \
+} while (0)
+
+#define LL_SEARCH(head,out,elt,cmp) \
+ LL_SEARCH2(head,out,elt,cmp,next)
+
+#define LL_SEARCH2(head,out,elt,cmp,next) \
+do { \
+ LL_FOREACH2(head,out,next) { \
+ if ((cmp(out,elt))==0) break; \
+ } \
+} while (0)
+
+#define LL_REPLACE_ELEM2(head, el, add, next) \
+do { \
+ LDECLTYPE(head) _tmp; \
+ assert((head) != NULL); \
+ assert((el) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el)->next; \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } else { \
+ _tmp = (head); \
+ while (_tmp->next && (_tmp->next != (el))) { \
+ _tmp = _tmp->next; \
+ } \
+ if (_tmp->next) { \
+ _tmp->next = (add); \
+ } \
+ } \
+} while (0)
+
+#define LL_REPLACE_ELEM(head, el, add) \
+ LL_REPLACE_ELEM2(head, el, add, next)
+
+#define LL_PREPEND_ELEM2(head, el, add, next) \
+do { \
+ if (el) { \
+ LDECLTYPE(head) _tmp; \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } else { \
+ _tmp = (head); \
+ while (_tmp->next && (_tmp->next != (el))) { \
+ _tmp = _tmp->next; \
+ } \
+ if (_tmp->next) { \
+ _tmp->next = (add); \
+ } \
+ } \
+ } else { \
+ LL_APPEND2(head, add, next); \
+ } \
+} while (0) \
+
+#define LL_PREPEND_ELEM(head, el, add) \
+ LL_PREPEND_ELEM2(head, el, add, next)
+
+#define LL_APPEND_ELEM2(head, el, add, next) \
+do { \
+ if (el) { \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el)->next; \
+ (el)->next = (add); \
+ } else { \
+ LL_PREPEND2(head, add, next); \
+ } \
+} while (0) \
+
+#define LL_APPEND_ELEM(head, el, add) \
+ LL_APPEND_ELEM2(head, el, add, next)
+
+#ifdef NO_DECLTYPE
+/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
+
+#undef LL_CONCAT2
+#define LL_CONCAT2(head1,head2,next) \
+do { \
+ char *_tmp; \
+ if (head1) { \
+ _tmp = (char*)(head1); \
+ while ((head1)->next) { (head1) = (head1)->next; } \
+ (head1)->next = (head2); \
+ UTLIST_RS(head1); \
+ } else { \
+ (head1)=(head2); \
+ } \
+} while (0)
+
+#undef LL_APPEND2
+#define LL_APPEND2(head,add,next) \
+do { \
+ if (head) { \
+ (add)->next = head; /* use add->next as a temp variable */ \
+ while ((add)->next->next) { (add)->next = (add)->next->next; } \
+ (add)->next->next=(add); \
+ } else { \
+ (head)=(add); \
+ } \
+ (add)->next=NULL; \
+} while (0)
+
+#undef LL_INSERT_INORDER2
+#define LL_INSERT_INORDER2(head,add,cmp,next) \
+do { \
+ if ((head) == NULL || (cmp(head, add)) >= 0) { \
+ (add)->next = (head); \
+ (head) = (add); \
+ } else { \
+ char *_tmp = (char*)(head); \
+ while ((head)->next != NULL && (cmp((head)->next, add)) < 0) { \
+ (head) = (head)->next; \
+ } \
+ (add)->next = (head)->next; \
+ (head)->next = (add); \
+ UTLIST_RS(head); \
+ } \
+} while (0)
+
+#undef LL_DELETE2
+#define LL_DELETE2(head,del,next) \
+do { \
+ if ((head) == (del)) { \
+ (head)=(head)->next; \
+ } else { \
+ char *_tmp = (char*)(head); \
+ while ((head)->next && ((head)->next != (del))) { \
+ (head) = (head)->next; \
+ } \
+ if ((head)->next) { \
+ (head)->next = ((del)->next); \
+ } \
+ UTLIST_RS(head); \
+ } \
+} while (0)
+
+#undef LL_REPLACE_ELEM2
+#define LL_REPLACE_ELEM2(head, el, add, next) \
+do { \
+ assert((head) != NULL); \
+ assert((el) != NULL); \
+ assert((add) != NULL); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } else { \
+ (add)->next = head; \
+ while ((add)->next->next && ((add)->next->next != (el))) { \
+ (add)->next = (add)->next->next; \
+ } \
+ if ((add)->next->next) { \
+ (add)->next->next = (add); \
+ } \
+ } \
+ (add)->next = (el)->next; \
+} while (0)
+
+#undef LL_PREPEND_ELEM2
+#define LL_PREPEND_ELEM2(head, el, add, next) \
+do { \
+ if (el) { \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } else { \
+ (add)->next = (head); \
+ while ((add)->next->next && ((add)->next->next != (el))) { \
+ (add)->next = (add)->next->next; \
+ } \
+ if ((add)->next->next) { \
+ (add)->next->next = (add); \
+ } \
+ } \
+ (add)->next = (el); \
+ } else { \
+ LL_APPEND2(head, add, next); \
+ } \
+} while (0) \
+
+#endif /* NO_DECLTYPE */
+
+/******************************************************************************
+ * doubly linked list macros (non-circular) *
+ *****************************************************************************/
+#define DL_PREPEND(head,add) \
+ DL_PREPEND2(head,add,prev,next)
+
+#define DL_PREPEND2(head,add,prev,next) \
+do { \
+ (add)->next = (head); \
+ if (head) { \
+ (add)->prev = (head)->prev; \
+ (head)->prev = (add); \
+ } else { \
+ (add)->prev = (add); \
+ } \
+ (head) = (add); \
+} while (0)
+
+#define DL_APPEND(head,add) \
+ DL_APPEND2(head,add,prev,next)
+
+#define DL_APPEND2(head,add,prev,next) \
+do { \
+ if (head) { \
+ (add)->prev = (head)->prev; \
+ (head)->prev->next = (add); \
+ (head)->prev = (add); \
+ (add)->next = NULL; \
+ } else { \
+ (head)=(add); \
+ (head)->prev = (head); \
+ (head)->next = NULL; \
+ } \
+} while (0)
+
+#define DL_INSERT_INORDER(head,add,cmp) \
+ DL_INSERT_INORDER2(head,add,cmp,prev,next)
+
+#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \
+do { \
+ LDECLTYPE(head) _tmp; \
+ if (head) { \
+ DL_LOWER_BOUND2(head, _tmp, add, cmp, next); \
+ DL_APPEND_ELEM2(head, _tmp, add, prev, next); \
+ } else { \
+ (head) = (add); \
+ (head)->prev = (head); \
+ (head)->next = NULL; \
+ } \
+} while (0)
+
+#define DL_LOWER_BOUND(head,elt,like,cmp) \
+ DL_LOWER_BOUND2(head,elt,like,cmp,next)
+
+#define DL_LOWER_BOUND2(head,elt,like,cmp,next) \
+do { \
+ if ((head) == NULL || (cmp(head, like)) >= 0) { \
+ (elt) = NULL; \
+ } else { \
+ for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \
+ if ((cmp((elt)->next, like)) >= 0) { \
+ break; \
+ } \
+ } \
+ } \
+} while (0)
+
+#define DL_CONCAT(head1,head2) \
+ DL_CONCAT2(head1,head2,prev,next)
+
+#define DL_CONCAT2(head1,head2,prev,next) \
+do { \
+ LDECLTYPE(head1) _tmp; \
+ if (head2) { \
+ if (head1) { \
+ UTLIST_CASTASGN(_tmp, (head2)->prev); \
+ (head2)->prev = (head1)->prev; \
+ (head1)->prev->next = (head2); \
+ UTLIST_CASTASGN((head1)->prev, _tmp); \
+ } else { \
+ (head1)=(head2); \
+ } \
+ } \
+} while (0)
+
+#define DL_DELETE(head,del) \
+ DL_DELETE2(head,del,prev,next)
+
+#define DL_DELETE2(head,del,prev,next) \
+do { \
+ assert((head) != NULL); \
+ assert((del)->prev != NULL); \
+ if ((del)->prev == (del)) { \
+ (head)=NULL; \
+ } else if ((del)==(head)) { \
+ (del)->next->prev = (del)->prev; \
+ (head) = (del)->next; \
+ } else { \
+ (del)->prev->next = (del)->next; \
+ if ((del)->next) { \
+ (del)->next->prev = (del)->prev; \
+ } else { \
+ (head)->prev = (del)->prev; \
+ } \
+ } \
+} while (0)
+
+#define DL_COUNT(head,el,counter) \
+ DL_COUNT2(head,el,counter,next) \
+
+#define DL_COUNT2(head,el,counter,next) \
+do { \
+ (counter) = 0; \
+ DL_FOREACH2(head,el,next) { ++(counter); } \
+} while (0)
+
+#define DL_FOREACH(head,el) \
+ DL_FOREACH2(head,el,next)
+
+#define DL_FOREACH2(head,el,next) \
+ for ((el) = (head); el; (el) = (el)->next)
+
+/* this version is safe for deleting the elements during iteration */
+#define DL_FOREACH_SAFE(head,el,tmp) \
+ DL_FOREACH_SAFE2(head,el,tmp,next)
+
+#define DL_FOREACH_SAFE2(head,el,tmp,next) \
+ for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
+
+/* these are identical to their singly-linked list counterparts */
+#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
+#define DL_SEARCH LL_SEARCH
+#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
+#define DL_SEARCH2 LL_SEARCH2
+
+#define DL_REPLACE_ELEM2(head, el, add, prev, next) \
+do { \
+ assert((head) != NULL); \
+ assert((el) != NULL); \
+ assert((add) != NULL); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ (add)->next = (el)->next; \
+ if ((el)->next == NULL) { \
+ (add)->prev = (add); \
+ } else { \
+ (add)->prev = (el)->prev; \
+ (add)->next->prev = (add); \
+ } \
+ } else { \
+ (add)->next = (el)->next; \
+ (add)->prev = (el)->prev; \
+ (add)->prev->next = (add); \
+ if ((el)->next == NULL) { \
+ (head)->prev = (add); \
+ } else { \
+ (add)->next->prev = (add); \
+ } \
+ } \
+} while (0)
+
+#define DL_REPLACE_ELEM(head, el, add) \
+ DL_REPLACE_ELEM2(head, el, add, prev, next)
+
+#define DL_PREPEND_ELEM2(head, el, add, prev, next) \
+do { \
+ if (el) { \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el); \
+ (add)->prev = (el)->prev; \
+ (el)->prev = (add); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } else { \
+ (add)->prev->next = (add); \
+ } \
+ } else { \
+ DL_APPEND2(head, add, prev, next); \
+ } \
+} while (0) \
+
+#define DL_PREPEND_ELEM(head, el, add) \
+ DL_PREPEND_ELEM2(head, el, add, prev, next)
+
+#define DL_APPEND_ELEM2(head, el, add, prev, next) \
+do { \
+ if (el) { \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el)->next; \
+ (add)->prev = (el); \
+ (el)->next = (add); \
+ if ((add)->next) { \
+ (add)->next->prev = (add); \
+ } else { \
+ (head)->prev = (add); \
+ } \
+ } else { \
+ DL_PREPEND2(head, add, prev, next); \
+ } \
+} while (0) \
+
+#define DL_APPEND_ELEM(head, el, add) \
+ DL_APPEND_ELEM2(head, el, add, prev, next)
+
+#ifdef NO_DECLTYPE
+/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
+
+#undef DL_INSERT_INORDER2
+#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \
+do { \
+ if ((head) == NULL) { \
+ (add)->prev = (add); \
+ (add)->next = NULL; \
+ (head) = (add); \
+ } else if ((cmp(head, add)) >= 0) { \
+ (add)->prev = (head)->prev; \
+ (add)->next = (head); \
+ (head)->prev = (add); \
+ (head) = (add); \
+ } else { \
+ char *_tmp = (char*)(head); \
+ while ((head)->next && (cmp((head)->next, add)) < 0) { \
+ (head) = (head)->next; \
+ } \
+ (add)->prev = (head); \
+ (add)->next = (head)->next; \
+ (head)->next = (add); \
+ UTLIST_RS(head); \
+ if ((add)->next) { \
+ (add)->next->prev = (add); \
+ } else { \
+ (head)->prev = (add); \
+ } \
+ } \
+} while (0)
+#endif /* NO_DECLTYPE */
+
+/******************************************************************************
+ * circular doubly linked list macros *
+ *****************************************************************************/
+#define CDL_APPEND(head,add) \
+ CDL_APPEND2(head,add,prev,next)
+
+#define CDL_APPEND2(head,add,prev,next) \
+do { \
+ if (head) { \
+ (add)->prev = (head)->prev; \
+ (add)->next = (head); \
+ (head)->prev = (add); \
+ (add)->prev->next = (add); \
+ } else { \
+ (add)->prev = (add); \
+ (add)->next = (add); \
+ (head) = (add); \
+ } \
+} while (0)
+
+#define CDL_PREPEND(head,add) \
+ CDL_PREPEND2(head,add,prev,next)
+
+#define CDL_PREPEND2(head,add,prev,next) \
+do { \
+ if (head) { \
+ (add)->prev = (head)->prev; \
+ (add)->next = (head); \
+ (head)->prev = (add); \
+ (add)->prev->next = (add); \
+ } else { \
+ (add)->prev = (add); \
+ (add)->next = (add); \
+ } \
+ (head) = (add); \
+} while (0)
+
+#define CDL_INSERT_INORDER(head,add,cmp) \
+ CDL_INSERT_INORDER2(head,add,cmp,prev,next)
+
+#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \
+do { \
+ LDECLTYPE(head) _tmp; \
+ if (head) { \
+ CDL_LOWER_BOUND2(head, _tmp, add, cmp, next); \
+ CDL_APPEND_ELEM2(head, _tmp, add, prev, next); \
+ } else { \
+ (head) = (add); \
+ (head)->next = (head); \
+ (head)->prev = (head); \
+ } \
+} while (0)
+
+#define CDL_LOWER_BOUND(head,elt,like,cmp) \
+ CDL_LOWER_BOUND2(head,elt,like,cmp,next)
+
+#define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \
+do { \
+ if ((head) == NULL || (cmp(head, like)) >= 0) { \
+ (elt) = NULL; \
+ } else { \
+ for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \
+ if ((cmp((elt)->next, like)) >= 0) { \
+ break; \
+ } \
+ } \
+ } \
+} while (0)
+
+#define CDL_DELETE(head,del) \
+ CDL_DELETE2(head,del,prev,next)
+
+#define CDL_DELETE2(head,del,prev,next) \
+do { \
+ if (((head)==(del)) && ((head)->next == (head))) { \
+ (head) = NULL; \
+ } else { \
+ (del)->next->prev = (del)->prev; \
+ (del)->prev->next = (del)->next; \
+ if ((del) == (head)) (head)=(del)->next; \
+ } \
+} while (0)
+
+#define CDL_COUNT(head,el,counter) \
+ CDL_COUNT2(head,el,counter,next) \
+
+#define CDL_COUNT2(head, el, counter,next) \
+do { \
+ (counter) = 0; \
+ CDL_FOREACH2(head,el,next) { ++(counter); } \
+} while (0)
+
+#define CDL_FOREACH(head,el) \
+ CDL_FOREACH2(head,el,next)
+
+#define CDL_FOREACH2(head,el,next) \
+ for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next))
+
+#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
+ CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
+
+#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
+ for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \
+ (el) && ((tmp2) = (el)->next, 1); \
+ (el) = ((el) == (tmp1) ? NULL : (tmp2)))
+
+#define CDL_SEARCH_SCALAR(head,out,field,val) \
+ CDL_SEARCH_SCALAR2(head,out,field,val,next)
+
+#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
+do { \
+ CDL_FOREACH2(head,out,next) { \
+ if ((out)->field == (val)) break; \
+ } \
+} while (0)
+
+#define CDL_SEARCH(head,out,elt,cmp) \
+ CDL_SEARCH2(head,out,elt,cmp,next)
+
+#define CDL_SEARCH2(head,out,elt,cmp,next) \
+do { \
+ CDL_FOREACH2(head,out,next) { \
+ if ((cmp(out,elt))==0) break; \
+ } \
+} while (0)
+
+#define CDL_REPLACE_ELEM2(head, el, add, prev, next) \
+do { \
+ assert((head) != NULL); \
+ assert((el) != NULL); \
+ assert((add) != NULL); \
+ if ((el)->next == (el)) { \
+ (add)->next = (add); \
+ (add)->prev = (add); \
+ (head) = (add); \
+ } else { \
+ (add)->next = (el)->next; \
+ (add)->prev = (el)->prev; \
+ (add)->next->prev = (add); \
+ (add)->prev->next = (add); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } \
+ } \
+} while (0)
+
+#define CDL_REPLACE_ELEM(head, el, add) \
+ CDL_REPLACE_ELEM2(head, el, add, prev, next)
+
+#define CDL_PREPEND_ELEM2(head, el, add, prev, next) \
+do { \
+ if (el) { \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el); \
+ (add)->prev = (el)->prev; \
+ (el)->prev = (add); \
+ (add)->prev->next = (add); \
+ if ((head) == (el)) { \
+ (head) = (add); \
+ } \
+ } else { \
+ CDL_APPEND2(head, add, prev, next); \
+ } \
+} while (0)
+
+#define CDL_PREPEND_ELEM(head, el, add) \
+ CDL_PREPEND_ELEM2(head, el, add, prev, next)
+
+#define CDL_APPEND_ELEM2(head, el, add, prev, next) \
+do { \
+ if (el) { \
+ assert((head) != NULL); \
+ assert((add) != NULL); \
+ (add)->next = (el)->next; \
+ (add)->prev = (el); \
+ (el)->next = (add); \
+ (add)->next->prev = (add); \
+ } else { \
+ CDL_PREPEND2(head, add, prev, next); \
+ } \
+} while (0)
+
+#define CDL_APPEND_ELEM(head, el, add) \
+ CDL_APPEND_ELEM2(head, el, add, prev, next)
+
+#ifdef NO_DECLTYPE
+/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
+
+#undef CDL_INSERT_INORDER2
+#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \
+do { \
+ if ((head) == NULL) { \
+ (add)->prev = (add); \
+ (add)->next = (add); \
+ (head) = (add); \
+ } else if ((cmp(head, add)) >= 0) { \
+ (add)->prev = (head)->prev; \
+ (add)->next = (head); \
+ (add)->prev->next = (add); \
+ (head)->prev = (add); \
+ (head) = (add); \
+ } else { \
+ char *_tmp = (char*)(head); \
+ while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \
+ (head) = (head)->next; \
+ } \
+ (add)->prev = (head); \
+ (add)->next = (head)->next; \
+ (add)->next->prev = (add); \
+ (head)->next = (add); \
+ UTLIST_RS(head); \
+ } \
+} while (0)
+#endif /* NO_DECLTYPE */
+
+#endif /* UTLIST_H */
diff --git a/head/uthash/utringbuffer.h b/head/uthash/utringbuffer.h
@@ -0,0 +1,108 @@
+/*
+Copyright (c) 2015-2022, Troy D. Hanson https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a ring-buffer implementation using macros
+ */
+#ifndef UTRINGBUFFER_H
+#define UTRINGBUFFER_H
+
+#define UTRINGBUFFER_VERSION 2.3.0
+
+#include <stdlib.h>
+#include <string.h>
+#include "utarray.h" // for "UT_icd"
+
+typedef struct {
+ unsigned i; /* index of next available slot; wraps at n */
+ unsigned n; /* capacity */
+ unsigned char f; /* full */
+ UT_icd icd; /* initializer, copy and destructor functions */
+ char *d; /* n slots of size icd->sz */
+} UT_ringbuffer;
+
+#define utringbuffer_init(a, _n, _icd) do { \
+ memset(a, 0, sizeof(UT_ringbuffer)); \
+ (a)->icd = *(_icd); \
+ (a)->n = (_n); \
+ if ((a)->n) { (a)->d = (char*)malloc((a)->n * (_icd)->sz); } \
+} while(0)
+
+#define utringbuffer_clear(a) do { \
+ if ((a)->icd.dtor) { \
+ if ((a)->f) { \
+ unsigned _ut_i; \
+ for (_ut_i = 0; _ut_i < (a)->n; ++_ut_i) { \
+ (a)->icd.dtor(utringbuffer_eltptr(a, _ut_i)); \
+ } \
+ } else { \
+ unsigned _ut_i; \
+ for (_ut_i = 0; _ut_i < (a)->i; ++_ut_i) { \
+ (a)->icd.dtor(utringbuffer_eltptr(a, _ut_i)); \
+ } \
+ } \
+ } \
+ (a)->i = 0; \
+ (a)->f = 0; \
+} while(0)
+
+#define utringbuffer_done(a) do { \
+ utringbuffer_clear(a); \
+ free((a)->d); (a)->d = NULL; \
+ (a)->n = 0; \
+} while(0)
+
+#define utringbuffer_new(a,n,_icd) do { \
+ a = (UT_ringbuffer*)malloc(sizeof(UT_ringbuffer)); \
+ utringbuffer_init(a, n, _icd); \
+} while(0)
+
+#define utringbuffer_free(a) do { \
+ utringbuffer_done(a); \
+ free(a); \
+} while(0)
+
+#define utringbuffer_push_back(a,p) do { \
+ if ((a)->icd.dtor && (a)->f) { (a)->icd.dtor(_utringbuffer_internalptr(a,(a)->i)); } \
+ if ((a)->icd.copy) { (a)->icd.copy( _utringbuffer_internalptr(a,(a)->i), p); } \
+ else { memcpy(_utringbuffer_internalptr(a,(a)->i), p, (a)->icd.sz); }; \
+ if (++(a)->i == (a)->n) { (a)->i = 0; (a)->f = 1; } \
+} while(0)
+
+#define utringbuffer_len(a) ((a)->f ? (a)->n : (a)->i)
+#define utringbuffer_empty(a) ((a)->i == 0 && !(a)->f)
+#define utringbuffer_full(a) ((a)->f != 0)
+
+#define _utringbuffer_real_idx(a,j) ((a)->f ? ((j) + (a)->i) % (a)->n : (j))
+#define _utringbuffer_internalptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j))))
+#define utringbuffer_eltptr(a,j) ((0 <= (j) && (j) < utringbuffer_len(a)) ? _utringbuffer_internalptr(a,_utringbuffer_real_idx(a,j)) : NULL)
+
+#define _utringbuffer_fake_idx(a,j) ((a)->f ? ((j) + (a)->n - (a)->i) % (a)->n : (j))
+#define _utringbuffer_internalidx(a,e) (((char*)(e) >= (a)->d) ? (((char*)(e) - (a)->d)/(a)->icd.sz) : -1)
+#define utringbuffer_eltidx(a,e) _utringbuffer_fake_idx(a, _utringbuffer_internalidx(a,e))
+
+#define utringbuffer_front(a) utringbuffer_eltptr(a,0)
+#define utringbuffer_next(a,e) ((e)==NULL ? utringbuffer_front(a) : utringbuffer_eltptr(a, utringbuffer_eltidx(a,e)+1))
+#define utringbuffer_prev(a,e) ((e)==NULL ? utringbuffer_back(a) : utringbuffer_eltptr(a, utringbuffer_eltidx(a,e)-1))
+#define utringbuffer_back(a) (utringbuffer_empty(a) ? NULL : utringbuffer_eltptr(a, utringbuffer_len(a) - 1))
+
+#endif /* UTRINGBUFFER_H */
diff --git a/head/uthash/utstack.h b/head/uthash/utstack.h
@@ -0,0 +1,88 @@
+/*
+Copyright (c) 2018-2022, Troy D. Hanson https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef UTSTACK_H
+#define UTSTACK_H
+
+#define UTSTACK_VERSION 2.3.0
+
+/*
+ * This file contains macros to manipulate a singly-linked list as a stack.
+ *
+ * To use utstack, your structure must have a "next" pointer.
+ *
+ * ----------------.EXAMPLE -------------------------
+ * struct item {
+ * int id;
+ * struct item *next;
+ * };
+ *
+ * struct item *stack = NULL;
+ *
+ * int main() {
+ * int count;
+ * struct item *tmp;
+ * struct item *item = malloc(sizeof *item);
+ * item->id = 42;
+ * STACK_COUNT(stack, tmp, count); assert(count == 0);
+ * STACK_PUSH(stack, item);
+ * STACK_COUNT(stack, tmp, count); assert(count == 1);
+ * STACK_POP(stack, item);
+ * free(item);
+ * STACK_COUNT(stack, tmp, count); assert(count == 0);
+ * }
+ * --------------------------------------------------
+ */
+
+#define STACK_TOP(head) (head)
+
+#define STACK_EMPTY(head) (!(head))
+
+#define STACK_PUSH(head,add) \
+ STACK_PUSH2(head,add,next)
+
+#define STACK_PUSH2(head,add,next) \
+do { \
+ (add)->next = (head); \
+ (head) = (add); \
+} while (0)
+
+#define STACK_POP(head,result) \
+ STACK_POP2(head,result,next)
+
+#define STACK_POP2(head,result,next) \
+do { \
+ (result) = (head); \
+ (head) = (head)->next; \
+} while (0)
+
+#define STACK_COUNT(head,el,counter) \
+ STACK_COUNT2(head,el,counter,next) \
+
+#define STACK_COUNT2(head,el,counter,next) \
+do { \
+ (counter) = 0; \
+ for ((el) = (head); el; (el) = (el)->next) { ++(counter); } \
+} while (0)
+
+#endif /* UTSTACK_H */
diff --git a/head/uthash/utstring.h b/head/uthash/utstring.h
@@ -0,0 +1,407 @@
+/*
+Copyright (c) 2008-2022, Troy D. Hanson https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a dynamic string implementation using macros
+ */
+#ifndef UTSTRING_H
+#define UTSTRING_H
+
+#define UTSTRING_VERSION 2.3.0
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdarg.h>
+
+#ifdef __GNUC__
+#define UTSTRING_UNUSED __attribute__((__unused__))
+#else
+#define UTSTRING_UNUSED
+#endif
+
+#ifdef oom
+#error "The name of macro 'oom' has been changed to 'utstring_oom'. Please update your code."
+#define utstring_oom() oom()
+#endif
+
+#ifndef utstring_oom
+#define utstring_oom() exit(-1)
+#endif
+
+typedef struct {
+ char *d; /* pointer to allocated buffer */
+ size_t n; /* allocated capacity */
+ size_t i; /* index of first unused byte */
+} UT_string;
+
+#define utstring_reserve(s,amt) \
+do { \
+ if (((s)->n - (s)->i) < (size_t)(amt)) { \
+ char *utstring_tmp = (char*)realloc( \
+ (s)->d, (s)->n + (amt)); \
+ if (!utstring_tmp) { \
+ utstring_oom(); \
+ } \
+ (s)->d = utstring_tmp; \
+ (s)->n += (amt); \
+ } \
+} while(0)
+
+#define utstring_init(s) \
+do { \
+ (s)->n = 0; (s)->i = 0; (s)->d = NULL; \
+ utstring_reserve(s,100); \
+ (s)->d[0] = '\0'; \
+} while(0)
+
+#define utstring_done(s) \
+do { \
+ if ((s)->d != NULL) free((s)->d); \
+ (s)->n = 0; \
+} while(0)
+
+#define utstring_free(s) \
+do { \
+ utstring_done(s); \
+ free(s); \
+} while(0)
+
+#define utstring_new(s) \
+do { \
+ (s) = (UT_string*)malloc(sizeof(UT_string)); \
+ if (!(s)) { \
+ utstring_oom(); \
+ } \
+ utstring_init(s); \
+} while(0)
+
+#define utstring_renew(s) \
+do { \
+ if (s) { \
+ utstring_clear(s); \
+ } else { \
+ utstring_new(s); \
+ } \
+} while(0)
+
+#define utstring_clear(s) \
+do { \
+ (s)->i = 0; \
+ (s)->d[0] = '\0'; \
+} while(0)
+
+#define utstring_bincpy(s,b,l) \
+do { \
+ utstring_reserve((s),(l)+1); \
+ if (l) memcpy(&(s)->d[(s)->i], b, l); \
+ (s)->i += (l); \
+ (s)->d[(s)->i]='\0'; \
+} while(0)
+
+#define utstring_concat(dst,src) \
+do { \
+ utstring_reserve((dst),((src)->i)+1); \
+ if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \
+ (dst)->i += (src)->i; \
+ (dst)->d[(dst)->i]='\0'; \
+} while(0)
+
+#define utstring_len(s) ((s)->i)
+
+#define utstring_body(s) ((s)->d)
+
+UTSTRING_UNUSED static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
+ int n;
+ va_list cp;
+ for (;;) {
+#ifdef _WIN32
+ cp = ap;
+#else
+ va_copy(cp, ap);
+#endif
+ n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
+ va_end(cp);
+
+ if ((n > -1) && ((size_t) n < (s->n-s->i))) {
+ s->i += n;
+ return;
+ }
+
+ /* Else try again with more space. */
+ if (n > -1) utstring_reserve(s,n+1); /* exact */
+ else utstring_reserve(s,(s->n)*2); /* 2x */
+ }
+}
+#ifdef __GNUC__
+/* support printf format checking (2=the format string, 3=start of varargs) */
+static void utstring_printf(UT_string *s, const char *fmt, ...)
+ __attribute__ (( format( printf, 2, 3) ));
+#endif
+UTSTRING_UNUSED static void utstring_printf(UT_string *s, const char *fmt, ...) {
+ va_list ap;
+ va_start(ap,fmt);
+ utstring_printf_va(s,fmt,ap);
+ va_end(ap);
+}
+
+/*******************************************************************************
+ * begin substring search functions *
+ ******************************************************************************/
+/* Build KMP table from left to right. */
+UTSTRING_UNUSED static void _utstring_BuildTable(
+ const char *P_Needle,
+ size_t P_NeedleLen,
+ long *P_KMP_Table)
+{
+ long i, j;
+
+ i = 0;
+ j = i - 1;
+ P_KMP_Table[i] = j;
+ while (i < (long) P_NeedleLen)
+ {
+ while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )
+ {
+ j = P_KMP_Table[j];
+ }
+ i++;
+ j++;
+ if (i < (long) P_NeedleLen)
+ {
+ if (P_Needle[i] == P_Needle[j])
+ {
+ P_KMP_Table[i] = P_KMP_Table[j];
+ }
+ else
+ {
+ P_KMP_Table[i] = j;
+ }
+ }
+ else
+ {
+ P_KMP_Table[i] = j;
+ }
+ }
+
+ return;
+}
+
+
+/* Build KMP table from right to left. */
+UTSTRING_UNUSED static void _utstring_BuildTableR(
+ const char *P_Needle,
+ size_t P_NeedleLen,
+ long *P_KMP_Table)
+{
+ long i, j;
+
+ i = P_NeedleLen - 1;
+ j = i + 1;
+ P_KMP_Table[i + 1] = j;
+ while (i >= 0)
+ {
+ while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )
+ {
+ j = P_KMP_Table[j + 1];
+ }
+ i--;
+ j--;
+ if (i >= 0)
+ {
+ if (P_Needle[i] == P_Needle[j])
+ {
+ P_KMP_Table[i + 1] = P_KMP_Table[j + 1];
+ }
+ else
+ {
+ P_KMP_Table[i + 1] = j;
+ }
+ }
+ else
+ {
+ P_KMP_Table[i + 1] = j;
+ }
+ }
+
+ return;
+}
+
+
+/* Search data from left to right. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_find(
+ const char *P_Haystack,
+ size_t P_HaystackLen,
+ const char *P_Needle,
+ size_t P_NeedleLen,
+ long *P_KMP_Table)
+{
+ long i, j;
+ long V_FindPosition = -1;
+
+ /* Search from left to right. */
+ i = j = 0;
+ while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )
+ {
+ while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )
+ {
+ i = P_KMP_Table[i];
+ }
+ i++;
+ j++;
+ if (i >= (int)P_NeedleLen)
+ {
+ /* Found. */
+ V_FindPosition = j - i;
+ break;
+ }
+ }
+
+ return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_findR(
+ const char *P_Haystack,
+ size_t P_HaystackLen,
+ const char *P_Needle,
+ size_t P_NeedleLen,
+ long *P_KMP_Table)
+{
+ long i, j;
+ long V_FindPosition = -1;
+
+ /* Search from right to left. */
+ j = (P_HaystackLen - 1);
+ i = (P_NeedleLen - 1);
+ while ( (j >= 0) && (j >= i) )
+ {
+ while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )
+ {
+ i = P_KMP_Table[i + 1];
+ }
+ i--;
+ j--;
+ if (i < 0)
+ {
+ /* Found. */
+ V_FindPosition = j + 1;
+ break;
+ }
+ }
+
+ return V_FindPosition;
+}
+
+
+/* Search data from left to right. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_find(
+ UT_string *s,
+ long P_StartPosition, /* Start from 0. -1 means last position. */
+ const char *P_Needle,
+ size_t P_NeedleLen)
+{
+ long V_StartPosition;
+ long V_HaystackLen;
+ long *V_KMP_Table;
+ long V_FindPosition = -1;
+
+ if (P_StartPosition < 0)
+ {
+ V_StartPosition = s->i + P_StartPosition;
+ }
+ else
+ {
+ V_StartPosition = P_StartPosition;
+ }
+ V_HaystackLen = s->i - V_StartPosition;
+ if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+ {
+ V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+ if (V_KMP_Table != NULL)
+ {
+ _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);
+
+ V_FindPosition = _utstring_find(s->d + V_StartPosition,
+ V_HaystackLen,
+ P_Needle,
+ P_NeedleLen,
+ V_KMP_Table);
+ if (V_FindPosition >= 0)
+ {
+ V_FindPosition += V_StartPosition;
+ }
+
+ free(V_KMP_Table);
+ }
+ }
+
+ return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_findR(
+ UT_string *s,
+ long P_StartPosition, /* Start from 0. -1 means last position. */
+ const char *P_Needle,
+ size_t P_NeedleLen)
+{
+ long V_StartPosition;
+ long V_HaystackLen;
+ long *V_KMP_Table;
+ long V_FindPosition = -1;
+
+ if (P_StartPosition < 0)
+ {
+ V_StartPosition = s->i + P_StartPosition;
+ }
+ else
+ {
+ V_StartPosition = P_StartPosition;
+ }
+ V_HaystackLen = V_StartPosition + 1;
+ if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+ {
+ V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+ if (V_KMP_Table != NULL)
+ {
+ _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);
+
+ V_FindPosition = _utstring_findR(s->d,
+ V_HaystackLen,
+ P_Needle,
+ P_NeedleLen,
+ V_KMP_Table);
+
+ free(V_KMP_Table);
+ }
+ }
+
+ return V_FindPosition;
+}
+/*******************************************************************************
+ * end substring search functions *
+ ******************************************************************************/
+
+#endif /* UTSTRING_H */
diff --git a/src/eloop/QUELLE b/src/eloop/QUELLE
@@ -0,0 +1,5 @@
+/pkg/umbrellix.net/prog/suitcase/src/eloop Statement of Origin
+
+The headers and source files herewithin ultimately come from the event loop facility of MXF-Remote, which was retrieved from https://git.umbrellix.net/nightmaremail version @6f7024a6c31f36d306a02de9804cb9d93cd67a7c, concerning file descriptor and protegé process management.
+
+This portion requires skalibs and the included uthash header.
diff --git a/src/eloop/sc_eloop_desc.c b/src/eloop/sc_eloop_desc.c
@@ -0,0 +1,3 @@
+// In this file, the addition and removal of file descriptors from the descriptortab is treated.
+// XXX: should use a null hash rather than a UTHash for the descriptortab.
+// XXX: should allow more than one descriptortab?
diff --git a/src/eloop/sc_eloop_pid.c b/src/eloop/sc_eloop_pid.c
diff --git a/src/eloop/sc_eloop_run.c b/src/eloop/sc_eloop_run.c
diff --git a/src/ta_stralloc/QUELLE b/src/ta_stralloc/QUELLE
@@ -0,0 +1,5 @@
+/pkg/umbrellix.net/prog/suitcase/src/ta_stralloc Statement of Origin
+
+The headers and source files herewithin ultimately come from the stralloc facility of qmail, which was retrieved from https://github.com/notqmail/notqmail.git version @8c53cd40a3329d682a905decb1f8734fa1ba2e9a. The proximate source is the stralloc facility of nightmaremail. The ultimate source library is also present in some PD and non-free DJB wares.
+
+This portion does not require skalibs. skalibs includes its own implementation of strallocs.
diff --git a/src/ta_stralloc/stralloc_arts.c b/src/ta_stralloc/stralloc_arts.c
@@ -0,0 +1,10 @@
+#include "byte.h"
+#include "str.h"
+#include "ta_stralloc/stralloc.h"
+
+int stralloc_starts(stralloc *sa, char *s) // PTYPE
+{
+ unsigned int len;
+ len = str_len(s);
+ return (sa->len >= len) && byte_equal(s,len,sa->s);
+}
diff --git a/src/ta_stralloc/stralloc_cat.c b/src/ta_stralloc/stralloc_cat.c
@@ -0,0 +1,7 @@
+#include "byte.h"
+#include "ta_stralloc/stralloc.h"
+
+int stralloc_cat(stralloc *sato, stralloc *safrom) // PTYPE
+{
+ return stralloc_catb(sato,safrom->s,safrom->len);
+}
diff --git a/src/ta_stralloc/stralloc_catb.c b/src/ta_stralloc/stralloc_catb.c
@@ -0,0 +1,19 @@
+#include "ta_stralloc/stralloc.h"
+#include "byte.h"
+#include "error.h"
+#include "oflops.h"
+
+int stralloc_catb(stralloc *sa, char *s, unsigned int n) // PTYPE
+{
+ unsigned int i;
+ if (!sa->s) return stralloc_copyb(sa,s,n);
+ if (__builtin_add_overflow(n, 1, &i)) {
+ errno = error_nomem;
+ return 0;
+ }
+ if (!stralloc_readyplus(sa,i)) return 0;
+ byte_copy(sa->s + sa->len,n,s);
+ sa->len += n;
+ sa->s[sa->len] = 'Z'; /* ``offensive programming'' */
+ return 1;
+}
diff --git a/src/ta_stralloc/stralloc_cats.c b/src/ta_stralloc/stralloc_cats.c
@@ -0,0 +1,8 @@
+#include "byte.h"
+#include "str.h"
+#include "ta_stralloc/stralloc.h"
+
+int stralloc_cats(stralloc *sa, char *s) // PTYPE
+{
+ return stralloc_catb(sa,s,str_len(s));
+}
diff --git a/src/ta_stralloc/stralloc_copy.c b/src/ta_stralloc/stralloc_copy.c
@@ -0,0 +1,7 @@
+#include "byte.h"
+#include "ta_stralloc/stralloc.h"
+
+int stralloc_copy(stralloc *sato, stralloc *safrom) // PTYPE
+{
+ return stralloc_copyb(sato,safrom->s,safrom->len);
+}
diff --git a/src/ta_stralloc/stralloc_eady.c b/src/ta_stralloc/stralloc_eady.c
@@ -0,0 +1,10 @@
+#include "ta_stralloc/stralloc.h"
+// needs lib version
+#ifndef HEADER
+#include "typealloc/typealloclib.h"
+#else
+#include "typealloc/typeallocdefs.h"
+#endif
+
+TypeAlloc_readyplus(stralloc,char,s,len,a,30,stralloc_readyplus)
+TypeAlloc_ready(stralloc,char,s,len,a,30,stralloc_ready)
diff --git a/src/ta_stralloc/stralloc_opyb.c b/src/ta_stralloc/stralloc_opyb.c
@@ -0,0 +1,18 @@
+#include "ta_stralloc/stralloc.h"
+#include "byte.h"
+#include "error.h"
+#include "oflops.h"
+
+int stralloc_copyb(stralloc *sa, char *s, unsigned int n) // PTYPE
+{
+ unsigned int i;
+ if (__builtin_add_overflow(n, 1, &i)) {
+ errno = error_nomem;
+ return 0;
+ }
+ if (!stralloc_ready(sa,i)) return 0;
+ byte_copy(sa->s,n,s);
+ sa->len = n;
+ sa->s[n] = 'Z'; /* ``offensive programming'' */
+ return 1;
+}
diff --git a/src/ta_stralloc/stralloc_opys.c b/src/ta_stralloc/stralloc_opys.c
@@ -0,0 +1,8 @@
+#include "byte.h"
+#include "str.h"
+#include "ta_stralloc/stralloc.h"
+
+int stralloc_copys(stralloc *sa, char *s) // PTYPE
+{
+ return stralloc_copyb(sa,s,str_len(s));
+}
diff --git a/src/ta_stralloc/stralloc_pend.c b/src/ta_stralloc/stralloc_pend.c
@@ -0,0 +1,8 @@
+#include "ta_stralloc/stralloc.h"
+#ifndef HEADER
+#include "typealloc/typealloclib.h"
+#else
+#include "typealloc/typeallocdefs.h"
+#endif
+
+GEN_ALLOC_append(stralloc,char,s,len,a,30,stralloc_readyplus,stralloc_append)
diff --git a/src/tcl/opts.tm b/src/tcl/opts.tm
@@ -0,0 +1,105 @@
+#!/usr/bin/env sh
+# \
+echo "You have reached libsuitcase Tcl component opts.tm. Please note that this"; \
+echo "Tcl module is not intended to be directly invoked."; \
+echo ""; \
+echo "This Tcl module requires Tcl 8.6 or above."; \
+echo "To use opts.tm in your script, you can read it in through tail -n +11, or"; \
+echo "you can add it to your script's project directory as a separate file."; \
+echo "Thank you for using /pkg/umbrellix.net/prog/suitcase"; \
+exit 64
+
+proc opts {{consume {h v H: M: help version headers: markdown:}} argl} {
+ # will always output a list n=2.
+ # [lindex [opts ...] 0] = a list of lists: option, argument(s)
+ # [lindex [opts ...] 1] = a list of arguments not consumed
+ # loptpile contains the long options followed by the number of arguments they consume
+ # a : not immediately preceded by a backslash means that consumed++
+ # two backslashes collapse to one.
+ # soptpile contains the options which are one letter (one may write -HM header markdown)
+ set loptpile [list]
+ set soptpile [list]
+ foreach {option} $consume {
+ set optname ""
+ set colons 0
+ set prevl ""
+ foreach {l} [split $option {}] {
+ if {$l == ":" && $prevl != "\\"} {incr colons}
+ if {($l != "\\" || $prevl == "\\") && $colons < 1} {
+ append optname $l
+ }
+ if {$prevl != "\\"} {set prevl $l} {set prevl ""}
+ }
+ if {[string length $optname] > 1} {lappend loptpile $optname $colons} {lappend soptpile $optname $colons}
+ }
+ set consumingargs [list]
+ set consumedargs [list]
+ set unconsumedargs [list]
+ set n 0
+ set dashdash 0
+ while {$n < [llength $argl]} {
+ set arg [lindex $argl $n]
+ set colons 0
+ if {$dashdash} {
+ lappend unconsumedargs $arg
+ } {
+ if {[string index $arg 0] == "-"} {
+ if {[string index $arg 1] == "-"} {
+ if {[string length $arg] == 2} {set dashdash 1} {
+ # long opt; consume argument immediately after, even if it starts with a dash
+ # if not a real opt, don't care
+ if {[set colons [dict get $loptpile [string range $arg 2 end]]] != ""} {
+ set consumedarg [list [string range $arg 2 end]]
+ if {$colons != 0} {
+ if {[llength [lrange $argl [expr {$n+1}] [expr {$n+$colons}]]] == $colons} {
+ lappend consumedarg [lrange $argl [expr {$n+1}] [expr {$n+$colons}]]
+ incr n $colons
+ } {
+ return -code error "Reached end of arguments list while consuming arguments for option $arg ([lrange $argl [expr {$n+1}] [expr {$n+$colons}]])"
+ }
+ }
+ lappend consumedargs $consumedarg
+ } {
+ lappend unconsumedargs $arg
+ }
+ }
+ } {
+ if {[string length $arg] == 1} {lappend unconsumedargs $arg} {
+ # short option
+ foreach {letter} [split [string range $arg 1 end] {}] {
+ if {[catch {dict get $soptpile $letter} colons] == 0} {
+ #set colons [dict get $soptpile $letter]
+ set consumedarg [list $letter]
+ if {$colons != 0} {
+ if {[llength [lrange $argl [expr {$n+1}] [expr {$n+$colons}]]] == $colons} {
+ foreach {ar} [lrange $argl [expr {$n+1}] [expr {$n+$colons}]] {lappend consumedarg $ar}
+ incr n $colons
+ } {
+ return -code error "Reached end of arguments list while consuming arguments for option $arg ([lrange $argl [expr {$n+1}] [expr {$n+$colons}]])"
+ }
+ }
+ lappend consumedargs $consumedarg
+ } {
+ # unrecognized dash option - warn user and treat as a separate non-option arg
+ puts stderr [format "warning: option -%s not recognized by this program. Treating as a SEPARATE non-option argument - if this wasn't intended, put the argument containing this option after a \'--\'!" $letter]
+ lappend unconsumedargs [join [list - $letter] {}]
+ }
+ # if there's even zero colons
+ }
+ # foreach letter
+ }
+ # if only dash, else short option
+ }
+ # if two dashes
+ } else {
+ lappend unconsumedargs $arg
+ }
+ # if one dash
+ }
+ # if dashdash
+ incr n
+ }
+ # while
+ return [list $consumedargs $unconsumedargs]
+}
+
diff --git a/src/typealloc/QUELLE b/src/typealloc/QUELLE
@@ -0,0 +1,5 @@
+/pkg/umbrellix.net/prog/suitcase/src/typealloc Statement of Origin
+
+The headers and source files herewithin ultimately come from the gen_alloc facility of qmail, which was retrieved from https://github.com/notqmail/notqmail.git version @8c53cd40a3329d682a905decb1f8734fa1ba2e9a. The proximate source is the typealloc facility in nightmaremail.git @6f7024a6c31f36d306a02de9804cb9d93cd67a7c src/mxf-remote/{typealloc.h,typeallocdefs.h,typealloclib.h}. The ultimate source library is also present in some PD and non-free DJB wares.
+
+This portion does not require skalibs.
diff --git a/src/typealloc/typealloc.h b/src/typealloc/typealloc.h
@@ -0,0 +1,9 @@
+#ifndef TypeAlloc_H // this will be fine though it's nonstandard
+#define TypeAlloc_H
+
+#define TypeAlloc_typedef(ta,type,field,len,a) \
+ typedef struct ta { type *field; size_t len; size_t a; } ta;
+
+#define TA_ZERO {NULL, 0, 0}
+
+#endif
diff --git a/src/typealloc/typeallocdefs.h b/src/typealloc/typeallocdefs.h
@@ -0,0 +1,33 @@
+#ifndef TypeAlloc_DEFS_H
+#define TypeAlloc_DEFS_H
+/* de https://github.com/notqmail/notqmail */
+
+//#include "alloc.h"
+//#include "error.h"
+// needed from qmail
+
+#include "oflops.h"
+// unclear
+
+#define TypeAlloc_readyplus(ta,type,field,len,a,base,ta_rplus) \
+int ta_rplus(ta *x, size_t n);
+
+/* this needs a TypeAlloc_readyplus call before as it reuses the internal helper
+ * function. */
+#define TypeAlloc_ready(ta,type,field,len,a,base,ta_ready) \
+int ta_ready(ta *x, size_t n);
+
+#define TypeAlloc_append(ta,type,field,len,a,base,ta_rplus,ta_append) \
+int ta_append(ta *x, type i);
+
+#define TypeAlloc_appendentries(ta,type,field,len,a,base,ta_rplus,ta_cat) \
+int ta_cat(ta *x, type *i, size_t n);
+
+// example usage -> ta_copy(saa, saa);
+#define TypeAlloc_copy(ta,type,field,len,a,base,ta_ready,ta_copy) \
+int ta_copy(ta *x, ta *y);
+
+#define TypeAlloc_free(ta,type,field,len,a,base,ta_free) \
+int ta_free(ta *x);
+
+#endif
diff --git a/src/typealloc/typealloclib.h b/src/typealloc/typealloclib.h
@@ -0,0 +1,70 @@
+#ifndef TypeAlloc_DEFS_H
+#define TypeAlloc_DEFS_H
+/* note - this is to make sure this overrides defs if both are included. */
+/* de https://github.com/notqmail/notqmail */
+
+#include "alloc.h"
+#include <stdlib.h>
+#include "error.h"
+// needed from qmail
+
+#include "oflops.h"
+// unclear
+
+#define TypeAlloc_readyplus(ta,type,field,len,a,base,ta_rplus) \
+static int ta_rplus ## _internal (ta *x, size_t n, size_t pluslen) \
+{ \
+ size_t nlen; \
+ errno = error_nomem; \
+ if (x->field) { \
+ size_t nnum; \
+ type *nfield; \
+ if (__builtin_add_overflow(n, pluslen, &n)) \
+ return 0; \
+ if (n <= x->a) \
+ return 1; \
+ if (__builtin_add_overflow(n, (n >> 3) + base, &nnum)) \
+ return 0; \
+ if (__builtin_mul_overflow(nnum, sizeof(type), &nlen)) \
+ return 0; \
+ nfield = realloc(x->field, nlen); \
+ if (nfield == NULL) \
+ return 0; \
+ x->field = nfield; \
+ x->a = nnum; \
+ return 1; } \
+ x->len = 0; \
+ if (__builtin_mul_overflow(n, sizeof(type), &nlen)) \
+ return 0; \
+ x->field = (type *) malloc(nlen); \
+ if (!x->field) \
+ return 0; \
+ x->a = n; \
+ return 1; } \
+int ta_rplus(ta *x, size_t n) \
+{ return ta_rplus ## _internal (x, n, x->len); }
+
+/* this needs a TypeAlloc_readyplus call before as it reuses the internal helper
+ * function. */
+#define TypeAlloc_ready(ta,type,field,len,a,base,ta_ready) \
+int ta_ready(ta *x, size_t n) \
+{ return ta_ready ## plus_internal (x, n, 0); }
+
+#define TypeAlloc_append(ta,type,field,len,a,base,ta_rplus,ta_append) \
+int ta_append(ta *x, type i) \
+{ if (!ta_rplus(x,1)) return 0; x->field[x->len++] = i; return 1; }
+
+#define TypeAlloc_appendentries(ta,type,field,len,a,base,ta_rplus,ta_cat) \
+int ta_cat(ta *x, type *i, size_t n) \
+{ if (!ta_rplus(x,n)) return 0; for (size_t j = 0; j < n; ++j) x->field[x->len++] = *(i + j); return 1; }
+
+// example usage -> ta_copy(saa, saa);
+#define TypeAlloc_copy(ta,type,field,len,a,base,ta_ready,ta_copy) \
+int ta_copy(ta *x, ta *y) \
+{ if (!ta_ready(x,y->len)) return 0; x->len = 0; for (size_t j = 0; j < y->len; ++j) x->field[x->len++] = *(y->field + j); return 1; }
+
+#define TypeAlloc_free(ta,type,field,len,a,base,ta_free) \
+int ta_free(ta *x) \
+{ free(x->field); x->field = NULL; x->a = x->len = 0; return 1; }
+
+#endif
