diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLCreateBranch.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyL/JudyLCreateBranch.c | 314 |
1 files changed, 0 insertions, 314 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLCreateBranch.c b/libnetdata/libjudy/src/JudyL/JudyLCreateBranch.c deleted file mode 100644 index ffe6b3bde..000000000 --- a/libnetdata/libjudy/src/JudyL/JudyLCreateBranch.c +++ /dev/null @@ -1,314 +0,0 @@ -// Copyright (C) 2000 - 2002 Hewlett-Packard Company -// -// This program is free software; you can redistribute it and/or modify it -// under the term of the GNU Lesser General Public License as published by the -// Free Software Foundation; either version 2 of the License, or (at your -// option) any later version. -// -// This program is distributed in the hope that it will be useful, but WITHOUT -// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or -// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License -// for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with this program; if not, write to the Free Software Foundation, -// Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -// _________________ - -// @(#) $Revision: 4.26 $ $Source: /judy/src/JudyCommon/JudyCreateBranch.c $ - -// Branch creation functions for Judy1 and JudyL. -// Compile with one of -DJUDY1 or -DJUDYL. - -#if (! (defined(JUDY1) || defined(JUDYL))) -#error: One of -DJUDY1 or -DJUDYL must be specified. -#endif - -#ifdef JUDY1 -#include "Judy1.h" -#else -#include "JudyL.h" -#endif - -#include "JudyPrivate1L.h" - - -// **************************************************************************** -// J U D Y C R E A T E B R A N C H L -// -// Build a BranchL from an array of JPs and associated 1 byte digits -// (expanses). Return with Pjp pointing to the BranchL. Caller must -// deallocate passed arrays, if necessary. -// -// 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); - } - } - j__udyFreeJBB(PjbbRaw, Pjpm); - return(-1); - } - -// Place the array of JPs in bitmap branch: - - JU_JBB_PJP(Pjbb, CurrSubExp) = PjpRaw; - -// Copy the JPs to new leaf: - - JU_COPYMEM(Pjp, PJPs + jj, NumJP); - -// On to the next bitmap branch "sub" expanse: - - jj = ii; - CurrSubExp = SubExp; - } - } // for each 1-byte expanse - -// Pass back some of the JP to the new Bitmap branch: - - Pjp->jp_Addr = (Word_t) PjbbRaw; - - return(1); - -} // j__udyCreateBranchB() - - -// **************************************************************************** -// J U D Y C R E A T E B R A N C H U -// -// Build a BranchU from a BranchB. Return with Pjp pointing to the BranchU. -// Free the BranchB and its JP subarrays. -// -// Return -1 if error (details in Pjpm), otherwise return 1. - -FUNCTION int j__udyCreateBranchU( - Pjp_t Pjp, - Pvoid_t Pjpm) -{ - jp_t JPNull; - Pjbu_t PjbuRaw; - Pjbu_t Pjbu; - Pjbb_t PjbbRaw; - Pjbb_t Pjbb; - Word_t ii, jj; - BITMAPB_t BitMap; - Pjp_t PDstJP; -#ifdef JU_STAGED_EXP - jbu_t BranchU; // Staged uncompressed branch -#else - -// Allocate memory for a BranchU: - - PjbuRaw = j__udyAllocJBU(Pjpm); - if (PjbuRaw == (Pjbu_t) NULL) return(-1); - Pjbu = P_JBU(PjbuRaw); -#endif - JU_JPSETADT(&JPNull, 0, 0, JU_JPTYPE(Pjp) - cJU_JPBRANCH_B2 + cJU_JPNULL1); - -// Get the pointer to the BranchB: - - PjbbRaw = (Pjbb_t) (Pjp->jp_Addr); - Pjbb = P_JBB(PjbbRaw); - -// Set the pointer to the Uncompressed branch -#ifdef JU_STAGED_EXP - PDstJP = BranchU.jbu_jp; -#else - PDstJP = Pjbu->jbu_jp; -#endif - for (ii = 0; ii < cJU_NUMSUBEXPB; ii++) - { - Pjp_t PjpA; - Pjp_t PjpB; - - PjpB = PjpA = P_JP(JU_JBB_PJP(Pjbb, ii)); - -// Get the bitmap for this subexpanse - BitMap = JU_JBB_BITMAP(Pjbb, ii); - -// NULL empty subexpanses - if (BitMap == 0) - { -// But, fill with NULLs - for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++) - { - PDstJP[jj] = JPNull; - } - PDstJP += cJU_BITSPERSUBEXPB; - continue; - } -// Check if Uncompressed subexpanse - if (BitMap == cJU_FULLBITMAPB) - { -// Copy subexpanse to the Uncompressed branch intact - JU_COPYMEM(PDstJP, PjpA, cJU_BITSPERSUBEXPB); - -// Bump to next subexpanse - PDstJP += cJU_BITSPERSUBEXPB; - -// Set length of subexpanse - jj = cJU_BITSPERSUBEXPB; - } - else - { - for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++) - { -// Copy JP or NULLJP depending on bit - if (BitMap & 1) { *PDstJP = *PjpA++; } - else { *PDstJP = JPNull; } - - PDstJP++; // advance to next JP - BitMap >>= 1; - } - jj = PjpA - PjpB; - } - -// Free the subexpanse: - - j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, ii), jj, Pjpm); - - } // for each JP in BranchU - -#ifdef JU_STAGED_EXP - -// Allocate memory for a BranchU: - - PjbuRaw = j__udyAllocJBU(Pjpm); - if (PjbuRaw == (Pjbu_t) NULL) return(-1); - Pjbu = P_JBU(PjbuRaw); - -// Copy staged branch to newly allocated branch: -// -// TBD: I think this code is broken. - - *Pjbu = BranchU; - -#endif // JU_STAGED_EXP - -// Finally free the BranchB and put the BranchU in its place: - - j__udyFreeJBB(PjbbRaw, Pjpm); - - Pjp->jp_Addr = (Word_t) PjbuRaw; - Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_B; - - return(1); - -} // j__udyCreateBranchU() |