view release on metacpan or  search on metacpan

src/judy-1.0.5/src/JudyCommon/JudyCreateBranch.c  view on Meta::CPAN

// We have no idea what kind of BranchL it is, so caller must set the jp_Type.
//
// Return -1 if error (details in Pjpm), otherwise return 1.

FUNCTION int j__udyCreateBranchL(
	Pjp_t	Pjp,		// Build JPs from this place
	Pjp_t	PJPs,		// Array of JPs to put into Bitmap branch
	uint8_t Exp[],		// Array of expanses to put into bitmap
	Word_t  ExpCnt,		// Number of above JPs and Expanses
	Pvoid_t	Pjpm)
{
	Pjbl_t	PjblRaw;	// pointer to linear branch.
	Pjbl_t	Pjbl;

	assert(ExpCnt <= cJU_BRANCHLMAXJPS);

	PjblRaw	= j__udyAllocJBL(Pjpm);
	if (PjblRaw == (Pjbl_t) NULL) return(-1);
        Pjbl    = P_JBL(PjblRaw);

//	Build a Linear Branch
	Pjbl->jbl_NumJPs = ExpCnt;

//	Copy from the Linear branch from splayed leaves
	JU_COPYMEM(Pjbl->jbl_Expanse, Exp,  ExpCnt);
	JU_COPYMEM(Pjbl->jbl_jp,      PJPs, ExpCnt);

//	Pass back new pointer to the Linear branch in JP
	Pjp->jp_Addr = (Word_t) PjblRaw;

	return(1);

} // j__udyCreateBranchL()


// ****************************************************************************
// J U D Y   C R E A T E   B R A N C H   B
//
// Build a BranchB from an array of JPs and associated 1 byte digits
// (expanses).  Return with Pjp pointing to the BranchB.  Caller must
// deallocate passed arrays, if necessary.
//
// We have no idea what kind of BranchB it is, so caller must set the jp_Type.
//
// Return -1 if error (details in Pjpm), otherwise return 1.

FUNCTION int j__udyCreateBranchB(
	Pjp_t	Pjp,		// Build JPs from this place
	Pjp_t	PJPs,		// Array of JPs to put into Bitmap branch
	uint8_t Exp[],		// Array of expanses to put into bitmap
	Word_t  ExpCnt,		// Number of above JPs and Expanses
	Pvoid_t	Pjpm)
{
	Pjbb_t	PjbbRaw;	// pointer to bitmap branch.
	Pjbb_t	Pjbb;
	Word_t  ii, jj;		// Temps
	uint8_t CurrSubExp;	// Current sub expanse for BM

// This assertion says the number of populated subexpanses is not too large.
// This function is only called when a BranchL overflows to a BranchB or when a
// cascade occurs, meaning a leaf overflows.  Either way ExpCnt cant be very
// large, in fact a lot smaller than cJU_BRANCHBMAXJPS.  (Otherwise a BranchU
// would be used.)  Popping this assertion means something (unspecified) has
// gone very wrong, or else Judys design criteria have changed, although in
// fact there should be no HARM in creating a BranchB with higher actual
// fanout.

	assert(ExpCnt <= cJU_BRANCHBMAXJPS);

//	Get memory for a Bitmap branch
	PjbbRaw	= j__udyAllocJBB(Pjpm);
	if (PjbbRaw == (Pjbb_t) NULL) return(-1);
	Pjbb = P_JBB(PjbbRaw);

//	Get 1st "sub" expanse (0..7) of bitmap branch
	CurrSubExp = Exp[0] / cJU_BITSPERSUBEXPB;

// Index thru all 1 byte sized expanses:

	for (jj = ii = 0; ii <= ExpCnt; ii++)
	{
		Word_t SubExp;	// Cannot be a uint8_t

//		Make sure we cover the last one
		if (ii == ExpCnt)
		{
			SubExp = cJU_ALLONES;	// Force last one
		}
		else
		{
//			Calculate the "sub" expanse of the byte expanse
			SubExp = Exp[ii] / cJU_BITSPERSUBEXPB;  // Bits 5..7.

//			Set the bit that represents the expanse in Exp[]
			JU_JBB_BITMAP(Pjbb, SubExp) |= JU_BITPOSMASKB(Exp[ii]);
		}
//		Check if a new "sub" expanse range needed
		if (SubExp != CurrSubExp)
		{
//			Get number of JPs in this sub expanse
			Word_t NumJP = ii - jj;
			Pjp_t  PjpRaw;
			Pjp_t  Pjp;

			PjpRaw = j__udyAllocJBBJP(NumJP, Pjpm);
                        Pjp    = P_JP(PjpRaw);

			if (PjpRaw == (Pjp_t) NULL)	// out of memory.
			{

// Free any previous allocations:

			    while(CurrSubExp--)
			    {
				NumJP = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb,
								  CurrSubExp));
				if (NumJP)
				{
				    j__udyFreeJBBJP(JU_JBB_PJP(Pjbb,
						    CurrSubExp), NumJP, Pjpm);
				}