path: root/libnetdata/libjudy/src/JudyL/JudyLCount.c

// 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.78 $ $Source: /judy/src/JudyCommon/JudyCount.c $
//
// Judy*Count() function for Judy1 and JudyL.
// Compile with one of -DJUDY1 or -DJUDYL.
//
// Compile with -DNOSMARTJBB, -DNOSMARTJBU, and/or -DNOSMARTJLB to build a
// version with cache line optimizations deleted, for testing.
//
// Compile with -DSMARTMETRICS to obtain global variables containing smart
// cache line metrics.  Note:  Dont turn this on simultaneously for this file
// and JudyByCount.c because they export the same globals.
//
// Judy*Count() returns the "count of Indexes" (inclusive) between the two
// specified limits (Indexes).  This code is remarkably fast.  It traverses the
// "Judy array" data structure.
//
// This count code is the GENERIC untuned version (minimum code size).  It
// might be possible to tuned to a specific architecture to be faster.
// However, in real applications, with a modern machine, it is expected that
// the instruction times will be swamped by cache line fills.
// ****************************************************************************

#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"


// define a phoney that is for sure

#define cJU_LEAFW       cJU_JPIMMED_CAP

// Avoid duplicate symbols since this file is multi-compiled:

#ifdef SMARTMETRICS
#ifdef JUDY1
Word_t jbb_upward   = 0;	// counts of directions taken:
Word_t jbb_downward = 0;
Word_t jbu_upward   = 0;
Word_t jbu_downward = 0;
Word_t jlb_upward   = 0;
Word_t jlb_downward = 0;
#else
extern Word_t jbb_upward;
extern Word_t jbb_downward;
extern Word_t jbu_upward;
extern Word_t jbu_downward;
extern Word_t jlb_upward;
extern Word_t jlb_downward;
#endif
#endif


// FORWARD DECLARATIONS (prototypes):

static	Word_t j__udy1LCountSM(const Pjp_t Pjp, const Word_t Index,
			       const Pjpm_t Pjpm);

// Each of Judy1 and JudyL get their own private (static) version of this
// function:

static	int j__udyCountLeafB1(const Pjll_t Pjll, const Word_t Pop1,
			      const Word_t Index);

// These functions are not static because they are exported to Judy*ByCount():
//
// TBD:  Should be made static for performance reasons?  And thus duplicated?
//
// Note:  There really are two different functions, but for convenience they
// are referred to here with a generic name.

#ifdef JUDY1
#define	j__udyJPPop1 j__udy1JPPop1
#else
#define	j__udyJPPop1 j__udyLJPPop1
#endif

Word_t j__udyJPPop1(const Pjp_t Pjp);


// LOCAL ERROR HANDLING:
//
// The Judy*Count() functions are unusual because they return 0 instead of JERR
// for an error.  In this source file, define C_JERR for clarity.

#define	C_JERR 0


// ****************************************************************************
// J U D Y   1   C O U N T
// J U D Y   L   C O U N T
//
// See the manual entry for details.
//
// This code is written recursively, at least at first, because thats much
// simpler; hope its fast enough.

#ifdef JUDY1
FUNCTION Word_t Judy1Count
#else
FUNCTION Word_t JudyLCount
#endif
        (
	Pcvoid_t  PArray,	// JRP to first branch/leaf in SM.
	Word_t	  Index1,	// starting Index.
	Word_t	  Index2,	// ending Index.
	PJError_t PJError	// optional, for returning error info.
        )
{
	jpm_t	  fakejpm;	// local temporary for small arrays.
	Pjpm_t	  Pjpm;		// top JPM or local temporary for error info.
	jp_t	  fakejp;	// constructed for calling j__udy1LCountSM().
	Pjp_t	  Pjp;		// JP to pass to j__udy1LCountSM().
	Word_t	  pop1;		// total for the array.
	Word_t	  pop1above1;	// indexes at or above Index1, inclusive.
	Word_t	  pop1above2;	// indexes at or above Index2, exclusive.
	int	  retcode;	// from Judy*First() calls.
JUDYLCODE(PPvoid_t PPvalue);	// from JudyLFirst() calls.


// CHECK FOR SHORTCUTS:
//
// As documented, return C_JERR if the Judy array is empty or Index1 > Index2.

	if ((PArray == (Pvoid_t) NULL) || (Index1 > Index2))
	{
	    JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
	    return(C_JERR);
	}

// If Index1 == Index2, simply check if the specified Index is set; pass
// through the return value from Judy1Test() or JudyLGet() with appropriate
// translations.

	if (Index1 == Index2)
	{
#ifdef JUDY1
	    retcode = Judy1Test(PArray, Index1, PJError);

	    if (retcode == JERRI) return(C_JERR);	// pass through error.

	    if (retcode == 0)
	    {
		JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
		return(C_JERR);
	    }
#else
	    PPvalue = JudyLGet(PArray, Index1, PJError);

	    if (PPvalue == PPJERR) return(C_JERR);	// pass through error.

	    if (PPvalue == (PPvoid_t) NULL)		// Index is not set.
	    {
		JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
		return(C_JERR);
	    }
#endif
	    return(1);					// single index is set.
	}


// CHECK JRP TYPE:
//
// Use an if/then for speed rather than a switch, and put the most common cases
// first.
//
// Note:  Since even cJU_LEAFW types require counting between two Indexes,
// prepare them here for common code below that calls j__udy1LCountSM(), rather
// than handling them even more specially here.

	if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
	{
	    Pjlw_t Pjlw	   = P_JLW(PArray);	// first word of leaf.
	    Pjpm	   = & fakejpm;
	    Pjp		   = & fakejp;
	    Pjp->jp_Addr   = (Word_t) Pjlw;
	    Pjp->jp_Type   = cJU_LEAFW;
	    Pjpm->jpm_Pop0 = Pjlw[0];		// from first word of leaf.
	    pop1	   = Pjpm->jpm_Pop0 + 1;
	}
	else
	{
	    Pjpm = P_JPM(PArray);
	    Pjp	 = &(Pjpm->jpm_JP);
	    pop1 = (Pjpm->jpm_Pop0) + 1;	// note: can roll over to 0.

#if (defined(JUDY1) && (! defined(JU_64BIT)))
	    if (pop1 == 0)		// rare special case of full array:
	    {
		Word_t count = Index2 - Index1 + 1;	// can roll over again.

		if (count == 0)
		{
		    JU_SET_ERRNO(PJError, JU_ERRNO_FULL);
		    return(C_JERR);
		}
		return(count);
	    }
#else
	    assert(pop1);	// JudyL or 64-bit cannot create a full array!
#endif
	}


// COUNT POP1 ABOVE INDEX1, INCLUSIVE:

	assert(pop1);		// just to be safe.

	if (Index1 == 0)	// shortcut, pop1above1 is entire population:
	{
	    pop1above1 = pop1;
	}
	else			// find first valid Index above Index1, if any:
	{
#ifdef JUDY1
	    if ((retcode = Judy1First(PArray, & Index1, PJError)) == JERRI)
		return(C_JERR);			// pass through error.
#else
	    if ((PPvalue = JudyLFirst(PArray, & Index1, PJError)) == PPJERR)
		return(C_JERR);			// pass through error.

	    retcode = (PPvalue != (PPvoid_t) NULL);	// found a next Index.
#endif

// If theres no Index at or above Index1, just return C_JERR (early exit):

	    if (retcode == 0)
	    {
		JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
		return(C_JERR);
	    }

// If a first/next Index was found, call the counting motor starting with that
// known valid Index, meaning the return should be positive, not C_JERR except
// in case of a real error:

	    if ((pop1above1 = j__udy1LCountSM(Pjp, Index1, Pjpm)) == C_JERR)
	    {
		JU_COPY_ERRNO(PJError, Pjpm);	// pass through error.
		return(C_JERR);
	    }
	}


// COUNT POP1 ABOVE INDEX2, EXCLUSIVE, AND RETURN THE DIFFERENCE:
//
// In principle, calculate the ordinal of each Index and take the difference,
// with caution about off-by-one errors due to the specified Indexes being set
// or unset.  In practice:
//
// - The ordinals computed here are inverse ordinals, that is, the populations
//   ABOVE the specified Indexes (Index1 inclusive, Index2 exclusive), so
//   subtract pop1above2 from pop1above1, rather than vice-versa.
//
// - Index1s result already includes a count for Index1 and/or Index2 if
//   either is set, so calculate pop1above2 exclusive of Index2.
//
// TBD:  If Index1 and Index2 fall in the same expanse in the top-state
// branch(es), would it be faster to walk the SM only once, to their divergence
// point, before calling j__udy1LCountSM() or equivalent?  Possibly a non-issue
// if a top-state pop1 becomes stored with each Judy1 array.  Also, consider
// whether the first call of j__udy1LCountSM() fills the cache, for common tree
// branches, for the second call.
//
// As for pop1above1, look for shortcuts for special cases when pop1above2 is
// zero.  Otherwise call the counting "motor".

	    assert(pop1above1);		// just to be safe.

	    if (Index2++ == cJU_ALLONES) return(pop1above1); // Index2 at limit.

#ifdef JUDY1
	    if ((retcode = Judy1First(PArray, & Index2, PJError)) == JERRI)
		return(C_JERR);
#else
	    if ((PPvalue = JudyLFirst(PArray, & Index2, PJError)) == PPJERR)
		return(C_JERR);

	    retcode = (PPvalue != (PPvoid_t) NULL);	// found a next Index.
#endif
	    if (retcode == 0) return(pop1above1);  // no Index above Index2.

// Just as for Index1, j__udy1LCountSM() cannot return 0 (locally == C_JERR)
// except in case of a real error:

	    if ((pop1above2 = j__udy1LCountSM(Pjp, Index2, Pjpm)) == C_JERR)
	    {
		JU_COPY_ERRNO(PJError, Pjpm);		// pass through error.
		return(C_JERR);
	    }

	    if (pop1above1 == pop1above2)
	    {
		JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
		return(C_JERR);
	    }

	    return(pop1above1 - pop1above2);

} // Judy1Count() / JudyLCount()


// ****************************************************************************
// __ J U D Y 1 L   C O U N T   S M
//
// Given a pointer to a JP (with invalid jp_DcdPopO at cJU_ROOTSTATE), a known
// valid Index, and a Pjpm for returning error info, recursively visit a Judy
// array state machine (SM) and return the count of Indexes, including Index,
// through the end of the Judy array at this state or below.  In case of error
// or a count of 0 (should never happen), return C_JERR with appropriate
// JU_ERRNO in the Pjpm.
//
// Note:  This function is not told the current state because its encoded in
// the JP Type.
//
// Method:  To minimize cache line fills, while studying each branch, if Index
// resides above the midpoint of the branch (which often consists of multiple
// cache lines), ADD the populations at or above Index; otherwise, SUBTRACT
// from the population of the WHOLE branch (available from the JP) the
// populations at or above Index.  This is especially tricky for bitmap
// branches.
//
// Note:  Unlike, say, the Ins and Del walk routines, this function returns the
// same type of returns as Judy*Count(), so it can use *_SET_ERRNO*() macros
// the same way.

FUNCTION static Word_t j__udy1LCountSM(
const	Pjp_t	Pjp,		// top of Judy (sub)SM.
const	Word_t	Index,		// count at or above this Index.
const	Pjpm_t	Pjpm)		// for returning error info.
{
	Pjbl_t	Pjbl;		// Pjp->jp_Addr masked and cast to types:
	Pjbb_t	Pjbb;
	Pjbu_t	Pjbu;
	Pjll_t	Pjll;		// a Judy lower-level linear leaf.

	Word_t	digit;		// next digit to decode from Index.
	long	jpnum;		// JP number in a branch (base 0).
	int	offset;		// index ordinal within a leaf, base 0.
	Word_t	pop1;		// total population of an expanse.
	Word_t	pop1above;	// to return.

// Common code to check Decode bits in a JP against the equivalent portion of
// Index; XOR together, then mask bits of interest; must be all 0:
//
// Note:  Why does this code only assert() compliance rather than actively
// checking for outliers?  Its because Index is supposed to be valid, hence
// always match any Dcd bits traversed.
//
// Note:  This assertion turns out to be always true for cState = 3 on 32-bit
// and 7 on 64-bit, but its harmless, probably removed by the compiler.

#define	CHECKDCD(Pjp,cState) \
	assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cState))

// Common code to prepare to handle a root-level or lower-level branch:
// Extract a state-dependent digit from Index in a "constant" way, obtain the
// total population for the branch in a state-dependent way, and then branch to
// common code for multiple cases:
//
// For root-level branches, the state is always cJU_ROOTSTATE, and the
// population is received in Pjpm->jpm_Pop0.
//
// Note:  The total population is only needed in cases where the common code
// "counts up" instead of down to minimize cache line fills.  However, its
// available cheaply, and its better to do it with a constant shift (constant
// state value) instead of a variable shift later "when needed".

#define	PREPB_ROOT(Pjp,Next)				\
	digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);	\
	pop1  = (Pjpm->jpm_Pop0) + 1;			\
	goto Next

#define	PREPB(Pjp,cState,Next)				\
	digit = JU_DIGITATSTATE(Index, cState);		\
	pop1  = JU_JPBRANCH_POP0(Pjp, (cState)) + 1;    \
	goto Next


// SWITCH ON JP TYPE:
//
// WARNING:  For run-time efficiency the following cases replicate code with
// varying constants, rather than using common code with variable values!

	switch (JU_JPTYPE(Pjp))
	{


// ----------------------------------------------------------------------------
// ROOT-STATE LEAF that starts with a Pop0 word; just count within the leaf:

	case cJU_LEAFW:
	{
	    Pjlw_t Pjlw = P_JLW(Pjp->jp_Addr);		// first word of leaf.

	    assert((Pjpm->jpm_Pop0) + 1 == Pjlw[0] + 1);  // sent correctly.
	    offset = j__udySearchLeafW(Pjlw + 1, Pjpm->jpm_Pop0 + 1, Index);
	    assert(offset >= 0);			// Index must exist.
	    assert(offset < (Pjpm->jpm_Pop0) + 1);	// Index be in range.
	    return((Pjpm->jpm_Pop0) + 1 - offset);	// INCLUSIVE of Index.
	}

// ----------------------------------------------------------------------------
// LINEAR BRANCH; count populations in JPs in the JBL ABOVE the next digit in
// Index, and recurse for the next digit in Index:
//
// Note:  There are no null JPs in a JBL; watch out for pop1 == 0.
//
// Note:  A JBL should always fit in one cache line => no need to count up
// versus down to save cache line fills.  (PREPB() sets pop1 for no reason.)

	case cJU_JPBRANCH_L2:  CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchL);
	case cJU_JPBRANCH_L3:  CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchL);

#ifdef JU_64BIT
	case cJU_JPBRANCH_L4:  CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchL);
	case cJU_JPBRANCH_L5:  CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchL);
	case cJU_JPBRANCH_L6:  CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchL);
	case cJU_JPBRANCH_L7:  CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchL);
#endif
	case cJU_JPBRANCH_L:   PREPB_ROOT(Pjp, BranchL);

// Common code (state-independent) for all cases of linear branches:

BranchL:

	Pjbl      = P_JBL(Pjp->jp_Addr);
	jpnum     = Pjbl->jbl_NumJPs;			// above last JP.
	pop1above = 0;

	while (digit < (Pjbl->jbl_Expanse[--jpnum]))	 // still ABOVE digit.
	{
	    if ((pop1 = j__udyJPPop1((Pjbl->jbl_jp) + jpnum)) == cJU_ALLONES)
	    {
		JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
		return(C_JERR);
	    }

	    pop1above += pop1;
	    assert(jpnum > 0);				// should find digit.
	}

	assert(digit == (Pjbl->jbl_Expanse[jpnum]));	// should find digit.

	pop1 = j__udy1LCountSM((Pjbl->jbl_jp) + jpnum, Index, Pjpm);
	if (pop1 == C_JERR) return(C_JERR);		// pass error up.

	assert(pop1above + pop1);
	return(pop1above + pop1);


// ----------------------------------------------------------------------------
// BITMAP BRANCH; count populations in JPs in the JBB ABOVE the next digit in
// Index, and recurse for the next digit in Index:
//
// Note:  There are no null JPs in a JBB; watch out for pop1 == 0.

	case cJU_JPBRANCH_B2:  CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchB);
	case cJU_JPBRANCH_B3:  CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchB);
#ifdef JU_64BIT
	case cJU_JPBRANCH_B4:  CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchB);
	case cJU_JPBRANCH_B5:  CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchB);
	case cJU_JPBRANCH_B6:  CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchB);
	case cJU_JPBRANCH_B7:  CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchB);
#endif
	case cJU_JPBRANCH_B:   PREPB_ROOT(Pjp, BranchB);

// Common code (state-independent) for all cases of bitmap branches:

BranchB:
	{
	    long   subexp;	// for stepping through layer 1 (subexpanses).
	    long   findsub;	// subexpanse containing   Index (digit).
	    Word_t findbit;	// bit	      representing Index (digit).
	    Word_t lowermask;	// bits for indexes at or below Index.
	    Word_t jpcount;	// JPs in a subexpanse.
	    Word_t clbelow;	// cache lines below digits cache line.
	    Word_t clabove;	// cache lines above digits cache line.

	    Pjbb      = P_JBB(Pjp->jp_Addr);
	    findsub   = digit / cJU_BITSPERSUBEXPB;
	    findbit   = digit % cJU_BITSPERSUBEXPB;
	    lowermask = JU_MASKLOWERINC(JU_BITPOSMASKB(findbit));
	    clbelow   = clabove = 0;	// initial/default => always downward.

	    assert(JU_BITMAPTESTB(Pjbb, digit)); // digit must have a JP.
	    assert(findsub < cJU_NUMSUBEXPB);	 // falls in expected range.

// Shorthand for one subexpanse in a bitmap and for one JP in a bitmap branch:
//
// Note: BMPJP0 exists separately to support assertions.

#define	BMPJP0(Subexp)       (P_JP(JU_JBB_PJP(Pjbb, Subexp)))
#define	BMPJP(Subexp,JPnum)  (BMPJP0(Subexp) + (JPnum))

#ifndef NOSMARTJBB  // enable to turn off smart code for comparison purposes.

// FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1s
// in JPs above Indexs JP, or subtracting the pop1s in JPs below Indexs JP.
//
// This is tricky because, while each set bit in the bitmap represents a JP,
// the JPs are scattered over cJU_NUMSUBEXPB subexpanses, each of which can
// contain JPs packed into multiple cache lines, and this code must visit every
// JP either BELOW or ABOVE the JP for Index.
//
// Number of cache lines required to hold a linear list of the given number of
// JPs, assuming the first JP is at the start of a cache line or the JPs in
// jpcount fit wholly within a single cache line, which is ensured by
// JudyMalloc():

#define	CLPERJPS(jpcount) \
	((((jpcount) * cJU_WORDSPERJP) + cJU_WORDSPERCL - 1) / cJU_WORDSPERCL)

// Count cache lines below/above for each subexpanse:

	    for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
	    {
		jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));

// When at the subexpanse containing Index (digit), add cache lines
// below/above appropriately, excluding the cache line containing the JP for
// Index itself:

		if	(subexp <  findsub)  clbelow += CLPERJPS(jpcount);
		else if (subexp >  findsub)  clabove += CLPERJPS(jpcount);
		else // (subexp == findsub)
		{
		    Word_t clfind;	// cache line containing Index (digit).

		    clfind = CLPERJPS(j__udyCountBitsB(
				    JU_JBB_BITMAP(Pjbb, subexp) & lowermask));

		    assert(clfind > 0);	 // digit itself should have 1 CL.
		    clbelow += clfind - 1;
		    clabove += CLPERJPS(jpcount) - clfind;
		}
	    }
#endif // ! NOSMARTJBB

// Note:  Its impossible to get through the following "if" without setting
// jpnum -- see some of the assertions below -- but gcc -Wall doesnt know
// this, so preset jpnum to make it happy:

	    jpnum = 0;


// COUNT POPULATION FOR A BITMAP BRANCH, in whichever direction should result
// in fewer cache line fills:
//
// Note:  If the remainder of Index is zero, pop1above is the pop1 of the
// entire expanse and theres no point in recursing to lower levels; but this
// should be so rare that its not worth checking for;
// Judy1Count()/JudyLCount() never even calls the motor for Index == 0 (all
// bytes).


// COUNT UPWARD, subtracting each "below or at" JPs pop1 from the whole
// expanses pop1:
//
// Note:  If this causes clbelow + 1 cache line fills including JPs cache
// line, thats OK; at worst this is the same as clabove.

	    if (clbelow < clabove)
	    {
#ifdef SMARTMETRICS
		++jbb_upward;
#endif
		pop1above = pop1;		// subtract JPs at/below Index.

// Count JPs for which to accrue pop1s in this subexpanse:
//
// TBD:  If JU_JBB_BITMAP is cJU_FULLBITMAPB, dont bother counting.

		for (subexp = 0; subexp <= findsub; ++subexp)
		{
		    jpcount = j__udyCountBitsB((subexp < findsub) ?
				      JU_JBB_BITMAP(Pjbb, subexp) :
				      JU_JBB_BITMAP(Pjbb, subexp) & lowermask);

		    // should always find findbit:
		    assert((subexp < findsub) || jpcount);

// Subtract pop1s from JPs BELOW OR AT Index (digit):
//
// Note:  The pop1 for Indexs JP itself is partially added back later at a
// lower state.
//
// Note:  An empty subexpanse (jpcount == 0) is handled "for free".
//
// Note:  Must be null JP subexp pointer in empty subexpanse and non-empty in
// non-empty subexpanse:

		    assert(   jpcount  || (BMPJP0(subexp) == (Pjp_t) NULL));
		    assert((! jpcount) || (BMPJP0(subexp) != (Pjp_t) NULL));

		    for (jpnum = 0; jpnum < jpcount; ++jpnum)
		    {
			if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum)))
			    == cJU_ALLONES)
			{
			    JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
			    return(C_JERR);
			}

			pop1above -= pop1;
		    }

		    jpnum = jpcount - 1;	// make correct for digit.
		}
	    }

// COUNT DOWNWARD, adding each "above" JPs pop1:

	    else
	    {
		long jpcountbf;			// below findbit, inclusive.
#ifdef SMARTMETRICS
		++jbb_downward;
#endif
		pop1above = 0;			// add JPs above Index.
		jpcountbf = 0;			// until subexp == findsub.

// Count JPs for which to accrue pop1s in this subexpanse:
//
// This is more complicated than counting upward because the scan of digits
// subexpanse must count ALL JPs, to know where to START counting down, and
// ALSO note the offset of digits JP to know where to STOP counting down.

		for (subexp = cJU_NUMSUBEXPB - 1; subexp >= findsub; --subexp)
		{
		    jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));

		    // should always find findbit:
		    assert((subexp > findsub) || jpcount);

		    if (! jpcount) continue;	// empty subexpanse, save time.

// Count JPs below digit, inclusive:

		    if (subexp == findsub)
		    {
			jpcountbf = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)
						  & lowermask);
		    }

		    // should always find findbit:
		    assert((subexp > findsub) || jpcountbf);
		    assert(jpcount >= jpcountbf);	// proper relationship.

// Add pop1s from JPs ABOVE Index (digit):

		    // no null JP subexp pointers:
		    assert(BMPJP0(subexp) != (Pjp_t) NULL);

		    for (jpnum = jpcount - 1; jpnum >= jpcountbf; --jpnum)
		    {
			if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum)))
			    == cJU_ALLONES)
			{
			    JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
			    return(C_JERR);
			}

			pop1above += pop1;
		    }
		    // jpnum is now correct for digit.
		}
	    } // else.

// Return the net population ABOVE the digits JP at this state (in this JBB)
// plus the population AT OR ABOVE Index in the SM under the digits JP:

	    pop1 = j__udy1LCountSM(BMPJP(findsub, jpnum), Index, Pjpm);
	    if (pop1 == C_JERR) return(C_JERR);		// pass error up.

	    assert(pop1above + pop1);
	    return(pop1above + pop1);

	} // case.


// ----------------------------------------------------------------------------
// UNCOMPRESSED BRANCH; count populations in JPs in the JBU ABOVE the next
// digit in Index, and recurse for the next digit in Index:
//
// Note:  If the remainder of Index is zero, pop1above is the pop1 of the
// entire expanse and theres no point in recursing to lower levels; but this
// should be so rare that its not worth checking for;
// Judy1Count()/JudyLCount() never even calls the motor for Index == 0 (all
// bytes).

	case cJU_JPBRANCH_U2:  CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchU);
	case cJU_JPBRANCH_U3:  CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchU);
#ifdef JU_64BIT
	case cJU_JPBRANCH_U4:  CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchU);
	case cJU_JPBRANCH_U5:  CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchU);
	case cJU_JPBRANCH_U6:  CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchU);
	case cJU_JPBRANCH_U7:  CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchU);
#endif
	case cJU_JPBRANCH_U:   PREPB_ROOT(Pjp, BranchU);

// Common code (state-independent) for all cases of uncompressed branches:

BranchU:
	    Pjbu = P_JBU(Pjp->jp_Addr);

#ifndef NOSMARTJBU  // enable to turn off smart code for comparison purposes.

// FIGURE OUT WHICH WAY CAUSES FEWER CACHE LINE FILLS; adding the JPs above
// Indexs JP, or subtracting the JPs below Indexs JP.
//
// COUNT UPWARD, subtracting the pop1 of each JP BELOW OR AT Index, from the
// whole expanses pop1:

	    if (digit < (cJU_BRANCHUNUMJPS / 2))
	    {
		pop1above = pop1;		// subtract JPs below Index.
#ifdef SMARTMETRICS
		++jbu_upward;
#endif
		for (jpnum = 0; jpnum <= digit; ++jpnum)
		{
		    if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
			continue;	// shortcut, save a function call.

		    if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum))
		     == cJU_ALLONES)
		    {
			JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
			return(C_JERR);
		    }

		    pop1above -= pop1;
		}
	    }

// COUNT DOWNWARD, simply adding the pop1 of each JP ABOVE Index:

	    else
#endif // NOSMARTJBU
	    {
		assert(digit < cJU_BRANCHUNUMJPS);
#ifdef SMARTMETRICS
		++jbu_downward;
#endif
		pop1above = 0;			// add JPs above Index.

		for (jpnum = cJU_BRANCHUNUMJPS - 1; jpnum > digit; --jpnum)
		{
		    if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
			continue;	// shortcut, save a function call.

		    if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum))
		     == cJU_ALLONES)
		    {
			JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
			return(C_JERR);
		    }

		    pop1above += pop1;
		}
	    }

	    if ((pop1 = j__udy1LCountSM(Pjbu->jbu_jp + digit, Index, Pjpm))
	     == C_JERR) return(C_JERR);		// pass error up.

	    assert(pop1above + pop1);
	    return(pop1above + pop1);


// ----------------------------------------------------------------------------
// LEAF COUNT MACROS:
//
// LEAF*ABOVE() are common code for different JP types (linear leaves, bitmap
// leaves, and immediates) and different leaf Index Sizes, which result in
// calling different leaf search functions.  Linear leaves get the leaf address
// from jp_Addr and the Population from jp_DcdPopO, while immediates use Pjp
// itself as the leaf address and get Population from jp_Type.

#define	LEAFLABOVE(Func)				\
	Pjll = P_JLL(Pjp->jp_Addr);			\
	pop1 = JU_JPLEAF_POP0(Pjp) + 1;	                \
	LEAFABOVE(Func, Pjll, pop1)

#define	LEAFB1ABOVE(Func) LEAFLABOVE(Func)  // different Func, otherwise same.

#ifdef JUDY1
#define	IMMABOVE(Func,Pop1)	\
	Pjll = (Pjll_t) Pjp;	\
	LEAFABOVE(Func, Pjll, Pop1)
#else
// Note:  For JudyL immediates with >= 2 Indexes, the index bytes are in a
// different place than for Judy1:

#define	IMMABOVE(Func,Pop1) \
	LEAFABOVE(Func, (Pjll_t) (Pjp->jp_LIndex), Pop1)
#endif

// For all leaf types, the population AT OR ABOVE is the total pop1 less the
// offset of Index; and Index should always be found:

#define	LEAFABOVE(Func,Pjll,Pop1)		\
	offset = Func(Pjll, Pop1, Index);	\
	assert(offset >= 0);			\
	assert(offset < (Pop1));		\
	return((Pop1) - offset)

// IMMABOVE_01 handles the special case of an immediate JP with 1 index, which
// the search functions arent used for anyway:
//
// The target Index should be the one in this Immediate, in which case the
// count above (inclusive) is always 1.

#define	IMMABOVE_01						\
	assert((JU_JPDCDPOP0(Pjp)) == JU_TRIMTODCDSIZE(Index));	\
	return(1)


// ----------------------------------------------------------------------------
// LINEAR LEAF; search the leaf for Index; size is computed from jp_Type:

#if (defined(JUDYL) || (! defined(JU_64BIT)))
	case cJU_JPLEAF1:  LEAFLABOVE(j__udySearchLeaf1);
#endif
	case cJU_JPLEAF2:  LEAFLABOVE(j__udySearchLeaf2);
	case cJU_JPLEAF3:  LEAFLABOVE(j__udySearchLeaf3);

#ifdef JU_64BIT
	case cJU_JPLEAF4:  LEAFLABOVE(j__udySearchLeaf4);
	case cJU_JPLEAF5:  LEAFLABOVE(j__udySearchLeaf5);
	case cJU_JPLEAF6:  LEAFLABOVE(j__udySearchLeaf6);
	case cJU_JPLEAF7:  LEAFLABOVE(j__udySearchLeaf7);
#endif


// ----------------------------------------------------------------------------
// BITMAP LEAF; search the leaf for Index:
//
// Since the bitmap describes Indexes digitally rather than linearly, this is
// not really a search, but just a count.

	case cJU_JPLEAF_B1:  LEAFB1ABOVE(j__udyCountLeafB1);


#ifdef JUDY1
// ----------------------------------------------------------------------------
// FULL POPULATION:
//
// Return the count of Indexes AT OR ABOVE Index, which is the total population
// of the expanse (a constant) less the value of the undecoded digit remaining
// in Index (its base-0 offset in the expanse), which yields an inclusive count
// above.
//
// TBD:  This only supports a 1-byte full expanse.  Should this extract a
// stored value for pop0 and possibly more LSBs of Index, to handle larger full
// expanses?

	case cJ1_JPFULLPOPU1:
	    return(cJU_JPFULLPOPU1_POP0 + 1 - JU_DIGITATSTATE(Index, 1));
#endif


// ----------------------------------------------------------------------------
// IMMEDIATE:

	case cJU_JPIMMED_1_01:  IMMABOVE_01;
	case cJU_JPIMMED_2_01:  IMMABOVE_01;
	case cJU_JPIMMED_3_01:  IMMABOVE_01;
#ifdef JU_64BIT
	case cJU_JPIMMED_4_01:  IMMABOVE_01;
	case cJU_JPIMMED_5_01:  IMMABOVE_01;
	case cJU_JPIMMED_6_01:  IMMABOVE_01;
	case cJU_JPIMMED_7_01:  IMMABOVE_01;
#endif

	case cJU_JPIMMED_1_02:  IMMABOVE(j__udySearchLeaf1,  2);
	case cJU_JPIMMED_1_03:  IMMABOVE(j__udySearchLeaf1,  3);
#if (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_1_04:  IMMABOVE(j__udySearchLeaf1,  4);
	case cJU_JPIMMED_1_05:  IMMABOVE(j__udySearchLeaf1,  5);
	case cJU_JPIMMED_1_06:  IMMABOVE(j__udySearchLeaf1,  6);
	case cJU_JPIMMED_1_07:  IMMABOVE(j__udySearchLeaf1,  7);
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
	case cJ1_JPIMMED_1_08:  IMMABOVE(j__udySearchLeaf1,  8);
	case cJ1_JPIMMED_1_09:  IMMABOVE(j__udySearchLeaf1,  9);
	case cJ1_JPIMMED_1_10:  IMMABOVE(j__udySearchLeaf1, 10);
	case cJ1_JPIMMED_1_11:  IMMABOVE(j__udySearchLeaf1, 11);
	case cJ1_JPIMMED_1_12:  IMMABOVE(j__udySearchLeaf1, 12);
	case cJ1_JPIMMED_1_13:  IMMABOVE(j__udySearchLeaf1, 13);
	case cJ1_JPIMMED_1_14:  IMMABOVE(j__udySearchLeaf1, 14);
	case cJ1_JPIMMED_1_15:  IMMABOVE(j__udySearchLeaf1, 15);
#endif

#if (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_2_02:  IMMABOVE(j__udySearchLeaf2,  2);
	case cJU_JPIMMED_2_03:  IMMABOVE(j__udySearchLeaf2,  3);
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
	case cJ1_JPIMMED_2_04:  IMMABOVE(j__udySearchLeaf2,  4);
	case cJ1_JPIMMED_2_05:  IMMABOVE(j__udySearchLeaf2,  5);
	case cJ1_JPIMMED_2_06:  IMMABOVE(j__udySearchLeaf2,  6);
	case cJ1_JPIMMED_2_07:  IMMABOVE(j__udySearchLeaf2,  7);
#endif

#if (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_3_02:  IMMABOVE(j__udySearchLeaf3,  2);
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
	case cJ1_JPIMMED_3_03:  IMMABOVE(j__udySearchLeaf3,  3);
	case cJ1_JPIMMED_3_04:  IMMABOVE(j__udySearchLeaf3,  4);
	case cJ1_JPIMMED_3_05:  IMMABOVE(j__udySearchLeaf3,  5);

	case cJ1_JPIMMED_4_02:  IMMABOVE(j__udySearchLeaf4,  2);
	case cJ1_JPIMMED_4_03:  IMMABOVE(j__udySearchLeaf4,  3);

	case cJ1_JPIMMED_5_02:  IMMABOVE(j__udySearchLeaf5,  2);
	case cJ1_JPIMMED_5_03:  IMMABOVE(j__udySearchLeaf5,  3);

	case cJ1_JPIMMED_6_02:  IMMABOVE(j__udySearchLeaf6,  2);

	case cJ1_JPIMMED_7_02:  IMMABOVE(j__udySearchLeaf7,  2);
#endif


// ----------------------------------------------------------------------------
// OTHER CASES:

	default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(C_JERR);

	} // switch on JP type

	/*NOTREACHED*/

} // j__udy1LCountSM()


// ****************************************************************************
// J U D Y   C O U N T   L E A F   B 1
//
// This is a private analog of the j__udySearchLeaf*() functions for counting
// in bitmap 1-byte leaves.  Since a bitmap leaf describes Indexes digitally
// rather than linearly, this is not really a search, but just a count of the
// valid Indexes == set bits below or including Index, which should be valid.
// Return the "offset" (really the ordinal), 0 .. Pop1 - 1, of Index in Pjll;
// if Indexs bit is not set (which should never happen, so this is DEBUG-mode
// only), return the 1s-complement equivalent (== negative offset minus 1).
//
// Note:  The source code for this function looks identical for both Judy1 and
// JudyL, but the JU_JLB_BITMAP macro varies.
//
// Note:  For simpler calling, the first arg is of type Pjll_t but then cast to
// Pjlb_t.

FUNCTION static int j__udyCountLeafB1(
const	Pjll_t	Pjll,		// bitmap leaf, as Pjll_t for consistency.
const	Word_t	Pop1,		// Population of whole leaf.
const	Word_t	Index)		// to which to count.
{
	Pjlb_t	Pjlb	= (Pjlb_t) Pjll;	// to proper type.
	Word_t	digit   = Index & cJU_MASKATSTATE(1);
	Word_t	findsub = digit / cJU_BITSPERSUBEXPL;
	Word_t	findbit = digit % cJU_BITSPERSUBEXPL;
	int	count;		// in leaf through Index.
	long	subexp;		// for stepping through subexpanses.


// COUNT UPWARD:
//
// The entire bitmap should fit in one cache line, but still try to save some
// CPU time by counting the fewest possible number of subexpanses from the
// bitmap.

#ifndef NOSMARTJLB  // enable to turn off smart code for comparison purposes.

	if (findsub < (cJU_NUMSUBEXPL / 2))
	{
#ifdef SMARTMETRICS
	    ++jlb_upward;
#endif
	    count = 0;

	    for (subexp = 0; subexp < findsub; ++subexp)
	    {
		count += ((JU_JLB_BITMAP(Pjlb, subexp) == cJU_FULLBITMAPL) ?
			  cJU_BITSPERSUBEXPL :
			  j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp)));
	    }

// This count includes findbit, which should be set, resulting in a base-1
// offset:

	    count += j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, findsub)
				& JU_MASKLOWERINC(JU_BITPOSMASKL(findbit)));

	    DBGCODE(if (! JU_BITMAPTESTL(Pjlb, digit)) return(~count);)
	    assert(count >= 1);
	    return(count - 1);		// convert to base-0 offset.
	}
#endif // NOSMARTJLB


// COUNT DOWNWARD:
//
// Count the valid Indexes above or at Index, and subtract from Pop1.

#ifdef SMARTMETRICS
	++jlb_downward;
#endif
	count = Pop1;			// base-1 for now.

	for (subexp = cJU_NUMSUBEXPL - 1; subexp > findsub; --subexp)
	{
	    count -= ((JU_JLB_BITMAP(Pjlb, subexp) == cJU_FULLBITMAPL) ?
		      cJU_BITSPERSUBEXPL :
		      j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp)));
	}

// This count includes findbit, which should be set, resulting in a base-0
// offset:

	count -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, findsub)
				& JU_MASKHIGHERINC(JU_BITPOSMASKL(findbit)));

	DBGCODE(if (! JU_BITMAPTESTL(Pjlb, digit)) return(~count);)
	assert(count >= 0);		// should find Index itself.
	return(count);			// is already a base-0 offset.

} // j__udyCountLeafB1()


// ****************************************************************************
// J U D Y   J P   P O P 1
//
// This function takes any type of JP other than a root-level JP (cJU_LEAFW* or
// cJU_JPBRANCH* with no number suffix) and extracts the Pop1 from it.  In some
// sense this is a wrapper around the JU_JP*_POP0 macros.  Why write it as a
// function instead of a complex macro containing a trinary?  (See version
// Judy1.h version 4.17.)  We think its cheaper to call a function containing
// a switch statement with "constant" cases than to do the variable
// calculations in a trinary.
//
// For invalid JP Types return cJU_ALLONES.  Note that this is an impossibly
// high Pop1 for any JP below a top level branch.

FUNCTION Word_t j__udyJPPop1(
const	Pjp_t Pjp)		// JP to count.
{
	switch (JU_JPTYPE(Pjp))
	{
#ifdef notdef // caller should shortcut and not even call with these:

	case cJU_JPNULL1:
	case cJU_JPNULL2:
	case cJU_JPNULL3:  return(0);
#ifdef JU_64BIT
	case cJU_JPNULL4:
	case cJU_JPNULL5:
	case cJU_JPNULL6:
	case cJU_JPNULL7:  return(0);
#endif
#endif // notdef

	case cJU_JPBRANCH_L2:
	case cJU_JPBRANCH_B2:
	case cJU_JPBRANCH_U2: return(JU_JPBRANCH_POP0(Pjp,2) + 1);

	case cJU_JPBRANCH_L3:
	case cJU_JPBRANCH_B3:
	case cJU_JPBRANCH_U3: return(JU_JPBRANCH_POP0(Pjp,3) + 1);

#ifdef JU_64BIT
	case cJU_JPBRANCH_L4:
	case cJU_JPBRANCH_B4:
	case cJU_JPBRANCH_U4: return(JU_JPBRANCH_POP0(Pjp,4) + 1);

	case cJU_JPBRANCH_L5:
	case cJU_JPBRANCH_B5:
	case cJU_JPBRANCH_U5: return(JU_JPBRANCH_POP0(Pjp,5) + 1);

	case cJU_JPBRANCH_L6:
	case cJU_JPBRANCH_B6:
	case cJU_JPBRANCH_U6: return(JU_JPBRANCH_POP0(Pjp,6) + 1);

	case cJU_JPBRANCH_L7:
	case cJU_JPBRANCH_B7:
	case cJU_JPBRANCH_U7: return(JU_JPBRANCH_POP0(Pjp,7) + 1);
#endif

#if (defined(JUDYL) || (! defined(JU_64BIT)))
	case cJU_JPLEAF1:
#endif
	case cJU_JPLEAF2:
	case cJU_JPLEAF3:
#ifdef JU_64BIT
	case cJU_JPLEAF4:
	case cJU_JPLEAF5:
	case cJU_JPLEAF6:
	case cJU_JPLEAF7:
#endif
	case cJU_JPLEAF_B1:	return(JU_JPLEAF_POP0(Pjp) + 1);

#ifdef JUDY1
	case cJ1_JPFULLPOPU1:	return(cJU_JPFULLPOPU1_POP0 + 1);
#endif

	case cJU_JPIMMED_1_01:
	case cJU_JPIMMED_2_01:
	case cJU_JPIMMED_3_01:	return(1);
#ifdef JU_64BIT
	case cJU_JPIMMED_4_01:
	case cJU_JPIMMED_5_01:
	case cJU_JPIMMED_6_01:
	case cJU_JPIMMED_7_01:	return(1);
#endif

	case cJU_JPIMMED_1_02:	return(2);
	case cJU_JPIMMED_1_03:	return(3);
#if (defined(JUDY1) || defined(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 (defined(JUDY1) && defined(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 (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_2_02:	return(2);
	case cJU_JPIMMED_2_03:	return(3);
#endif
#if (defined(JUDY1) && defined(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 (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_3_02:	return(2);
#endif
#if (defined(JUDY1) && defined(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

	default:		return(cJU_ALLONES);
	}

	/*NOTREACHED*/

} // j__udyJPPop1()