Open superbobry opened 8 years ago
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.
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.
I like the API, look forward to seeing it in the next libdatrie
release :)
I think binary keys should be represented with a separate set of APIs, just like how
memcpy()
is separated fromstrcpy()
.
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.
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
touint16
forTrieChar
.The original request was submitted to the Python wrapper, see pytries/datrie#31.