? 2022/3/1 ??6:06, Eugenio Perez Martin ??:>>> +
>>> + /*
>>> + * Find a valid hole for the mapping
>>> + *
>>> + * Assuming low iova_begin, so no need to do a binary search
to
>>> + * locate the first node.
>>> + *
>>> + * TODO: Replace all this with g_tree_node_first/next/last
when available
>>> + * (from glib since 2.68). To do it with g_tree_foreach
complicates the
>>> + * code a lot.
>>> + *
>> One more question
>>
>> The current code looks work but still a little bit complicated to be
>> reviewed. Looking at the missing helpers above, if the add and remove
>> are seldom. I wonder if we can simply do
>>
>> g_tree_foreach() during each add/del to build a sorted list then we can
>> emulate g_tree_node_first/next/last easily?
>>
> This sounds a lot like the method in v1 [1]:).
Oh, right. I missed that and it takes time to recover the memory.
>
> But it didn't use the O(N) foreach, since we can locate the new
node's
> previous element looking for the upper bound of iova-1, maintaining
> the insertion's complexity O(log(N)). The function g_tree_upper_bound
> is added in Glib version 2.68, so the proposed version will be deleted
> sooner or later.
>
> Also the deletion keeps being O(log(N)) since deleting a node in QLIST is
O(1).
Yes, so I think we can leave the log as is and do optimization on top.
Thanks
>