[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