Re: [ovs-dev] [PATCH v8 07/16] hmap: Add HMAP_FOR_EACH_POP.

2016-04-21 Thread Daniele Di Proietto 


On 21/04/2016 14:54, "Ben Pfaff"  wrote:

>On Thu, Apr 21, 2016 at 09:41:03PM +, Daniele Di Proietto wrote:
>> 
>> 
>> On 21/04/2016 11:28, "Ben Pfaff"  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 
>> >
>> >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, __),
>> 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

Re: [ovs-dev] [PATCH v8 07/16] hmap: Add HMAP_FOR_EACH_POP.

2016-04-21 Thread Ben Pfaff 
On Thu, Apr 21, 2016 at 09:41:03PM +, Daniele Di Proietto wrote:
> 
> 
> On 21/04/2016 11:28, "Ben Pfaff"  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 
> >
> >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, __),
> 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

Re: [ovs-dev] [PATCH v8 07/16] hmap: Add HMAP_FOR_EACH_POP.

2016-04-21 Thread Daniele Di Proietto 


On 21/04/2016 11:28, "Ben Pfaff"  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 
>
>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, __),
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

Re: [ovs-dev] [PATCH v8 07/16] hmap: Add HMAP_FOR_EACH_POP.

2016-04-21 Thread Ben Pfaff 
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 

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