[Snort-users] Why are splay trees used in the preprocessors?

Joe Smith just2999782 at ...131...
Sat Nov 22 21:10:03 EST 2003


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/




More information about the Snort-users mailing list