Re: [PATCH v2] of: use hash based search in of_find_node_by_phandle

[Chintan Pandya]

> I'm probably missing something obvious, but: Aren't phandles in practice
> small consecutive integers assigned by dtc? If so, why not just have a
> smallish static array mapping the small phandle values directly to
> device node, instead of adding a pointer to every struct device_node? Or
> one could determine the size of the array dynamically (largest seen
> phandle value, capping at something sensible, e.g. 1024).
Haven't noticed this earlier !! If following is known or true, we can avoid
using hash-table and save per device_node hlish_node.

ÂÂÂ 1. How to know max phandle value without traversing tree once? In 
my case,
ÂÂÂÂÂÂ max is 1263.
ÂÂÂ 2. Although, I haven't observed collision but is it like every 
device_node
ÂÂÂÂÂÂ is associated with unique phandle value ?
> In either case, one would still need to keep the code doing the
> whole-tree traversal for handling large phandle values, but I think the
> above should make lookup O(1) in most cases.
I would refrain doing this because that will make this API inconsistent 
in terms
of time taken by different nodes. I see that people do change their device
placing in DT and that changes time taken in of_* APIs for them but 
affecting
others.

> Alternatively, one could just count the number of nodes with a phandle,
> allocate an array of that many pointers (so the memory use is certainly
> no more than if adding a pointer to each device_node), and sort it by
> phandle, so one can do lookup using a binary search.
>
> Rasmus
This is certainly doable if current approach is not welcomed due to
addition on hlish_node in device_node.

Chintan Pandya

--
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
a Linux Foundation Collaborative Project