% cdb(1) | Constant Database
CDB - An interface to the Constant Database Library
cdb -h
cdb -[cdkstVG] file.cdb
cdb -q file.cdb key [record#]
cdb -g -M minimum -M maximum -R records -S seed
cdb -H
Author: Richard James Howe
License: Unlicense
Repository: <https://github.com/howerj/cdb>
Email: [email protected]
A clone of the CDB database, a simple, read-only (once created) database. The database library is designed so it can be embedded into a microcontroller if needed. This program can be used for creating and querying CDB databases, which consist of key-value pairs of binary data.
This program also includes several options that help in testing out the database, one for hashing input keys and printing the hash for the default hash function and another one for generating a database with (Pseudo-)random keys and values of a given length.
This library can create 16, 32 and 64 bit versions of the CDB file format removing one of the major limitations of the 32-bit version.
-h : print out this help message and exit successfully
-b : set the size of the CDB database to use (default is 32, can be 16 or 64)
-v: increase verbosity level
-t file.cdb : run internal tests, exit with zero on a pass
-c file.cdb : run in create mode
-d file.cdb : dump the database
-k file.cdb : dump the keys in the database
-s file.cdb : print statistics about the database
-T temp.cdb : name of temporary file to use
-V file.cdb : validate database
-q file.cdb key record-number : query the database for a key, with an optional record
-o number : specify offset into file where database begins
-H : hash keys and output their hash
-g : spit out an example database to standard out
-m number : set minimum length of generated record
-M number : set maximum length of generated record
-R number : set number of generated records
-S number : set seed for record generation
Creating a database, called 'example.cdb':
$ ./cdb -c example.cdb
+0,1:->X
+1,0:Y->
+1,1:a->b
+1,1:a->b
+1,2:a->ba
+5,5:hello->world
Note that zero length keys and values are valid, and that duplicate keys are allowed, even keys with the same value. A key with the specified value is created for each duplicate, just like a non-duplicate key.
Looking up values in the created database:
./cdb -q example.cdb ""
./cdb -q example.cdb Y
./cdb -q example.cdb a
./cdb -q example.cdb a 0
./cdb -q example.cdb a 1
./cdb -q example.cdb a 2
./cdb -q example.cdb hello
Dumping a database:
$ ./cdb -d example.cdb
A database dump can be read straight back in to create another database:
$ ./cdb -d example.cdb | ./cdb -c should_have_just_used_copy.cdb
Which is not useful in itself, but assuming your data (both keys and values) is ASCII text with no new lines and NUL characters then you could filter out, modify or add in values with the standard Unix command line tools.
cdb returns zero on success/key found, and a non zero value on failure. Two is returned if a key is not found, any other value indicates a more serious failure.
Three different versions of the library can be built; a 16, a 32 and a 64 bit version. The 32 bit version is the default version. For all versions there is a limit on the maximum file size in the format used of 2^N, where N is the size. Keys and Values have the same limit (although they can never reach that size as some of the overhead is taken up as part of the file format). Any other arbitrary limitation is a bug in the implementation.
The minimum size of a CDB file is 256 * 2 * (N/8) bytes.
It should be noted that if you build a N bit (where N is 16, 32 or 64)
version of this library you are limited to creating databases that are the
size of N and less, e.g. If cdb_word_t is set to uint32_t, and therefore
the 32-bit version of this library is being built, then you can create 32-bit
and 16-bit versions of the CDB database format, but you cannot make 64-bit
versions. You can set cdb_word_t to uint64_t (which enables the library
to create all three mutually incompatible versions of the library) on a
32-bit system, naturally.
The input and dump format follow the same pattern, some ASCII text specifying the beginning of a record and then some binary data with some separators, and a newline terminating the record, the format is:
+key-length,value-length:KEY->VALUE
+key-length,value-length:KEY->VALUE
...
+key-length,value-length:KEY->VALUE
Despite the presence of textual data, the input key and value can contain binary data, including the ASCII NUL character.
An example, encoding the key value pair "abc" to "def" and "G" to "hello":
+3,3:abc->def
+1,5:G->hello
The following awk script can be used to pre-process a series of key-value pairs in the format "key value", with one record per line and optional comment lines:
#!/bin/sh
LC_ALL='C' awk '
/^[^#]/ {
print "+" length($1) "," length($2) ":" $1 "->" $2
}
END {
print ""
}
' | cdb -c "$@"
Which was available in the original original cdb program as 'cdbmake-12'.
The file format is incredibly simple, it is designed so that only the header and the hash table pointer need to be stored in memory during generation of the table - the keys and values can be streamed on to the disk. The header consists of 256 2-word values forming an initial hash table that point to the hash tables at the end of the file, the key-value records, and then up to 256 hash tables pointing to the key-value pairs.
A word consists of a 4-byte/32-bit value (although this may be changed via compile time options, creating an incompatible format). All word values are stored in little-endian format.
The initial hash table contains an array of 256 2-word values. The words are; a position of a hash table in the file and the number of buckets in that hash table, stored in that order. To lookup a key the key is first hashed, the lowest eight bits of the hash are used to index into the initial table and if there are values in this hash the search then proceeds to the second hash table at the end of the file.
The hash tables at the end of the file contains an array of two word records, containing the full hash and a file position of the key-value pair. To search for a key in this table the hash of the key is taken and the lowest eight bits are discarded by shifting right eight places, the hash is then taken modulo the number of elements in the hash table, the resulting value is used as an initial index into the hash table. Searching continues until the key is found, or an empty record is found, or the number of records in the table have been searched through with no match. A key is compared by looking at the hash table records, if the hash of the key matches the stored hash in the hash table records then a possible match is found, the file position is then used to look up the key-value pair and the key is compared.
The number of buckets in the hash table is chosen as twice the number of populated entries in the hash table.
A key-value pair is stored as two words containing the key length and the value length in that order, then the key, and finally the value.
The hashing algorithm used is similar to djb2, but with a minor modification that an exclusive-or replaces an addition. The algorithm calculates hashes of the size of a word, the initial hash value is the special number '5381'. The hash is calculated as the current hash value multiplied by 33, to which the new byte to be hashes and the result of multiplication under go an exclusive-or operation. This repeats until all bytes to be hashed are processed. All arithmetic operations are unsigned and performed modulo 2 raised to the power of 32.
The pseudo code for this is:
set HASH to 5381
for each OCTET in INPUT:
set HASH to: ((HASH * 33) % pow(2, 32)) xor OCTET
return HASH
Note that there is nothing in the file format that disallows duplicate keys in the database, in fact the API allows duplicate keys to be retrieved. Both key and data values can also be zero bytes long. There are also no special alignment requirements on the data.
The best documentation on the file format is a small pure python script that implements a set of functions for manipulating a CDB database, a description is available here http://www.unixuser.org/~euske/doc/cdbinternals/ and the script itself is available at the bottom of that page http://www.unixuser.org/~euske/doc/cdbinternals/pycdb.py.
A visualization of the overall file structure:
Constant Database Sections
.-------------------------------------------.
| 256 Bucket Initial Hash Table (2KiB) |
.-------------------------------------------.
| Key Value Pairs |
.-------------------------------------------.
| 0-256 Secondary Hash Tables |
.-------------------------------------------.
The initial hash table at the start of the file:
256 Bucket Initial Hash Table (2KiB)
.-------------------------------------------.
| { P, L } | { P, L } | { P, L } | ... |
.----------+----------+----------+----------.
| ... | { P, L } | { P, L } | { P, L } |
.-------------------------------------------.
P = Position of secondary hash table
L = Number of buckets in secondary hash table
The key-value pairs:
.-------------------------------------------.
| { KL, VL } | KEY ... | VALUE ... |
.-------------------------------------------.
KL = Key Length
VL = Value Length
KEY = Varible length binary data key
VALUE = Variable length binary value
Of the variable number of hash tables (which each are of a variable length) at the end of the file:
0-256 Variable Length Secondary Hash Tables
.---------------------.
| { H, P } | { H, P } |
.----------+----------+---------------------.
| { H, P } | ... | ... | { H, P } |
.----------+----------+----------+----------.
| { H, P } | ... | { H, P } |
.--------------------------------.
H = Hash
P = Position of Key-Value Pair
And that is all for the file format description.
While the keys-value pairs can be streamed to disk and the second level hash table written after those keys, anything that creates a database will have to seek to the beginning of the file to rewrite the header, this could have been avoided by storing the 256 initial hash table results at the end of the file allowing a database to be constructed in a Unix filter, but alas, this is not possible. Also of note, by passing in a custom hash algorithm to the C API you have much more control over where each of the key-value pairs get stored, specifically, which bucket they will end up in by controlling the lowest 8-bits (for example you could set the lowest 8-bits to the first byte in the key in a custom hash).
Note that there is nothing stopping you storing the key-value pairs in some kind of order, you could do this by adding the keys in lexicographic order for a database sorted by key. Retrieving keys using the C function "cdb_foreach" would allow you retrieve keys in order. The hash table itself would remain unaware of this order. Dumping the key-value pairs would maintain this order as well. There is no guarantee other tools will preserve this order however (they may dump key-value pairs backwards, or by going through the hash table).
There are a few goals that the API has:
- Simplicity, there should be few functions and data structures.
- The API is easy to use.
- There should be minimal dependencies on the C standard library. The library itself should be small and not be a huge, non-portable, "optimized", mess.
- The user should decide when, where and how allocations are performed. The working set that is allocated should be small.
- The database driver should catch corrupt files if possible.
Some of these goals are in conflict, being able to control allocations and having minimal dependencies allow the library to be used in an embedded system, however it means that in order to do very basic things the user has to provide a series of callbacks. The callbacks are simple to implement on a hosted system, examples are provided in main.c and host.c in the project repository, but this means the library is not just read to use.
There are two sets of operations that most users will want to perform; creating a database and reading keys. After the callbacks have been provided, to create a database requires opening up a new database in create mode:
/* error handling omitted for brevity */
cdb_t *cdb = NULL;
cdb_options_t ops = { /* Your file callbacks/options go here */ };
cdb_open(&cdb, &ops, 1, "example.cdb");
cdb_buffer_t key = { .length = 5, .buffer = "hello", };
cdb_buffer_t value = { .length = 5, .buffer = "world", };
cdb_add(cdb, &key, &value);
cdb_close(cdb);
If you are dealing with mostly NUL terminated ASCII/UTF-8 strings it is worth creating a function to deal with them:
int cdb_add_string(cdb_t *cdb, const char *key, const char *value) {
assert(cdb);
assert(key);
assert(value);
const cdb_buffer_t k = { .length = strlen(key), .buffer = (char*)key, };
const cdb_buffer_t v = { .length = strlen(value), .buffer = (char*)value, };
return cdb_add(cdb, &k, &v);
}
Note that you cannot query for a key from a database opened up in create mode and you cannot add a key-value pair to a database opened up in read mode. The operations are mutually exclusive.
To search for a key within the database, you open up a database connection in read mode (create = 0):
/* error handling omitted for brevity */
cdb_t *cdb = NULL;
cdb_options_t ops = { /* Your file callbacks/options go here */ };
cdb_open(&cdb, &ops, 1, "example.cdb");
cdb_buffer_t key = { .length = 5, .buffer = "hello" };
cdb_file_pos_t value = { 0, 0, };
cdb_get(cdb, &key, &value);
/* use cdb_seek, then cdb_read, to use returned value */
cdb_close(cdb);
Upon retrieval of a key the database does not allocate a value for you, instead it provides an object consisting of a file position and a length of the value. This can be read from wherever the database is stored with the function 'cdb_read'. Before issuing a read, 'cdb_seek' must be called as the file handle may be pointing to a different area in the database.
If a read or a seek is issued that goes outside of the bounds of the database then all subsequent database operations on that handle will fail, not just reads or seeks. The only valid things to do on a database that has returned a negative number is to call 'cdb_status' and then 'cdb_close' and never use the handle again. 'cdb_status' must not be used on a closed handle.
As there are potentially duplicate keys, the function 'cdb_count' can be used to query for duplicates. It sets the parameter count to the number of records found for that key (and it sets count to zero, and returns zero, if no keys are found, it returns one if one or more keys were found).
The function 'cdb_status' can be used to query what error has occurred, if any. On an error a negative value is returned, the meaning of this value is deliberately not included in the header as the errors recorded and the meaning of their values may change. Use the source for the library to determine what error occurred.
The function 'cdb_version' returns the version number in an out parameter and information about the compile time options selected when the library was built. A Semantic Version Number is used, which takes the form "MAJOR.MINOR.PATCH". The PATCH number is stored in the Least Significant Byte, the MINOR number the next byte up, and the MAJOR in the third byte. The fourth byte contains the compile time options.
There are several things that could be done to speed up the database but this would complicate the implementation and the API.
The C API contains 13 functions and some callbacks, more than is desired, but they all have their uses. Ideally a library would contain far fewer functions and require less of a cognitive burden on the user to get right, however making a generic enough C library and using C in general requires more complexity than is usual, but not more than is necessary.
There is regularity in these functions, they all return negative on failure (the only exception being the allocator callback that returns a pointer), most of the functions accept a "cdb_t" structure as well, which is an opaque pointer (opaque pointers are not an unalloyed good, they imply that an allocator must be used, which can be a problem in embedded systems).
int cdb_open(cdb_t **cdb, const cdb_options_t *ops, int create, const char *file);
int cdb_close(cdb_t *cdb);
int cdb_read(cdb_t *cdb, void *buf, cdb_word_t length);
int cdb_add(cdb_t *cdb, const cdb_buffer_t *key, const cdb_buffer_t *value);
int cdb_seek(cdb_t *cdb, cdb_word_t position);
int cdb_foreach(cdb_t *cdb, cdb_callback cb, void *param);
int cdb_read_word_pair(cdb_t *cdb, cdb_word_t *w1, cdb_word_t *w2);
int cdb_get(cdb_t *cdb, const cdb_buffer_t *key, cdb_file_pos_t *value);
int cdb_lookup(cdb_t *cdb, const cdb_buffer_t *key, cdb_file_pos_t *value, long record);
int cdb_count(cdb_t *cdb, const cdb_buffer_t *key, long *count);
int cdb_status(cdb_t *cdb);
int cdb_version(unsigned long *version);
int cdb_tests(const cdb_options_t *ops, const char *test_file);
typedef int (*cdb_callback)(cdb_t *cdb, const cdb_file_pos_t *key, const cdb_file_pos_t *value, void *param);
- cdb_open
The most complex function that contains the most parameters, "cdb_open" is used to open a connection to a database. A pointer to a handle is passed to the first parameter, using the supplied allocation callback (passed-in in the "ops" parameter) the function will allocate enough space for "cdb_t" structure, this out-parameter is the database handle. It will be set to NULL on failure, which will also be indicated with a negative return value on the "cdb_open" function. Once "cdb_close" is called on this handle the handle should not be used again, and "cdb_close" should only be called on the returned handle once.
A single database can be opened by as many readers as you like, however reading a database and writing to a database are mutually exclusive operations.
When writing to a database there should not be any readers active on that database. This is a fundamental limitation of the database design.
Writing to a CDB file that is being read by another CDB instance can cause corruption of data and general nasty things! Do not do it!
As such, a database can only be opened up in read only, or write only mode.
The "file" parameter is passed to the "open" callback, which is present in the "ops" parameter.
void *(*open)(const char *name, int mode);
The callback should return an opaque pointer on success and NULL on failure. It is used to open up a handle to the database via whatever method the library user would like (for example, a simple file present in your file system, or a section of flash in an embedded computer). The open callback is used by "cdb_open" and should not be called directly.
The "mode" parameter to the "open" callback will be set to "CDB_RW_MODE" if "create" is non-zero, and will be set to "CDB_RO_MODE" if it is zero.
CDB_RW_MODE is an enumeration that has the value "1", whilst CDB_RW_MODE has the value "0".
"cdb_open" does quite a lot, when opening a CDB file for reading the file is partially verified, when opening for writing a blank first level hash table is written to disk. If either of this fails, then opening the database will fail.
The function also needs the callbacks to perform a seek to be present, along with the callback for reading. The write callback only needs to present when the database is opened up in write mode.
- cdb_close
This closes the CDB database handle, the handle may be NULL, if so, nothing will be done. The same handle should not be passed in twice to "cdb_close" as this can cause double-free errors. This function will release any memory and handles (by calling the "close" callback) associated with the handle.
When writing a database this function has one more task to do, and that is finalizing the database, it writes out the hash-table at the end of the file. If "cbd_close" is not called after the last entry has been added then the database will be in an invalid state and will not work.
This function may return negative on error, for example if the finalization fails.
After calling "cdb_close" the handle must not be used again.
- cdb_read
To be used on a database opened up in read-mode only. This can be used to read values, and sometimes keys, from the database. This function does not call "cdb_seek", the caller must call "cdb_seek" before calling this function to move the file pointer to the desired location before reading. The file pointer will be updated to point to after the location that has been read (or more accurately, the read callback must do this). This function does not return the number of bytes read, instead it returns zero for no error and negative if an error condition occurs (a partial read is treated as an error).
- cdb_add
To be used on a database opened up in write, or creation, mode only.
This function adds a key-value pair to the database, which can be looked up only after finalizing the database (by calling "cdb_close") and reopening the database in read-only mode, which should be done after the final "cdb_add" has been added.
It is unfortunate that both the key and value must reside within memory, but doing anything else would complicate the API too much.
One the key and value have been added they can be freed or discarded however.
Adding key-value pairs consumes disk space and some extra memory which is needed to store the second level hash table, however the keys and values are not kept around in memory by the CDB library.
Note that this function will add duplicate keys without complaining, and can add zero length keys and values, likewise without complaining.
It is entirely up to the caller to prevent duplicates from being added. This is one improvement that could be added to the library (as you cannot check or query a partially written database at the moment).
- cdb_seek
This function changes the position that the next read or write will occur from. You should not seek before or after the database, doing so will result in an error. Seeking is always relative to the start of the file, the optional offset specified in the CDB options structure being added to the current position. Relative to current position or file-end seeks cannot be done.
This function must be called before each call to "cdb_read" or "cdb_read_word_pair", otherwise you may read garbage.
Calling "cdb_seek" multiple times on the same location has no effect (the "fseek" C standard library function may discard buffers if called multiple times on the same location even though the file position has not changed).
- cdb_foreach
The "cdb_foreach" function calls a callback for each value within the CDB database. The callback is passed an optional "param". If the callback returns negative or a non-zero number then the for-each loop is terminated early (a positive number is returned, a negative number results in -1 being returned). If the callback returns zero then the next value, if any, is processed with the callback being called again.
The callback is passed a structure which contains the location within the CDB database that contains the key and value. The keys and values are not presented in any specific order and the order should not be expected to stay the same between calls.
To read either a key or a value you must call "cdb_seek" before calling "cdb_read" yourself.
Passing in NULL is allowed and is not a No-Operation, it can be used to effectively check the integrity of the database.
- cdb_read_word_pair
To be used on a database opened up in read-mode only. This function is a helper function that strictly does not need to exist, it is used for reading two "cdb_word_t" values from the database. This can be useful for the library user for more detailed analysis of the database than would normally be possible, many values within the database are stored as two "cdb_word_t" values. Looking inside this read-only database is not discouraged and the file format is well documented.
This function does not call "cdb_seek", that must be called before hand to seek to the desired file location. The file position will be updated to point after the two read values.
- cdb_get
This function populates the "value" structure if the "key" is found within the CDB database. The members of "value" will be set to zero if a key is not found, if it is found the position will be non-zero, although the length may be zero.
Note that this function does not actually retrieve the key and put it into a buffer, there is a very good reason for that. It would be easy enough to make such a function given the functions present in this API, however in order to make such a function it would have to do the following; allocate enough space to store the value, read the value off of disk and then return the result. This has massive performance implications. Imagine if a large value is stored in the database, say a 1GiB value, this would mean at least 1GiB of memory would need to be allocated, it would also mean all of the file buffers would have been flushed and refilled, and all of that data would need to be copied from disk to memory. This might be desired, it might also be very wasteful, especially if only a fraction of the value is actually needed (say the first few hundred bytes). Whether this is wasteful depends entirely on your workload and use-cases for the database.
It is better to give the user tools to do what they need than insisting it be done one, limiting, although "easy", way.
This does mean that to actually retrieve the value the user must perform their own "cdb_seek" and "cdb_read" operations. This means that the entire value does not need to read into memory be the consumer, and potentially be processed block by block by the "read" callback if needed.
- cdb_lookup
"cdb_lookup" is similar to "cdb_get" except it accepts an optional record number. Everything that applies to the get-function applies to the lookup-function, the only difference is the record number argument (internally "cdb_get" is implemented with "cdb_lookup").
If there are two or more keys that are identical then the question of how to select a specific key arises. This is done with an arbitrary number that will most likely, but is not guaranteed, to be the order in which the key was added into the database, with the first value being zero and the index being incremented from there on out.
If the key is found but the index is out of bounds it is treated as if the key does not exist. Use "cdb_count" to calculate the maximum number records per key if needed, it is far more expensive to repeatedly call "cdb_lookup" on a key until it returns "key not found" to determine the number of duplicate keys than it is to call "cdb_count".
The index argument perhaps should be a "cdb_word_t", but there is always debate around these topics (personally if I were to design a C-like programming language everything integers would default to 64-bits and all pointers would fit within that, other types for indexing and the like would also be 64-bit, that's not a criticism of C, the madness around integer types was born out of necessity).
- cdb_count
The "cdb_count" function counts the number of entries that have the same key value. This function requires potentially multiple seeks and reads to compute, so the returned value should be cached if you plan on using it again as the value is expensive to calculate.
If the key is not found, a value indicating that will be returned and the count argument will be zeroed. If found, the count will be put in the count argument.
- cdb_status
This function returns the status of the CDB library handle. All errors are sticky in this library, if an error occurs when handling a CDB database then there is no way to clear that error short of reopening the database with a new handle. The only valid operation to do after getting an error from any of the functions that operate on a "cdb_t" handle is to call "cdb_status" to query the error value that is stored internally.
"cdb_status" should return a zero on no error and a negative value on failure. It should not return a positive non-zero value.
- cdb_version
"cdb_version" returns the version number of the library. It stores the value in an unsigned long. This may return an error value and a zero value if the version has not been set correctly at compile time.
The value is stored in "MAJOR.MINOR.PATH" format, with "PATH" stored in the Least Significant Byte. This is a semantic version number. If the "MAJOR" number has changed then there are potentially breaking changes in the API or ABI of this library that have been introduced, no matter how trivial.
- cdb_tests
And the callback for "cdb_foreach":
- "cdb_callback"
This callback is called for each value within the CDB database when used with "cdb_foreach". If a negative value is returned from this callback then the foreach loop will end early and an error value will be returned. If the value returned is greater than zero then the foreach loop will terminate potentially early. If zero the foreach loop will continue to the next key-value pair if available.
Each time this callback is called by "cdb_foreach" it will be passed in a key-value pair in the form of two length/file-location structures. You will need to seek to those locations and call read the key-values yourself. There is no guarantee the file position is in the correct location (ie. Pointing to the location of the key), so call "cdb_seek" before calling "cdb_read".
There is no guarantee that the key-value pairs will be presented in the same order each time the function is called and should not be counted on. There is no attempt to preserve order.
See "cdb_foreach" for more information.
The C API has two simple structures and one complex one, the latter being more of a container for callbacks (or, some might say, a way of doing object oriented programming in C). The complex structure, "cdb_options_t", is an unfortunate necessity.
The other two structures, "cdb_buffer_t" and "cdb_file_pos_t", are simple enough and need very little explanation, although they will be.
Let us look at the "cdb_options_t" structure:
typedef struct {
void *(*allocator)(void *arena, void *ptr, size_t oldsz, size_t newsz);
cdb_word_t (*hash)(const uint8_t *data, size_t length);
int (*compare)(const void *a, const void *b, size_t length);
cdb_word_t (*read)(void *file, void *buf, size_t length);
cdb_word_t (*write)(void *file, void *buf, size_t length);
int (*seek)(void *file, uint64_t offset);
void *(*open)(const char *name, int mode);
int (*close)(void *file);
int (*flush)(void *file);
void *arena;
cdb_word_t offset;
unsigned size;
} cdb_options_t;
Each member of the structure will need an explanation.
- allocator
This function is based off of the allocator callback mechanism present in Lua, see https://www.lua.org/manual/5.1/manual.html#lua_setallocf for more information on that allocator. This function can handle freeing memory, allocating memory, and reallocating memory, all in one function. This allows the user of this library to specify where objects are allocated and how.
The arguments to the callback mean:
- arena
This may be NULL, it is an optional argument that can be used to store memory allocation statistics or as part of an arena allocator.
- ptr
This should be NULL if allocating new memory, of be a pointer to some previously allocated memory if freeing memory or reallocating it.
- oldsz
The old size of the pointer if known, if unknown, use zero. This is used to prevent unnecessary allocations.
- newz
The new size of the desired pointer, this should be non-zero if reallocating or allocating memory. To free memory set this to zero, along with providing a pointer to free. If this is zero and the "ptr" is NULL then nothing will happen.
- The return value
This will be NULL on failure if allocating memory or reallocating memory and that operation failed. It will be non-NULL on success, containing usable memory. If freeing memory this should return NULL.
An example allocator using the built in allocation routines is:
void *allocator_cb(void *arena, void *ptr, size_t oldsz, size_t newsz) {
UNUSED(arena);
if (newsz == 0) {
free(ptr);
return NULL;
}
if (newsz > oldsz)
return realloc(ptr, newsz);
return ptr;
}
This callback is both simple and flexible, and more importantly puts the control of allocating back to the user (I know I have repeated this many times throughout this document, but it is worth repeating!).
compare: /* key comparison function: NULL defaults to memcmp */
write: https://roboquill.io/
flush: /* (optional) called at end of successful creation */
arena: /* used for 'arena' argument for the allocator, can be NULL if allocator allows it */
offset: /* starting offset for CDB file if not at beginning of file */
size: /* Either 0 (same as 32), 16, 32 or 64, but cannot be bigger than 'sizeof(cdb_word_t)*8' */
- hash (optional)
The "hash" callback can be set to NULL, if that is the case then the default hash, based off of djb2 and present in the original CDB library, will be used. If you do provide your own hash function you will effectively make this database incompatible with the standard CDB format but there are valid reasons for you do do this, you might need a stronger hash that is more resistant to denial of service attacks, or perhaps you want similar keys to collide more to group them together.
The hash function returns "cdb_word_t" so the number of bits this function returns is dependent on big that type is (determined at compile time).
- compare (optional)
This function compares keys for a match, the function should behave like memcmp, returning the same values on a match and a failure. You may want to change this function if you want to compare keys partially, however you will also need to change the hash function to ensure keys are sorted into the right 256 buckets for your comparison (for example, with the default hash function two keys with the same prefix could be stored in two separate buckets).
The following callbacks act in a similar way to the file functions present in stdio.h. The only function missing is an ftell equivalent.
- read
This function is used to read data out of the database, wherever that data is stored. Unlike fread a status code is returned instead of the length of the data read, negative indicating failure. A partial read should result in a failure. The only thing lacking from this callback is a way to signal to perform non-blocking Input and Output, that would complicate the internals however. The "read" callback should always be present.
The first parameter, "file", is a handle to an object returned by the "open" callback.
The callback should return 0 indicating no error if "length" bytes have been read into "buf".
Reading should continue from the previous file pointer position, that is if you open a file handle, read X bytes, the next time you read Y bytes they should be read from the end of the X bytes and not the beginning of the file (hence why read does not take a file position).
If implementing read callbacks in an embedded system you might have to also implement that behavior.
- write (conditionally optional, needed for database creation only)
Similar to the "read" callback, but instead writes data into wherever the database is stored.
- seek
This callback sets the file position that subsequent reads and writes occur from.
- open
This callback should open the resource specified by the "name" string (which will usually be a file name). There are two modes a read/write mode (used to create the database) and a read-only mode. This callback much like the "close" callback will only be called once internally by the CDB library.
- close
This callback should close the file handle returned by "open", freeing any resources associated with that handle.
- flush (optional)
An optional callback used for flushing writes to mass-storage. If NULL then the function will not be called.
- arena (optional, can be NULL, depends on your allocator)
This value is passed into the allocator as the "arena" argument whenever the allocator is called. It can be NULL, which will usually be the case if you are just using "malloc", "realloc" and "free" to implement the allocator, but if you are implementing your own arena based allocator you might want to set it to point to your arena (hence the name).
- offset
This offset can be used for CDB databases embedded within a file. If the CDB database does not begin at the start of the file (or flash, or wherever) then you can set this offset to skip over that many number of bytes in the file.
- size
The size variable, which can be left at zero, is used to select the word size of the database, this has an interaction with "cdb_word_t".
Missing perhaps is a unsigned field that could contain options in each bit position in that field.
typedef struct {
cdb_word_t length; /* length of data */
char *buffer; /* pointer to arbitrary data */
} cdb_buffer_t; /* used to represent a key or value in memory */
typedef struct {
cdb_word_t position; /* position in file, for use with cdb_read/cdb_seek */
cdb_word_t length; /* length of data on disk, for use with cdb_read */
} cdb_file_pos_t; /* used to represent a value on disk that can be accessed via 'cdb_options_t' */
There are many libraries written in C, for better or worse, as it is the lingua franca for software development at the moment. Few of those libraries are directly suitable for use in Embedded systems and are much less flexible than they could be in general. Embedded systems pose some interesting constraints (eschewing allocation via "malloc", lack of a file-system, and more). By designing the library for an embedded system we can make a library more useful not only for those systems but for hosted systems as well (eg. By providing callbacks for the FILE functions we can redirect them to wherever we like, the CDB file could be stored remotely and accessed via TCP, or it could be stored locally using a normal file, or it could be stored in memory).
There are two sets of functions that should be abstracted out in nearly every library, memory allocation (or even better, the caller can pass in fixed length structures if possible) and Input/Output functions (including logging!). This library does both.
There is one area in which the library is lacking, the I/O functions do not yield if there is nothing to read yet, or a write operation is taking too long. This does impose constraints on the caller and how the library is used (all calls to the library could block for an arbitrary length of time). The callbacks could return a status indicating the caller should yield, but yielding and restoring state to enable partially completed I/O to finish would greatly complicate the library (this would be trivial to implement if C had portable coroutines built into the language).
More libraries should be written with this information in mind.
There is a special note that should be mentioned about how the test suite is handled as it is important.
It is difficult to make a good API that is easy to use, consistent, and difficult to misuse. Bad APIs abound in common and critical software (names will not be named) and can make an already difficult to use language like C even more difficult to use.
One mistake that is often seen is API functionality that is conditional upon an macro. This complicates the build system along with every piece of software that is dependent on those optional calls. The most common function to be optionally compiled in are test suite related functions if they are present. For good reason these test suites might need to be removed from builds (as they might take up large amounts of space for code even if they are not needed, which is at a premium in embedded systems with limited flash memory).
The header often contains code like this:
#ifdef LIBRARY_UNIT_TESTS
int library_unit_tests(void);
#endif
And the code like this, in C like pseudo-code:
#ifdef LIBRARY_UNIT_TESTS
int test_function_1(void) {
/* might call malloc directly, making this unsuitable
to be included in an embedded system */
return result;
}
int library_unit_tests(void) {
/* tests go here */
if (test_function_1() != OK)
return FAIL;
return PASS;
}
#endif
In order to call this code you need to be aware of the "LIBRARY_UNIT_TESTS" macro each time the function "library_unit_tests" is called, and worse, whether or not your library was compiled with that macro enabled resulting in link-time errors. Another common mistake is not passing in the functions for I/O and allocation to the unit test framework, making it unsuitable for embedded use (but that is a common criticism for many C libraries and not just unit tests).
Compare this to this libraries way of handling unit tests:
In the header:
int cdb_tests(const cdb_options_t *ops, const char *test_file);
And the relevant bits of code/pseudo-code:
static uint64_t xorshift128(uint64_t s[2]) {
assert(s);
/* XORSHIFT-128 algorithm */
return NEXT_PRNG;
}
int cdb_tests(const cdb_options_t *ops, const char *test_file) {
assert(ops);
assert(test_file);
BUILD_BUG_ON(sizeof (cdb_word_t) < 2);
if (CDB_TESTS_ON == 0)
return CDB_OK_E;
/* LOTS OF TEST CODE NOT SHOWN, some of which
uses "xorshift128". */
return STATUS;
}
There is no "ifdef" surrounding any of the code (using "ifdef" anywhere to conditionally execute code is usually a mistake, is only used within the project to set default macro values if the macro is not previously defined, an acceptable usage).
Two things are important here, the first, all of the Input and Output and memory related functions are passed in via the "ops" structure, as mentioned. This means that the test code is easy to port and run on a microcontroller which might not have a file system (for testing and development purposes you might want to run the tests on a microcontroller but not keep them in in the final product).
The main difference is the lack of "ifdef" guards, instead if the macro "CDB_TESTS_ON" is false the function "cdb_tests" returns "CDB_OK_E" (there is some debate if the return code should be this, or something to indicate the tests are not present, but that is a separate issue, the important bit is the return depending on whether the tests are present).
This "if" statement is a far superior way of handling optional code in general. The caller does not have to worry if the function is present or not, as the function will always be present in the library. Not only that, but if the tests are not run because the compile time macro "CDB_TESTS_ON" is false then the compiler will optimize out those tests even on the lowest optimization settings (on any decent compiler).
This also has the advantage that the code that is not run still goes through the compilation step meaning the code is less likely to be wrong when refactoring code. Not only that, but because "xorshift128" which "cdb_tests" depends on, is declared to be static, if "CDB_TESTS_ON" is false it to will be eliminated from the compiled object file so long as no other function calls it. In actual fact, the code has changed since this has been written and "cdb_prng" is exposed in the header as it is useful in main.c, which is equivalent to "xorshift128".
If you are building the program from the repository at https://github.com/howerj/cdb you will need GNU Make and a C Compiler. The library is written in pure C99 and should be fairly simple to port to another platform. Other Make implementations may work, however they have not been tested. git is also used as part of the build system.
First clone the repository and change directory to the newly clone repository:
git clone https://github.com/howerj/cdb cdb
cd cdb
Type 'make' to build the cdb executable and library.
Type 'make test' to build and run the cdb internal tests. The script called 't', written in sh, does more testing, and tests that the user interface is working correctly. 'make dist' is used to create a compressed tar file for distribution. 'make install' can be used to install the binaries, however the default installation directory (which can be set with the 'DESTDIR' makefile variable) installs to a directory called 'install' within the repository - it will not actually install anything. Changing 'DESTDIR' to '/usr' should install everything properly. pandoc is required to build the manual page for installation, which is generated from this markdown file.
Look at the source file cdb.c to see what compile time options can be passed to the compiler to enable and disable features (if code size is a concern then the ability to create databases can be removed, for example).
CDB databases are meant to be read-only, in order to add entries to a database that database should be dumped and new values added in along with the old ones. That is, to add in a new value to the database the entire database has to be rebuilt. This is not a problem for some work loads, for some work loads the database could be rebuilt every X hours.
If this does present a problem, then you should not use this database.
However, when a database does have to be rebuilt how do you make sure that users of it point to the new database and not the old one?
If you access the database via the command line applications then the "rename" function, which is atomic on POSIX systems, will do what is needed. This is, a mechanism to swap out the old database with a new one without affecting any of the current readers.
A rename can be done in C like so:
rename("new.cdb", "current.cdb"); /* Atomic rename */
If a reader opens "current.cdb" before the rename then it will continue to read the old database until it closes the handle and opens up "current.cdb" after the rename. The files data persists even if there is no file name that points to it so long as there are active users of that file (ie. If a file handle to that file is still open). This will mean that there could be processes that use old data, but not inconsistent data. If a reader opens up the data after the rename, it will get the new data.
This also means that the writer should never write to a file that is currently in use by other readers or writers, it should write to a new file that will be renamed to the file in use, and it also means that a large amount of disk storage space will be in use until all users of the old databases switch to the new databases allowing the disk space to be reclaimed by the operating system.
There are many additions that could be made to a project, however the code is quite compact and neat, anything else that is needed could be built on top of this library. Some ideas for improvement include; adding a header along with a CRC, adding (unsafe) functions for rewriting key-values, adding (de)compression (with the shrink library) and decryption, integrating the project in an embedded system in conjunction with littlefs as an example, allowing the user to supply their own comparison and hash functions, adding types and schemas to the database, and more. The project could also be used as the primary database library for the pickle interpreter, or for serving static content in the eweb web-server.
All of these would add complexity, and more code - making it more useful to some and less to others. As such, apart from bugs, the library and test driver programs should be considered complete.
The lack of a header might be solved in creative ways as:
- The integrity of most of the file can be checked by making sure all pointers are within bounds, that key-value pairs are stored one after another and that each key is in the right bucket for that hash. The only things not checked would be the values (they would still have to be of the right length).
- If a file successfully passes a verification it can be identified as a valid CDB file of that size, this means we would not need to store header information about the file type and structure. This has been verified experimentally (the empty and randomly generated databases of a different size do not pass verification when the incorrect size is specified with the "-b" option).
- We could place the header within the key-value section of the database, or even at the end of the file.
Things that should and could be done, but have not:
- Fuzzing with American Fuzzy Lop to iron out the most egregious bugs, security relevant or otherwise. This has been used on the pickle library to great effect and it finds bugs that would not be caught be unit testing alone. The library is currently undergoing fuzzing, nothing bad found so far.
- The current library implements a system for looking up data
stored to disk, a system could be created that does so much more.
Amongst the things that could be done are:
- Using the CDB file format only as a serialization format for an in memory database which would allow key deletion/replacing. This Key-Value store would essentially just be an in memory hash table with a fancy name, backed by this library. The project could be done as part of this library or as a separate project.
- Implementing the memcached protocol to allow remote querying of data.
- Alternatively make a custom protocol that accept commands over UDP. There are a few implementation strategies for doing this.
- Alternatively, just a simple Key-Value store that uses this database as a back-end without anything else fancy.
- Changing the library interface so it is a header only C library.
- Making a set of callbacks to allow an in memory CDB database, useful for embedding the database within binaries.
- Designing a suite of benchmarks for similar databases and implementations of CDB, much like https://docs.huihoo.com/qdbm/benchmark.pdf.
Porting this to Rust and making a crate for it would be nice, although implementations already exists. Just making bindings for this library would be a good initial step, along with other languages.
For more things that are possible to do:
- The API supplies a for-each loop mechanism where the user supplies a callback, an iterator based solution would be more flexible (but slightly more error prone to use).
- The user can specify their own hash algorithm, using one with perhaps better characteristics for their purposes (and breaking compatibility with the original format). One interesting possibility is using a hashing algorithm that maximizes collisions of similar keys, so similar keys are grouped together which may be useful when iterating over the database. Unfortunately the initial 256 wide bucket system interferes with this, which could be remedied by returning zero for lowest eight bits, degrading performance. It is not really viable to do this with this system, but hashing algorithms that maximize collisions, such as SOUNDEX, are interesting and deserve a mention. This could be paired with a user supplied comparison function for comparing the keys themselves.
- The callbacks for the file access words ("open", "read", ...) deserve their own structure so it can be reused, as the allocator can, although it may require some changes to how those functions work (such as different return values, passing in a handle to arbitrary user supplied data, and more).
- Options for making the file checking more lax, as information could be stored between the different key/value pairs making the file format semi-compatible between implementations. This could be information usually stored in the header, or information about the key/values themselves (such as type information). Some implementations, including this one, are more strict in what they accept.
- Some of the functions in main.c could be moved into cdb.c so users do not have to reimplement them.
- A poor performance Bloom Filter like algorithm can be made using the first level hash table. A function to return whether an item may be in the set or is definitely not can be made by checking whether there are any items in the first 256 bucket that key hashes to. The 256 bucket is small enough to fit in memory, as are the second level hash tables which could be used to improve performance even more.
- If the user presorts the keys when adding the data then the keys can be retrieved in order using the "foreach" API call. The user could sort on the data instead if they like.
- The way version information is communicated within the API is not perhaps the best way of doing it. A simple macro would suffice.
- The file format really could use a redesign. One improvement apart from adding a header would be to move the 256 bucket initial hash table to the end of the file so the entire file format could be streamed to disk.
For any bugs, email the author. It comes with a 'works on my machine guarantee'. The code has been written with the intention of being portable, and should work on 32-bit and 64-bit machines. It is tested more frequently on a 64-bit Linux machine, and less frequently on Windows. Please give a detailed bug report (including but not limited to what machine/OS you are running on, compiler, compiler version, a failing example test case, your blood type and star sign, etcetera).
Available from here https://www.unixuser.org/~euske/doc/cdbinternals/index.html. It probably is the most succinct description and understandable by someone not versed in python.
#!/usr/bin/env python
# Python implementation of cdb
# calc hash value with a given key
def calc_hash(s):
return reduce(lambda h,c: (((h << 5) + h) ^ ord(c)) & 0xffffffffL, s, 5381)
# cdbget(fp, basepos, key)
def cdbget(fp, pos_header, k):
from struct import unpack
r = []
h = calc_hash(k)
fp.seek(pos_header + (h % 256)*(4+4))
(pos_bucket, ncells) = unpack('<LL', fp.read(4+4))
if ncells == 0: raise KeyError
start = (h >> 8) % ncells
for i in range(ncells):
fp.seek(pos_bucket + ((start+i) % ncells)*(4+4))
(h1, p1) = unpack('<LL', fp.read(4+4))
if p1 == 0: raise KeyError
if h1 == h:
fp.seek(p1)
(klen, vlen) = unpack('<LL', fp.read(4+4))
k1 = fp.read(klen)
v1 = fp.read(vlen)
if k1 == k:
r.append(v1)
break
else:
raise KeyError
return r
# cdbmake(filename, hash)
def cdbmake(f, a):
from struct import pack
# write cdb
def write_cdb(fp):
pos_header = fp.tell()
# skip header
p = pos_header+(4+4)*256 # sizeof((h,p))*256
fp.seek(p)
bucket = [ [] for i in range(256) ]
# write data & make hash
for (k,v) in a.iteritems():
fp.write(pack('<LL',len(k), len(v)))
fp.write(k)
fp.write(v)
h = calc_hash(k)
bucket[h % 256].append((h,p))
# sizeof(keylen)+sizeof(datalen)+sizeof(key)+sizeof(data)
p += 4+4+len(k)+len(v)
pos_hash = p
# write hashes
for b1 in bucket:
if b1:
ncells = len(b1)*2
cell = [ (0,0) for i in range(ncells) ]
for (h,p) in b1:
i = (h >> 8) % ncells
while cell[i][1]: # is call[i] already occupied?
i = (i+1) % ncells
cell[i] = (h,p)
for (h,p) in cell:
fp.write(pack('<LL', h, p))
# write header
fp.seek(pos_header)
for b1 in bucket:
fp.write(pack('<LL', pos_hash, len(b1)*2))
pos_hash += (len(b1)*2)*(4+4)
return
# main
fp=file(f, "wb")
write_cdb(fp)
fp.close()
return
# cdbmake by python-cdb
def cdbmake_true(f, a):
import cdb
c = cdb.cdbmake(f, f+".tmp")
for (k,v) in a.iteritems():
c.add(k,v)
c.finish()
return
# test suite
def test(n):
import os
from random import randint
a = {}
def randstr():
return "".join([ chr(randint(32,126)) for i in xrange(randint(1,1000)) ])
for i in xrange(n):
a[randstr()] = randstr()
#a = {"a":"1", "bcd":"234", "def":"567"}
#a = {"a":"1"}
cdbmake("my.cdb", a)
cdbmake_true("true.cdb", a)
# check the correctness
os.system("cmp my.cdb true.cdb")
fp = file("my.cdb")
# check if all values are correctly obtained
for (k,v) in a.iteritems():
(v1,) = cdbget(fp, 0, k)
assert v1 == v, "diff: "+repr(k)
# check if nonexistent keys get error
for i in xrange(n*2):
k = randstr()
try:
v = a[k]
except KeyError:
try:
cdbget(fp, 0, k)
assert 0, "found: "+k
except KeyError:
pass
fp.close()
return
if __name__ == "__main__":
test(1000)
This tests the python version implemented here against another python implementation. It only implements the original 32-bit version.
The libraries, documentation, and the test driver program are licensed under the Unlicense. Do what thou wilt.