view release on metacpan or  search on metacpan

rbhash.cpppp  view on Meta::CPAN

## param $feature_print= 1;
## param $feature_demo= 0;
## param $run_with_scissors= 0;
## param @public_includes = (
##   qw( <stdint.h> <stdlib.h> <stdbool.h> <assert.h> ),
##   qw( <stdio.h> <string.h> )x!!($feature_print || $feature_demo)
## );
## param @private_includes = qw( "rbhash.h" );

## my $NAMESPACE= uc($namespace);
## my @bits= map +(1<<$_), (log($min_bits)/log(2)) .. (log($max_bits)/log(2));
## sub log2($x) { log($x)/log(2) }
## sub word_type($bits) { 'uint'.$bits.'_t' }

## section PUBLIC;
## use CodeGen::Cpppp::Template "format_commandline";

/*
Generated by rbhash.cpppp using command

  ${{ format_commandline }}

*/

#include $_  ## for @public_includes

## section PRIVATE;

/*
Generated by rbhash.cpppp using command

  ${{ format_commandline }}

*/

#include $_  ## for @private_includes

// A setting that disables all the runtime sanity checks and safeguards
#ifndef ${NAMESPACE}_RUN_WITH_SCISSORS
#define ${NAMESPACE}_RUN_WITH_SCISSORS $run_with_scissors
#endif

#ifndef ${NAMESPACE}_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 ${NAMESPACE}_RUN_WITH_SCISSORS
      #define ${NAMESPACE}_ASSERT(x) (void)0
   #elif defined(NDEBUG)
      #define ${NAMESPACE}_ASSERT(x) if (!(x)) return 0
   #else
      #define ${NAMESPACE}_ASSERT(x) assert(x)
   #endif
#endif
## my $assert= "${NAMESPACE}_ASSERT";

## section PUBLIC;

/* 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.
 */
## for my $bits (@bits) {
#define ${NAMESPACE}_MAX_ELEMENTS_$bits     0x${{ sprintf "%X", (1<<($bits-1))-1 }}
#define ${NAMESPACE}_MAX_TREE_HEIGHT_$bits  ${{ int(2*log2((2**($bits-1)-1)/2+1)) }}
## }

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

/* This macro selects the word size needed to index 'capacity' number of
 * user elements.
 */
#define ${NAMESPACE}_SIZEOF_WORD(capacity) ( \
## for my $bits (@bits) {
##   if ($bits < $max_bits) {
           (capacity) <= ${NAMESPACE}_MAX_ELEMENTS_$bits? ${{ $bits/8 }} : \
##   } else {
           ${{ $bits/8 }} \
##   }
## }
        )

/* 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 ${NAMESPACE}_SIZEOF(capacity, buckets) ( \
           ${NAMESPACE}_SIZEOF_WORD(capacity) \
           * ( ${NAMESPACE}_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.
 */
## for my $bits (@bits) {
struct ${namespace}_path_${bits} {
   uint8_t len, lim;
   size_t refs[${NAMESPACE}_MAX_TREE_HEIGHT_${bits}];
};
## section PRIVATE;
void ${namespace}_path_${bits}_init(struct ${namespace}_path_${bits} *p);
## section PUBLIC;

inline void ${namespace}_path_${bits}_init(struct ${namespace}_path_${bits} *p) {
   p->len= 0;
   p->lim= ${NAMESPACE}_MAX_TREE_HEIGHT_${bits};
}

## }