[systemd-devel] [PATCH 00/26] hashmap rewrite

[Lennart Poettering]

On Thu, 16.10.14 09:50, Michal Schmidt (mschmidt at redhat.com) wrote:

> Hello,
> 
> I rewrote the hashmaps implementation to use less memory.
> See patch PATCH 21/26 for details and some measurements.
> 
> I'd like to push this upstream after v217 is released,
> unless there are objections.
> 
> Key changes that affect other code:
>  - Sets and Hashmaps do not remember the insertion order anymore.
>    They can still be iterated with *_FOREACH* or *_first*, but
>    the order of entries is undefined.

Hmm, this means the iteration logic will have to iteratively skip over
empty buckets to be able to enumerate? I figure that isn't too bad if
we scale the number of buckets by the size of the hashmap anyway.

> 
>  - There is a new type "LinkedHashmap" to use in the few cases where
>    insertion order matters. The cases that I believe need it are
>    converted in this patch series.

Sounds good. Don't like the name though. I think "OrderedHashmap"
would be better, since for the user of the data structure the
different is all about the order, right?

> 
>  - Two hashmap operations that previously could not fail with -ENOMEM
>    may now do so:
>      *_move
>      *_move_one
>
> 
>  - A new hashmap operation is introduced:
>      *_reserve
>    It can be used to ensure subsequent *_move or *_move_one operations
>    will not need to allocate memory and won't fail with -ENOMEM, thus
>    bringing back the old implementation's guarantees.
>    (Actually it also ensures that for *_put operations, but that should
>     not be relied on, because it's an implementation detail.)
>    It can also be used as a hint before putting a known number of
>    entries into a hashmap, to avoid later automatic resizing.

Makes sense.

Lennart

-- 
Lennart Poettering, Red Hat