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