view release on metacpan or  search on metacpan

src/judy-1.0.5/src/JudyCommon/JudyPrivate.h  view on Meta::CPAN

// LeafLs).  Use Pjlw_t for LeafWs.  Use Pleaf (with type uint8_t *, uint16_t
// *, etc) when the leaf index size is known.

typedef PWord_t Pjlw_t;  // pointer to root-level leaf (whole-word indexes).
typedef Pvoid_t Pjll_t;  // pointer to lower-level linear leaf.

#ifdef JUDYL
typedef PWord_t Pjv_t;   // pointer to JudyL value area.
#endif


// POINTER PREPARATION MACROS:
//
// These macros are used to strip malloc-namespace-type bits from a pointer +
// malloc-type word (which references any Judy mallocd object that might be
// obtained from other than a direct call of malloc()), prior to dereferencing
// the pointer as an address.  The malloc-type bits allow Judy mallocd objects
// to come from different "malloc() namespaces".
//
//    (root pointer)    (JRP, see above)
//    jp.jp_Addr        generic pointer to next-level node, except when used
//                      as a JudyL Immed01 value area
//    JU_JBB_PJP        macro hides jbbs_Pjp (pointer to JP subarray)
//    JL_JLB_PVALUE     macro hides jLlbs_PValue (pointer to value subarray)
//
// When setting one of these fields or passing an address to j__udyFree*(), the
// "raw" memory address is used; otherwise the memory address must be passed
// through one of the macros below before its dereferenced.
//
// Note:  After much study, the typecasts below appear in the macros rather
// than at the point of use, which is both simpler and allows the compiler to
// do type-checking.


#define P_JLW(  ADDR) ((Pjlw_t) (ADDR))  // root leaf.
#define P_JPM(  ADDR) ((Pjpm_t) (ADDR))  // root JPM.
#define P_JBL(  ADDR) ((Pjbl_t) (ADDR))  // BranchL.
#define P_JBB(  ADDR) ((Pjbb_t) (ADDR))  // BranchB.
#define P_JBU(  ADDR) ((Pjbu_t) (ADDR))  // BranchU.
#define P_JLL(  ADDR) ((Pjll_t) (ADDR))  // LeafL.
#define P_JLB(  ADDR) ((Pjlb_t) (ADDR))  // LeafB1.
#define P_JP(   ADDR) ((Pjp_t)  (ADDR))  // JP.

#ifdef JUDYL
#define P_JV(   ADDR) ((Pjv_t)  (ADDR))  // &value.
#endif


// LEAST BYTES:
//
// Mask for least bytes of a word, and a macro to perform this mask on an
// Index.
//
// Note:  This macro has been problematic in the past to get right and to make
// portable.  Its not OK on all systems to shift by the full word size.  This
// macro should allow shifting by 1..N bytes, where N is the word size, but
// should produce a compiler warning if the macro is called with Bytes == 0.
//
// Warning:  JU_LEASTBYTESMASK() is not a constant macro unless Bytes is a
// constant; otherwise it is a variable shift, which is expensive on some
// processors.

#define JU_LEASTBYTESMASK(BYTES) \
        ((0x100UL << (cJU_BITSPERBYTE * ((BYTES) - 1))) - 1)

#define JU_LEASTBYTES(INDEX,BYTES)  ((INDEX) & JU_LEASTBYTESMASK(BYTES))


// BITS IN EACH BITMAP SUBEXPANSE FOR BITMAP BRANCH AND LEAF:
//
// The bits per bitmap subexpanse times the number of subexpanses equals a
// constant (cJU_SUBEXPPERSTATE).  You can also think of this as a compile-time
// choice of "aspect ratio" for bitmap branches and leaves (which can be set
// independently for each).
//
// A default aspect ratio is hardwired here if not overridden at compile time,
// such as by "EXTCCOPTS=-DBITMAP_BRANCH16x16 make".

#if (! (defined(BITMAP_BRANCH8x32) || defined(BITMAP_BRANCH16x16) || defined(BITMAP_BRANCH32x8)))
#define BITMAP_BRANCH32x8 1     // 32 bits per subexpanse, 8 subexpanses.
#endif

#ifdef BITMAP_BRANCH8x32
#define BITMAPB_t uint8_t
#endif

#ifdef BITMAP_BRANCH16x16
#define BITMAPB_t uint16_t
#endif

#ifdef BITMAP_BRANCH32x8
#define BITMAPB_t uint32_t
#endif

// Note:  For bitmap leaves, BITMAP_LEAF64x4 is only valid for 64 bit:
//
// Note:  Choice of aspect ratio mostly matters for JudyL bitmap leaves.  For
// Judy1 the choice doesnt matter much -- the code generated for different
// BITMAP_LEAF* values choices varies, but correctness and performance are the
// same.

#ifndef JU_64BIT

#if (! (defined(BITMAP_LEAF8x32) || defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8)))
#define BITMAP_LEAF32x8         // 32 bits per subexpanse, 8 subexpanses.
#endif

#else // 32BIT

#if (! (defined(BITMAP_LEAF8x32) || defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)))
#define BITMAP_LEAF64x4         // 64 bits per subexpanse, 4 subexpanses.

#endif
#endif // JU_64BIT

#ifdef BITMAP_LEAF8x32
#define BITMAPL_t uint8_t
#endif

#ifdef BITMAP_LEAF16x16
#define BITMAPL_t uint16_t

src/judy-1.0.5/src/JudyCommon/JudyPrivate.h  view on Meta::CPAN

#define JU_JPDCDPOP0(PJP)               \
    ((Word_t)(PJP)->jp_DcdP0[0] << 48 | \
     (Word_t)(PJP)->jp_DcdP0[1] << 40 | \
     (Word_t)(PJP)->jp_DcdP0[2] << 32 | \
     (Word_t)(PJP)->jp_DcdP0[3] << 24 | \
     (Word_t)(PJP)->jp_DcdP0[4] << 16 | \
     (Word_t)(PJP)->jp_DcdP0[5] <<  8 | \
     (Word_t)(PJP)->jp_DcdP0[6])


#define JU_JPSETADT(PJP,ADDR,DCDPOP0,TYPE)                      \
{                                                               \
    (PJP)->jp_Addr     = (ADDR);                                \
    (PJP)->jp_DcdP0[0] = (uint8_t)((Word_t)(DCDPOP0) >> 48);    \
    (PJP)->jp_DcdP0[1] = (uint8_t)((Word_t)(DCDPOP0) >> 40);    \
    (PJP)->jp_DcdP0[2] = (uint8_t)((Word_t)(DCDPOP0) >> 32);    \
    (PJP)->jp_DcdP0[3] = (uint8_t)((Word_t)(DCDPOP0) >> 24);    \
    (PJP)->jp_DcdP0[4] = (uint8_t)((Word_t)(DCDPOP0) >> 16);    \
    (PJP)->jp_DcdP0[5] = (uint8_t)((Word_t)(DCDPOP0) >>  8);    \
    (PJP)->jp_DcdP0[6] = (uint8_t)((Word_t)(DCDPOP0));          \
    (PJP)->jp_Type     = (TYPE);                                \
}

#else   // 32 Bit

#define JU_JPDCDPOP0(PJP)               \
    ((Word_t)(PJP)->jp_DcdP0[0] << 16 | \
     (Word_t)(PJP)->jp_DcdP0[1] <<  8 | \
     (Word_t)(PJP)->jp_DcdP0[2])


#define JU_JPSETADT(PJP,ADDR,DCDPOP0,TYPE)                      \
{                                                               \
    (PJP)->jp_Addr     = (ADDR);                                \
    (PJP)->jp_DcdP0[0] = (uint8_t)((Word_t)(DCDPOP0) >> 16);    \
    (PJP)->jp_DcdP0[1] = (uint8_t)((Word_t)(DCDPOP0) >>  8);    \
    (PJP)->jp_DcdP0[2] = (uint8_t)((Word_t)(DCDPOP0));          \
    (PJP)->jp_Type     = (TYPE);                                \
}

#endif  // 32 Bit

// NUMBER OF BITS IN A BRANCH OR LEAF BITMAP AND SUBEXPANSE:
//
// Note:  cJU_BITSPERBITMAP must be the same as the number of JPs in a branch.

#define cJU_BITSPERBITMAP cJU_SUBEXPPERSTATE

// Bitmaps are accessed in units of "subexpanses":

#define cJU_BITSPERSUBEXPB  (sizeof(BITMAPB_t) * cJU_BITSPERBYTE)
#define cJU_NUMSUBEXPB      (cJU_BITSPERBITMAP / cJU_BITSPERSUBEXPB)

#define cJU_BITSPERSUBEXPL  (sizeof(BITMAPL_t) * cJU_BITSPERBYTE)
#define cJU_NUMSUBEXPL      (cJU_BITSPERBITMAP / cJU_BITSPERSUBEXPL)


// MASK FOR A SPECIFIED BIT IN A BITMAP:
//
// Warning:  If BitNum is a variable, this results in a variable shift that is
// expensive, at least on some processors.  Use with caution.
//
// Warning:  BitNum must be less than cJU_BITSPERWORD, that is, 0 ..
// cJU_BITSPERWORD - 1, to avoid a truncated shift on some machines.
//
// TBD:  Perhaps use an array[32] of masks instead of calculating them.

#define JU_BITPOSMASKB(BITNUM) (1L << ((BITNUM) % cJU_BITSPERSUBEXPB))
#define JU_BITPOSMASKL(BITNUM) (1L << ((BITNUM) % cJU_BITSPERSUBEXPL))


// TEST/SET/CLEAR A BIT IN A BITMAP LEAF:
//
// Test if a byte-sized Digit (portion of Index) has a corresponding bit set in
// a bitmap, or set a byte-sized Digits bit into a bitmap, by looking up the
// correct subexpanse and then checking/setting the correct bit.
//
// Note:  Mask higher bits, if any, for the convenience of the user of this
// macro, in case they pass a full Index, not just a digit.  If the caller has
// a true 8-bit digit, make it of type uint8_t and the compiler should skip the
// unnecessary mask step.

#define JU_SUBEXPL(DIGIT) (((DIGIT) / cJU_BITSPERSUBEXPL) & (cJU_NUMSUBEXPL-1))

#define JU_BITMAPTESTL(PJLB, INDEX)  \
    (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) &  JU_BITPOSMASKL(INDEX))

#define JU_BITMAPSETL(PJLB, INDEX)   \
    (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) |= JU_BITPOSMASKL(INDEX))

#define JU_BITMAPCLEARL(PJLB, INDEX) \
    (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) ^= JU_BITPOSMASKL(INDEX))


// MAP BITMAP BIT OFFSET TO DIGIT:
//
// Given a digit variable to set, a bitmap branch or leaf subexpanse (base 0),
// the bitmap (BITMAP*_t) for that subexpanse, and an offset (Nth set bit in
// the bitmap, base 0), compute the digit (also base 0) corresponding to the
// subexpanse and offset by counting all bits in the bitmap until offset+1 set
// bits are seen.  Avoid expensive variable shifts.  Offset should be less than
// the number of set bits in the bitmap; assert this.
//
// If theres a better way to do this, I dont know what it is.

#define JU_BITMAPDIGITB(DIGIT,SUBEXP,BITMAP,OFFSET)             \
        {                                                       \
            BITMAPB_t bitmap = (BITMAP); int remain = (OFFSET); \
            (DIGIT) = (SUBEXP) * cJU_BITSPERSUBEXPB;            \
                                                                \
            while ((remain -= (bitmap & 1)) >= 0)               \
            {                                                   \
                bitmap >>= 1; ++(DIGIT);                        \
                assert((DIGIT) < ((SUBEXP) + 1) * cJU_BITSPERSUBEXPB); \
            }                                                   \
        }

#define JU_BITMAPDIGITL(DIGIT,SUBEXP,BITMAP,OFFSET)             \
        {                                                       \
            BITMAPL_t bitmap = (BITMAP); int remain = (OFFSET); \
            (DIGIT) = (SUBEXP) * cJU_BITSPERSUBEXPL;            \