view release on metacpan or  search on metacpan

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

// Error (rare), or end of indexes while traversing new BranchU (performance
// path); either way, mark the remaining JPs, if any, in the BranchU as nulls
// and exit the loop:
//
// Arrive here with digit and Pjp set to the first JP to set to null.

ClearBranch:
            for (/* null */; digit < cJU_BRANCHUNUMJPS; ++digit, ++Pjp)
                SETJPNULL(Pjp);
            break;                              // saves one more compare.

        } // for each digit


// FINISH JPBRANCH_U*:
//
// Arrive here with a BranchU built under Pjbu, numJPs set, and either:  retval
// == TRUE and *PPop1 unmodified, or else retval == FALSE, *PPop1 set to the
// actual number of indexes saved (possibly 0 for complete failure at a lower
// level upon the first call of j__udyInsArray()), and the Judy error set in
// Pjpm.  Either way, PIndex points to an index within the expanse just
// handled.

        Pjbany = (Word_t) PjbuRaw;              // default = use this BranchU.
        JPtype = branchU_JPtype[levelsub];

// Check for complete failure above:

        assert((! retval) || *PPop1);           // sanity check.

        if ((! retval) && (*PPop1 == 0))        // nothing stored, full failure.
        {
            j__udyFreeJBU(PjbuRaw, Pjpm);
            SETJPNULL_PARENT;
            return(FALSE);
        }

// Complete or partial success so far; watch for sorting error after the
// maximum digit (255) in the BranchU, which is indicated by having more
// indexes to store in the BranchUs expanse:
//
// For example, if an index to store has a digit of 255 at levelsub, followed
// by an index with a digit of 254, the for-loop above runs out of digits
// without reducing pop1 to 0.

        if (pop1 != 0)
        {
            JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED);
            *PPop1 -= pop1;             // deduct unsaved indexes.
            retval  = FALSE;
        }
        assert(*PPop1 != 0);            // branch (still) cannot be empty.


// OPTIONALLY COMPRESS JPBRANCH_U*:
//
// See if the BranchU should be compressed to a BranchL or BranchB; if so, do
// that and free the BranchU; otherwise just use the existing BranchU.  Follow
// the same rules as in JudyIns.c (version 4.95):  Only check local population
// (cJU_OPP_UNCOMP_POP0) for BranchL, and only check global memory efficiency
// (JU_OPP_UNCOMPRESS) for BranchB.  TBD:  Have the rules changed?
//
// Note:  Because of differing order of operations, the latter compression
// might not result in the same set of branch nodes as a series of sequential
// insertions.
//
// Note:  Allocating a BranchU only to sometimes convert it to a BranchL or
// BranchB is unfortunate, but attempting to work with a temporary BranchU on
// the stack and then allocate and keep it as a BranchU in many cases is worse
// in terms of error handling.


// COMPRESS JPBRANCH_U* TO JPBRANCH_L*:

        if (numJPs <= cJU_BRANCHLMAXJPS)        // JPs fit in a BranchL.
        {
            Pjbl_t PjblRaw = (Pjbl_t) NULL;     // new BranchL; init for cc.
            Pjbl_t Pjbl;

            if ((*PPop1 > JU_BRANCHL_MAX_POP)   // pop too high.
             || ((PjblRaw = j__udyAllocJBL(Pjpm)) == (Pjbl_t) NULL))
            {                                   // cant alloc BranchL.
                goto SetParent;                 // just keep BranchU.
            }

            Pjbl = P_JBL(PjblRaw);

// Copy BranchU JPs to BranchL:

            (Pjbl->jbl_NumJPs) = numJPs;
            offset = 0;

            for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit)
            {
                if ((((Pjbu->jbu_jp) + digit)->jp_Type) == JPtype_null)
                    continue;

                (Pjbl->jbl_Expanse[offset  ]) = digit;
                (Pjbl->jbl_jp     [offset++]) = Pjbu->jbu_jp[digit];
            }
            assert(offset == numJPs);           // found same number.

// Free the BranchU and prepare to use the new BranchL instead:

            j__udyFreeJBU(PjbuRaw, Pjpm);

            Pjbany = (Word_t) PjblRaw;
            JPtype = branchL_JPtype[levelsub];

        } // compress to BranchL


// COMPRESS JPBRANCH_U* TO JPBRANCH_B*:
//
// If unable to allocate the BranchB or any JP subarray, free all related
// memory and just keep the BranchU.
//
// Note:  This use of JU_OPP_UNCOMPRESS is a bit conservative because the
// BranchU is already allocated while the (presumably smaller) BranchB is not,
// the opposite of how its used in single-insert code.