Alien-Judy
view release on metacpan or search on metacpan
TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
the exclusion of warranty; and each file should have at least the
"copyright" line and a pointer to where the full notice is found.
<one line to give the program's name and a brief idea of what it does.>
Copyright (C) 19yy <name of author>
src/judy-1.0.5/Makefile.in view on Meta::CPAN
CTAGS = ctags
DIST_SUBDIRS = $(SUBDIRS)
DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST)
distdir = $(PACKAGE)-$(VERSION)
top_distdir = $(distdir)
am__remove_distdir = \
{ test ! -d $(distdir) \
|| { find $(distdir) -type d ! -perm -200 -exec chmod u+w {} ';' \
&& rm -fr $(distdir); }; }
DIST_ARCHIVES = $(distdir).tar.gz
GZIP_ENV = --best
distuninstallcheck_listfiles = find . -type f -print
distcleancheck_listfiles = find . -type f -print
ACLOCAL = @ACLOCAL@
AMDEP_FALSE = @AMDEP_FALSE@
AMDEP_TRUE = @AMDEP_TRUE@
AMTAR = @AMTAR@
AR = @AR@
AUTOCONF = @AUTOCONF@
AUTOHEADER = @AUTOHEADER@
AUTOMAKE = @AUTOMAKE@
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
_LT_AC_TAGVAR(archive_cmds_need_lc, $1)=yes
# This is similar to how AIX traditionally builds its shared libraries.
_LT_AC_TAGVAR(archive_expsym_cmds, $1)="\$CC $shared_flag"' -o $output_objdir/$soname $libobjs $deplibs ${wl}-bnoentry $compiler_flags ${wl}-bE:$export_symbols${allow_undefined_flag}~$AR $AR_FLAGS $output_objdir/$libname$release.a $output_objdir/$so...
fi
fi
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
_LT_AC_TAGVAR(allow_undefined_flag, $1)=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
_LT_AC_TAGVAR(archive_cmds, $1)='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
_LT_AC_TAGVAR(ld_shlibs, $1)=no
fi
;;
chorus*)
case $cc_basename in
*)
src/judy-1.0.5/aclocal.m4 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
_LT_AC_TAGVAR(ld_shlibs, $1)=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
_LT_AC_TAGVAR(allow_undefined_flag, $1)=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
_LT_AC_TAGVAR(archive_cmds, $1)='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
_LT_AC_TAGVAR(ld_shlibs, $1)=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, $1) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, ) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
archive_cmds_need_lc_CXX=yes
# This is similar to how AIX traditionally builds its shared libraries.
archive_expsym_cmds_CXX="\$CC $shared_flag"' -o $output_objdir/$soname $libobjs $deplibs ${wl}-bnoentry $compiler_flags ${wl}-bE:$export_symbols${allow_undefined_flag}~$AR $AR_FLAGS $output_objdir/$libname$release.a $output_objdir/$soname'
fi
fi
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_CXX=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_CXX='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_CXX=no
fi
;;
chorus*)
case $cc_basename in
*)
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs_F77=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_F77=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_F77='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_F77=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, F77) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/output.0 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs_GCJ=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_GCJ=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_GCJ='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_GCJ=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, GCJ) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, ) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
archive_cmds_need_lc_CXX=yes
# This is similar to how AIX traditionally builds its shared libraries.
archive_expsym_cmds_CXX="\$CC $shared_flag"' -o $output_objdir/$soname $libobjs $deplibs ${wl}-bnoentry $compiler_flags ${wl}-bE:$export_symbols${allow_undefined_flag}~$AR $AR_FLAGS $output_objdir/$libname$release.a $output_objdir/$soname'
fi
fi
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_CXX=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_CXX='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_CXX=no
fi
;;
chorus*)
case $cc_basename in
*)
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs_F77=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_F77=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_F77='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_F77=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, F77) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/output.1 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs_GCJ=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_GCJ=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_GCJ='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_GCJ=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, GCJ) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
_LT_AC_TAGVAR(archive_cmds_need_lc, $1)=yes
# This is similar to how AIX traditionally builds its shared libraries.
_LT_AC_TAGVAR(archive_expsym_cmds, $1)="\$CC $shared_flag"' -o $output_objdir/$soname $libobjs $deplibs ${wl}-bnoentry $compiler_flags ${wl}-bE:$export_symbols${allow_undefined_flag}~$AR $AR_FLAGS $output_objdir/$libname$release.a $output_objdir/$so...
fi
fi
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
_LT_AC_TAGVAR(allow_undefined_flag, $1)=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
_LT_AC_TAGVAR(archive_cmds, $1)='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
_LT_AC_TAGVAR(ld_shlibs, $1)=no
fi
;;
chorus*)
case $cc_basename in
*)
src/judy-1.0.5/autom4te.cache/traces.0 view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
_LT_AC_TAGVAR(ld_shlibs, $1)=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
_LT_AC_TAGVAR(allow_undefined_flag, $1)=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
_LT_AC_TAGVAR(archive_cmds, $1)='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
_LT_AC_TAGVAR(ld_shlibs, $1)=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, $1) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/configure view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, ) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/configure view on Meta::CPAN
archive_cmds_need_lc_CXX=yes
# This is similar to how AIX traditionally builds its shared libraries.
archive_expsym_cmds_CXX="\$CC $shared_flag"' -o $output_objdir/$soname $libobjs $deplibs ${wl}-bnoentry $compiler_flags ${wl}-bE:$export_symbols${allow_undefined_flag}~$AR $AR_FLAGS $output_objdir/$libname$release.a $output_objdir/$soname'
fi
fi
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_CXX=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_CXX='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_CXX=no
fi
;;
chorus*)
case $cc_basename in
*)
src/judy-1.0.5/configure view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs_F77=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_F77=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_F77='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_F77=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, F77) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/configure view on Meta::CPAN
# to version 4, is to share data among multiple programs linked
# with the same dynamic library. Since this doesn't match the
# behavior of shared libraries on other platforms, we can't use
# them.
ld_shlibs_GCJ=no
;;
beos*)
if $LD --help 2>&1 | grep ': supported targets:.* elf' > /dev/null; then
allow_undefined_flag_GCJ=unsupported
# Joseph Beckenbach <jrb3@best.com> says some releases of gcc
# support --undefined. This deserves some investigation. FIXME
archive_cmds_GCJ='$CC -nostart $libobjs $deplibs $compiler_flags ${wl}-soname $wl$soname -o $lib'
else
ld_shlibs_GCJ=no
fi
;;
cygwin* | mingw* | pw32*)
# _LT_AC_TAGVAR(hardcode_libdir_flag_spec, GCJ) is actually meaningless,
# as there is no search path for DLLs.
src/judy-1.0.5/doc/ext/JudyHS_3.htm view on Meta::CPAN
<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
practical. The <B>Length</B> of each array-of-bytes can be from 0 to
the limits of <I>malloc()</I> (about 2GB).
<P>
The hallmark of <B>JudyHS</B> is speed with scalability, but memory
efficiency is excellent. The speed is very competitive with the best
hashing methods. The memory efficiency is similar to a linked list of
the same <B>Indexes</B> and <B>Values</B>. <B>JudyHS</B> is designed to
scale from 0 to billions of <B>Indexes</B>.
<P>
A JudyHS array is allocated with a <B>NULL</B> pointer
<PRE>
Pvoid_t PJHSArray = (Pvoid_t) NULL;
</PRE>
<P>
Because the macro forms of the API have a simpler error handling
src/judy-1.0.5/doc/ext/Judy_3.htm view on Meta::CPAN
<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
<B>JudyL</B> arrays and a virtual hash table size of 4 billion).
<P>
src/judy-1.0.5/ltmain.sh view on Meta::CPAN
show="$echo"
show_help=
execute_dlfiles=
duplicate_deps=no
preserve_args=
lo2o="s/\\.lo\$/.${objext}/"
o2lo="s/\\.${objext}\$/.lo/"
#####################################
# Shell function definitions:
# This seems to be the best place for them
# func_mktempdir [string]
# Make a temporary directory that won't clash with other running
# libtool processes, and avoids race conditions if possible. If
# given, STRING is the basename for that directory.
func_mktempdir ()
{
my_template="${TMPDIR-/tmp}/${1-$progname}"
if test "$run" = ":"; then
src/judy-1.0.5/ltmain.sh view on Meta::CPAN
IFS="$save_ifs"
eval cmd=\"$cmd\"
$show "$cmd"
$run eval "$cmd"
if test "$?" -ne 0 && test "$rmforce" != yes; then
exit_status=1
fi
done
IFS="$save_ifs"
fi
# FIXME: should reinstall the best remaining shared library.
;;
esac
fi
;;
*.lo)
# Possibly a libtool object, so verify it.
if (${SED} -e '2q' $file | grep "^# Generated by .*$PACKAGE") >/dev/null 2>&1; then
# Read the .lo file
src/judy-1.0.5/src/JudyCommon/JudyByCount.c view on Meta::CPAN
// given Index (that is, its position in the list of valid indexes from the
// beginning) as a degenerate case, because in general the count between two
// Indexes, inclusive, is not always just the difference in their ordinals.
// However, it suffices for Judy*ByCount() to simply be an ordinal-to-Index
// mapper.
//
// Note: Like Judy*Count(), this code must "count sideways" in branches, which
// can result in a lot of cache line fills. However, unlike Judy*Count(), this
// code does not receive a specific Index, hence digit, where to start in each
// branch, so it cant accurately calculate cache line fills required in each
// direction. The best it can do is an approximation based on the total
// population of the expanse (pop1 from Pjp) and the ordinal of the target
// Index (see SETOFFSET()) within the expanse.
//
// Compile with -DSMARTMETRICS to obtain global variables containing smart
// cache line metrics. Note: Dont turn this on simultaneously for this file
// and JudyCount.c because they export the same globals.
// ****************************************************************************
#if (! (defined(JUDY1) || defined(JUDYL)))
#error: One of -DJUDY1 or -DJUDYL must be specified.
src/judy-1.0.5/src/JudyCommon/JudyPrivateBranch.h view on Meta::CPAN
//
// To use this, compile a temporary *.c file containing:
//
// #define DEBUG
// #define JUDY_ASSERT
// #define TEST_INSDEL
// #include "JudyPrivate.h"
// #include "JudyPrivateBranch.h"
//
// Use a command like this: cc -Ae +DD64 -I. -I JudyCommon -o t t.c
// For best results, include +DD64 on a 64-bit system.
//
// This test code exercises some tricky macros, but the output must be studied
// manually to verify it. Assume that for even-index testing, whole words
// (Word_t) suffices.
#include <stdio.h>
#define INDEXES 3 // in each array.
src/judy-1.0.5/src/JudyHS/JudyHS.c view on Meta::CPAN
much faster that a RAM access, so building up a word from bytes takes
no longer that a whole word access. I am taking advantage of this to
make this code endian neutral. A side effect of this is strings do
not need to be aligned, nor tested to be on to a word boundry. In
older and in slow (RISC) machines, this may be a performance issue.
I have given up trying to optimize for machines that have very slow
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
src/judy-1.0.5/test/SLcompare.c view on Meta::CPAN
//
// Judy <textfile>
// Hash <textfile>
// Splay <textfile>
// Redblack <textfile>
/*
This program will give you a chance to measure the speed/space
performance of 4 different string store/lookup algorithms on your data
set. All are very fast and generally can scale to very large data sets.
The memory efficiency is usually best with the Judy algorithm because it
uses the opportunity to compress data in a digital tree. The Hashing is
generally the fastest algorithm, however it looses its advantage when
the number of stored exceeds about 5X the size of the hash table.
Many thanks to J. Zobel for supplying the code for Hash, Splay and
Redblack algorithms.
I will be including more algorithms as people donate code for testing.
The Judy code is available at: <http://sourceforge.net/projects/judy>
9/2002 (dlb).
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
#define PTR_UINT unsigned long
#endif
/*
INTERNAL_SIZE_T is the word-size used for internal bookkeeping
of chunk sizes.
The default version is the same as size_t.
While not strictly necessary, it is best to define this as an
unsigned type, even if size_t is a signed type. This may avoid some
artificial size limitations on some systems.
On a 64-bit machine, you may be able to reduce malloc overhead by
defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
expense of not being able to handle more than 2^32 of malloced
space. If this limitation is acceptable, you are encouraged to set
this unless you are on a platform requiring 16byte alignments. In
this case the alignment requirements turn out to negate any
potential advantages of decreasing size_t word size.
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
/* #define MORECORE_CANNOT_TRIM */
/*
Define HAVE_MMAP as true to optionally make malloc() use mmap() to
allocate very large blocks. These will be returned to the
operating system immediately after a free(). Also, if mmap
is available, it is used as a backup strategy in cases where
MORECORE fails to provide space from system.
This malloc is best tuned to work with mmap for large requests.
If you do not have mmap, operations involving very large chunks (1MB
or so) may be slower than you'd like.
*/
#define HAVE_MMAP 0
#ifndef HAVE_MMAP
#define HAVE_MMAP 1
#endif
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
is 64 (also the default). You wouldn't want it any higher than this
anyway. Fastbins are designed especially for use with many small
structs, objects or strings -- the default handles
structs/objects/arrays with sizes up to 16 4byte fields, or small
strings representing words, tokens, etc. Using fastbins for larger
objects normally worsens fragmentation without improving speed.
M_MXFAST is set in REQUEST size units. It is internally used in
chunksize units, which adds padding and alignment. You can reduce
M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
algorithm to be a closer approximation of fifo-best-fit in all cases,
not just for larger requests, but will generally cause it to be
slower.
*/
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST 1
#endif
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
}
}
transfer_tree_links(t, c);
check_tree(c);
}
}
static Void_t* use_treechunk(mstate av,
CHUNK_SIZE_T nb,
tchunkptr bestchunk,
CHUNK_SIZE_T bestsize,
tchunkptr leaf) {
CHUNK_SIZE_T rsize;
if (bestchunk->bk != bestchunk)
unlink_chained_node(bestchunk);
else {
unlink_leaf_node(av, leaf);
if (leaf != bestchunk)
transfer_tree_links(bestchunk, leaf);
}
rsize = bestsize - nb;
if (rsize >= MINSIZE) {
mchunkptr rem = chunk_at_offset(bestchunk, nb);
set_head(bestchunk, nb | PREV_INUSE);
set_head(rem, rsize | PREV_INUSE);
set_foot(rem, rsize);
insert_chunk(av, rem, rsize);
}
else {
set_inuse_bit_at_offset(bestchunk, bestsize);
}
check_malloced_chunk((mchunkptr)(bestchunk), nb);
return chunk2mem(bestchunk);
}
/*
------------------------------ malloc ------------------------------
*/
Void_t* mALLOc(size_t bytes) {
mstate av = get_malloc_state();
CHUNK_SIZE_T nb;
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
}
}
check_malloced_chunk(p, nb);
return chunk2mem(p);
}
if (av->treebits != 0) {
bitmap_t vbit = least_bit(av->treebits);
bin_index_t vidx = bit2idx(vbit);
tbinptr* vbin = tbin_at(av, vidx);
tchunkptr bestchunk = *vbin;
tchunkptr c = leftmost_child(bestchunk);
CHUNK_SIZE_T bestsize = chunksize(bestchunk);
tchunkptr leaf;
CHUNK_SIZE_T rsize;
/* Fast path if remainder will replace bestchunk */
if (c == 0) {
rsize = bestsize - nb;
leaf = bestchunk;
if (rsize >= minsize_for_treeindex(vidx) &&
bestchunk->bk == bestchunk) {
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;
bestsize = csize;
}
leaf = c;
c = leftmost_child(c);
} while (c != 0);
}
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
}
}
else {
bin_index_t tidx = treebin_index(nb);
bitmap_t tbit = idx2bit(tidx);
if (tbit <= av->treebits) {
tchunkptr bestchunk = 0;
CHUNK_SIZE_T bestsize = MAX_CHUNK_SIZE;
tchunkptr leaf;
bitmap_t vbit;
for (;;) {
if ((tbit & av->treebits) != 0) {
tchunkptr t = *tbin_at(av, tidx);
bin_index_t shift = bitshift_for_index(tidx);
for (;;) {
int dir;
CHUNK_SIZE_T tsize = chunksize(t);
leaf = t;
if (tsize >= nb && tsize < bestsize) {
bestchunk = t;
bestsize = tsize;
if (tsize == nb && t->bk != t)
break;
}
dir = (shift == 0)? 0 : (nb >> shift--) & 1;
t = leaf->child[dir];
if (t == 0) {
shift = 0; /* if forced right, go leftmost from now on */
t = leaf->child[1-dir];
if (t == 0)
break;
}
}
if (bestchunk != 0)
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
}
if (have_fastchunks(av))
malloc_consolidate(av);
else
break;
}
vbit = least_bit(left_bits(tbit) & av->treebits);
if (vbit != 0) {
bin_index_t vidx = bit2idx(vbit);
tbinptr* vbin = tbin_at(av, vidx);
tchunkptr c = *vbin;
do {
CHUNK_SIZE_T csize = chunksize(c);
leaf = c;
if (csize < bestsize) {
bestchunk = c;
bestsize = csize;
}
c = leftmost_child(c);
} while (c != 0);
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
}
}
}
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). This is called in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).
We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhuasted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
* malloc_extend_top: fix mask error that caused wastage after
foreign sbrks
* Add linux mremap support code from HJ Liu
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
* Integrated most documentation with the code.
* Add support for mmap, with help from
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
* Use last_remainder in more cases.
* Pack bins using idea from colin@nyx10.cs.du.edu
* Use ordered bins instead of best-fit threshhold
* Eliminate block-local decls to simplify tracing and debugging.
* Support another case of realloc via move into top
* Fix error occuring when initial sbrk_base not word-aligned.
* Rely on page size for units instead of SBRK_UNIT to
avoid surprises about sbrk alignment conventions.
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
(raymond@es.ele.tue.nl) for the suggestion.
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
* More precautions for cases where other routines call sbrk,
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
* Inverted this history list
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
* Removed all preallocation code since under current scheme
the work required to undo bad preallocations exceeds
the work saved in good cases for most test programs.
* No longer use return list or unconsolidated bins since
no scheme using them consistently outperforms those that don't
given above changes.
* Use best fit for very large chunks to prevent some worst-cases.
* Added some support for debugging
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
* Removed footers when chunks are in use. Thanks to
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
* Added malloc_trim, with help from Wolfram Gloger
(wmglo@Dent.MED.Uni-Muenchen.DE).
( run in 1.336 second using v1.01-cache-2.11-cpan-4e96b696675 )