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.
Thanks,
Daniele
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
