-
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. Discussed with: Dimitry Luhtionov MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D30516
935fc93a