Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
fi
AC_CACHE_VAL(lt_cv_path_LD,
[if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
test -z "$LD" && AC_MSG_ERROR([no acceptable ld found in \$PATH])
AC_PROG_LD_GNU
])# AC_PROG_LD
# AC_PROG_LD_GNU
# --------------
AC_DEFUN([AC_PROG_LD_GNU],
[AC_REQUIRE([AC_PROG_EGREP])dnl
AC_CACHE_CHECK([if the linker ($LD) is GNU ld], lt_cv_prog_gnu_ld,
[# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac])
with_gnu_ld=$lt_cv_prog_gnu_ld
])# AC_PROG_LD_GNU
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
{ echo "$as_me: error: Working directory cannot be determined" >&2
{ (exit 1); exit 1; }; }
test "X$ac_ls_di" = "X$ac_pwd_ls_di" ||
{ echo "$as_me: error: pwd does not report name of working directory" >&2
{ (exit 1); exit 1; }; }
# Find the source files, if location was not specified.
if test -z "$srcdir"; then
ac_srcdir_defaulted=yes
# Try the directory containing this script, then the parent directory.
ac_confdir=`$as_dirname -- "$0" ||
$as_expr X"$0" : 'X\(.*[^/]\)//*[^/][^/]*/*$' \| \
X"$0" : 'X\(//\)[^/]' \| \
X"$0" : 'X\(//\)$' \| \
X"$0" : 'X\(/\)' \| . 2>/dev/null ||
echo X"$0" |
sed '/^X\(.*[^/]\)\/\/*[^/][^/]*\/*$/{
s//\1/
q
}
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
echo $ECHO_N "(cached) $ECHO_C" >&6
else
if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
echo "${ECHO_T}no" >&6; }
fi
test -z "$LD" && { { echo "$as_me:$LINENO: error: no acceptable ld found in \$PATH" >&5
echo "$as_me: error: no acceptable ld found in \$PATH" >&2;}
{ (exit 1); exit 1; }; }
{ echo "$as_me:$LINENO: checking if the linker ($LD) is GNU ld" >&5
echo $ECHO_N "checking if the linker ($LD) is GNU ld... $ECHO_C" >&6; }
if test "${lt_cv_prog_gnu_ld+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac
fi
{ echo "$as_me:$LINENO: result: $lt_cv_prog_gnu_ld" >&5
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
echo $ECHO_N "(cached) $ECHO_C" >&6
else
if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
echo "${ECHO_T}no" >&6; }
fi
test -z "$LD" && { { echo "$as_me:$LINENO: error: no acceptable ld found in \$PATH" >&5
echo "$as_me: error: no acceptable ld found in \$PATH" >&2;}
{ (exit 1); exit 1; }; }
{ echo "$as_me:$LINENO: checking if the linker ($LD) is GNU ld" >&5
echo $ECHO_N "checking if the linker ($LD) is GNU ld... $ECHO_C" >&6; }
if test "${lt_cv_prog_gnu_ld+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac
fi
{ echo "$as_me:$LINENO: result: $lt_cv_prog_gnu_ld" >&5
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
{ echo "$as_me: error: Working directory cannot be determined" >&2
{ (exit 1); exit 1; }; }
test "X$ac_ls_di" = "X$ac_pwd_ls_di" ||
{ echo "$as_me: error: pwd does not report name of working directory" >&2
{ (exit 1); exit 1; }; }
# Find the source files, if location was not specified.
if test -z "$srcdir"; then
ac_srcdir_defaulted=yes
# Try the directory containing this script, then the parent directory.
ac_confdir=`$as_dirname -- "$0" ||
$as_expr X"$0" : 'X\(.*[^/]\)//*[^/][^/]*/*$' \| \
X"$0" : 'X\(//\)[^/]' \| \
X"$0" : 'X\(//\)$' \| \
X"$0" : 'X\(/\)' \| . 2>/dev/null ||
echo X"$0" |
sed '/^X\(.*[^/]\)\/\/*[^/][^/]*\/*$/{
s//\1/
q
}
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
echo $ECHO_N "(cached) $ECHO_C" >&6
else
if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
echo "${ECHO_T}no" >&6; }
fi
test -z "$LD" && { { echo "$as_me:$LINENO: error: no acceptable ld found in \$PATH" >&5
echo "$as_me: error: no acceptable ld found in \$PATH" >&2;}
{ (exit 1); exit 1; }; }
{ echo "$as_me:$LINENO: checking if the linker ($LD) is GNU ld" >&5
echo $ECHO_N "checking if the linker ($LD) is GNU ld... $ECHO_C" >&6; }
if test "${lt_cv_prog_gnu_ld+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac
fi
{ echo "$as_me:$LINENO: result: $lt_cv_prog_gnu_ld" >&5
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
echo $ECHO_N "(cached) $ECHO_C" >&6
else
if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
echo "${ECHO_T}no" >&6; }
fi
test -z "$LD" && { { echo "$as_me:$LINENO: error: no acceptable ld found in \$PATH" >&5
echo "$as_me: error: no acceptable ld found in \$PATH" >&2;}
{ (exit 1); exit 1; }; }
{ echo "$as_me:$LINENO: checking if the linker ($LD) is GNU ld" >&5
echo $ECHO_N "checking if the linker ($LD) is GNU ld... $ECHO_C" >&6; }
if test "${lt_cv_prog_gnu_ld+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac
fi
{ echo "$as_me:$LINENO: result: $lt_cv_prog_gnu_ld" >&5
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
fi
AC_CACHE_VAL(lt_cv_path_LD,
[if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
if test -n "$LD"; then
AC_MSG_RESULT($LD)
else
AC_MSG_RESULT(no)
fi
test -z "$LD" && AC_MSG_ERROR([no acceptable ld found in \$PATH])
AC_PROG_LD_GNU
])
m4trace:/usr/share/aclocal/libtool.m4:2200: -1- AC_DEFUN([AC_PROG_LD_GNU], [AC_REQUIRE([AC_PROG_EGREP])dnl
AC_CACHE_CHECK([if the linker ($LD) is GNU ld], lt_cv_prog_gnu_ld,
[# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac])
with_gnu_ld=$lt_cv_prog_gnu_ld
])
src/judy-1.0.5/configure view on Meta::CPAN
{ echo "$as_me: error: Working directory cannot be determined" >&2
{ (exit 1); exit 1; }; }
test "X$ac_ls_di" = "X$ac_pwd_ls_di" ||
{ echo "$as_me: error: pwd does not report name of working directory" >&2
{ (exit 1); exit 1; }; }
# Find the source files, if location was not specified.
if test -z "$srcdir"; then
ac_srcdir_defaulted=yes
# Try the directory containing this script, then the parent directory.
ac_confdir=`$as_dirname -- "$0" ||
$as_expr X"$0" : 'X\(.*[^/]\)//*[^/][^/]*/*$' \| \
X"$0" : 'X\(//\)[^/]' \| \
X"$0" : 'X\(//\)$' \| \
X"$0" : 'X\(/\)' \| . 2>/dev/null ||
echo X"$0" |
sed '/^X\(.*[^/]\)\/\/*[^/][^/]*\/*$/{
s//\1/
q
}
src/judy-1.0.5/configure view on Meta::CPAN
echo $ECHO_N "(cached) $ECHO_C" >&6
else
if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/configure view on Meta::CPAN
echo "${ECHO_T}no" >&6; }
fi
test -z "$LD" && { { echo "$as_me:$LINENO: error: no acceptable ld found in \$PATH" >&5
echo "$as_me: error: no acceptable ld found in \$PATH" >&2;}
{ (exit 1); exit 1; }; }
{ echo "$as_me:$LINENO: checking if the linker ($LD) is GNU ld" >&5
echo $ECHO_N "checking if the linker ($LD) is GNU ld... $ECHO_C" >&6; }
if test "${lt_cv_prog_gnu_ld+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac
fi
{ echo "$as_me:$LINENO: result: $lt_cv_prog_gnu_ld" >&5
src/judy-1.0.5/configure view on Meta::CPAN
echo $ECHO_N "(cached) $ECHO_C" >&6
else
if test -z "$LD"; then
lt_save_ifs="$IFS"; IFS=$PATH_SEPARATOR
for ac_dir in $PATH; do
IFS="$lt_save_ifs"
test -z "$ac_dir" && ac_dir=.
if test -f "$ac_dir/$ac_prog" || test -f "$ac_dir/$ac_prog$ac_exeext"; then
lt_cv_path_LD="$ac_dir/$ac_prog"
# Check to see if the program is GNU ld. I'd rather use --version,
# but apparently some variants of GNU ld only accept -v.
# Break only if it was the GNU/non-GNU ld that we prefer.
case `"$lt_cv_path_LD" -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
test "$with_gnu_ld" != no && break
;;
*)
test "$with_gnu_ld" != yes && break
;;
esac
fi
src/judy-1.0.5/configure view on Meta::CPAN
echo "${ECHO_T}no" >&6; }
fi
test -z "$LD" && { { echo "$as_me:$LINENO: error: no acceptable ld found in \$PATH" >&5
echo "$as_me: error: no acceptable ld found in \$PATH" >&2;}
{ (exit 1); exit 1; }; }
{ echo "$as_me:$LINENO: checking if the linker ($LD) is GNU ld" >&5
echo $ECHO_N "checking if the linker ($LD) is GNU ld... $ECHO_C" >&6; }
if test "${lt_cv_prog_gnu_ld+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
# I'd rather use --version here, but apparently some GNU lds only accept -v.
case `$LD -v 2>&1 </dev/null` in
*GNU* | *'with BFD'*)
lt_cv_prog_gnu_ld=yes
;;
*)
lt_cv_prog_gnu_ld=no
;;
esac
fi
{ echo "$as_me:$LINENO: result: $lt_cv_prog_gnu_ld" >&5
src/judy-1.0.5/src/JudyCommon/JudyDecascade.c view on Meta::CPAN
NumJPs = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, SubExp));
assert(NumJPs);
JU_COPYMEM(Pjpjbl, Pjp, NumJPs); // one subarray at a time.
Pjpjbl += NumJPs;
j__udyFreeJBBJP(PjpRaw, NumJPs, Pjpm); // subarray.
}
j__udyFreeJBB(PjbbRaw, Pjpm); // BranchB itself.
// Finish up: Calculate new JP type (same index size = level in new class),
// and tie new BranchB into parent JP:
Pjp->jp_Type += cJU_JPBRANCH_L - cJU_JPBRANCH_B;
Pjp->jp_Addr = (Word_t) PjblRaw;
return(1);
} // j__udyBranchBToBranchL()
#ifdef notdef
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
//
// Return values:
//
// -1 error; details in JPM
//
// 0 Index already deleted (should never happen, Index is known to be valid)
//
// 1 previously valid Index deleted
//
// 2 same as 1, but in addition the JP now points to a BranchL containing a
// single JP, which should be compressed into the parent branch (if there
// is one, which is not the case for a top-level branch under a JPM)
DBGCODE(uint8_t parentJPtype;) // parent branch JP type.
FUNCTION static int j__udyDelWalk(
Pjp_t Pjp, // current JP under which to delete.
Word_t Index, // to delete.
Word_t ParentLevel, // of parent branch.
Pjpm_t Pjpm) // for returning info to top level.
{
Word_t pop1; // of a leaf.
Word_t level; // of a leaf.
uint8_t digit; // from Index, in current branch.
Pjll_t PjllnewRaw; // address of newly allocated leaf.
Pjll_t Pjllnew;
int offset; // within a branch.
int retcode; // return code: -1, 0, 1, 2.
JUDYLCODE(Pjv_t PjvRaw;) // value area.
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHL:
//
// Come here with level and digit set.
BranchLKeep:
Pjbl = P_JBL(Pjp->jp_Addr);
numJPs = Pjbl->jbl_NumJPs;
assert(numJPs > 0);
DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
// Search for a match to the digit (valid Index => must find digit):
for (offset = 0; (Pjbl->jbl_Expanse[offset]) != digit; ++offset)
assert(offset < numJPs - 1);
Pjp = (Pjbl->jbl_jp) + offset;
// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through
// the BranchL):
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHB:
//
// Come here with level and digit set.
BranchBKeep:
Pjbb = P_JBB(Pjp->jp_Addr);
subexp = digit / cJU_BITSPERSUBEXPB;
bitmap = JU_JBB_BITMAP(Pjbb, subexp);
bitmask = JU_BITPOSMASKB(digit);
assert(bitmap & bitmask); // Index valid => digits bit is set.
DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
// Compute digits offset into the bitmap, with a fast method if all bits are
// set:
offset = ((bitmap == (cJU_FULLBITMAPB)) ?
digit % cJU_BITSPERSUBEXPB :
j__udyCountBitsB(bitmap & JU_MASKLOWEREXC(bitmask)));
Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
Pjp2 = P_JP(Pjp2Raw);
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
// else compressed to a leaf. Variables level, Index, Pjp, and pop1 are in the
// context.
//
// Note: BranchU handling differs from BranchL and BranchB as described above.
#define JU_BRANCHU(cLevel,MaxPop1,LeafType,NullJPType,NewJPType, \
LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
\
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \
assert(ParentLevel > (cLevel)); \
DBGCODE(parentJPtype = JU_JPTYPE(Pjp);) \
\
pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \
\
if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \
{ \
level = (cLevel); \
Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cLevel);\
break; /* descend to next level */ \
} \
assert(pop1 == (MaxPop1)); \
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA,
JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
#endif // JU_64BIT
// A top-level BranchU is different and cannot use JU_BRANCHU(): Dont try to
// compress to a (LEAFW) leaf yet, but leave this for a later deletion
// (hysteresis > 0); just descend through the BranchU:
case cJU_JPBRANCH_U:
DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
level = cJU_ROOTSTATE;
Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
break;
// ****************************************************************************
// LINEAR LEAF:
//
// State transitions while deleting an Index, the inverse of the similar table
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
#ifdef JUDY1
// ****************************************************************************
// FULL POPULATION LEAF:
//
// Convert to a LeafB1 and delete the index. Hysteresis = 0; none is possible.
//
// Note: Earlier the second assertion below said, "== 2", but in fact the
// parent could be at a higher level if a fullpop is under a narrow pointer.
case cJ1_JPFULLPOPU1:
{
Pjlb_t PjlbRaw;
Pjlb_t Pjlb;
Word_t subexp;
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, 2));
assert(ParentLevel > 1); // see above.
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
// If theres just the one Index in the Immed, convert the JP to a JPNULL*
// (should only happen in a BranchU); otherwise delete the Index from the
// Immed. See the state transitions table elsewhere in this file for a summary
// of which Immed types must be handled. Hysteresis = 0; none is possible with
// Immeds.
//
// MACROS FOR COMMON CODE:
//
// Single Index remains in cJU_JPIMMED_*_01; convert JP to null:
//
// Variables Pjp and parentJPtype are in the context.
//
// Note: cJU_JPIMMED_*_01 should only be encountered in BranchUs, not in
// BranchLs or BranchBs (where its improper to merely modify the JP to be a
// null JP); that is, BranchL and BranchB code should have already handled
// any cJU_JPIMMED_*_01 by different means.
#define JU_IMMED_01(NewJPType,ParentJPType) \
\
assert(parentJPtype == (ParentJPType)); \
assert(JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(Index)); \
JU_JPSETADT(Pjp, 0, 0, NewJPType); \
return(1)
// Convert cJ*_JPIMMED_*_02 to cJU_JPIMMED_*_01:
//
// Move the undeleted Index, whichever does not match the least bytes of Index,
// from undecoded-bytes-only (in jp_1Index or jp_LIndex as appropriate) to
// jp_DcdPopO (full-field). Pjp, Index, and offset are in the context.
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);
} // switch
// PROCESS JP -- RECURSIVELY:
//
// For non-Immed JP types, if successful, post-decrement the population count
// at this level, or collapse a BranchL if necessary by copying the remaining
// JP in the BranchL to the parent (hysteresis = 0), which implicitly creates a
// narrow pointer if there was not already one in the hierarchy.
assert(level);
retcode = j__udyDelWalk(Pjp, Index, level, Pjpm);
assert(retcode != 0); // should never happen.
if ((JU_JPTYPE(Pjp)) < cJU_JPIMMED_1_01) // not an Immed.
{
switch (retcode)
{
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
Pjpm = P_JPM(*PPArray); // top object in array (tree).
Pjp = &(Pjpm->jpm_JP); // next object (first branch or leaf).
assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)
|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)
|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));
// WALK THE TREE
//
// Note: Recursive code in j__udyDelWalk() knows how to collapse a lower-level
// BranchL containing a single JP into the parent JP as a narrow pointer, but
// the code here cant do that for a top-level BranchL. The result can be
// PArray -> JPM -> BranchL containing a single JP. This situation is
// unavoidable because a JPM cannot contain a narrow pointer; the BranchL is
// required in order to hold the top digit decoded, and it does not collapse to
// a LEAFW until the population is low enough.
//
// TBD: Should we add a topdigit field to JPMs so they can hold narrow
// pointers?
if (j__udyDelWalk(Pjp, Index, cJU_ROOTSTATE, Pjpm) == -1)
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
offset = Pjbl->jbl_Expanse[numJPs];
Pjbu->jbu_jp[offset] = *Pjp1;
#ifdef SUBEXPCOUNTS
Pjbu->jbu_subPop1[offset/cJU_NUMSUBEXPU] +=
JU_JPDCDPOP0(Pjp1) & popmask + 1;
#endif
}
}
j__udyFreeJBL(PjblRaw, Pjpm); // free old BranchL.
// Plug new values into parent JP:
Pjp->jp_Addr = (Word_t) PjbuRaw;
Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_L; // to BranchU.
// Save global population of last BranchU conversion:
Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;
goto ContinueInsWalk;
} // case cJU_JPBRANCH_L.
src/judy-1.0.5/src/JudyCommon/JudyIns.c view on Meta::CPAN
Word_t DcdP0;
int offset;
Pjlb_t PjlbRaw;
Pjlb_t Pjlb;
offset = j__udySearchLeaf1((Pjll_t) Pjp->jp_1Index, 15, Index);
JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);
// Create a bitmap leaf (special case for Judy1 64-bit only, see usage): Set
// new Index in bitmap, copy an Immed1_15 to the bitmap, and set the parent JP
// EXCEPT jp_DcdPopO, leaving any followup to the caller:
if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
return(-1);
Pjlb = P_JLB(PjlbRaw);
JU_BITMAPSETL(Pjlb, Index);
for (offset = 0; offset < 15; ++offset)
JU_BITMAPSETL(Pjlb, Pjp->jp_1Index[offset]);
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
// - a JPM for tracking memory usage and returning errors
//
// Recursively build a subtree (immediate indexes, leaf, or branch with
// subtrees) and modify the JP accordingly. On the way down, build a BranchU
// (only) for any expanse with *PPop1 too high for a leaf; on the way out,
// convert the BranchU to a BranchL or BranchB if appropriate. Keep memory
// statistics in the JPM.
//
// Return TRUE for success, or FALSE with error information set in the JPM in
// case of error, in which case leave a partially constructed but healthy tree,
// and modify parent population counts on the way out.
//
// Note: Each call of this function makes all modifications to the PjpParent
// it receives; neither the parent nor child calls do this.
FUNCTION static bool_t j__udyInsArray(
Pjp_t PjpParent, // parent JP in/under which to store.
int Level, // initial digits remaining to decode.
PWord_t PPop1, // number of indexes to store.
PWord_t PIndex, // list of indexes to store.
#ifdef JUDYL
Pjv_t PValue, // list of corresponding values.
#endif
Pjpm_t Pjpm) // for memory and errors.
{
Pjp_t Pjp; // lower-level JP.
Word_t Pjbany; // any type of branch.
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
#define SETJPNULL_PARENT \
JU_JPSETADT(PjpParent, 0, 0, cJU_JPNULL1 + Level - 1);
// Variation to set a specified JP (in a branch being built) to a precomputed
// null JP:
#define SETJPNULL(Pjp) *(Pjp) = JPnull
// Handle complete (as opposed to partial) memory allocation failure: Set the
// parent JP to an appropriate null type (to leave a consistent tree), zero the
// callers population count, and return FALSE:
//
// Note: At Level == cJU_ROOTSTATE this sets the JPMs JPs jp_Type to a bogus
// value, but it doesnt matter because the JPM should be deleted by the
// caller.
#define NOMEM { SETJPNULL_PARENT; *PPop1 = 0; return(FALSE); }
// Allocate a Leaf1-N and save the address in Pjll; in case of failure, NOMEM:
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
Pjv = P_JV(PjvRaw);
JU_COPYMEM(Pjv, PValue, pop1sub);
JL_JLB_PVALUE(Pjlb, offset) = PjvRaw; // first-tier pointer.
PValue += pop1sub;
} // for each subexpanse
#endif // JUDYL
// Attach new LeafB1 to parent JP; note use of *PPop1 possibly < pop1:
JU_JPSETADT(PjpParent, (Word_t) PjlbRaw,
(*PIndex & cJU_DCDMASK(1)) | (*PPop1 - 1), cJU_JPLEAF_B1);
return(retval);
} // JPLEAF_B1 or JPFULLPOPU1
// BUILD JPBRANCH_U*:
src/judy-1.0.5/src/JudyCommon/JudyInsArray.c view on Meta::CPAN
j__udyFreeJBU(PjbuRaw, Pjpm);
Pjbany = (Word_t) PjbbRaw;
JPtype = branchB_JPtype[levelsub];
} // compress to BranchB
// COMPLETE OR PARTIAL SUCCESS:
//
// Attach new branch (under Pjp, with JPtype) to parent JP; note use of *PPop1,
// possibly reduced due to partial failure.
SetParent:
(PjpParent->jp_Addr) = Pjbany;
(PjpParent->jp_Type) = JPtype;
if (Level < cJU_ROOTSTATE) // PjpParent not in JPM:
{
Word_t DcdP0 = (*PIndex & cJU_DCDMASK(levelsub)) | (*PPop1 - 1);
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
// OVERVIEW OF Judy*Prev():
//
// Use a reentrant switch statement (state machine, SM1 = "get") to decode the
// callers *PIndex-1, starting with the (PArray), through branches, if
// any, down to an immediate or a leaf. Look for *PIndex-1 in that leaf, and
// if found, return it.
//
// A dead end is either a branch that does not contain a JP for the appropriate
// digit in *PIndex-1, or a leaf that does not contain the undecoded digits of
// *PIndex-1. Upon reaching a dead end, backtrack through the leaf/branches
// that were just traversed, using a list (history) of parent JPs that is built
// while going forward in SM1Get. Start with the current leaf or branch. In a
// backtracked leaf, look for an Index less than *PIndex-1. In each
// backtracked branch, look "sideways" for the next JP, if any, lower than the
// one for the digit (from *PIndex-1) that was previously decoded. While
// backtracking, if a leaf has no previous Index or a branch has no lower JP,
// go to its parent branch in turn. Upon reaching the JRP, return failure, "no
// previous Index". The backtrack process is sufficiently different from
// SM1Get to merit its own separate reentrant switch statement (SM2 =
// "backtrack").
//
// While backtracking, upon finding a lower JP in a branch, there is certain to
// be a "prev" Index under that JP (unless the Judy array is corrupt).
// Traverse forward again, this time taking the last (highest, right-most) JP
// in each branch, and the last (highest) Index upon reaching an immediate or a
// leaf. This traversal is sufficiently different from SM1Get and SM2Backtrack
// to merit its own separate reentrant switch statement (SM3 = "findlimit").
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
// passes control to SM2Backtrack to look sideways, even in a leaf. Actually
// its a little more efficient for the SM1Get leaf cases to shortcut this and
// take care of the sideways searches themselves. Hence the history list only
// contains branch JPs, and SM2Backtrack only handles branches. In fact, even
// the branch handling cases in SM1Get do some shortcutting (sideways
// searching) to avoid pushing history and calling SM2Backtrack unnecessarily.
//
// Upon reaching an Index to return after backtracking, *PIndex must be
// modified to the found Index. In principle this could be done by building
// the Index from a saved rootdigit (in the top branch) plus the Dcd bytes from
// the parent JP plus the appropriate Index bytes from the leaf. However,
// Immediates are difficult because their parent JPs lack one (last) digit. So
// instead just build the *PIndex to return "top down" while backtracking and
// findlimiting.
//
// This function is written iteratively for speed, rather than recursively.
//
// CAVEATS:
//
// Why use a backtrack list (history stack), since it has finite size? The
// size is small for Judy on both 32-bit and 64-bit systems, and a list (really
// just an array) is fast to maintain and use. Other alternatives include
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
// should be pretty cheap for linear and bitmap branches, but it could result
// in up to 31 unnecessary additional cache line fills (in extreme cases) for
// every uncompressed branch traversed. We have considered means of attaching
// to or hiding within an uncompressed branch (in null JPs) a "cache line map"
// or other structure, such as an offset to the next non-null JP, that would
// speed this up, but it seems unnecessary merely to avoid having a
// finite-length list (array). (If JudySL is ever made "native", the finite
// list length will be an issue.)
//
// Restarting at the top of the Judy array after a dead end requires a careful
// modification of *PIndex-1 to decrement the digit for the parent branch and
// set the remaining lower digits to all 1s. This must be repeated each time a
// parent branch contains another dead end, so even though it should all happen
// in cache, the CPU time can be excessive. (For JudySL or an equivalent
// "infinitely deep" Judy array, consider a hybrid of a large, finite,
// "circular" list and a restart-at-top when the list is backtracked to
// exhaustion.)
//
// Why search for *PIndex-1 instead of *PIndex during SM1Get? In rare
// instances this prevents an unnecessary decode down the wrong path followed
// by a backtrack; its pretty cheap to set up initially; and it means the
// SM1Get machine can simply return if/when it finds that Index.
//
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
Word_t pop1 = 0; // in a leaf.
#else
Word_t pop1; // in a leaf.
#endif
int offset; // linear branch/leaf, from j__udySearchLeaf*().
int subexp; // subexpanse in a bitmap branch.
Word_t bitposmask; // bit in bitmap for Index.
// History for SM2Backtrack:
//
// For a given histnum, APjphist[histnum] is a parent JP that points to a
// branch, and Aoffhist[histnum] is the offset of the NEXT JP in the branch to
// which the parent JP points. The meaning of Aoffhist[histnum] depends on the
// type of branch to which the parent JP points:
//
// Linear: Offset of the next JP in the JP list.
//
// Bitmap: Which subexpanse, plus the offset of the next JP in the
// subexpanses JP list (to avoid bit-counting again), plus for Judy*Next(),
// hidden one byte to the left, which digit, because Judy*Next() also needs
// this.
//
// Uncompressed: Digit, which is actually the offset of the JP in the branch.
//
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
case cJU_JPBRANCH_L6: CHECKDCD(6); SM1PREPB(6, SM1BranchL);
case cJU_JPBRANCH_L7: CHECKDCD(7); SM1PREPB(7, SM1BranchL);
#endif
case cJU_JPBRANCH_L: SM1PREPB(cJU_ROOTSTATE, SM1BranchL);
// Common code (state-independent) for all cases of linear branches:
SM1BranchL:
Pjbl = P_JBL(Pjp->jp_Addr);
// Found JP matching current digit in *PIndex; record parent JP and the next
// JPs offset, and iterate to the next JP:
if ((offset = j__udySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse),
Pjbl->jbl_NumJPs, digit)) >= 0)
{
HISTPUSH(Pjp, offset);
Pjp = (Pjbl->jbl_jp) + offset;
goto SM1Get;
}
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
subexp = digit / cJU_BITSPERSUBEXPB;
assert(subexp < cJU_NUMSUBEXPB); // falls in expected range.
bitposmask = JU_BITPOSMASKB(digit);
offset = SEARCHBITMAPB(JU_JBB_BITMAP(Pjbb, subexp), digit,
bitposmask);
// right range:
assert((offset >= -1) && (offset < (int) cJU_BITSPERSUBEXPB));
// Found JP matching current digit in *PIndex:
//
// Record the parent JP and the next JPs offset; and iterate to the next JP.
// if (JU_BITMAPTESTB(Pjbb, digit)) // slower.
if (JU_JBB_BITMAP(Pjbb, subexp) & bitposmask) // faster.
{
// not negative since at least one bit is set:
assert(offset >= 0);
HISTPUSH(Pjp, HISTPUSHBOFF(subexp, offset, digit));
if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
case cJU_JPBRANCH_U: SM1PREPB(cJU_ROOTSTATE, SM1BranchU);
// Common code (state-independent) for all cases of uncompressed branches:
SM1BranchU:
Pjbu = P_JBU(Pjp->jp_Addr);
Pjp2 = (Pjbu->jbu_jp) + digit;
// Found JP matching current digit in *PIndex:
//
// Record the parent JP and the next JPs digit, and iterate to the next JP.
//
// TBD: Instead of this, just goto SM1Get, and add cJU_JPNULL* cases to the
// SM1Get state machine? Then backtrack? However, it means you cant detect
// an inappropriate cJU_JPNULL*, when it occurs in other than a BranchU, and
// return JU_RET_CORRUPT.
if (! JPNULL(JU_JPTYPE(Pjp2))) // digit has a JP.
{
HISTPUSH(Pjp, digit);
Pjp = Pjp2;
src/judy-1.0.5/src/JudyCommon/JudyPrevNextEmpty.c view on Meta::CPAN
//
// LEAF PRIMARY dead end: Finding a valid (non-empty) index in an immediate or
// leaf matching Index. Search sideways in the immediate/leaf for the
// previous/next empty index; if found, set *PIndex to match and return success.
//
// LEAF SECONDARY dead end: Reaching the end of an immediate or leaf during a
// sideways search after a leaf primary dead end. Just as for a branch
// secondary dead end, restart at the top of the tree with Index set to the
// lowest/highest index possible in the whole immediate/leafs expanse.
// TBD: If leaf secondary dead end occurs, could shortcut and treat it as a
// branch primary dead end; but this would require remembering the parent
// branchs type and offset (a "one-deep stack"), and also wrestling with
// narrow pointers, at least for leaves (but not for immediates).
//
// Note some ASYMMETRIES between SearchValid and SearchEmpty:
//
// - The SearchValid code, upon descending through a narrow pointer, if Index
// is outside the expanse of the subsidiary node (effectively a secondary
// dead end), must decide whether to backtrack or findlimit. But the
// SearchEmpty code simply returns success (Index is empty).
//
// - Similarly, the SearchValid code, upon finding no previous/next index in
// the expanse of a narrow pointer (again, a secondary dead end), can simply
// start to backtrack at the parent JP. But the SearchEmpty code would have
// to first determine whether or not the parent JPs narrow expanse contains
// a previous/next empty index outside the subexpanse. Rather than keeping a
// parent state stack and backtracking this way, upon a secondary dead end,
// the SearchEmpty code simply restarts at the top of the tree, whether or
// not a narrow pointer is involved. Again, see the equivalent comments in
// JudyPrevNext.c for comparison.
//
// This function is written iteratively for speed, rather than recursively.
//
// TBD: Wed like to enhance this function to make successive searches faster.
// This would require saving some previous state, including the previous Index
// returned, and in which leaf it was found. If the next call is for the same
// Index and the array has not been modified, start at the same leaf. This
src/judy-1.0.5/src/JudyCommon/JudyPrevNextEmpty.c view on Meta::CPAN
#define JPNULL(Type) (((Type) >= cJU_JPNULL1) && ((Type) <= cJU_JPNULLMAX))
// CHECK FOR A FULL JP:
//
// Given a JP, indicate if it is fully populated. Use digits, pop0mask, and
// possfullJP1..3 in the context.
//
// This is a difficult problem because it requires checking the Pop0 bits for
// all-ones, but the number of bytes depends on the JP type, which is not
// directly related to the parent branchs type or level -- the JPs child
// could be under a narrow pointer (hence not full). The simple answer
// requires switching on or otherwise calculating the JP type, which could be
// slow. Instead, in SMPREPB* precalculate pop0mask and also record in
// possfullJP1..3 the child JP (branch) types that could possibly be full (one
// level down), and use them here. For level-2 branches (with digits == 2),
// the test for a full child depends on Judy1/JudyL.
//
// Note: This cannot be applied to the JP in a JPM because it doesnt have
// enough pop0 digits.
//
src/judy-1.0.5/src/JudyCommon/JudyPrivate.h view on Meta::CPAN
// application code.
#ifndef DEBUG
#define NDEBUG 1 // must be 1 for "#if".
#endif
// Shorthand notations to avoid #ifdefs for single-line conditional statements:
//
// Warning: These cannot be used around compiler directives, such as
// "#include", nor in the case where Code contains a comma other than nested
// within parentheses or quotes.
#ifndef DEBUG
#define DBGCODE(Code) // null.
#else
#define DBGCODE(Code) Code
#endif
#ifdef JUDY1
#define JUDY1CODE(Code) Code
#define JUDYLCODE(Code) // null.
src/judy-1.0.5/src/JudyCommon/JudyPrivate.h view on Meta::CPAN
// Given a pointer to an array of "even" (native), same-sized objects
// (indexes), the current population of the array, an offset in the array, and
// a new Index to insert, "shift up" the array elements (Indexes) above the
// insertion point and insert the new Index. Assume there is sufficient memory
// to do this.
//
// In these macros, "i_offset" is an index offset, and "b_off" is a byte
// offset for odd Index sizes.
//
// Note: Endian issues only arise fro insertion, not deletion, and even for
// insertion, they are transparent when native (even) objects are used, and
// handled explicitly for odd (non-native) Index sizes.
//
// Note: The following macros are tricky enough that there is some test code
// for them appended to this file.
#define JU_INSERTINPLACE(PARRAY,POP1,OFFSET,INDEX) \
assert((long) (POP1) > 0); \
assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
{ \
Word_t i_offset = (POP1); \
src/judy-1.0.5/src/JudyCommon/JudyPrivateBranch.h view on Meta::CPAN
((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)))
#endif // ! _JUDY_PRIVATE_BRANCH_INCLUDED
#ifdef TEST_INSDEL
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
} // while.
} // NOTREACHED, JudySLIns()
// ****************************************************************************
// J U D Y S L D E L
//
// See the comments in JudySLGet(), which is somewhat similar.
//
// Unlike JudySLGet() and JudySLIns(), recurse downward through the tree of
// JudyL arrays to find and delete the given Index, if present, and then on the
// way back up, any of its parent arrays which ends up empty.
//
// TECHNICAL NOTES:
//
// Recursion seems bad, but this allows for an arbitrary-length Index. Also, a
// more clever iterative solution that used JudyLCount() (see below) would
// still require a function call per tree level, so why not just recurse?
//
// An earlier version (1.20) used a fixed-size stack, which limited the Index
// size. We were going to replace this with using JudyLCount(), in order to
// note and return to (read this carefully) the highest level JudyL array with
src/judy-1.0.5/test/SLcompare.c view on Meta::CPAN
wc /data/domnames.txt
28826508 28826508 488227095 /data/domnames.txt
For the curious, JudySL (I.E JSLI/G macros in this program) is simply an
application subroutine that uses JudyL to the work. JudyL is a very
scaleable word to word (or pointer) mapper. JudySL is implemented as a
digital tree using JudyL arrays as 2^32 (or 2^64 in 64 bit machines)
wide (virtual) nodes. Each level in the digital tree decodes the next 4
(or 8) bytes of the line/string until only one entry would be in the
node. Then the remaining undecoded portion of the line is stored as a
string from the parent node. A digital tree does not need rotation or
balancing. In practice, digital trees are rarely use because of their
poor memory efficiency in the nodes and a tendency to have large depths.
These problems are solved in the Judy algorithm. For more details see
application notes on: www.sourcejudy.com. And for the really curious,
a technical paper is available in the application section. If you would
like to be a reviewer, contact Doug Baskins at <doug@sourcejudy.com>
*/
#include <unistd.h>
src/judy-1.0.5/test/jbgraph view on Meta::CPAN
getopt_PARM="?C:D:EGIL:MN:P:SVc:d:g:ilmno:prsuvx:y:"
set -- `getopt ${getopt_PARM} $*` # Place options in argc/argv.
if [ "${?}" != "0" ]; then # If getopt returns an errror.
${v}echo "${C}.${0}: \${?}=${?}, USAGE message from return code."
echo "${USAGE}"
exit 1
fi
while [ ${#} -gt 0 ] # while there are options...
do # ( for vi parenthesis matching
${v}echo "${C}.${0}: parsing option \"${1}\", then \"${2}\""
case ${1} in
-C)
OPT_C="${1}"
OPT_C_PARM="${2}" # GNU_CMDFILE name.
${v}echo "${C}.${0}: OPT_C=${OPT_C}, # -C GNU_CMDFILE name."
${v}echo "${C}.${0}: OPT_C_PARM=${OPT_C_PARM}, # GNU_CMDFILE name."
export GNU_CMDFILE="${OPT_C_PARM}"
MSG="# GNU_CMDFILE name."
${v}echo "${C}.${0}: GNU_CMDFILE=${GNU_CMDFILE}, ${MSG}"
shift
;; # ( for vi parenthesis matching
-D)
OPT_D="${1}"
OPT_D_PARM="${2}" # LP_DEV name.
${v}echo "${C}.${0}: OPT_D=${OPT_D}, # -D LP_DEV printer device."
#${v}echo "${C}.${0}: OPT_D_PARM=${OPT_D_PARM}, # LP_DEV name."
LP_DEV="${OPT_D_PARM}"
${v}echo "${C}.${0}: LP_DEV=${LP_DEV}, # LP_DEV name."
shift
;; # ( for vi parenthesis matching
-E)
OPT_E="${1}"
${v}echo "${C}.${0}: OPT_E=${OPT_E}, # -E use embedded options"
;; # ( for vi parenthesis matching
-G)
OPT_G="${1}"
${v}echo "${C}.${0}: OPT_G=${OPT_G}, # -G grid lines on."
;; # ( for vi parenthesis matching
-H)
OPT_H="${1}"
${v}echo "${C}.${0}: OPT_H=${OPT_H}, # -H default column headings."
;; # ( for vi parenthesis matching
-I)
OPT_I="${1}"
${v}echo "${C}.${0}: OPT_I=${OPT_I}, # -I Memory used / index."
CMN="12"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
;; # ( for vi parenthesis matching
-L)
OPT_L="${1}"
${v}echo "${C}.${0}: OPT_L=${OPT_L}, -L set logscale axis"
OPT_L_PARM="${2}" # axis name, x or y
if [ ${OPT_L_PARM} = "x" ]; then
OPT_L_xaxis="${OPT_L_PARM}"
elif [ ${OPT_L_PARM} = "y" ]; then
OPT_L_yaxis="${OPT_L_PARM}"
else
MSG="must be either \"x\" or \"y\" axis. exit 5"
echo "${C}.${0}: ERROR, OPT_L_PARM=${OPT_L_PARM} ${MSG}"
exit 5
fi
OPT_NL="" # -L turn off -NL.
shift
;; # ( for vi parenthesis matching
-M)
OPT_M="${1}"
${v}echo "${C}.${0}: OPT_M=${OPT_M}, # -M Memory used and free."
CMN="8"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
;; # ( for vi parenthesis matching
-N)
OPT_N="${1}"
OPT_N_PARM="${2}" # LP_DEV name.
${v}echo "${C}.${0}: OPT_N=${OPT_N}, # -N not option"
${v}echo "${C}.${0}: OPT_N_PARM=${OPT_N_PARM}, # Turn option off."
if [ "${OPT_N_PARM}" = "E" ]; then
OPT_E="" # -E use embedded options
OPT_NE="-NE" # -NE turn off -E.
elif [ "${OPT_N_PARM}" = "L" ]; then
src/judy-1.0.5/test/jbgraph view on Meta::CPAN
OPT_L_yaxis=""
OPT_NL="-NL" # -NL turn off -L.
elif [ "${OPT_N_PARM}" = "G" ]; then
OPT_G="" # -G grid lines on.
OPT_NG="-NG" # -NG turn off -G.
elif [ "${OPT_N_PARM}" = "H" ]; then
OPT_H="" # -H default column headings.
OPT_NH="-NH" # -NH turn off -H.
fi
shift
;; # ( for vi parenthesis matching
-P)
OPT_P="${1}"
OPT_P_PARM="${2}" # GNU_PSFILE name.
${v}echo "${C}.${0}: OPT_P=${OPT_P}, # -P GNU_PSFILE name."
#${v}echo "${C}.${0}: OPT_P_PARM=${OPT_P_PARM}, # GNU_PSFILE name."
GNU_PSFILE="${OPT_P_PARM}"
${v}echo "${C}.${0}: GNU_PSFILE=${GNU_PSFILE}, # GNU_PSFILE name."
shift
;; # ( for vi parenthesis matching
-S)
OPT_S="${1}"
${v}echo "${C}.${0}: OPT_S=${OPT_S}, # -S save files."
;; # ( for vi parenthesis matching
-V)
OPT_V="${1}"
${v}echo "${C}.${0}: OPT_V=${OPT_V}, # -V vi the plot file."
;; # ( for vi parenthesis matching
-c)
OPT_c="${1}"
OPT_c_PARM="${2}" # COLUMN_NUMBER.
${v}echo "${C}.${0}: OPT_c=${OPT_c}, # -c plot column number."
${v}echo "${C}.${0}: OPT_c_PARM=${OPT_c_PARM}, # COLUMN_NUMBER."
if [ ${OPT_c_PARM} -ge ${#CHA[*]} ] ||
[ ${OPT_c_PARM} -le 0 ]; then
MSG="must be greater than 0 and less than ${#CHA[*]}. exit 6"
echo "${C}.${0}: ERROR, OPT_c_PARM=${OPT_c_PARM} ${MSG}"
exit 6
fi
CMN="${OPT_c_PARM}"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
shift
;; # ( for vi parenthesis matching
-d)
OPT_d="${1}"
OPT_d_PARM="${2}" # DERIVATIVE_TYPE
${v}echo "${C}.${0}: OPT_d=${OPT_d}, # -d plot derivative type."
${v}echo "${C}.${0}: OPT_d_PARM=${OPT_d_PARM}, # DERIVITIVE_TYPE"
if [ "${OPT_d_PARM}" = "i" ]; then
OPT_di="${OPT_d_PARM}"
CMN="3"
elif [ "${OPT_d_PARM}" = "m" ]; then
src/judy-1.0.5/test/jbgraph view on Meta::CPAN
CMN="7"
elif [ "${OPT_d_PARM}" = "r" ]; then
OPT_dr="${OPT_d_PARM}"
CMN="5"
else
echo "${C}.${0}: ERROR, ${OPT_d_PARM} must be one of i, m, r."
fi
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
shift
;; # ( for vi parenthesis matching
-g)
OPT_g="${1}"
OPT_g_PARM="${2}" # Option parameter
${v}echo "${C}.${0}: OPT_g=${OPT_g}, # -g geometry description."
${v}echo "${C}.${0}: OPT_g_PARM=${OPT_g_PARM}, # window geometry"
GNU_GEOMETRY="-geometry ${OPT_g_PARM}" # Environment geometry.
MSG="# window geometry"
${v}echo "${C}.${0}: GNU_GEOMETRY=${GNU_GEOMETRY}, ${MSG}"
shift
;; # ( for vi parenthesis matching
-i)
OPT_i="${1}"
${v}echo "${C}.${0}: OPT_i=${OPT_i}, # -i plot insert."
CMN="2"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
;; # ( for vi parenthesis matching
-l)
OPT_l="${1}"
${v}echo "${C}.${0}: OPT_l=${OPT_l}, # -l plot leaf data."
CMN="10"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
CMN="11"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
;; # ( for vi parenthesis matching
-m)
OPT_m="${1}"
${v}echo "${C}.${0}: OPT_m=${OPT_m}, # -m plot memory malloced."
CMN="9"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
;; # ( for vi parenthesis matching
-n)
OPT_n="${1}"
MSG="# -n number plot descriptions."
${v}echo "${C}.${0}: OPT_n=${OPT_n}, ${MSG}"
;; # ( for vi parenthesis matching
-o)
OPT_o="${1}"
OPT_o_PARM="${2}" # Option parameter
MSG="# -o LP_OPT printer option(s)."
${v}echo "${C}.${0}: OPT_o=${OPT_o}, ${MSG}"
MSG="# -o LP_OPT printer option(s)."
${v}echo "${C}.${0}: OPT_o_PARM=${OPT_o_PARM}, ${MSG}"
# Check for duplicates, only add to LP_OPT if not a duplicate.
LP_SET="`echo ${LP_OPT} | adjust -m1 | grep -- -${OPT_o_PARM}`"
if [ "${LP_SET}" != "-${OPT_o_PARM}" ];
then
LP_OPT="${LP_OPT} -${OPT_o_PARM}"
fi
unset LP_SET
${v}echo "${C}.${0}: LP_OPT=${LP_OPT}, # LP_OPT printer option(s)."
shift
;; # ( for vi parenthesis matching
-p)
OPT_p="${1}"
${v}echo "${C}.${0}: OPT_p=${OPT_p}, # -p print the plot."
;; # ( for vi parenthesis matching
-q)
OPT_v="${1}"
v='eval #' # Set verbose off (quiet).
${v}echo "${C}.${0}: OPT_v=${OPT_v}, # -q quiet mode."
;; # ( for vi parenthesis matching
-r)
OPT_r="${1}"
${v}echo "${C}.${0}: OPT_r=${OPT_r}, # -r plot retrieve."
CMN="4"
COL[$CMN]="${CMN}"
${v}echo "${C}.${0}: COL[$CMN]=${COL[$CMN]}"
;; # ( for vi parenthesis matching
-v)
OPT_v="${1}"
v="" # Set verbose on.
${v}echo "${C}.${0}: OPT_v=${OPT_v}, # -v verbose mode."
${v}echo
;; # ( for vi parenthesis matching
-x)
OPT_x="${1}"
OPT_x_PARM="${2}" # Option parameter
${v}echo "${C}.${0}: OPT_x=${OPT_x}, # -x xRANGE, scale range."
#${v}echo "${C}.${0}: OPT_x_PARM=${OPT_x_PARM}, # parameter desc."
xRANGE="${OPT_x_PARM}"
${v}echo "${C}.${0}: xRANGE=${xRANGE}, # parameter desc."
shift
;; # ( for vi parenthesis matching
-y)
OPT_y="${1}"
OPT_y_PARM="${2}" # Option parameter
${v}echo "${C}.${0}: OPT_y=${OPT_y}, # -y yRANGE, scale range."
#${v}echo "${C}.${0}: OPT_y_PARM=${OPT_y_PARM}, # parameter desc."
yRANGE="${OPT_y_PARM}"
${v}echo "${C}.${0}: yRANGE=${yRANGE}, # parameter desc."
shift
;; # ( for vi parenthesis matching
-u)
OPT_u="-u"
${v}echo "${C}.${0}: OPT_u=${OPT_u}, # -u Usage message."
echo "${USAGE}"
exit 4
;; # ( for vi parenthesis matching
-a)
OPT_a="${1}"
${v}echo "${C}.${0}: OPT_a=${OPT_a}, # -a Option description."
;; # ( for vi parenthesis matching
-b)
OPT_b="${1}"
OPT_b_PARM="${2}" # Option parameter
${v}echo "${C}.${0}: OPT_b=${OPT_b}, # -b Option description."
${v}echo "${C}.${0}: OPT_b_PARM=${OPT_b_PARM}, # parameter desc."
shift
;; # ( for vi parenthesis matching
--)
shift # Remove the "--".
break
;; # ( for vi parenthesis matching
*)
echo "${C}.${0}: Option not understood. \"${1}\""
echo "USAGE message follows: "
echo "${USAGE}" # USAGE message
exit 2
;;
esac
shift
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
`head:' | Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk of same size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk of same size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pointer to left child (child[0]) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pointer to right child (child[1]) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pointer to parent |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| bin index of this chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*/
struct malloc_tree_chunk {
INTERNAL_SIZE_T prev_size; /* same as in malloc_chunk */
INTERNAL_SIZE_T size;
struct malloc_tree_chunk* fd; /* double links -- used only if free. */
struct malloc_tree_chunk* bk;
struct malloc_tree_chunk* child[2];
struct malloc_tree_chunk* parent;
bin_index_t index;
};
typedef struct malloc_tree_chunk* tchunkptr;
typedef struct malloc_tree_chunk* tbinptr;
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
}
static INTERNAL_SIZE_T check_tree_fields(tchunkptr t) {
INTERNAL_SIZE_T size = chunksize(t);
assert(size >= MIN_TREEBIN_SIZE);
do_check_chunk(((mchunkptr)t));
assert(!inuse(t));
assert(t->fd->bk == t);
assert(t->bk->fd == t);
assert(t->parent != t);
assert(t->child[0] != t);
assert(t->child[1] != t);
if (t->child[0] != 0 && t->child[1] != 0) {
check_all_less(t->child[0], chunksize(t->child[1]));
check_all_greater(t->child[1], chunksize(t->child[0]));
}
return size;
}
static INTERNAL_SIZE_T do_check_tree(tchunkptr t) {
tchunkptr p;
tchunkptr h;
INTERNAL_SIZE_T total = check_tree_fields(t);
/* If t is on a same-sized list, another node on list must have a parent */
if (t->parent == 0) {
h = t->bk;
while (h != t && h->parent == 0)
h = h->bk;
assert(h != t);
}
else
h = t;
assert (h->parent->child[0] == h ||
h->parent->child[1] == h ||
*((tbinptr*)(h->parent)) == h);
/* only one node on a same-sized list has parent or children */
p = h->bk;
while (p != h) {
assert(p->child[0] == 0);
assert(p->child[1] == 0);
assert(p->parent == 0);
assert(chunksize(p) == chunksize(h));
total += check_tree_fields(p);
p = p->bk;
}
if (h->child[0] != 0) {
assert(h->child[0]->parent == h);
total += do_check_tree(h->child[0]);
}
if (h->child[1] != 0) {
assert(h->child[1]->parent == h);
total += do_check_tree(h->child[1]);
}
return total;
}
static void do_check_links(mchunkptr p) {
if (in_smallbin_range(chunksize(p))) {
assert(p->fd->bk == p);
assert(p->bk->fd == p);
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
tbinptr* bin = tbin_at(av, idx);
tchunkptr t = *bin;
x->child[0] = 0;
x->child[1] = 0;
x->index = idx;
if (t == 0) {
av->treebits |= idx2bit(idx);
*bin = x;
x->parent = (tchunkptr)bin;
x->fd = x;
x->bk = x;
}
else {
bin_index_t shift = bitshift_for_index(idx);
tchunkptr b;
check_tree(t);
while (chunksize(t) != nb) {
tchunkptr* pchild = &(t->child[(nb >> shift--) & 1]);
if (*pchild != 0) {
t = *pchild;
}
else {
*pchild = x;
x->parent = t;
x->fd = x;
x->bk = x;
return;
}
}
/* Link in same-sized node */
b = t->bk;
x->parent = 0;
x->fd = t;
x->bk = b;
b->fd = t->bk = x;
}
}
static void transfer_tree_links(tchunkptr oldt, tchunkptr newt) {
tchunkptr p = oldt->parent;
newt->parent = p;
if (p->child[0] == oldt)
p->child[0] = newt;
else if (p->child[1] == oldt)
p->child[1] = newt;
else
*((tbinptr*)p) = newt;
if ( (newt->child[0] = oldt->child[0]) != 0)
newt->child[0]->parent = newt;
if ( (newt->child[1] = oldt->child[1]) != 0)
newt->child[1]->parent = newt;
}
static tchunkptr find_replacement(tchunkptr t) {
/*
Unless t is itself a leaf node, we must replace t with a leaf
node (not merely one with an open left or right, as with binary
search trees), to make sure that lefts and rights of descendents
correspond properly to bit masks. We use the leftmost leaf of
right child, or, if there is no right child, the rightmost leaf
of left child. We could use any other leaf, but these choices
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
if ((c = *(cp = &(t->child[0]->child[1]))) == 0)
c = *(cp = &(t->child[0]));
assert(c != 0);
for (;;) {
if (c->child[0] != 0)
c = *(cp = &(c->child[0]));
else if (c->child[1] != 0)
c = *(cp = &(c->child[1]));
else {
*cp = 0; /* unlink from parent */
return c;
}
}
}
static void unlink_leaf_node(mstate av, tchunkptr t) {
tchunkptr p = t->parent;
if (p->child[0] == t)
p->child[0] = 0;
else if (p->child[1] == t)
p->child[1] = 0;
else {
assert(is_tbin(av, p));
*((tbinptr*)p) = 0;
av->treebits &= ~idx2bit(t->index);
}
}
static void unlink_chained_node(tchunkptr t) {
tchunkptr bck = t->bk;
tchunkptr fwd = t->fd;
fwd->bk = bck;
bck->fd = fwd;
/* t's parent is nonnull if t was head of chain */
if (t->parent != 0)
transfer_tree_links(t, fwd);
check_tree(fwd);
}
/*
----------- other helper functions -----------
We expect these to be inlined
*/
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
if (c == t) {
if (t->child[0] == t->child[1]) {
unlink_leaf_node(av, t);
return;
}
else {
c = find_replacement(t);
}
}
else {
if (t->parent == 0) {
return;
}
}
transfer_tree_links(t, c);
check_tree(c);
}
}
static Void_t* use_treechunk(mstate av,
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
tchunkptr r = (tchunkptr)(chunk_at_offset(bestchunk, nb));
set_head(bestchunk, nb | PREV_INUSE);
set_head(r, rsize | PREV_INUSE);
set_foot(r, rsize);
*vbin = r;
r->fd = r;
r->bk = r;
r->child[0] = 0;
r->child[1] = 0;
r->parent = (tchunkptr)vbin;
r->index = vidx;
check_malloced_chunk((mchunkptr)bestchunk, nb);
return chunk2mem(bestchunk);
}
}
else {
do {
CHUNK_SIZE_T csize = chunksize(c);
if (csize < bestsize) {
bestchunk = c;
src/judy-1.0.5/test/timeit.h view on Meta::CPAN
// gcc compiler does not optimize out the register access:
#define TIMER_vars(T) \
register volatile cycles_t __start_##T, __stop_##T; \
struct timeval __TVBeg_##T, __TVEnd_##T
// This seems required for linux_ia32:
// Older code (see 4.13) used rdtscl(), but this is not portable and does not
// result in a 64-bit value, unlike get_cycles(), which apparently takes
// advantage of a 64-bit control register on both IA32 and IPF => always
// high-res timing with no rollover issues. Note, cycles_t is unsigned, so the
// math works even in case of a rollover.
#define __START_HRTm(T) __start_##T = get_cycles()
#define __END_HRTm(T) __stop_##T = get_cycles()
#define STARTTm(T) __START_HRTm(T)
#define ENDTm(D,T) { __END_HRTm(T); __HRONLY(D,T); }
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
#define PUTC(Char) (void) putc((int) (Char), stdout)
#ifndef DEBUG
#define NDEBUG // turn off assertions by default.
#endif
// Shorthand notation to avoid #ifdefs for single-line conditional statement:
//
// Warning: This cannot be used around compiler directives, such as
// "#include", nor in the case where Code contains a comma other than nested
// within parentheses or quotes.
#ifndef DEBUG
#define DBGCODE(Code) // null.
#else
#define DBGCODE(Code) Code
#endif
// ****************************************************************************
// MISCELLANEOUS GLOBAL VALUES:
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
#define TAG(DN_Type) (g_dntype[DN_Type].dnt_tag)
#define SAVETAG(DN_Type) (g_dntype[DN_Type].dnt_savetag)
#define NEST(DN_Type) (g_dntype[DN_Type].dnt_nest)
// ****************************************************************************
// DOCUMENT NODE DATA STRUCTURES:
//
// Document nodes are saved in a doubly-linked tree of docnodes. Each docnode
// points sideways to a doubly-linked list of sibling docnodes for
// previous/successive unnested document objects, plus points to its parent and
// to the first of a sideways doubly-linked child list of nested objects. All
// data lives in malloc'd memory.
//
// 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)
Pdn_t g_Pdnhead = PDNNULL; // head of docnode tree.
// ****************************************************************************
// FUNCTION SIGNATURES (forward declarations):
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
void ExtractHeader( Pdn_t Pdn, char ** PFileRev,
char ** PPageName, char ** PPageSection,
char * PLcLetter, char ** PRevision);
char * ExtractText( Pdn_t Pdn);
void ExtractPageInfo(Pdn_t Pdn, char * Pch,
char ** PPageName, char ** PPageSection,
char * PLcLetter);
int TagType(char * Tag, bool_t * isclosing, char * Filename, int Linenum);
Pdn_t AppDocNode( Pdn_t Pdn, int linenum);
Pdn_t NewDocNode( Pdn_t dn_Pparent, int linenum);
char * SaveDocNode(Pdn_t Pdn, int DN_Type, char * Pch,
char * Filename, int Linenum);
bool_t ParentPre(Pdn_t Pdn, bool_t BoldOnly);
void MarkNoEmit( Pdn_t Pdn, bool_t Font);
void EmitText( char * Pch, int InPRE, int Linenum);
void EmitTextPRE( char * Pch, int InPRE);
void EmitTextBS( char * Pch);
bool_t NoWhiteSpace( char * Pch);
int CountNewlines(char * Pch);
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
if ((Pdnprev->dn_type) == dn_type)
{
(Pdnprev->dn_closed) = TRUE; // optional closing.
break;
}
}
if (Pdnprev != PDNNULL) continue; // matched closing.
// Otherwise check that the closing tag is the (required) closing tag for the
// (required) parent node (which must not have been closed yet):
if ((Pdn->dn_Pparent) == PDNNULL)
{
Error(ERREXIT, NOERRNO, FILELINE "Closing HTML tag "
"\"%s\" does not match an opening tag",
Filename, linenum, tagname);
}
assert(! (Pdn->dn_Pparent->dn_closed));
if ((Pdn->dn_Pparent->dn_type) != dn_type)
{
Error(ERREXIT, NOERRNO, FILELINE "Parent HTML tag "
"\"%s\" found on line %d requires a closing tag, "
"but \"%s\" does not match it; check for out-of-"
"order HTML tags", Filename, linenum,
TAG(Pdn->dn_Pparent->dn_type),
Pdn->dn_Pparent->dn_linenum, tagname);
}
// Go uplevel in the tree to the parent node:
Pdn = Pdn->dn_Pparent;
(Pdn->dn_closed) = TRUE;
continue;
} // closing tag.
// NEW HTML TAG: ADD SIBLING OR CHILD NODE TO TREE:
//
// Save appropriate information about the tag and move beyond its closing point
// in the input line.
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
//
// Note: For a correct line number, SETPREV() must account for any newlines in
// the text just emitted.
#define SETPREV(Text) g_prevlinenum = (Pdn->dn_linenum) + CountNewlines(Text)
#define SETPREVNONL g_prevlinenum = g_linenumlim // no newline.
// Check if under a lower-level <DL>, for continuing an indented paragraph:
#define UNDER_DL ((DLLevel > 1) \
&& ((Pdn->dn_Pparent) != PDNNULL) \
&& ((Pdn->dn_Pparent->dn_type) == DN_TYPE_DL))
// SWITCH ON DOCNODE TYPE:
if (Pdn->dn_noemit) // upstream node said to skip this one.
goto NextNode;
switch (Pdn->dn_type)
{
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
// 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:
PUTS(UNDER_DL ? "\n.IP\n" : "\n.PP\n");
SETPREVNONL;
break;
// LINE BREAK:
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
if ((Pdn->dn_Pnext) != PDNNULL)
EmitNroffBody(Pdn->dn_Pnext, DLLevel, InPRE, PageName);
} // EmitNroffBody()
// ****************************************************************************
// E X T R A C T H E A D E R
//
// Given a current docnode and pointers to values to return, walk the entire
// docnode tree once, recursively, in-order (parent then child then sibling) to
// extract nroff header information. Find the first comment line, insist it
// contain "@\(#)", and put this in *PFileRev. Also find exactly one
// DN_TYPE_TABLE, containing exactly one DN_TYPE_TR, containing one DN_TYPE_TD
// containing "align=\"left\"" and one DN_TYPE_TD containing
// "align=\"center\"", and extract from these the nroff .TH pagename,
// pagesection, and lcletter, and nroff ]W variable revision string,
// respectively. Error out if anything goes wrong.
//
// Note: Some of the returned strings are in separate malloc'd memory and
// others are not; treat them as read-only.
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
} // ExtractHeader()
// ****************************************************************************
// E X T R A C T T E X T
//
// Given a non-null docnode, return the non-null dn_text field from its first
// child (directly, not a copy). Error out if anything goes wrong.
FUNCTION char * ExtractText(
Pdn_t Pdn) // parent node.
{
assert(Pdn != PDNNULL);
#define ERR_NULLTEXT "Node for HTML tag \"%s\", found at line %d, lacks a " \
"child \"text\" node containing a non-null text string " \
"as required"
// TBD: This does not report a case of a text string containing only
// whitespace, but some callers do that themselves:
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
FUNCTION Pdn_t AppDocNode(
Pdn_t Pdn, // current docnode tree node.
int Linenum) // in input file.
{
// No current tree, insert first node:
if (g_Pdnhead == PDNNULL)
return(g_Pdnhead = NewDocNode(PDNNULL, Linenum));
// Insert new node as child, with parent set to current node:
if (NEST(Pdn->dn_type) && (! (Pdn->dn_closed)))
return((Pdn->dn_Pchild) = NewDocNode(Pdn, Linenum));
// Insert new node as sibling with same parent:
(Pdn->dn_Pnext) = NewDocNode(Pdn->dn_Pparent, Linenum);
(Pdn->dn_Pnext->dn_Pprev) = Pdn;
return(Pdn->dn_Pnext);
} // AppDocNode()
// ****************************************************************************
// N E W D O C N O D E
//
// Malloc() a new docnode and initialize its fields except dn_type, with error
// checking. Set its parent to the given value.
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()
// ****************************************************************************
// S A V E D O C N O D E
//
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);
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
} // Error()
#ifdef DEBUG
// ****************************************************************************
// D U M P T R E E
//
// Dump to stdout a representation of the docnode tree under g_Pdnhead.
// Recursively traverse the tree in-order (parent then child then sibling).
FUNCTION void DumpTree(
Pdn_t Pdn, // first node of current sibling list.
int Depth, // current depth.
bool_t Separator) // print a separator line after a long dump.
{
int indent; // for counting to Depth.
// Check if enabled:
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
{
(void) printf("%lx ", (unsigned long) Pdn);
for (indent = 0; indent <= Depth; ++indent) PUTC('.');
(void) printf(" %-5s %3d %c %lx %lx \"%s\"\n",
((Pdn -> dn_type) == DN_TYPE_TEXT) ?
"text" : TAG(Pdn -> dn_type),
Pdn -> dn_linenum,
(Pdn->dn_closed) ? 'c' : 'o',
Pdn -> dn_Pparent,
Pdn -> dn_Pprev,
Pdn -> dn_text);
if ((Pdn -> dn_Pchild) != PDNNULL)
DumpTree(Pdn -> dn_Pchild, Depth + 1, Separator);
Pdn = Pdn -> dn_Pnext;
}
// Print separator line:
( run in 0.323 second using v1.01-cache-2.11-cpan-4d50c553e7e )