From: Lennart Poettering <lennart@poettering.net>
Date: Mon, 30 Sep 2013 22:13:18 +0000 (+0200)
Subject: hashmap: size hashmap bucket array dynamically
X-Git-Tag: v208~20
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=commitdiff_plain;h=45fa9e29f8c9759c8f2f4238fed956f695c73dc3;hp=45fa9e29f8c9759c8f2f4238fed956f695c73dc3

hashmap: size hashmap bucket array dynamically

Instead of fixing the hashmap bucket array to 127 entries dynamically
size it, starting with a smaller one of 31. As soon as a fill level of
75% is reached, quadruple the size, and so on.

This should siginficantly optimize the lookup time in large tables
(from O(n) back to O(1)), and save memory on smaller tables (which most
are).
---