diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c | 135 |
1 files changed, 135 insertions, 0 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c b/libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c new file mode 100644 index 00000000..cfa16bd6 --- /dev/null +++ b/libnetdata/libjudy/src/JudyL/JudyLInsertBranch.c @@ -0,0 +1,135 @@ +// 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() |