OSDev.org

Hey people, I've finally managed to implement the AVL Data structure in a way that I am happy with.

It took me a long time, but I've finally done it. So, in the spirit of goodwill and all that jazz, I'm placing my implementation up here for people to learn from, modify, whatever.

If you do modify the source, please send me a copy of the updates. You can append your name to the source headers. If changes are made, please create a changelog. That would be much appreciated.

It is ZC-App AVL.

The code is broken up into multiple files, so that it can be dealt with much easier. The source follows the

Node Convention.
http://zenobit.asmhackers.net/nr_doc_code_standard.html

So far... this is what I have tested.
- Sequential insertion (0 up to 0xFFFF)
- Sequential insertion (0x10000 to 0x1)
- Random Insertion (of 0x10000 random keys)

- Deletion
- Tree destruction via repeated deletion of Root node.
- Tree destruction via repeated deletion of tree's minimum value.
- Tree destruction via repeated deletion of tree's maximum value.
- Tree destruction via repeated deletion of random nodes.
- Sequential deletion (0x0 to 0xFFFF)
- Sequential deletion (0x10000 to 0x1)

And... some code statistics:
- Compiled successfully under DevC++ 4.9 and GCC 3.4.3 - 3.4.6
- C99 Standard.
- Raw code < 300 lines.
- Iterative implementation, using parent links.
- No stacks in use for tracing balance-update paths.

If anyone finds this at all useful, it means a couple months of my life HASNT been wasted. So, that would be neat.

Anywho, Enjoy!
~zeii.[/url]

No feedback at all?

~Zeii

What's AVL...

pcmattman wrote:What's AVL...

...and that has 4 stars below his name...

Seriously, I'm happy enough with the fact that you managed to get it to work. Since my OS languages are assembly and basic, I doubt your code will be of much use to me, but thanks for the offer anyway.

Oh and, nice work

Combuster wrote:

pcmattman wrote:What's AVL...

...and that has 4 stars below his name...

Seriously, I'm happy enough with the fact that you managed to get it to work. Since my OS languages are assembly and basic, I doubt your code will be of much use to me, but thanks for the offer anyway.

Oh and, nice work

... 4 stars because I take the effort to, after posting such a post, research AVL trees.

Well done on your achievment, zeii... Never believe you've wasted time, you'll probably find a good use for them later. I wrote a full linked list system that took forever to figure out but just today I basically copy-and-pasted it into my OS code and now I can use linked lists - the only thing I need to change are function names and type names (and there was also an unreferenced symbol, _memmove, but I implemented it). I like OS-independent code, and if yours is OS-independent I might find good use for it.

Edit: BTW, if you can find a context in which I could use your code in my OS I would be happy to try to implement it and tell you the results.

Thanks guys

Although, you might not want to use it juuuust yet. Ive discovered a bug that I am yet to squish.

Was bored, so I started doing more tests. Insertion of whatever number of nodes, works fine.

Buuuut... Deletion seems to die out when testing with 0xFFF nodes. Im trying to find out why. Ill keep you guys posted!

Weirdly enough, deletion works fine with 0xEFF nodes.

~zeii

Alrighty! Ze bug has been squished.
Well and truly, man I feel so very satisfied.

Bug was a mistake in logic, tried to use a pointer after I had invalidated it. Kinda impressive that the Program lasted as long as it did.

In any case, I will upload ZC-AVL 0.7 in a few minutes.

I have tested up to 16,777,215 Nodes. I will try and test a higher number later on.

While pondering over coffee, I had an interesting idea that I would particularly like opinions on.

The idea is... Solar is making a portable C Lib, rrrriiight? I should make a portable ADT library!

That way, more people can use exotic and useful data structures, without seriously agonizing pain.

The kinds of data structures I would include in the library would be along the lines of :

- Binary Search tree.
- AVL Tree.
- Redblack Tree.
- Stacks.
- Linked List (Singly and Doubly linked)
- Queues. (FIFO, Priorty Queue, D-Queue)
- Heap
- Maybe basic hash tables?
- Others that people would find useful?

If I made such a library, I would go to serious effort to make it support whatever Node structure you would feed it, that being said, the library would support a certain Node format (It could just be the first field of whatever Node structure you come up with). But... We can ponder this at a later time, should the idea be supported.

Library would also support a variety of allocation / deallocation methods.
It could use a Wrapper for allocation / deallocation, that way - youd just have to rewrite the wrapper or something, instead of the entire library.

*Shrug*

Anywho, Bugs fixed.
~zeii

I decided to post this too, simply because I think its pretty.

http://homepages.ihug.co.nz/~scroodle/avlpic.PNG

EDIT: Linked to the Image, because it was way, way too wide!

~Zeii.

Now, ADT implementations become interesting when you can run modifications asynchronously...

Combuster wrote:Now, ADT implementations become interesting when you can run modifications asynchronously...

Indeed, though I don't think a balanced tree can easily support purely lock-free synchronization (I could be wrong) but at least the ability to lock only the relevant parts of the tree would be nice. OTOH, depending on what you use the tree for, that could just result in unacceptable amounts of useless overhead compared to simple reader-writer locking for the whole tree..

zeii wrote: I decided to post this too, simply because I think its pretty.

Uhm.. you could have made it a little less wide.. now it breaks my layout (though that's forum's stylesheets fault really). Anyway, what program did you use to render the tree (or well, what library did the drawing)? I mean, if you rendered it directly in anti-aliased form, then the library you used has serious issues with gamma correction (though what do I complain, my own lib still suffers from this as well, should fix it "really soon now").

Self written program to render the tree, using the SDL/SDL_GFX libraries.
Yeah, I agree. The Anti-aliasing isnt so hot. However, that could be because I saved the .png on another computer, using MS Paint.

With the ADT Library thing im pondering, I wouldnt provide any really, really fancy locking type stuff, Id leave that for people to add should they wish to. My library would simply provide either a) A tested framework of ADTs, that people could use / modify as they needed. b) A bunch of handy ADTs that people could use, should they be lazy or not have the knowledge to implement them, themselves.

Advice / Thoughts on the ADT Library idea would be appreciated. I recently bought a domain and setup a server and I want to make use of it in some way that can be useful to the OS Deving public.

I was just pondering about how I could handle Memory management in a really, really ... uncoupled way for the ADT Library. Personally, I would just make a few Wrapper functions, that someone would modify, then compile the Library.

Wrappers for:
- Block Allocation of arbitrary size. (to provide an interface between the library and whatever Kernel's malloc-ish thing) (My system is largely incompatible with Mallocish ideas, so... by default the library would probably interface with Keeper).

- Page / Page Group allocation. (To provide the Library with an interface to allocate large chunks of memory, efficiently, should the Library need to).

Alternatively, The Library could just have two wrappers, that would need to be modified.

- allocate_block (takes a single parameter, holding the allocation size, hopefully returns a valid pointer to a memory block of that size...)

- allocate_page (takes no parameters, hopefully returns a pointer to a page the library can use.)

This way, the person using the library can decide like ... "Oh, I want page allocations to come strictly from Virtualized memory..." or whatever.

Of course, the Library would be entirely open-source, so... people here could totally mess with it, to add whatever needed locking mechanisms.

Sorry about the picture Mystran, I can invalidate the link if youd like.
~zeii

zeii wrote:Self written program to render the tree, using the SDL/SDL_GFX libraries.
Yeah, I agree. The Anti-aliasing isnt so hot. However, that could be because I saved the .png on another computer, using MS Paint.

Nah, it's just rendering without taking into account that typical desktop gamma is somewhere around 2.0 to 2.2. Instead it's rendering with the assumption that gamma is 1.0 (twice as big color value gives twice as bright pixel).

The result is that when you have a 1-pixel wide white line on black background, when a nearly horizontal line totally covers a single pixel, that pixel gets the value 1, and when it's covering half of two pixels, both of them get a value of 0.5. Unfortunately, because of gamma, what's really displayed is around 0.5^2.0 or so on the analog brightness scale (1 being the maximum of the monitor), which is around 0.25. When you add the values of the two pixels, they don't add to 1, but 0.5, so the line will appear half as bright when it's covering half of two pixels each, compared to when it's fully covering one pixel.

On CRTs it doesn't look nearly as bad for nearly-vertical lines because each horizontal line will get blurred a bit when scanning (analog electronics are never perfect), but the issue is otherwise the same, and on TFTs it'll look just as bad. But yeah well, I'm just being elitist. Most anti-aliasing graphics libs ignore the issue, and therefore look just as bad when you use very thin lines. Once the lines get wider, the issue gets less visible anyway.

zeii wrote:Advice / Thoughts on the ADT Library idea would be appreciated.

Totally my idea

However, if you'd be willing to work on it, I'd be willing to use it, as you seem to have much more done than I. (Mine having barely anything....) Also, I'd be willing to help with testing and whatever else, really.

When I was thinking of the design for mine, I was going to focus on flexibility, so I could have whatever type of data structure packed into any other data structure. I would find this nifty.

Also, I was going to have an interface that parsed strings and created data structures on the fly. Although, this idea needs much refinement.....

I like data structures....I'm not really sure why...It's like emulation and information theory....

Id be willing to work on it, although progress my initially be slow.
I am currently doing some academic research, which led to me having to learn AVL in the first place.

That being said, I love Data structures. I consider them the lifeblood of any good program. How good you can code means crap all, if the only data structure you understand how to use is an Array or a List.

Flexibility will be important to my Library as well. What good is a Library if you have to like, seriously modify HEAPS of it... all the time? It wouldnt be very great.

The idea I have is, Is that a few 'core' Node types would be declared. Specific ADT Functions would require these nodes to be passed. These nodes could reside within your own standard template. For example...
This way, We can use our own custom Structures, but still use the Library's various ADT Functions.

Im particularly obsessive when it comes to a Node's size in Memory. So, The various Node types will probably be using some kind of encoding, even if it is just making use of individual bits, instead of entire bytes.

First things first, that I feel is important:
- AVL Nodes
- I can implement an AVL tree, that doesnt require a Key. Atleast,
Not a key assigned by the Developer / User. The Key would instead be
the memory address of the Node itself. This an save us 4b.

- With 3 Parent links + 1byte for 'flags', 13bytes for a AVL Node.
Is that acceptable?

Working on a Public-Domain ADT Library for helping OS Development would be a cool thing, if only to help me, myself, learn more about ADTs.

So, I may need to ask questions in the future about various ADTs, as I implement them.

Ones I can do off the top of my head, iteratively:
- Binary Search Tree.
- AVL Tree.
(Lists could have a SMALL and LARGE variant. Small lists use no head/tail pointers and scan for insertion point, so they save a few bytes on Memory use. Large have the head/tail pointers are much, much faster in execution).
- Singly linked list.
- Doubly linked list.
- Various Stacks, implemented using the List types.
- A few queues, implemented using the Stack types.
- Dynamically-sized Array Type.
- Heap ADT
- I know how to implement the Heap, represented from an Array. However, A dynamically sized Array could be both painful and slow for this purpose, no? It would be interesting to talk about the Heap.

Things I will have to learn:
- Hash Tables.
- Redblack trees.

These maybe needed, Im not sure if anyone here uses them:
- Unrolled Linked Lists
- Skiplists
- Splay trees
- B-Trees

Any ideas?
~zeii[/code]

There is a problem I can see with the code (haven't tested it though). Take this code: