Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
// 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.116 $ $Source: /judy/src/JudyCommon/JudyIns.c $
//
// Judy1Set() and JudyLIns() functions for Judy1 and JudyL.
// Compile with one of -DJUDY1 or -DJUDYL.
//
// TBD: Should some of the assertions here be converted to product code that
// returns JU_ERRNO_CORRUPT?
#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"
// Note: Call JudyCheckPop() even before "already inserted" returns, to catch
// population errors; see fix in 4.84:
DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)
DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)
#ifdef TRACEJP
#include "JudyPrintJP.c"
#endif
// These are defined to generic values in JudyCommon/JudyPrivateTypes.h:
//
// TBD: These should be exported from a header file, but perhaps not, as they
// are only used here, and exported from Judy*Decascade, which is a separate
// file for profiling reasons (to prevent inlining), but which potentially
// could be merged with this file, either in SoftCM or at compile-time.
#ifdef JUDY1
extern int j__udy1CreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
extern int j__udy1CreateBranchU(Pjp_t, Pvoid_t);
#ifndef JU_64BIT
extern int j__udy1Cascade1(Pjp_t, Pvoid_t);
#endif
extern int j__udy1Cascade2(Pjp_t, Pvoid_t);
extern int j__udy1Cascade3(Pjp_t, Pvoid_t);
#ifdef JU_64BIT
extern int j__udy1Cascade4(Pjp_t, Pvoid_t);
extern int j__udy1Cascade5(Pjp_t, Pvoid_t);
extern int j__udy1Cascade6(Pjp_t, Pvoid_t);
extern int j__udy1Cascade7(Pjp_t, Pvoid_t);
#endif
extern int j__udy1CascadeL(Pjp_t, Pvoid_t);
extern int j__udy1InsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);
#else // JUDYL
extern int j__udyLCreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
extern int j__udyLCreateBranchU(Pjp_t, Pvoid_t);
extern int j__udyLCascade1(Pjp_t, Pvoid_t);
extern int j__udyLCascade2(Pjp_t, Pvoid_t);
extern int j__udyLCascade3(Pjp_t, Pvoid_t);
#ifdef JU_64BIT
extern int j__udyLCascade4(Pjp_t, Pvoid_t);
extern int j__udyLCascade5(Pjp_t, Pvoid_t);
extern int j__udyLCascade6(Pjp_t, Pvoid_t);
extern int j__udyLCascade7(Pjp_t, Pvoid_t);
#endif
extern int j__udyLCascadeL(Pjp_t, Pvoid_t);
extern int j__udyLInsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);
#endif
// ****************************************************************************
// MACROS FOR COMMON CODE:
//
// Check if Index is an outlier to (that is, not a member of) this expanse:
//
// An outlier is an Index in-the-expanse of the slot containing the pointer,
// but not-in-the-expanse of the "narrow" pointer in that slot. (This means
// the Dcd part of the Index differs from the equivalent part of jp_DcdPopO.)
// Therefore, the remedy is to put a cJU_JPBRANCH_L* between the narrow pointer
// and the object to which it points, and add the outlier Index as an Immediate
// in the cJU_JPBRANCH_L*. The "trick" is placing the cJU_JPBRANCH_L* at a
// Level that is as low as possible. This is determined by counting the digits
// in the existing narrow pointer that are the same as the digits in the new
// Index (see j__udyInsertBranch()).
//
// Note: At some high Levels, cJU_DCDMASK() is all zeros => dead code; assume
// the compiler optimizes this out.
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
assert(exppop1 <= (MaxPop1)); \
PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
Pleaf = (Type) P_JLL(PjllRaw); \
JU_LEAFPREPVALUE(Pjv, ValueArea)
// Add to, or grow, a linear leaf: Find Index position; if the Index is
// absent, if theres room in the leaf, insert the Index [and value of 0] in
// place, otherwise grow the leaf:
//
// Note: These insertions always take place with whole words, using
// JU_INSERTINPLACE() or JU_INSERTCOPY().
#ifdef JUDY1
#define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset) // null.
#else
#define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset) \
JU_INSERTINPLACE(Pjv, ExpPop1, Offset, 0); \
Pjpm->jpm_PValue = (Pjv) + (Offset)
#endif
#ifdef JUDY1
#define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset) // null.
#else
#define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset) \
{ \
Pjv_t Pjvnew = ValueArea(Pleafnew, (ExpPop1) + 1); \
JU_INSERTCOPY(Pjvnew, Pjv, ExpPop1, Offset, 0); \
Pjpm->jpm_PValue = (Pjvnew) + (Offset); \
}
#endif
#define JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace, \
InsertInPlace,InsertCopy,Alloc,Free) \
\
offset = Search(Pleaf, exppop1, Index); \
JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \
\
if (GrowInPlace(exppop1)) /* add to current leaf */ \
{ \
InsertInPlace(Pleaf, exppop1, offset, Index); \
JU_LEAFGROWVALUEADD(Pjv, exppop1, offset); \
DBGCODE(JudyCheckSorted((Pjll_t) Pleaf, exppop1 + 1, cIS);) \
return(1); \
} \
\
if (exppop1 < (MaxPop1)) /* grow to new leaf */ \
{ \
Pjll_t PjllnewRaw; \
Type Pleafnew; \
if ((PjllnewRaw = Alloc(exppop1 + 1, Pjpm)) == 0) return(-1); \
Pleafnew = (Type) P_JLL(PjllnewRaw); \
InsertCopy(Pleafnew, Pleaf, exppop1, offset, Index); \
JU_LEAFGROWVALUENEW(ValueArea, Pjv, exppop1, offset); \
DBGCODE(JudyCheckSorted((Pjll_t) Pleafnew, exppop1 + 1, cIS);) \
Free(PjllRaw, exppop1, Pjpm); \
(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \
return(1); \
} \
assert(exppop1 == (MaxPop1))
// Handle linear leaf overflow (cascade): Splay or compress into smaller
// leaves:
#define JU_LEAFCASCADE(MaxPop1,Cascade,Free) \
if (Cascade(Pjp, Pjpm) == -1) return(-1); \
Free(PjllRaw, MaxPop1, Pjpm); \
goto ContinueInsWalk
// Wrapper around all of the above:
#define JU_LEAFSET(cIS,Type,MaxPop1,Search,GrowInPlace,InsertInPlace, \
InsertCopy,Cascade,Alloc,Free,ValueArea) \
{ \
JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea); \
JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace, \
InsertInPlace,InsertCopy,Alloc,Free); \
JU_LEAFCASCADE(MaxPop1,Cascade,Free); \
}
// END OF MACROS; LEAFL CASES START HERE:
//
// 64-bit Judy1 does not have 1-byte leaves:
#if (defined(JUDYL) || (! defined(JU_64BIT)))
case cJU_JPLEAF1:
JU_LEAFSET(1, uint8_t *, cJU_LEAF1_MAXPOP1, j__udySearchLeaf1,
JU_LEAF1GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
j__udyCascade1, j__udyAllocJLL1, j__udyFreeJLL1,
JL_LEAF1VALUEAREA);
#endif // (JUDYL || ! JU_64BIT)
case cJU_JPLEAF2:
JU_LEAFSET(2, uint16_t *, cJU_LEAF2_MAXPOP1, j__udySearchLeaf2,
JU_LEAF2GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
j__udyCascade2, j__udyAllocJLL2, j__udyFreeJLL2,
JL_LEAF2VALUEAREA);
case cJU_JPLEAF3:
JU_LEAFSET(3, uint8_t *, cJU_LEAF3_MAXPOP1, j__udySearchLeaf3,
JU_LEAF3GROWINPLACE, JU_INSERTINPLACE3, JU_INSERTCOPY3,
j__udyCascade3, j__udyAllocJLL3, j__udyFreeJLL3,
JL_LEAF3VALUEAREA);
#ifdef JU_64BIT
case cJU_JPLEAF4:
JU_LEAFSET(4, uint32_t *, cJU_LEAF4_MAXPOP1, j__udySearchLeaf4,
JU_LEAF4GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
j__udyCascade4, j__udyAllocJLL4, j__udyFreeJLL4,
JL_LEAF4VALUEAREA);
case cJU_JPLEAF5:
JU_LEAFSET(5, uint8_t *, cJU_LEAF5_MAXPOP1, j__udySearchLeaf5,
JU_LEAF5GROWINPLACE, JU_INSERTINPLACE5, JU_INSERTCOPY5,
j__udyCascade5, j__udyAllocJLL5, j__udyFreeJLL5,
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
Index = JU_TRIMTODCDSIZE(Index); \
\
if (oldIndex == Index) \
{ \
Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr)); \
return(0); \
} \
\
if ((PjllRaw = (LeafType) Alloc(2, Pjpm)) == (LeafType) NULL) \
return(-1); \
Pjll = (LeafType) P_JLL(PjllRaw); \
Pjv = ValueArea(Pjll, 2); \
\
oldValue = Pjp->jp_Addr; \
\
Copy(cIS,CopyWord); \
DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \
\
*Pjv = 0; \
Pjpm->jpm_PValue = Pjv; \
D_P0 = Index & cJU_DCDMASK(cIS); /* pop0 = 0 */ \
JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType); \
\
return(1); \
}
#endif // JUDYL
// Handle growth of cJU_JPIMMED_*_[02..15]:
#ifdef JUDY1
// Insert an Index into an immediate JP that has room for more, if the Index is
// not already present; given Pjp, Index, exppop1, Pjv, and Pjpm in the
// context:
//
// Note: Use this only when the JP format doesnt change, that is, going from
// cJU_JPIMMED_X_0Y to cJU_JPIMMED_X_0Z, where X >= 2 and Y+1 = Z.
//
// Note: Incrementing jp_Type is how to increase the Index population.
#define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \
{ \
LeafType Pjll; \
int offset; \
\
exppop1 = JU_JPTYPE(Pjp) - (BaseJPType_02) + 2; \
offset = Search((Pjll_t) (Pjp->jp_1Index), exppop1, Index); \
\
JU_CHECK_IF_EXISTS(offset, ignore, Pjpm); \
\
Pjll = (LeafType) (Pjp->jp_1Index); \
InsertInPlace(Pjll, exppop1, offset, Index); \
DBGCODE(JudyCheckSorted(Pjll, exppop1 + 1, cIS);) \
++(Pjp->jp_Type); \
return(1); \
}
// Insert an Index into an immediate JP that has no room for more:
//
// If the Index is not already present, do a cascade (to a leaf); given Pjp,
// Index, Pjv, and Pjpm in the context.
#define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType, \
ignore,Search,InsertCopy,Alloc) \
{ \
Word_t D_P0; \
Pjll_t PjllRaw; \
Pjll_t Pjll; \
int offset; \
\
offset = Search((Pjll_t) (Pjp->jp_1Index), (OldPop1), Index); \
JU_CHECK_IF_EXISTS(offset, ignore, Pjpm); \
\
if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0) return(-1); \
Pjll = P_JLL(PjllRaw); \
\
InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_1Index), \
OldPop1, offset, Index); \
DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);) \
\
D_P0 = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1; \
JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType); \
return(1); \
}
#else // JUDYL
// Variations to also handle value areas; see comments above:
//
// For JudyL, Pjv (start of value area) is also in the context.
//
// TBD: This code makes a true but weak assumption that a JudyL 32-bit 2-index
// value area must be copied to a new 3-index value area. AND it doesnt know
// anything about JudyL 64-bit cases (cJU_JPIMMED_1_0[3-7] only) where the
// value area can grow in place! However, this should not break it, just slow
// it down.
#define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \
{ \
LeafType Pleaf; \
int offset; \
Pjv_t PjvRaw; \
Pjv_t Pjv; \
Pjv_t PjvnewRaw; \
Pjv_t Pjvnew; \
\
exppop1 = JU_JPTYPE(Pjp) - (BaseJPType_02) + 2; \
offset = Search((Pjll_t) (Pjp->jp_LIndex), exppop1, Index); \
PjvRaw = (Pjv_t) (Pjp->jp_Addr); \
Pjv = P_JV(PjvRaw); \
\
JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \
\
if ((PjvnewRaw = j__udyLAllocJV(exppop1 + 1, Pjpm)) \
== (Pjv_t) NULL) return(-1); \
Pjvnew = P_JV(PjvnewRaw); \
\
Pleaf = (LeafType) (Pjp->jp_LIndex); \
\
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
// [4-7]_01 lead to [4-7]_02 for Judy1, and to leaves for JudyL:
//
// (4_01 => [[ 4_02..03 => ]] LeafL)
// (5_01 => [[ 5_02..03 => ]] LeafL)
// (6_01 => [[ 6_02 => ]] LeafL)
// (7_01 => [[ 7_02 => ]] LeafL)
#ifdef JUDY1
case cJU_JPIMMED_4_01: JU_IMMSET_01(4, uint32_t *, cJ1_JPIMMED_4_02);
case cJU_JPIMMED_5_01: JU_IMMSET_01_ODD(5, cJ1_JPIMMED_5_02,
JU_COPY5_LONG_TO_PINDEX);
case cJU_JPIMMED_6_01: JU_IMMSET_01_ODD(6, cJ1_JPIMMED_6_02,
JU_COPY6_LONG_TO_PINDEX);
case cJU_JPIMMED_7_01: JU_IMMSET_01_ODD(7, cJ1_JPIMMED_7_02,
JU_COPY7_LONG_TO_PINDEX);
#else // JUDYL
case cJU_JPIMMED_4_01:
JU_IMMSET_01_CASCADE(4, uint32_t *, cJU_JPLEAF4, JL_LEAF4VALUEAREA,
JU_IMMSET_01_COPY_EVEN, ignore,
j__udyAllocJLL4);
case cJU_JPIMMED_5_01:
JU_IMMSET_01_CASCADE(5, uint8_t *, cJU_JPLEAF5, JL_LEAF5VALUEAREA,
JU_IMMSET_01_COPY_ODD,
JU_COPY5_LONG_TO_PINDEX, j__udyAllocJLL5);
case cJU_JPIMMED_6_01:
JU_IMMSET_01_CASCADE(6, uint8_t *, cJU_JPLEAF6, JL_LEAF6VALUEAREA,
JU_IMMSET_01_COPY_ODD,
JU_COPY6_LONG_TO_PINDEX, j__udyAllocJLL6);
case cJU_JPIMMED_7_01:
JU_IMMSET_01_CASCADE(7, uint8_t *, cJU_JPLEAF7, JL_LEAF7VALUEAREA,
JU_IMMSET_01_COPY_ODD,
JU_COPY7_LONG_TO_PINDEX, j__udyAllocJLL7);
#endif // JUDYL
#endif // JU_64BIT
// cJU_JPIMMED_1_* cases that can grow in place:
//
// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)
case cJU_JPIMMED_1_02:
#if (defined(JUDY1) || defined(JU_64BIT))
case cJU_JPIMMED_1_03:
case cJU_JPIMMED_1_04:
case cJU_JPIMMED_1_05:
case cJU_JPIMMED_1_06:
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
case cJU_JPIMMED_1_07:
case cJ1_JPIMMED_1_08:
case cJ1_JPIMMED_1_09:
case cJ1_JPIMMED_1_10:
case cJ1_JPIMMED_1_11:
case cJ1_JPIMMED_1_12:
case cJ1_JPIMMED_1_13:
case cJ1_JPIMMED_1_14:
#endif
JU_IMMSETINPLACE(1, uint8_t *, cJU_JPIMMED_1_02, j__udySearchLeaf1,
JU_INSERTINPLACE);
// cJU_JPIMMED_1_* cases that must cascade:
//
// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)
#if (defined(JUDYL) && (! defined(JU_64BIT)))
case cJU_JPIMMED_1_03:
JU_IMMSETCASCADE(1, 3, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,
j__udySearchLeaf1, JU_INSERTCOPY,
j__udyAllocJLL1);
#endif
#if (defined(JUDY1) && (! defined(JU_64BIT)))
case cJU_JPIMMED_1_07:
JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, ignore,
j__udySearchLeaf1, JU_INSERTCOPY,
j__udyAllocJLL1);
#endif
#if (defined(JUDYL) && defined(JU_64BIT))
case cJU_JPIMMED_1_07:
JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,
j__udySearchLeaf1, JU_INSERTCOPY,
j__udyAllocJLL1);
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
// Special case, as described above, go directly from Immed to LeafB1:
case cJ1_JPIMMED_1_15:
{
Word_t DcdP0;
int offset;
Pjlb_t PjlbRaw;
Pjlb_t Pjlb;
offset = j__udySearchLeaf1((Pjll_t) Pjp->jp_1Index, 15, Index);
JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);
// Create a bitmap leaf (special case for Judy1 64-bit only, see usage): Set
// new Index in bitmap, copy an Immed1_15 to the bitmap, and set the parent JP
// EXCEPT jp_DcdPopO, leaving any followup to the caller:
if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
return(-1);
Pjlb = P_JLB(PjlbRaw);
JU_BITMAPSETL(Pjlb, Index);
for (offset = 0; offset < 15; ++offset)
JU_BITMAPSETL(Pjlb, Pjp->jp_1Index[offset]);
// Set jp_DcdPopO including the current pop0; incremented later:
DcdP0 = (Index & cJU_DCDMASK(1)) + 15 - 1;
JU_JPSETADT(Pjp, (Word_t)PjlbRaw, DcdP0, cJU_JPLEAF_B1);
return(1);
}
#endif
// cJU_JPIMMED_[2..7]_[02..15] cases that grow in place or cascade:
//
// (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)
#if (defined(JUDY1) || defined(JU_64BIT))
case cJU_JPIMMED_2_02:
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
case cJU_JPIMMED_2_03:
case cJ1_JPIMMED_2_04:
case cJ1_JPIMMED_2_05:
case cJ1_JPIMMED_2_06:
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
JU_IMMSETINPLACE(2, uint16_t *, cJU_JPIMMED_2_02, j__udySearchLeaf2,
JU_INSERTINPLACE);
#endif
#undef OLDPOP1
#if ((defined(JUDY1) && (! defined(JU_64BIT))) || (defined(JUDYL) && defined(JU_64BIT)))
case cJU_JPIMMED_2_03:
#define OLDPOP1 3
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
case cJ1_JPIMMED_2_07:
#define OLDPOP1 7
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
JU_IMMSETCASCADE(2, OLDPOP1, uint16_t *, cJU_JPLEAF2,
JL_LEAF2VALUEAREA, j__udySearchLeaf2,
JU_INSERTCOPY, j__udyAllocJLL2);
#endif
// (3_01 => [ 3_02 => [ 3_03..05 => ]] LeafL)
#if (defined(JUDY1) && defined(JU_64BIT))
case cJU_JPIMMED_3_02:
case cJ1_JPIMMED_3_03:
case cJ1_JPIMMED_3_04:
JU_IMMSETINPLACE(3, uint8_t *, cJU_JPIMMED_3_02, j__udySearchLeaf3,
JU_INSERTINPLACE3);
#endif
#undef OLDPOP1
#if ((defined(JUDY1) && (! defined(JU_64BIT))) || (defined(JUDYL) && defined(JU_64BIT)))
case cJU_JPIMMED_3_02:
#define OLDPOP1 2
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
case cJ1_JPIMMED_3_05:
#define OLDPOP1 5
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
JU_IMMSETCASCADE(3, OLDPOP1, uint8_t *, cJU_JPLEAF3,
JL_LEAF3VALUEAREA, j__udySearchLeaf3,
JU_INSERTCOPY3, j__udyAllocJLL3);
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
#ifdef JUDYL
Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);
#endif
offset = j__udySearchLeafW(Pjlw + 1, pop1, Index);
if (offset >= 0) // index is already valid:
{
DBGCODE(JudyCheckPop(*PPArray);)
JUDY1CODE(return(0); )
JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )
}
offset = ~offset;
// Insert index in cases where no new memory is needed:
if (JU_LEAFWGROWINPLACE(pop1))
{
++Pjlw[0]; // increase population.
JU_INSERTINPLACE(Pjlw + 1, pop1, offset, Index);
#ifdef JUDYL
JU_INSERTINPLACE(Pjv, pop1, offset, 0);
#endif
DBGCODE(JudyCheckPop(*PPArray);)
DBGCODE(JudyCheckSorted(Pjlw + 1, pop1 + 1, cJU_ROOTSTATE);)
JUDY1CODE(return(1); )
JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )
}
// Insert index into a new, larger leaf:
if (pop1 < cJU_LEAFW_MAXPOP1) // can grow to a larger leaf.
{
Pjlwnew = j__udyAllocJLW(pop1 + 1);
JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)
JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)
Pjlwnew[0] = pop1; // set pop0 in new leaf.
JU_INSERTCOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, Index);
#ifdef JUDYL
Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 + 1);
JU_INSERTCOPY(Pjvnew, Pjv, pop1, offset, 0);
#endif
DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 + 1, cJU_ROOTSTATE);)
j__udyFreeJLW(Pjlw, pop1, NULL);
*PPArray = (Pvoid_t) Pjlwnew;
DBGCODE(JudyCheckPop(*PPArray);)
JUDY1CODE(return(1); )
JUDYLCODE(return((PPvoid_t) (Pjvnew + offset)); )
}
assert(pop1 == cJU_LEAFW_MAXPOP1);
// Leaf at max size => cannot insert new index, so cascade instead:
//
// Upon cascading from a LEAFW leaf to the first branch, must allocate and
// initialize a JPM.
Pjpm = j__udyAllocJPM();
JUDY1CODE(JU_CHECKALLOC(Pjpm_t, Pjpm, JERRI );)
JUDYLCODE(JU_CHECKALLOC(Pjpm_t, Pjpm, PPJERR);)
(Pjpm->jpm_Pop0) = cJU_LEAFW_MAXPOP1 - 1;
(Pjpm->jpm_JP.jp_Addr) = (Word_t) Pjlw;
if (j__udyCascadeL(&(Pjpm->jpm_JP), Pjpm) == -1)
{
JU_COPY_ERRNO(PJError, Pjpm);
JUDY1CODE(return(JERRI );)
JUDYLCODE(return(PPJERR);)
}
// Note: No need to pass Pjpm for memory decrement; LEAFW memory is never
// counted in a JPM at all:
j__udyFreeJLW(Pjlw, cJU_LEAFW_MAXPOP1, NULL);
*PPArray = (Pvoid_t) Pjpm;
} // JU_LEAFW
// ****************************************************************************
// BRANCH:
{
int retcode; // really only needed for Judy1, but free for JudyL.
Pjpm = P_JPM(*PPArray);
retcode = j__udyInsWalk(&(Pjpm->jpm_JP), Index, Pjpm);
if (retcode == -1)
{
JU_COPY_ERRNO(PJError, Pjpm);
JUDY1CODE(return(JERRI );)
JUDYLCODE(return(PPJERR);)
}
if (retcode == 1) ++(Pjpm->jpm_Pop0); // incr total array popu.
assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)
|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)
|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));
DBGCODE(JudyCheckPop(*PPArray);)
#ifdef JUDY1
assert((retcode == 0) || (retcode == 1));
return(retcode); // == JU_RET_*_JPM().
#else
assert(Pjpm->jpm_PValue != (Pjv_t) NULL);
return((PPvoid_t) Pjpm->jpm_PValue);
#endif
}
/*NOTREACHED*/
} // Judy1Set() / JudyLIns()
( run in 1.363 second using v1.01-cache-2.11-cpan-e1769b4cff6 )