Separate CClaimTrie into trie implementation and ClaimTrie / Write base template trie class #108

New issue

Closed

opened 2018-03-19 20:59:47 +01:00 by kaykurokawa · 3 comments

kaykurokawa commented

2018-03-19 20:59:47 +01:00

(Migrated from github.com)

The CClaimTrie class, which implements the Claim Trie, has a tight integration between the trie data structure and the logic involved in claims.

It would be nice if we had a base template trie class which the CClaimTrie class either inherits from, or used as a member variable (CClaimTrie would either way use a trie class where the node are CClaimTrieNodes). This will improve code readability and allow us to write unit tests exclusively for the trie class to verify its correctness instead of relying on integration tests.

Also, it will allow easier implementation of https://github.com/lbryio/lbrycrd/issues/106, as we should just be able to switch out the trie class while keeping the logic for claims intact.

The CClaimTrie class, which implements the Claim Trie, has a tight integration between the trie data structure and the logic involved in claims. It would be nice if we had a base template trie class which the CClaimTrie class either inherits from, or used as a member variable (CClaimTrie would either way use a trie class where the node are CClaimTrieNodes). This will improve code readability and allow us to write unit tests exclusively for the trie class to verify its correctness instead of relying on integration tests. Also, it will allow easier implementation of https://github.com/lbryio/lbrycrd/issues/106, as we should just be able to switch out the trie class while keeping the logic for claims intact.

👍 1

snugchaise commented

2018-03-20 10:21:44 +01:00

(Migrated from github.com)

I checked the class today, is there any way to find out which methods are responsible for the trie data structure and which ones are for the claim logic? Or that is kind of intuitive?

kaykurokawa commented

2018-03-21 19:11:31 +01:00

(Migrated from github.com)

It's not intuitive at all (which is part of the problem) so here's some more details.

The "trie" data structure is your standard trie (aka prefix tie/digital trie) https://en.wikipedia.org/wiki/Trie . As far as I know, there is no deviation between the standard implementation and what we have implemented. Here are the important functions for this trie data structure that we use:

There is an insert() function implemented by updateName() which either adds a new node to the trie or replaces the old node with a new one: https://github.com/lbryio/lbrycrd/blob/master/src/claimtrie.cpp#L834

There is a find() / iterator (the iterator is left to right) function that traverses through the trie which is not implemented anywhere , but an example can be found here: https://github.com/lbryio/lbrycrd/blob/master/src/claimtrie.cpp#L915 (this kind of code is duplicated elsewhere and violates DRY principles) .

There is a erase() function which is implemented here that deletes a node and all its descendants https://github.com/lbryio/lbrycrd/blob/master/src/claimtrie.cpp#L879

Hope that makes a bit more sense.

It's not intuitive at all (which is part of the problem) so here's some more details. The "trie" data structure is your standard trie (aka prefix tie/digital trie) https://en.wikipedia.org/wiki/Trie . As far as I know, there is no deviation between the standard implementation and what we have implemented. Here are the important functions for this trie data structure that we use: There is an insert() function implemented by updateName() which either adds a new node to the trie or replaces the old node with a new one: https://github.com/lbryio/lbrycrd/blob/master/src/claimtrie.cpp#L834 There is a find() / iterator (the iterator is left to right) function that traverses through the trie which is not implemented anywhere , but an example can be found here: https://github.com/lbryio/lbrycrd/blob/master/src/claimtrie.cpp#L915 (this kind of code is duplicated elsewhere and violates DRY principles) . There is a erase() function which is implemented here that deletes a node and all its descendants https://github.com/lbryio/lbrycrd/blob/master/src/claimtrie.cpp#L879 Hope that makes a bit more sense.

technovelist commented

2018-03-21 20:20:01 +01:00

(Migrated from github.com)

I'm working on replacing the trie data structure with one from ethereum. When I do that, I'll separate the claim logic structure from the trie itself.

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: LBRYCommunity/lbrycrd#108

No description provided.

Rows
Columns