pollfd_rbhash.c

/*
Generated by rbhash.cpppp using command

  cpppp -p 'max_bits=16' \
      -p 'namespace=pollfd_rbhash' \
      -p '@default_search_args=('\''int search_fd'\'')' \
      -p 'default_search_cmp=search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd' \
      rbhash.cpppp \
      -o 'public=pollfd_rbhash.h' \
      -o pollfd_rbhash.c

*/

#include "pollfd_rbhash.h"

// A setting that disables all the runtime sanity checks and safeguards
#ifndef POLLFD_RBHASH_RUN_WITH_SCISSORS
#define POLLFD_RBHASH_RUN_WITH_SCISSORS 0
#endif

#ifndef POLLFD_RBHASH_ASSERT
   /* The assertions of this library are fairly important since so much of the
    * implementation is exposed to the rest of the program, so only actually
    * remove the checks if RUN_WITH_SCISSORS is set.
    */
   #if POLLFD_RBHASH_RUN_WITH_SCISSORS
      #define POLLFD_RBHASH_ASSERT(x) (void)0
   #elif defined(NDEBUG)
      #define POLLFD_RBHASH_ASSERT(x) if (!(x)) return 0
   #else
      #define POLLFD_RBHASH_ASSERT(x) assert(x)
   #endif
#endif
void pollfd_rbhash_path_8_init(struct pollfd_rbhash_path_8 *p);
void pollfd_rbhash_path_16_init(struct pollfd_rbhash_path_16 *p);

/* Only called when capacity is out of bounds. Used by the inline bit-selectors. */
extern size_t pollfd_rbhash_capacity_bounds_assertion(size_t capacity) {
   POLLFD_RBHASH_ASSERT(capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16);
   return 0;
}


/* Find a node in the hash table, or tree.  Returns the node_id, or 0 if no
 * nodes match.
 *
 * This is a simplified version of find_path that doesn't keep track of the
 * path through the tree, saving time but not facilitating inserts or deletes.
 */
size_t pollfd_rbhash_find(
   void *rbhash, size_t capacity, size_t bucket_idx,
   int search_fd
) {
   size_t node_id= 0;
   int cmp;
   if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8) {
      node_id= ((uint8_t *)rbhash)[ POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + bucket_idx ] >> 1;
      while (node_id && (cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd))
         node_id= ((uint8_t *)rbhash)[ (node_id<<1) | (cmp < 0? 0 : 1) ] >> 1;
   }
   else if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16) {
      node_id= ((uint16_t *)rbhash)[ POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + bucket_idx ] >> 1;
      while (node_id && (cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd))
         node_id= ((uint16_t *)rbhash)[ (node_id<<1) | (cmp < 0? 0 : 1) ] >> 1;
   }
   else {
      POLLFD_RBHASH_ASSERT(capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16);
   }
   return node_id;
}

/* Find a node in the hash table, and record the path to arrive at the node
 * or the node pointer where it would exist.  The path can be used for
 * inserting or deleting without re-comparing any elements.
 *
 * The path should already have been initialized using `pollfd_rbhash_path_init`.
 */
size_t pollfd_rbhash_find_path(
   void *rbhash, size_t capacity, pollfd_rbhash_path *path, size_t bucket_idx,
   int search_fd
) {
   size_t ref, node_id= 0;
   int cmp, p_i= 0, p_lim= path->lim;
   path->len= 0; // in case POLLFD_RBHASH_ASSERT calls 'return 0'
   POLLFD_RBHASH_ASSERT(p_lim > 0);
   if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8) {
      uint8_t *rbhash_w= (uint8_t*) rbhash;
      path->refs[0]= POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + bucket_idx;
      node_id= rbhash_w[ path->refs[0] ] >> 1;
      while (node_id && (cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd)) {
         ref= (node_id<<1) | (cmp < 0? 0 : 1);
         ++p_i;
         POLLFD_RBHASH_ASSERT(p_i < p_lim);
         path->refs[p_i]= ref;
         node_id= rbhash_w[ref] >> 1;
      }
   }
   else if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16) {
      uint16_t *rbhash_w= (uint16_t*) rbhash;
      path->refs[0]= POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + bucket_idx;
      node_id= rbhash_w[ path->refs[0] ] >> 1;
      while (node_id && (cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd)) {
         ref= (node_id<<1) | (cmp < 0? 0 : 1);
         ++p_i;
         POLLFD_RBHASH_ASSERT(p_i < p_lim);
         path->refs[p_i]= ref;
         node_id= rbhash_w[ref] >> 1;
      }
   }
   else {
      POLLFD_RBHASH_ASSERT(capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16);
   }
   path->len= p_i+1;
   return node_id;
}

/* Insert a node into the hashtable, storing collisions in a tree.
 * If it finds a node with same key, it returns that index and does not insert
 * the new node, else it will insert and return your 'new_node' value.
 * If it returns node 0, you have a corrupted data structure.
 */
extern size_t pollfd_rbhash_insert(
   void *rbhash, size_t capacity, size_t at_node_id, size_t bucket_idx,
   int search_fd
) {
   size_t node_id= 0, ref= POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + bucket_idx;
   int cmp, p_i= 0, p_lim;
   if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8) {
      uint8_t *rbhash_w= (uint8_t*) rbhash;
      node_id= rbhash_w[ref] >> 1;
      if (!node_id) {
         rbhash_w[ref]= at_node_id << 1;
         return at_node_id;
      }
      else {
         struct pollfd_rbhash_path_8 path;
         pollfd_rbhash_path_8_init(&path);
         p_lim= path.lim;
         path.refs[0]= ref;
         do {
            if (!(cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd))
               return node_id;
            ref= (node_id<<1) | (cmp < 0? 0 : 1);
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            path.refs[p_i]= ref;
            node_id= rbhash_w[ref] >> 1;
         } while (node_id);
         node_id= at_node_id;
         // Handle simple case of adding to black parent without invoking balance.
         if (!(rbhash_w[path.refs[p_i-1]] & 1)) {
            rbhash_w[ref]= (node_id << 1) | 1;
            return node_id;
         }
         path.len= p_i+1;
         return pollfd_rbhash_path_insert_8(rbhash_w, (pollfd_rbhash_path*) &path, node_id);
      }
   }
   else if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16) {
      uint16_t *rbhash_w= (uint16_t*) rbhash;
      node_id= rbhash_w[ref] >> 1;
      if (!node_id) {
         rbhash_w[ref]= at_node_id << 1;
         return at_node_id;
      }
      else {
         struct pollfd_rbhash_path_16 path;
         pollfd_rbhash_path_16_init(&path);
         p_lim= path.lim;
         path.refs[0]= ref;
         do {
            if (!(cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd))
               return node_id;
            ref= (node_id<<1) | (cmp < 0? 0 : 1);
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            path.refs[p_i]= ref;
            node_id= rbhash_w[ref] >> 1;
         } while (node_id);
         node_id= at_node_id;
         // Handle simple case of adding to black parent without invoking balance.
         if (!(rbhash_w[path.refs[p_i-1]] & 1)) {
            rbhash_w[ref]= (node_id << 1) | 1;
            return node_id;
         }
         path.len= p_i+1;
         return pollfd_rbhash_path_insert_16(rbhash_w, (pollfd_rbhash_path*) &path, node_id);
      }
   }
   POLLFD_RBHASH_ASSERT(capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16);
   return 0;
}

/* Find and delete a node in the hashtable.  If found, this returns the node_id
 * that was removed.  If not found (or if the data structure is currupt) this
 * returns 0.  It may also return 0 if an assertion fails and you have disabled
 * aborting on assertions.
 */
extern size_t pollfd_rbhash_delete(
   void *rbhash, size_t capacity, size_t bucket_idx,
   int search_fd
) {
   size_t cur= 0, ref= POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + bucket_idx;
   int cmp, p_i= 0, p_lim;
   if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8) {
      uint8_t *rbhash_w= (uint8_t*) rbhash;
      if ((cur= rbhash_w[ref])) {
         struct pollfd_rbhash_path_8 path;
         pollfd_rbhash_path_8_init(&path);
         p_lim= path.lim;
         path.refs[0]= ref;
         
         #define node_id (cur >> 1)
         while ((cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd)) {
         #undef node_id
            ref= (cur|1) ^ (cmp < 0? 1 : 0);
            cur= rbhash_w[ref];
            if (!cur)
               return 0;
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            path.refs[p_i]= ref;
         }
         path.len= p_i+1;
         return pollfd_rbhash_path_delete_8(rbhash_w, (pollfd_rbhash_path*) &path);
      }
   }
   else if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16) {
      uint16_t *rbhash_w= (uint16_t*) rbhash;
      if ((cur= rbhash_w[ref])) {
         struct pollfd_rbhash_path_16 path;
         pollfd_rbhash_path_16_init(&path);
         p_lim= path.lim;
         path.refs[0]= ref;
         
         #define node_id (cur >> 1)
         while ((cmp= search_fd - ((struct pollfd*)rbhash)[(int)node_id-1-(int)capacity].fd)) {
         #undef node_id
            ref= (cur|1) ^ (cmp < 0? 1 : 0);
            cur= rbhash_w[ref];
            if (!cur)
               return 0;
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            path.refs[p_i]= ref;
         }
         path.len= p_i+1;
         return pollfd_rbhash_path_delete_16(rbhash_w, (pollfd_rbhash_path*) &path);
      }
   }
   POLLFD_RBHASH_ASSERT(capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16);
   return 0;
}


/* Given a path to a node, make that path point to a new node assuming that
 * the new node contains the same search key that the old node used to.
 * This is used when moving array elements to a new index where the NodeID
 * would be different.
 *
 * This is a O(1) operation, though building the path probably took O(log N).
 *
 * Returns the NodeID that the path previously ended with, and the path has
 * been modified to end with new_node_id and is still valid.  May return
 * 0 if an assertion fails and you have disabled assertions.
 */
extern size_t pollfd_rbhash_path_swap(
   void *rbhash, size_t capacity, pollfd_rbhash_path *path, size_t new_node_id
) {
   size_t ref;
   /* path must point to a node, and new_node_id must not be the sentinel */
   POLLFD_RBHASH_ASSERT(path->len > 0 && new_node_id);
   if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8) {
      uint8_t *rbhash_w= (uint8_t*) rbhash, prev;
      // It is an error if new_node_id is not already zeroed
      POLLFD_RBHASH_ASSERT(((uint16_t*) rbhash)[new_node_id] == 0);
      // Swap the references
      ref= path->refs[path->len-1];
      prev= rbhash_w[ref];
      rbhash_w[ref]= (new_node_id << 1) | (prev&1);
      ((uint16_t*) rbhash)[new_node_id]= ((uint16_t*) rbhash)[prev>>1];
      // and clear out the 'prev' before returning it
      ((uint16_t*) rbhash)[prev>>1]= 0;
      return prev >> 1;
   }
   else if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16) {
      uint16_t *rbhash_w= (uint16_t*) rbhash, prev;
      // It is an error if new_node_id is not already zeroed
      POLLFD_RBHASH_ASSERT(((uint32_t*) rbhash)[new_node_id] == 0);
      // Swap the references
      ref= path->refs[path->len-1];
      prev= rbhash_w[ref];
      rbhash_w[ref]= (new_node_id << 1) | (prev&1);
      ((uint32_t*) rbhash)[new_node_id]= ((uint32_t*) rbhash)[prev>>1];
      // and clear out the 'prev' before returning it
      ((uint32_t*) rbhash)[prev>>1]= 0;
      return prev >> 1;
   }
   POLLFD_RBHASH_ASSERT(capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16);
   return 0;
}

/* Insert a node_id at the end of a path which points to the Sentinel.
 * The final ref will be updated to point to node_id, and then the tree
 * will be balanced according to the Red/Black algorithm.  The path is
 * destroyed in the process and should not be used after this call.
 * (the path could be updated during balance rotations, but would add
 *  overhead and users are unlikely to need it afterward anyway)
 *
 * Returns the node_id on success, or 0 on an assertion failure if you
 * disabled assertions.
 */
extern size_t pollfd_rbhash_path_insert_8(
   uint8_t *rbhash, pollfd_rbhash_path *path, size_t node_id
) {
   /*
   Legend for deciphering crazy bitwise operations below:
     X_ref            - the index within the rbhash array which holds X
     X= rbhash[X_ref] - an integer of ((node_id << 1) | red)
   i.e. if pos is like a pointer with embedded color information,
   pos_ref is like a pointer to that pointer.
     X & 1            - 1 = red, 0 = black
     X >> 1           - the node_id X is pointing to
   If X_ref is from a tree node (true for all path->refs[i > 0]) then
   the location of the ref also indicates which node it belongs to,
   by virtue of nodes being located at rbhash[node_id*2].
     X_ref >> 1       - the node_id of the parent of X
     X_ref & 1        - true if X is the right-subtree of its parent
     X_ref ^ 1        - a ref to the sibling of X
     X | 1            - the ref to X's node_id's right subtree
     X >> 1 << 1      - the ref to X's node_id's left subtree
     (X|1) ^ 1        - same, maybe optimized if (X|1) is already in a register
     X ^ 1            - a shortcut for one of the above when the color is known
   */
   int p_i= path->len - 1;
   // Empty paths or paths ending with a non-Sentinel reference are invalid.
   POLLFD_RBHASH_ASSERT(path->len > 0 && rbhash[path->refs[p_i]] == 0);
   // Add new_node to the final parent-ref of the path.
   // If p_i is 0, this will be altering the hash bucket.
   rbhash[path->refs[p_i--]]= (node_id << 1) | 1; // and make it red
   // 'pos' will be the parent node of that.
   while (p_i > 0) {
      uint8_t pos_ref= path->refs[p_i--];
      uint8_t pos= rbhash[pos_ref];
      uint8_t parent_ref= path->refs[p_i];
      // if current is a black node, no rotations needed
      if (!(pos & 1))
         break;
      // pos is red, its new child is red, and parent will be black.
      // if the sibling is also red, we can pull down the color black from the parent
      // if not, need a rotation.
      if (!(rbhash[pos_ref^1]&1)) {
         // Sibling is black, need a rotation
         // if the imbalanced child (red node) is on the same side as the parent,
         //  need to rotate those lower nodes to the opposite side in preparation
         //  for the rotation.
         // e.g. if pos_ref is leftward (even) and pos's rightward child (odd) is the red one...
         uint8_t child_ref= pos ^ (pos_ref&1);
         uint8_t child= rbhash[child_ref];
         if (child&1) {
            // rotate pos toward [side] so parent's [side] now points to pos's [otherside]
            // set pos's child-ref to child's [otherside] ref
            uint8_t near_grandchild_ref= child ^ (child_ref&1);
            rbhash[child_ref]= rbhash[near_grandchild_ref];
            // set child's [side] to pos
            rbhash[near_grandchild_ref]= pos;
            pos= child; // keep pos as a red node, soon to become black
            rbhash[pos_ref]= child;
            // parent's [side] has not been updated here, but is about to become 'child'
            child_ref= near_grandchild_ref^1;
            child= rbhash[child_ref];
         }
         // Now we can rotate toward parent to balance the tree.
         rbhash[pos_ref]= child;
         rbhash[child_ref]= pos_ref|1; // = parent, colored red.  simplification of ((pos_ref>>1)<<1)|1
         rbhash[parent_ref]= pos^1; // also make pos black
         // rotation finished, exit.
         break;
      }
      rbhash[pos_ref^1] ^= 1;     // toggle color of sibling
      rbhash[pos_ref]= pos^1;     // toggle color of pos
      rbhash[parent_ref] ^= 1;    // toggle color of parent
      // Now pos is black.
      // Jump twice up the tree so that once again, pos has one red child.
      p_i--;
   }
   // Root of tree is always black
   if (rbhash[path->refs[0]] & 1)
      rbhash[path->refs[0]] ^= 1;
   #if !POLLFD_RBHASH_RUN_WITH_SCISSORS
   // Path is no longer valid, because rotations may have destroyed it.
   path->len= 0;
   #endif
   return node_id;
}
extern size_t pollfd_rbhash_path_insert_16(
   uint16_t *rbhash, pollfd_rbhash_path *path, size_t node_id
) {
   /*
   Legend for deciphering crazy bitwise operations below:
     X_ref            - the index within the rbhash array which holds X
     X= rbhash[X_ref] - an integer of ((node_id << 1) | red)
   i.e. if pos is like a pointer with embedded color information,
   pos_ref is like a pointer to that pointer.
     X & 1            - 1 = red, 0 = black
     X >> 1           - the node_id X is pointing to
   If X_ref is from a tree node (true for all path->refs[i > 0]) then
   the location of the ref also indicates which node it belongs to,
   by virtue of nodes being located at rbhash[node_id*2].
     X_ref >> 1       - the node_id of the parent of X
     X_ref & 1        - true if X is the right-subtree of its parent
     X_ref ^ 1        - a ref to the sibling of X
     X | 1            - the ref to X's node_id's right subtree
     X >> 1 << 1      - the ref to X's node_id's left subtree
     (X|1) ^ 1        - same, maybe optimized if (X|1) is already in a register
     X ^ 1            - a shortcut for one of the above when the color is known
   */
   int p_i= path->len - 1;
   // Empty paths or paths ending with a non-Sentinel reference are invalid.
   POLLFD_RBHASH_ASSERT(path->len > 0 && rbhash[path->refs[p_i]] == 0);
   // Add new_node to the final parent-ref of the path.
   // If p_i is 0, this will be altering the hash bucket.
   rbhash[path->refs[p_i--]]= (node_id << 1) | 1; // and make it red
   // 'pos' will be the parent node of that.
   while (p_i > 0) {
      uint16_t pos_ref= path->refs[p_i--];
      uint16_t pos= rbhash[pos_ref];
      uint16_t parent_ref= path->refs[p_i];
      // if current is a black node, no rotations needed
      if (!(pos & 1))
         break;
      // pos is red, its new child is red, and parent will be black.
      // if the sibling is also red, we can pull down the color black from the parent
      // if not, need a rotation.
      if (!(rbhash[pos_ref^1]&1)) {
         // Sibling is black, need a rotation
         // if the imbalanced child (red node) is on the same side as the parent,
         //  need to rotate those lower nodes to the opposite side in preparation
         //  for the rotation.
         // e.g. if pos_ref is leftward (even) and pos's rightward child (odd) is the red one...
         uint16_t child_ref= pos ^ (pos_ref&1);
         uint16_t child= rbhash[child_ref];
         if (child&1) {
            // rotate pos toward [side] so parent's [side] now points to pos's [otherside]
            // set pos's child-ref to child's [otherside] ref
            uint16_t near_grandchild_ref= child ^ (child_ref&1);
            rbhash[child_ref]= rbhash[near_grandchild_ref];
            // set child's [side] to pos
            rbhash[near_grandchild_ref]= pos;
            pos= child; // keep pos as a red node, soon to become black
            rbhash[pos_ref]= child;
            // parent's [side] has not been updated here, but is about to become 'child'
            child_ref= near_grandchild_ref^1;
            child= rbhash[child_ref];
         }
         // Now we can rotate toward parent to balance the tree.
         rbhash[pos_ref]= child;
         rbhash[child_ref]= pos_ref|1; // = parent, colored red.  simplification of ((pos_ref>>1)<<1)|1
         rbhash[parent_ref]= pos^1; // also make pos black
         // rotation finished, exit.
         break;
      }
      rbhash[pos_ref^1] ^= 1;     // toggle color of sibling
      rbhash[pos_ref]= pos^1;     // toggle color of pos
      rbhash[parent_ref] ^= 1;    // toggle color of parent
      // Now pos is black.
      // Jump twice up the tree so that once again, pos has one red child.
      p_i--;
   }
   // Root of tree is always black
   if (rbhash[path->refs[0]] & 1)
      rbhash[path->refs[0]] ^= 1;
   #if !POLLFD_RBHASH_RUN_WITH_SCISSORS
   // Path is no longer valid, because rotations may have destroyed it.
   path->len= 0;
   #endif
   return node_id;
}

/* Delete a node at the end of a path.  The path must end with a non-Sentinel
 * reference, and must also be allocated to the maximum height of the tree,
 * because the node you want to delete might need to be replaced by a node
 * deeper in the tree.  The tree will be re-balanced using the Red/Black
 * algorithm.  If this is the last node in the tree, it clears the hash bucket.
 *
 * The path is destroyed in the process, as rotations and node-replacement
 * occur.  You may not use the path afterward, even if the function fails.
 * (the path could be updated during balance rotations, but would add
 *  overhead and users are unlikely to need it afterward anyway)
 *
 * Returns the deleted node_id on success, or 0 on an assertion failure if
 * you disabled assertions.
 */
extern size_t pollfd_rbhash_path_delete_8(uint8_t *rbhash, pollfd_rbhash_path *path) {
   // See pollfd_rbhash_path_insert for the notes on the bitwise operations
   uint8_t pos, ch1, ch2, sibling;
   int p_i= path->len-1, p_lim= path->lim;
   size_t *parent_refs= path->refs, ref, pos_ref;
   // Path should be at least 1 element (the bucket root ref)
   POLLFD_RBHASH_ASSERT(path->len >= 1);
   // Read the final ref to find 'pos_ref' and 'pos'
   pos_ref= parent_refs[p_i];
   pos= rbhash[pos_ref];
   // Path must point to a non-sentinel node
   POLLFD_RBHASH_ASSERT(pos != 0);
   // If pos has children, find a leaf to swap with.
   // Then delete this node in the leaf's position.
   // Note that normal red/black would delete the element first, then swap, but if we do that
   // a rotation could change the path->refs putting the node-to-delete somwhere else.
   ch1= rbhash[pos], ch2= rbhash[pos ^ 1];
   if (ch1 || ch2) {
      if (ch1 && ch2) {
         int orig_p_i= p_i;
         uint8_t alt= pos, alt2;
         // Descend one level to the left.
         // The path should always have room for this additional reference if it
         // was allocated to max-tree-height and the tree is actually balanced.
         ++p_i;
         POLLFD_RBHASH_ASSERT(p_i < p_lim);
         parent_refs[p_i]= ref= (pos >> 1 << 1); // go left;
         alt= rbhash[ref]; // either ch1 or ch2, but now we know it's the left one
         // descend as many levels as possible to the right
         while ((alt= rbhash[ref= alt | 1])) {
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            parent_refs[p_i]= ref;
         }
         // 'alt' is the node we swap with.
         alt= rbhash[parent_refs[p_i]];
         // is there one to the left?
         if ((alt2= rbhash[(alt >> 1 << 1)])) {
            POLLFD_RBHASH_ASSERT(alt2 & 1);
            // it is required to be a red leaf, so replace alt with it
            rbhash[parent_refs[p_i]]= alt2 ^ 1;
            ((uint16_t *)rbhash)[alt2 >> 1]= 0;
            // Now substitute this for pos and we're done.
            ((uint16_t *)rbhash)[alt >> 1]= ((uint16_t *)rbhash)[pos >> 1];
            rbhash[pos_ref]= (alt >> 1 << 1) | (pos & 1); // preserve color of pos
            goto done;
         }
         else {
            // swap colors of alt and pos
            alt ^= pos & 1;
            pos ^= alt & 1;
            alt ^= pos & 1;
            ((uint16_t *)rbhash)[alt >> 1]= ((uint16_t *)rbhash)[pos >> 1];
            rbhash[pos_ref]= alt;
            // the parent ref at orig_p_i+1 just changed address, so update that
            // (and this affects the next line if alt was a child of pos)
            parent_refs[orig_p_i + 1]= (alt >> 1 << 1); // was left branch at that point
            pos_ref= parent_refs[p_i];
         }  
      }
      else {
         // Node is black with one child.  Swap with it.
         rbhash[pos_ref]= ((ch1 | ch2) >> 1 << 1); // and make it black
         goto done;
      }
   }
   // Remove it.
   rbhash[pos_ref]= 0;
   // It was a black node with no children.  Now it gets interesting.
   if (!(pos & 1)) {
      // The tree must have the same number of black nodes along any path from root
      // to leaf.  We want to remove a black node, disrupting the number of black
      // nodes along the path from the root to the current leaf.  To correct this,
      // we must either reduce all other paths, or add a black node to the current
      // path.
      // Loop until the current node is red, or until we get to the root node.
      sibling= rbhash[pos_ref ^ 1];
      --p_i; // p_i is now the index of the ref to the parent
      while (p_i >= 0) {
         size_t near_nephew_ref;
         uint8_t near_nephew;
         // If the sibling is red, we are unable to reduce the number of black
         //  nodes in the sibling tree, and we can't increase the number of black
         //  nodes in our tree..  Thus we must do a rotation from the sibling
         //  tree to our tree to give us some extra (red) nodes to play with.
         // This is Case 1 from the text
         if (sibling & 1) {
            // Node is black and sibling is red. Get ref to sibling's near subtree
            near_nephew_ref= (sibling ^ 1) | (pos_ref & 1);
            // sibling is new parent, and now black.
            rbhash[parent_refs[p_i]]= sibling ^ 1;
            // move sibling's child under parent, becoming new sibling (which is black)
            sibling= rbhash[near_nephew_ref];
            rbhash[pos_ref ^ 1]= sibling;
            rbhash[near_nephew_ref]= pos_ref | 1; // former sibling sameside tree = parent, now red
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            parent_refs[p_i] = near_nephew_ref; // insert new parent into list
         }
         // sibling will be black here

         // If the sibling is black and both children are black, we have to
         //  reduce the black node count in the sibling's tree to match ours.
         // This is Case 2a from the text.
         near_nephew_ref= sibling | (pos_ref & 1);
         near_nephew= rbhash[near_nephew_ref];
         if (!((near_nephew|rbhash[near_nephew_ref ^ 1]) & 1)) {
            POLLFD_RBHASH_ASSERT(sibling > 1);
            rbhash[pos_ref ^ 1] |= 1; // change sibling to red
            // Now we move one level up the tree to continue fixing the other branches
            if (p_i < 1)
               break;
            pos_ref= parent_refs[p_i--];
            if (rbhash[pos_ref] & 1) {
               // Now, make the current node black (to fulfill Case 2b)
               rbhash[pos_ref] ^= 1;
               break;
            }
            sibling= rbhash[pos_ref ^ 1];
         }
         else {
            // sibling will be black with 1 or 2 red children here

            // If one of the sibling's children are red, we again can't make the
            //  sibling red to balance the tree at the parent, so we have to do a
            //  rotation.  If the "near" nephew is red and the "far" nephew is
            //  black, we need to rotate that tree away before rotating the
            //  parent toward.
            // After doing a rotation and rearranging a few colors, the effect is
            //  that we maintain the same number of black nodes per path on the far
            //  side of the parent, and we gain a black node on the current side,
            //  so we are done.
            if (near_nephew & 1) {
               // Case 3 from the text, double rotation
               size_t tmp_ref= near_nephew ^ (pos_ref & 1); // near nephew's far child
               rbhash[near_nephew_ref]= rbhash[tmp_ref];
               rbhash[pos_ref ^ 1]= near_nephew;
               rbhash[tmp_ref]= sibling;
               sibling= near_nephew ^ 1; // make it black
               near_nephew_ref= sibling | (pos_ref & 1);
            }
            else
               rbhash[near_nephew_ref ^ 1] ^= 1; // far nephew becomes black
            // now Case 4 from the text
            POLLFD_RBHASH_ASSERT(sibling > 1);
            rbhash[pos_ref ^ 1]= rbhash[near_nephew_ref];
            // parent becomes black, balancing current path
            rbhash[near_nephew_ref]= (pos_ref >> 1 << 1); 
            // Sibling assumes parent's color and position
            rbhash[parent_refs[p_i]]= sibling | (rbhash[parent_refs[p_i]] & 1);
            break;
         }
      }
   }
   done:
   // Ensure root-ref is black
   if (rbhash[parent_refs[0]] & 1)
      rbhash[parent_refs[0]] ^= 1;
   // clean the 'pos' node for future use
   ((uint16_t *)rbhash)[pos >> 1]= 0;
   #if !POLLFD_RBHASH_RUN_WITH_SCISSORS
   // Path is no longer valid, because rotations may have destroyed it.
   path->len= 0;
   #endif
   return pos >> 1;
}
extern size_t pollfd_rbhash_path_delete_16(uint16_t *rbhash, pollfd_rbhash_path *path) {
   // See pollfd_rbhash_path_insert for the notes on the bitwise operations
   uint16_t pos, ch1, ch2, sibling;
   int p_i= path->len-1, p_lim= path->lim;
   size_t *parent_refs= path->refs, ref, pos_ref;
   // Path should be at least 1 element (the bucket root ref)
   POLLFD_RBHASH_ASSERT(path->len >= 1);
   // Read the final ref to find 'pos_ref' and 'pos'
   pos_ref= parent_refs[p_i];
   pos= rbhash[pos_ref];
   // Path must point to a non-sentinel node
   POLLFD_RBHASH_ASSERT(pos != 0);
   // If pos has children, find a leaf to swap with.
   // Then delete this node in the leaf's position.
   // Note that normal red/black would delete the element first, then swap, but if we do that
   // a rotation could change the path->refs putting the node-to-delete somwhere else.
   ch1= rbhash[pos], ch2= rbhash[pos ^ 1];
   if (ch1 || ch2) {
      if (ch1 && ch2) {
         int orig_p_i= p_i;
         uint16_t alt= pos, alt2;
         // Descend one level to the left.
         // The path should always have room for this additional reference if it
         // was allocated to max-tree-height and the tree is actually balanced.
         ++p_i;
         POLLFD_RBHASH_ASSERT(p_i < p_lim);
         parent_refs[p_i]= ref= (pos >> 1 << 1); // go left;
         alt= rbhash[ref]; // either ch1 or ch2, but now we know it's the left one
         // descend as many levels as possible to the right
         while ((alt= rbhash[ref= alt | 1])) {
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            parent_refs[p_i]= ref;
         }
         // 'alt' is the node we swap with.
         alt= rbhash[parent_refs[p_i]];
         // is there one to the left?
         if ((alt2= rbhash[(alt >> 1 << 1)])) {
            POLLFD_RBHASH_ASSERT(alt2 & 1);
            // it is required to be a red leaf, so replace alt with it
            rbhash[parent_refs[p_i]]= alt2 ^ 1;
            ((uint32_t *)rbhash)[alt2 >> 1]= 0;
            // Now substitute this for pos and we're done.
            ((uint32_t *)rbhash)[alt >> 1]= ((uint32_t *)rbhash)[pos >> 1];
            rbhash[pos_ref]= (alt >> 1 << 1) | (pos & 1); // preserve color of pos
            goto done;
         }
         else {
            // swap colors of alt and pos
            alt ^= pos & 1;
            pos ^= alt & 1;
            alt ^= pos & 1;
            ((uint32_t *)rbhash)[alt >> 1]= ((uint32_t *)rbhash)[pos >> 1];
            rbhash[pos_ref]= alt;
            // the parent ref at orig_p_i+1 just changed address, so update that
            // (and this affects the next line if alt was a child of pos)
            parent_refs[orig_p_i + 1]= (alt >> 1 << 1); // was left branch at that point
            pos_ref= parent_refs[p_i];
         }  
      }
      else {
         // Node is black with one child.  Swap with it.
         rbhash[pos_ref]= ((ch1 | ch2) >> 1 << 1); // and make it black
         goto done;
      }
   }
   // Remove it.
   rbhash[pos_ref]= 0;
   // It was a black node with no children.  Now it gets interesting.
   if (!(pos & 1)) {
      // The tree must have the same number of black nodes along any path from root
      // to leaf.  We want to remove a black node, disrupting the number of black
      // nodes along the path from the root to the current leaf.  To correct this,
      // we must either reduce all other paths, or add a black node to the current
      // path.
      // Loop until the current node is red, or until we get to the root node.
      sibling= rbhash[pos_ref ^ 1];
      --p_i; // p_i is now the index of the ref to the parent
      while (p_i >= 0) {
         size_t near_nephew_ref;
         uint16_t near_nephew;
         // If the sibling is red, we are unable to reduce the number of black
         //  nodes in the sibling tree, and we can't increase the number of black
         //  nodes in our tree..  Thus we must do a rotation from the sibling
         //  tree to our tree to give us some extra (red) nodes to play with.
         // This is Case 1 from the text
         if (sibling & 1) {
            // Node is black and sibling is red. Get ref to sibling's near subtree
            near_nephew_ref= (sibling ^ 1) | (pos_ref & 1);
            // sibling is new parent, and now black.
            rbhash[parent_refs[p_i]]= sibling ^ 1;
            // move sibling's child under parent, becoming new sibling (which is black)
            sibling= rbhash[near_nephew_ref];
            rbhash[pos_ref ^ 1]= sibling;
            rbhash[near_nephew_ref]= pos_ref | 1; // former sibling sameside tree = parent, now red
            ++p_i;
            POLLFD_RBHASH_ASSERT(p_i < p_lim);
            parent_refs[p_i] = near_nephew_ref; // insert new parent into list
         }
         // sibling will be black here

         // If the sibling is black and both children are black, we have to
         //  reduce the black node count in the sibling's tree to match ours.
         // This is Case 2a from the text.
         near_nephew_ref= sibling | (pos_ref & 1);
         near_nephew= rbhash[near_nephew_ref];
         if (!((near_nephew|rbhash[near_nephew_ref ^ 1]) & 1)) {
            POLLFD_RBHASH_ASSERT(sibling > 1);
            rbhash[pos_ref ^ 1] |= 1; // change sibling to red
            // Now we move one level up the tree to continue fixing the other branches
            if (p_i < 1)
               break;
            pos_ref= parent_refs[p_i--];
            if (rbhash[pos_ref] & 1) {
               // Now, make the current node black (to fulfill Case 2b)
               rbhash[pos_ref] ^= 1;
               break;
            }
            sibling= rbhash[pos_ref ^ 1];
         }
         else {
            // sibling will be black with 1 or 2 red children here

            // If one of the sibling's children are red, we again can't make the
            //  sibling red to balance the tree at the parent, so we have to do a
            //  rotation.  If the "near" nephew is red and the "far" nephew is
            //  black, we need to rotate that tree away before rotating the
            //  parent toward.
            // After doing a rotation and rearranging a few colors, the effect is
            //  that we maintain the same number of black nodes per path on the far
            //  side of the parent, and we gain a black node on the current side,
            //  so we are done.
            if (near_nephew & 1) {
               // Case 3 from the text, double rotation
               size_t tmp_ref= near_nephew ^ (pos_ref & 1); // near nephew's far child
               rbhash[near_nephew_ref]= rbhash[tmp_ref];
               rbhash[pos_ref ^ 1]= near_nephew;
               rbhash[tmp_ref]= sibling;
               sibling= near_nephew ^ 1; // make it black
               near_nephew_ref= sibling | (pos_ref & 1);
            }
            else
               rbhash[near_nephew_ref ^ 1] ^= 1; // far nephew becomes black
            // now Case 4 from the text
            POLLFD_RBHASH_ASSERT(sibling > 1);
            rbhash[pos_ref ^ 1]= rbhash[near_nephew_ref];
            // parent becomes black, balancing current path
            rbhash[near_nephew_ref]= (pos_ref >> 1 << 1); 
            // Sibling assumes parent's color and position
            rbhash[parent_refs[p_i]]= sibling | (rbhash[parent_refs[p_i]] & 1);
            break;
         }
      }
   }
   done:
   // Ensure root-ref is black
   if (rbhash[parent_refs[0]] & 1)
      rbhash[parent_refs[0]] ^= 1;
   // clean the 'pos' node for future use
   ((uint32_t *)rbhash)[pos >> 1]= 0;
   #if !POLLFD_RBHASH_RUN_WITH_SCISSORS
   // Path is no longer valid, because rotations may have destroyed it.
   path->len= 0;
   #endif
   return pos >> 1;
}
// Handy for gdb: "p pollfd_rbhash_treeprint_8(rbhash, capacity, i, i, NULL, NULL, stdout)"
static size_t pollfd_rbhash_print_tree_8(
   uint8_t *rbhash, uint8_t max_node, uint8_t node, uint8_t mark_node,
   void (*print_node)(void*,size_t,FILE*), void* userdata, FILE * out
) {
   uint8_t node_path[ 1+POLLFD_RBHASH_MAX_TREE_HEIGHT_8 ];
   bool cycle;
   int i, pos, step= 0;
   size_t nodecount= 0;
   if (!node) {
      fputs("(empty tree)\n", out);
      return 0;
   }
   node_path[0]= 0;
   node_path[pos= 1]= node << 1;
   while (node && pos) {
      switch (step) {
      case 0:
         // Check for cycles
         cycle= false;
         for (i= 1; i < pos; i++)
            if ((node_path[i]>>1) == (node_path[pos]>>1))
               cycle= true;
         
         // Proceed down right subtree if possible
         if (!cycle && pos < POLLFD_RBHASH_MAX_TREE_HEIGHT_8
            && node <= max_node && rbhash[(node<<1)|1]
         ) {
            node= rbhash[(node<<1)|1] >> 1;
            node_path[++pos]= node << 1;
            continue;
         }
      case 1:
         // Print tree branches for nodes up until this one
         for (i= 2; i < pos; i++)
            fputs((node_path[i]&1) == (node_path[i+1]&1)? "    " : "   |", out);
         if (pos > 1)
            fputs((node_path[pos]&1)? "   `" : "   ,", out);
         
         // Print content of this node
         fprintf(out, "--%c%c%c #%ld%s ",
            (node == mark_node? '(' : '-'),
            (node > max_node? '!' : (rbhash[ (node_path[pos-1]|1) ^ (node_path[pos]&1) ]&1)? 'R':'B'),
            (node == mark_node? ')' : ' '),
            (long) node,
            cycle? " CYCLE DETECTED"
               : pos >= POLLFD_RBHASH_MAX_TREE_HEIGHT_8? " MAX DEPTH EXCEEDED"
               : node > max_node? " VALUE OUT OF BOUNDS"
               : ""
         );
         if (print_node) print_node(userdata, node, out);
         fputs("\n", out);
         ++nodecount;
         
         // Proceed down left subtree if possible
         if (!cycle && pos < POLLFD_RBHASH_MAX_TREE_HEIGHT_8
            && node <= max_node && rbhash[node<<1]
         ) {
            node= rbhash[node<<1] >> 1;
            node_path[++pos]= (node << 1) | 1;
            step= 0;
            continue;
         }
      case 2:
         // Return to parent
         step= (node_path[pos]&1) + 1;
         node= node_path[--pos] >> 1;
         cycle= false;
      }
   }
   return nodecount;
}
// Handy for gdb: "p pollfd_rbhash_treeprint_16(rbhash, capacity, i, i, NULL, NULL, stdout)"
static size_t pollfd_rbhash_print_tree_16(
   uint16_t *rbhash, uint16_t max_node, uint16_t node, uint16_t mark_node,
   void (*print_node)(void*,size_t,FILE*), void* userdata, FILE * out
) {
   uint16_t node_path[ 1+POLLFD_RBHASH_MAX_TREE_HEIGHT_16 ];
   bool cycle;
   int i, pos, step= 0;
   size_t nodecount= 0;
   if (!node) {
      fputs("(empty tree)\n", out);
      return 0;
   }
   node_path[0]= 0;
   node_path[pos= 1]= node << 1;
   while (node && pos) {
      switch (step) {
      case 0:
         // Check for cycles
         cycle= false;
         for (i= 1; i < pos; i++)
            if ((node_path[i]>>1) == (node_path[pos]>>1))
               cycle= true;
         
         // Proceed down right subtree if possible
         if (!cycle && pos < POLLFD_RBHASH_MAX_TREE_HEIGHT_16
            && node <= max_node && rbhash[(node<<1)|1]
         ) {
            node= rbhash[(node<<1)|1] >> 1;
            node_path[++pos]= node << 1;
            continue;
         }
      case 1:
         // Print tree branches for nodes up until this one
         for (i= 2; i < pos; i++)
            fputs((node_path[i]&1) == (node_path[i+1]&1)? "    " : "   |", out);
         if (pos > 1)
            fputs((node_path[pos]&1)? "   `" : "   ,", out);
         
         // Print content of this node
         fprintf(out, "--%c%c%c #%ld%s ",
            (node == mark_node? '(' : '-'),
            (node > max_node? '!' : (rbhash[ (node_path[pos-1]|1) ^ (node_path[pos]&1) ]&1)? 'R':'B'),
            (node == mark_node? ')' : ' '),
            (long) node,
            cycle? " CYCLE DETECTED"
               : pos >= POLLFD_RBHASH_MAX_TREE_HEIGHT_16? " MAX DEPTH EXCEEDED"
               : node > max_node? " VALUE OUT OF BOUNDS"
               : ""
         );
         if (print_node) print_node(userdata, node, out);
         fputs("\n", out);
         ++nodecount;
         
         // Proceed down left subtree if possible
         if (!cycle && pos < POLLFD_RBHASH_MAX_TREE_HEIGHT_16
            && node <= max_node && rbhash[node<<1]
         ) {
            node= rbhash[node<<1] >> 1;
            node_path[++pos]= (node << 1) | 1;
            step= 0;
            continue;
         }
      case 2:
         // Return to parent
         step= (node_path[pos]&1) + 1;
         node= node_path[--pos] >> 1;
         cycle= false;
      }
   }
   return nodecount;
}

void pollfd_rbhash_print(
   void *rbhash, size_t capacity, size_t n_buckets,
   void (*print_node)(void*,size_t,FILE*), void* userdata, FILE *out
) {
   size_t used= 0, collision= 0, empty=0, i;
   fprintf(out, "# rbhash for capacity=%ld: %ld hash buckets, %ld bytes\n"
                "--------------------\n",
                (long) capacity, (long) n_buckets, (long) POLLFD_RBHASH_SIZEOF(capacity, n_buckets));
   if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8) {
      uint8_t *nodes= (uint8_t*) rbhash;
      uint8_t *table= nodes + POLLFD_RBHASH_TABLE_WORD_OFS(capacity);
      for (i= 0; i < n_buckets; i++) {
         if (table[i]) {
            if (empty) {
               fprintf(out, "(%ld empty buckets)\n", (long) empty);
               empty= 0;
            }
            ++used;
            collision += pollfd_rbhash_print_tree_8(rbhash, capacity, table[i]>>1, 0, print_node, userdata, out) - 1;
         } else
            ++empty;
      }
      if (empty) {
         fprintf(out, "(%ld empty buckets)\n", (long) empty);
         empty= 0;
      }
   }
   else if (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16) {
      uint16_t *nodes= (uint16_t*) rbhash;
      uint16_t *table= nodes + POLLFD_RBHASH_TABLE_WORD_OFS(capacity);
      for (i= 0; i < n_buckets; i++) {
         if (table[i]) {
            if (empty) {
               fprintf(out, "(%ld empty buckets)\n", (long) empty);
               empty= 0;
            }
            ++used;
            collision += pollfd_rbhash_print_tree_16(rbhash, capacity, table[i]>>1, 0, print_node, userdata, out) - 1;
         } else
            ++empty;
      }
      if (empty) {
         fprintf(out, "(%ld empty buckets)\n", (long) empty);
         empty= 0;
      }
   }
   fprintf(out, "--------------------\n"
                "# used %ld/%ld buckets, %ld collisions\n",
                (long) used, (long) n_buckets, (long) collision);
}