在 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
_______________________________________________
Virtualization mailing list
Virtualization@xxxxxxxxxxxxxxxxxxxxxxxxxx
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
