search

gnolang / gno

Gno: An interpreted, stack-based Go virtual machine to build succinct and composable apps + gno.land: a blockchain for timeless code and fair open-source.
https://gno.land/
Other
899 stars 377 forks source link

feat: A fully featured btree implementation #3126

Open wyhaines opened 1 week ago

wyhaines commented 1 week ago

This is a fully featured btree implementation. A friend gave me some incomplete (and broken) btree code for Go, and when I started reworking it, I discovered that it was a broken semi-copy of an old version of Google's btree for Go.

I finished reworking it so that it adhere's to that original Google version's API, though there are some differences internally in places, and I think that my version is much easier to follow and to understand.

This implementation is quite a bit faster than the AVL tree. I will add links to some benchmarks that I did in a comment. This implementation supports copy-on-write for the trees, for inexpensively creating copies of a tree that are effectively isolated from each other with respect to changes that happen after the fork.

Contributors' checklist... - [x] Added new tests, or not needed, or not feasible - [x] Provided an example (e.g. screenshot) to aid review or the PR is self-explanatory - [x] Updated the official documentation or not needed - [x] No breaking changes were made, or a `BREAKING CHANGE: xxx` message was included in the description - [ ] Added references to related issues and PRs - [ ] Provided any useful hints for running manual tests
n0izn0iz commented 1 week ago

Thanks! I need this for that https://github.com/TERITORI/teritori-dapp/blob/2a5c8390438e6aad332f71410bcf8aabaaecab4b/gno/p/havl/havl.gno#L18 :D

codecov[bot] commented 1 week ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

:loudspeaker: Thoughts on this report? Let us know!

notJoon commented 1 week ago

related with #3021