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). 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.
Regards,
Dumitru
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
