Ill be adding a "string" key binary tree since i need it for nfs filenames.
for nfs it will be easy since all strings are padded by xdr to be a multiple of 4 bytes.
however i will make it handle strings that are not a multiple of guint32 in length as well.
say we have the string foo="ABCDEFGHI"
We can already handle this by
guint32 residual, strlen;
strlen=9;
residual=foo[8]; /* add the residual 1-3 bytes to this variable*/
se_key_t key[4] = {
{1, &strlen },
{2, &foo[0] }, /* deals with the first 8 characters. */
{1, &residual },
{0, NULL }
};
se_tree_insert32_array(, key, )
we just need some nice helpers to hide the array thing.
On 3/7/06, LEGO <luis.ontanon@xxxxxxxxx
> wrote:On 3/7/06, ronnie sahlberg <ronniesahlberg@xxxxxxxxx
> wrote:
> Do we really want hashtables ?
They may turn useful...
How do we handle arbitrary length strings with the rb_tree?
> Hashtables very quickly degenerate to becoming a very slow linear search.
> Usually they do not provide any savings in memory usage either
Ack
> So their only benefit is that they are so conceptually simple that one can
> hack them up from memory in 5 minutes.
There are several hashtables with string indices in the codebase so I
thought them as a replacement until we figure out a mechanism to
handle arbitrary length strings.
We should keep the interface... I won't argue on the fact that there
are better implementations.
> I belive binary trees are superior in every single respect (now that we
> already have them and implementation is not an issue)
> * they are as memory efficient as hash tables
> * they are infinitely faster than hashtables.
Still the issue: how do we handle arbitrary length string keys?
> Do you really really want to have hashtables here?
> I think we should not implement hashtables.
We could make the keys limited to at most 128 bytes and handle them as
an array of (up to?) 32 32bit integers...
L
--
This information is top security. When you have read it, destroy yourself.
-- Marshall McLuhan
_______________________________________________
Ethereal-dev mailing list
Ethereal-dev@xxxxxxxxxxxx
http://www.ethereal.com/mailman/listinfo/ethereal-dev