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@xxxxxxxxxx +1-919-301-3266
Libvirt virtualization library http://libvirt.org
Attachment:
signature.asc
Description: OpenPGP digital signature
-- libvir-list mailing list libvir-list@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/libvir-list