diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c | 135 |
1 files changed, 0 insertions, 135 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c b/libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c deleted file mode 100644 index cfa16bd6d..000000000 --- a/libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c +++ /dev/null @@ -1,135 +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.17 $ $Source: /judy/src/JudyCommon/JudyInsertBranch.c $ - -// BranchL insertion 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" - -extern int j__udyCreateBranchL(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t); - - -// **************************************************************************** -// __ J U D Y I N S E R T B R A N C H -// -// Insert 2-element BranchL in between Pjp and Pjp->jp_Addr. -// -// Return -1 if out of memory, otherwise return 1. - -FUNCTION int j__udyInsertBranch( - Pjp_t Pjp, // JP containing narrow pointer. - Word_t Index, // outlier to Pjp. - Word_t BranchLevel, // of what JP points to, mapped from JP type. - Pjpm_t Pjpm) // for global accounting. -{ - jp_t JP2 [2]; - jp_t JP; - Pjp_t PjpNull; - Word_t XorExp; - Word_t Inew, Iold; - Word_t DCDMask; // initially for original BranchLevel. - int Ret; - uint8_t Exp2[2]; - uint8_t DecodeByteN, DecodeByteO; - -// Get the current mask for the DCD digits: - - DCDMask = cJU_DCDMASK(BranchLevel); - -// Obtain Dcd bits that differ between Index and JP, shifted so the -// digit for BranchLevel is the LSB: - - XorExp = ((Index ^ JU_JPDCDPOP0(Pjp)) & (cJU_ALLONES >> cJU_BITSPERBYTE)) - >> (BranchLevel * cJU_BITSPERBYTE); - assert(XorExp); // Index must be an outlier. - -// Count levels between object under narrow pointer and the level at which -// the outlier diverges from it, which is always at least initial -// BranchLevel + 1, to end up with the level (JP type) at which to insert -// the new intervening BranchL: - - do { ++BranchLevel; } while ((XorExp >>= cJU_BITSPERBYTE)); - assert((BranchLevel > 1) && (BranchLevel < cJU_ROOTSTATE)); - -// Get the MSB (highest digit) that differs between the old expanse and -// the new Index to insert: - - DecodeByteO = JU_DIGITATSTATE(JU_JPDCDPOP0(Pjp), BranchLevel); - DecodeByteN = JU_DIGITATSTATE(Index, BranchLevel); - - assert(DecodeByteO != DecodeByteN); - -// Determine sorted order for old expanse and new Index digits: - - if (DecodeByteN > DecodeByteO) { Iold = 0; Inew = 1; } - else { Iold = 1; Inew = 0; } - -// Copy old JP into staging area for new Branch - JP2 [Iold] = *Pjp; - Exp2[Iold] = DecodeByteO; - Exp2[Inew] = DecodeByteN; - -// Create a 2 Expanse Linear branch -// -// Note: Pjp->jp_Addr is set by j__udyCreateBranchL() - - Ret = j__udyCreateBranchL(Pjp, JP2, Exp2, 2, Pjpm); - if (Ret == -1) return(-1); - -// Get Pjp to the NULL of where to do insert - PjpNull = ((P_JBL(Pjp->jp_Addr))->jbl_jp) + Inew; - -// Convert to a cJU_JPIMMED_*_01 at the correct level: -// Build JP and set type below to: cJU_JPIMMED_X_01 - JU_JPSETADT(PjpNull, 0, Index, cJU_JPIMMED_1_01 - 2 + BranchLevel); - -// Return pointer to Value area in cJU_JPIMMED_X_01 - JUDYLCODE(Pjpm->jpm_PValue = (Pjv_t) PjpNull;) - -// The old JP now points to a BranchL that is at higher level. Therefore -// it contains excess DCD bits (in the least significant position) that -// must be removed (zeroed); that is, they become part of the Pop0 -// subfield. Note that the remaining (lower) bytes in the Pop0 field do -// not change. -// -// Take from the old DCDMask, which went "down" to a lower BranchLevel, -// and zero any high bits that are still in the mask at the new, higher -// BranchLevel; then use this mask to zero the bits in jp_DcdPopO: - -// Set old JP to a BranchL at correct level - - Pjp->jp_Type = cJU_JPBRANCH_L2 - 2 + BranchLevel; - DCDMask ^= cJU_DCDMASK(BranchLevel); - DCDMask = ~DCDMask & JU_JPDCDPOP0(Pjp); - JP = *Pjp; - JU_JPSETADT(Pjp, JP.jp_Addr, DCDMask, JP.jp_Type); - - return(1); - -} // j__udyInsertBranch() |