Change `BTreeMap` to use parent pointers

[apasel422]

This will require nodes to have a stable address.

CC #26227 @gankro.

[Gankra]

All nodes are boxed, so this is trivially true?

[apasel422]

BTreeMap directly contains a Node, and actually no nodes are boxed. They have fields for the allocated keys/vals/edges instead of being boxed themselves.

[apasel422]

Well, the root node definitely isn't boxed. I guess the non-root ones do have a stable address, though, because their parent nodes' allocations never change (as far as I can tell).

[Gankra]

Oh whoops, yes you're right. I forgot that we did that.

I fear that without ManuallyDrop we're going to have to go Full HashMap and manage all of our allocations/destructing.

[Gankra]

Oh wait no we're 90% of the way to Full HashMap anyway. I'm remembering the good ol' days...

[Gankra]

Auuuugh all of this is coming back to me.

Basically it seems to me that you "want"

Node {
  len: u8,
  parent_idx: u8,
  is_leaf: bool,
  parent: *mut Node,
  keys: ManuallyDrop<[K; n]>
  vals: ManuallyDrop<[V; n]>
  edges: ManuallyDrop<[Box<Node>; n + 1]> 
}

Map {
  root: Option<Box<Node>>
}

But this design forbids you from not allocating space for your edges in your leaves. This is why we currently have (effectively):

Node {
    len: u8,
    // Actually just Uniques that we manually allocate and manage
    keys: Box<ManuallyDrop<[K; n]>>,
    vals: Box<ManuallyDrop<[V; n]>>,
    edges: Option<Box<ManuallyDrop<[Node; n + 1]>>>,
}

Which enables the edges to not be allocated (doubling as is_leaf). We then also abuse this fact to keep the root inline, and avoid an extra allocation/indirection.

We could also consider a hybrid:

Node {
    len: u8,
    keys: [K; n],
    vals: [V; n],
    edges: Option<Box<ManuallyDrop<[Node; n + 1]>>>,
}

But this has the negative side-effect of making the edges array enormous.

I think google's btree does the following:

struct BaseNode {
   is_leaf: bool,
   keys: ManuallyDrop<[K; n]>
   vals: ManuallyDrop<[V; n]>
   // and other common stuff like parent pointers
}

// Inherit from BaseNode
struct InternalNode: BaseNode {
   edges: ManuallyDrop<[Unique<BaseNode>; n+1]>
}

And then based on the value of is_leaf, may cast the BaseNode to an InternalNode.

This works because a Leaf never becomes Internal or vice-versa. So leaves only allocate the space they need, and internal nodes allocate more but get type-erased to "only" leaves. And then blah blah figure out deallocation yourself whatever.

[apasel422]

The type-erasure approach seems best, but as I understand it, it's technically undefined behavior for us to transmute between the two struct types, right?

[Gankra]

Not if they're repr(C) and one is a prefix of the other. You would be transmuting the pointers, of course.

[apasel422]

OK, I got a prototype working with type-erasure and parent-pointer insertion, though it's not using the existing BTree code. I need to play around with it more in isolation before attempting a PR.

[apasel422]

How important is it to keep the ability to specify b? It seems like we're waiting for type-level integers (or associated constants) to land before stabilizing that functionality anyway.

[apasel422]

I'm leaning toward the following representation:

const T: usize = 6;

pub struct BTreeMap<K, V> {
    root: Option<Box<Node<K, V>>>,
    ...
}

#[repr(C)]
struct Node<K, V> {
    keys: [K; 2 * T - 1],
    vals: [V: 2 * T - 1],
    parent: *mut InternalNode<K, V>,
    len: u16,
    idx: u16,
    is_leaf: bool,
}

#[repr(C)]
struct InternalNode<K, V> {
    node: Node<K, V>,
    edges: [*mut Node<K, V>; 2 * T],
}

We don't need ManuallyDrop right now, because we can just take the root and mem::forget the node after running the key and value destructors and recursively dropping any edges. We should be able to easily replace the T const with an integer parameter when those are ready.

[Gankra]

Being able to specify B is totally unimportant and is slated to be deprecated.

Also this layout wastes an extra ptr of space over using a u8 for len and idx on 32-bit (no effect on 64bit).

As a minor bikeshed I'd maybe call idx "parent_idx" or whatever.

[Gankra]

Oh but otherwise 👍 this is basically what I had in mind.

[apasel422]

I was aware of the waste, but unsure whether we wanted to support B > 255. u8 should suffice, though. (In a future Rust, we might even be able to determine how big to make {len, parent_idx} based on B.)

What do we have to be aware of with zero-sized types here?