Data structures notes [WIP]

[Bnaya]

Moving forward, seems like we need to implement self balancing binary search tree to be used for quite few parts of the library.
The difficulty would be how to make it generic to several nodes values types.

Allocator part 2

• part one mostly done
• TBW part 2

## Allocator part 1 _{(The allocator is an adaptation of [thing/malloc](https://github.com/thi-ng/umbrella/tree/develop/packages/malloc))}

• freelist
• one way linked list for used blocks
• one way linked list for free blocks
• blocks does not have their size on the end.
• freeing single pointer
  • Basically adding removing element from the used linked list and adding it to the used list
  • Is O(n), because we need to find the prev node. adding a back link can improve that significantly.
• merging adjacent free blocks is expensive, need to analyse exact complexity. (It's on by default on free)
  • To efficiently find the physical before block we can add the block size in the block end, to figure out if it's free or not we need a flag or another data structure for fast retrieval

object/map/set

• linked hashmap
• does not support deletion current position while iterating (js spec does support it 🥴)
• as long you don't need rehash you will be fine
  • Consider swapping it with a search tree to avoid rebalancing
• If we could add static-shaped objects that can be great
• If we can save the object shape separately - even better

String deduplication

• Only between strings on the same save operating using js Map
• Consider adding strings registry in a search tree