John,
> No no, you misunderstand.
No, no, you miscommunicated. :-)
> Its the subroutines INSIDE the actual uses of it that are not.
I see.
> The problemn is JudyCheckPop and JudyCheckSorted are not defined
> anywhere.
I unpacked my tarchive and found sources for them, see below.
> Those specific checks must have previously existed, but didn't make it
> into the repository.
No clue about whether/why Doug or someone would have left them out.
> ...The Windows port primarily consisted of fixing the incorrect
> assumption that long is 64 bits on Win64. Its not...
Right. You've mentioned that before.
> Anyhow whatever I messed up, or *failed* to convert, I have not been
> able to find it.
Maybe this will help, see below. Do these source files exist in your
source set? Does #ifdef DEBUG appear in them, or was that removed?
Cheers,
Alan
-------------
Found in src/JudyCommon/JudyGet.c; merely appending, hope you can copy/paste or
whatever without losing alignment.
#ifndef JUDYGETINLINE // only compile the following function once:
#ifdef DEBUG
// ****************************************************************************
// J U D Y C H E C K P O P
//
// Given a pointer to a Judy array, traverse the entire array to ensure
// population counts add up correctly. This can catch various coding errors.
//
// Since walking the entire tree is probably time-consuming, enable this
// function by setting env parameter $CHECKPOP to first call at which to start
// checking. Note: This function is called both from insert and delete code.
//
// Note: Even though this function does nothing useful for JAP leaves, it's
// good practice to call it anyway, and cheap too.
//
// TBD: This is a debug-only check function similar to JudyCheckSorted(), but
// since it walks the tree it is Judy1/JudyL-specific and must live in a source
// file that is built both ways.
//
// TBD: As feared, enabling this code for every insert/delete makes Judy
// deathly slow, even for a small tree (10K indexes). It's not so bad if
// present but disabled (<1% slowdown measured). Still, should it be ifdef'd
// other than DEBUG and/or called less often?
//
// TBD: Should this "population checker" be expanded to a comprehensive tree
// checker? It currently detects invalid JAP/JP types as well as inconsistent
// pop1's. Other possible checks, all based on essentially redundant data in
// the Judy tree, include:
//
// - Zero LS bits in jp_Addr field.
//
// - Correct Dcd bits.
//
// - Consistent JP types (always descending down the tree).
//
// - Sorted linear lists in BranchL's and leaves (using JudyCheckSorted(), but
// ideally that function is already called wherever appropriate after any
// linear list is modified).
//
// - Any others possible?
#include <stdlib.h> // for getenv() and atol().
static Word_t JudyCheckPopSM(Pjp_t Pjp, Word_t RootPop1);
FUNCTION void JudyCheckPop(
Pvoid_t PArray)
{
static bool_t checked = FALSE; // already checked env parameter.
static bool_t enabled = FALSE; // env parameter set.
static bool_t active = FALSE; // calls >= callsmin.
static Word_t callsmin; // start point from $CHECKPOP.
static Word_t calls = 0; // times called so far.
Word_t JAPtype; // JAP type part of PArray.
// CHECK FOR EXTERNAL ENABLING:
if (! checked) // only check once.
{
char * value; // for getenv().
checked = TRUE;
if ((value = getenv("CHECKPOP")) == (char *) NULL)
{
#ifdef notdef
// Take this out because nightly tests want to be flavor-independent; it's not
// OK to emit special non-error output from the debug flavor:
(void) puts("JudyCheckPop() present but not enabled by "
"$CHECKPOP env parameter; set it to the number of "
"calls at which to begin checking");
#endif
return;
}
callsmin = atol(value); // note: non-number evaluates to 0.
enabled = TRUE;
(void) printf("JudyCheckPop() present and enabled; callsmin = "
"%lu\n", callsmin);
}
else if (! enabled) return;
// Previously or just now enabled; check if non-active or newly active:
if (! active)
{
if (++calls < callsmin) return;
(void) printf("JudyCheckPop() activated at call %lu\n", calls);
active = TRUE;
}
// START AT TOP OF TREE:
JAPtype = JAPTYPE(PArray);
switch (JAPtype)
{
case cJU_JAPNULL:
{
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
assert(Pjlw == (Pjlw_t) NULL); // rest of word must be null.
return; // valid null JAP.
}
#if (LOW_POP && JUDYL)
// Little or no pop checking is possible for these types, but see function
// header comments:
case cJL_JAPLEAF_POPU1: return;
case cJL_JAPLEAF_POPU2: return;
#endif
case cJU_JAPLEAF:
{
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
assert(*Pjlw + 1 <= cJU_JAPLEAF_MAXPOP1);
return;
}
// Check JPM pop0 against tree, recursively:
//
// Note: The traversal code in JudyCheckPopSM() is simplest when the case
// statement for each JP type compares the pop1 for that JP to its subtree (if
// any) after traversing the subtree (that's the hard part) and adding up
// actual pop1's. A top branch's JP in the JPM does not have room for a
// full-word pop1, so pass it in as a special case.
case cJU_JAPBRANCH:
{
Pjpm_t Pjpm = P_JPM(PArray);
(void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1);
return;
}
}
assert(FALSE); // unrecognized JAP type => corruption.
} // JudyCheckPop()
// ****************************************************************************
// J U D Y C H E C K P O P S M
//
// Recursive state machine (subroutine) for JudyCheckPop(): Given a Pjp (other
// than JPNULL*; caller should shortcut) and the root population for top-level
// branches, check the subtree's actual pop1 against its nominal value, and
// return the total pop1 for the subtree.
//
// Note: Expect RootPop1 to be ignored at lower levels, so pass down 0, which
// should pop an assertion if this expectation is violated.
FUNCTION static Word_t JudyCheckPopSM(
Pjp_t Pjp, // top of subtree.
Word_t RootPop1) // whole array, for top-level branches only.
{
Word_t pop1_jp; // nominal population from the JP.
Word_t pop1 = 0; // actual population at this level.
Word_t offset; // in a branch.
#define PREPBRANCH(cPopBytes,Next) \
pop1_jp = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, cPopBytes) + 1; goto Next
assert((((Word_t) (Pjp->jp_Addr)) & 7) == 3);
switch (Pjp->jp_Type)
{
case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL);
case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL);
#ifdef JU_64BIT
case cJU_JPBRANCH_L4: PREPBRANCH(4, BranchL);
case cJU_JPBRANCH_L5: PREPBRANCH(5, BranchL);
case cJU_JPBRANCH_L6: PREPBRANCH(6, BranchL);
case cJU_JPBRANCH_L7: PREPBRANCH(7, BranchL);
#endif
case cJU_JPBRANCH_L: pop1_jp = RootPop1;
{
Pjbl_t Pjbl;
BranchL:
Pjbl = P_JBL(Pjp->jp_Addr);
for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset)
pop1 += JudyCheckPopSM((Pjbl->jbl_jp) + offset, 0);
assert(pop1_jp == pop1);
return(pop1);
}
case cJU_JPBRANCH_B2: PREPBRANCH(2, BranchB);
case cJU_JPBRANCH_B3: PREPBRANCH(3, BranchB);
#ifdef JU_64BIT
case cJU_JPBRANCH_B4: PREPBRANCH(4, BranchB);
case cJU_JPBRANCH_B5: PREPBRANCH(5, BranchB);
case cJU_JPBRANCH_B6: PREPBRANCH(6, BranchB);
case cJU_JPBRANCH_B7: PREPBRANCH(7, BranchB);
#endif
case cJU_JPBRANCH_B: pop1_jp = RootPop1;
{
Word_t subexp;
Word_t jpcount;
Pjbb_t Pjbb;
BranchB:
Pjbb = P_JBB(Pjp->jp_Addr);
for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
{
jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
for (offset = 0; offset < jpcount; ++offset)
{
pop1 += JudyCheckPopSM(P_JP(JU_JBB_PJP(Pjbb, subexp))
+ offset, 0);
}
}
assert(pop1_jp == pop1);
return(pop1);
}
case cJU_JPBRANCH_U2: PREPBRANCH(2, BranchU);
case cJU_JPBRANCH_U3: PREPBRANCH(3, BranchU);
#ifdef JU_64BIT
case cJU_JPBRANCH_U4: PREPBRANCH(4, BranchU);
case cJU_JPBRANCH_U5: PREPBRANCH(5, BranchU);
case cJU_JPBRANCH_U6: PREPBRANCH(6, BranchU);
case cJU_JPBRANCH_U7: PREPBRANCH(7, BranchU);
#endif
case cJU_JPBRANCH_U: pop1_jp = RootPop1;
{
Pjbu_t Pjbu;
BranchU:
Pjbu = P_JBU(Pjp->jp_Addr);
for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
{
if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1)
&& ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX))
{
continue; // skip null JP to save time.
}
pop1 += JudyCheckPopSM((Pjbu->jbu_jp) + offset, 0);
}
assert(pop1_jp == pop1);
return(pop1);
}
// -- Cases below here terminate and do not recurse. --
//
// For all of these cases except JPLEAF_B1, there is no way to check the JP's
// pop1 against the object itself; just return the pop1; but for linear leaves,
// a bounds check is possible.
#define CHECKLEAF(MaxPop1) \
pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1; \
assert(pop1 >= 1); \
assert(pop1 <= (MaxPop1)); \
return(pop1)
#if (JUDYL || (! JU_64BIT ))
case cJU_JPLEAF1: CHECKLEAF(cJU_LEAF1_MAXPOP1);
#endif
case cJU_JPLEAF2: CHECKLEAF(cJU_LEAF2_MAXPOP1);
case cJU_JPLEAF3: CHECKLEAF(cJU_LEAF3_MAXPOP1);
#ifdef JU_64BIT
case cJU_JPLEAF4: CHECKLEAF(cJU_LEAF4_MAXPOP1);
case cJU_JPLEAF5: CHECKLEAF(cJU_LEAF5_MAXPOP1);
case cJU_JPLEAF6: CHECKLEAF(cJU_LEAF6_MAXPOP1);
case cJU_JPLEAF7: CHECKLEAF(cJU_LEAF7_MAXPOP1);
#endif
case cJU_JPLEAF_B1:
{
Word_t subexp;
Pjlb_t Pjlb;
pop1_jp = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
Pjlb = P_JLB(Pjp->jp_Addr);
for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
pop1 += __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
assert(pop1_jp == pop1);
return(pop1);
}
JUDY1CODE(case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0);)
case cJU_JPIMMED_1_01: return(1);
case cJU_JPIMMED_2_01: return(1);
case cJU_JPIMMED_3_01: return(1);
#ifdef JU_64BIT
case cJU_JPIMMED_4_01: return(1);
case cJU_JPIMMED_5_01: return(1);
case cJU_JPIMMED_6_01: return(1);
case cJU_JPIMMED_7_01: return(1);
#endif
case cJU_JPIMMED_1_02: return(2);
case cJU_JPIMMED_1_03: return(3);
#if (JUDY1 || JU_64BIT)
case cJU_JPIMMED_1_04: return(4);
case cJU_JPIMMED_1_05: return(5);
case cJU_JPIMMED_1_06: return(6);
case cJU_JPIMMED_1_07: return(7);
#endif
#if (JUDY1 && JU_64BIT)
case cJ1_JPIMMED_1_08: return(8);
case cJ1_JPIMMED_1_09: return(9);
case cJ1_JPIMMED_1_10: return(10);
case cJ1_JPIMMED_1_11: return(11);
case cJ1_JPIMMED_1_12: return(12);
case cJ1_JPIMMED_1_13: return(13);
case cJ1_JPIMMED_1_14: return(14);
case cJ1_JPIMMED_1_15: return(15);
#endif
#if (JUDY1 || JU_64BIT)
case cJU_JPIMMED_2_02: return(2);
case cJU_JPIMMED_2_03: return(3);
#endif
#if (JUDY1 && JU_64BIT)
case cJ1_JPIMMED_2_04: return(4);
case cJ1_JPIMMED_2_05: return(5);
case cJ1_JPIMMED_2_06: return(6);
case cJ1_JPIMMED_2_07: return(7);
#endif
#if (JUDY1 || JU_64BIT)
case cJU_JPIMMED_3_02: return(2);
#endif
#if (JUDY1 && JU_64BIT)
case cJ1_JPIMMED_3_03: return(3);
case cJ1_JPIMMED_3_04: return(4);
case cJ1_JPIMMED_3_05: return(5);
case cJ1_JPIMMED_4_02: return(2);
case cJ1_JPIMMED_4_03: return(3);
case cJ1_JPIMMED_5_02: return(2);
case cJ1_JPIMMED_5_03: return(3);
case cJ1_JPIMMED_6_02: return(2);
case cJ1_JPIMMED_7_02: return(2);
#endif
} // switch (Pjp->jp_Type)
assert(FALSE); // unrecognized JP type => corruption.
return(0); // to make some compilers happy.
} // JudyCheckPopSM()
#endif // DEBUG
#endif // ! JUDYGETINLINE
-------------
Found in src/JudyCommon/JudySearchLeaf.c (no idea about why I placed
them where I found them):
#ifdef DEBUG
// ****************************************************************************
// J U D Y C H E C K S O R T E D
//
// Given a pointer to a packed list of Pop1 N-byte indexes (N = IndexSize),
// assert that the list is in order.
FUNCTION void JudyCheckSorted(
Pjll_t Pjll, // leaf or list to check.
Word_t Pop1, // number of indexes to check.
long IndexSize) // bytes per index in list.
{
// Macros for common code:
//
// Check a list of "even"-sized indexes, counting backwards from last to first:
//
// Pjll and Pop1 are in the context.
#define JU_CHECKSORTED(PType) \
while (--Pop1 > 0) \
assert(((PType) Pjll)[Pop1 - 1] < ((PType) Pjll)[Pop1]); \
break
// Check a list of "odd"-sized indexes, which requires first copying each one
// to an aligned word:
//
// Pjll, Pop1, and IndexSize are in the context.
#define JU_CHECKSORTED_ODD(CopyIndex) \
{ \
Word_t indexlow; \
Word_t indexhigh; \
long offset; \
\
CopyIndex(indexlow, (uint8_t *) Pjll); \
\
for (offset = 1; offset < Pop1; ++offset) \
{ \
CopyIndex(indexhigh, \
((uint8_t *) Pjll) + (offset * IndexSize)); \
assert(indexlow < indexhigh); \
indexlow = indexhigh; \
} \
break; \
}
switch (IndexSize)
{
case 1: JU_CHECKSORTED(uint8_t *);
case 2: JU_CHECKSORTED(uint16_t *);
case 3: JU_CHECKSORTED_ODD(JU_COPY3_PINDEX_TO_LONG);
case 4: JU_CHECKSORTED(uint32_t *);
#ifdef JU_64BIT
case 5: JU_CHECKSORTED_ODD(JU_COPY5_PINDEX_TO_LONG);
case 6: JU_CHECKSORTED_ODD(JU_COPY6_PINDEX_TO_LONG);
case 7: JU_CHECKSORTED_ODD(JU_COPY7_PINDEX_TO_LONG);
case 8: JU_CHECKSORTED(Pjlw_t);
#endif
default: assert(FALSE); // invalid IndexSize.
}
} // JudyCheckSorted()
#endif // DEBUG
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
