On 3/21/25 17:32, Dumitru Ceara via dev wrote:
> On 3/21/25 7:31 AM, Ales Musil wrote:
>> @@ -108,40 +98,52 @@ bool
>> ofctrl_acked_seqnos_contains(const struct ofctrl_acked_seqnos *seqnos,
>> uint64_t val)
>> {
>> - struct ofctrl_ack_seqno *sn;
>> + if (vector_is_empty(&seqnos->acked)) {
>> + return false;
>> + }
>> +
>> + size_t low = 0;
>> + size_t high = vector_len(&seqnos->acked) -1;
>> + uint64_t *acked = vector_get_array(&seqnos->acked);
>>
>> - HMAP_FOR_EACH_WITH_HASH (sn, node, hash_uint64(val), &seqnos->acked) {
>> - if (sn->seqno == val) {
>> + while (low <= high) {
>> + size_t mid = low + (high - low) / 2;
>> +
>> + if (acked[mid] == val) {
>> return true;
>> }
>> +
>> + if (acked[mid] >= acked[low]) {
>> + if (val >= acked[low] && val < acked[mid]) {
>> + high = mid - 1;
>> + } else {
>> + low = mid + 1;
>> + }
>> + } else {
>> + if (val > acked[mid] && val <= acked[high]) {
>> + low = mid + 1;
>> + } else {
>> + high = mid - 1;
>> + }
>> + }
>> }
>> - return false;
>> -}
>
> I think this definitely deserves a comment. :)
>
> This works because sequence numbers are acked in increasing order
> (except for the case when sequence numbers overflow).
The data structure is also used for nb_cfg numbers. I'm not sure we can
guarantee that they can never jump back or overflow. Database can be reset
for example. And while this is far reached and the function is not used
for this use case, I'm not convinced it's a good idea to assume any kind
of order in this generic function.
> So the sequence
> number collection is always a "sorted and shifted" ordered collection
> which allows us to implement the binary search above if we store them as
> a vector.
FWIW, I'm also not sure this binary search implementation is correct.
I didn't look very close, but on a first read it seems that it can't
find the second element of an ascending 2-element vector. And if that's
true, it will fail to find elements in any array half the time.
I'd suggest to add vector_find function instead and use the standard
bsearch() inside. And and some unit tests.
But again, I'm not convinced we can assume the values to be sorted here.
Best regards, Ilya Maximets.
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
