[PATCH 3/5] maple_tree: use vacant nodes to reduce worst case allocations

[Liam R. Howlett]

* Wei Yang <richard.weiyang at gmail.com> [241118 21:31]:
> On Mon, Nov 18, 2024 at 11:36:18AM -0500, Sidhartha Kumar wrote:
> >On 11/15/24 8:41 PM, Wei Yang wrote:
> >> On Fri, Nov 15, 2024 at 03:34:55PM -0500, Sidhartha Kumar wrote:
> >> > On 11/15/24 2:52 AM, Wei Yang wrote:
...

> >> 
> >> Hmm... I come up with a case in which vacant_height may not high enough.
> >> 
> >> Here is the subtree where spanning write locates. The first level is the
> >> parent node of the second level nodes.
> >> 
> >>                  vacant node
> >>                  +--------+-+-+-------+
> >>                  |        |l|r|       |
> >>                  +--------+-+-+-------+
> >> 
> >>                  l                 r
> >>      +------+    +----+-------+    +---------+--+    +------+
> >>      |      |    |    |       |    |         |  |    |      |
> >>      +------+    +----+-------+    +---------+--+    +------+
> >>                       ^                      ^
> >> 		     |                      |
> >> 		   index                   last
> >> 
> >> When mas_wr_walk_descend() to node l, mas_is_span_wr() return true since last
> >> is in the right sibling, node r. Let's say the parent is vacant and l/r is
> >> leaf. So the request number is (1 * 3) + 1.
> >> 
> >> Let's assume:
> >> 
> >>    * vacant node is just sufficient
> >>    * l's left part + r's right part is sufficient but not overflow
> >> 
> >> Then the "new vacant node" would be deficient and needs another round
> >> rebalance.
> >> 
> >> For this case, I am afraid it doesn't allocate enough nodes. Or I
> >> misunderstand this?
> >
> >I think you are correct and we need to use the sufficient height which is
> >introduced in patch 5 in the spanning store case similar to how patch 5 uses
> >it for the rebalance store case.
> >
> >	case wr_rebalance:
> >		if (wr_mas->sufficient_height < wr_mas->vacant_height) {
> >			ret = (height - wr_mas->sufficient_height)*2 +1;
> >			break;
> >		}
> >		ret = delta * 2 + 1;
> >		break;
> >
> 
> I have thought about this.
> 
> But the spanning write case seems to be a little special to
> splitting/rebalance.
> 
> It could be both require one more extra slot and may need to be rebalanced.
> We are not sure the exact behavior on converge node. Only check one aspect
> seems not enough.
> 
> Do you think so ?

I'm pretty sure the calculation will need to be different than the
rebalance case.  He was just saying that it's going to need to be like
rebalance, but not the same code.

Let's see what Sid comes up with.