Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Collapse prev_sybling and last_child into prev_cyclic_sybling #12

Open
matklad opened this issue Jul 2, 2018 · 2 comments
Open

Collapse prev_sybling and last_child into prev_cyclic_sybling #12

matklad opened this issue Jul 2, 2018 · 2 comments
Labels
enhancement help wanted

Comments

@matklad
Copy link

matklad commented Jul 2, 2018 •
edited
Loading

See "Data structures for the document object model" http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html section for a neat trick to save one pointer per node while maintaining O(1) operations.
@saschagrunert
Copy link
Owner

Cool, thank you for the input. I will take this into consideration.

@lo48576 lo48576 mentioned this issue Aug 3, 2019
Merged
lo48576 added a commit to lo48576/indextree that referenced this issue Aug 4, 2019
@lo48576
Use cyclic previous sibling technique
98e9d1e 
See <http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html>.
Note that, by this implementation, node insersions and removals are not
O(1) for top-level nodes.

Fixes saschagrunert#12.
@lo48576 lo48576 mentioned this issue Aug 4, 2019
Closed
lo48576 added a commit to lo48576/indextree that referenced this issue Aug 4, 2019
@lo48576
Use cyclic previous sibling technique
64c8ce1 
See <http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html>.
Note that, by this implementation, node insersions and removals are not
O(1) for top-level nodes.

Fixes saschagrunert#12.
lo48576 added a commit to lo48576/indextree that referenced this issue Aug 4, 2019
@lo48576
Use cyclic previous sibling technique
b52dcf7 
See <http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html>.
Note that, by this implementation, node insersions and removals are not
O(1) for top-level nodes.

Fixes saschagrunert#12.
lo48576 added a commit to lo48576/indextree that referenced this issue Aug 4, 2019
@lo48576
Use cyclic previous sibling technique
7eaed19 
See <http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html>.
Note that, by this implementation, node insersions and removals are not
O(1) for top-level nodes.

Fixes saschagrunert#12.
lo48576 added a commit to lo48576/indextree that referenced this issue Aug 4, 2019
@lo48576
Use cyclic previous sibling technique
7469076 
See <http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html>.
Note that, by this implementation, node insersions and removals are not
O(1) for top-level nodes.

Fixes saschagrunert#12.
@lo48576
Copy link
Contributor

lo48576 commented Sep 16, 2019

As I wrote in #38 (comment), I don't like this trick, because it makes things complex for both internal implementation and library users.

To reduce memory consumption, I like another method to make node ID a type parameter, as string-interner crate does (by Symbol trait).
This won't affect core logic, and users can choose balance between memory consumption and number of nodes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement help wanted
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@saschagrunert @lo48576 @matklad