Splay trees

This forum is for general developer support questions.

Splay trees

Postby chris » Tue Sep 01, 2015 2:57 pm

I'd like to use utility.library's splay tree functions. I've looked at them in the past and decided they weren't ideal at that time (probably lucky as looks like they were broken for ages), however I've now bothered to try them I've remembered why they weren't ideal...

What I need to be able to do is deallocate some resources when the tree is destroyed. I can't see any way of adding a callback when node are deleted, so this causes a big memory leak problem.

Is there any way to parse through an entire tree? I'd like to periodically trim the branches to avoid excessive memory usage.

If there's no way around these, I see btree.library would work, but it doesn't support splay trees (although a binary tree would still be better than what I have been using). Are there any other splay tree or similar implementations that are GPL or in an Amiga shared library that might be better for me?
chris
 
Posts: 551
Joined: Sat Jun 18, 2011 12:05 pm

Re: Splay trees

Postby salass00 » Fri Sep 11, 2015 2:47 pm

chris wrote:What I need to be able to do is deallocate some resources when the tree is destroyed. I can't see any way of adding a callback when node are deleted, so this causes a big memory leak problem.


Why not just use a memory pool for these allocations that you then free just after freeing the splay tree?

Is there any way to parse through an entire tree? I'd like to periodically trim the branches to avoid excessive memory usage.


If the purpose is to remove nodes that haven't been accessed in a while you could use an LRU list for this.

Are there any other splay tree or similar implementations that are GPL or in an Amiga shared library that might be better for me?


https://github.com/salass00/ntfs-3g/blo ... playtree.c
User avatar
salass00
AmigaOS Core Developer
AmigaOS Core Developer
 
Posts: 502
Joined: Sat Jun 18, 2011 4:12 pm
Location: Finland

Re: Splay trees

Postby chris » Fri Sep 11, 2015 3:32 pm

salass00 wrote:
chris wrote:What I need to be able to do is deallocate some resources when the tree is destroyed. I can't see any way of adding a callback when node are deleted, so this causes a big memory leak problem.


Why not just use a memory pool for these allocations that you then free just after freeing the splay tree?


It's not just plain memory, I have other pointers in my SplayNode which need freeing using other OS calls.

Is there any way to parse through an entire tree? I'd like to periodically trim the branches to avoid excessive memory usage.


If the purpose is to remove nodes that haven't been accessed in a while you could use an LRU list for this.


Sort of what I was doing anyway. I suppose I could keep the current list and use that to remove the nodes... should work.

Are there any other splay tree or similar implementations that are GPL or in an Amiga shared library that might be better for me?


https://github.com/salass00/ntfs-3g/blo ... playtree.c

[/quote]

That looks... actually identical to the one in utility.library, but at least I can modify it so that should solve the main problem, thanks.
chris
 
Posts: 551
Joined: Sat Jun 18, 2011 12:05 pm


Return to General Developer Support

Who is online

Users browsing this forum: No registered users and 2 guests