Alien-Judy
view release on metacpan or search on metacpan
lib/Alien/Judy.pm view on Meta::CPAN
};
# The provided functions inc_dirs() and lib_dirs() are currently
# identical. Initially, they weren't.
*lib_dirs = \&inc_dirs;
# TODO: add literate documentation
sub inc_dirs {
# Find files from ., $sitearch and @INC.
my @dirs =
grep { defined() && length() }
@Config::Config{qw(sitearchexp sitearch)},
@INC,
Cwd::getcwd();
# But first try to find them in $_/Alien/Judy/
unshift @dirs,
map { File::Spec->catdir( $_, 'Alien', 'Judy' ) }
@dirs;
# Return the unique-ified list
src/judy-1.0.5/COPYING view on Meta::CPAN
When a "work that uses the Library" uses material from a header file
that is part of the Library, the object code for the work may be a
derivative work of the Library even though the source code is not.
Whether this is true is especially significant if the work can be
linked without the Library, or if the work is itself a library. The
threshold for this to be true is not precisely defined by law.
If such an object file uses only numerical parameters, data
structure layouts and accessors, and small macros and small inline
functions (ten lines or less in length), then the use of the object
file is unrestricted, regardless of whether it is legally a derivative
work. (Executables containing this object code plus portions of the
Library will still fall under Section 6.)
Otherwise, if the work is a derivative of the Library, you may
distribute the object code for the work under the terms of Section 6.
Any executables containing that work also fall under Section 6,
whether or not they are linked directly with the Library itself.
6. As an exception to the Sections above, you may also combine or
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
ifelse([$4], , :, [$4])
else
ifelse([$5], , :, [$5])
fi
])# AC_LIBTOOL_LINKER_OPTION
# AC_LIBTOOL_SYS_MAX_CMD_LEN
# --------------------------
AC_DEFUN([AC_LIBTOOL_SYS_MAX_CMD_LEN],
[# find the maximum length of command line arguments
AC_MSG_CHECKING([the maximum length of command line arguments])
AC_CACHE_VAL([lt_cv_sys_max_cmd_len], [dnl
i=0
teststring="ABCD"
case $build_os in
msdosdjgpp*)
# On DJGPP, this test can blow up pretty badly due to problems in libc
# (any single argument exceeding 2000 bytes causes a buffer overrun
# during glob expansion). Even if it were fixed, the result of this
# check would be larger than it should be.
lt_cv_sys_max_cmd_len=12288; # 12K is about right
;;
gnu*)
# Under GNU Hurd, this test is not required because there is
# no limit to the length of command line arguments.
# Libtool will interpret -1 as no limit whatsoever
lt_cv_sys_max_cmd_len=-1;
;;
cygwin* | mingw*)
# On Win9x/ME, this test blows up -- it succeeds, but takes
# about 5 minutes as the teststring grows exponentially.
# Worse, since 9x/ME are not pre-emptively multitasking,
# you end up with a "frozen" computer, even though with patience
# the test eventually succeeds (with a max line length of 256k).
# Instead, let's just punt: use the minimum linelength reported by
# all of the supported platforms: 8192 (on NT/2K/XP).
lt_cv_sys_max_cmd_len=8192;
;;
amigaos*)
# On AmigaOS with pdksh, this test takes hours, literally.
# So we just punt and use a minimum line length of 8192.
lt_cv_sys_max_cmd_len=8192;
;;
netbsd* | freebsd* | openbsd* | darwin* | dragonfly*)
# This has been around since 386BSD, at least. Likely further.
if test -x /sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/sbin/sysctl -n kern.argmax`
elif test -x /usr/sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/usr/sbin/sysctl -n kern.argmax`
else
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
sysv5* | sco5v6* | sysv4.2uw2*)
kargmax=`grep ARG_MAX /etc/conf/cf.d/stune 2>/dev/null`
if test -n "$kargmax"; then
lt_cv_sys_max_cmd_len=`echo $kargmax | sed 's/.*[[ ]]//'`
else
lt_cv_sys_max_cmd_len=32768
fi
;;
*)
# If test is not a shell built-in, we'll probably end up computing a
# maximum length that is only half of the actual maximum length, but
# we can't tell.
SHELL=${SHELL-${CONFIG_SHELL-/bin/sh}}
while (test "X"`$SHELL [$]0 --fallback-echo "X$teststring" 2>/dev/null` \
= "XX$teststring") >/dev/null 2>&1 &&
new_result=`expr "X$teststring" : ".*" 2>&1` &&
lt_cv_sys_max_cmd_len=$new_result &&
test $i != 17 # 1/2 MB should be enough
do
i=`expr $i + 1`
teststring=$teststring$teststring
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_[]_LT_AC_TAGVAR(lt_prog_compiler_pic, $1)
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_[]_LT_AC_TAGVAR(lt_cv_prog_compiler_c_o, $1)
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
} >&5
rm -f core *.core core.conftest.* &&
rm -f -r conftest* confdefs* conf$$* $ac_clean_files &&
exit $exit_status
' 0
for ac_signal in 1 2 13 15; do
trap 'ac_signal='$ac_signal'; { (exit 1); exit 1; }' $ac_signal
done
ac_signal=0
# confdefs.h avoids OS command line length limits that DEFS can exceed.
rm -f -r conftest* confdefs.h
# Predefined preprocessor variables.
cat >>confdefs.h <<_ACEOF
@%:@define PACKAGE_NAME "$PACKAGE_NAME"
_ACEOF
cat >>confdefs.h <<_ACEOF
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
ac_ext=c
ac_cpp='$CPP $CPPFLAGS'
ac_compile='$CC -c $CFLAGS $CPPFLAGS conftest.$ac_ext >&5'
ac_link='$CC -o conftest$ac_exeext $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS >&5'
ac_compiler_gnu=$ac_cv_c_compiler_gnu
# Autoconf 2.13's AC_OBJEXT and AC_EXEEXT macros only works for C compilers!
# find the maximum length of command line arguments
{ echo "$as_me:$LINENO: checking the maximum length of command line arguments" >&5
echo $ECHO_N "checking the maximum length of command line arguments... $ECHO_C" >&6; }
if test "${lt_cv_sys_max_cmd_len+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
i=0
teststring="ABCD"
case $build_os in
msdosdjgpp*)
# On DJGPP, this test can blow up pretty badly due to problems in libc
# (any single argument exceeding 2000 bytes causes a buffer overrun
# during glob expansion). Even if it were fixed, the result of this
# check would be larger than it should be.
lt_cv_sys_max_cmd_len=12288; # 12K is about right
;;
gnu*)
# Under GNU Hurd, this test is not required because there is
# no limit to the length of command line arguments.
# Libtool will interpret -1 as no limit whatsoever
lt_cv_sys_max_cmd_len=-1;
;;
cygwin* | mingw*)
# On Win9x/ME, this test blows up -- it succeeds, but takes
# about 5 minutes as the teststring grows exponentially.
# Worse, since 9x/ME are not pre-emptively multitasking,
# you end up with a "frozen" computer, even though with patience
# the test eventually succeeds (with a max line length of 256k).
# Instead, let's just punt: use the minimum linelength reported by
# all of the supported platforms: 8192 (on NT/2K/XP).
lt_cv_sys_max_cmd_len=8192;
;;
amigaos*)
# On AmigaOS with pdksh, this test takes hours, literally.
# So we just punt and use a minimum line length of 8192.
lt_cv_sys_max_cmd_len=8192;
;;
netbsd* | freebsd* | openbsd* | darwin* | dragonfly*)
# This has been around since 386BSD, at least. Likely further.
if test -x /sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/sbin/sysctl -n kern.argmax`
elif test -x /usr/sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/usr/sbin/sysctl -n kern.argmax`
else
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
sysv5* | sco5v6* | sysv4.2uw2*)
kargmax=`grep ARG_MAX /etc/conf/cf.d/stune 2>/dev/null`
if test -n "$kargmax"; then
lt_cv_sys_max_cmd_len=`echo $kargmax | sed 's/.*[ ]//'`
else
lt_cv_sys_max_cmd_len=32768
fi
;;
*)
# If test is not a shell built-in, we'll probably end up computing a
# maximum length that is only half of the actual maximum length, but
# we can't tell.
SHELL=${SHELL-${CONFIG_SHELL-/bin/sh}}
while (test "X"`$SHELL $0 --fallback-echo "X$teststring" 2>/dev/null` \
= "XX$teststring") >/dev/null 2>&1 &&
new_result=`expr "X$teststring" : ".*" 2>&1` &&
lt_cv_sys_max_cmd_len=$new_result &&
test $i != 17 # 1/2 MB should be enough
do
i=`expr $i + 1`
teststring=$teststring$teststring
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_CXX
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_CXX
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_F77
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_F77
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_GCJ
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_GCJ
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_RC
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_RC
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
} >&5
rm -f core *.core core.conftest.* &&
rm -f -r conftest* confdefs* conf$$* $ac_clean_files &&
exit $exit_status
' 0
for ac_signal in 1 2 13 15; do
trap 'ac_signal='$ac_signal'; { (exit 1); exit 1; }' $ac_signal
done
ac_signal=0
# confdefs.h avoids OS command line length limits that DEFS can exceed.
rm -f -r conftest* confdefs.h
# Predefined preprocessor variables.
cat >>confdefs.h <<_ACEOF
@%:@define PACKAGE_NAME "$PACKAGE_NAME"
_ACEOF
cat >>confdefs.h <<_ACEOF
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
ac_ext=c
ac_cpp='$CPP $CPPFLAGS'
ac_compile='$CC -c $CFLAGS $CPPFLAGS conftest.$ac_ext >&5'
ac_link='$CC -o conftest$ac_exeext $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS >&5'
ac_compiler_gnu=$ac_cv_c_compiler_gnu
# Autoconf 2.13's AC_OBJEXT and AC_EXEEXT macros only works for C compilers!
# find the maximum length of command line arguments
{ echo "$as_me:$LINENO: checking the maximum length of command line arguments" >&5
echo $ECHO_N "checking the maximum length of command line arguments... $ECHO_C" >&6; }
if test "${lt_cv_sys_max_cmd_len+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
i=0
teststring="ABCD"
case $build_os in
msdosdjgpp*)
# On DJGPP, this test can blow up pretty badly due to problems in libc
# (any single argument exceeding 2000 bytes causes a buffer overrun
# during glob expansion). Even if it were fixed, the result of this
# check would be larger than it should be.
lt_cv_sys_max_cmd_len=12288; # 12K is about right
;;
gnu*)
# Under GNU Hurd, this test is not required because there is
# no limit to the length of command line arguments.
# Libtool will interpret -1 as no limit whatsoever
lt_cv_sys_max_cmd_len=-1;
;;
cygwin* | mingw*)
# On Win9x/ME, this test blows up -- it succeeds, but takes
# about 5 minutes as the teststring grows exponentially.
# Worse, since 9x/ME are not pre-emptively multitasking,
# you end up with a "frozen" computer, even though with patience
# the test eventually succeeds (with a max line length of 256k).
# Instead, let's just punt: use the minimum linelength reported by
# all of the supported platforms: 8192 (on NT/2K/XP).
lt_cv_sys_max_cmd_len=8192;
;;
amigaos*)
# On AmigaOS with pdksh, this test takes hours, literally.
# So we just punt and use a minimum line length of 8192.
lt_cv_sys_max_cmd_len=8192;
;;
netbsd* | freebsd* | openbsd* | darwin* | dragonfly*)
# This has been around since 386BSD, at least. Likely further.
if test -x /sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/sbin/sysctl -n kern.argmax`
elif test -x /usr/sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/usr/sbin/sysctl -n kern.argmax`
else
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
sysv5* | sco5v6* | sysv4.2uw2*)
kargmax=`grep ARG_MAX /etc/conf/cf.d/stune 2>/dev/null`
if test -n "$kargmax"; then
lt_cv_sys_max_cmd_len=`echo $kargmax | sed 's/.*[ ]//'`
else
lt_cv_sys_max_cmd_len=32768
fi
;;
*)
# If test is not a shell built-in, we'll probably end up computing a
# maximum length that is only half of the actual maximum length, but
# we can't tell.
SHELL=${SHELL-${CONFIG_SHELL-/bin/sh}}
while (test "X"`$SHELL $0 --fallback-echo "X$teststring" 2>/dev/null` \
= "XX$teststring") >/dev/null 2>&1 &&
new_result=`expr "X$teststring" : ".*" 2>&1` &&
lt_cv_sys_max_cmd_len=$new_result &&
test $i != 17 # 1/2 MB should be enough
do
i=`expr $i + 1`
teststring=$teststring$teststring
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_CXX
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_CXX
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_F77
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_F77
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_GCJ
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_GCJ
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_RC
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_RC
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
$rm conftest*
LDFLAGS="$save_LDFLAGS"
])
if test x"[$]$2" = xyes; then
ifelse([$4], , :, [$4])
else
ifelse([$5], , :, [$5])
fi
])
m4trace:/usr/share/aclocal/libtool.m4:695: -1- AC_DEFUN([AC_LIBTOOL_SYS_MAX_CMD_LEN], [# find the maximum length of command line arguments
AC_MSG_CHECKING([the maximum length of command line arguments])
AC_CACHE_VAL([lt_cv_sys_max_cmd_len], [dnl
i=0
teststring="ABCD"
case $build_os in
msdosdjgpp*)
# On DJGPP, this test can blow up pretty badly due to problems in libc
# (any single argument exceeding 2000 bytes causes a buffer overrun
# during glob expansion). Even if it were fixed, the result of this
# check would be larger than it should be.
lt_cv_sys_max_cmd_len=12288; # 12K is about right
;;
gnu*)
# Under GNU Hurd, this test is not required because there is
# no limit to the length of command line arguments.
# Libtool will interpret -1 as no limit whatsoever
lt_cv_sys_max_cmd_len=-1;
;;
cygwin* | mingw*)
# On Win9x/ME, this test blows up -- it succeeds, but takes
# about 5 minutes as the teststring grows exponentially.
# Worse, since 9x/ME are not pre-emptively multitasking,
# you end up with a "frozen" computer, even though with patience
# the test eventually succeeds (with a max line length of 256k).
# Instead, let's just punt: use the minimum linelength reported by
# all of the supported platforms: 8192 (on NT/2K/XP).
lt_cv_sys_max_cmd_len=8192;
;;
amigaos*)
# On AmigaOS with pdksh, this test takes hours, literally.
# So we just punt and use a minimum line length of 8192.
lt_cv_sys_max_cmd_len=8192;
;;
netbsd* | freebsd* | openbsd* | darwin* | dragonfly*)
# This has been around since 386BSD, at least. Likely further.
if test -x /sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/sbin/sysctl -n kern.argmax`
elif test -x /usr/sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/usr/sbin/sysctl -n kern.argmax`
else
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
sysv5* | sco5v6* | sysv4.2uw2*)
kargmax=`grep ARG_MAX /etc/conf/cf.d/stune 2>/dev/null`
if test -n "$kargmax"; then
lt_cv_sys_max_cmd_len=`echo $kargmax | sed 's/.*[[ ]]//'`
else
lt_cv_sys_max_cmd_len=32768
fi
;;
*)
# If test is not a shell built-in, we'll probably end up computing a
# maximum length that is only half of the actual maximum length, but
# we can't tell.
SHELL=${SHELL-${CONFIG_SHELL-/bin/sh}}
while (test "X"`$SHELL [$]0 --fallback-echo "X$teststring" 2>/dev/null` \
= "XX$teststring") >/dev/null 2>&1 &&
new_result=`expr "X$teststring" : ".*" 2>&1` &&
lt_cv_sys_max_cmd_len=$new_result &&
test $i != 17 # 1/2 MB should be enough
do
i=`expr $i + 1`
teststring=$teststring$teststring
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_[]_LT_AC_TAGVAR(lt_prog_compiler_pic, $1)
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_[]_LT_AC_TAGVAR(lt_cv_prog_compiler_c_o, $1)
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/autom4te.cache/traces.1 view on Meta::CPAN
m4trace:configure.ac:232: -1- AC_SUBST([LIB@&t@OBJS], ["$LIB@&t@OBJS lstat.$ac_objext"])
m4trace:configure.ac:232: -1- AC_SUBST_TRACE([LIB@&t@OBJS])
m4trace:configure.ac:232: -1- m4_pattern_allow([^LIB@&t@OBJS$])
m4trace:configure.ac:232: -1- AC_LIBSOURCE([stat.c])
m4trace:configure.ac:232: -1- AC_SUBST([LIB@&t@OBJS], ["$LIB@&t@OBJS stat.$ac_objext"])
m4trace:configure.ac:232: -1- AC_SUBST_TRACE([LIB@&t@OBJS])
m4trace:configure.ac:232: -1- m4_pattern_allow([^LIB@&t@OBJS$])
m4trace:configure.ac:232: -1- AC_DEFINE_TRACE_LITERAL([HAVE_STAT_EMPTY_STRING_BUG])
m4trace:configure.ac:232: -1- m4_pattern_allow([^HAVE_STAT_EMPTY_STRING_BUG$])
m4trace:configure.ac:232: -1- AH_OUTPUT([HAVE_STAT_EMPTY_STRING_BUG], [/* Define to 1 if `stat\' has the bug that it succeeds when given the
zero-length file name argument. */
#undef HAVE_STAT_EMPTY_STRING_BUG])
m4trace:configure.ac:233: -1- AH_OUTPUT([HAVE_VPRINTF], [/* Define to 1 if you have the `vprintf\' function. */
#undef HAVE_VPRINTF])
m4trace:configure.ac:233: -1- AC_DEFINE_TRACE_LITERAL([HAVE_DOPRNT])
m4trace:configure.ac:233: -1- m4_pattern_allow([^HAVE_DOPRNT$])
m4trace:configure.ac:233: -1- AH_OUTPUT([HAVE_DOPRNT], [/* Define to 1 if you don\'t have `vprintf\' but do have `_doprnt.\' */
#undef HAVE_DOPRNT])
m4trace:configure.ac:234: -1- AH_OUTPUT([HAVE_GETPAGESIZE], [/* Define to 1 if you have the `getpagesize\' function. */
#undef HAVE_GETPAGESIZE])
m4trace:configure.ac:234: -1- AH_OUTPUT([HAVE_GETTIMEOFDAY], [/* Define to 1 if you have the `gettimeofday\' function. */
src/judy-1.0.5/config.h.in view on Meta::CPAN
/* Define to 1 if you have the `munmap' function. */
#undef HAVE_MUNMAP
/* Define to 1 if you have the `pow' function. */
#undef HAVE_POW
/* Define to 1 if the system has the type `ptrdiff_t'. */
#undef HAVE_PTRDIFF_T
/* Define to 1 if `stat' has the bug that it succeeds when given the
zero-length file name argument. */
#undef HAVE_STAT_EMPTY_STRING_BUG
/* Define to 1 if stdbool.h conforms to C99. */
#undef HAVE_STDBOOL_H
/* Define to 1 if you have the <stddef.h> header file. */
#undef HAVE_STDDEF_H
/* Define to 1 if you have the <stdint.h> header file. */
#undef HAVE_STDINT_H
src/judy-1.0.5/configure view on Meta::CPAN
} >&5
rm -f core *.core core.conftest.* &&
rm -f -r conftest* confdefs* conf$$* $ac_clean_files &&
exit $exit_status
' 0
for ac_signal in 1 2 13 15; do
trap 'ac_signal='$ac_signal'; { (exit 1); exit 1; }' $ac_signal
done
ac_signal=0
# confdefs.h avoids OS command line length limits that DEFS can exceed.
rm -f -r conftest* confdefs.h
# Predefined preprocessor variables.
cat >>confdefs.h <<_ACEOF
#define PACKAGE_NAME "$PACKAGE_NAME"
_ACEOF
cat >>confdefs.h <<_ACEOF
src/judy-1.0.5/configure view on Meta::CPAN
ac_ext=c
ac_cpp='$CPP $CPPFLAGS'
ac_compile='$CC -c $CFLAGS $CPPFLAGS conftest.$ac_ext >&5'
ac_link='$CC -o conftest$ac_exeext $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS >&5'
ac_compiler_gnu=$ac_cv_c_compiler_gnu
# Autoconf 2.13's AC_OBJEXT and AC_EXEEXT macros only works for C compilers!
# find the maximum length of command line arguments
{ echo "$as_me:$LINENO: checking the maximum length of command line arguments" >&5
echo $ECHO_N "checking the maximum length of command line arguments... $ECHO_C" >&6; }
if test "${lt_cv_sys_max_cmd_len+set}" = set; then
echo $ECHO_N "(cached) $ECHO_C" >&6
else
i=0
teststring="ABCD"
case $build_os in
msdosdjgpp*)
# On DJGPP, this test can blow up pretty badly due to problems in libc
# (any single argument exceeding 2000 bytes causes a buffer overrun
# during glob expansion). Even if it were fixed, the result of this
# check would be larger than it should be.
lt_cv_sys_max_cmd_len=12288; # 12K is about right
;;
gnu*)
# Under GNU Hurd, this test is not required because there is
# no limit to the length of command line arguments.
# Libtool will interpret -1 as no limit whatsoever
lt_cv_sys_max_cmd_len=-1;
;;
cygwin* | mingw*)
# On Win9x/ME, this test blows up -- it succeeds, but takes
# about 5 minutes as the teststring grows exponentially.
# Worse, since 9x/ME are not pre-emptively multitasking,
# you end up with a "frozen" computer, even though with patience
# the test eventually succeeds (with a max line length of 256k).
# Instead, let's just punt: use the minimum linelength reported by
# all of the supported platforms: 8192 (on NT/2K/XP).
lt_cv_sys_max_cmd_len=8192;
;;
amigaos*)
# On AmigaOS with pdksh, this test takes hours, literally.
# So we just punt and use a minimum line length of 8192.
lt_cv_sys_max_cmd_len=8192;
;;
netbsd* | freebsd* | openbsd* | darwin* | dragonfly*)
# This has been around since 386BSD, at least. Likely further.
if test -x /sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/sbin/sysctl -n kern.argmax`
elif test -x /usr/sbin/sysctl; then
lt_cv_sys_max_cmd_len=`/usr/sbin/sysctl -n kern.argmax`
else
src/judy-1.0.5/configure view on Meta::CPAN
sysv5* | sco5v6* | sysv4.2uw2*)
kargmax=`grep ARG_MAX /etc/conf/cf.d/stune 2>/dev/null`
if test -n "$kargmax"; then
lt_cv_sys_max_cmd_len=`echo $kargmax | sed 's/.*[ ]//'`
else
lt_cv_sys_max_cmd_len=32768
fi
;;
*)
# If test is not a shell built-in, we'll probably end up computing a
# maximum length that is only half of the actual maximum length, but
# we can't tell.
SHELL=${SHELL-${CONFIG_SHELL-/bin/sh}}
while (test "X"`$SHELL $0 --fallback-echo "X$teststring" 2>/dev/null` \
= "XX$teststring") >/dev/null 2>&1 &&
new_result=`expr "X$teststring" : ".*" 2>&1` &&
lt_cv_sys_max_cmd_len=$new_result &&
test $i != 17 # 1/2 MB should be enough
do
i=`expr $i + 1`
teststring=$teststring$teststring
src/judy-1.0.5/configure view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/configure view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_CXX
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_CXX
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/configure view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_F77
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_F77
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/configure view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_GCJ
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_GCJ
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/configure view on Meta::CPAN
# Shared library suffix (normally ".so").
shrext_cmds='$shrext_cmds'
# Executable file suffix (normally "").
exeext="$exeext"
# Additional compiler flags for building library objects.
pic_flag=$lt_lt_prog_compiler_pic_RC
pic_mode=$pic_mode
# What is the maximum length of a command?
max_cmd_len=$lt_cv_sys_max_cmd_len
# Does compiler simultaneously support -c and -o options?
compiler_c_o=$lt_lt_cv_prog_compiler_c_o_RC
# Must we lock files when doing compilation?
need_locks=$lt_need_locks
# Do we need the lib prefix for modules?
need_lib_prefix=$need_lib_prefix
src/judy-1.0.5/doc/ext/JudyHS_3.htm view on Meta::CPAN
<A href="#JHSI" >JHSI</A>( PValue, PJHSArray, Index, Length); // <A href="JudyHS_funcs_3.htm#JudyHSIns">JudyHSIns()</A>
<A href="#JHSD" >JHSD</A>( Rc_int, PJHSArray, Index, Length); // <A href="JudyHS_funcs_3.htm#JudyHSDel">JudyHSDel()</A>
<A href="#JHSG" >JHSG</A>( PValue, PJHSArray, Index, Length); // <A href="JudyHS_funcs_3.htm#JudyHSGet">JudyHSGet()</A>
<A href="#JHSFA">JHSFA</A>(Rc_word, PJHSArray); // <A href="JudyHS_funcs_3.htm#JudyHSFreeArray">JudyHSFreeArray()</A>
</PRE></B>
<!----------------->
<DT><B>DESCRIPTION</B></DT>
<DD>
A JudyHS array is the equivalent of an array of word-sized
value/pointers. An <B>Index</B> is a pointer to an array-of-bytes of
specified length: <B>Length</B>. Rather than using a null terminated
string, this difference from <A href="JudySL_3.htm">JudySL(3)</A>
allows strings to contain all bits (specifically the null character).
This new addition (May 2004) to Judy arrays is a hybird using the best
capabilities of hashing and Judy methods. <B>JudyHS</B> does not have a
poor performance case where knowledge of the hash algorithm can be used
to degrade the performance.
<P>
Since JudyHS is based on a hash method, <B>Indexes</B> are not stored in
any particular order. Therefore the JudyHSFirst(), JudyHSNext(),
JudyHSPrev() and JudyHSLast() neighbor search functions are not
src/judy-1.0.5/doc/ext/JudyHS_3.htm view on Meta::CPAN
<P>
Because the macro forms of the API have a simpler error handling
interface than the equivalent
<A href="JudyHS_funcs_3.htm">functions</A>,
they are the preferred way to use JudyHS.
<P>
<DT>
<A name="JHSI"><B>JHSI(PValue, PJHSArray, Index, Length)</B></A> // <A href="JudyHS_funcs_3.htm#JudyHSIns">JudyHSIns()</A></DT>
<DD>
Given a pointer to a JudyHS array (<B>PJHSArray</B>), insert an
<B>Index</B> string of length: <B>Length</B> and a <B>Value</B> into the
JudyHS array: <B>PJHSArray</B>. If the <B>Index</B> is successfully
inserted, the <B>Value</B> is initialized to 0. If the <B>Index</B> was
already present, the <B>Value</B> is not modified.
<P>
Return <B>PValue</B> pointing to <B>Value</B>. Your program should use
this pointer to read or modify the <B>Value</B>, for example:
<PRE>
Value = *PValue;
*PValue = 1234;
</PRE>
src/judy-1.0.5/doc/ext/JudyHS_3.htm view on Meta::CPAN
duplicate lines and their line number from <I>stdin</I>.
<P><PRE>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <Judy.h>
// Compiled:
// cc -O PrintDupLines.c -lJudy -o PrintDupLines
#define MAXLINE 1000000 /* max fgets length of line */
uint8_t Index[MAXLINE]; // string to check
int // Usage: PrintDupLines < file
main()
{
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // Judy array element pointer.
Word_t Bytes; // size of JudyHS array.
Word_t LineNumb = 0; // current line number
Word_t Dups = 0; // number of duplicate lines
src/judy-1.0.5/doc/ext/JudyHS_funcs_3.htm view on Meta::CPAN
<TD width="10%" align="center"> </TD>
<TD width="40%" align="right">JudyHS_funcs(3)</TD>
</TR></TABLE>
<P>
<DL>
<!----------------->
<DT><B>NAME</B></DT>
<DD>
JudyHS functions -
C library for creating and accessing a dynamic array,
using an array-of-bytes of a length: <B>Length</B> as an <B>Index</B> and a word
as a <B>Value</B>.
<!----------------->
<P>
<DT><B>SYNOPSIS</B></DT>
<DD>
<B><PRE>
PPvoid_t <A href="#JudyHSIns" >JudyHSIns</A>(PPvoid_t PPJHS, void *Index, Word_t Length, PJError_t PJError);
int <A href="#JudyHSDel" >JudyHSDel</A>(PPvoid_t PPJHS, void *Index, Word_t Length, PJError_t PJError);
PPvoid_t <A href="#JudyHSGet" >JudyHSGet</A>(Pcvoid_t PJHS, void *Index, Word_t Length, PJError_t PJError);
Word_t <A href="#JudyHSFreeArray">JudyHSFreeArray</A>(PPvoid_t PPJHS, PJError_t PJError);
src/judy-1.0.5/doc/ext/JudySL_3.htm view on Meta::CPAN
a null-terminated string as an <B>Index</B> (associative array)
<!----------------->
<P>
<DT><B>SYNOPSIS</B></DT>
<DD>
<B><PRE>
cc [flags] <I>sourcefiles</I> -lJudy
#include <Judy.h>
#define MAXLINELEN 1000000 // define maximum string length
Word_t * PValue; // JudySL array element
uint8_t Index[MAXLINELEN]; // string
int Rc_int; // return value
Word_t Rc_word; // full word return value
Pvoid_t PJSLArray = (Pvoid_t) NULL; // initialize JudySL array
<A href="#JSLI" >JSLI</A>( PValue, PJSLArray, Index); // <A href="JudySL_funcs_3.htm#JudySLIns">JudySLIns()</A>
<A href="#JSLD" >JSLD</A>( Rc_int, PJSLArray, Index); // <A href="JudySL_funcs_3.htm#JudySLDel">JudySLDel()</A>
src/judy-1.0.5/doc/ext/JudySL_3.htm view on Meta::CPAN
<A href="#JSLP" >JSLP</A>( PValue, PJSLArray, Index); // <A href="JudySL_funcs_3.htm#JudySLPrev">JudySLPrev()</A>
</PRE></B>
<!----------------->
<P>
<DT><B>DESCRIPTION</B></DT>
<DD>
A JudySL array is the equivalent of a sorted set of strings, each associated
with a <B>Value</B> (word).
A <B>Value</B> is addressed by an <B>Index</B> (key), which is a null-terminated
character string of any length.
Memory to support the array is allocated as index/value pairs are inserted,
and released as index/value pairs are deleted.
This is a form of associative array, where array elements are also sorted
lexicographically (case-sensitive) by indexes.
This could be thought of as
<P><PRE>
void * JudySLArray["Toto, I don't think we're in Kansas any more"];
</PRE>
<P>
A JudySL array is allocated with a <B>NULL</B> pointer
src/judy-1.0.5/doc/ext/JudySL_3.htm view on Meta::CPAN
<B>Index</B> string.
<B>JSLN()</B> is typically used to <I>continue</I> a sorted-order scan of
the valid indexes in a JudySL array, or to locate a "neighbor" of a given
index.
<P>
<DT><A name="JSLL"><B>JSLL(PValue, PJSLArray, Index)</B></A> // <A href="JudySL_funcs_3.htm#JudySLLast">JudySLLast()</A></DT>
<DD>
Search (inclusive) for the last index present that is equal to or less
than the passed <B>Index</B> string.
(Start with a maximum-valued string to look up the last index in the array,
such as a max-length string of 0xff bytes.)
<B>JSLL()</B> is typically used to <I>begin</I> a reverse-sorted-order
scan of the valid indexes in a JudySL array.
<P>
<DT><A name="JSLP"><B>JSLP(PValue, PJSLArray, Index)</B></A> // <A href="JudySL_funcs_3.htm#JudySLPrev">JudySLPrev()</A></DT>
<DD>
Search (exclusive) for the previous index present that is less than the
passed <B>Index</B> string.
<B>JSLP()</B> is typically used to <I>continue</I> a reverse-sorted-order
scan of the valid indexes in a JudySL array, or to locate a "neighbor" of
a given index.
src/judy-1.0.5/doc/ext/JudySL_3.htm view on Meta::CPAN
<P>
<DT><A name="JSLERR"><B>ERRORS:</B> See: </A><A href="Judy_3.htm#ERRORS">Judy_3.htm#ERRORS</A></DT>
<DD>
<!----------------->
<P>
<DT><B>EXAMPLE</B> of a string sort routine</DT>
<P><PRE>
#include <stdio.h>
#include <Judy.h>
#define MAXLINE 1000000 // max string (line) length
uint8_t Index[MAXLINE]; // string to insert
int // Usage: JudySort < file_to_sort
main()
{
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // Judy array element.
Word_t Bytes; // size of JudySL array.
src/judy-1.0.5/doc/ext/Judy_3.htm view on Meta::CPAN
<A href="JudyL_3.htm">JudyL</A> - maps an <B>Index</B> (word) to a <B>Value</B> (word/pointer)
<A href="JudySL_3.htm">JudySL</A> - maps an <B>Index</B> (null terminated string) to a <B>Value</B>
<A href="JudyHS_3.htm">JudyHS</A> - maps an <B>Index</B> (array-of-bytes) of <B>Length</B> to a <B>Value</B>
</PRE>
<!----------------->
<P>
<DT><B>DESCRIPTION</B></DT>
<DD>
The Judy family of functions supports fully dynamic arrays. These
arrays may be indexed by a 32- or 64-bit word (depending on processor
word size), a null terminated string or an array-of-bytes plus length.
A dynamic array (sparsely populated) can also be thought of as a
<I>mapping function</I> or <I>associative memory</I>.
<P>
A <B>Word_t</B> is a <I>typedef unsigned long int </I> in <B>Judy.h</B>
and must be the same size as <I>sizeof(void *)</I> I.E. a pointer.
<P>
<A href="Judy1_3.htm">Judy1</A> functions: <B>Index</B> is a
<B>Word_t</B> and <B>Value</B> is just a <B>bit</B> or simply
a flag that <B>Index</B> is present or missing from the array.
This can be thought of as a huge bitmap.
<P>
<A href="JudyL_3.htm">JudyL</A> functions: <B>Index</B> is a
<B>Word_t</B> and <B>Value</B> is a <B>Word_t</B>. This makes
<B>JudyL</B> a pure word-to-word/pointer mapper. <B>JudySL</B> and
<B>JudyHL</B> are based on this property of <B>JudyL</B>.
<P>
<A href="JudySL_3.htm">JudySL</A> functions: <B>Index</B> is a
null-terminated string and <B>Value</B> is a <B>Word_t</B>.
<P>
<A href="JudyHS_3.htm">JudyHS</A> functions: <B>Index</B> is an
array-of-bytes of length: <B>Length</B>. <B>Value</B> is a
<B>Word_t</B>. This new addition (May 2004) to Judy is a hybird using
the best features of hashing and Judy methods. The author believes
<B>JudyHS</B> is a good replacement for a hashing method when resizing
the hash table is done during population growth. A correctly tuned hash
method with a <B>static</B> hash table size and population is unbeatable
for speed. However, <B>JudyHS</B> will perform better than a hashing
method with smaller and larger populations than the optimum hash table
size. <B>JudyHS</B> does not have a degenerate performance case where
knowledge of the hash algorithm can be exploited. (I.E. JudyHS does
not use a linked list to handle hash collisions, it uses a tree of
src/judy-1.0.5/doc/int/10minutes.htm view on Meta::CPAN
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>
src/judy-1.0.5/src/JudyCommon/JudyCreateBranch.c view on Meta::CPAN
}
// Check if Uncompressed subexpanse
if (BitMap == cJU_FULLBITMAPB)
{
// Copy subexpanse to the Uncompressed branch intact
JU_COPYMEM(PDstJP, PjpA, cJU_BITSPERSUBEXPB);
// Bump to next subexpanse
PDstJP += cJU_BITSPERSUBEXPB;
// Set length of subexpanse
jj = cJU_BITSPERSUBEXPB;
}
else
{
for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++)
{
// Copy JP or NULLJP depending on bit
if (BitMap & 1) { *PDstJP = *PjpA++; }
else { *PDstJP = JPNull; }
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
//
// A lookahead means noting the last branch traversed which contained a
// non-null JP lower than the one specified by a digit in *PIndex-1, and
// returning to that point for SM3Findlimit. This seems like a good idea, and
// 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.)
//
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
//=======================================================================
#include <string.h> // for memcmp(), memcpy()
#include <Judy.h> // for JudyL* routines/macros
/*
This routine is a very fast "string" version of an ADT that stores
(JudyHSIns()), retrieves (JudyHSGet()), deletes (JudyHSDel()) and
frees the entire ADT (JudyHSFreeArray()) strings. It uses the "Judy
arrays" JudyL() API as the main workhorse. The length of the string
is included in the calling parameters so that strings with embedded
\0s can be used. The string lengths can be from 0 bytes to whatever
malloc() can handle (~2GB).
Compile:
cc -O JudyHS.c -c needs to link with -lJudy (libJudy.a)
Note: in gcc version 3.3.1, -O2 generates faster code than -O
Note: in gcc version 3.3.2, -O3 generates faster code than -O2
NOTES:
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
mpy, mod, variable shifts and call returns.
3) JudyHS is very scalable from 1 string to billions (with enough RAM).
The memory usage is also scales with population. I have attempted to
combine the best characteristics of JudyL arrays with Hashing methods
and well designed modern processors (such as the 1.3Ghz Intel
Centrino this is being written on).
HOW JudyHS WORKS: ( 4[8] means 4 bytes in 32 bit machine and 8 in 64)
A) A JudyL array is used to separate strings of equal lengths into
their own structures (a different hash table is used for each length
of string). The additional time overhead is very near zero because
of the CPU cache. The space efficiency is improved because the
length need not be stored with the string (ls_t). The "JLHash" ADT
in the test program "StringCompare" is verification of both these
assumptions.
B) A 32 bit hash value is produced from the string. Many thanks to
the Internet and the author (Bob Jenkins) for coming up with a very
good and fast universal string hash. Next the 32 bit hash number is
used as an Index to another JudyL array. Notice that one (1) JudyL
array is used as a hash table per each string length. If there are
no hash collisions (normally) then the string is copied to a
structure (ls_t) along with room for storing a Value. A flag is
added to the pointer to note it is pointing to a ls_t structure.
Since the lengths of the strings are the same, there is no need to
stored length of string in the ls_t structure. This saves about a
word per string of memory.
C) When there is a hashing collision (very rare), a JudyL array is
used to decode the next 4[8] bytes of the string. That is, the next
4[8] bytes of the string are used as the Index. This process is
repeated until the remaining string is unique. The remaining string
(if any) is stored in a (now smaller) ls_t structure. If the
remaining string is less or equal to 4[8] bytes, then the ls_t
structure is not needed and the Value area in the JudyL array is
used. A compile option -DDONOTUSEHASH is available to test this
structure without using hashing (only the JudyL tree is used). This
is equivalent to having all strings hashed to the same bucket. The
speed is still better than all other tree based ADTs I have tested.
An added benefit of this is a very fast "hash collision" resolving.
It could foil hackers that exploit the slow synonym (linked-list)
collision handling property used with most hashing algorithms. If
this is not a necessary property, then a simpler ADT "JLHash" that is
documented the the test program "StringCompare.c" may be used with a
little loss of memory efficiency (because it includes the string
length with the ls_t structure). JudyHS was written to be the
fastest, very scalable, memory efficient, general purpose string ADT
possible. (However, I would like to eat those words someday). (dlb)
*/
#ifdef EXAMPLE_CODE
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <Judy.h>
//#include "JudyHS.h" // for Judy.h without JudyHS*()
// By Doug Baskins Apr 2004 - for JudyHS man page
#define MAXLINE 1000000 /* max length of line */
char Index[MAXLINE]; // string to check
int // Usage: CheckDupLines < file
main()
{
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // ^ Judy array element.
Word_t Bytes; // size of JudyHS array.
Word_t LineNumb = 0; // current line number
Word_t Dups = 0; // number of duplicate lines
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
// Note: Use JLAP_INVALID, which is non-zero, to mark pointers to a ls_t
// This makes it compatable with previous versions of JudyL()
#define IS_PLS(PLS) (((Word_t) (PLS)) & JLAP_INVALID)
#define CLEAR_PLS(PLS) (((Word_t) (PLS)) & (~JLAP_INVALID))
#define SET_PLS(PLS) (((Word_t) (PLS)) | JLAP_INVALID)
#define WORDSIZE (sizeof(Word_t))
// this is the struct used for "leaf" strings. Note that
// the Value is followed by a "variable" length ls_String array.
//
typedef struct L_EAFSTRING
{
Word_t ls_Value; // Value area (cannot change size)
uint8_t ls_String[WORDSIZE]; // to fill out to a Word_t size
} ls_t , *Pls_t;
#define LS_STRUCTOVD (sizeof(ls_t) - WORDSIZE)
// Calculate size of ls_t including the string of length of LEN.
//
#define LS_WORDLEN(LEN) (((LEN) + LS_STRUCTOVD + WORDSIZE - 1) / WORDSIZE)
// Copy from 0..4[8] bytes from string to a Word_t
// NOTE: the copy in in little-endian order to take advantage of improved
// memory efficiency of JudyLIns() with smaller numbers
//
#define COPYSTRING4toWORD(WORD,STR,LEN) \
{ \
WORD = 0; \
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
} \
/* c_ &= gHmask; see above */ \
(HVALUE) = c_; \
}
// Find String of Len in JudyHS structure, return pointer to associated Value
PPvoid_t
JudyHSGet(Pcvoid_t PArray, // pointer (^) to structure
void * Str, // pointer to string
Word_t Len // length of string
)
{
uint8_t *String = (uint8_t *)Str;
PPvoid_t PPValue; // pointer to Value
Word_t Index; // 4[8] bytes of String
JLG(PPValue, PArray, Len); // find hash table for strings of Len
if (PPValue == (PPvoid_t) NULL)
return ((PPvoid_t) NULL); // no strings of this Len
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
}
}
// Get remaining 1..4[8] bytes left in string
COPYSTRINGtoWORD(Index, String, Len);
JLG(PPValue, *PPValue, Index); // decode last 1-4[8] bytes
return (PPValue);
}
// Add string to a tree of JudyL arrays (all lengths must be same)
static PPvoid_t
insStrJudyLTree(uint8_t * String, // string to add to tree of JudyL arrays
Word_t Len, // length of string
PPvoid_t PPValue, // pointer to root pointer
PJError_t PJError // for returning error info
)
{
Word_t Index; // next 4[8] bytes of String
while (Len > WORDSIZE) // add to JudyL tree
{
// CASE 1, pointer is to a NULL, make a new ls_t leaf
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
*PPValue = (Pvoid_t)SET_PLS(Pls); // mark pointer
return ((PPvoid_t) (&Pls->ls_Value)); // return ^ to Value
} // no exit here
// CASE 2: is a ls_t, free (and shorten), then decode into JudyL tree
if (IS_PLS(*PPValue)) // pointer to a ls_t? (leaf)
{
Pls_t Pls; // ^ to ls_t
uint8_t *String0; // ^ to string in ls_t
Word_t Index0; // 4[8] bytes in string
Word_t FreeLen; // length of ls_t
PPvoid_t PPsplit;
FreeLen = LS_WORDLEN(Len); // length of ls_t
Pls = (Pls_t) CLEAR_PLS(*PPValue); // demangle ^ to ls_t
String0 = Pls->ls_String;
if (memcmp(String, String0, Len) == 0) // check if match?
{
return ((PPvoid_t) (&Pls->ls_Value)); // yes, duplicate
}
*PPValue = NULL; // clear ^ to ls_t and make JudyL
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
return (PPValue);
}
// Insert string to JudyHS structure, return pointer to associated Value
PPvoid_t
JudyHSIns(PPvoid_t PPArray, // ^ to JudyHashArray name
void * Str, // pointer to string
Word_t Len, // length of string
PJError_t PJError // optional, for returning error info
)
{
uint8_t * String = (uint8_t *)Str;
PPvoid_t PPValue;
// string can only be NULL if Len is 0.
if ((String == (uint8_t *) NULL) && (Len != 0UL))
{
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
#endif // DONOTUSEHASH
PPValue = insStrJudyLTree(String, Len, PPValue, PJError); // add string
return (PPValue); // ^ to Value
}
// Delete string from tree of JudyL arrays (all Lens must be same)
static int
delStrJudyLTree(uint8_t * String, // delete from tree of JudyL arrays
Word_t Len, // length of string
PPvoid_t PPValue, // ^ to hash bucket
PJError_t PJError // for returning error info
)
{
PPvoid_t PPValueN; // next pointer
Word_t Index;
int Ret; // -1=failed, 1=success, 2=quit del
if (IS_PLS(*PPValue)) // is pointer to ls_t?
{
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
Ret = JudyLDel(PPValue, Index, PJError);
}
return (Ret);
}
// Delete string from JHS structure
int
JudyHSDel(PPvoid_t PPArray, // ^ to JudyHashArray struct
void * Str, // pointer to string
Word_t Len, // length of string
PJError_t PJError // optional, for returning error info
)
{
uint8_t * String = (uint8_t *)Str;
PPvoid_t PPBucket, PPHtble;
int Ret; // return bool from Delete routine
#ifndef DONOTUSEHASH
uint32_t HValue = 0; // hash value of input string
#endif // DONOTUSEHASH
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
#endif // USEHASH
// delete from JudyL tree
//
Ret = delStrJudyLTree(String, Len, PPBucket, PJError);
if (Ret != 1)
{
JU_SET_ERRNO(PJError, 0);
return(-1);
}
// handle case of missing JudyL array from hash table and length table
if (*PPBucket == (Pvoid_t)NULL) // if JudyL tree gone
{
#ifndef DONOTUSEHASH
if (Len > WORDSIZE)
{
// delete entry in Hash table
Ret = JudyLDel(PPHtble, (Word_t)HValue, PJError);
if (Ret != 1)
{
JU_SET_ERRNO(PJError, 0);
return(-1);
}
}
#endif // USEHASH
if (*PPHtble == (PPvoid_t) NULL) // if Hash table gone
{
// delete entry from the String length table
Ret = JudyLDel(PPArray, Len, PJError);
if (Ret != 1)
{
JU_SET_ERRNO(PJError, 0);
return(-1);
}
}
}
return (1); // success
}
static Word_t
delJudyLTree(PPvoid_t PPValue, // ^ to JudyL root pointer
Word_t Len, // length of string
PJError_t PJError) // for returning error info
{
Word_t bytes_freed = 0; // bytes freed at point
Word_t bytes_total = 0; // accumulated bytes freed
PPvoid_t PPValueN;
// Pointer is to another tree of JudyL arrays or ls_t struct
if (Len > WORDSIZE) // more depth to tree
{
Word_t NEntry;
// Pointer is to a ls_t struct
if (IS_PLS(*PPValue))
{
Pls_t Pls;
Word_t freewords;
freewords = LS_WORDLEN(Len); // calculate length
Pls = (Pls_t)CLEAR_PLS(*PPValue); // demangle pointer
// *PPValue = (Pvoid_t)NULL; // clean pointer
JudyFree((Pvoid_t)Pls, freewords); // free the ls_t
return(freewords * WORDSIZE);
}
// else
// Walk all the entrys in the JudyL array
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
)
{
Word_t Len; // start at beginning
Word_t bytes_freed; // bytes freed at this level.
Word_t bytes_total; // bytes total at all levels.
PPvoid_t PPHtble;
if (PPArray == NULL)
return (0); // no pointer, return none
// Walk the string length table for subsidary hash structs
// NOTE: This is necessary to determine the depth of the tree
bytes_freed = 0;
bytes_total = 0;
Len = 0; // walk to length table
for (PPHtble = JudyLFirst(*PPArray, &Len, PJError);
(PPHtble != (PPvoid_t) NULL) && (PPHtble != PPJERR);
PPHtble = JudyLNext(*PPArray, &Len, PJError))
{
PPvoid_t PPValueH;
#ifndef DONOTUSEHASH
if (Len > WORDSIZE)
{
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
(PPValueH != (PPvoid_t) NULL) && (PPValueH != PPJERR);
PPValueH = JudyLNext(*PPHtble, &HEntry, PJError))
{
bytes_freed = delJudyLTree(PPValueH, Len, PJError);
if (bytes_freed == JERR) return(JERR);
bytes_total += bytes_freed;
}
if (PPValueH == PPJERR) return(JERR);
// free the Hash table for this length of string
bytes_freed = JudyLFreeArray(PPHtble, PJError);
if (bytes_freed == JERR) return(JERR);
bytes_total += bytes_freed;
}
else
#endif // DONOTUSEHASH
{
PPValueH = PPHtble; // simulate hash table
bytes_freed = delJudyLTree(PPValueH, Len, PJError);
if (bytes_freed == JERR) return(JERR);
bytes_total += bytes_freed;
}
}
if (PPHtble == PPJERR) return(JERR);
// free the length table
bytes_freed = JudyLFreeArray(PPArray, PJError);
if (bytes_freed == JERR) return(JERR);
bytes_total += bytes_freed;
return(bytes_total); // return bytes freed
}
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
#define WORDS(BYTES) (((BYTES) + WORDSIZE - 1) / WORDSIZE) // round up.
// To mark a pointer is to a "short cut leaf", set least bit
#define IS_PSCL(PSCL) (((Word_t) (PSCL)) & JLAP_INVALID)
#define CLEAR_PSCL(PSCL) ((Pscl_t)(((Word_t) (PSCL)) & (~JLAP_INVALID)))
#define SET_PSCL(PSCL) (((Word_t) (PSCL)) | JLAP_INVALID)
// MISCELLANEOUS GLOBALS:
// Get the Index (string) length in bytes, including the trailing \0, which
// is an integral part of the string:
// A string is "in the last word" if a previously-set byte count is at or below
// the system word size, or in some cases if the last byte in the (null-padded)
// word is null (assume big-endian, including in a register on a little-endian
// machine):
#define LASTWORD_BY_VALUE(WORD) (! ((WORD) & 0xffL))
#ifdef JU_64BIT
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
#define STRLEN(S1) (strlen((void *)(S1)) + 1)
// Index and value area for a shortcut leaf, depending on how it matches the
// undecoded remainder of the Index, given a Pscl_t that includes type bits
// that must be cleared:
//
// PSCLINDEX() and PSCLVALUE() are also useful when Pscl contains uncleared
// TYPE bits.
//
// Note: SCLCMP() cannot take advantage of knowing the Index length because
// the scl_Index length is not pre-known when these macros are used.
#define PSCLINDEX(PSCL) ((CLEAR_PSCL(PSCL))->scl_Index)
#define PSCLVALUE(PSCL) ((CLEAR_PSCL(PSCL))->scl_Pvalue)
#define SCLCMP(INDEX,PSCL) STRCMP(INDEX, PSCLINDEX(PSCL))
#define PPSCLVALUE_EQ(INDEX,PSCL) \
((SCLCMP(INDEX, PSCL) == 0) ? &PSCLVALUE(PSCL) : (PPvoid_t)NULL)
#define PPSCLVALUE_LT(INDEX,PSCL) \
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
// 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
// a count of 1, all of whose descendant JudyL arrays also have a count of 1,
// and delete from that point downwards. This solution would traverse the
// array tree downward looking to see if the given Index is in the tree, then
// if so, delete layers downwards starting below the last one that contains
src/judy-1.0.5/test/Centrino_1.3Mhz_Plots/Hash_CO.plot view on Meta::CPAN
# COLHEAD 5 Get Time (uS)
# COLHEAD 6 Hash Chain Length
# COLHEAD 7 Average RAM/String
# Linux localhost 2.6.3-4mdkenterprise #1 SMP Tue Mar 2 07:00:53 CET 2004 i686
# 32 Bit CPU
# Processor speed compiled at 1299 Mhz
# Hash record struct: sizeof(hrec_t) = 16
# Allocate Hash table = 1048576 elements
# 11218731 (75.0%) non-Word_t aligned string buffers
# Ram used for input data = 372621771 bytes
# Average string length = 15.9 bytes
# 3200000 bytes malloc() for 'cached' strings for Get measurement
# Access Time = 0.103 uS average per string (mostly from Cache)
# HashStr() Time = 0.270 uS average per string (mostly from Cache)
# Access Time = 0.287 uS average per string (mostly from RAM)
# HashStr() Time = 0.477 uS average per string (mostly from RAM)
# Pass 0
# TotInserts DeltaGets DupStrs InsTime GetTime HChainLen Ram/String
# 1 1 0 5775.911 1.182 1.000000 4194356.0
# 2 2 0 3.406 0.417 1.000000 2097190.0
# 3 3 0 1.251 0.374 1.000000 1398136.0
src/judy-1.0.5/test/Centrino_1.3Mhz_Plots/JLHash_CO.plot view on Meta::CPAN
# COLHEAD 4 Insert Time (uS)
# COLHEAD 5 Get Time (uS)
# COLHEAD 6 Hash Chain Length
# COLHEAD 7 Average RAM/String
# Linux localhost 2.6.3-4mdkenterprise #1 SMP Tue Mar 2 07:00:53 CET 2004 i686
# 32 Bit CPU
# Processor speed compiled at 1299 Mhz
# JLHash table virtual size = 4294967296
# 9999673 (75.0%) non-Word_t aligned string buffers
# Ram used for input data = 333834600 bytes
# Average string length = 16.0 bytes
# 3400000 bytes malloc() for 'cached' strings for Get measurement
# Access Time = 0.102 uS average per string (mostly from Cache)
# HashStr() Time = 0.274 uS average per string (mostly from Cache)
# Access Time = 0.285 uS average per string (mostly from RAM)
# HashStr() Time = 0.474 uS average per string (mostly from RAM)
# Pass 0
# TotInserts DeltaGets DupStrs InsTime GetTime HChainLen Ram/String
# 1 1 0 38.004 1.742 1.000000 108.0
# 2 2 0 8.817 0.905 1.000000 74.0
# 3 3 0 1.388 0.705 1.000000 60.0
src/judy-1.0.5/test/Centrino_1.3Mhz_Plots/JudyHS_CO.plot view on Meta::CPAN
# COLHEAD 3 Duplicate strings
# COLHEAD 4 Insert Time (uS)
# COLHEAD 5 Get Time (uS)
# COLHEAD 6 Hash Chain Length
# COLHEAD 7 Average RAM/String
# Linux localhost 2.6.3-4mdkenterprise #1 SMP Tue Mar 2 07:00:53 CET 2004 i686
# 32 Bit CPU
# Processor speed compiled at 1299 Mhz
# 11218731 (75.0%) non-Word_t aligned string buffers
# Ram used for input data = 372621771 bytes
# Average string length = 15.9 bytes
# 3200000 bytes malloc() for 'cached' strings for Get measurement
# Access Time = 0.112 uS average per string (mostly from Cache)
# HashStr() Time = 0.271 uS average per string (mostly from Cache)
# Access Time = 0.295 uS average per string (mostly from RAM)
# HashStr() Time = 0.476 uS average per string (mostly from RAM)
# Pass 0
# TotInserts DeltaGets DupStrs InsTime GetTime HChainLen Ram/String
# 1 1 0 30.232 2.608 0.000000 52.0
# 2 2 0 8.020 0.314 0.000000 44.0
# 3 3 0 1.616 0.268 0.000000 42.7
src/judy-1.0.5/test/Centrino_1.3Mhz_Plots/JudySL_CO.plot view on Meta::CPAN
# COLHEAD 3 Duplicate strings
# COLHEAD 4 Insert Time (uS)
# COLHEAD 5 Get Time (uS)
# COLHEAD 6 Hash Chain Length
# COLHEAD 7 Average RAM/String
# Linux localhost 2.6.3-4mdkenterprise #1 SMP Tue Mar 2 07:00:53 CET 2004 i686
# 32 Bit CPU
# Processor speed compiled at 1299 Mhz
# 12587648 (75.0%) non-Word_t aligned string buffers
# Ram used for input data = 418243455 bytes
# Average string length = 15.9 bytes
# 3200000 bytes malloc() for 'cached' strings for Get measurement
# Access Time = 0.101 uS average per string (mostly from Cache)
# HashStr() Time = 0.270 uS average per string (mostly from Cache)
# Access Time = 0.296 uS average per string (mostly from RAM)
# HashStr() Time = 0.482 uS average per string (mostly from RAM)
# Pass 0
# TotInserts DeltaGets DupStrs InsTime GetTime HChainLen Ram/String
# 1 1 0 24.309 5.002 0.000000 16.0
# 2 2 0 21.507 0.328 0.000000 26.0
# 3 3 0 1.485 0.184 0.000000 25.3
src/judy-1.0.5/test/CheckDupLines.c view on Meta::CPAN
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <Judy.h>
//#include "JudyHS.h" // for Judy.h without JudyHS*()
// By Doug Baskins Apr 2004 - for JudyHS man page
#define MAXLINE 1000000 /* max length of line */
char Index[MAXLINE]; // string to check
int // Usage: CheckDupLines < file
main()
{
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // Judy array element.
Word_t Bytes; // size of JudyHS array.
Word_t LineNumb = 0; // current line number
Word_t Dups = 0; // number of duplicate lines
src/judy-1.0.5/test/JudyString.c view on Meta::CPAN
Pvoid_t PJHArray = (PWord_t)NULL; // Judy array.
// By Doug Baskins Apr 2004 - for JudyHS man page -- but too long
int // Usage: JudyString file_to_store
main(int argc, char *argv[])
{
Pvoid_t PJHArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // Judy array element.
Word_t Bytes; // size of JudySL array.
Word_t Len; // length of string
FILE *fid = NULL; // stream id
int Chr; // next char
long Lines; // number of lines input file
Word_t Dups; // Count duplicate lines
if (argc < 2)
{
printf("Must supply input file in arg\n");
exit(2);
}
src/judy-1.0.5/test/SLcompare.c view on Meta::CPAN
//=======================================================================
//
// From memory map POINTER store next '\n' terminated string to BUFFER
// Delete spaces, tabs, returns and resulting blank lines.
// POINTER must be check to be within memory mapped file range
//
// NOTE: This code will core-dump if a corrupt text file because
// POINTER is not checked to exceed end of file.
#define MAXLINE 10000 // max length line
#define GETLINE(BUFFER,POINTER) \
{ \
char _chr; \
int _count = 0; \
for (;;) /* forever */ \
{ \
switch (_chr = *POINTER++) \
{ \
case ' ': /* eat spaces */ \
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
static Word_t nStrg = INFSTRGS; // infinity -- measure all strings
static Word_t TValues = 100000; // max measure points for RETRIVE tests
static int pFlag = 0; // pre-fault hash table pages into RAM
static int rFlag = 0; // do not randomize input file
static int aFlag = 0; // word align string buffers
static int DFlag = 0; // do the delete measurement
static int CFlag = 0; // build sequential Get buffers
static Word_t aCount = 0; // Count of missaligned string buffers
// define the maximum length of a string allowed
#define MAXSTRLEN (100000)
static int MLength = MAXSTRLEN;
static Word_t HTblsz; // 1M default hash table size
static int fileidx; // argv[fileidx] == file string
// for saving input string data
typedef struct STRING_
{
int dt_strlen;
uint8_t *dt_string;
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
}
return (PdtS_);
}
//=======================================================================
// H A S H M E T H O D S T R U C T U R E S
//=======================================================================
// These structures are used in Hash() and JLHash() ADTs
// for storing length of string
// Hash chain structure (varible length depending on string)
// static part of the length
#define HSTRUCTOVD (sizeof(hrec_t) - sizeof(int))
typedef struct HASHREC_ *Phrec_t;
typedef struct HASHREC_
{
Phrec_t hr_Next; // collision chain link pointer
Word_t hr_Value; // Data associated with string
int hr_Strlen; // length of string 2 billion max
uint8_t hr_String[sizeof(int)]; // string is allocated with struct
} hrec_t;
// hash head structure to keep hash array information
typedef struct HASHINFO_
{
Pvoid_t hi_Htbl; // Hash table
Word_t hi_tblsize; // Hash table size (Words)
Word_t hi_TotalWords; // Hash array total words
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
hval = HASHSTR(String, Strlen, PHash->hi_tblsize);
JLG(PPhrec, PHash->hi_Htbl, hval); // use JudyL to get &pointer
if (PPhrec == NULL)
return (NULL); // no table entry
// search for matching string
for (Phrec = *PPhrec; Phrec != NULL; Phrec = Phrec->hr_Next)
{
gChainln++; // Hash chain length
if (Phrec->hr_Strlen == Strlen) // length match?
{
if (memcmp(Phrec->hr_String, String, Strlen) == 0)
return (&(Phrec->hr_Value)); // match! pointer to Value
}
}
return (NULL);
}
// Return pointer to struct hrec_t associated with string
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
}
// get hash value, if mod(%) is slow (in some CPUs), make it a power of 2
hval = HASHSTR(String, Strlen, PHash->hi_tblsize);
// get pointer to hash table entry
JLI(PPhrec, PHash->hi_Htbl, hval); // JLI will exit if out of memory
// search for matching string
for (Phrec = *PPhrec; Phrec != NULL; Phrec = Phrec->hr_Next)
{
if (Phrec->hr_Strlen == Strlen) // string length match?
{
if (memcmp(Phrec->hr_String, String, Strlen) == 0)
{
return (&(Phrec->hr_Value)); // match! pointer to Value
}
}
}
// String match not found, so do an insert
Len = BYTES2WORDS(Strlen + HSTRUCTOVD);
Phrec = (Phrec_t) JudyMalloc(Len); // get memory for storing string
if (Phrec == NULL)
MALLOCERROR;
PHash->hi_TotalWords += Len; // keep track of total mallocs
Phrec->hr_Strlen = Strlen; // set string length
memcpy(Phrec->hr_String, String, Strlen);
Phrec->hr_Next = *PPhrec; // pointer to synonym
*PPhrec = Phrec; // place new struct in front of list
(PHash->hi_Pop1)++; // add one to population
Phrec->hr_Value = (Word_t)0; // zero the associated Value
return (&(Phrec->hr_Value)); // return pointer to Value
}
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
// get pointer hash table entry
JLG(PPhrec, PHash->hi_Htbl, hval);
if (PPhrec == NULL)
return (0); // hash entry not found
PPhrec1 = PPhrec; // save head hash entry ^
// search for matching string
for (Phrec = *PPhrec; Phrec != NULL; Phrec = Phrec->hr_Next)
{
if (Phrec->hr_Strlen == Strlen) // string length match?
{
if (memcmp(Phrec->hr_String, String, Strlen) == 0) // string match?
{
int Rc; // not used
Word_t Len;
*PPhrec = Phrec->hr_Next; // put next in previous
Len = BYTES2WORDS(Strlen + HSTRUCTOVD);
JudyFree(Phrec, Len);
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
// walk the synonym linked list
while (Phrec != NULL)
{
Word_t Len;
Phrec_t Phrecfree = Phrec;
// number of words to free -- struct hrec_t
Len = BYTES2WORDS(Phrec->hr_Strlen + HSTRUCTOVD);
// sum total length of mallocs in words
DeletedWords += Len;
(PHash->hi_Pop1)--; // Decrement population
// get pointer to next synonym on list
Phrec = Phrec->hr_Next;
// free the struct hrec_t
JudyFree(Phrecfree, Len);
}
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
// get hash value, if mod(%) is slow (in some CPUs), make it a power of 2
hval = HASHSTR(String, Strlen, PHash->hi_tblsize);
// type Hash table pointer
Htbl = (Phrec_t *) PHash->hi_Htbl;
// search for matching string
for (Phrec = Htbl[hval]; Phrec != NULL; Phrec = Phrec->hr_Next)
{
gChainln++; // Hash chain length
if (Phrec->hr_Strlen == Strlen) // length match?
{
if (memcmp(Phrec->hr_String, String, Strlen) == 0)
return (&(Phrec->hr_Value)); // match! pointer to Value
}
}
return (NULL);
}
// Return pointer to struct hrec_t associated with string
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
}
// get hash value, if mod(%) is slow (in some CPUs), make it a power of 2
hval = HASHSTR(String, Strlen, TblSize);
// type Hash table pointer
Htbl = (Phrec_t *) PHash->hi_Htbl;
// search for matching string in hash table entry
for (Phrec = Htbl[hval]; Phrec != NULL; Phrec = Phrec->hr_Next)
{
if (Phrec->hr_Strlen == Strlen) // string length match?
{
if (memcmp(Phrec->hr_String, String, Strlen) == 0) // string match?
{
return (&(Phrec->hr_Value)); // match! pointer to Value
}
}
}
// string not found, so do an insert
Len = BYTES2WORDS(Strlen + HSTRUCTOVD);
Phrec = (Phrec_t) JudyMalloc(Len);
if (Phrec == NULL)
MALLOCERROR;
PHash->hi_TotalWords += Len; // keep track of total mallocs
Phrec->hr_Strlen = Strlen; // set string length
memcpy(Phrec->hr_String, String, Strlen); // copy it
// place new allocation first in chain
Phrec->hr_Next = Htbl[hval];
Htbl[hval] = Phrec;
(PHash->hi_Pop1)++; // add one to population
Phrec->hr_Value = (Word_t)0; // zero the associated Value
return (&(Phrec->hr_Value)); // return pointer to Value
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
// type Hash table pointer
Htbl = (Phrec_t *) PHash->hi_Htbl;
// get pointer hash table entry
PPhrec = &Htbl[hval];
// search for matching string
for (Phrec = *PPhrec; Phrec != NULL; Phrec = Phrec->hr_Next)
{
if (Phrec->hr_Strlen == Strlen) // length match?
{
if (memcmp(Phrec->hr_String, String, Strlen) == 0)
{
Word_t Len;
// put next hrec_t in previous hrec_t
*PPhrec = Phrec->hr_Next;
Len = BYTES2WORDS(Strlen + HSTRUCTOVD);
JudyFree(Phrec, Len);
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
//Word_t TotalJudyMalloc;
#define GETSTRING(PCurStr, Strlen)
int
main(int argc, char *argv[])
{
TIMER_vars(tm); // declare timer variables
FILE *fid; // to read file.
int Chr; // char read from fgetc
Pdt_t Pdt, Pdts; // array of lengths and pointers to str
uint8_t *PCurStr; // Current string pointer
Word_t LineCnt; // line counter
int Strlen; // = strlen();
Word_t StrTot; // Total len of strings
Word_t StrNumb; // current line number
Word_t ReadLin; // strings to read
double Mult; // multiplier between groups
Word_t Groups; // number of measurement groups
Word_t grp; // current group
Pvoid_t JudySL = NULL; // JudySL root pointer
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
break;
case 'T': // Maximum retrieve tests for timing
TValues = strtoul(optarg, NULL, 0);
break;
case 'P': // measurement points per decade
PtsPdec = strtoul(optarg, NULL, 0);
break;
case 'M': // maximum length of input string
MLength = atoi(optarg);
break;
case 'p': // pre-initialize Hash table
pFlag = 1;
break;
case 'r': // do not randomize input
if (CFlag)
{
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
// OPEN INPUT FILE:
if ((fid = fopen(argv[fileidx], "r")) == NULL)
FILERROR;
for (StrTot = Strlen = LineCnt = 0; (Chr = fgetc(fid)) != EOF;)
{
if (Chr == '\n')
{
if (Strlen) // eat zero length lines
{
if (Strlen > MLength)
Strlen = MLength;
LineCnt++; // increase string count
Strlen++; // add a \0 for JudySL
if (aFlag) // for word alignment
StrTot += ROUNDUPWORD(Strlen);
else
StrTot += Strlen; // memory needed to store strings
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
//=======================================================================
if ((fid = fopen(argv[fileidx], "r")) == NULL)
FILERROR;
for (Strlen = LineCnt = 0; LineCnt < nStrg;)
{
Chr = fgetc(fid);
if (Chr == '\n')
{
if (Strlen) // eat zero length lines
{
if (Strlen > MLength)
Strlen = MLength;
Pdt[LineCnt].dt_string = PCurStr - Strlen;
Pdt[LineCnt].dt_strlen = Strlen;
LineCnt++;
Strlen = 0;
*PCurStr++ = '\0'; // for JudySL
if (aFlag) // for word alignment
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
}
fclose(fid);
fid = NULL;
assert(nStrg == LineCnt);
printf("# %lu (%.1f%%) non-Word_t aligned string buffers\n",
aCount, (double)aCount / (double)LineCnt * 100.0);
printf("# Ram used for input data = %lu bytes\n", StringMemory);
printf("# Average string length = %.1f bytes\n",
(double)(StrTot - LineCnt) / LineCnt);
// Allocate memory for Cached assess to 'Get' (largest delta). This flag
// will put the 'randomized' 'Get' order strings in a sequential buffer.
// Modern processors will 'read ahead' with an access to RAM is sequential
// -- thus saving the 'Get' having to bring the string into cache.
if (CFlag)
{
PdtS_ = (Pdt_t) malloc(TValues * sizeof(dt_t));
if (PdtS_ == NULL)
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
STARTTm(tm); // start timer
for (LineCnt = 0; LineCnt < nStrg; LineCnt++)
{
GETSTRING(PCurStr, Strlen);
Strlen = Pdt[LineCnt].dt_strlen;
PCurStr = Pdt[LineCnt].dt_string;
if (strlen(PCurStr) != Strlen) // bring string into Cache
{
// necessary to prevent cc from optimizing out
printf(" !! OOps Bug, wrong string length\n");
exit(1);
}
}
ENDTm(DeltaUSec, tm); // end timer
printf
("# Access Time = %6.3f uS average per string (mostly from Cache)\n",
DeltaUSec / nStrg);
//=======================================================================
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
STARTTm(tm); // start timer
for (LineCnt = 0; LineCnt < nStrg; LineCnt++)
{
GETSTRING(PCurStr, Strlen);
Strlen = Pdt[LineCnt].dt_strlen;
PCurStr = Pdt[LineCnt].dt_string;
if (strlen(PCurStr) != Strlen) // bring string into Cache
{
// necessary to prevent cc from optimizing out
printf(" !! OOps Bug, wrong string length\n");
exit(1);
}
}
ENDTm(DeltaUSec, tm); // end timer
printf
("# Access Time = %6.3f uS average per string (mostly from RAM)\n",
DeltaUSec / nStrg);
//=======================================================================
src/judy-1.0.5/test/StringCompare.c view on Meta::CPAN
Pms[grp].ms_Bytes /= (double)gStored;
fflush(stdout);
//=======================================================================
// READ BACK LOOP
//=======================================================================
Pdts = Pdt; // Strings to 'Get'
gChainln = 0; // total chain lengths
if (rFlag == 0)
{
Randomize(Pdt, StrNumb); // Randomize ONLY those stored
if (CFlag)
{
// Allocate and make sequencial string buffer
Pdts = BuildSeqBuf(Pdt, ReadLin);
}
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
of which starts out cleared, and can be independently freed,
realloc'ed etc. The elements are guaranteed to be adjacently
allocated (this is not guaranteed to occur with multiple callocs or
mallocs), which may also improve cache locality in some
applications.
The "chunks" argument is optional (i.e., may be null, which is
probably the most typical usage). If it is null, the returned array
is itself dynamically allocated and should also be freed when it is
no longer needed. Otherwise, the chunks array must be of at least
n_elements in length. It is filled in with the pointers to the
chunks.
In either case, independent_calloc returns this pointer array, or
null if the allocation failed. If n_elements is zero and "chunks"
is null, it returns a chunk representing an array with zero elements
(which should be freed if not wanted).
Each element must be individually freed when it is no longer
needed. If you'd like to instead be able to free all at once, you
should instead use regular calloc and assign pointers into this
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
chunks with sizes indicated in the "sizes" array. It returns
an array of pointers to these elements, each of which can be
independently freed, realloc'ed etc. The elements are guaranteed to
be adjacently allocated (this is not guaranteed to occur with
multiple callocs or mallocs), which may also improve cache locality
in some applications.
The "chunks" argument is optional (i.e., may be null). If it is null
the returned array is itself dynamically allocated and should also
be freed when it is no longer needed. Otherwise, the chunks array
must be of at least n_elements in length. It is filled in with the
pointers to the chunks.
In either case, independent_comalloc returns this pointer array, or
null if the allocation failed. If n_elements is zero and chunks is
null, it returns a chunk representing an array with zero elements
(which should be freed if not wanted).
Each element must be individually freed when it is no longer
needed. If you'd like to instead be able to free all at once, you
should instead use a single regular malloc, and assign pointers at
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
mchunkptr p; /* corresponding chunk */
CHUNK_SIZE_T remainder_size; /* remaining bytes while splitting */
Void_t** marray; /* either "chunks" or malloced ptr array */
mchunkptr array_chunk; /* chunk for malloced ptr array */
unsigned int mprops; /* to disable mmap */
CHUNK_SIZE_T size;
size_t i;
ensure_initialization(av);
/* compute array length, if needed */
if (chunks != 0) {
if (n_elements == 0)
return chunks; /* nothing to do */
marray = chunks;
array_size = 0;
}
else {
/* if empty req, must still return chunk representing empty array */
if (n_elements == 0)
return (Void_t**) mALLOc(0);
src/judy-1.0.5/tool/README view on Meta::CPAN
# .sbcm file, optionally the basename part only (except for trailing "/"):
awk < "$dir/$file" '
(NF > 0) && ($0 !~ /^[ '"$tab"'#]/) {
if ($1 == "README") next;
if ($1 == ".sbcm" ) next;
if ("'"$optb"'" == "yes")
while ((at = index ($1, "/")) && (at < length ($1)))
$1 = substr ($1, at + 1);
print $1;
}' |
sort -u > $temp1
# COMPARE:
#
src/judy-1.0.5/tool/jhton.c view on Meta::CPAN
//
// - Exception: (char *) and (char[]) types, that is, strings, do not
// necessarily start with "P". A generic char pointer is named "Pch".
// Variables of type (char **) start with a single P.
//
// - Exception: the well known name "char ** argv".
//
// - Pointers to first elements of serial linked lists of structures have names
// ending in "Phead".
//
// - Line lengths are less than 80 columns. Message parameters to Error()
// begin on the same line for easy finding.
//
// - Error messages might exceed one line when emitted, but no effort is made
// to wrap them nicely.
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h> // for varargs.
#include <string.h> // for str*().
#include <errno.h>
( run in 1.042 second using v1.01-cache-2.11-cpan-65fba6d93b7 )