[dpdk-dev] bus: skip useless iterations in rte_bus_find
Checks
Commit Message
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(-)
Comments
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>
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
@@ -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;
}