On Thu, 16.10.14 09:50, Michal Schmidt (mschm...@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 _______________________________________________ systemd-devel mailing list systemd-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/systemd-devel
