Storing arbitrary byte sequences

[superbobry]

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:

1. Switch from unit8 to uint16 for TrieChar.
2. Implement an API with explicit length parameter.

The original request was submitted to the Python wrapper, see pytries/datrie#31.

[thep]

Changing TrieChar type would involve replacing <string.h> function calls in the Tails implementation with custom functions written for uint16 strings.

The amount of work should be about the same as changing the string representation from 0-terminated to length-counted. So, I think changing the type is not necessary.

What really matters is AlphaChar string, for which 0 termination is still assumed on every API. We need new APIs to allow character 0 in keys.

[thep]

I think binary keys should be represented with a separate set of APIs, just like how memcpy() is separated from strcpy(). For ease of use, let's define a dedicated data type BinKey, e.g.

typedef struct _BinKey BinKey;
struct _BinKey {
    AlphaChar *key;
    int        key_len;
};

with some associated functions, say:

void bin_key_set (BinKey *bk, AlphaChar *key, int key_len);
void bin_key_cpy (BinKey *dst, const BinKey *src);
int  bin_key_cmp (const BinKey *bk1, const BinKey *bk2);
void bin_key_destruct (BinKey *bk);  // freeing the allocated *key

Then, it can be used in our APIs:

Bool trie_bin_retrieve (const Trie *trie, const BinKey *bin_key, TrieData *o_data);
Bool trie_bin_store (Trie *trie, const BinKey *bin_key, TrieData data);
Bool trie_bin_store_if_absent (Trie *trie, const BinKey *bin_key, TrieData data);
Bool trie_bin_delete (Trie *trie, const BinKey *bin_key);

typedef Bool (*TrieBinEnumFunc) (const BinKey *bin_key, TrieData data, void *user_data);
Bool trie_bin_enumerate (const Trie *trie, TrieBinEnumFunc enum_func, void *user_data);

The TrieIterator part also needs the BinKey counterpart. But let's elaborate further whether it needs a new iterator type for BinKey or just an additional method to the existing TrieIterator type.

[superbobry]

I like the API, look forward to seeing it in the next libdatrie release :)

[thep]

I think binary keys should be represented with a separate set of APIs, just like how memcpy() is separated from strcpy().

I've just got some free time to work on this. And the length-counted key appears to be a bad idea, as the concept of terminating TRIE_CHAR_TERM ('\0') is hard-wired in the trie structure, to allow a key to be prefix to other keys (e.g. 'an' is prefix to 'another'). And this also applies to binary keys.

So, let's consider changing the TrieChar typedef instead. AFAIK, this would break compatibility of the TAIL structure in current trie files.