Adding upstream version 1.44.3.upstream/1.44.3upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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()