Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/doc/int/10minutes.htm view on Meta::CPAN
, but it took me about three hours to read!)</P>
<P CLASS="Body">
<A NAME="pgfId=997354">
</A>
A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the "Judy Scalable Hashing" configuration, Judy is generally faster then a hashing...
<A HREF="http://www.sourcejudy.com/application/">http://www.sourcejudy.com/application/</A>
Judy_hashing.</P>
<P CLASS="Body">
<A NAME="pgfId=997488">
</A>
<EM CLASS="bold">
Expanse</EM>
, <EM CLASS="bold">
population</EM>
, and <EM CLASS="bold">
density</EM>
are not commonly used terms in tree search literature, so let's define them here:</P>
<UL>
<LI CLASS="Bulleted">
<A NAME="pgfId=997357">
</A>
<EM CLASS="bold">
Expanse</EM>
is a range of possible keys, such as: 256..511</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997358">
</A>
<EM CLASS="bold">
Population</EM>
is the count of keys contained in an expanse, such as, 260, 300, 499, 500 = 4.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997359">
</A>
<EM CLASS="bold">
Density</EM>
is used to describe the sparseness of an expanse of keys; density = population / expanse. A density of 1.0 means that all possible keys are set or valid in that expanse.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=997360">
</A>
<EM CLASS="bold">
Node</EM>
and <EM CLASS="bold">
branch</EM>
are used interchangeably in this document.</P>
<P CLASS="Body">
<A NAME="pgfId=997361">
</A>
<EM CLASS="bold">
Key</EM>
and <EM CLASS="bold">
index</EM>
are used interchangeably. A Judy tree is thought of as an unbounded Judy array at the API level. The expanse of JudyL or Judy1 arrays are bounded by the expanse of the word (32[64]-bits) used for the index/key. A JudySL array is only bounded by the ...
<P CLASS="Body">
<A NAME="pgfId=997362">
</A>
A (CPU) <EM CLASS="bold">
cache-line fill</EM>
is additional time required to do a read reference from RAM when a word is not found in cache. In today's computers the time for a cache-line fill is in the range of 50..2000 machine instructions. Therefore a cache-line fill should be avoided when f...
<P CLASS="Body">
<A NAME="pgfId=997363">
</A>
Some of the reasons Judy outperforms binary trees, b-trees, and skip-lists:</P>
<UL>
<LI CLASS="Bulleted">
<A NAME="pgfId=997364">
</A>
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
#define SKIPNONSPACE(Pch) { while ((! ISSPACE(*(Pch))) \
&& (*(Pch) != CHNULL) \
&& (*(Pch) != '>')) ++(Pch); }
// Highest line number + 1, and last input line number that caused output:
int g_linenumlim;
int g_prevlinenum = 0;
// <PRE> block equivalents in nroff need some special handling for bold font
// and for continuing a tagged paragraph; these are bit flags:
#define INPRE_BLOCK 0x1 // came from <PRE>.
#define INPRE_BOLD 0x2 // came from <B><PRE>.
#define INPRE_INDENT 0x4 // under <DL> below top level.
// ****************************************************************************
// DOCUMENT NODE TYPES:
//
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
// The dn_text field is null for a tag node unless the tag text is worth
// saving. The field is non-null for non-tag (document) text.
typedef struct docnode * Pdn_t;
struct docnode {
int dn_type; // node type, index in g_dntype[].
int dn_linenum; // where introduced, for reconstructing.
bool_t dn_closed; // flag: closing tag was seen.
bool_t dn_noemit; // flag: skip on output, for marking ahead.
bool_t dn_bold; // flag: for <PRE>, whole section is bold.
char * dn_text; // node text; see above.
Pdn_t dn_Pprev; // previous node in sibling list.
Pdn_t dn_Pnext; // next node in sibling list.
Pdn_t dn_Pparent; // up-link to parent node, if any.
Pdn_t dn_Pchild; // down-link to first node in child subtree.
};
#define PDNNULL ((Pdn_t) NULL)
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
case DN_TYPE_TABLE:
case DN_TYPE_TR:
case DN_TYPE_TD:
MarkNoEmit(Pdn->dn_Pchild, /* Font = */ FALSE);
break;
// DESCRIPTIVE LIST:
//
// At the top level these represent manual entry sections, and any bold markers
// around the text are ignored. Below the top level these translate to tagged
// paragraphs. Here, just note the increment and continue the walk.
case DN_TYPE_DL:
DLcount = 1;
break;
// DESCRIPTIVE LIST TAG:
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
// See if anchor label appears to be a reference to the current page, to some
// other page, or else just make it italicized text:
//
// TBD: This is pretty shaky, hope it's close enough.
len = strlen(PageName);
if (strncmp(Pdn2->dn_text, PageName, len) == 0) // self-reference.
{
CHECKPREV;
PUTS("\\fB"); // bold font.
SETPREVNONL;
suffix = "\\fP"; // revert to previous font.
break;
}
// Contains '(' and no whitespace => appears to reference some other page:
//
// Emit revised, tagged anchor label text immediately.
if (((Pch = strchr(Pdn2->dn_text, '(')) != PCNULL)
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
} // case DN_TYPE_A
// BOLD TEXT:
//
// If the first child is <PRE>, use a "hard" font change; otherwise an in-line
// change.
//
// Note: For <DT><B>, this node is already marked dn_noemit and not seen here.
//
// Note: For <B><PRE>, nroff seems to reset font upon .PP, so mark the bold
// for later emission.
case DN_TYPE_B:
if (((Pdn->dn_Pchild) != PDNNULL)
&& ((Pdn->dn_Pchild->dn_type) == DN_TYPE_PRE))
{
(Pdn->dn_Pchild->dn_bold) = TRUE; // see above.
break;
}
CHECKPREV;
PUTS("\\fB"); // bold font.
SETPREVNONL;
suffix = "\\fP"; // revert to previous font.
break;
// ITALIC TEXT:
case DN_TYPE_I:
CHECKPREV;
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
break;
// PREFORMATTED TEXT:
//
// Emit prefix/suffix directives based on example in strchr(3C).
case DN_TYPE_PRE:
PUTS(UNDER_DL ? "\n.IP\n.nf\n.ps +1\n" : "\n.PP\n.nf\n.ps +1\n");
if (Pdn->dn_bold) PUTS(".ft B\n"); // deferred bold.
SETPREVNONL;
suffix = ((Pdn->dn_bold) ? "\n.ft P\n.ps\n.fi\n" : "\n.ps\n.fi\n");
// set for all children:
InPRE = INPRE_BLOCK
| ((Pdn->dn_bold) ? INPRE_BOLD : 0)
| (UNDER_DL ? INPRE_INDENT : 0);
break;
// PARAGRAPH BREAK:
//
// If the parent is a <DL> below the top level, use .IP to continue a .TP
// (tagged paragraph); otherwise emit a standard .PP.
case DN_TYPE_P:
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
FUNCTION Pdn_t NewDocNode(
Pdn_t dn_Pparent, // parent to record.
int Linenum) // in input file.
{
Pdn_t Pdn = (Pdn_t) Malloc(sizeof(struct docnode));
(Pdn -> dn_linenum) = Linenum;
(Pdn -> dn_closed) = FALSE;
(Pdn -> dn_noemit) = FALSE;
(Pdn -> dn_bold) = FALSE;
(Pdn -> dn_text) = PCNULL;
(Pdn -> dn_Pprev) = PDNNULL;
(Pdn -> dn_Pnext) = PDNNULL;
(Pdn -> dn_Pparent) = dn_Pparent;
(Pdn -> dn_Pchild) = PDNNULL;
return(Pdn);
} // NewDocNode()
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
}
return(Pch2 + 1);
} // SaveDocNode()
// ****************************************************************************
// P A R E N T P R E
//
// Given a docnode (can be null) and a flag whether only bold <PRE> is of
// interest, return TRUE if any of its parents is a <PRE> (marked for bold
// text), that is, DN_TYPE_PRE (with dn_bold set); otherwise return FALSE.
FUNCTION bool_t ParentPre(
Pdn_t Pdn, // starting node.
bool_t BoldOnly) // flag: only care about bold <PRE>.
{
if (Pdn == PDNNULL) return (FALSE); // no parent.
for (Pdn = Pdn->dn_Pparent; Pdn != PDNNULL; Pdn = Pdn->dn_Pparent)
{
if (((Pdn->dn_type) == DN_TYPE_PRE)
&& ((! BoldOnly) || (Pdn->dn_bold)))
{
return(TRUE);
}
}
return(FALSE);
} // ParentPre()
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
// ****************************************************************************
// E M I T T E X T
//
// Given a text string, a bitflag for <PRE> status, and an input line number
// for error reporting, copy the text string to stdout with no added newlines,
// but translating selected HTML escape codes to simple characters, doubling
// any backslashes, and if InPRE, inserting .IP (if INPRE_INDENT) or .PP at
// blank lines (between successive newlines), and if INPRE_BOLD, putting back
// bold font since .IP/.PP seems to reset the font. Warn about unrecognized
// escape codes.
struct et_list {
char * et_escape; // expected text.
size_t et_len; // of expected text.
char et_emit; // equivalent char.
} et_list[] = {
{ "amp;", 4, '&', },
{ "gt;", 3, '>', },
{ "lt;", 3, '<', },
( run in 0.312 second using v1.01-cache-2.11-cpan-c333fce770f )