[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re: [libvirt] [PATCHv2 2/4] util: add virNetDevVlanType



On 08/14/2012 11:01 PM, Laine Stump wrote:
> I've changed the algorithm to the following. Unfortunately I again
> wasn't thinking, and changed it during a git rebase, so I don't have a
> diff handy. Should I resend the entire patch, or is seeing this changed
> function enough for an ACK?

Nah, seeing this is fine.

> 
> (Note that the following would return true if one array was {1,1,2,2,2}
> and the other was {2,1,2,1,1} (i.e. if both have all the same members,
> but with differing counts of each). However, it makes no sense for a
> vlan trunk to list the same tag more than once anyway, so I guess
> effectively they *would* be the same.)

Yeah, that makes me wonder if we should do duplicate detection at XML
parse time.  But it's not the end of the world if we don't (the behavior
is the same, and most people won't be tickling this corner case).

> 
>     for (ai = 0; ai < a->nTags; ai++) {
>         for (bi = 0; bi < b->nTags; bi++) {
>             if (a->tag[ai] == b->tag[bi])
>                 break;
>         }
>         if (bi >= b->nTags) {
>             /* no matches for a->tag[ai] anywhere in b->tag */
>             return false;
>         }
>     }

That's O(n^2).  As long as N is small, it doesn't matter; and
considering that N cannot be larger than 4095 and most people won't
bundle that many vlans together on a trunk, I think we're fine.  In
other words, any rewrite to use conversions to two bitsets followed by
an intersection to cut it down to O(n) is probably premature
optimization not worth doing.

ACK.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

Attachment: signature.asc
Description: OpenPGP digital signature


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]