跟算法复杂度干上了

最近设计了两个算法，一个是IP规则匹配算法，另一个是连接管理算法。

第一个算法中每个规则是一个五元组（源IP、目的IP、源端口、目的端口、协议）外加一个标签，五元组的任意一个域可以为wildcard，但不支持mask，规则存放在一个几兆大的高速存储器内，同时对查找速度要求比较高。

参考了一下nf-hipac的算法思路，设计了一个很简洁的算法。我 这里的情况比nf-hipac所面对的情况要简单一点，不需要支持mask（没有看nf-hipac的源码，但是相信它在解决mask问题的时候会遇到严 重的空间爆炸），但是在支持wildcard的时候还是遇到了空间爆炸的问题。好在牺牲了点时间，解决了这个问题。最终算法每个IP包只需要做大约26次 32bit比较就可以了，而且10万条规则所占用的存储空间也只有4兆多。

第二个算法跟第一个算法有点类似，是一个连接数据库管理算法，提供对一个连接数据库的查找、删除、增加操作。与第一个算法不同的是，不需要支持wildcard，但是要求高速的查找和比较快速的插入和删除，并且同样要求较小的存储空间。

原先采用的查找树空间浪费严重，在恶劣情况下16兆空间只能支持几万的连接。设计了一种路径压缩算法，可以在恶劣情况下存储45万以上的连接。但是这个算 法目前在删除操作中会产生碎片（可以避免产生碎片，但是算法复杂度较高），在频繁的增加、删除操作中，占用空间会微弱的上升。