List,
I have been started doing some design requirements for a red-black
tree implementation for ethereal to replace all the hashtables we use.
The requirements I have come up with so far to make it applicable to
as many parts of ehtereal as possible are as follows, please provide
input or add extra requirements so I can work it into the design
before it is finalized:
1, The treesd are allocated with SE style allocations only. (I dont
think EP style trees are useful)
2, A user (dissector) registers/creates the tree by calling
rbtree_t *rb_tree=NULL;
se_rbtree_create(&rb_tree, ...) from the
proto_register_xxx() function once during initialization.
All these tree pointers are kept inside SE in a malloc()ed list so that when we
release all SE memory, the pointers are automatically reset to NULL.
This eliminates the need for explicit register_init_routine() calls
from the dissector in order just to reset the tree and reduces code
size and also reduces the risk for memoryleaks.
This would also eliminate the need for the _free() function used to
release keys/data.
3, The tree takes a list of 1 or more 32bit integers as a "key" and
implements its own internal compare functions which would obviously
make the tree only work for data sets where one can du a basic compare
for (a list of) guint32.
This would eliminate the need for the hastable style _hash() and
_equal() function callbacks.
This is a limitation in flexibility but I think most of the usage
from ethereal would not need anything more than this anyway.
We can still build trees keyed by frame-number, FID,
nfs-filehandles, tcp-sequence-numbers, GUIDs etc.
4, for keys of more than one single 32bit integer, there is trees
inside trees, so that there is one tree for the first 32bit quantity
and this end node then contains a pointer to another tree which
contains a pointer for the tree of the next 32bit quantity of the key
etc.
4.1, optionally and at a later stage, IF there are many keys for
certain applications that always start with the same initial pattern
we can change the top tree to instead manage a 32 bit hash of the
entire key.
5, There are two very similar LOOKUP functions.
One that will return the data for an exact match and a second one that
returns the data for the node that has largest key smaller than or
equal to the specified key we search for. (will be useful to combine
with the tcvp dpu tracking and later a new implementation of tcp
reassembly code)
comments?
