#arena #generation #linked-list

no-std triple_arena

Regular, Chain, Surjection, and Ordered Arenas supporting non-Clone types, deletion, and more

16 releases (breaking)

0.13.0 Feb 20, 2024
0.12.1 Aug 29, 2023
0.11.0 Aug 20, 2023
0.9.0 Jun 5, 2023
0.1.0 Jun 2, 2021

#149 in Memory management

Download history 123/week @ 2024-07-20 55/week @ 2024-07-27 64/week @ 2024-08-03 43/week @ 2024-08-10 142/week @ 2024-08-17 52/week @ 2024-08-24 53/week @ 2024-08-31 86/week @ 2024-09-07 101/week @ 2024-09-14 137/week @ 2024-09-21 47/week @ 2024-09-28 72/week @ 2024-10-05 45/week @ 2024-10-12 35/week @ 2024-10-19 45/week @ 2024-10-26 77/week @ 2024-11-02

222 downloads per month
Used in 9 crates (3 directly)

MIT/Apache

365KB
7K SLoC

Triple Arena

Provides 4 very flexible arena types. All support non-Clone entry insertion and deletion. All are indexable with a P: Ptr generic, which contains an optional generation counter to check for invalidity (zero cost when omitted). no_std compatible.

  • Arena<P, T> is the basic unassociated and nonhereditary arena type
  • ChainArena<P, T> allows associating entries together into multiple linear or cyclic chains, representing an idealized doubly linked list stored on an arena
  • SurjectArena<P, K, V> is a special kind of union-find data structure that can associate key entries into nonhereditary sets with a common value entry
  • OrdArena<P, K, V> is a fusion between an ordered balanced tree and an arena. All entries are key and value pairs that are all ordered by the key. Hereditary and nonhereditary insertion is supported. Unlike most BTreeMaps and HashMaps, the P: Ptr references to entries are stable, and can be trivially reused for O(1) operations.

Dependencies