tlwg / libdatrie Goto Github PK
View Code? Open in Web Editor NEWLicense: GNU Lesser General Public License v2.1
License: GNU Lesser General Public License v2.1
datrie - Double-Array Trie Library ================================== This is an implementation of double-array structure for representing trie, as proposed by Junichi Aoe [1]. Trie is a kind of digital search tree, an efficient indexing method in which search time is independent of database size. It only takes O(m) search time, where m is the length of the search string. Comparably as efficient as hashing, trie also provides flexibility on incremental matching and key spelling manipulation. This makes it ideal for lexical analyzers, as well as spelling dictionaries. See the details of the implementation at [2]: https://linux.thai.net/~thep/datrie/datrie.html Historically, this was first implemented as C++ classes in a library called midatrie [2], but later simplified and rewritten from scratch in C. -- Theppitak Karoonboonyanan. September 2006. References ---------- [1] Aoe, J. "An Efficient Digital Search Algorithm by Using a Double-Array Structure". IEEE Transactions on Software Engineering. Vol. 15, 9 (Sep 1989). pp. 1066-1077. [2] Karoonboonyanan, T. "An Implementation of Double-Array Trie". https://linux.thai.net/~thep/datrie/datrie.html
This might be the wrong first step, but I did: ./autogen.sh
:
+ DIE=0
+ libtoolize --version
+ LIBTOOLIZE=libtoolize
+ [ 0 -eq 1 ]
+ autoheader [20/373]
+ libtoolize --force
libtoolize: putting auxiliary files in AC_CONFIG_AUX_DIR, 'build-aux'.
libtoolize: linking file 'build-aux/ltmain.sh'
libtoolize: putting macros in AC_CONFIG_MACRO_DIRS, 'm4'.
libtoolize: linking file 'm4/libtool.m4'
libtoolize: linking file 'm4/ltoptions.m4'
libtoolize: linking file 'm4/ltsugar.m4'
libtoolize: linking file 'm4/ltversion.m4'
libtoolize: linking file 'm4/lt~obsolete.m4'
+ aclocal
+ automake --add-missing
configure.ac:29: installing 'build-aux/compile'
configure.ac:13: installing 'build-aux/missing'
datrie/Makefile.am: installing 'build-aux/depcomp'
+ autoconf -f
configure.ac:120: error: possibly undefined macro: AC_MSG_RESULT
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
It does result in configure
, so if I do ./configure
it ends with:
checking for size_t... yes
./configure: line 12895: syntax error near unexpected token `$DOXYGEN_VER,ge,DOXYGEN_REQ_VER,'
./configure: line 12895: ` AX_COMPARE_VERSION($DOXYGEN_VER,ge,DOXYGEN_REQ_VER,'
I have doxygen 1.8.13-10 installed, and configure has DOXYGEN_REQ_VER=1.8.8
, but something is unhappy...
I just commented out the check, since I knew it was OK, and then configure completes, and make works too.
Here are some reports from Coverity Scan for libdatrie-0.2.13.
1. Defect type: GCC_ANALYZER_WARNING
1. libdatrie-0.2.13/datrie/trie.c:1115:14: warning[-Wanalyzer-malloc-leak]: leak of 's'
41. libdatrie-0.2.13/datrie/trie.c:75:62: note: in definition of macro 'trie_da_get_tail_index'
# 1113| *alpha_p++ = alpha_map_trie_to_char (s->trie->alpha_map, *tail_str++);
# 1114| }
# 1115|-> *alpha_p = 0;
# 1116|
# 1117| return alpha_key;
2. Defect type: GCC_ANALYZER_WARNING
1. libdatrie-0.2.13/datrie/trie-string.c:64:8: warning[-Wanalyzer-possible-null-dereference]: dereference of possibly-NULL 'p'
# 62| *p++ = *str++;
# 63| }
# 64|-> *p = TRIE_CHAR_TERM;
# 65|
# 66| return dup;
Does the above defect mean some issue or just false alert?
Current API of libdatrie
requires all strings to be nul-terminated. Because of this, the trie can't store arbitrary byte sequences e.g. integers.
I see two ways of addressing this limitation:
unit8
to uint16
for TrieChar
.The original request was submitted to the Python wrapper, see pytries/datrie#31.
mv -f .deps/alpha-map.Tpo .deps/alpha-map.Plo
/bin/sh ../libtool --tag=CC --mode=link gcc -g -O2 -no-undefined -version-info 4:4:3 -Wl,-version-script -Wl,./libdatrie.map -o libdatrie.la -rpath /usr/local/libdatrie/lib dstring.lo trie-string.lo fileutils.lo darray.lo tail.lo trie.lo alpha-map.lo
libtool: link: gcc -shared -fPIC -DPIC .libs/dstring.o .libs/trie-string.o .libs/fileutils.o .libs/darray.o .libs/tail.o .libs/trie.o .libs/alpha-map.o -g -O2 -Wl,-version-script -Wl,./libdatrie.map -Wl,-soname -Wl,libdatrie.so.1 -o .libs/libdatrie.so.1.3.4
libtool: link: (cd ".libs" && rm -f "libdatrie.so.1" && ln -s "libdatrie.so.1.3.4" "libdatrie.so.1")
libtool: link: (cd ".libs" && rm -f "libdatrie.so" && ln -s "libdatrie.so.1.3.4" "libdatrie.so")
libtool: link: ar cru .libs/libdatrie.a dstring.o trie-string.o fileutils.o darray.o tail.o trie.o alpha-map.o
libtool: link: ranlib .libs/libdatrie.a
libtool: link: ( cd ".libs" && rm -f "libdatrie.la" && ln -s "../libdatrie.la" "libdatrie.la" )
make[2]: Leaving directory /home/devphp/downloads/libdatrie-0.2.11/datrie' Making all in tools make[2]: Entering directory
/home/devphp/downloads/libdatrie-0.2.11/tools'
gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trietool.o -MD -MP -MF .deps/trietool.Tpo -c -o trietool.o trietool.c
mv -f .deps/trietool.Tpo .deps/trietool.Po
/bin/sh ../libtool --tag=CC --mode=link gcc -g -O2 -o trietool trietool.o ../datrie/libdatrie.la
libtool: link: gcc -g -O2 -o .libs/trietool trietool.o ../datrie/.libs/libdatrie.so -Wl,-rpath -Wl,/usr/local/libdatrie/lib
trietool.o: In function conv_from_alpha': /home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:170: undefined reference to
libiconv'
trietool.o: In function conv_to_alpha': /home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:125: undefined reference to
libiconv'
trietool.o: In function command_delete_list': /home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:470: undefined reference to
libiconv_open'
/home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:506: undefined reference to libiconv_close' trietool.o: In function
command_add_list':
/home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:368: undefined reference to libiconv_open' /home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:417: undefined reference to
libiconv_close'
trietool.o: In function init_conv': /home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:108: undefined reference to
libiconv_open'
/home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:109: undefined reference to libiconv_open' trietool.o: In function
close_conv':
/home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:180: undefined reference to libiconv_close' /home/devphp/downloads/libdatrie-0.2.11/tools/trietool.c:181: undefined reference to
libiconv_close'
collect2: error: ld returned 1 exit status
make[2]: *** [trietool] Error 1
make[2]: Leaving directory /home/devphp/downloads/libdatrie-0.2.11/tools' make[1]: *** [all-recursive] Error 1 make[1]: Leaving directory
/home/devphp/downloads/libdatrie-0.2.11'
make: *** [all] Error 2
Building libdatrie-0.2.10 on OS X 10.11, I get a warning:
gcc -DHAVE_CONFIG_H -I. -I.. -I.. -I/sw/include -g -O2 -MT trietool.o -MD -MP -MF .deps/trietool.Tpo -c -o trietool.o trietool.c
trietool.c:128:13: warning: comparison of unsigned expression < 0 is always false [-Wtautological-compare]
if (res < 0)
~~~ ^ ~
1 warning generated.
res is (correctly per iconv prototype) a size_t, but size_t is generally some sort of unsigned int: the warning seems on target. The iconv manpage says that the return in case of error isn't "-1" but is "(size_t)(-1)": -1 cast to the return type. And its example code is:
size_t nconv;
nconv = iconv (cd, &inptr, &insize, &wrptr, &avail);
if (nconv == (size_t) -1) ...
So trietool.c at line 128 should be changed:
- if (res < 0)
+ if (res == (size_t) -1)
return res;
Using C++ should allow to replace handcoded parser with a Kaitai Struct generated one. There also may be other benefits, but I have not checked if they apply to this code.
This would add the convenience of loading a trie from an array. The capability is somewhat present via a roundtrip, because a serialized trie can be saved to a file and then loaded from it using the existing API, so I am not sure how useful it would be.
Autotools is damn damn damn damn shit. Completely unusable. And in the current state of build scripts it is unbuildable on my machine, so I don't test the lib as it is, I just test its python bindings (which build the lib themselves without autotools).
from git master
topkek@ayylmai MSYS /self/libdatrie/src/libdatrie
$ sh autogen.sh
+ DIE=0
+ libtoolize --version
+ LIBTOOLIZE=libtoolize
+ '[' 0 -eq 1 ']'
+ autoheader
+ libtoolize --force
libtoolize: putting auxiliary files in AC_CONFIG_AUX_DIR, 'build-aux'.
libtoolize: linking file 'build-aux/ltmain.sh'
libtoolize: putting macros in AC_CONFIG_MACRO_DIRS, 'm4'.
libtoolize: linking file 'm4/libtool.m4'
libtoolize: linking file 'm4/ltoptions.m4'
libtoolize: linking file 'm4/ltsugar.m4'
libtoolize: linking file 'm4/ltversion.m4'
libtoolize: linking file 'm4/lt~obsolete.m4'
+ aclocal
+ automake --add-missing
configure.ac:29: installing 'build-aux/compile'
configure.ac:33: installing 'build-aux/config.guess'
configure.ac:33: installing 'build-aux/config.sub'
configure.ac:13: installing 'build-aux/install-sh'
configure.ac:13: installing 'build-aux/missing'
datrie/Makefile.am: installing 'build-aux/depcomp'
parallel-tests: installing 'build-aux/test-driver'
+ autoconf -f
configure.ac:121: error: possibly undefined macro: AC_MSG_RESULT
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
The Readme suggests that this algorithm has a O(1) time complexity for searching.
However, every other source I read so far about time complexity of tries claims that the complexity is O(M) for searching where M is the maximum length of all inserted words. Which also does make more sense to me intuitively because in my imagination, the algorithm works like this: for every letter in the prefix I enter, the algorithm takes the corresponding path in the tree. This means it has to follow at least the number of letters in my prefix and at most M edges.
Can you explain to me where (or if) I'm wrong here?
Running the test suite in parallel via the -j<number of tests to run in parallel>
flag of make currently leads to test failures. This is caused by two tests (test_file
and test_serialization
) operating on the same file (test.tri
). If both tests are run at the same time, they interfere with each other, causing one of them to fail.
A solution might be to rename the test file in the define of TRIE_FILENAME
in tests/test_file.c and tests/test_serialization.c to something specific / unique for each tests.
configure && make
.
.
checking for locale_charset in -liconv... yes
.
.
libtool: link: cc -O2 -pipe -DLIBICONV_PLUG -fstack-protector-strong -isystem /usr/local/include -fno-strict-aliasing -fstack-protector-strong -o .libs/trietool trietool.o -L/usr/local/lib ../datrie/.libs/libdatrie.so -Wl,-rpath -Wl,/usr/local/lib
ld: error: undefined symbol: locale_charset
>>> referenced by trietool.c
>>> trietool.o:(main)
cc: error: linker command failed with exit code 1 (use -v to see invocation)
*** [trietool] Error code 1
make[6]: stopped in /wrkdirs/usr/ports/devel/libdatrie/work/libdatrie-0.2.13/tools
Noticed on FreeBSD 12 with the libiconv package installed (in /usr/local).
The link command is missing -liconv
Under
Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin15.6.0
make put this warning
trietool.c:128:13: warning: comparison of unsigned expression < 0 is always false [-Wtautological-compare]
if (res < 0)1 warning generated.
128c128
< if (res < 0)
---
> if (res == (size_t) -1)
Running ./autogen.sh
results in the following error.
configure.ac:120: error: possibly undefined macro: AC_MSG_RESULT
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
There is issue as show below
`
[root@61-90-188-123 libdatrie-r_0_2_10]# ./autogen.sh
.'. libtoolize: linking file
./ltmain.sh'm4'. libtoolize: linking file
m4/libtool.m4'm4/ltoptions.m4' libtoolize: linking file
m4/ltsugar.m4'm4/ltversion.m4' libtoolize: linking file
m4/lt~obsolete.m4'[root@61-90-188-123
libdatrie-r_0_2_9]# diff ./configure.ac ../libdatrie-r_0_2_10/configure.acAC_INIT(libdatrie, 0.2.10, [email protected])
17c17
< LT_REVISION=2
LT_REVISION=3
116,121c116,118
< if expr $DOXYGEN_VER < $DOXYGEN_REQ_VER > /dev/null; then
< AC_MSG_RESULT([$DOXYGEN_VER, no, documentation disabled])
< enable_doxygen_doc="no"
< else
< AC_MSG_RESULT([$DOXYGEN_VER, yes])
< fi
AX_COMPARE_VERSION([$DOXYGEN_VER],[ge],[DOXYGEN_REQ_VER], [AC_MSG_RESULT([$DOXYGEN_VER, yes])], [AC_MSG_RESULT([$DOXYGEN_VER, no, documentation disabled]); enable_doxygen_doc="no"])
`
When I attempt to cross-compile using arm-linux-gnueabihf-gcc
, I get the following:
vanessa@vanessa-desktop ~/git-builds/junk/libdatrie-0.2.12 🌸 ./configure --host=arm-linux-gnueabihf
checking for a BSD-compatible install... /usr/bin/install -c
checking whether build environment is sane... yes
checking for arm-linux-gnueabihf-strip... arm-linux-gnueabihf-strip
checking for a thread-safe mkdir -p... /bin/mkdir -p
checking for gawk... no
checking for mawk... mawk
checking whether make sets $(MAKE)... yes
checking whether make supports nested variables... yes
checking for arm-linux-gnueabihf-gcc... arm-linux-gnueabihf-gcc
checking whether the C compiler works... yes
checking for C compiler default output file name... a.out
checking for suffix of executables...
checking whether we are cross compiling... yes
checking for suffix of object files... o
checking whether we are using the GNU C compiler... yes
checking whether arm-linux-gnueabihf-gcc accepts -g... yes
checking for arm-linux-gnueabihf-gcc option to accept ISO C89... none needed
checking whether arm-linux-gnueabihf-gcc understands -c and -o together... yes
checking for style of include used by make... GNU
checking dependency style of arm-linux-gnueabihf-gcc... gcc3
checking whether ln -s works... yes
checking whether make sets $(MAKE)... (cached) yes
checking build system type... x86_64-pc-linux-gnu
checking host system type... arm-unknown-linux-gnueabihf
checking how to print strings... printf
checking for a sed that does not truncate output... /home/vanessa/.cpkg/bin/sed
checking for grep that handles long lines and -e... /bin/grep
checking for egrep... /bin/grep -E
checking for fgrep... /bin/grep -F
checking for ld used by arm-linux-gnueabihf-gcc... /usr/arm-linux-gnueabihf/bin/ld
checking if the linker (/usr/arm-linux-gnueabihf/bin/ld) is GNU ld... yes
checking for BSD- or MS-compatible name lister (nm)... /usr/bin/arm-linux-gnueabihf-nm -B
checking the name lister (/usr/bin/arm-linux-gnueabihf-nm -B) interface... BSD nm
checking the maximum length of command line arguments... 1572864
checking how to convert x86_64-pc-linux-gnu file names to arm-unknown-linux-gnueabihf format... func_convert_file_noop
checking how to convert x86_64-pc-linux-gnu file names to toolchain format... func_convert_file_noop
checking for /usr/arm-linux-gnueabihf/bin/ld option to reload object files... -r
checking for arm-linux-gnueabihf-objdump... objdump
checking how to recognize dependent libraries... pass_all
checking for arm-linux-gnueabihf-dlltool... dlltool
checking how to associate runtime and link libraries... printf %s\n
checking for arm-linux-gnueabihf-ar... arm-linux-gnueabihf-ar
checking for archiver @FILE support... @
checking for arm-linux-gnueabihf-strip... (cached) arm-linux-gnueabihf-strip
checking for arm-linux-gnueabihf-ranlib... arm-linux-gnueabihf-ranlib
checking command to parse /usr/bin/arm-linux-gnueabihf-nm -B output from arm-linux-gnueabihf-gcc object... ok
checking for sysroot... no
checking for a working dd... /bin/dd
checking how to truncate binary pipes... /bin/dd bs=4096 count=1
checking for arm-linux-gnueabihf-mt... no
checking for mt... mt
configure: WARNING: using cross tools not prefixed with host triplet
checking if mt is a manifest tool... no
checking how to run the C preprocessor... arm-linux-gnueabihf-gcc -E
checking for ANSI C header files... yes
checking for sys/types.h... yes
checking for sys/stat.h... yes
checking for stdlib.h... yes
checking for string.h... yes
checking for memory.h... yes
checking for strings.h... yes
checking for inttypes.h... yes
checking for stdint.h... yes
checking for unistd.h... yes
checking for dlfcn.h... yes
checking for objdir... .libs
checking if arm-linux-gnueabihf-gcc supports -fno-rtti -fno-exceptions... no
checking for arm-linux-gnueabihf-gcc option to produce PIC... -fPIC -DPIC
checking if arm-linux-gnueabihf-gcc PIC flag -fPIC -DPIC works... yes
checking if arm-linux-gnueabihf-gcc static flag -static works... yes
checking if arm-linux-gnueabihf-gcc supports -c -o file.o... yes
checking if arm-linux-gnueabihf-gcc supports -c -o file.o... (cached) yes
checking whether the arm-linux-gnueabihf-gcc linker (/usr/arm-linux-gnueabihf/bin/ld) supports shared libraries... yes
checking whether -lc should be explicitly linked in... no
checking dynamic linker characteristics... GNU/Linux ld.so
checking how to hardcode library paths into programs... immediate
checking whether stripping libraries is possible... yes
checking if libtool supports shared libraries... yes
checking whether to build shared libraries... yes
checking whether to build static libraries... yes
checking whether linker supports -version-script... yes
checking for iconv_open... yes
checking for locale_charset in -liconv... no
checking for nl_langinfo (CODESET)... yes
checking for ANSI C header files... (cached) yes
checking limits.h usability... yes
checking limits.h presence... yes
checking for limits.h... yes
checking for stdlib.h... (cached) yes
checking stdio.h usability... yes
checking stdio.h presence... yes
checking for stdio.h... yes
checking for string.h... (cached) yes
checking for an ANSI C-conforming const... yes
checking for size_t... yes
checking for doxygen... no
checking for stdlib.h... (cached) yes
checking for GNU libc compatible malloc... no
checking that generated files are newer than configure... done
configure: creating ./config.status
config.status: creating Makefile
config.status: creating datrie-0.2.pc
config.status: creating datrie/Makefile
config.status: creating tools/Makefile
config.status: creating man/Makefile
config.status: creating doc/Makefile
config.status: creating doc/Doxyfile
config.status: creating tests/Makefile
config.status: creating config.h
config.status: executing depfiles commands
config.status: executing libtool commands
vanessa@vanessa-desktop ~/git-builds/junk/libdatrie-0.2.12 🌸 make -j6
make all-recursive
make[1]: Entering directory '/home/vanessa/git-builds/junk/libdatrie-0.2.12'
Making all in datrie
make[2]: Entering directory '/home/vanessa/git-builds/junk/libdatrie-0.2.12/datrie'
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT dstring.lo -MD -MP -MF .deps/dstring.Tpo -c -o dstring.lo dstring.c
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trie-string.lo -MD -MP -MF .deps/trie-string.Tpo -c -o trie-string.lo trie-string.c
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT fileutils.lo -MD -MP -MF .deps/fileutils.Tpo -c -o fileutils.lo fileutils.c
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT darray.lo -MD -MP -MF .deps/darray.Tpo -c -o darray.lo darray.c
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT tail.lo -MD -MP -MF .deps/tail.Tpo -c -o tail.lo tail.c
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trie.lo -MD -MP -MF .deps/trie.Tpo -c -o trie.lo trie.c
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT dstring.lo -MD -MP -MF .deps/dstring.Tpo -c dstring.c -fPIC -DPIC -o .libs/dstring.o
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT fileutils.lo -MD -MP -MF .deps/fileutils.Tpo -c fileutils.c -fPIC -DPIC -o .libs/fileutils.o
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trie-string.lo -MD -MP -MF .deps/trie-string.Tpo -c trie-string.c -fPIC -DPIC -o .libs/trie-string.o
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT darray.lo -MD -MP -MF .deps/darray.Tpo -c darray.c -fPIC -DPIC -o .libs/darray.o
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trie.lo -MD -MP -MF .deps/trie.Tpo -c trie.c -fPIC -DPIC -o .libs/trie.o
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trie-string.lo -MD -MP -MF .deps/trie-string.Tpo -c trie-string.c -o trie-string.o >/dev/null 2>&1
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT tail.lo -MD -MP -MF .deps/tail.Tpo -c tail.c -fPIC -DPIC -o .libs/tail.o
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT fileutils.lo -MD -MP -MF .deps/fileutils.Tpo -c fileutils.c -o fileutils.o >/dev/null 2>&1
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT dstring.lo -MD -MP -MF .deps/dstring.Tpo -c dstring.c -o dstring.o >/dev/null 2>&1
mv -f .deps/trie-string.Tpo .deps/trie-string.Plo
mv -f .deps/fileutils.Tpo .deps/fileutils.Plo
/bin/bash ../libtool --tag=CC --mode=compile arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT alpha-map.lo -MD -MP -MF .deps/alpha-map.Tpo -c -o alpha-map.lo alpha-map.c
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trie.lo -MD -MP -MF .deps/trie.Tpo -c trie.c -o trie.o >/dev/null 2>&1
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT darray.lo -MD -MP -MF .deps/darray.Tpo -c darray.c -o darray.o >/dev/null 2>&1
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT tail.lo -MD -MP -MF .deps/tail.Tpo -c tail.c -o tail.o >/dev/null 2>&1
mv -f .deps/dstring.Tpo .deps/dstring.Plo
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT alpha-map.lo -MD -MP -MF .deps/alpha-map.Tpo -c alpha-map.c -fPIC -DPIC -o .libs/alpha-map.o
mv -f .deps/darray.Tpo .deps/darray.Plo
mv -f .deps/tail.Tpo .deps/tail.Plo
libtool: compile: arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT alpha-map.lo -MD -MP -MF .deps/alpha-map.Tpo -c alpha-map.c -o alpha-map.o >/dev/null 2>&1
mv -f .deps/trie.Tpo .deps/trie.Plo
mv -f .deps/alpha-map.Tpo .deps/alpha-map.Plo
/bin/bash ../libtool --tag=CC --mode=link arm-linux-gnueabihf-gcc -g -O2 -no-undefined -version-info 4:5:3 -Wl,-version-script -Wl,./libdatrie.map -o libdatrie.la -rpath /usr/local/lib dstring.lo trie-string.lo fileutils.lo darray.lo tail.lo trie.lo alpha-map.lo
libtool: link: arm-linux-gnueabihf-gcc -shared -fPIC -DPIC .libs/dstring.o .libs/trie-string.o .libs/fileutils.o .libs/darray.o .libs/tail.o .libs/trie.o .libs/alpha-map.o -g -O2 -Wl,-version-script -Wl,./libdatrie.map -Wl,-soname -Wl,libdatrie.so.1 -o .libs/libdatrie.so.1.3.5
libtool: link: (cd ".libs" && rm -f "libdatrie.so.1" && ln -s "libdatrie.so.1.3.5" "libdatrie.so.1")
libtool: link: (cd ".libs" && rm -f "libdatrie.so" && ln -s "libdatrie.so.1.3.5" "libdatrie.so")
libtool: link: arm-linux-gnueabihf-ar cru .libs/libdatrie.a dstring.o trie-string.o fileutils.o darray.o tail.o trie.o alpha-map.o
arm-linux-gnueabihf-ar: `u' modifier ignored since `D' is the default (see `U')
libtool: link: arm-linux-gnueabihf-ranlib .libs/libdatrie.a
libtool: link: ( cd ".libs" && rm -f "libdatrie.la" && ln -s "../libdatrie.la" "libdatrie.la" )
make[2]: Leaving directory '/home/vanessa/git-builds/junk/libdatrie-0.2.12/datrie'
Making all in tools
make[2]: Entering directory '/home/vanessa/git-builds/junk/libdatrie-0.2.12/tools'
arm-linux-gnueabihf-gcc -DHAVE_CONFIG_H -I. -I.. -I.. -g -O2 -MT trietool.o -MD -MP -MF .deps/trietool.Tpo -c -o trietool.o trietool.c
mv -f .deps/trietool.Tpo .deps/trietool.Po
/bin/bash ../libtool --tag=CC --mode=link arm-linux-gnueabihf-gcc -g -O2 -o trietool trietool.o ../datrie/libdatrie.la
libtool: link: arm-linux-gnueabihf-gcc -g -O2 -o .libs/trietool trietool.o ../datrie/.libs/libdatrie.so
/usr/lib/gcc-cross/arm-linux-gnueabihf/8/../../../../arm-linux-gnueabihf/bin/ld: trietool.o: in function `full_path':
/home/vanessa/git-builds/junk/libdatrie-0.2.12/tools/trietool.c:187: undefined reference to `rpl_malloc'
collect2: error: ld returned 1 exit status
make[2]: *** [Makefile:394: trietool] Error 1
make[2]: Leaving directory '/home/vanessa/git-builds/junk/libdatrie-0.2.12/tools'
make[1]: *** [Makefile:491: all-recursive] Error 1
make[1]: Leaving directory '/home/vanessa/git-builds/junk/libdatrie-0.2.12'
make: *** [Makefile:379: all] Error 2
It may be solvable by commenting out/removing https://github.com/tlwg/libdatrie/blob/master/configure.ac#L135
Thanks!
Is there one in the public API?
We currently use O(n) implementation via trie_enumerate
in pytries/datrie, but as a user I'd expect size queries to always be constant time, so I'd love to improve this part of the bindings if possible.
I used libdatrie v2.9.0 in a PHP extension and it works.
I saw there was a libdatrie v2.10.0, so I tried it, but it would get memory corruption error in "trie_new" method in trie.c. I think it's because that you changed alpha map data structure in v2.10.0
Here below contains related source file methods and core dump backtrace:
PHP_FUNCTION(datrie_filter_new)
{
Trie *trie;
AlphaMap *alpha_map;
int ret;
alpha_map = alpha_map_new();
if (! alpha_map) {
RETURN_NULL();
}
if (alpha_map_add_range(alpha_map, 0x00, 0xff) != 0) {
/* treat all strings as byte stream */
alpha_map_free(alpha_map);
RETURN_NULL();
}
trie = trie_new(alpha_map); /** line 252*/
alpha_map_free(alpha_map);
if (! trie) {
RETURN_NULL();
}
RETURN_RES(zend_register_resource(trie, le_datrie_filter));
}
Trie *
trie_new (const AlphaMap *alpha_map)
{
Trie *trie;
trie = (Trie *) malloc (sizeof (Trie)); /** line 120 */
if (UNLIKELY (!trie))
return NULL;
trie->alpha_map = alpha_map_clone (alpha_map);
if (UNLIKELY (!trie->alpha_map))
goto exit_trie_created;
trie->da = da_new ();
if (UNLIKELY (!trie->da))
goto exit_alpha_map_created;
trie->tail = tail_new ();
if (UNLIKELY (!trie->tail))
goto exit_da_created;
trie->is_dirty = TRUE;
return trie;
exit_da_created:
da_free (trie->da);
exit_alpha_map_created:
alpha_map_free (trie->alpha_map);
exit_trie_created:
free (trie);
return NULL;
}
Core was generated by `php test.php'.
Program terminated with signal SIGABRT, Aborted.
#0 0xb76e6cf9 in __kernel_vsyscall ()
(gdb) bt
#0 0xb76e6cf9 in __kernel_vsyscall ()
#1 0xb6ff7050 in __libc_signal_restore_set (set=0xbfb7e890) at ../sysdeps/unix/sysv/linux/nptl-signals.h:79
#2 __GI_raise (sig=6) at ../sysdeps/unix/sysv/linux/raise.c:55
#3 0xb6ff8577 in __GI_abort () at abort.c:89
#4 0xb7032f4f in __libc_message (do_abort=<optimized out>, fmt=<optimized out>)
at ../sysdeps/posix/libc_fatal.c:175
#5 0xb7039b47 in malloc_printerr (action=<optimized out>, str=0xb712b7fa "malloc(): memory corruption",
ptr=<optimized out>, ar_ptr=0xb7181780 <main_arena>) at malloc.c:5046
#6 0xb703bb22 in _int_malloc (av=av@entry=0xb7181780 <main_arena>, bytes=bytes@entry=16) at malloc.c:3509
#7 0xb703d735 in __GI___libc_malloc (bytes=16) at malloc.c:2925
#8 0xb76d5257 in trie_new (alpha_map=0x8174b738) at trie.c:120
#9 0xb76dd561 in zif_datrie_filter_new (execute_data=0xb5013290, return_value=0xb50130d0)
at /home/xiao/Documents/datrie_filter/datrie_filter.c:252
#10 0x802639e4 in ?? ()
#11 0x80253e1a in execute_ex ()
#12 0x802abeae in zend_execute ()
#13 0x8021361d in zend_execute_scripts ()
#14 0x801b0784 in php_execute_script ()
#15 0x802add1d in ?? ()
#16 0x80086fc4 in main ()
If i add full 1-byte range from 0x00 to 0xff. TrieChar 255 appears int the results of trie_state_walkable_chars() or trie_enumerate().
1byte.abm
[0x0,0xff]
trietool 1byte add 12
trietool 1byte add 122
trietool 1byte list
12ÿ -1
122 -1
ru@ru-mi:/usr/local/libdatrie/bin#
I'm trying to make an extension for php to work with your library. With the compiled version of the libdatrie from debian package i have successfully made these functions:
PHP_FUNCTION (trie_new);
PHP_FUNCTION(trie_state_new);
PHP_FUNCTION(trie_state_rewind);
PHP_FUNCTION(trie_store);
PHP_FUNCTION(trie_load);
PHP_FUNCTION(trie_save);
PHP_FUNCTION(trie_state_free);
PHP_FUNCTION(trie_state_walkable_chars);
PHP_FUNCTION(trie_state_walk);
PHP_FUNCTION(trie_state_rewind);
PHP_FUNCTION(trie_state_is_walkable);
PHP_FUNCTION(trie_state_is_single);
PHP_FUNCTION(trie_enumerate);
PHP_FUNCTION(trie_retrieve);
Now i'm trying to make PHP(tail_walk_char) which requires tail.h header. This header is not available in the package. Why?
Found from running make check
:
test_walk.c:78:26: warning: format specifies type 'wint_t' (aka 'int') but the argument has type 'AlphaChar' (aka 'unsigned int') [-Wformat]
printf ("'%lc'", walkables[i]);
~~~ ^~~~~~~~~~~~
%c
This could be fix by changing to %c
instead?
what is wrong here?
topkek@ayylmai MSYS /self/libdatrie
$ cat src/libdatrie-0.2.13/tests/test-suite.log
============================================
libdatrie 0.2.13: tests/test-suite.log
============================================
# TOTAL: 10
# PASS: 3
# SKIP: 0
# XFAIL: 0
# FAIL: 7
# XPASS: 0
# ERROR: 0
.. contents:: :depth: 2
FAIL: test_walk
===============
=> Preparing trie...
Failed to add key 'pool', data 1.
FAIL test_walk.exe (exit status: 1)
FAIL: test_iterator
===================
=> Preparing trie...
=> Adding data to trie...
Failed to add key 'a', data 1.
FAIL test_iterator.exe (exit status: 1)
FAIL: test_store-retrieve
=========================
=> Preparing trie...
=> Adding data to trie...
Failed to add key 'a', data 1.
FAIL test_store-retrieve.exe (exit status: 1)
FAIL: test_file
===============
=> Preparing trie...
Failed to add key 'a', data 1.
FAIL test_file.exe (exit status: 1)
FAIL: test_serialization
========================
=> Preparing trie...
Failed to add key 'a', data 1.
FAIL test_serialization.exe (exit status: 1)
FAIL: test_nonalpha
===================
=> Preparing trie...
=> Adding data to trie...
Failed to add key 'a', data 1.
FAIL test_nonalpha.exe (exit status: 1)
FAIL: test_term_state
=====================
=> Preparing trie...
=> Populating trie with test set...
Failed to add key 'ab', data 1.
FAIL test_term_state.exe (exit status: 1)
7 tests out of 10 failed
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.