Why are splay trees used in the preprocessors?

[Joe Smith <just2999782 () yahoo com>]

I have been studying the Snort code (v2.0.2) for a few
weeks with most of my focus on the stateful
preprocessors (portscan, portscan2, frag2, stream4).  

I noticed that they all use splay trees to store
information (such as Portscanner nodes, Target nodes,
Conversation nodes, etc.).  Obviously, speed is of
utmost priority in packet processing code.  My
question is why is a splay tree the preferred data
structure for this?  Would a hash have worked better?

I understand that a splay tree will arrange itself to
have the most frequently accessed nodes near the top
(root) and thus have a very low avg. search time. 
Also, it would be faster to examine every node in
order (based on some comparison criteria) in a splay
tree than in a hash because the hash would require a
sorting of the keys for this purpose.  Additionally,
since the preprocessors prune their trees every time
they recieve a packet, it seems the traversal becomes
a critical feature of the chosen data structure.

Anyway, this argument does not fully convince me that
the splay tree is the fastest choice.  What about the
cost of inserting a node?  Is it possible that the
splay tree was chosen for reasons other than speed?


Thanks,
Peter


__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/


-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
Does SourceForge.net help you be more productive?  Does it
help you create better code?  SHARE THE LOVE, and help us help
YOU!  Click Here: http://sourceforge.net/donate/
_______________________________________________
Snort-users mailing list
Snort-users () lists sourceforge net
Go to this URL to change user options or unsubscribe:
https://lists.sourceforge.net/lists/listinfo/snort-users
Snort-users list archive:
http://www.geocrawler.com/redir-sf.php3?list=snort-users