Initial commit for lib/qpselect.c & .h and lib/qtimers.c & .h

lib/qpselect supports data structure to multiplex between many file
descriptors using pselect().

lib/qtimers supports data structures to run multiple timers.

Also affected:

  lib/Makefile.am  -- to add the new files
  lib/memtypes.c   -- to add further memory types for the above

1 files changed, 973 insertions, 0 deletions

diff --git a/lib/qpselect.c b/lib/qpselect.c
new file mode 100644
index 00000000..e792bbaa
--- /dev/null
+++ b/lib/qpselect.c
@@ -0,0 +1,973 @@
+/* Quagga pselect support -- header
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2, or (at your
+ * option) any later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <signal.h>
+#include <string.h>
+
+#include "zassert.h"
+#include "qpselect.h"
+#include "qpthreads.h"
+#include "qtime.h"
+#include "memory.h"
+#include "vector.h"
+
+/*==============================================================================
+ * Quagga pselect -- qps_xxxx
+ *
+ * Here and in qpselect.h is a data structure for managing multiple file
+ * descriptors and running pselect to wait for I/O activity and to multiplex
+ * between the file descriptors.
+ *
+ * The qps_selection structure manages a collection of file descriptors which
+ * are to be waited on together in a pselect statement.
+ *
+ * NB: it is ASSUMED that a qps_selection will be private to the thread in
+ *     which it is created and used.
+ *
+ *     There is NO mutex handling here.
+ *
+ * This supports pselect, so supports:
+ *
+ *   * waiting for file descriptors, which may each be expecting any combination
+ *     of error/read/write events.
+ *
+ *     Files may be added or removed from the selection.  Files in the selection
+ *     may then be enabled/disabled for any combination of error/read/write
+ *     "mode" events.
+ *
+ *   * a timeout
+ *
+ *     Infinite timeouts are not supported.
+ *
+ *   * an optional signal number and sigmask
+ *
+ *     So that a signal may be used to interrupt a waiting pselect.
+ *
+ *     For this to work there must be a signal which is generally masked, and
+ *     is unmasked for the duration of the pselect.
+ *
+ * When a pselect returns there may be a number of files with events pending.
+ * The qps_dispatch_next() calls the action routine for the next event to be
+ * dealt with.  Events are dispatched in the order: error, read and write, and
+ * then in file descriptor order.  (So all error events in fd order, then all
+ * read events, and so on.)
+ *
+ * Note that at no time are any modes automatically disabled.  So the system is
+ * level triggered.  So, for example, a read event that is not dealt with will
+ * be triggered again on the next pselect -- unless the read mode is explicitly
+ * disabled for the file.
+ *
+ * Action Functions
+ * ----------------
+ *
+ * There is a separate action function for each mode.  Each file has its own
+ * set of action functions -- so these may be used to implement a form of
+ * state machine for the file.
+ *
+ * When the action function is called it is passed the qps_file structure and
+ * the file_info pointer from that structure.
+ *
+ * During an action function modes may be enabled/disabled, actions changed,
+ * the file removed from the selection... there are no restrictions.
+ *
+ *
+ * TODO: worry about closing down a selection.
+ *
+ * TODO: worry about closing down files
+ */
+
+static int qps_super_set_map_made = 0 ;
+
+static void qps_make_super_set_map(void) ;
+
+/*==============================================================================
+ * qps_selection handling
+ */
+
+/* Forward references   */
+static qps_file qps_file_lookup_fd(qps_selection qps, int fd, qps_file insert) ;
+static void qps_file_remove(qps_selection qps, qps_file qf) ;
+static int qps_file_check(qps_selection qps, qps_file qf) ;
+static void qps_super_set_zero(fd_super_set* p_set, int n) ;
+static int qps_next_fd_pending(fd_super_set* pending, int fd, int fd_last) ;
+
+/* See qps_make_super_set_map() and qps_pselect() below.        */
+static short fd_byte_count[FD_SETSIZE] ;    /* number of bytes for fds 0..fd */
+
+/* Initialise a selection -- allocating it if required.
+ *
+ * Returns the qps_selection.
+ */
+qps_selection
+qps_selection_init_new(qps_selection qps)
+{
+  if (!qps_super_set_map_made)
+    qps_make_super_set_map() ;  /* map the fd_super_set         */
+
+  if (qps == NULL)
+    qps = XCALLOC(MTYPE_QPS_SELECTION, sizeof(struct qps_selection)) ;
+  else
+    memset(qps, 0, sizeof(struct qps_selection)) ;
+
+  /* Zeroising initialises:
+   *
+   *   fd_count      -- no fd's yet
+   *   fd_direct     -- not direct lookup
+   *
+   *   files         -- empty vector
+   *
+   *   fd_last       -- unset
+   *   enabled_count -- no fd's enabled in any mode
+   *   enabled       -- empty bit vectors
+   *
+   *   tried_fd_last -- nothing tried yet
+   *   tried_count   -- nothing tried yet
+   *   results       -- empty bit vectors
+   *
+   *   pend_count    -- no results to dispatch
+   *   pend_mnum     -- unset
+   *   pend_fd       -- unset
+   *
+   *   signum        -- no signal to be enabled
+   *   sigmask       -- unset
+   *
+   * So nothing else to do.
+   */
+
+  return qps ;
+} ;
+
+/* Add given file to the selection, setting its fd and pointer to further
+ * file information.  All modes are disabled.
+ *
+ * This initialises most of the qps_file structure, but not the actions.
+ *
+ * Adding a file using the same fd as an existing file is a fatal error.
+ */
+void
+qps_add_file(qps_selection qps, qps_file qf, int fd, void* file_info)
+{
+  qf->selection    = qps ;
+
+  qf->file_info    = file_info ;
+  qf->fd           = fd ;
+
+  qf->enabled_bits = 0 ;
+
+  qps_file_lookup_fd(qps, fd, qf) ;     /* Add. */
+} ;
+
+/* Remove given file from the selection.
+ *
+ * It is the callers responsibility to ensure that the file is in a suitable
+ * state to be removed from the selection.
+ *
+ * The file is disabled in all modes.
+ *
+ * NB: it is a FATAL error to remove a file that is not a member of its
+ *     selection.
+ */
+void
+qps_remove_file(qps_file qf)
+{
+  passert(qf->selection != NULL) ;
+
+  qps_file_remove(qf->selection, qf) ;
+
+  qf->selection = NULL ;        /* no longer a selection member */
+} ;
+
+/* Set the signal mask for the selection.
+ *
+ * This supports the unmasking of a single signal for the duration of the
+ * pselect operation.
+ *
+ * It is assumed that the set of signals generally masked by a thread is
+ * essentially static.  So this function is passed that set.  (So the sigmask
+ * argument must have the signum signal masked.)
+ *
+ * If the set of signals masked by the thread changes, then this function
+ * should be called again.
+ *
+ * Setting a signum == 0 turns OFF the use of the sigmask.
+ */
+void
+qps_set_signal(qps_selection qps, int signum, sigset_t sigmask)
+{
+  qps->signum  = signum ;
+
+  if (signum != 0)
+    {
+      assert(sigismember(&sigmask, signum)) ;
+      sigdelset(&sigmask, signum) ;
+      qps->sigmask = sigmask ;
+    } ;
+} ;
+
+/* Execute a pselect for the given selection -- subject to the given timeout
+ * *time*.
+ *
+ * The time-out time is an "absolute" time, as measured by qt_get_monotonic().
+ *
+ * A timeout time <= the current qt_get_monotonic() is treated as a zero
+ * timeout period, and will return immediately from the pselect.
+ *
+ * There is no support for an infinite timeout.
+ *
+ * Returns: -1 => EINTR occurred
+ *           0 => hit timeout -- no files are ready
+ *         > 0 => there are this many files ready in one or more modes
+ *
+ * All other errors are FATAL.
+ *
+ * The qps_dispatch_next() processes the returns from pselect().
+ */
+int
+qps_pselect(qps_selection qps, qtime_t timeout)
+{
+  struct timespec ts ;
+  qps_mnum_t  mnum ;
+  fd_set*     p_fds[qps_mnum_count] ;
+  int  n ;
+
+  /* Convert timeout time to interval for pselect()     */
+  timeout -= qt_get_monotonic() ;
+  if (timeout < 0)
+    timeout = 0 ;
+
+  /* Prepare the argument/result bitmaps                */
+  /* Capture pend_mnum and tried_count[]                */
+
+  n   = fd_byte_count[qps->fd_last] ; /* copy up to last sig. byte  */
+
+  qps->pend_mnum = qps_mnum_count ;
+  for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum)
+    if ((qps->tried_count[mnum] = qps->enabled_count[mnum]) != 0)
+      {
+        memcpy(&(qps->results[mnum].bytes), &(qps->enabled[mnum].bytes), n) ;
+        p_fds[mnum] = &(qps->results[mnum].fdset) ;
+        if (mnum < qps->pend_mnum)
+          qps->pend_mnum = mnum ;
+      }
+    else
+      p_fds[mnum] = NULL ;
+
+  /* Capture tried_fd_last and set initial pend_fd.     */
+  qps->tried_fd_last = qps->fd_last ;
+  qps->pend_fd       = 0 ;
+
+  /* Finally ready for the main event                   */
+  n = pselect(qps->fd_last + 1, p_fds[qps_read_mnum],
+                                p_fds[qps_write_mnum],
+                                p_fds[qps_error_mnum],
+                                qtime2timespec(&ts, timeout),
+                                (qps->signum != 0) ? &qps->sigmask : NULL) ;
+
+  qps->pend_count = (n >= 0) ? n : 0 ;  /* avoid setting -ve pend_count */
+
+  /* if 1 or more pending results, then must have at least one pending mode  */
+  assert((n <= 0) || (qps->pend_mnum < qps_mnum_count)) ;
+
+  /* Return appropriately, if we can                    */
+  if ((n >= 0) || (errno == EINTR))
+    return n ;
+
+  zabort_errno("Failed in pselect") ;
+} ;
+
+/* Dispatch the next errored/readable/writeable file, as returned by the
+ * most recent qps_pselect().
+ *
+ * Processes the errored files, then the readable and lastly the writeable.
+ *
+ * Processes one file per call of this function, by invoking the file's
+ * "action" routine.
+ *
+ * If a given file is ready in more than one mode, all modes will be processed,
+ * unless the action routine for one mode disables the file for other modes, or
+ * removes it from the selection.
+ *
+ * Returns the number of files left to process (after the one just processed).
+ */
+int
+qps_dispatch_next(qps_selection qps)
+{
+  int        fd ;
+  qps_file   qf ;
+  qps_mnum_t mnum ;
+
+  if (qps->pend_count == 0)
+    return 0 ;                  /* quit immediately of nothing to do.   */
+
+  fd   = qps->pend_fd ;
+  mnum = qps->pend_mnum ;
+
+  while (1)
+    {
+      fd = qps_next_fd_pending(&(qps->results[mnum]), fd, qps->tried_fd_last) ;
+      if (fd >= 0)
+        break ;                 /* easy if have another fd in current mode.  */
+
+      do                        /* step to next mode that was not empty      */
+        {
+          ++mnum ;
+          if (mnum >= qps_mnum_count)
+            zabort("Unexpectedly ran out of pending stuff") ;
+        } while (qps->tried_count[mnum] == 0) ;
+
+      qps->pend_mnum = mnum ;   /* update mode                  */
+      fd = 0 ;                  /* back to the beginning        */
+    } ;
+
+  qps->pend_count -= 1 ;        /* one less pending             */
+  qps->pend_fd     = fd ;       /* update scan                  */
+
+  qf = qps_file_lookup_fd(qps, fd, NULL) ;
+
+  dassert( ((qf->enabled_bits && qps_mbit(mnum)) != 0) &&
+           (qf->actions[mnum] != NULL) ) ;
+
+  qf->actions[mnum](qf, qf->file_info) ;  /* dispatch the required action */
+
+  return qps->pend_count ;
+} ;
+
+/*==============================================================================
+ * qps_file structure handling
+ */
+
+/* Initialise qps_file structure -- allocating one if required.
+ *
+ * If a template is given, then the action functions are copied from there to
+ * the new structure.  See above for discussion of action functions.
+ *
+ * Once initialised, the file may be added to a selection.
+ *
+ * Returns the qps_file.
+ */
+qps_file
+qps_file_init_new(qps_file qf, qps_file template)
+{
+  if (qf == NULL)
+    qf = XCALLOC(MTYPE_QPS_FILE, sizeof(struct qps_file)) ;
+  else
+    memset(qf, 0, sizeof(struct qps_file)) ;
+
+  /* Zeroising has initialised:
+   *
+   *   selection     -- NULL  -- ditto
+   *
+   *   file_info     -- NULL  -- is set by qps_add_file()
+   *   fd            -- unset -- ditto
+   *
+   *   enabled_bits  -- nothing enabled
+   *
+   *   actions[]     -- all set to NULL
+   */
+
+  if (template != NULL)
+    memcpy(qf->actions, template->actions, sizeof(qf->actions)) ;
+
+  return qf ;
+} ;
+
+/* Free dynamically allocated qps_file structure.
+ *
+ * It is the caller's responsibility to have removed it from any selection it
+ * may have been in.
+ */
+void
+qps_file_free(qps_file qf)
+{
+  assert(qf->selection == NULL) ;       /* Mustn't be a selection member ! */
+
+  XFREE(MTYPE_QPS_FILE, qf) ;
+} ;
+
+/* Enable (or re-enable) file for the given mode.
+ *
+ * If the action argument is not NULL, set the action for the mode.
+ *
+ * NB: It is a FATAL error to enable a mode with a NULL action.
+ *
+ * NB: It is a FATAL error to enable modes for a file which is not in a
+ *     selection.
+ */
+void
+qps_enable_mode(qps_file qf, qps_mnum_t mnum, qps_action* action)
+{
+  qps_mbit_t    mbit = qps_mbit(mnum) ;
+  qps_selection qps  = qf->selection ;
+
+  dassert((qps != NULL) && (qps_file_check(qps, qf))) ;
+  dassert(mnum <= qps_mnum_count) ;
+
+  if (action != NULL)
+    qf->actions[mnum] = action ;
+  else
+    dassert(qf->actions[mnum] != NULL) ;
+
+  if (qf->enabled_bits & mbit)
+    dassert(FD_ISSET(qf->fd, &(qps->enabled[mnum].fdset))) ;
+  else
+    {
+      dassert( ! FD_ISSET(qf->fd, &(qps->enabled[mnum].fdset))) ;
+      FD_SET(qf->fd, &(qps->enabled[mnum].fdset)) ;
+      ++qps->enabled_count[mnum] ;
+      qf->enabled_bits |= mbit ;
+    } ;
+} ;
+
+/* Set action for given mode -- does not enable/disable.
+ *
+ * May unset an action by setting it NULL !
+ *
+ * See above for discussion of action functions.
+ *
+ * NB: it is a fatal error to unset an action for a mode which is enabled.
+ */
+void
+qps_set_action(qps_file qf, qps_mnum_t mnum, qps_action* action)
+{
+  qps_selection qps = qf->selection ;
+
+  dassert((qps != NULL) && (qps_file_check(qps, qf))) ;
+  dassert(mnum < qps_mnum_count) ;
+
+  if (action == NULL)
+    passert((qf->enabled_bits & qps_mbit(mnum)) == 0) ;
+
+  qf->actions[mnum] = action ;
+} ;
+
+/* Disable file for one or more modes.
+ *
+ * If there are any pending pending results for the modes, those are discarded.
+ *
+ * Note that this is modestly "optimised" to deal with disabling a single mode.
+ * (Much of the time only the write mode will be being disabled !)
+ */
+
+static qps_mnum_t qps_first_mnum[qps_mbit(qps_mnum_count)] =
+  {
+     -1,  /* 0 -> -1 -- no bit set      */
+      0,  /* 1 ->  0 -- B0 is first bit */
+      1,  /* 2 ->  1 -- B1 is first bit */
+      1,  /* 3 ->  1 -- B1 is first bit */
+      2,  /* 4 ->  2 -- B2 is first bit */
+      2,  /* 5 ->  2 -- B2 is first bit */
+      2,  /* 6 ->  2 -- B2 is first bit */
+      2   /* 7 ->  2 -- B2 is first bit */
+  } ;
+
+static qps_mbit_t qps_first_mbit[qps_mbit(qps_mnum_count)] =
+  {
+      0,  /* 0 ->  0 -- no bit set      */
+      1,  /* 1 ->  1 -- B0 is first bit */
+      2,  /* 2 ->  2 -- B1 is first bit */
+      2,  /* 3 ->  2 -- B1 is first bit */
+      4,  /* 4 ->  4 -- B2 is first bit */
+      4,  /* 5 ->  4 -- B2 is first bit */
+      4,  /* 6 ->  4 -- B2 is first bit */
+      4   /* 7 ->  4 -- B2 is first bit */
+  } ;
+
+CONFIRM(qps_mbit(qps_mnum_count) == 8) ;
+
+void
+qps_disable_modes(qps_file qf, qps_mbit_t mbits)
+{
+  qps_mnum_t  mnum ;
+
+  qps_selection qps = qf->selection ;
+
+  dassert((qps != NULL) && (qps_file_check(qps, qf))) ;
+  dassert(mbits <= qps_all_mbits) ;
+
+  mbits &= qf->enabled_bits ;   /* don't bother with any not enabled  */
+  qf->enabled_bits ^= mbits ;   /* unset what we're about to disable  */
+
+  while (mbits != 0)
+    {
+      mnum = qps_first_mnum[mbits] ;
+
+      if (FD_ISSET(qf->fd, &(qps->enabled[mnum].fdset)))
+        {
+          FD_CLR(qf->fd, &(qps->enabled[mnum].fdset)) ;
+          dassert(qps->enabled_count[mnum] > 0) ;
+          --qps->enabled_count[mnum] ;
+        } ;
+      if ((qps->pend_count != 0) && (qps->tried_count[mnum] != 0)
+                       && (FD_ISSET(qf->fd, &(qps->results[mnum].fdset))))
+        {
+          FD_CLR(qf->fd, &(qps->results[mnum].fdset)) ;
+          dassert(qps->pend_count > 0) ;
+          --qps->pend_count ;
+        } ;
+
+      mbits ^= qps_first_mbit[mnum] ;
+    } ;
+} ;
+
+/*==============================================================================
+ * Handling the files vector.
+ *
+ * For small numbers of fd's, the files vector is kept as a list, in fd order.
+ * Files are found by binary chop, and added/removed by insert/delete in the
+ * list.
+ *
+ * For large numbers of fd's, the files vector is kept as an array, indexed by
+ * fd.
+ */
+
+/* Comparison function for binary chop  */
+static int
+qps_fd_cmp(const int** pp_fd, const qps_file* p_qf)
+{
+  if (**pp_fd  < (*p_qf)->fd)
+    return -1 ;
+  if (**pp_fd  > (*p_qf)->fd)
+    return +1 ;
+  return 0 ;
+}
+
+/* Lookup/Insert file by file-descriptor.
+ *
+ * Inserts if insert argument is not NULL.
+ *
+ * Returns the file we found (if any) or the file we just inserted.
+ *
+ * NB: FATAL error to insert file with same fd as an existing one.
+ */
+static qps_file
+qps_file_lookup_fd(qps_selection qps, int fd, qps_file insert)
+{
+  qps_file qf ;
+
+  dassert((fd >= 0) && (fd < FD_SETSIZE)) ;
+
+  /* If we are expecting to insert, then now may be the time to change  */
+  /* up to a directly address files vector.                             */
+  if ((insert != NULL) && !qps->fd_direct && (qps->fd_count > 9))
+    {
+      vector_index i ;
+      vector   tmp ;
+
+      tmp = vector_move_here(NULL, &qps->files) ;
+
+      for (VECTOR_ITEMS(tmp, qf, i))
+        vector_set_item(&qps->files, qf->fd, qf) ;
+
+      vector_free(tmp) ;
+
+      qps->fd_direct = 1 ;
+    } ;
+
+  /* Look-up and perhaps insert.                                        */
+  if (qps->fd_direct)
+    {
+      qf = vector_get_item(&qps->files, fd) ;   /* NULL if not there    */
+      if (insert != NULL)
+        {
+          if (qf != NULL)
+            zabort("File with given fd already exists in qps_selection") ;
+          qf = insert ;
+          vector_set_item(&qps->files, fd, insert) ;
+        } ;
+    }
+  else
+    {
+      int ret ;
+      vector_index i = vector_bsearch(&qps->files,
+                                      (vector_bsearch_cmp*)qps_fd_cmp,
+                                      &fd, &ret) ;
+      if (insert != NULL)
+        {
+          if (ret == 0)
+            zabort("File with given fd already exists in qps_selection") ;
+          qf = insert ;
+          vector_insert_item_here(&qps->files, i, ret, insert) ;
+        } ;
+    } ;
+
+  /* If we inserted, keep fd_count and fd_last up to date.              */
+  if (insert != NULL)
+    {
+      ++qps->fd_count ;
+      if (fd > qps->fd_last)
+        qps->fd_last = fd ;
+    } ;
+
+  /* Sanity checking.                                                   */
+  dassert( (qf == NULL) || ((qps == qf->selection) && (fd == qf->fd)) ) ;
+
+  /* Return the file we found or inserted.                              */
+  return qf ;
+} ;
+
+/* Check file in selection.
+ *
+ * This looks up the file in the selection and performs a number of sanity
+ * checks.
+ *
+ * NB: it is a FATAL error if the file has an invalid fd, or the selection does
+ *     not natch the file's selection, or the files selection is NULL.
+ *
+ * NB: it is a FATAL error for the file not to be in the selection when looked
+ *     up by its fd.
+ *
+ * When (or if) returns, returns 1.
+ */
+static int
+qps_file_check(qps_selection qps, qps_file qf)
+{
+  qps_file qff ;
+  int fd = qf->fd ;
+
+  passert((fd >= 0) && (fd < FD_SETSIZE)
+                    && (qf->selection != NULL) && (qps == qf->selection)) ;
+
+  if (qps->fd_direct)
+    qff = vector_get_item(&qps->files, fd) ;   /* NULL if not there    */
+  else
+    {
+      int ret ;
+      vector_index i = vector_bsearch(&qps->files,
+                                      (vector_bsearch_cmp*)qps_fd_cmp,
+                                      &fd, &ret) ;
+      if (ret == 0)
+        qff = vector_get_item(&qps->files, i) ;
+      else
+        qff = NULL ;
+    } ;
+
+  passert(qff == qf) ;
+
+  return 1 ;
+} ;
+
+/* Remove file from selection by file-descriptor.
+ *
+ * Returns the file we found and have removed (if any).
+ *
+ * TODO: should deleting a non existent file be fatal ?
+ */
+static qps_file
+qps_file_remove_fd(qps_selection qps, int fd)
+{
+  qps_file qf ;
+  int      fd_last ;
+
+  dassert((fd >= 0) && (fd < FD_SETSIZE)) ;
+
+  /* Look-up and remove.                                                */
+  if (qps->fd_direct)
+    {
+      qf      = vector_unset_item(&qps->files, fd) ; /* NULL if not there  */
+      fd_last = vector_end(&qps->files) - 1 ;
+    }
+  else
+    {
+      int ret ;
+      vector_index i = vector_bsearch(&qps->files,
+                                      (vector_bsearch_cmp*)qps_fd_cmp,
+                                      &fd, &ret) ;
+      if (ret == 0)
+        {
+          qps_file qf_last ;
+          qf = vector_delete_item(&qps->files, i) ;
+
+          qf_last = vector_get_last_item(&qps->files) ;
+          if (qf_last == NULL)
+            fd_last = -1 ;
+          else
+            fd_last = qf_last->fd ;
+        }
+      else
+        qf = NULL ;
+    } ;
+
+  /* If we removed, keep fd_count and fd_last up to date.               */
+  /* Also, remove the fd from all vectors.                              */
+  if (qf != NULL)
+    {
+      dassert(qps->fd_count != 0) ;
+      ++qps->fd_count ;
+
+      dassert( ((qps->fd_count != 0) && (fd_last >= 0)) ||
+               ((qps->fd_count == 0) && (fd_last <  0)) ) ;
+
+      qps->fd_last = (fd_last >= 0) ? fd_last : 0 ;
+
+      qps_disable_modes(qf, qps_all_mbits) ;
+    } ;
+
+  /* Return the file we found and have removed.                         */
+  return qf ;
+} ;
+
+/* Remove file from selection.
+ *
+ * NB: FATAL error if file is not in the selection, or the file-descriptor
+ * is invalid (or refers to some other file !).
+ */
+static void
+qps_file_remove(qps_selection qps, qps_file qf)
+{
+  qps_file qfd ;
+
+  passert((qf->fd >= 0) && (qf->fd < FD_SETSIZE) && (qps == qf->selection)) ;
+
+  qfd = qps_file_remove_fd(qps, qf->fd) ;
+
+  passert(qfd == qf) ;
+} ;
+
+ /*==============================================================================
+ * fd_super_set support.
+ *
+ * For large sets of file descriptors something faster than testing for all
+ * possible bits is required.  The fd_super_set assumes that the fd_set is a
+ * straightforward bit-vector, and overlays a 32-bit word array and a byte
+ * array over that.
+ *
+ * Cannot tell if the underlying bit vector is arranged in bytes, or some
+ * longer words.  Cannot tell if words are held big or little endian.  Cannot
+ * tell if lowest numbered fd will be highest or lowest in whatever unit it's
+ * held in.
+ *
+ * So...  we have maps for fd -> our word index, and fd -> byte index.
+ *
+ *        we have a map for fd -> mask for bit used in its byte.
+ *
+ * We require that fds will be numbered consistently in bytes.  That is,
+ * every (fd mod 8) == n will appear in the same bit in a byte, for all fd (
+ * for n = 0..7).  This allows the final map, which takes a byte value and
+ * returns the lowest numbered fd in the byte, mod 8.
+ *
+ * To copy all the bytes for all descriptors 0..fd, also construct
+ * fd_byte_count[] -- which copes with the fact that on a big-endian machine
+ * it is possible that descriptor fd - 8 may be in a higher numbered byte than
+ * fd !  Using this count assumes that the underlying system really does not
+ * look at bits beyond the given maximum fd.
+ */
+
+static short    fd_word_map[FD_SETSIZE] ; /* maps fd to word index         */
+static short    fd_byte_map[FD_SETSIZE] ; /* maps fd to byte index         */
+static uint8_t  fd_bit_map [FD_SETSIZE] ; /* maps fd to bit in byte        */
+
+static int8_t   fd_first_map[256] ; /* maps byte value to 0..7, where that */
+                                    /* is the lowest fd bit set in byte.   */
+
+/* Scan for next fd in given fd set, and clear it.
+ *
+ * Starts at the given fd, will not consider anything above fd_last.
+ *
+ * Returns next fd, or -1 if none.
+ */
+static int
+qps_next_fd_pending(fd_super_set* pending, int fd, int fd_last)
+{
+  uint8_t b ;
+
+  while (pending->words[fd_word_map[fd]] == 0)  /* step past zero words */
+    {
+      fd = (fd & ~ 0x001F) + FD_WORD_BITS ;
+                                        /* step to start of next word   */
+      if (fd > fd_last)
+        return -1 ;                     /* quit if past last            */
+    } ;
+
+  fd &= ~0x0007 ;                       /* step back to first in byte   */
+  while (1)
+    {
+      b = pending->bytes[fd_byte_map[fd]] ;
+                                        /* byte associated with fd      */
+      if (b != 0)
+        break ;                         /* stop looking                 */
+
+      fd += 8 ;
+      if (fd > fd_last)
+        return -1 ;
+    } ;
+
+  fd += fd_first_map[b] ;
+
+  dassert(fd <= fd_last) ;
+  dassert((b & fd_bit_map[fd]) == fd_bit_map[fd]) ;
+
+  FD_CLR(fd, &pending->fdset) ;
+
+  dassert((b ^ fd_bit_map[fd]) == pending->bytes[fd_byte_map[fd]]) ;
+
+  return fd ;
+} ;
+
+/* Make a map of the fd_super_set.
+ *
+ * The form of an fd_set is not defined.  This code verifies that it is, in
+ * fact a bit vector, and hence that the fd_super_set works here !
+ *
+ * It is a FATAL error if things don't work out.
+ */
+static void
+qps_make_super_set_map(void)
+{
+  fd_super_set test ;
+  int fd, i, iw, ib ;
+
+  /* (1) check that a zeroised fd_super_set is an empty one.    */
+  qps_super_set_zero(&test, 1) ;
+
+  for (fd = 0 ; fd < FD_SETSIZE ; ++fd)
+    if (FD_ISSET(fd, &test.fdset))
+      zabort("Zeroised fd_super_set is not empty") ;
+
+  /* (2) check that zeroising the fd_set doesn't change things  */
+  FD_ZERO(&test.fdset) ;
+  for (iw = 0 ; iw < FD_SUPER_SET_WORD_SIZE ; ++iw)
+    if (test.words[iw] != 0)
+      zabort("Zeroised fd_super_set is not all zero words") ;
+
+  /* (3) check that setting one fd sets one bit, and construct the      */
+  /*     fd_word_map[], fd_byte_map[] and fd_bit_map[].                 */
+  for (fd = 0 ; fd < FD_SETSIZE ; ++fd)
+    {
+      fd_word_t w ;
+
+      FD_SET(fd, &test.fdset) ;
+
+      w = 0 ;
+      for (iw = 0 ; iw < FD_SUPER_SET_WORD_SIZE ; ++iw)
+        {
+          if (test.words[iw] != 0)
+            {
+              if (w != 0)
+                zabort("FD_SET set a bit in more than one word") ;
+
+              w = test.words[iw] ;
+              if ((w == 0) || ((w & (w - 1)) != 0))
+                zabort("FD_SET set more than one bit in a word") ;
+
+              fd_word_map[fd] = iw ;
+
+              ib = iw * FD_WORD_BYTES ;
+              while (test.bytes[ib] == 0)
+                {
+                  ++ib ;
+                  if (ib >= ((iw + 1) * FD_WORD_BYTES))
+                    zabort("FD_SET set something beyond the expected bytes") ;
+                } ;
+              fd_byte_map[fd] = ib ;
+              fd_bit_map[fd]  = test.bytes[ib] ;
+            } ;
+        } ;
+
+        if (w == 0)
+          zabort("FD_SET did not set any bit in any word") ;
+
+      FD_CLR(fd, &test.fdset) ;
+
+      for (iw = 0 ; iw < FD_SUPER_SET_WORD_SIZE ; ++iw)
+        if (test.words[iw] != 0)
+          zabort("FD_CLR did not leave the fd_super_set empty") ;
+    } ;
+
+  /* (4) check the fd_byte_map.                                         */
+  /*     make sure that have  8 contiguous fd to a byte.                */
+  /*     make sure that have 32 contiguous fd to a word.                */
+
+  for (fd = 0 ; fd < FD_SETSIZE ; fd += 8)
+    {
+      int fds ;
+      ib  = fd_byte_map[fd] ;
+      iw  = fd_word_map[fd] ;
+
+      /* Must share the same byte as the next 7 fds                     */
+      for (fds = fd + 1 ; fds < (fd + 8) ; ++fds)
+        if (fd_byte_map[fds] != ib)
+          zabort("Broken fd_byte_map -- not 8 contiguous fd's in a byte") ;
+
+      /* Must not share the same byte as any other set of 8 fd's        */
+      for (fds = 0 ; fds < FD_SETSIZE ; fds += 8)
+        if ((fd_byte_map[fds] == ib) && (fds != fd))
+          zabort("Broken fd_byte_map -- fd's not in expected bytes") ;
+
+      /* Must be one of the bytes in the current word's fd's            */
+      if ( (ib < (iw * FD_WORD_BYTES)) || (ib >= ((iw + 1) * FD_WORD_BYTES)) )
+        zabort("Broken fd_byte_map -- fd's not in expected words") ;
+    } ;
+
+  /* (5) check the fd_bit_map                                           */
+  /*     make sure that all fd mod 8 map to the same byte value         */
+
+  for (i = 0 ; i < 8 ; ++i)
+    {
+      uint8_t b = fd_bit_map[i] ;
+      for (fd = 8 + i ; fd < FD_SETSIZE ; fd += 8)
+        if (fd_bit_map[fd] != b)
+          zabort("Broken fd_bit_map -- inconsistent bit mapping") ;
+    } ;
+
+  /* (6) construct fd_first_map, to get lowest numbered fd (mod 8) from */
+  /*     a given byte value.                                            */
+
+  for (i = 0 ; i < 256 ; ++i)
+    fd_first_map[i] = -1 ;
+
+  for (i = 0 ; i < 8 ; ++i)
+    {
+      uint8_t fdb = fd_bit_map[i] ;
+      uint8_t b ;
+      for (b = 0 ; b < 256 ; ++b)
+        if ((fd_first_map[b] == -1) && ((b & fdb) != 0))
+          fd_first_map[b] = i ;
+    } ;
+
+  /* (7) construct fd_byte_count[] -- number of bytes required to       */
+  /*     include fds 0..fd.                                             */
+
+  i = 0 ;
+  for (fd = 0 ; fd < FD_SETSIZE ; ++fd)
+    {
+      fd_byte_count[fd] = fd_byte_map[fd] + 1 ;
+      if (fd_byte_count[fd] < i)
+        fd_byte_count[fd] = i ;
+      else
+        i = fd_byte_count[fd] ;
+    } ;
+
+  /* Phew -- we're all set now                                          */
+  qps_super_set_map_made = 1 ;
+} ;
+
+/* Zeroise 'n' contiguous fd_super_sets
+ *
+ * NB: this MUST be used in place of FD_ZERO because the fd_set may be shorter
+ *     than the overlayed words/bytes vectors.
+ *
+ * NB: it is CONFIRMED elsewhere that the fd_set is no longer than the overlays.
+ */
+static void
+qps_super_set_zero(fd_super_set* p_set, int n)
+{
+  memset(p_set, 0, SIZE(fd_super_set, n)) ;
+} ;