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

[Lennart Poettering]

On Tue, 21.10.14 17:36, Michal Schmidt (mschmidt at redhat.com) wrote:

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

"OrderedHashmap" sounds more descriptive to me...

Lennart

-- 
Lennart Poettering, Red Hat