-
Lutz Donnerhacke authored
Current data structure is using a hash of unordered lists. Those unordered lists are quite efficient, because the least recently inserted entries are most likely to be used again. In order to avoid long search times in other cases, the lists are hashed into many buckets. Unfortunatly a search for a miss needs an exhaustive inspection and a careful definition of the hash. Splay trees offer a similar feature: Almost O(1) for access of the least recently used entries, and amortized O(ln(n)) for almost all other cases. Get rid of the hash. Now the data structure should able to quickly react to external packets without eating CPU cycles for breakfast, preventing a DoS. PR: 192888 Discussed with: Dimitry Luhtionov MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D30536
d261e57d