pollfd_rbhash.h

#ifndef POLLFD_RBHASH_H
#define POLLFD_RBHASH_H
/*
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 <stdint.h> 
#include <stdlib.h> 
#include <stdbool.h> 
#include <assert.h> 
#include <stdio.h> 
#include <string.h> 

/* MAX_TREE_HEIGHT is the maximum number of nodes from root to leaf in any
 * correctly balanced tree.  The exact formula for the maximum height (including
 * root node) is floor(2*log2(N/2+1)) for a tree of N nodes.
 */
#define POLLFD_RBHASH_MAX_ELEMENTS_8       0x7F
#define POLLFD_RBHASH_MAX_TREE_HEIGHT_8      12
#define POLLFD_RBHASH_MAX_ELEMENTS_16    0x7FFF
#define POLLFD_RBHASH_MAX_TREE_HEIGHT_16     28

/* This macro tells you the word offset (treating rbhash as an array of words)
 * of the first hash bucket.
 */
#define POLLFD_RBHASH_TABLE_WORD_OFS(capacity) ( (capacity)*2 + 2 )

/* This macro selects the word size needed to index 'capacity' number of
 * user elements.
 */
#define POLLFD_RBHASH_SIZEOF_WORD(capacity) ( \
           (capacity) <= POLLFD_RBHASH_MAX_ELEMENTS_8? 1 : \
           2 \
        )

/* This macro defines the total size (in bytes) of the rbhash storage
 * for a given number of elements and buckets.  This does not include
 * the user's elements themselves, since those are whatever size the
 * user wants them to be, and rbhash doesn't need to know.
 */
#define POLLFD_RBHASH_SIZEOF(capacity, buckets) ( \
           POLLFD_RBHASH_SIZEOF_WORD(capacity) \
           * ( POLLFD_RBHASH_TABLE_WORD_OFS(capacity) + buckets ) \
        )

/* Several functions can operate on a "path", which is a list of
 * references starting at the bucket and ending at a tree node.
 * The path is allocated to the maximum depth that a tree of that
 * word-bits-size could reach.  Since this drastically affects the
 * amount of stack used, a struct is declared for each word-bit size.
 *
 * The structs each record their length so that they can be passed
 * interchangably to the functions.  You could even allocate custom
 * lengths with alloca, but that seems overcomplicated.
 */
struct pollfd_rbhash_path_8 {
   uint8_t len, lim;
   size_t refs[POLLFD_RBHASH_MAX_TREE_HEIGHT_8];
};

inline void pollfd_rbhash_path_8_init(struct pollfd_rbhash_path_8 *p) {
   p->len= 0;
   p->lim= POLLFD_RBHASH_MAX_TREE_HEIGHT_8;
}

struct pollfd_rbhash_path_16 {
   uint8_t len, lim;
   size_t refs[POLLFD_RBHASH_MAX_TREE_HEIGHT_16];
};

inline void pollfd_rbhash_path_16_init(struct pollfd_rbhash_path_16 *p) {
   p->len= 0;
   p->lim= POLLFD_RBHASH_MAX_TREE_HEIGHT_16;
}


// Different template output may end up with different structs claiming
// the name of pollfd_rbhash_path, but that should be OK.
typedef struct pollfd_rbhash_path_16 pollfd_rbhash_path;
#define pollfd_rbhash_path_init(p) pollfd_rbhash_path_16_init(p)

// Iterate one or more places through the R/B tree of a bucket, updating 'path'
extern size_t pollfd_rbhash_path_step(void *rbhash, size_t capacity, pollfd_rbhash_path *path, int ofs);

// Exchange the tree node of one node_id (at the end of 'path') for another node_id
extern size_t pollfd_rbhash_path_swap(void *rbhash, size_t capacity, pollfd_rbhash_path *path, size_t new_node_id);

// implementation detail used to reduce size of inline functions
extern size_t pollfd_rbhash_capacity_bounds_assertion(size_t capacity);

// Add a node_id at the end of 'path', and balance the tree if needed
extern size_t pollfd_rbhash_path_insert_8(uint8_t *rbhash, pollfd_rbhash_path *path, size_t node_id);
extern size_t pollfd_rbhash_path_insert_16(uint16_t *rbhash, pollfd_rbhash_path *path, size_t node_id);
inline size_t pollfd_rbhash_path_insert(void *rbhash, size_t capacity, pollfd_rbhash_path *path, size_t node) {
   return
      (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8)? pollfd_rbhash_path_insert_8((uint8_t*) rbhash, path, node) :
      (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16)? pollfd_rbhash_path_insert_16((uint16_t*) rbhash, path, node) :
      pollfd_rbhash_capacity_bounds_assertion(capacity);
}

// Remove the node_id from the end of 'path', and balance the tree if needed
extern size_t pollfd_rbhash_path_delete_8(uint8_t *rbhash, pollfd_rbhash_path *path);
extern size_t pollfd_rbhash_path_delete_16(uint16_t *rbhash, pollfd_rbhash_path *path);
inline size_t pollfd_rbhash_path_delete(void *rbhash, size_t capacity, pollfd_rbhash_path *path) {
   return
      (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_8)? pollfd_rbhash_path_delete_8((uint8_t*) rbhash, path) :
      (capacity <= POLLFD_RBHASH_MAX_ELEMENTS_16)? pollfd_rbhash_path_delete_16((uint16_t*) rbhash, path) :
      pollfd_rbhash_capacity_bounds_assertion(capacity);
}

// Find a node_id matching the search criteria and fill in the 'path' to it, else return 0
extern size_t pollfd_rbhash_find_path(void *rbhash, size_t capacity, pollfd_rbhash_path *path, size_t bucket_idx, int search_fd);

// Simplified search for node_id, without building a path
extern size_t pollfd_rbhash_find(void *rbhash, size_t capacity, size_t bucket_idx, int search_fd);

// Insert a node_id, unless one already matches the search criteria
extern size_t pollfd_rbhash_insert(void *rbhash, size_t capacity, size_t node_id, size_t bucket_idx, int search_fd);

// Delete a node matching the search criteria
extern size_t pollfd_rbhash_delete(void *rbhash, size_t capacity, size_t bucket_idx, int search_fd);


// Handy for gdb:
//    p pollfd_rbhash_print(rbhash, capacity, buckets, NULL, NULL, stdout)
extern void pollfd_rbhash_print(void *rbhash, size_t capacity, size_t n_buckets,
   void (*print_node)(void*,size_t,FILE*), void* userdata, FILE *out);

#endif