]> git.bitcoin.ninja Git - rust-lightning/commit
Add a new `IndexedMap` type and use it in network graph storage
authorMatt Corallo <git@bluematt.me>
Tue, 25 Oct 2022 03:50:07 +0000 (03:50 +0000)
committerMatt Corallo <git@bluematt.me>
Wed, 25 Jan 2023 18:58:51 +0000 (18:58 +0000)
commit1bd35367d8495d9a8b90f5de0f02b68014523e3b
treef7b84491c9740a44022fbc1c0f55887ff2a280fc
parenta3f7b790b45698ccc33d9f08265a1863688c08fe
Add a new `IndexedMap` type and use it in network graph storage

Our network graph has to be iterable in a deterministic order and
with the ability to iterate over a specific range. Thus,
historically, we've used a `BTreeMap` to do the iteration. This is
fine, except our map needs to also provide high performance lookups
in order to make route-finding fast. Sadly, `BTreeMap`s are quite
slow due to the branching penalty.

Here we replace the `BTreeMap`s in the scorer with a dummy wrapper.
In the next commit the internals thereof will be replaced with a
`HashMap`-based implementation.
lightning/src/routing/gossip.rs
lightning/src/routing/router.rs
lightning/src/util/indexed_map.rs [new file with mode: 0644]
lightning/src/util/mod.rs