]> git.ipfire.org Git - thirdparty/bind9.git/commit
Implement incremental hash table resizing in isc_ht
authorOndřej Surý <ondrej@isc.org>
Tue, 15 Mar 2022 20:45:33 +0000 (21:45 +0100)
committerOndřej Surý <ondrej@isc.org>
Thu, 17 Mar 2022 07:16:24 +0000 (08:16 +0100)
commite42cb1f198ae945fc322ffed388cd647c8c75fbf
tree401cadddfc12589d7e7db83a6f658c13a899a095
parent7ba3a069355875409fadd0da094293cd08d7ccb6
Implement incremental hash table resizing in isc_ht

Previously, an incremental hash table resizing was implemented for the
dns_rbt_t hash table implementation.  Using that as a base, also
implement the incremental hash table resizing also for isc_ht API
hashtables:

 1. During the resize, allocate the new hash table, but keep the old
    table unchanged.
 2. In each lookup, delete, or iterator operation, check both tables.
 3. Perform insertion operations only in the new table.
 4. At each insertion also move <r> elements from the old table to
    the new table.
 5. When all elements are removed from the old table, deallocate it.

To ensure that the old table is completely copied over before the new
table itself needs to be enlarged, it is necessary to increase the
size of the table by a factor of at least (<r> + 1)/<r> during resizing.

In our implementation <r> is equal to 1.

The downside of this approach is that the old table and the new table
could stay in memory for longer when there are no new insertions into
the hash table for prolonged periods of time as the incremental
rehashing happens only during the insertions.
lib/isc/ht.c
lib/isc/include/isc/ht.h