]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/commit
libalias: Switch to efficient data structure for outgoing traffic
authorLutz Donnerhacke <donner@FreeBSD.org>
Thu, 27 May 2021 21:42:54 +0000 (23:42 +0200)
committerLutz Donnerhacke <donner@FreeBSD.org>
Sat, 19 Jun 2021 20:09:44 +0000 (22:09 +0200)
commit935fc93af157dee352eb4b6c83f8a2a9e7fd9a4e
tree0a8f6aff0a974b8c88926fffd1d40bba47bbbf49
parentd989935b5bcd880353f0de89eda958c45e7e3342
libalias: Switch to efficient data structure for outgoing traffic

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
sys/netinet/libalias/alias_db.c
sys/netinet/libalias/alias_local.h