Skip to content

[SortedSet] Fix subtreeCount inconsistency after remove at index#502

Merged
lorentey merged 1 commit intoapple:mainfrom
brianchang928:main
Aug 12, 2025
Merged

[SortedSet] Fix subtreeCount inconsistency after remove at index#502
lorentey merged 1 commit intoapple:mainfrom
brianchang928:main

Conversation

@brianchang928
Copy link
Copy Markdown
Contributor

@brianchang928 brianchang928 commented Aug 1, 2025

This PR fixes an issue where calling remove(at:) on a SortedSet would correctly remove the element but fail to update the set’s count, leading to inconsistency between the actual contents and the reported size of the set.

The root cause was a missing update to the internal B-Tree node’s subtreeCount when removing an element from a node's child node. This PR ensures the internal node properly decrements its subtreeCount after removal, keeping the tree metadata consistent.

Resolves #441

Checklist

  • I've read the Contribution Guidelines
  • My contributions are licensed under the Swift license.
  • I've followed the coding style of the rest of the project.
  • I've added tests covering all new code paths my change adds to the project (if appropriate).
  • I've added benchmarks covering new functionality (if appropriate).
  • I've verified that my change does not break any existing tests or introduce unexplained benchmark regressions.
  • I've updated the documentation if necessary.

Previously, when removing an element from a child node, the subtreeCount
of the current internal node wasn't updated, leading to incorrect counts.
@brianchang928 brianchang928 requested a review from lorentey as a code owner August 1, 2025 14:53
Copy link
Copy Markdown
Member

@lorentey lorentey left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks! 👍

@lorentey
Copy link
Copy Markdown
Member

@swift-ci test

@lorentey lorentey merged commit 990d4b3 into apple:main Aug 12, 2025
25 checks passed
@lorentey lorentey added this to the 1.3.0 milestone Sep 27, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

SortedSet remove at index does not work

2 participants