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

[Michal Schmidt]

On 10/20/2014 08:23 PM, Lennart Poettering wrote:
> On Thu, 16.10.14 09:50, Michal Schmidt (mschmidt at redhat.com) wrote:
>> 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?

Yes, to find occupied buckets, it does a sequential scan over the array
of DIB values. That should be pretty fast.

> I figure that isn't too bad if we scale the number of buckets by the
> size of the hashmap anyway.

Yes, though we never scale back down when many entries get removed from
a hashmap (unless ALL of them get removed). It does not seem to be
needed often.

>>  - 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?

I saw the name "LinkedHashmap" used for this thing in Java/Android,
so I went with that. I can rename it, no problem.

Michal