bitcoindevkit / bdk / 12270472655

79%

Build Type

push

github

Committed by evanlinjin

Commit Message

Merge bitcoindevkit/bdk#1670: Introduce `O(n)` canonicalization algorithm

956d0a93b test(chain): Update test docs to stop referencing `get_chain_position` (志宇)
1508ae3db chore: Fix typos (志宇)
af92199b6 refactor(wallet): Reuse chain position instead of obtaining new one (Jiri Jakes)
caa0f13d4 docs(wallet): Explain `.take` usage (志宇)
119640590 refactor(chain): Reorganize `TxGraph::insert_anchor` logic for clarity (志宇)
4706315e8 chore(chain): Address `CanonicalIter` nitpicks (志宇)
68f7b7724 test(chain): Add canonicalization test (志宇)
da0c43ed9 refactor(chain)!: Rename `LastSeenIn` to `ObservedIn` (志宇)
d4102b4b6 perf(chain): add benchmarks for canonicalization logic (志宇)
e34024cd5 feat(chain): Derive `Clone` on `IndexedTxGraph` (志宇)
e9854455c docs: Add ADR for `O(n)` canonicalization algorithm (志宇)
4325e2c25 test(chain): Add transitive anchor tests (志宇)
8fbee12b1 feat(chain)!: rm `get_chain_position` and associated methods (志宇)
582d6b51f feat(chain)!: `O(n)` canonicalization algorithm (志宇)
f6192a615 feat(chain)!: Add `run_until_finished` methods (志宇)
0aa39f9e1 feat(chain)!: `TxGraph` contain anchors in one field (志宇)

Pull request description:

  Fixes #1665
  Replaces #1659

  ### Description

  Previously, getting the canonical history of transactions/UTXOs required calling `TxGraph::get_chain_position` on each transaction. This was highly inefficient and resulted in an `O(n^2)` algorithm. The situation is especially problematic when we have many unconfirmed conflict... (continued)

Run Details

386 of 402 new or added lines in 4 files covered. (96.02%)

13 existing lines in 2 files now uncovered.

11927 of 14239 relevant lines covered (83.76%)

19638.19 hits per line