projects / platform / upstream / systemd.git / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: bcd8e6d) | patch
hashmap: size hashmap bucket array dynamically
authorLennart Poettering <lennart@poettering.net>
Mon, 30 Sep 2013 22:13:18 +0000 (00:13 +0200)
committerLennart Poettering <lennart@poettering.net>
Mon, 30 Sep 2013 22:17:21 +0000 (00:17 +0200)
commit45fa9e29f8c9759c8f2f4238fed956f695c73dc3
tree456b6168141128bd35319af35ac9e437851680b1tree | snapshot
parentbcd8e6d1bd3f434af894faeb400fee0e99445a7fcommit | diff
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).
src/shared/hashmap.c diff | blob | history
src/shared/hashmap.h diff | blob | history
src/test/test-hashmap.c diff | blob | history
Domain: System / System Framework;