On 21/04/2016 14:54, "Ben Pfaff" <b...@ovn.org> wrote:
>On Thu, Apr 21, 2016 at 09:41:03PM +0000, Daniele Di Proietto wrote:
>>
>>
>> On 21/04/2016 11:28, "Ben Pfaff" <b...@ovn.org> wrote:
>>
>> >On Tue, Apr 19, 2016 at 03:28:39PM -0700, Daniele Di Proietto wrote:
>> >> Makes popping each member of the hmap a bit easier.
>> >>
>> >> Signed-off-by: Daniele Di Proietto <diproiet...@vmware.com>
>> >
>> >It's unfortunately quite expensive, though: O(n**2) in the number of
>> >buckets in the hmap, as opposed to O(n) for HMAP_FOR_EACH_SAFE.
>>
>> You're right, I didn't realize that hmap_first() is O(n) in the number
>>of
>> buckets. Apologies for this oversight and thanks for noticing it.
>>
>> How about this instead?
>>
>> ---8<---
>> static inline struct hmap_node *
>> hmap_pop_helper__(struct hmap *hmap, size_t *bucket) {
>>
>> for (; *bucket <= hmap->mask; (*bucket)++) {
>> struct hmap_node *node = hmap->buckets[*bucket];
>>
>> if (node) {
>> hmap_remove(hmap, node);
>> return node;
>> }
>> }
>>
>> return NULL;
>> }
>>
>> #define HMAP_FOR_EACH_POP(NODE, MEMBER, HMAP) \
>> for (size_t bucket__ = 0; \
>> (INIT_CONTAINER(NODE, hmap_pop_helper__(HMAP, &bucket__),
>> MEMBER), \
>> false) \
>> || (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) || (NODE =
>> NULL);)
>> ---8<---
>>
>> I wanted to introduce this because I found that sometimes having a
>> "next" local variable is too verbose, but if you don't think it's
>> worth I can drop this patch.
>
>Much better, thanks.
>
>You can write "(a, false) || b || c" as "a, b || c" though.
Right, I'll fold this in, thanks.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
