Snort mailing list archives
Why are splay trees used in the preprocessors?
From: Joe Smith <just2999782 () yahoo com>
Date: Sat, 22 Nov 2003 21:09:37 -0800 (PST)
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
Current thread:
- Why are splay trees used in the preprocessors? Joe Smith (Nov 22)
- <Possible follow-ups>
- Why are splay trees used in the preprocessors? Joe Smith (Nov 22)
- Re: Why are splay trees used in the preprocessors? Dragos Ruiu (Nov 23)
- RE: Why are splay trees used in the preprocessors? Jim Cervantes (Nov 23)
- Re: Why are splay trees used in the preprocessors? Dragos Ruiu (Nov 23)