aboutgitcodebugslistschat
path: root/util.c
diff options
context:
space:
mode:
authorDavid Gibson <david@gibson.dropbear.id.au>2023-12-07 16:53:51 +1100
committerStefano Brivio <sbrivio@redhat.com>2023-12-27 19:29:45 +0100
commit5913f2641506c0c6df32baf2556f683d7c5e6185 (patch)
tree0f1e608a284015d3e18179e0f356d7b182265c44 /util.c
parent89fcb563fc63229aeac374a0aed057e467ba7f0a (diff)
downloadpasst-5913f2641506c0c6df32baf2556f683d7c5e6185.tar
passt-5913f2641506c0c6df32baf2556f683d7c5e6185.tar.gz
passt-5913f2641506c0c6df32baf2556f683d7c5e6185.tar.bz2
passt-5913f2641506c0c6df32baf2556f683d7c5e6185.tar.lz
passt-5913f2641506c0c6df32baf2556f683d7c5e6185.tar.xz
passt-5913f2641506c0c6df32baf2556f683d7c5e6185.tar.zst
passt-5913f2641506c0c6df32baf2556f683d7c5e6185.zip
tcp: Switch hash table to linear probing instead of chaining
Currently we deal with hash collisions by letting a hash bucket contain multiple entries, forming a linked list using an index in the connection structure. That's a pretty standard and simple approach, but in our case we can use an even simpler one: linear probing. Here if a hash bucket is occupied we just move onto the next one until we find a feww one. This slightly simplifies lookup and more importantly saves some precious bytes in the connection structure by removing the need for a link. It does require some additional complexity for hash removal. This approach can perform poorly with hash table load is high. However, we already size our hash table of pointers larger than the connection table, which puts an upper bound on the load. It's relatively cheap to decrease that bound if we find we need to. I adapted the linear probing operations from Knuth's The Art of Computer Programming, Volume 3, 2nd Edition. Specifically Algorithm L and Algorithm R in Section 6.4. Note that there is an error in Algorithm R as printed, see errata at [0]. [0] https://www-cs-faculty.stanford.edu/~knuth/all3-prepre.ps.gz Signed-off-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
Diffstat (limited to 'util.c')
0 files changed, 0 insertions, 0 deletions