1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
libpfxtree
==========
Delwink prefix tree (trie) library
What's this for?
----------------
This was written for use with Delwink's LiberTI encoder to find keywords in
source lines, but it is a fairly standard implementation of the
well-established "trie" structure, also called a prefix tree.
The purpose of a trie structure is to function as an efficient dictionary
registry. New words are added to the dictionary, and the dictionary is searched
one letter at a time to find the quickest route to the end of the desired word,
as opposed to checking string equality for each string in the dictionary which
is slow and inefficient on the CPU. Trie structures can be more memory
efficient that a static string dictionary as well, because any words that share
the same starting characters (prefix) will share the same memory for those
characters. This does come at a cost for dictionaries with words that are
nothing alike, because each character in the dictionary is more than 1 byte (32
bytes each on my implementation) since it must keep track of what characters
are adjacent to it, and this implementation of the structure allows storage of
one integer as data for complete words (used in LiberTI's encoder to determine
which token to replace the keyword with).
Many implementations of this structure exist, but this is Delwink's preferred
implementation since it follows Delwink's standards and development styles.
Build
-----
You'll need an ANSI C compiler and a POSIX build environment. On Debian-based
systems, you can get this with:
# apt install build-essential
libpfxtree uses a simple build process. You can compile it like so:
$ make
Install
-------
After building (see above), you can install the library with this:
# make install
Hacking
-------
Match the style you see in the source code. Do not use spaces for indentation.
To submit a patch, [submit your diff to Delwink][1], or use GitHub's pull
request system.
License
-------
libpfxtree is free software, released under the terms of version 0.5 of the
Copyfree Open Innovation License. You are free to copy, modify, and
redistribute this software and use it for whatever purpose. See
[COPYING](COPYING) for more details.
[1]: mailto:contribute@delwink.com
|
