Splay trees

This forum is for general developer support questions.
Post Reply
chris
Posts: 562
Joined: Sat Jun 18, 2011 11:05 am
Contact:

Splay trees

Post by chris »

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?
User avatar
salass00
AmigaOS Core Developer
AmigaOS Core Developer
Posts: 530
Joined: Sat Jun 18, 2011 3:12 pm
Location: Finland
Contact:

Re: Splay trees

Post by salass00 »

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
chris
Posts: 562
Joined: Sat Jun 18, 2011 11:05 am
Contact:

Re: Splay trees

Post by chris »

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.
Post Reply