getIndexInParent method

int getIndexInParent(TKey key)

Returns the zero-based index of key within the live sibling list of its parent (or the live root list, if key is a root). Returns -1 if key is not present or is itself pending deletion.

Live-space: not full-list-space: so the returned index directly matches positions in liveRootKeys / getLiveChildren and the input space of reorderRoots / reorderChildren.

O(1) amortized: answers come from _liveIndexCache; the first read against a list after any mutation refreshes that whole list in one pass, and every subsequent read is a stamp check until the next mutation anywhere. The slot-stamp check makes the read safe even when a parent link and its sibling list transiently disagree mid-mutation (the stale slot reads -1, same as the old scan's miss).

Implementation

int getIndexInParent(TKey key) {
  if (!_hasKey(key) || _isPendingDeletion(key)) return -1;
  final parent = _parentKeyOfKey(key);
  final int parentNid = parent == null ? kRootListParentNid : nidOf(parent);
  if (!_liveIndexCache.isParentFresh(parentNid)) {
    final List<TKey> full = parent == null
        ? _roots
        : (_childListOf(parent) ?? const []);
    _liveIndexCache.beginRefresh(parentNid);
    int liveIndex = 0;
    for (final k in full) {
      debugIndexInParentIterationCount++;
      if (_isPendingDeletion(k)) continue;
      _liveIndexCache.writeSlot(nidOf(k), liveIndex);
      liveIndex++;
    }
  }
  final int result = _liveIndexCache.readSlot(nidOf(key));
  assert(() {
    if (debugFullConsistencyChecks) {
      final int scanned = _debugScanIndexInParent(key);
      assert(
        result == scanned,
        "live-index cache diverged for $key: cached $result, scan "
        "$scanned (a mutation path is missing its bump)",
      );
    }
    return true;
  }());
  return result;
}