artmap 0.8.0

A concurrent in-memory Adaptive Radix Tree (ART) featuring optimistic lock coupling.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
// Copyright (c) 2026 SurrealDB Ltd
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! # The heap tree behind [`VersionedArtMap`](crate::VersionedArtMap)
//!
//! The ART structure is the shared core; this module adds the version-chain
//! protocol (§11.4):
//!
//! - every chain mutation holds the leaf's `chain_latch`, which is terminal in
//!   the lock order, and no ART latch is involved (siblings update in parallel);
//! - the writer re-loads `head` and finds its position under the latch; hints
//!   read before the latch are never used to link;
//! - same-version replacement is out of place: a new node is linked and the
//!   old one marked `superseded`, then retired (heap) or left to the leaf
//!   (inline slot) after unlocking;
//! - `len` changes by the liveness of the head before and after, decided under
//!   the latch;
//! - readers take no latch: `head` and `next` are loaded with `Acquire`;
//! - a leaf is unlinked (by a prune, `remove_key`, `remove_version` or
//!   `clear`) only once its chain latch is killed under the ART latches, and a
//!   writer that finds the latch dead looks the key up again (§13).

#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]

use std::cell::Cell;
use std::ptr::NonNull;

use crate::guard::{retire, Retired};
use crate::key::AsBytes;
use crate::latch::{AbortOnUnwind, ChainGuard, SpinBackoff};
use crate::raw::heap::HeapStorage;
use crate::raw::{Mode, Outcome, RawTree, Unpublished};
use crate::versioned::node::{VersionNode, VersionedLeaf};

pub(crate) type Storage<K, V> = HeapStorage<VersionedLeaf<K, V>>;

/// A leaf and the head version that `remove_head` replaced.
pub(crate) type RemovedHead<K, V> = (NonNull<VersionedLeaf<K, V>>, NonNull<VersionNode<V>>);

/// The concurrent tree of a `VersionedArtMap`.
pub(crate) struct VersionedTree<K, V> {
    pub(crate) raw: RawTree<Storage<K, V>>,
}

impl<K, V> VersionedTree<K, V> {
    crate::sync::const_fn_unless_loom! {
        pub(crate) fn new() -> Self {
            Self {
                raw: RawTree::new_in(HeapStorage::new()),
            }
        }
    }

    #[inline]
    pub(crate) fn len(&self) -> usize {
        self.raw.len()
    }
}

impl<K, V> Drop for VersionedTree<K, V> {
    fn drop(&mut self) {
        // SAFETY: exclusive access in `drop` (Inv 2). Each leaf's drop frees
        // its live chain; detached heap nodes belong to EBR.
        unsafe { self.raw.destroy() }
    }
}

/// The newest node with `version <= max` in the chain starting at `head`.
#[inline]
pub(crate) fn find_le<V>(head: &VersionNode<V>, max: u64) -> Option<&VersionNode<V>> {
    let mut cur: *const VersionNode<V> = head;
    while !cur.is_null() {
        // SAFETY: chain nodes reachable from a protected leaf are protected
        // (EBR for heap nodes, the leaf for inline slots).
        let n = unsafe { &*cur };
        if n.version <= max {
            return Some(n);
        }
        cur = n.next();
    }
    None
}

/// As [`find_le`], but walks and returns raw pointers, keeping the
/// allocation's provenance: a node found here may be retired (Inv 1).
fn find_le_ptr<V>(head: *mut VersionNode<V>, max: u64) -> Option<*mut VersionNode<V>> {
    let mut cur = head;
    while !cur.is_null() {
        // SAFETY: as for `find_le`.
        let n = unsafe { &*cur };
        if n.version <= max {
            return Some(cur);
        }
        cur = n.next();
    }
    None
}

/// Iterates a chain, newest first.
pub(crate) fn chain<V>(head: &VersionNode<V>) -> impl Iterator<Item = &VersionNode<V>> {
    let mut cur: *const VersionNode<V> = head;
    std::iter::from_fn(move || {
        if cur.is_null() {
            return None;
        }
        // SAFETY: as for `find_le`.
        let n = unsafe { &*cur };
        cur = n.next();
        Some(n)
    })
}

/// The result of trying to unlink a versioned leaf (§13).
pub(crate) enum Unlinked {
    /// Unlinked; its chain held this many versions.
    Done(usize),
    /// Its chain was already dead, or the check refused it. Nothing changed.
    Refused,
    /// Not found by its own key bytes (an inconsistent `AsBytes`, Inv 10).
    Missing,
}

impl<K: AsBytes + Send + 'static, V: Send + 'static> VersionedTree<K, V> {
    /// Adds `version` of `key` (a tombstone if `value` is `None`). The caller
    /// holds `guard` (Inv 6). Returns the change in the number of live keys.
    pub(crate) fn insert(
        &self,
        key: K,
        version: u64,
        value: Option<V>,
        guard: &crossbeam_epoch::Guard,
    ) -> isize {
        let mut backoff = SpinBackoff::new();
        // Fast path: the key exists. The probe on the caller's key is a hint
        // (Inv 10); the chain protocol does not depend on it.
        while let Some(leaf) = self.raw.get(key.as_bytes()) {
            // SAFETY: a published leaf, protected by `guard`.
            let l = unsafe { leaf.as_ref() };
            let Some(w) = l.chain_latch.lock() else {
                // Dead: the leaf is being unlinked (§13). Look again: the key
                // is then absent, or lives in a new leaf.
                backoff.spin();
                continue;
            };
            let delta = self.apply_locked(l, version, value, w, guard);
            // `K::drop` runs after the latch is released.
            drop(key);
            return delta;
        }
        let count = isize::from(value.is_some());
        let leaf = VersionedLeaf::new_boxed(key, version, value);
        // SAFETY: a fresh, fully initialised Box allocation owned by this call.
        let owner = unsafe { Unpublished::new(&self.raw.storage, leaf) };
        // SAFETY: `owner` keeps the leaf alive for the call (§9.3).
        let key_bytes = unsafe { leaf.as_ref() }.key.as_bytes();
        loop {
            let outcome =
                match self
                    .raw
                    .insert(&owner, key_bytes, Mode::InsertIfAbsent, count, guard)
                {
                    Ok(o) => o,
                    Err(never) => match never {},
                };
            match outcome {
                Outcome::Inserted(_) => return count,
                Outcome::Existing(existing) => {
                    // SAFETY: a published leaf, protected by `guard`.
                    let e = unsafe { existing.as_ref() };
                    let Some(w) = e.chain_latch.lock() else {
                        // It is being unlinked: ours takes its place once it
                        // is gone.
                        backoff.spin();
                        continue;
                    };
                    // Lost the race to a live leaf: move the version out of
                    // the unpublished one and apply it there. `owner` then
                    // frees the husk (and its key) outside every latch.
                    // SAFETY: never published, exclusively owned through `owner`.
                    let (version, value) = unsafe { VersionedLeaf::take_first(owner.ptr()) };
                    return self.apply_locked(e, version, value, w, guard);
                }
                Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
            }
        }
    }

    /// Applies one version to a published leaf whose chain latch `w` the
    /// caller holds. Returns the change in the number of live keys.
    ///
    /// `value` is declared before `w`, so an unwind drops the latch guard
    /// first and runs `V::drop` outside the latch.
    fn apply_locked(
        &self,
        leaf: &VersionedLeaf<K, V>,
        version: u64,
        value: Option<V>,
        w: ChainGuard<'_>,
        guard: &crossbeam_epoch::Guard,
    ) -> isize {
        // Positions are found under the latch.
        let head = leaf.head_ptr();
        // SAFETY: `head` is live (see `VersionedLeaf::head`).
        let old_live = !unsafe { &*head }.is_tombstone();
        // Every node reachable from `head` under the latch is live and not
        // superseded, and protected by `guard`.
        let at = |p: *mut VersionNode<V>| -> Option<&VersionNode<V>> {
            // SAFETY: as stated above; null means the end of the chain.
            unsafe { p.as_ref() }
        };
        let mut prev: *mut VersionNode<V> = std::ptr::null_mut();
        let mut cur = head;
        while let Some(n) = at(cur).filter(|n| n.version > version) {
            prev = cur;
            cur = n.next();
        }
        let node = leaf.alloc_version(&w, version, value);
        let replaced = at(cur).is_some_and(|n| n.version == version);
        // SAFETY: `node` is unpublished; `cur` (if non-null) is live.
        unsafe {
            (*node).init_next(if replaced { (*cur).next() } else { cur });
        }
        let bomb = AbortOnUnwind;
        if prev.is_null() {
            leaf.set_head(&w, node);
        } else {
            // SAFETY: `prev` is a live node of this chain.
            unsafe { (*prev).set_next(&w, node) };
        }
        if replaced {
            // SAFETY: `cur` is live and now unlinked by us.
            unsafe { (*cur).mark_superseded(&w) };
        }
        let new_head = leaf.head_ptr();
        // SAFETY: live.
        let new_live = !unsafe { &*new_head }.is_tombstone();
        let delta = isize::from(new_live) - isize::from(old_live);
        self.raw.len_add(delta);
        bomb.defuse();
        drop(w);
        if replaced {
            // SAFETY: unlinked under the chain latch, exactly once.
            unsafe { retire_version(cur, guard) };
        }
        delta
    }

    /// The deprecated unversioned remove (§11.5): publishes a tombstone with
    /// the head's version in place of a live head. Returns the old head.
    pub(crate) fn remove_head(
        &self,
        key: &[u8],
        guard: &crossbeam_epoch::Guard,
    ) -> Option<RemovedHead<K, V>> {
        let mut backoff = SpinBackoff::new();
        loop {
            let leaf_ptr = self.raw.get(key)?;
            // SAFETY: protected by `guard`.
            let leaf = unsafe { leaf_ptr.as_ref() };
            let Some(w) = leaf.chain_latch.lock() else {
                // Being unlinked: look again.
                backoff.spin();
                continue;
            };
            let head = leaf.head_ptr();
            // SAFETY: live.
            let h = unsafe { &*head };
            if h.is_tombstone() {
                return None;
            }
            let tomb = leaf.alloc_version(&w, h.version, None);
            // SAFETY: unpublished.
            unsafe { (*tomb).init_next(h.next()) };
            let bomb = AbortOnUnwind;
            leaf.set_head(&w, tomb);
            h.mark_superseded(&w);
            self.raw.len_add(-1);
            bomb.defuse();
            drop(w);
            // SAFETY: unlinked under the chain latch, exactly once.
            unsafe { retire_version(head, guard) };
            // SAFETY: non-null.
            return Some((leaf_ptr, unsafe { NonNull::new_unchecked(head) }));
        }
    }

    /// Unlinks `leaf` and its whole chain from the tree if `check` accepts
    /// it (§13, versioned leaves).
    ///
    /// The unlinker takes the ART latches (the parent's too if the unlink
    /// compacts), then the terminal chain latch. Under it, it runs `check`
    /// (which must not run user code) and kills the latch before the
    /// unlinking store: a writer that found the leaf earlier then fails to
    /// lock it and retries from the tree, so no version is ever written into
    /// an unlinked leaf. `len` drops by the liveness of the head.
    fn unlink_leaf(
        &self,
        leaf: NonNull<VersionedLeaf<K, V>>,
        check: impl Fn(&VersionedLeaf<K, V>) -> bool,
        guard: &crossbeam_epoch::Guard,
    ) -> Unlinked {
        // User code, outside every latch; the bytes come from the leaf itself
        // (Inv 10), which `guard` protects.
        // SAFETY: protected by `guard`.
        let key = unsafe { leaf.as_ref() }.key.as_bytes();
        // Set by `confirm`, which runs at most once: `Some(n)` if it accepted
        // a chain of `n` versions, `None` if it refused.
        let seen: Cell<Option<Option<usize>>> = Cell::new(None);
        let removed = self.raw.remove_confirmed(
            key,
            |c| c == leaf,
            |c| {
                seen.set(Some(None));
                // SAFETY: `c` is `leaf`, protected by `guard`.
                let l = unsafe { c.as_ref() };
                let w = l.chain_latch.lock()?;
                if !check(l) {
                    return None;
                }
                seen.set(Some(Some(chain(l.head()).count())));
                let live = !l.head().is_tombstone();
                w.kill();
                Some(isize::from(live))
            },
            guard,
        );
        match (removed, seen.get()) {
            (Some(_), Some(Some(n))) => Unlinked::Done(n),
            (Some(_), _) => unreachable!("confirm accepted without counting"),
            (None, Some(_)) => Unlinked::Refused,
            // Not reached: already unlinked by another thread, or not found
            // by its own key bytes.
            // SAFETY: protected by `guard`.
            (None, None) if unsafe { leaf.as_ref() }.chain_latch.is_dead() => Unlinked::Refused,
            (None, None) => Unlinked::Missing,
        }
    }

    /// Prunes the chain of `leaf` at `min_version` (§11.4). If its newest
    /// version is a tombstone at or below `min_version` (a built-in one, or a
    /// value `is_tombstone` accepts), no snapshot at or above `min_version`
    /// can see the key, and the whole leaf is unlinked (§13). Otherwise every
    /// version older than the newest one `<= min_version` is unlinked.
    /// Returns the number of versions unlinked.
    pub(crate) fn prune_leaf<F: Fn(&V) -> bool>(
        &self,
        leaf_ptr: NonNull<VersionedLeaf<K, V>>,
        min_version: u64,
        is_tombstone: &F,
        guard: &crossbeam_epoch::Guard,
    ) -> usize {
        // SAFETY: protected by `guard`.
        let leaf = unsafe { leaf_ptr.as_ref() };
        // Prune is best-effort maintenance: a chain that keeps moving (for
        // example, an `is_tombstone` that writes this key) is left alone
        // rather than retried forever.
        for _attempt in 0..64 {
            // 1. Without any latch, find T and evaluate the user closure on it.
            let head = leaf.head_ptr();
            // `t_ptr` comes from the chain links, not from a reference, so that
            // retiring it later deallocates with the allocation's provenance.
            let Some(t_ptr) = find_le_ptr(head, min_version) else {
                return 0;
            };
            // SAFETY: live.
            let t = unsafe { &*t_ptr };
            if t_ptr == head && t.value().is_none_or(is_tombstone) {
                // 2. A dead key: unlink it, if T is still its head.
                match self.unlink_leaf(leaf_ptr, |l| l.head_ptr() == t_ptr, guard) {
                    Unlinked::Done(n) => return n,
                    Unlinked::Refused if leaf.chain_latch.is_dead() => return 0,
                    // The head moved: start again.
                    Unlinked::Refused => continue,
                    // Trim the chain instead.
                    Unlinked::Missing => {}
                }
            }

            // 3. Re-check under the latch.
            let Some(w) = leaf.chain_latch.lock() else {
                // Unlinked meanwhile, by a remove or another prune.
                return 0;
            };
            let head_now = leaf.head_ptr();
            if find_le_ptr(head_now, min_version) != Some(t_ptr) || t.is_superseded() {
                drop(w);
                continue;
            }

            // 4. Detach everything older than T.
            let bomb = AbortOnUnwind;
            let mut unlinked: Vec<*mut VersionNode<V>> = Vec::new();
            let mut cur = t.next();
            t.set_next(&w, std::ptr::null_mut());
            while !cur.is_null() {
                // SAFETY: a detached node, immutable now (unreachable from head).
                let n = unsafe { &*cur };
                n.mark_superseded(&w);
                unlinked.push(cur);
                cur = n.next();
            }
            bomb.defuse();
            drop(w);

            // 5. Retire every detached heap node, exactly once.
            let count = unlinked.len();
            for n in unlinked {
                // SAFETY: unlinked under the chain latch by this call only.
                unsafe { retire_version(n, guard) };
            }
            return count;
        }
        0
    }

    /// Unlinks `key` and every version of it, for every snapshot (§13).
    /// Returns `false` if the key had no version.
    pub(crate) fn remove_key(&self, key: &[u8], guard: &crossbeam_epoch::Guard) -> bool {
        let mut backoff = SpinBackoff::new();
        loop {
            let Some(leaf) = self.raw.get(key) else {
                return false;
            };
            match self.unlink_leaf(leaf, |_| true, guard) {
                Unlinked::Done(_) => return true,
                Unlinked::Missing => return false,
                // Another thread is unlinking it: look again.
                Unlinked::Refused => backoff.spin(),
            }
        }
    }

    /// Unlinks exactly `version` of `key`, a value or a tombstone. If it was
    /// the key's only version, the key goes with it. Returns `false` if there
    /// was no such version.
    pub(crate) fn remove_version(
        &self,
        key: &[u8],
        version: u64,
        guard: &crossbeam_epoch::Guard,
    ) -> bool {
        let only = |l: &VersionedLeaf<K, V>| {
            let h = l.head();
            h.version == version && h.next().is_null()
        };
        let mut backoff = SpinBackoff::new();
        loop {
            let Some(leaf_ptr) = self.raw.get(key) else {
                return false;
            };
            // SAFETY: protected by `guard`.
            let leaf = unsafe { leaf_ptr.as_ref() };
            if only(leaf) {
                // The key's only version: unlink the whole leaf, since a
                // chain is never empty.
                match self.unlink_leaf(leaf_ptr, only, guard) {
                    Unlinked::Done(_) => return true,
                    Unlinked::Missing => return false,
                    Unlinked::Refused if leaf.chain_latch.is_dead() => {
                        backoff.spin();
                        continue;
                    }
                    // A version arrived: edit the chain below.
                    Unlinked::Refused => {}
                }
            }
            let Some(w) = leaf.chain_latch.lock() else {
                backoff.spin();
                continue;
            };
            // Positions are found under the latch.
            let head = leaf.head_ptr();
            let at = |p: *mut VersionNode<V>| -> Option<&VersionNode<V>> {
                // SAFETY: nodes reachable from `head` under the latch are live
                // and protected by `guard`; null is the end of the chain.
                unsafe { p.as_ref() }
            };
            let mut prev: *mut VersionNode<V> = std::ptr::null_mut();
            let mut cur = head;
            while let Some(n) = at(cur).filter(|n| n.version > version) {
                prev = cur;
                cur = n.next();
            }
            let Some(n) = at(cur).filter(|n| n.version == version) else {
                return false;
            };
            if prev.is_null() && n.next().is_null() {
                // It became the only version meanwhile.
                drop(w);
                continue;
            }
            // SAFETY: live.
            let old_live = !unsafe { &*head }.is_tombstone();
            let bomb = AbortOnUnwind;
            if prev.is_null() {
                leaf.set_head(&w, n.next());
            } else {
                // SAFETY: `prev` is a live node of this chain.
                unsafe { (*prev).set_next(&w, n.next()) };
            }
            n.mark_superseded(&w);
            let new_live = !leaf.head().is_tombstone();
            self.raw
                .len_add(isize::from(new_live) - isize::from(old_live));
            bomb.defuse();
            drop(w);
            // SAFETY: unlinked under the chain latch, exactly once.
            unsafe { retire_version(cur, guard) };
            return true;
        }
    }

    /// Removes every key (§9.8), killing each detached leaf's chain before
    /// counting its head, so no writer changes it afterwards.
    pub(crate) fn clear(&self, guard: &crossbeam_epoch::Guard) {
        self.raw.clear_counting(guard, |l| {
            // SAFETY: a detached leaf, protected by `guard`.
            let l = unsafe { l.as_ref() };
            let Some(w) = l.chain_latch.lock() else {
                debug_assert!(false, "only its node's latch holder kills a chain");
                return 0;
            };
            let live = !l.head().is_tombstone();
            w.kill();
            isize::from(live)
        });
    }

    /// Checks the tree's invariants at quiescence; `len` counts the keys
    /// whose newest version is live.
    pub(crate) fn validate(&mut self) {
        self.raw.validate_counting(|l| {
            // SAFETY: exclusive access (`&mut self`); a reachable leaf.
            usize::from(!unsafe { l.as_ref() }.head().is_tombstone())
        });
    }
}

/// Retires a heap version node; inline nodes are left to their leaf (D5).
///
/// # Safety
/// `n` is unlinked from its chain, marked superseded, and passed here once.
unsafe fn retire_version<V: Send + 'static>(
    n: *mut VersionNode<V>,
    guard: &crossbeam_epoch::Guard,
) {
    // SAFETY: `n` is live until retired.
    if unsafe { (*n).is_inline() } {
        return;
    }
    // SAFETY: a heap node from `Box::into_raw`, unlinked, retired once.
    retire(guard, unsafe {
        Retired::from_non_null(NonNull::new_unchecked(n))
    });
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::atomic::{AtomicBool, Ordering};
    use std::sync::Arc;

    /// §16.5 transient `len` for the versioned tree (Inv 12): a key whose
    /// head alternates between a value and a tombstone never shows a
    /// negative or over-counted raw counter.
    #[test]
    fn transient_len_never_negative() {
        let t = Arc::new(VersionedTree::<Vec<u8>, u64>::new());
        let stop = Arc::new(AtomicBool::new(false));
        let writer = {
            let (t, stop) = (Arc::clone(&t), Arc::clone(&stop));
            std::thread::spawn(move || {
                let n = if cfg!(miri) { 20 } else { 100_000 };
                let mut v = 1u64;
                while !stop.load(Ordering::Relaxed) && v < n {
                    let g = crate::guard::pin();
                    t.insert(vec![7], v, Some(v), &g);
                    t.insert(vec![7], v + 1, None, &g);
                    v += 2;
                }
            })
        };
        let polls = if cfg!(miri) { 50 } else { 200_000 };
        for _ in 0..polls {
            let len = t.raw.raw_len();
            assert!((0..=1).contains(&len), "raw len {len} out of range");
        }
        stop.store(true, Ordering::Relaxed);
        writer.join().unwrap();
        assert_eq!(t.raw.raw_len(), 0);
    }
}