view release on metacpan or  search on metacpan

pollfd_rbhash.h  view on Meta::CPAN

#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;
}