view release on metacpan or  search on metacpan

src/judy-1.0.5/src/JudyCommon/JudyPrivateBranch.h  view on Meta::CPAN

#ifndef _JUDY_PRIVATE_BRANCH_INCLUDED
#define _JUDY_PRIVATE_BRANCH_INCLUDED
// _________________
//
// 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.57 $ $Source: /judy/src/JudyCommon/JudyPrivateBranch.h $
//
// Header file for all Judy sources, for global but private (non-exported)
// declarations specific to branch support.
//
// See also the "Judy Shop Manual" (try judy/doc/int/JudyShopManual.*).


// ****************************************************************************
// JUDY POINTER (JP) SUPPORT
// ****************************************************************************
//
// This "rich pointer" object is pivotal to Judy execution.
//
// JP CONTAINING OTHER THAN IMMEDIATE INDEXES:
//
// If the JP points to a linear or bitmap leaf, jp_DcdPopO contains the
// Population-1 in LSbs and Decode (Dcd) bytes in the MSBs.  (In practice the
// Decode bits are masked off while accessing the Pop0 bits.)
//
// The Decode Size, the number of Dcd bytes available, is encoded in jpo_Type.
// It can also be thought of as the number of states "skipped" in the SM, where
// each state decodes 8 bits = 1 byte.
//
// TBD:  Dont need two structures, except possibly to force jp_Type to highest
// address!
//
// Note:  The jpo_u union is not required by HP-UX or Linux but Win32 because
// the cl.exe compiler otherwise refuses to pack a bitfield (DcdPopO) with
// anything else, even with the -Zp option.  This is pretty ugly, but
// fortunately portable, and its all hide-able by macros (see below).

typedef struct J_UDY_POINTER_OTHERS      // JPO.
        {
            Word_t      j_po_Addr;       // first word:  Pjp_t, Word_t, etc.
            union {
//              Word_t  j_po_DcdPop0:cJU_BITSPERWORD-cJU_BITSPERBYTE;
                uint8_t j_po_DcdP0[sizeof(Word_t) - 1];
                uint8_t j_po_Bytes[sizeof(Word_t)];     // last byte = jp_Type.
            } jpo_u;
        } jpo_t;


// JP CONTAINING IMMEDIATE INDEXES:
//
// j_pi_1Index[] plus j_pi_LIndex[] together hold as many N-byte (1..3-byte
// [1..7-byte]) Indexes as will fit in sizeof(jpi_t) less 1 byte for j_pi_Type
// (that is, 7..1 [15..1] Indexes).
//
// For Judy1, j_pi_1Index[] is used and j_pi_LIndex[] is not used.
// For JudyL, j_pi_LIndex[] is used and j_pi_1Index[] is not used.
//
// Note:  Actually when Pop1 = 1, jpi_t is not used, and the least bytes of the
// single Index are stored in j_po_DcdPopO, for both Judy1 and JudyL, so for
// JudyL the j_po_Addr field can hold the target value.
//
// TBD:  Revise this structure to not overload j_po_DcdPopO this way?  The
// current arrangement works, its just confusing.

typedef struct _JUDY_POINTER_IMMED      // JPI.
        {
            uint8_t j_pi_1Index[sizeof(Word_t)];        // see above.
            uint8_t j_pi_LIndex[sizeof(Word_t) - 1];    // see above.

src/judy-1.0.5/src/JudyCommon/JudyPrivateBranch.h  view on Meta::CPAN

            jbbs_t jbb_jbbs   [cJU_NUMSUBEXPB];
#ifdef SUBEXPCOUNTS
            Word_t jbb_subPop1[cJU_NUMSUBEXPB];
#endif
        } jbb_t, * Pjbb_t;

#define JU_BRANCHJP_NUMJPSTOWORDS(NumJPs) (j__U_BranchBJPPopToWords[NumJPs])

#ifdef SUBEXPCOUNTS
#define cJU_NUMSUBEXPU  16      // number of subexpanse counts.
#endif


// ****************************************************************************
// JUDY BRANCH UNCOMPRESSED (JBU) SUPPORT
// ****************************************************************************

// Convenience wrapper for referencing BranchU JPs:
//
// Note:  This produces a non-"raw" address already passed through P_JBU().

#define JU_JBU_PJP(Pjp,Index,Level) \
        (&((P_JBU((Pjp)->jp_Addr))->jbu_jp[JU_DIGITATSTATE(Index, Level)]))
#define JU_JBU_PJP0(Pjp) \
        (&((P_JBU((Pjp)->jp_Addr))->jbu_jp[0]))

typedef struct J__UDY_BRANCH_UNCOMPRESSED
        {
            jp_t   jbu_jp     [cJU_BRANCHUNUMJPS];  // JPs for populated exp.
#ifdef SUBEXPCOUNTS
            Word_t jbu_subPop1[cJU_NUMSUBEXPU];
#endif
        } jbu_t, * Pjbu_t;


// ****************************************************************************
// OTHER SUPPORT FOR JUDY STATE MACHINES (SMs)
// ****************************************************************************

// OBJECT SIZES IN WORDS:
//
// Word_ts per various JudyL structures that have constant sizes.
// cJU_WORDSPERJP should always be 2; this is fundamental to the Judy
// structures.

#define cJU_WORDSPERJP (sizeof(jp_t)   / cJU_BYTESPERWORD)
#define cJU_WORDSPERCL (cJU_BYTESPERCL / cJU_BYTESPERWORD)


// OPPORTUNISTIC UNCOMPRESSION:
//
// Define populations at which a BranchL or BranchB must convert to BranchU.
// Earlier conversion is possible with good memory efficiency -- see below.

#ifndef NO_BRANCHU

// Max population below BranchL, then convert to BranchU:

#define JU_BRANCHL_MAX_POP      1000

// Minimum global population increment before next conversion of a BranchB to a
// BranchU:
//
// This is was done to allow malloc() to coalesce memory before the next big
// (~512 words) allocation.

#define JU_BTOU_POP_INCREMENT    300

// Min/max population below BranchB, then convert to BranchU:

#define JU_BRANCHB_MIN_POP       135
#define JU_BRANCHB_MAX_POP       750

#else // NO_BRANCHU

// These are set up to have conservative conversion schedules to BranchU:

#define JU_BRANCHL_MAX_POP      (-1UL)
#define JU_BTOU_POP_INCREMENT      300
#define JU_BRANCHB_MIN_POP        1000
#define JU_BRANCHB_MAX_POP      (-1UL)

#endif // NO_BRANCHU


// MISCELLANEOUS MACROS:

// Get N most significant bits from the shifted Index word:
//
// As Index words are decoded, they are shifted left so only relevant,
// undecoded Index bits remain.

#define JU_BITSFROMSFTIDX(SFTIDX, N)  ((SFTIDX) >> (cJU_BITSPERWORD - (N)))

// TBD:  I have my doubts about the necessity of these macros (dlb):

// Produce 1-digit mask at specified state:

#define cJU_MASKATSTATE(State)  (0xffL << (((State) - 1) * cJU_BITSPERBYTE))

// Get byte (digit) from Index at the specified state, right justified:
//
// Note:  State must be 1..cJU_ROOTSTATE, and Digits must be 1..(cJU_ROOTSTATE
// - 1), but theres no way to assert these within an expression.

#define JU_DIGITATSTATE(Index,cState) \
         ((uint8_t)((Index) >> (((cState) - 1) * cJU_BITSPERBYTE)))

// Similarly, place byte (digit) at correct position for the specified state:
//
// Note:  Cast digit to a Word_t first so there are no complaints or problems
// about shifting it more than 32 bits on a 64-bit system, say, when it is a
// uint8_t from jbl_Expanse[].  (Believe it or not, the C standard says to
// promote an unsigned char to a signed int; -Ac does not do this, but -Ae
// does.)
//
// Also, to make lint happy, cast the whole result again because apparently
// shifting a Word_t does not result in a Word_t!

#define JU_DIGITTOSTATE(Digit,cState) \
        ((Word_t) (((Word_t) (Digit)) << (((cState) - 1) * cJU_BITSPERBYTE)))