tree sort - Linux-audio-dev - lists.linuxaudio.org

Jens M Andreasen

16 Oct 16 Oct

11:06 a.m.

What you can do is, take an existing implementation and preallocate a fixed number of objects in a linked list, like a stack. Then you pop off the first object whereever there is a malloc() and push it on again whereever there is a free() On Sat, 2010-10-16 at 00:35 +0200, Lieven Moors wrote:

...

Hi everyone, I am looking for a self balancing binary tree implementation in C or C++ that I can use in the JACK proces callback. I was thinking about something like multiset in c++ (equal keys allowed), but that doesn't use dynamic memory allocation. Thanks for your help Greetings, Lieven _______________________________________________ Linux-audio-dev mailing list Linux-audio-dev(a)lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev

-- eins, zwei, drei ... tekno tekno?? http://www.youtube.com/watch?v=ZEgbW1FxR78

Reply

Jeremy

17 Oct 17 Oct

3:04 a.m.

On Sat, Oct 16, 2010 at 6:41 AM, lieven moors <lievenmoors(a)gmail.com> wrote:

...

On Sat, Oct 16, 2010 at 11:06:19AM +0200, Jens M Andreasen wrote:

What you can do is, take an existing implementation and preallocate a fixed number of objects in a linked list, like a stack. Then you pop off the first object whereever there is a malloc() and push it on again whereever there is a free()

Hi Jens, Thanks for the suggestion! That sounds exactly like what I want to do. Though I still wonder if there are any existing implementations out there that use the stack directly... Greetings, Lieven

On Sat, 2010-10-16 at 00:35 +0200, Lieven Moors wrote: > Hi everyone, > > I am looking for a self balancing binary tree implementation > in C or C++ that I can use in the JACK proces callback. > I was thinking about something like multiset in c++ (equal keys

allowed),

but that doesn't use dynamic memory allocation. Thanks for your help Greetings, Lieven _______________________________________________ Linux-audio-dev mailing list Linux-audio-dev(a)lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev

-- eins, zwei, drei ... tekno tekno?? http://www.youtube.com/watch?v=ZEgbW1FxR78

_______________________________________________ Linux-audio-dev mailing list Linux-audio-dev(a)lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev

Hi, I'm not sure if this will help you, but I wrote a fixed block size memory allocator which is really simple for the TI89 calculator. I wrote it a while ago, and I think I'm the only one who's actually used it till now, so it's not well tested, but it's available on google code: http://code.google.com/p/lardalloc/ It should fit your requirements, as it just uses the free blocks to implement a stack, and thus is really fast. The only problem you might encounter is that because implemented for a graphing calculator, it is limited to 2^16 blocks maximum. I wouldn't expect it to cause any problems running on a non-calculator platform, because it is written in standard C. Again, you'd still have to write a tree implementation on top of it. Jeremy

Reply

Lieven Moors

3:50 a.m.

On Sat, Oct 16, 2010 at 09:04:09PM -0400, Jeremy wrote:

...

On Sat, Oct 16, 2010 at 6:41 AM, lieven moors <lievenmoors(a)gmail.com> wrote:

On Sat, Oct 16, 2010 at 11:06:19AM +0200, Jens M Andreasen wrote:

What you can do is, take an existing implementation and preallocate a fixed number of objects in a linked list, like a stack. Then you pop off the first object whereever there is a malloc() and push it on again whereever there is a free()

Hi Jens, Thanks for the suggestion! That sounds exactly like what I want to do. Though I still wonder if there are any existing implementations out there that use the stack directly... Greetings, Lieven

On Sat, 2010-10-16 at 00:35 +0200, Lieven Moors wrote: > Hi everyone, > > I am looking for a self balancing binary tree implementation > in C or C++ that I can use in the JACK proces callback. > I was thinking about something like multiset in c++ (equal keys

allowed),

but that doesn't use dynamic memory allocation. Thanks for your help Greetings, Lieven _______________________________________________ Linux-audio-dev mailing list Linux-audio-dev(a)lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev

-- eins, zwei, drei ... tekno tekno?? http://www.youtube.com/watch?v=ZEgbW1FxR78

_______________________________________________ Linux-audio-dev mailing list Linux-audio-dev(a)lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev

Hi, I'm not sure if this will help you, but I wrote a fixed block size memory allocator which is really simple for the TI89 calculator. I wrote it a while ago, and I think I'm the only one who's actually used it till now, so it's not well tested, but it's available on google code: http://code.google.com/p/lardalloc/ It should fit your requirements, as it just uses the free blocks to implement a stack, and thus is really fast. The only problem you might encounter is that because implemented for a graphing calculator, it is limited to 2^16 blocks maximum. I wouldn't expect it to cause any problems running on a non-calculator platform, because it is written in standard C. Again, you'd still have to write a tree implementation on top of it. Jeremy

Hi Jeremy, Thanks for the link. I think that when I would do this properly, I would have to use a proper memory pool, which I was just reading about on Boost site. But since I'm still learning the basics, and I want to keep it simple, i will preallocate a list, and use that as a memory pool. But I will certainly have a look at your code, and see if I can use it. Thanks again, Greetings, Lieven

Reply