Is this a bug? about libart HOT 7 CLOSED

As part of the API semantics, you cannot have a key that is a full-prefix of another key. This is a non-issue with C-style strings since every key is null terminated, and thus avoids the full-prefix issue.

from libart.

I see. Apparently this behaviour had been encountered before. Sorry for not browsing through the closed issues.
What confuses me is that the key_len parameter is required yet a null terminated string is expected.
Anyway, thanks.

from libart.

@gnois It does not have to be a null terminated string, it just so happens that using one always prevents a full-prefix situation. For example, if you are using an integer as a key, it may not be null terminated.

from libart.

Hi,
I got into the same issue. From the API description I couldn't deduct what is clarified here. Maybe that should be described explicitly in art_insert().

As it is now, I'm evaluating whether I could rely on this library to store IPv6 addresses and networks (that is fixed 16-byte strings for addresses and less than 16-byte strings for networks). Since networks are full prefixes of addresses (and other networks), it's not apparent how that can work...

from libart.

@nmav This should not be an issue as each input is a full 16 bytes, so there is no input that could be a prefix of any other except for an exact match. This is an issue if you use the key "foo" and then key "foobar" as one is now a full prefix of the other (not assuming null terminator, with C-style strings this actually isn't a problem).

from libart.

@armon I glanced through the paper, been looking through the closed issues, and I keep seeing that "you cannot have a key that is a full-prefix of another key." However, it is never actually said why this cannot be done. Could we get an explanation of why this won't work somewhere? I'd suggest the wiki, but there isn't anything even there yet, so...

from libart.

@KitLing It's an implementation issue, as I wrote this for C-strings where that is not an issue (null terminator avoids full prefix, also fixed-size things like integers do not have this issue). It stems from a fact that an internal node must point to a leaf or an internal node, and cannot point to both. This is a space optimization to save a word per internal node. So if you do have a key that is a full prefix of another key, there is no way to represent that, as you need the pointer to somehow point to both a leaf and an internal node.

from libart.