tree 4c2b6ab7cd45677157eeec8bbff5a6ca2ed9ef14
parent a329233ef9e80285ba8fe989ee068ce957e2c1d4
author Olivier Matz <olivier.matz@6wind.com> 1695299712 +0200
committer Michal Vasko <mvasko@cesnet.cz> 1696426823 +0200

hash_table REFACTOR simplify collision management

The current implementation manages collision by browsing the next
records to find an unused one.

This has the following consequences:
- when there are a lot of collisions, the insertion can take a lot
  of time before finding an empty entry.
- this may require to rehash the table to get rid of invalid records
- the code that handles the collisions is not trivial

This commit reworks the hash table to use a per-hash list of records.

It prepares the work to have an insertion in the hash table in O(1) even
if there are hash collisions. This commit is not sufficient for that yet,
since we always check for duplicates at insertion. See the introduction
of ly_ht_insert_no_check() in a latter commit.

Note: this change breaks the validation unit test. It is fixed by the
next commit.

Signed-off-by: Olivier Matz <olivier.matz@6wind.com>