view release on metacpan or  search on metacpan

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

// ****************************************************************************
// JUDY1 POINTER (JP) -- RELATED MACROS AND CONSTANTS
// ****************************************************************************

// MAXIMUM POPULATIONS OF LINEAR LEAVES:
//
// Allow up to 2 cache lines per leaf, with N bytes per index.
//
// J_1_MAXB is the maximum number of bytes (sort of) to allocate per leaf.
// ALLOCSIZES is defined here, not there, for single-point control of these key
// definitions.  See JudyTables.c for "TERMINATOR".

#define J_1_MAXB   (sizeof(Word_t) * 32)
#define ALLOCSIZES { 3, 5, 7, 11, 15, 23, 32, 47, 64, TERMINATOR } // in words.
#define cJ1_LEAF1_MAXWORDS  5           // Leaf1 max alloc size in words.

// Under JRP (root-state leaves):
//
// Includes a count (Population) word.
//
// Under JP (non-root-state leaves), which have no count (Population) words:
//
// When a 1-byte index leaf grows above cJ1_LEAF1_MAXPOP1 Indexes (bytes),
// the memory chunk required grows to a size where a bitmap is just as
// efficient, so use a bitmap instead for all greater Populations, on both
// 32-bit and 64-bit systems.  However, on a 32-bit system this occurs upon
// going from 6 to 8 words (24 to 32 bytes) in the memory chunk, but on a
// 64-bit system this occurs upon going from 2 to 4 words (16 to 32 bytes).  It
// would be silly to go from a 15-Index Immediate JP to a 16-Index linear leaf
// to a 17-Index bitmap leaf, so just use a bitmap leaf for 16+ Indexes, which
// means set cJ1_LEAF1_MAXPOP1 to cJ1_IMMED1_MAXPOP1 (15) to cause the
// transition at that point.
//
// Note:  cJ1_LEAF1_MAXPOP1 is not used on 64-bit systems.

#ifndef JU_64BIT // 32-bit

#define cJ1_LEAF1_MAXPOP1    (cJ1_LEAF1_MAXWORDS * cJU_BYTESPERWORD)
#define cJ1_LEAF2_MAXPOP1    (J_1_MAXB / 2)
#define cJ1_LEAF3_MAXPOP1    (J_1_MAXB / 3)
#define cJ1_LEAFW_MAXPOP1    ((J_1_MAXB - cJU_BYTESPERWORD) / cJU_BYTESPERWORD)

#else // 64-bit

// #define cJ1_LEAF1_MAXPOP1                    // no LEAF1 in 64-bit.
#define cJ1_LEAF2_MAXPOP1    (J_1_MAXB / 2)
#define cJ1_LEAF3_MAXPOP1    (J_1_MAXB / 3)
#define cJ1_LEAF4_MAXPOP1    (J_1_MAXB / 4)
#define cJ1_LEAF5_MAXPOP1    (J_1_MAXB / 5)
#define cJ1_LEAF6_MAXPOP1    (J_1_MAXB / 6)
#define cJ1_LEAF7_MAXPOP1    (J_1_MAXB / 7)
#define cJ1_LEAFW_MAXPOP1    ((J_1_MAXB - cJU_BYTESPERWORD) / cJU_BYTESPERWORD)

#endif


// MAXIMUM POPULATIONS OF IMMEDIATE JPs:
//
// These specify the maximum Population of immediate JPs with various Index
// Sizes (== sizes of remaining undecoded Index bits).

#define cJ1_IMMED1_MAXPOP1  ((sizeof(jp_t) - 1) / 1)    // 7 [15].
#define cJ1_IMMED2_MAXPOP1  ((sizeof(jp_t) - 1) / 2)    // 3  [7].
#define cJ1_IMMED3_MAXPOP1  ((sizeof(jp_t) - 1) / 3)    // 2  [5].

#ifdef JU_64BIT
#define cJ1_IMMED4_MAXPOP1  ((sizeof(jp_t) - 1) / 4)    //    [3].
#define cJ1_IMMED5_MAXPOP1  ((sizeof(jp_t) - 1) / 5)    //    [3].
#define cJ1_IMMED6_MAXPOP1  ((sizeof(jp_t) - 1) / 6)    //    [2].
#define cJ1_IMMED7_MAXPOP1  ((sizeof(jp_t) - 1) / 7)    //    [2].
#endif


// ****************************************************************************
// JUDY1 BITMAP LEAF (J1LB) SUPPORT
// ****************************************************************************

#define J1_JLB_BITMAP(Pjlb,Subexp)  ((Pjlb)->j1lb_Bitmap[Subexp])

typedef struct J__UDY1_BITMAP_LEAF
{
        BITMAPL_t j1lb_Bitmap[cJU_NUMSUBEXPL];

} j1lb_t, * Pj1lb_t;


// ****************************************************************************
// 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 Judy1 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_UDY1_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
// Note:  Field names match PJError_t for convenience in macros:
/* 7 */ char       je_Errno;            // one of the enums in Judy.h.
/* 7/8 */ int      je_ErrID;            // often an internal source line number.
/* 8/9 */ Word_t   jpm_TotalMemWords;   // words allocated in array.
} j1pm_t, *Pj1pm_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.  This violates the