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 > [EMAIL PROTECTED] > http://www.ethereal.com/mailman/listinfo/ethereal-cvs _______________________________________________ Ethereal-dev mailing list [EMAIL PROTECTED] http://www.ethereal.com/mailman/listinfo/ethereal-dev
