new trie

[cheme]

Opening this PR to prepare the branch to start the new repo (not for merge here).

Based on https://github.com/paritytech/trie/tree/arkpar/new-trie

Substrate branch: https://github.com/cheme/polkadot-sdk/tree/cheme/new-trie also based on https://github.com/paritytech/polkadot-sdk/tree/arkpar/new-trie

[cheme]

Basically we can't cache a node before we know its location info. Otherwise if we add a node with no location info, it may be later retrieved from the cache and the database will fail to locate children.

I see, probably some things to do in the future, but seems better to start this way.

[cheme]

Might be a good idea to rename this to NodeDB or NodeStore at this point

Question, if we do a new trie crate, suposedly with a new name. We would need a new hashdb crate (so nodedb), a new memory-db crate (no idea for the name here) and also a new trie-bench. Trie_root would not really need a new name.

Or just keeping old name and using new repo would be the idea (would make previous crate publishing difficult)?

[cheme]

new memory-db crate (no idea for the name here) : mem-node-db maybe

[arkpar]

The new repo is supposed to be this: https://github.com/paritytech/subtrie

Also, I guess we can put everythung into a single crate for simplicity. memry-db and hash-db are not that useful on their own.

[cheme]

The new repo is supposed to be this: https://github.com/paritytech/subtrie

Also, I guess we can put everythung into a single crate for simplicity. memry-db and hash-db are not that useful on their own.

yes, can be this way, all are supposed to support no_std and none declare an alloc, will try after doing all review changes

[cheme]

In https://github.com/paritytech/trie/pull/210/commits/28a5476ac9b30faff2eb650e1c21740ca9d0d0a9 I did merge the memory db mem tree db and hash db crate in trie one. Looks good I think, except I chose to keep using Hasher trait from old hash_db (but I deleted the dep in the project as it should be very stable and only this trait would be used). When trying to use Hasher in trie-db crate I end up needing keccack hasher to depend on triedb, but is use in memorydb test so I moved memorydb test to trie-db-test, but then I all private field access are problematic.

Another way to do it would be to move keccak hasher and trie root in triedb, maybe it is a good idea actually, may do tomorrow (only bad point is that we duplicate code here, I mean old crate and new crate, so not totally sure). Maybe also trie-bench.

[cheme]

In https://github.com/paritytech/trie/pull/210/commits/554187bd82e8b3db5ae5463395d74e8720fb65f3 I did remove lot of crates, only keeping h256. I could have kept trie-root, but then old crates like hash-db would have been added to dependencies in substrate. keccak hasher is a bit awkward, could use a real test hasher (with no dependency) in place but tiny keccak should be behind a feature.

[cheme]

Also did flatten the crate hieriarchy since there is not many left.