onflow / atree

Atree provides scalable arrays and scalable ordered maps.
https://onflow.org
Apache License 2.0
39 stars 13 forks source link

Refactor encoding version and flag to add more flags #338

Closed fxamacker closed 10 months ago

fxamacker commented 10 months ago

Updates #292 https://github.com/onflow/flow-go/issues/1744

Changes:

Currently, version number uses 1 byte and flags uses 1 byte.

We don't need 255 versions but we need more flags now in order to support atree inlining.

For now, reserve the first 4 bits for version (0-15), but also reserve the 5th bit separately so in the future, we can decide if we want to use 5th bit to have more versions (0-31) or a new flag.

So the first byte has (beginning with top bit): 1-4: version (0 to 15) and version 1 only uses 4th bit. 5: reserved to provide 16 more versions or another flag 6: reserved (use this for next new flag if needed) 7: slab has next slab ID (only relevant for data slab) 8: slab has inlined slabs (for atree inlining)

Atree inlining bumps version from 0 to 1. The top bit won't be needed until version 7, so it can be used to change this layout in the future if needed.

This PR is backward compatible and simpler than alternatives (e.g. doesn't reverse top bits, etc.).


codecov-commenter commented 10 months ago

Codecov Report

Patch coverage: 62.23% and project coverage change: -0.40% :warning:

Comparison is base (74e19aa) 65.24% compared to head (a5c7323) 64.84%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #338 +/- ## ========================================== - Coverage 65.24% 64.84% -0.40% ========================================== Files 14 14 Lines 8761 8787 +26 ========================================== - Hits 5716 5698 -18 - Misses 2327 2356 +29 - Partials 718 733 +15 ``` | [Files Changed](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow) | Coverage Δ | | |---|---|---| | [basicarray.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-YmFzaWNhcnJheS5nbw==) | `49.36% <14.28%> (-0.42%)` | :arrow_down: | | [slab.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-c2xhYi5nbw==) | `66.66% <40.00%> (-33.34%)` | :arrow_down: | | [storable\_slab.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-c3RvcmFibGVfc2xhYi5nbw==) | `27.53% <50.00%> (-4.35%)` | :arrow_down: | | [encode.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-ZW5jb2RlLmdv) | `76.47% <57.14%> (-2.90%)` | :arrow_down: | | [array.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-YXJyYXkuZ28=) | `69.91% <60.25%> (-0.63%)` | :arrow_down: | | [map.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-bWFwLmdv) | `67.05% <64.10%> (-0.31%)` | :arrow_down: | | [flag.go](https://app.codecov.io/gh/onflow/atree/pull/338?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-ZmxhZy5nbw==) | `74.21% <72.61%> (-2.06%)` | :arrow_down: |

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.