Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
// HANDLE SMALL COUNT (= POP1):
//
// First ensure indexes are in sorted order:
for (offset = 1; offset < Count; ++offset)
{
if (PIndex[offset - 1] >= PIndex[offset])
{ JU_SET_ERRNO(PJError, JU_ERRNO_UNSORTED); return(JERRI); }
}
if (Count == 0) return(1); // *PPArray remains null.
{
Pjlw = j__udyAllocJLW(Count + 1);
JU_CHECKALLOC(Pjlw_t, Pjlw, JERRI);
*PPArray = (Pvoid_t) Pjlw;
Pjlw[0] = Count - 1; // set pop0.
Pjlwindex = Pjlw + 1;
}
// Copy whole-word indexes (and values) to the root-level leaf:
JU_COPYMEM(Pjlwindex, PIndex, Count);
JUDYLCODE(JU_COPYMEM(JL_LEAFWVALUEAREA(Pjlw, Count), PValue, Count));
DBGCODE(JudyCheckPop(*PPArray);)
return(1);
} // Judy1SetArray() / JudyLInsArray()
// ****************************************************************************
// __ J U D Y I N S A R R A Y
//
// Given:
//
// - a pointer to a JP
//
// - the JPs level in the tree, that is, the number of digits left to decode
// in the indexes under the JP (one less than the level of the JPM or branch
// in which the JP resides); cJU_ROOTSTATE on first entry (when JP is the one
// in the JPM), down to 1 for a Leaf1, LeafB1, or FullPop
//
// - a pointer to the number of indexes (and corresponding values) to store in
// this subtree, to modify in case of partial success
//
// - a list of indexes (and for JudyL, corresponding values) to store in this
// subtree
//
// - a JPM for tracking memory usage and returning errors
//
// Recursively build a subtree (immediate indexes, leaf, or branch with
// subtrees) and modify the JP accordingly. On the way down, build a BranchU
// (only) for any expanse with *PPop1 too high for a leaf; on the way out,
// convert the BranchU to a BranchL or BranchB if appropriate. Keep memory
// statistics in the JPM.
//
// Return TRUE for success, or FALSE with error information set in the JPM in
// case of error, in which case leave a partially constructed but healthy tree,
// and modify parent population counts on the way out.
//
// Note: Each call of this function makes all modifications to the PjpParent
// it receives; neither the parent nor child calls do this.
FUNCTION static bool_t j__udyInsArray(
Pjp_t PjpParent, // parent JP in/under which to store.
int Level, // initial digits remaining to decode.
PWord_t PPop1, // number of indexes to store.
PWord_t PIndex, // list of indexes to store.
#ifdef JUDYL
Pjv_t PValue, // list of corresponding values.
#endif
Pjpm_t Pjpm) // for memory and errors.
{
Pjp_t Pjp; // lower-level JP.
Word_t Pjbany; // any type of branch.
int levelsub; // actual, of Pjps node, <= Level.
Word_t pop1 = *PPop1; // fast local value.
Word_t pop1sub; // population of one subexpanse.
uint8_t JPtype; // current JP type.
uint8_t JPtype_null; // precomputed value for new branch.
jp_t JPnull; // precomputed for speed.
Pjbu_t PjbuRaw; // constructed BranchU.
Pjbu_t Pjbu;
int digit; // in BranchU.
Word_t digitmask; // for a digit in a BranchU.
Word_t digitshifted; // shifted to correct offset.
Word_t digitshincr; // increment for digitshifted.
int offset; // in PIndex, or a bitmap subexpanse.
int numJPs; // number non-null in a BranchU.
bool_t retval; // to return from this func.
JUDYLCODE(Pjv_t PjvRaw); // destination value area.
JUDYLCODE(Pjv_t Pjv);
// MACROS FOR COMMON CODE:
//
// Note: These use function and local parameters from the context.
// Note: Assume newly allocated memory is zeroed.
// Indicate whether a sorted list of indexes in PIndex, based on the first and
// last indexes in the list using pop1, are in the same subexpanse between
// Level and L_evel:
//
// This can be confusing! Note that SAMESUBEXP(L) == TRUE means the indexes
// are the same through level L + 1, and it says nothing about level L and
// lower; they might be the same or they might differ.
//
// Note: In principle SAMESUBEXP needs a mask for the digits from Level,
// inclusive, to L_evel, exclusive. But in practice, since the indexes are all
// known to be identical above Level, it just uses a mask for the digits
// through L_evel + 1; see subexp_mask[].
#define SAMESUBEXP(L_evel) \
(! ((PIndex[0] ^ PIndex[pop1 - 1]) & subexp_mask[L_evel]))
// Set PjpParent to a null JP appropriate for the level of the node to which it
// points, which is 1 less than the level of the node in which the JP resides,
// which is by definition Level:
//
// Note: This can set the JPMs JP to an invalid jp_Type, but it doesnt
// matter because the JPM is deleted by the caller.
#define SETJPNULL_PARENT \
JU_JPSETADT(PjpParent, 0, 0, cJU_JPNULL1 + Level - 1);
// Variation to set a specified JP (in a branch being built) to a precomputed
// null JP:
#define SETJPNULL(Pjp) *(Pjp) = JPnull
// Handle complete (as opposed to partial) memory allocation failure: Set the
// parent JP to an appropriate null type (to leave a consistent tree), zero the
// callers population count, and return FALSE:
//
// Note: At Level == cJU_ROOTSTATE this sets the JPMs JPs jp_Type to a bogus
// value, but it doesnt matter because the JPM should be deleted by the
// caller.
#define NOMEM { SETJPNULL_PARENT; *PPop1 = 0; return(FALSE); }
// Allocate a Leaf1-N and save the address in Pjll; in case of failure, NOMEM:
#define ALLOCLEAF(AllocLeaf) \
if ((PjllRaw = AllocLeaf(pop1, Pjpm)) == (Pjll_t) NULL) NOMEM; \
Pjll = P_JLL(PjllRaw);
// Copy indexes smaller than words (and values which are whole words) from
// given arrays to immediate indexes or a leaf:
//
// TBD: These macros overlap with some of the code in JudyCascade.c; do some
// merging? That file has functions while these are macros.
#define COPYTOLEAF_EVEN_SUB(Pjll,LeafType) \
{ \
LeafType * P_leaf = (LeafType *) (Pjll); \
Word_t p_op1 = pop1; \
PWord_t P_Index = PIndex; \
\
assert(pop1 > 0); \
\
do { *P_leaf++ = *P_Index++; /* truncates */\
} while (--(p_op1)); \
}
#define COPYTOLEAF_ODD_SUB(cLevel,Pjll,Copy) \
{ \
uint8_t * P_leaf = (uint8_t *) (Pjll); \
Word_t p_op1 = pop1; \
PWord_t P_Index = PIndex; \
\
assert(pop1 > 0); \
\
do { \
Copy(P_leaf, *P_Index); \
P_leaf += (cLevel); ++P_Index; \
} while (--(p_op1)); \
}
#ifdef JUDY1
#define COPYTOLEAF_EVEN(Pjll,LeafType) COPYTOLEAF_EVEN_SUB(Pjll,LeafType)
#define COPYTOLEAF_ODD(cLevel,Pjll,Copy) COPYTOLEAF_ODD_SUB(cLevel,Pjll,Copy)
#else // JUDYL adds copying of values:
#define COPYTOLEAF_EVEN(Pjll,LeafType) \
{ \
COPYTOLEAF_EVEN_SUB(Pjll,LeafType) \
JU_COPYMEM(Pjv, PValue, pop1); \
}
#define COPYTOLEAF_ODD(cLevel,Pjll,Copy) \
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
// JPFULLPOPU1:
if (pop1 == cJU_JPFULLPOPU1_POP0 + 1)
{
Word_t Addr = PjpParent->jp_Addr;
Word_t DcdP0 = (*PIndex & cJU_DCDMASK(1))
| cJU_JPFULLPOPU1_POP0;
JU_JPSETADT(PjpParent, Addr, DcdP0, cJ1_JPFULLPOPU1);
return(TRUE);
}
#endif
// JPLEAF_B1:
if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
NOMEM;
Pjlb = P_JLB(PjlbRaw);
for (offset = 0; offset < pop1; ++offset)
JU_BITMAPSETL(Pjlb, PIndex[offset]);
retval = TRUE; // default.
#ifdef JUDYL
// Build subexpanse values-only leaves (LeafVs) under LeafB1:
for (offset = 0; offset < cJU_NUMSUBEXPL; ++offset)
{
if (! (pop1sub = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, offset))))
continue; // skip empty subexpanse.
// Allocate one LeafV = JP subarray; if out of memory, clear bitmaps for higher
// subexpanses and adjust *PPop1:
if ((PjvRaw = j__udyLAllocJV(pop1sub, Pjpm))
== (Pjv_t) NULL)
{
for (/* null */; offset < cJU_NUMSUBEXPL; ++offset)
{
*PPop1 -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, offset));
JU_JLB_BITMAP(Pjlb, offset) = 0;
}
retval = FALSE;
break;
}
// Populate values-only leaf and save the pointer to it:
Pjv = P_JV(PjvRaw);
JU_COPYMEM(Pjv, PValue, pop1sub);
JL_JLB_PVALUE(Pjlb, offset) = PjvRaw; // first-tier pointer.
PValue += pop1sub;
} // for each subexpanse
#endif // JUDYL
// Attach new LeafB1 to parent JP; note use of *PPop1 possibly < pop1:
JU_JPSETADT(PjpParent, (Word_t) PjlbRaw,
(*PIndex & cJU_DCDMASK(1)) | (*PPop1 - 1), cJU_JPLEAF_B1);
return(retval);
} // JPLEAF_B1 or JPFULLPOPU1
// BUILD JPBRANCH_U*:
//
// Arriving at BuildBranch means Level < top level but the pop1 is too large
// for immediate indexes or a leaf, even under a narrow pointer, including a
// LeafB1 or FullPop at level 1. This implies SAMESUBEXP(1) == FALSE, that is,
// the indexes to be stored "branch" at level 2 or higher.
BuildBranch: // come here directly if a leaf wont work.
assert(Level >= 2);
assert(Level < cJU_ROOTSTATE);
assert(! SAMESUBEXP(1)); // sanity check, see above.
// Determine the appropriate level for a new branch node; see if a narrow
// pointer can be used:
//
// This can be confusing. The branch is required at the lowest level L where
// the indexes to store are not in the same subexpanse at level L-1. Work down
// from Level to tree level 3, which is 1 above the lowest tree level = 2 at
// which a branch can be used. Theres no need to check SAMESUBEXP at level 2
// because its known to be false at level 2-1 = 1.
//
// Note: Unlike for a leaf node, a narrow pointer is always used for a branch
// if possible, that is, maximum compression is always used, except at the top
// level of the tree, where a JPM cannot support a narrow pointer, meaning a
// top BranchL can have a single JP (fanout = 1); but that case jumps directly
// to BuildBranch2.
//
// Note: For 32-bit systems the only usable values for a narrow pointer are
// Level = 3 and levelsub = 2; 64-bit systems have many more choices; but
// hopefully this for-loop is fast enough even on a 32-bit system.
//
// TBD: If not fast enough, #ifdef JU_64BIT and handle the 32-bit case faster.
for (levelsub = Level; levelsub >= 3; --levelsub) // see above.
if (! SAMESUBEXP(levelsub - 1)) // at limit of narrow pointer.
break; // put branch at levelsub.
BuildBranch2: // come here directly for Level = levelsub = cJU_ROOTSTATE.
assert(levelsub >= 2);
assert(levelsub <= Level);
// Initially build a BranchU:
//
// Always start with a BranchU because the number of populated subexpanses is
// not yet known. Use digitmask, digitshifted, and digitshincr to avoid
// expensive variable shifts within JU_DIGITATSTATE within the loop.
//
// TBD: The use of digitmask, etc. results in more increment operations per
// loop, is there an even faster way?
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
JU_BITMAPSETB(Pjbb, digit);
// Copy non-null JPs to BranchB JP subarrays:
for (offset = 0; offset < cJU_NUMSUBEXPB; ++offset)
{
Pjp_t PjparrayRaw;
Pjp_t Pjparray;
if (! (numJPs = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, offset))))
continue; // skip empty subexpanse.
// If unable to allocate a JP subarray, free all BranchB memory so far and
// continue to use the BranchU:
if ((PjparrayRaw = j__udyAllocJBBJP(numJPs, Pjpm))
== (Pjp_t) NULL)
{
while (offset-- > 0)
{
if (JU_JBB_PJP(Pjbb, offset) == (Pjp_t) NULL) continue;
j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, offset),
j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, offset)),
Pjpm);
}
j__udyFreeJBB(PjbbRaw, Pjpm);
goto SetParent; // keep BranchU.
}
// Set one JP subarray pointer and copy the subexpanses JPs to the subarray:
//
// Scan the BranchU for non-null JPs until numJPs JPs are copied.
JU_JBB_PJP(Pjbb, offset) = PjparrayRaw;
Pjparray = P_JP(PjparrayRaw);
while (numJPs-- > 0)
{
while ((Pjp2->jp_Type) == JPtype_null)
{
++Pjp2;
assert(Pjp2 < (Pjbu->jbu_jp) + cJU_BRANCHUNUMJPS);
}
*Pjparray++ = *Pjp2++;
}
} // for each subexpanse
// Free the BranchU and prepare to use the new BranchB instead:
j__udyFreeJBU(PjbuRaw, Pjpm);
Pjbany = (Word_t) PjbbRaw;
JPtype = branchB_JPtype[levelsub];
} // compress to BranchB
// COMPLETE OR PARTIAL SUCCESS:
//
// Attach new branch (under Pjp, with JPtype) to parent JP; note use of *PPop1,
// possibly reduced due to partial failure.
SetParent:
(PjpParent->jp_Addr) = Pjbany;
(PjpParent->jp_Type) = JPtype;
if (Level < cJU_ROOTSTATE) // PjpParent not in JPM:
{
Word_t DcdP0 = (*PIndex & cJU_DCDMASK(levelsub)) | (*PPop1 - 1);
JU_JPSETADT(PjpParent ,Pjbany, DcdP0, JPtype);
}
return(retval);
} // j__udyInsArray()
( run in 0.793 second using v1.01-cache-2.11-cpan-2398b32b56e )