[PATCH] bus: skip useless iterations in rte_bus_find

[PATCH] bus: skip useless iterations in rte_bus_find

[Gaetan Rivet]

The starting point is known. The iterator can be directly set to it.

The function rte_bus_find can easily be used with a comparison function
always returning True. This would make it a regular bus iterator.

Users doing so would however accomplish such iteration in

   O(N * N/2) = O(N^2)

Which can be avoided.

Signed-off-by: Gaetan Rivet <gaetan.rivet@6wind.com>
---

In practice, such cost is entirely negligible of course.
It is cleaner and more correct though.

 lib/librte_eal/common/eal_common_bus.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/lib/librte_eal/common/eal_common_bus.c b/lib/librte_eal/common/eal_common_bus.c
index 9d1be8a..53bb004 100644
--- a/lib/librte_eal/common/eal_common_bus.c
+++ b/lib/librte_eal/common/eal_common_bus.c
@@ -153,15 +153,16 @@ struct rte_bus *
 rte_bus_find(const struct rte_bus *start, rte_bus_cmp_t cmp,
 	     const void *data)
 {
-	struct rte_bus *bus = NULL;
+	struct rte_bus *bus;
 
-	TAILQ_FOREACH(bus, &rte_bus_list, next) {
-		if (start && bus == start) {
-			start = NULL; /* starting point found */
-			continue;
-		}
+	if (start != NULL)
+		bus = TAILQ_NEXT(start, next);
+	else
+		bus = TAILQ_FIRST(&rte_bus_list);
+	while (bus != NULL) {
 		if (cmp(bus, data) == 0)
 			break;
+		bus = TAILQ_NEXT(bus, next);
 	}
 	return bus;
 }
-- 
2.1.4

Re: [PATCH] bus: skip useless iterations in rte_bus_find

[Ferruh Yigit]

On 8/29/2017 9:19 AM, Gaetan Rivet wrote:
> The starting point is known. The iterator can be directly set to it.
> 
> The function rte_bus_find can easily be used with a comparison function
> always returning True. This would make it a regular bus iterator.
> 
> Users doing so would however accomplish such iteration in
> 
>    O(N * N/2) = O(N^2)
> 
> Which can be avoided.
> 
> Signed-off-by: Gaetan Rivet <gaetan.rivet@6wind.com>
> ---
> 
> In practice, such cost is entirely negligible of course.
> It is cleaner and more correct though.

+1 for more clean approach

Reviewed-by: Ferruh Yigit <ferruh.yigit@intel.com>

Re: [PATCH] bus: skip useless iterations in rte_bus_find

[Thomas Monjalon]

24/10/2017 02:18, Ferruh Yigit:
> On 8/29/2017 9:19 AM, Gaetan Rivet wrote:
> > The starting point is known. The iterator can be directly set to it.
> > 
> > The function rte_bus_find can easily be used with a comparison function
> > always returning True. This would make it a regular bus iterator.
> > 
> > Users doing so would however accomplish such iteration in
> > 
> >    O(N * N/2) = O(N^2)
> > 
> > Which can be avoided.
> > 
> > Signed-off-by: Gaetan Rivet <gaetan.rivet@6wind.com>
> > ---
> > 
> > In practice, such cost is entirely negligible of course.
> > It is cleaner and more correct though.
> 
> +1 for more clean approach
> 
> Reviewed-by: Ferruh Yigit <ferruh.yigit@intel.com>

Applied, thanks