libcoveb: bigmac.h Source File

00001 /*
00002  * coveb : An open source van Emde Boas Priority Queue library
00003  * by Rudi Cilibrasi (cilibrar@cilibrar.com)
00004  *
00005  * Distributed under the BSD license.  Copyright 2008 Rudi Cilibrasi.
00006  *
00007  * v 0.71
00008  *
00009  * Uses stratified trees inspired by van Emde Boas to hold a priority queue
00010  * of unsigned 32-bit integer values.  Standard operations are supported.
00011  */
00012 
00013 #ifndef __COVEB_BIGMAC_H
00014 #define __COVEB_BIGMAC_H
00015 
00016 /* Bit manipulation macros */
00017 #define get_fullbitsize(s) (s->t._fullbitsize)
00018 #define is_single(s) (s->t._size == 1)
00019 #define bpcrec(blocksize) (32 + 450 * (blocksize <= 0x00001000))
00020 #define direct_table_contains(v,x) ((v->_bits >> x) & 0x01)
00021 
00022 #define TOP_K_FROM_K(k) (k > 8 ? (k >> 1) : 3)
00023 #define BOT_K_FROM_K(k) (k > 8 ? (k >> 1) : 5)
00024 
00025 #define TOP_IS_DIRECT(k) (k <= 2*MAXDIRECTK)
00026 #define BOT_IS_DIRECT(k) (k <= 2*MAXDIRECTK)
00027 
00028 #define GET_DIRECT(n) ((struct vEBSimpleBitTable *)&n)
00029 
00030 #define TOP_CONTAINS(v, x) (TOP_IS_DIRECT(get_fullbitsize(v)) ?  \
00031     direct_table_contains(GET_DIRECT(v->fn._top), x) :           \
00032     coveb__ibq_contains(v->fn._top, x))
00033 
00034 #define TOP_SIZE(v) (TOP_IS_DIRECT(get_fullbitsize(v)) ? \
00035     direct_table_size(GET_DIRECT(v->fn._top)) :          \
00036     coveb__ibq_size(v->fn._top))
00037 
00038 #define TOP_EXTRACTMIN(v) (TOP_IS_DIRECT(get_fullbitsize(v)) ? \
00039     direct_table_extractmin(GET_DIRECT(v->fn._top)) :          \
00040     coveb__ibq_extractmin(v->fn._top))
00041 
00042 #define TOP_MIN(v) (TOP_IS_DIRECT(get_fullbitsize(v)) ? \
00043     direct_table_min(GET_DIRECT(v->fn._top)) :          \
00044     coveb__ibq_min(v->fn._top))
00045 
00046 #define BOT_REMOVE(v, ind, x) do { if (BOT_IS_DIRECT(get_fullbitsize(v))) \
00047       direct_table_remove(GET_DIRECT(v->fn._bot[ind]), x);                \
00048      else                                                                 \
00049       coveb__ibq_remove(v->fn._bot[ind], x); } while (0)
00050 
00051 #define TOP_REMOVE(v, x) do { if (TOP_IS_DIRECT(get_fullbitsize(v))) \
00052       direct_table_remove(GET_DIRECT(v->fn._top), x);                \
00053      else                                                            \
00054       coveb__ibq_remove(v->fn._top, x); } while (0)
00055 
00056 #define TOP_INSERT(v, x) do { if (TOP_IS_DIRECT(get_fullbitsize(v))) \
00057       direct_table_insert(GET_DIRECT(v->fn._top), x);                \
00058     else                                                             \
00059       coveb__ibq_insert(v->fn._top, x); } while(0)
00060 
00061 #define TOP_LOCATESNLT(v, lb, rx, gr) do {                                    \
00062 if (TOP_IS_DIRECT(get_fullbitsize(v)))                                        \
00063   direct_table_locate_smallest_not_less_than(GET_DIRECT(v->fn._top),lb,rx,gr);\
00064 else                                                                          \
00065   coveb__ibq_locate_smallest_not_less_than(v->fn._top,lb,rx,gr); } while (0)
00066 
00067 #define BOT_LOCATESNLT(v, ind, lb, rx, gr) do { \
00068 if (BOT_IS_DIRECT(get_fullbitsize(v)))          \
00069   direct_table_locate_smallest_not_less_than(   \
00070   GET_DIRECT(v->fn._bot[ind]),lb,rx,gr);        \
00071 else                                            \
00072   coveb__ibq_locate_smallest_not_less_than(     \
00073   v->fn._bot[ind],lb,rx,gr); } while (0)
00074 
00075 #define BOT_CONTAINS(v, ind, x) (v->fn._bot[ind] != 0 &&      \
00076                         (BOT_IS_DIRECT(get_fullbitsize(v)) ?  \
00077     direct_table_contains(GET_DIRECT(v->fn._bot[ind]), x) :   \
00078     coveb__ibq_contains(v->fn._bot[ind], x)))
00079 
00080 #define BOT_SIZE(v, ind) (BOT_IS_DIRECT(get_fullbitsize(v)) ? \
00081     direct_table_size(GET_DIRECT(v->fn._bot[ind])) :          \
00082     coveb__ibq_size(v->fn._bot[ind]))
00083 
00084 #define BOT_EXTRACTMIN(v, ind) (BOT_IS_DIRECT(get_fullbitsize(v)) ? \
00085     direct_table_extractmin(GET_DIRECT(v->fn._bot[ind])) :          \
00086     coveb__ibq_extractmin(v->fn._bot[ind]))
00087 
00088 #define BOT_MIN(v, ind) (BOT_IS_DIRECT(get_fullbitsize(v)) ? \
00089     direct_table_min(GET_DIRECT(v->fn._bot[ind])) :          \
00090     coveb__ibq_min(v->fn._bot[ind]))
00091 
00092 #define BOT_INSERT(v, ind, x) do { if (BOT_IS_DIRECT(get_fullbitsize(v))) \
00093     direct_table_insert(GET_DIRECT(v->fn._bot[ind]), x);                  \
00094   else                                                                    \
00095     coveb__ibq_insert(v->fn._bot[ind], x); } while(0)
00096 
00097 #define PAYLOAD_BITS(v) ( v->t._payload_bits_minus_one + 1 )
00098 #endif