[ovs-dev] [ovs-discuss] [ACLv2 18/19] hmap: Add HMAP_FOR_EACH_WITH_HASH_SAFE.
Jesse Gross
jesse at nicira.com
Sat Sep 5 00:01:21 UTC 2009
Ben Pfaff wrote:
> Jesse Gross <jesse at nicira.com> writes:
>
>
>> Add a _SAFE version of the macro to allow callers to delete entries
>> as they are iterating over matching entries.
>>
>
> I'm really nervous about this. It only makes sense to allow
> duplicates in an hmap if the maximum number of duplicates for a
> given key is bounded by a very small constant and if it is
> unusual for there to be duplicates. For example, if occasionally
> there might be exactly 2 entries for a given key but there are
> normally only one, then it's OK. But if there might be dozens or
> hundreds of entries with a given key, then that's going to kill
> hash performance and it's a much better idea to use a single
> hmap_node that keeps a list of the duplicate items, e.g.:
>
> struct my_node {
> struct hmap_node hmap_node;
> int my_key; /* or whatever */
> struct list list;
> };
>
> Then the performance will be much better.
>
Good point. I changed it to use a linked list and removed this commit.
More information about the dev
mailing list