Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudyCommon/JudyPrivate.h view on Meta::CPAN
// A Linear branch has a ~1.75 cache line fill cost when at maximum population.
// A Bitmap branch has ~2.0 cache line fills. Linear and Bitmap branches are
// converted to Uncompressed branches when the additional memory can be
// amortized with larger populations. Higher-state branches have higher
// priority to be converted.
//
// Linear branches can hold 28 elements (based on detailed analysis) -- thus 28
// expanses. A Linear branch is converted to a Bitmap branch when the 29th
// expanse is required.
//
// A Bitmap branch could hold 256 expanses, but is forced to convert to an
// Uncompressed branch when 185 expanses are required. Hopefully, it is
// converted before that because of population growth (again, based on detailed
// analysis and heuristics in the code).
//
// A path through the SM terminates to a leaf when the Index (or key)
// population in the expanse below a pointer will fit into 1 or 2 cache lines
// (~31..255 Indexes). A maximum-population Leaf has ~1.5 cache line fill
// cost.
//
// Leaves are sorted arrays of Indexes, where the Index Sizes (IS) are: 0, 1,
// 8, 16, 24, 32, [40, 48, 56, 64] bits. The IS depends on the "density"
// (population/expanse) of the values in the Leaf. Zero bits are possible if
// population == expanse in the SM (that is, a full small expanse).
//
// Elements of a branches are called Judy Pointers (JPs). Each JP object
// points to the next object in the SM, plus, a JP can decode an additional
// 2[6] bytes of an Index, but at the cost of "narrowing" the expanse
// represented by the next object in the SM. A "narrow" JP (one which has
// decode bytes/digits) is a way of skipping states in the SM.
//
// Although counterintuitive, we think a Judy SM is optimal when the Leaves are
// stored at MINIMUM compression (narrowing, or use of Decode bytes). If more
// aggressive compression was used, decompression of a leaf be required to
// insert an index. Additional compression would save a little memory but not
// help performance significantly.
#ifdef A_PICTURE_IS_WORTH_1000_WORDS
*******************************************************************************
JUDY 32-BIT STATE MACHINE (SM) EXAMPLE, FOR INDEX = 0x02040103
The Index used in this example is purposely chosen to allow small, simple
examples below; each 1-byte "digit" from the Index has a small numeric value
that fits in one column. In the drawing below:
JRP == Judy Root Pointer;
C == 1 byte of a 1..3 byte Population (count of Indexes) below this
pointer. Since this is shared with the Decode field, the combined
sizes must be 3[7], that is, 1 word less 1 byte for the JP Type.
The 1-byte field jp_Type is represented as:
1..3 == Number of bytes in the population (Pop0) word of the Branch or Leaf
below the pointer (note: 1..7 on 64-bit); indicates:
- number of bytes in Decode field == 3 - this number;
- number of bytes remaining to decode.
Note: The maximum is 3, not 4, because the 1st byte of the Index is
always decoded digitally in the top branch.
-B- == JP points to a Branch (there are many kinds of Branches).
-L- == JP points to a Leaf (there are many kinds of Leaves).
(2) == Digit of Index decoded by position offset in branch (really
0..0xff).
4* == Digit of Index necessary for decoding a "narrow" pointer, in a
Decode field; replaces 1 missing branch (really 0..0xff).
4+ == Digit of Index NOT necessary for decoding a "narrow" pointer, but
used for fast traversal of the SM by Judy1Test() and JudyLGet()
(see the code) (really 0..0xff).
0 == Byte in a JPs Pop0 field that is always ignored, because a leaf
can never contain more than 256 Indexes (Pop0 <= 255).
+----- == A Branch or Leaf; drawn open-ended to remind you that it could
| have up to 256 columns.
+-----
|
| == Pointer to next Branch or Leaf.
V
|
O == A state is skipped by using a "narrow" pointer.
|
< 1 > == Digit (Index) shown as an example is not necessarily in the
position shown; is sorted in order with neighbor Indexes.
(Really 0..0xff.)
Note that this example shows every possibly topology to reach a leaf in a
32-bit Judy SM, although this is a very subtle point!
STATE or`
LEVEL
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
|RJP| |RJP| |RJP| |RJP| |RJP| |RJP| |RJP| |RJP|
L---+ B---+ B---+ B---+ B---+ B---+ B---+ B---+
| | | | | | | |
| | | | | | | |
V V (2) V (2) V (2) V (2) V (2) V (2) V (2)
+------ +------ +------ +------ +------ +------ +------ +------
Four |< 2 > | 0 | 4* | C | 4* | 4* | C | C
byte |< 4 > | 0 | 0 | C | 1* | C | C | C 4
Index|< 1 > | C | C | C | C | C | C | C
Leaf |< 3 > | 3 | 2 | 3 | 1 | 2 | 3 | 3
+------ +--L--- +--L--- +--B--- +--L--- +--B--- +--B--- +--B---
| | | | | | |
/ | / | | / /
/ | / | | / /
| | | | | | |
V | V (4) | | V (4) V (4)
+------ | +------ | | +------ +------
Three |< 4 > | | 4+ | | | 4+ | 4+
byte Index|< 1 > O | 0 O O | 1* | C 3
Leaf |< 3 > | | C | | | C | C
+------ | | 2 | | | 1 | 2
/ +----L- | | +----L- +----B-
/ | | | | |
| / | / / /
| / | / / /
| / | | / /
src/judy-1.0.5/src/JudyCommon/JudyPrivate.h view on Meta::CPAN
#define JUDYLCODE(Code) // null.
#endif
#ifdef JUDYL
#define JUDYLCODE(Code) Code
#define JUDY1CODE(Code) // null.
#endif
#include <assert.h>
// ****************************************************************************
// FUNDAMENTAL CONSTANTS FOR MACHINE
// ****************************************************************************
// Machine (CPU) cache line size:
//
// NOTE: A leaf size of 2 cache lines maximum is the target (optimal) for
// Judy. Its hard to obtain a machines cache line size at compile time, but
// if the machine has an unexpected cache line size, its not devastating if
// the following constants end up causing leaves that are 1 cache line in size,
// or even 4 cache lines in size. The assumed 32-bit system has 16-word =
// 64-byte cache lines, and the assumed 64-bit system has 16-word = 128-byte
// cache lines.
#ifdef JU_64BIT
#define cJU_BYTESPERCL 128 // cache line size in bytes.
#else
#define cJU_BYTESPERCL 64 // cache line size in bytes.
#endif
// Bits Per Byte:
#define cJU_BITSPERBYTE 0x8
// Bytes Per Word and Bits Per Word, latter assuming sizeof(byte) is 8 bits:
//
// Expect 32 [64] bits per word.
#define cJU_BYTESPERWORD (sizeof(Word_t))
#define cJU_BITSPERWORD (sizeof(Word_t) * cJU_BITSPERBYTE)
#define JU_BYTESTOWORDS(BYTES) \
(((BYTES) + cJU_BYTESPERWORD - 1) / cJU_BYTESPERWORD)
// A word that is all-ones, normally equal to -1UL, but safer with ~0:
#define cJU_ALLONES (~0UL)
// Note, these are forward references, but thats OK:
#define cJU_FULLBITMAPB ((BITMAPB_t) cJU_ALLONES)
#define cJU_FULLBITMAPL ((BITMAPL_t) cJU_ALLONES)
// ****************************************************************************
// MISCELLANEOUS JUDY-SPECIFIC DECLARATIONS
// ****************************************************************************
// ROOT STATE:
//
// State at the start of the Judy SM, based on 1 byte decoded per state; equal
// to the number of bytes per Index to decode.
#define cJU_ROOTSTATE (sizeof(Word_t))
// SUBEXPANSES PER STATE:
//
// Number of subexpanses per state traversed, which is the number of JPs in a
// branch (actual or theoretical) and the number of bits in a bitmap.
#define cJU_SUBEXPPERSTATE 256
// LEAF AND VALUE POINTERS:
//
// Some other basic object types are in declared in JudyPrivateBranch.h
// (Pjbl_t, Pjbb_t, Pjbu_t, Pjp_t) or are Judy1/L-specific (Pjlb_t). The
// few remaining types are declared below.
//
// Note: Leaf pointers are cast to different-sized objects depending on the
// leafs level, but are at least addresses (not just numbers), so use void *
// (Pvoid_t), not PWord_t or Word_t for them, except use Pjlw_t for whole-word
// (top-level, root-level) leaves. Value areas, however, are always whole
// words.
//
// Furthermore, use Pjll_t only for generic leaf pointers (for various size
// LeafLs). Use Pjlw_t for LeafWs. Use Pleaf (with type uint8_t *, uint16_t
// *, etc) when the leaf index size is known.
typedef PWord_t Pjlw_t; // pointer to root-level leaf (whole-word indexes).
typedef Pvoid_t Pjll_t; // pointer to lower-level linear leaf.
#ifdef JUDYL
typedef PWord_t Pjv_t; // pointer to JudyL value area.
#endif
// POINTER PREPARATION MACROS:
//
// These macros are used to strip malloc-namespace-type bits from a pointer +
// malloc-type word (which references any Judy mallocd object that might be
// obtained from other than a direct call of malloc()), prior to dereferencing
// the pointer as an address. The malloc-type bits allow Judy mallocd objects
// to come from different "malloc() namespaces".
//
// (root pointer) (JRP, see above)
// jp.jp_Addr generic pointer to next-level node, except when used
// as a JudyL Immed01 value area
// JU_JBB_PJP macro hides jbbs_Pjp (pointer to JP subarray)
// JL_JLB_PVALUE macro hides jLlbs_PValue (pointer to value subarray)
//
// When setting one of these fields or passing an address to j__udyFree*(), the
// "raw" memory address is used; otherwise the memory address must be passed
// through one of the macros below before its dereferenced.
//
// Note: After much study, the typecasts below appear in the macros rather
// than at the point of use, which is both simpler and allows the compiler to
// do type-checking.
( run in 1.184 second using v1.01-cache-2.11-cpan-39bf76dae61 )