Page MenuHomeFreeBSD

libalias: Switch to efficient data structure for incoming traffic

Authored by donner on May 28 2021, 9:00 PM.
Referenced Files
Unknown Object (File)
Tue, Feb 20, 9:10 PM
Unknown Object (File)
Fri, Feb 16, 8:16 AM
Unknown Object (File)
Mon, Feb 5, 2:15 PM
Unknown Object (File)
Jan 26 2024, 11:51 PM
Unknown Object (File)
Jan 25 2024, 8:09 AM
Unknown Object (File)
Jan 25 2024, 8:09 AM
Unknown Object (File)
Dec 20 2023, 4:10 AM
Unknown Object (File)
Dec 13 2023, 12:51 PM



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 used again. In order to avoid
long search times in other cases, the lists are hashed in to 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.

Depends on D30516

Diff Detail

rG FreeBSD src repository
Lint Not Applicable
Tests Not Applicable

Event Timeline

This revision was not accepted when it landed; it landed in state Needs Review.Jun 19 2021, 8:29 PM
This revision was automatically updated to reflect the committed changes.