Just to mention my current works:
A doubly linked RedBlack Tree based self-balancing and self-sorting tree based storage scheme for arbitrary objects.
Asynchronous File IO via IOCP (specifically, NetCom's IOCP engine).
A new 3D collision testing algorithm based on "binary feature trees".
Experiments with neural networks.

Posted on 2009-12-23 00:19:04 by Homer
Implementing Asynch File IO in NetCOM turned out to be fairly easy, now I just need to get it to work !!
Posted on 2009-12-29 22:20:08 by Homer
How's your redblack tree going?
Posted on 2010-01-11 19:08:28 by roticv
Its complete and working, with the current restriction that keys must be unique (this issue can be overcome).
And all the credit goes to Biterider who has singlehandedly worked on this.
So it's not mine at all :P
Posted on 2010-01-11 23:39:56 by Homer
Hi roticv
Here is a first beta of the Red-Black Tree code. I have distributed it on some testers and all seems to work, but some bugs may remain hidden.

Regards,

Biterider
Attachments:
Posted on 2010-01-12 13:54:03 by Biterider
Congratulations, Biterider for the code, but I have some "critical" notes about the speed of
your code and I hope to see faster "assembly" code in your next release..Why faster?
Because we pay the price of difficult coding of the self balanced Red Black Trees just for speed!!!
Otherwise we use simple binary search trees...

"Write VB/C/C++ interoperable asm code with EASE.. Modular is Good!"

I disagree for red-black tree code and hope to see your faster "assembly" code (without so much If.Then.ElseIf.Else) with assembly way of thinking rather than simple compilation of the existing C/C++ code.

Let's get rolling:
- Try to implement top-down red-black tree Insert proc. Its primary advantage is that rebalancing can be implemented in a single pass down the tree, rather than the traditional pass down and back up.
- Try to replace all sentinel nodes or Nills with simple zero
- Try to use similar node structure:
lpParent dd ?
lpLeftChild dd ?
lpRightChild dd ?
nColor dd ? -> it is faster to use dword rather than a bit or byte for color
nKey dd ?  -> or address of structure with key
lpList dd ? -> address in the linked list or 0
     ; if you have duplicate Node  just add it's address in the linked list
- Don't use recursion - for C/C++ people it is "elegant" but for the "assembly" man it is slow...
a lot of unusual calls and returns...just to lose time
Example:
1. Your code

; Method:    RedBlackTree.ForEach
; Purpose:   Traverses all nodes in the tree in ascending order.
; Arguments: Arg1: -> Processing procedure (static address).
;            Arg2-n: (Optional) Parameters to be used by the processing procedure.
; Return:    Nothing.
; Note:      While the loop is running, no object should be deleted or inserted!
ForEachRBSubtree proc pNode:PRBT_NODE                   ;esi, ebx & ebp are passed from ForEach
   ;Go for the smaller sibling
   mov edx,                                  ;pNode
   mov eax, .RBT_NODE.pLeftNode
   .if eax != .RedBlackTree.pNilNode
     invoke ForEachRBSubtree, eax
   .endif

   ;Call action procedure
   mov edi,                                  ;pNode
   push ecx                                            ;Save ecx
   mov eax, ebx
   sub edi, .RedBlackTree.dNodeOffset
   .while ecx != 0
     push                                        ;push parameter
     sub eax, 4
     dec ecx
   .endw
   push edi
   call ebp                                            ;Call procedure
   pop ecx                                             ;Restore ecx

   ;Go for the bigger sibling
   mov edx,                                  ;pNode
   mov eax, .RBT_NODE.pRightNode
   .if eax != .RedBlackTree.pNilNode
     invoke ForEachRBSubtree, eax
   .endif
   ret 4
ForEachRBSubtree endp


2. My code:

On entry:   ecx -> address of the Root node
 edx->  address of the empty buffer to put all node addresses in assending order
On exit:     edx->  address of the last node in the Buffer
Used registers: eax, ecx, edx
Align 16 ;
TraversePrint2: ; search for min left child
mov eax, ecx ; save parent
xor ecx, ecx ;
add ecx, ; get the left child
jne TraversePrint2 ; no, loop again
;Print.......................................................................................;
T_Print2: ;
mov , eax ; eax->address of node ; edx->lpBuffer
add edx, 4 ;
add ecx, ; -> address of  linked list or zero
jne Eq_Wr ; If ecx != 0 we have linked list with equal nodes
; for printing here too..
; Right Child Check
add ecx, ; if ecx =0 -> No Right Child
jne TraversePrint2 ; else Has Right Child and jmp
@@: ; No Right Child
mov ecx, eax ; save curr parent in ecx
xor eax, eax ;
Ko1: ;
add eax, ; get prev parent in eax
je @f ; if eax=0->It is a Root from right->exit
cmp , ecx ; is it return from right child?
je @b ; yes, loop again
xor ecx, ecx ; ecx=0
je T_Print2 ;
align 8 ;
@@: ;
sub edx, 4 ;
ret ; Return
align 8 ;
Eq_Wr: ;linked list with equal nodes
; for printing here too..
mov , ecx ; ecx->address of node
add edx, 4 ;
mov ecx,     ; -> next node in the linked list or zero
test ecx, ecx ; no more nodes and return to main loop
jne Eq_Wr ;
; Right Child Check
add ecx, ; if ecx =0 -> No Right Child
jne TraversePrint2 ; else Has Right Child and jmp
mov ecx, eax ; save curr parent in ecx
xor eax, eax ;
je Ko1 ;
;... ;

- Try to substitute the usage of  Rotating Left and Rotating Right (C/C++) procedures & Insert proc with
simple assembly subroutines (for the different cases)  which just get the right addresses and colors from the Parent, Grand Parent,GrandGrand Parent, Uncle etc., and put directly them  in the right locations.

Enough for now... and thank you for the code again. :)
Posted on 2010-01-13 00:02:47 by lingo12
Yes speed is very important - its why we bother, isn't it?
But do note that the code provided is merely a BETA, it has not been optimized yet, that comes after the code has been extensively and intensively tested :)

Also note that the code presented represents (more or less) a complete rewrite of the C++ code apon which it was based - the original implementation appears to have had some serious bugs, and I wonder to myself if the original author ever actually tried to use it !! He claims he used it for sorting 2D sprites to maintain correct drawing order, but the implementation was categorically broken, so I have my doubts..

Finally, I'm a little concerned about your idea of arbitrary insertions into the tree - this will cause the tree to become unbalanced, correct? Can you provide links to any reference material which describes your implementation nuances?
Posted on 2010-01-13 00:19:24 by Homer
"Finally, I'm a little concerned about your idea of arbitrary insertions into the tree - this will cause the tree to become unbalanced, correct? Can you provide links to any reference material which describes your implementation nuances?"
Yes. :)
You can see my last post here: http://www.masm32.com/board/index.php?topic=12443.0
Posted on 2010-01-13 01:09:57 by lingo12
I like the way you think, I need to take some time to look over your implementation and digest the ramifications.
Generally, I hold the opinion that there is always a better way to do anything, however only a tinkerer will discover it, or a dreamer will conceive it (I see myself as both, and I say that with due humility).
But the main use for a red black tree is not sorting a static list, its handling a DYNAMIC list, where EVERY entry's sorting key is subject to change without notice by some external godlike hand! And so, I do not perceive your benchtest as being a reliable indication of effectiveness or efficiency, not just yet.
In fact, there is NO benefit to using a RB tree UNLESS the sorting keys are subject to change, and therefore, the only way to gauge the efficacy of any particular implementation is under intense stress!
Posted on 2010-01-13 04:02:20 by Homer
Hi lingo
Thanks for your comments. Iím always interested in speeding up the code. In this case I made the mistake when traversing efficiently the tree. At first glance it seemed to be a good idea to use a recursive algorithm, but without recursion it will be faster. I will change the affected methods. It is also possible to inline the rotation procedures to gain another few cycles.

At the beginning I needed a sorted tree for a dynamic database application and I decided to use the RB-Tree witch I was looking after for a long time yet. I asked Homer if he had an implementation of the algorithm and he showed me a source in C++ . Unfortunately it had some bugs that I decided to code it again from scratch, focusing on a general purpose implementation. This way, for a specific problem, to achieve a special purpose, only little modifications in a descendant object are needed.

In particular, the problem of non unique keys can not be simply solved adding the address of the node to the comparison routine. If you do so, you are not able to find a node again without knowing its address before hand.
One possible solution is to have 2 comparison routines, one for the insertion and another for the search methods. I saw some people using a linked list together with a RB-Tree which allows sorting the unique nodes in the linked list. The remaining nodes (non unique nodes) are placed in between them. To differentiate these nodes a new colour to mark them is used until they become unique due to the deletion of another node in the tree.

My idea was to implement something in this direction in a descendant object. This way I did not put all subroutines in the main methods. In a final version I maybe can further optimize the codeÖ

Regads,

Biterider
Posted on 2010-01-13 13:34:12 by Biterider
Hi
I finally found the time to rework some code paths of the Red Black Tree. I tried to follow the above advice of lingo and found some papers that described more efficient ways to traverse the tree. I added the links to the file header.
Benchmarking the code for insertion and traversal showed some speed boost, but far less than that what I expected.

Regards,

Biterider
Attachments:
Posted on 2010-01-21 14:17:01 by Biterider