Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
j__udyFreeJBL(PjblRaw, Pjpm); // free old BranchL.
// Having changed branch types, now do the insert in the new branch type:
goto ContinueInsWalk;
// OPPORTUNISTICALLY CONVERT FROM BRANCHL TO BRANCHU:
//
// Memory efficiency is no object because the branchs pop1 is large enough, so
// speed up array access. Come here with PjblRaw set. Note: This is goto
// code because the previous block used to fall through into it as well, but no
// longer.
ConvertBranchLtoU:
// Allocate memory for an uncompressed branch:
if ((PjbuRaw = j__udyAllocJBU(Pjpm)) == (Pjbu_t) NULL)
return(-1);
Pjbu = P_JBU(PjbuRaw);
// Set the proper NULL type for most of the uncompressed branchs JPs:
JU_JPSETADT(&newJP, 0, 0,
JU_JPTYPE(Pjp) - cJU_JPBRANCH_L2 + cJU_JPNULL1);
// Initialize: Pre-set uncompressed branch to mostly JPNULL*s:
for (numJPs = 0; numJPs < cJU_BRANCHUNUMJPS; ++numJPs)
Pjbu->jbu_jp[numJPs] = newJP;
// Copy JPs from linear branch to uncompressed branch:
{
#ifdef SUBEXPCOUNTS
Word_t popmask = cJU_POP0MASK(JU_JPTYPE(Pjp))
- cJU_JPBRANCH_L2 - 2;
for (numJPs = 0; numJPs < cJU_NUMSUBEXPU; ++numJPs)
Pjbu->jbu_subPop1[numJPs] = 0;
#endif
for (numJPs = 0; numJPs < Pjbl->jbl_NumJPs; ++numJPs)
{
Pjp_t Pjp1 = &(Pjbl->jbl_jp[numJPs]);
offset = Pjbl->jbl_Expanse[numJPs];
Pjbu->jbu_jp[offset] = *Pjp1;
#ifdef SUBEXPCOUNTS
Pjbu->jbu_subPop1[offset/cJU_NUMSUBEXPU] +=
JU_JPDCDPOP0(Pjp1) & popmask + 1;
#endif
}
}
j__udyFreeJBL(PjblRaw, Pjpm); // free old BranchL.
// Plug new values into parent JP:
Pjp->jp_Addr = (Word_t) PjbuRaw;
Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_L; // to BranchU.
// Save global population of last BranchU conversion:
Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;
goto ContinueInsWalk;
} // case cJU_JPBRANCH_L.
// ****************************************************************************
// JPBRANCH_B*:
//
// If the new Index is not an outlier to the branchs expanse, extract the
// digit and record the Immediate type to create for a new Immed JP, before
// going to common code.
//
// Note: JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.
case cJU_JPBRANCH_B2:
JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);
goto JudyBranchB;
case cJU_JPBRANCH_B3:
JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);
goto JudyBranchB;
#ifdef JU_64BIT
case cJU_JPBRANCH_B4:
JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);
goto JudyBranchB;
case cJU_JPBRANCH_B5:
JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);
goto JudyBranchB;
case cJU_JPBRANCH_B6:
JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);
goto JudyBranchB;
case cJU_JPBRANCH_B7:
JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);
goto JudyBranchB;
#endif
case cJU_JPBRANCH_B:
{
Pjbb_t Pjbb; // pointer to bitmap branch.
Pjbb_t PjbbRaw; // pointer to bitmap branch.
Pjp_t Pjp2Raw; // 1 of N arrays of JPs.
Pjp_t Pjp2; // 1 of N arrays of JPs.
Word_t subexp; // 1 of N subexpanses in bitmap.
BITMAPB_t bitmap; // for one subexpanse.
BITMAPB_t bitmask; // bit set for Indexs digit.
Word_t numJPs; // number of JPs = populated expanses.
int offset; // in bitmap branch.
// Similar to common code above, but no outlier check is needed, and the Immed
// type depends on the word size:
digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
exppop1 = Pjpm->jpm_Pop0;
// fall through:
// COMMON CODE FOR BITMAP BRANCHES:
//
// Come here with digit and exppop1 already set.
JudyBranchB:
// If population increment is greater than.. (300):
if ((Pjpm->jpm_Pop0 - Pjpm->jpm_LastUPop0) > JU_BTOU_POP_INCREMENT)
{
// If total population of array is greater than.. (750):
if (Pjpm->jpm_Pop0 > JU_BRANCHB_MAX_POP)
{
// If population under the branch is greater than.. (135):
if (exppop1 > JU_BRANCHB_MIN_POP)
{
if (j__udyCreateBranchU(Pjp, Pjpm) == -1) return(-1);
// Save global population of last BranchU conversion:
Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;
goto ContinueInsWalk;
}
}
}
// CONTINUE TO USE BRANCHB:
//
// Get pointer to bitmap branch (JBB):
PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);
Pjbb = P_JBB(PjbbRaw);
// Form the Int32 offset, and Bit offset values:
//
// 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
// |SubExpanse | Bit offset |
//
// Get the 1 of 8 expanses from digit, Bits 5..7 = 1 of 8, and get the 32-bit
// word that may have a bit set:
subexp = digit / cJU_BITSPERSUBEXPB;
bitmap = JU_JBB_BITMAP(Pjbb, subexp);
Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
Pjp2 = P_JP(Pjp2Raw);
// Get the bit position that represents the desired expanse, and get the offset
// into the array of JPs for the JP that matches the bit.
bitmask = JU_BITPOSMASKB(digit);
offset = j__udyCountBitsB(bitmap & (bitmask - 1));
// If JP is already in this expanse, get Pjp and continue the walk:
if (bitmap & bitmask)
{
#ifdef SUBEXPCOUNTS
PSubExp = &(Pjbb->jbb_Counts[subexp]); // ptr to subexp counts.
#endif
Pjp = Pjp2 + offset;
break; // continue walk.
}
// ADD NEW EXPANSE FOR NEW INDEX:
//
// The new expanse always an cJU_JPIMMED_*_01 containing just the new Index, so
// finish setting up an Immed JP.
JU_JPSETADT(&newJP, 0, Index,
JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01-cJU_JPBRANCH_B2);
// Get 1 of the 8 JP arrays and calculate number of JPs in subexpanse array:
Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
Pjp2 = P_JP(Pjp2Raw);
numJPs = j__udyCountBitsB(bitmap);
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
Word_t SubExpCount = 0; // current subexpanse counter.
if (PSubExp != (PWord_t) NULL) // only if BranchB/U.
SubExpCount = PSubExp[0];
#endif
// PROCESS JP -- RECURSIVELY:
//
// For non-Immed JP types, if successful, post-increment the population count
// at this Level.
retcode = j__udyInsWalk(Pjp, Index, Pjpm);
// Successful insert, increment JP and subexpanse count:
if ((JU_JPTYPE(Pjp) < cJU_JPIMMED_1_01) && (retcode == 1))
{
jp_t JP;
Word_t DcdP0;
#ifdef SUBEXPCOUNTS
// Note: Pjp must be a pointer to a BranchB/U:
if (PSubExp != (PWord_t) NULL) PSubExp[0] = SubExpCount + 1;
#endif
JP = *Pjp;
DcdP0 = JU_JPDCDPOP0(Pjp) + 1;
JU_JPSETADT(Pjp, JP.jp_Addr, DcdP0, JU_JPTYPE(&JP));
}
}
return(retcode);
} // j__udyInsWalk()
// ****************************************************************************
// J U D Y 1 S E T
// J U D Y L I N S
//
// Main entry point. See the manual entry for details.
#ifdef JUDY1
FUNCTION int Judy1Set
#else
FUNCTION PPvoid_t JudyLIns
#endif
(
PPvoid_t PPArray, // in which to insert.
Word_t Index, // to insert.
PJError_t PJError // optional, for returning error info.
)
{
#ifdef JUDY1
#define Pjv ignore // placeholders for macros.
#define Pjvnew ignore
#else
Pjv_t Pjv; // value area in old leaf.
Pjv_t Pjvnew; // value area in new leaf.
#endif
Pjpm_t Pjpm; // array-global info.
int offset; // position in which to store new Index.
Pjlw_t Pjlw;
// CHECK FOR NULL POINTER (error by caller):
if (PPArray == (PPvoid_t) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
JUDY1CODE(return(JERRI );)
JUDYLCODE(return(PPJERR);)
}
Pjlw = P_JLW(*PPArray); // first word of leaf.
// ****************************************************************************
// PROCESS TOP LEVEL "JRP" BRANCHES AND LEAVES:
// ****************************************************************************
// JRPNULL (EMPTY ARRAY): BUILD A LEAFW WITH ONE INDEX:
// if a valid empty array (null pointer), so create an array of population == 1:
if (Pjlw == (Pjlw_t)NULL)
{
Pjlw_t Pjlwnew;
Pjlwnew = j__udyAllocJLW(1);
JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)
JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)
Pjlwnew[0] = 1 - 1; // pop0 = 0.
Pjlwnew[1] = Index;
*PPArray = (Pvoid_t) Pjlwnew;
DBGCODE(JudyCheckPop(*PPArray);)
JUDY1CODE(return(1); )
JUDYLCODE(Pjlwnew[2] = 0; ) // value area.
JUDYLCODE(return((PPvoid_t) (Pjlwnew + 2)); )
} // NULL JRP
// ****************************************************************************
// LEAFW, OTHER SIZE:
if (JU_LEAFW_POP0(*PPArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
{
Pjlw_t Pjlwnew;
Word_t pop1;
Pjlw = P_JLW(*PPArray); // first word of leaf.
pop1 = Pjlw[0] + 1;
#ifdef JUDYL
Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);
#endif
offset = j__udySearchLeafW(Pjlw + 1, pop1, Index);
if (offset >= 0) // index is already valid:
( run in 1.562 second using v1.01-cache-2.11-cpan-e1769b4cff6 )