view release on metacpan or  search on metacpan

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

#endif // 64-bit


// MAXIMUM POPULATIONS OF IMMEDIATE JPs:
//
// These specify the maximum Population of immediate JPs with various Index
// Sizes (== sizes of remaining undecoded Index bits).  Since the JP Types enum
// already lists all the immediates in order by state and size, calculate these
// values from it to avoid redundancy.

#define cJL_IMMED1_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 1)        // 3 [7].
#define cJL_IMMED2_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 2)        // 1 [3].
#define cJL_IMMED3_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 3)        // 1 [2].

#ifdef JU_64BIT
#define cJL_IMMED4_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 4)        //   [1].
#define cJL_IMMED5_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 5)        //   [1].
#define cJL_IMMED6_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 6)        //   [1].
#define cJL_IMMED7_MAXPOP1  ((cJU_BYTESPERWORD - 1) / 7)        //   [1].
#endif


// ****************************************************************************
// JUDYL LEAF BITMAP (JLLB) SUPPORT
// ****************************************************************************
//
// Assemble bitmap leaves out of smaller units that put bitmap subexpanses
// close to their associated pointers.  Why not just use a bitmap followed by a
// series of pointers?  (See 4.27.)  Turns out this wastes a cache fill on
// systems with smaller cache lines than the assumed value cJU_WORDSPERCL.

#define JL_JLB_BITMAP(Pjlb, Subexp)  ((Pjlb)->jLlb_jLlbs[Subexp].jLlbs_Bitmap)
#define JL_JLB_PVALUE(Pjlb, Subexp)  ((Pjlb)->jLlb_jLlbs[Subexp].jLlbs_PValue)

typedef struct J__UDYL_LEAF_BITMAP_SUBEXPANSE
{
        BITMAPL_t jLlbs_Bitmap;
        Pjv_t     jLlbs_PValue;

} jLlbs_t;

typedef struct J__UDYL_LEAF_BITMAP
{
        jLlbs_t jLlb_jLlbs[cJU_NUMSUBEXPL];

} jLlb_t, * PjLlb_t;

// Words per bitmap leaf:

#define cJL_WORDSPERLEAFB1  (sizeof(jLlb_t) / cJU_BYTESPERWORD)


// ****************************************************************************
// MEMORY ALLOCATION SUPPORT
// ****************************************************************************

// ARRAY-GLOBAL INFORMATION:
//
// At the cost of an occasional additional cache fill, this object, which is
// pointed at by a JRP and in turn points to a JP_BRANCH*, carries array-global
// information about a JudyL array that has sufficient population to amortize
// the cost.  The jpm_Pop0 field prevents having to add up the total population
// for the array in insert, delete, and count code.  The jpm_JP field prevents
// having to build a fake JP for entry to a state machine; however, the
// jp_DcdPopO field in jpm_JP, being one byte too small, is not used.
//
// Note:  Struct fields are ordered to keep "hot" data in the first 8 words
// (see left-margin comments) for machines with 8-word cache lines, and to keep
// sub-word fields together for efficient packing.

typedef struct J_UDYL_POPULATION_AND_MEMORY
{
/* 1 */ Word_t     jpm_Pop0;            // total population-1 in array.
/* 2 */ jp_t       jpm_JP;              // JP to first branch; see above.
/* 4 */ Word_t     jpm_LastUPop0;       // last jpm_Pop0 when convert to BranchU
/* 7 */ Pjv_t      jpm_PValue;          // pointer to value to return.
// Note:  Field names match PJError_t for convenience in macros:
/* 8 */ char       je_Errno;            // one of the enums in Judy.h.
/* 8/9  */ int     je_ErrID;            // often an internal source line number.
/* 9/10 */ Word_t  jpm_TotalMemWords;   // words allocated in array.
} jLpm_t, *PjLpm_t;


// TABLES FOR DETERMINING IF LEAVES HAVE ROOM TO GROW:
//
// These tables indicate if a given memory chunk can support growth of a given
// object into wasted (rounded-up) memory in the chunk.  Note:  This violates
// the hiddenness of the JudyMalloc code.

extern const uint8_t j__L_Leaf1PopToWords[cJL_LEAF1_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf2PopToWords[cJL_LEAF2_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf3PopToWords[cJL_LEAF3_MAXPOP1 + 1];
#ifdef JU_64BIT
extern const uint8_t j__L_Leaf4PopToWords[cJL_LEAF4_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf5PopToWords[cJL_LEAF5_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf6PopToWords[cJL_LEAF6_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf7PopToWords[cJL_LEAF7_MAXPOP1 + 1];
#endif
extern const uint8_t j__L_LeafWPopToWords[cJL_LEAFW_MAXPOP1 + 1];
extern const uint8_t j__L_LeafVPopToWords[];

// These tables indicate where value areas start:

extern const uint8_t j__L_Leaf1Offset    [cJL_LEAF1_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf2Offset    [cJL_LEAF2_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf3Offset    [cJL_LEAF3_MAXPOP1 + 1];
#ifdef JU_64BIT
extern const uint8_t j__L_Leaf4Offset    [cJL_LEAF4_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf5Offset    [cJL_LEAF5_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf6Offset    [cJL_LEAF6_MAXPOP1 + 1];
extern const uint8_t j__L_Leaf7Offset    [cJL_LEAF7_MAXPOP1 + 1];
#endif
extern const uint8_t j__L_LeafWOffset    [cJL_LEAFW_MAXPOP1 + 1];

// Also define macros to hide the details in the code using these tables.

#define JL_LEAF1GROWINPLACE(Pop1) \
        J__U_GROWCK(Pop1, cJL_LEAF1_MAXPOP1, j__L_Leaf1PopToWords)
#define JL_LEAF2GROWINPLACE(Pop1) \
        J__U_GROWCK(Pop1, cJL_LEAF2_MAXPOP1, j__L_Leaf2PopToWords)