bigmac.h

/*
 * coveb : An open source van Emde Boas Priority Queue library
 * by Rudi Cilibrasi (cilibrar@cilibrar.com)
 *
 * Distributed under the BSD license.  Copyright 2008 Rudi Cilibrasi.
 *
 * v 0.71
 *
 * Uses stratified trees inspired by van Emde Boas to hold a priority queue
 * of unsigned 32-bit integer values.  Standard operations are supported.
 */

#ifndef __COVEB_BIGMAC_H
#define __COVEB_BIGMAC_H

/* Bit manipulation macros */
#define get_fullbitsize(s) (s->t._fullbitsize)
#define is_single(s) (s->t._size == 1)
#define bpcrec(blocksize) (32 + 450 * (blocksize <= 0x00001000))
#define direct_table_contains(v,x) ((v->_bits >> x) & 0x01)

#define TOP_K_FROM_K(k) (k > 8 ? (k >> 1) : 3)
#define BOT_K_FROM_K(k) (k > 8 ? (k >> 1) : 5)

#define TOP_IS_DIRECT(k) (k <= 2*MAXDIRECTK)
#define BOT_IS_DIRECT(k) (k <= 2*MAXDIRECTK)

#define GET_DIRECT(n) ((struct vEBSimpleBitTable *)&n)

#define TOP_CONTAINS(v, x) (TOP_IS_DIRECT(get_fullbitsize(v)) ?  \
    direct_table_contains(GET_DIRECT(v->fn._top), x) :           \
    coveb__ibq_contains(v->fn._top, x))

#define TOP_SIZE(v) (TOP_IS_DIRECT(get_fullbitsize(v)) ? \
    direct_table_size(GET_DIRECT(v->fn._top)) :          \
    coveb__ibq_size(v->fn._top))

#define TOP_EXTRACTMIN(v) (TOP_IS_DIRECT(get_fullbitsize(v)) ? \
    direct_table_extractmin(GET_DIRECT(v->fn._top)) :          \
    coveb__ibq_extractmin(v->fn._top))

#define TOP_MIN(v) (TOP_IS_DIRECT(get_fullbitsize(v)) ? \
    direct_table_min(GET_DIRECT(v->fn._top)) :          \
    coveb__ibq_min(v->fn._top))

#define BOT_REMOVE(v, ind, x) do { if (BOT_IS_DIRECT(get_fullbitsize(v))) \
      direct_table_remove(GET_DIRECT(v->fn._bot[ind]), x);                \
     else                                                                 \
      coveb__ibq_remove(v->fn._bot[ind], x); } while (0)

#define TOP_REMOVE(v, x) do { if (TOP_IS_DIRECT(get_fullbitsize(v))) \
      direct_table_remove(GET_DIRECT(v->fn._top), x);                \
     else                                                            \
      coveb__ibq_remove(v->fn._top, x); } while (0)

#define TOP_INSERT(v, x) do { if (TOP_IS_DIRECT(get_fullbitsize(v))) \
      direct_table_insert(GET_DIRECT(v->fn._top), x);                \
    else                                                             \
      coveb__ibq_insert(v->fn._top, x); } while(0)

#define TOP_LOCATESNLT(v, lb, rx, gr) do {                                    \
if (TOP_IS_DIRECT(get_fullbitsize(v)))                                        \
  direct_table_locate_smallest_not_less_than(GET_DIRECT(v->fn._top),lb,rx,gr);\
else                                                                          \
  coveb__ibq_locate_smallest_not_less_than(v->fn._top,lb,rx,gr); } while (0)

#define BOT_LOCATESNLT(v, ind, lb, rx, gr) do { \
if (BOT_IS_DIRECT(get_fullbitsize(v)))          \
  direct_table_locate_smallest_not_less_than(   \
  GET_DIRECT(v->fn._bot[ind]),lb,rx,gr);        \
else                                            \
  coveb__ibq_locate_smallest_not_less_than(     \
  v->fn._bot[ind],lb,rx,gr); } while (0)

#define BOT_CONTAINS(v, ind, x) (v->fn._bot[ind] != 0 &&      \
                        (BOT_IS_DIRECT(get_fullbitsize(v)) ?  \
    direct_table_contains(GET_DIRECT(v->fn._bot[ind]), x) :   \
    coveb__ibq_contains(v->fn._bot[ind], x)))

#define BOT_SIZE(v, ind) (BOT_IS_DIRECT(get_fullbitsize(v)) ? \
    direct_table_size(GET_DIRECT(v->fn._bot[ind])) :          \
    coveb__ibq_size(v->fn._bot[ind]))

#define BOT_EXTRACTMIN(v, ind) (BOT_IS_DIRECT(get_fullbitsize(v)) ? \
    direct_table_extractmin(GET_DIRECT(v->fn._bot[ind])) :          \
    coveb__ibq_extractmin(v->fn._bot[ind]))

#define BOT_MIN(v, ind) (BOT_IS_DIRECT(get_fullbitsize(v)) ? \
    direct_table_min(GET_DIRECT(v->fn._bot[ind])) :          \
    coveb__ibq_min(v->fn._bot[ind]))

#define BOT_INSERT(v, ind, x) do { if (BOT_IS_DIRECT(get_fullbitsize(v))) \
    direct_table_insert(GET_DIRECT(v->fn._bot[ind]), x);                  \
  else                                                                    \
    coveb__ibq_insert(v->fn._bot[ind], x); } while(0)

#define PAYLOAD_BITS(v) ( v->t._payload_bits_minus_one + 1 )
#endif

---