[Guy Harris <guy@xxxxxxxxxxxx>]

On Dec 4, 2003, at 3:20 AM, Ronnie Sahlberg wrote:

> I was just looking at it today and thinking
> this structure and the way we use it: it is just a normal binary tree

Well, N-ary, really.

> but with one extra pointer to point to the last entry straight down 
> right/left
> (depending on how you draw it) for performance.
>
> Looking at how it is used in proto.c I saw:
>
> 1 we add leaf nodes to it.
> 2 we never rebalance it.

Yes, the structure of the tree reflects the structure of the packet.

> 3 when we traverse it we only traverse it in order and fully.

Fully, yes, at least for now.

In-order, no - proto_tree_traverse_pre_order() is used by 
"proto_find_field_from_offset()".  I'm not sure it has to be, however.

> 4 we never remove nodes unless we remove all nodes at once.
>
> If we make 4 into a requirement instead of an implementation detail

I can't think offhand of a reason why we couldn't make it a requirement.

> then the node alloc/node free functions should be replaced with
> SLAB_ALLOC/FREE macros and we win once again.

Which alloc functions are those?  "proto_tree_add_node()" calls 
"PROTO_NODE_NEW()", which is a macro that uses "SLAB_ALLOC()".