search

tezc / sc

Common libraries and data structures for C.
BSD 3-Clause "New" or "Revised" License
2.25k stars 243 forks source link

Any plans on implementing AVL tree? #90

Open germaniuss opened 2 years ago

germaniuss commented 2 years ago

I was in need of a simple string map data structure that would be alphabetically sorted, however the only map implementation in here is a simple hash map. I was wondering if there are any plans to implement an ordered map in the form of an AVL tree? I ended up using another random implementation I found on github though I would've loved to use this library since it's awesome and I use it for everything else.

tezc commented 2 years ago

I agree a tree implementation is missing in the toolset :)

Currently, there is no plan for it. There is a bplus tree which I couldn't publish due to licensing but I was told that I can open source it after 2022. So, I guess, I'll add it by the end of this year. Not sure if it helps you though.

germaniuss commented 2 years ago

Well for now I'll use the other tree implementation I found. On another note is there anything in the library that can be used as a shared semaphore between processes. Kind of like semaphore.h on POSIX systems.

tezc commented 2 years ago

Sorry, there is nothing for inter-process communication.

germaniuss commented 2 years ago

That's fine I might just change the mutex implementation a little and use the mmap to store it. Thanks for your time anyways!

iz0eyj commented 1 year ago

Here you can find a non-recursive implementation of the AVL Tree that is well done and simple to adapt to your needs.

https://github.com/xieqing/avl-tree

MykolaKovalyk commented 1 month ago

@tezc Any updates on this? A b+ tree would be nice too.

tezc commented 1 month ago

@MykolaKovalyk Unfortunately, I could not open source the b+ tree implementation I mentioned above (I was not allowed).

Whenever I have some free time, I'll check if I can come up with a new tree implementation. I try to make these libraries short, fast and easy to use. Hope I can achieve these goals with a tree implementation, let me experiment a bit.