Re: [PATCH v2 08/14] util: Add iova_tree_alloc

[Jason Wang]

在 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


>