Ethereal-dev: [Ethereal-dev] Re: [Ethereal-cvs] cvs commit: ethereal/epan proto.c proto.h
Very Cool.
I was just looking at it today and thinking
this structure and the way we use it: it is just a normal binary tree 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.
3 when we traverse it we only traverse it in order and fully.
4 we never remove nodes unless we remove all nodes at once.
If we make 4 into a requirement instead of an implementation detail then we
can easily replace
the traverse function call when deleting the tree in
proto_tree_free()/proto_tree_free_node() with one single
nonrecursive cheap function. This assumes that both shildren and siblings
point parent to the same parent as a normal left/right binary tree would.
I see you did already change this with proto_tree_traverse_in_order() but
that one is recursive and it will be called once for every single field.
I would like to try to rewrite it to be nonrecursive and save the
unnecessary function call overhead (which is nonnonsignificant)
This is made easier if we also mandate 3 as a requirement which then allows
the generic traversal function to be completely nonrecursive and we
remove the function call overhead.
2 is not much we can do about.
1 is already addressed by the extra pointer for last node.
Let me play with it, Im sure we can squeze a % or two more out of this one.
then the node alloc/node free functions should be replaced with
SLAB_ALLOC/FREE macros and we win once again.
----- Original Message -----
From: "Guy Harris"
Sent: Thursday, December 04, 2003 9:59 PM
Subject: [Ethereal-cvs] cvs commit: ethereal/epan proto.c proto.h
> guy 2003/12/04 04:59:34 CST
>
> Modified files:
> epan proto.c proto.h
> Log:
> Don't use GNodes for the protocol tree, put the sibling pointer, and
> pointers to the first *and* last child, in the "proto_node" structure
> itself. That saves us one level of indirection and memory allocation,
> and lets us append to a tree by appending to the last child directly,
> rather than having to scan through the list of siblings of the first
> child to find the end of that list.
>
> Revision Changes Path
> 1.124 +117 -25 ethereal/epan/proto.c
> 1.52 +13 -9 ethereal/epan/proto.h
>
> _______________________________________________
> Ethereal-cvs mailing list
> Ethereal-cvs@xxxxxxxxxxxx
> http://www.ethereal.com/mailman/listinfo/ethereal-cvs
