README.md
1# NetBSD's constant database (cdb) library #
2
3The NetBSD's constant database (cdb) library provides a space efficient
4key-value database based on perfect hashing, thus guaranteeing the O(1)
5lookup time. The database preserves the key order.
6
7This package provides a shared library. Just `make rpm` to build an RPM.
8
9## Algorithm ##
10
11CHM-3: "An optimal algorithm for generating minimal perfect hash functions",
12by Czech, Havas and Majewski in Information Processing Letters, 43(5):256-264, October 1992.
13
14References:
15- http://cmph.sourceforge.net/papers/chm92.pdf
16- http://www.netbsd.org/gallery/presentations/joerg/asiabsdcon2013/hashing.pdf
17
18## Examples ##
19
20The following are the C code fragments to demonstrate the use of libcdb.
21
22To create a cdb:
23
24```c
25#include <cdbw.h>
26...
27
28const char *key = "some-key";
29const char *val = "some-key:some-val";
30struct cdbw *cdb;
31
32if ((cdb = cdbw_open()) == NULL)
33 err(EXIT_FAILURE, "cdbw_open");
34
35if (cdbw_put(cdb, key, strlen(key), val, strlen(val)) == -1)
36 err(EXIT_FAILURE, "cdbw_put");
37
38if (cdbw_output(cdb, fd, "my-cdb", NULL) == -1)
39 err(EXIT_FAILURE, "cdbw_output");
40
41cdbw_close(cdb);
42```
43
44To read a cdb:
45
46```c
47#include <cdbr.h>
48...
49
50const char key[] = "some-key";
51const size_t keylen = sizeof(key) - 1;
52struct cdbr *cdb;
53const void *data;
54size_t len;
55
56if ((cdb = cdbr_open(path, CDBR_DEFAULT)) == NULL)
57 err(EXIT_FAILURE, "cdbr_open");
58
59/*
60 * Perform a lookup. Note that it must be validated that the value
61 * corresponds to our key, e.g. pref_match() illustrates the prefix check
62 * for the example above where the key is a part of the value as a prefix.
63 */
64if (cdbr_find(cdb, key, keylen, &data, &len) == 0 && pref_match(data, key)) {
65 /* Found .. */
66} else {
67 /* Not found .. */
68}
69
70cdbr_close(cdb);
71```
72
73For more details, see cdb(5), cdbr(3) and cdbw(3) manual pages.
74
75## Author ##
76
77This code is derived from software contributed to The NetBSD Foundation
78by Joerg Sonnenberger.
79
80## Packages
81
82Just build the package, install it and link the library using the
83`-lcdb` flag.
84* RPM (tested on RHEL/CentOS 7): `make rpm`
85* DEB (tested on Debian 9): `make deb`
86