I just commited a version of (my suggestion for) DelphiSpringTrees; this is the first version that I'm happy with.

-
I just commited a version of (my suggestion for) DelphiSpringTrees; this is the first version that I'm happy with.
Features:
- Fast
- Does not use or require recursion (except in unit-testing).
- Does not need an explicit (or implicit) stack.
- Uses parent pointers for very fast traversal.
- Stores node data in a jenny-array (TArray>) to prevent memory fragmentation. With some trickery only the last item in this array is ever added/removed, so there are never gaps.

It is safe for managed types.

It comes with a full set of unit tests, and a supports all the Spring4D features plus a few extra goodies.

Feel free to suggest improvements (esp performance improvements).
Currently RedBlackTree and RedBlackTree are the only supported types. An AVL tree is planned.

The tree is not threadsafe, but I've made some preperations so that adding in threadsafety is not impossibly difficult.

https://github.com/JBontes/DelphiSpringTrees

Currently it requires XE7 (because it uses the intrinsic function (IsManagedType(T)), if anyone knows an alternative for that pre-XE7 I'd like to hear about it, so that it can work in older versions as well.
https://github.com/JBontes/DelphiSpringTrees/

Comments

  1. Johan BontesDecember 4, 2017 at 2:05 AM

    Why not? The reference count does not need to get updated, it's just a simple move of the reference. If not what code should I use for managed types instead. If I do:

    if IsManangedType(T) then begin
    Node.fKey:= LastNode.fKey;
    Finalize(LastNode.fKey);
    end;

    Then I just add extra ref counting code for no reason.
    On the other hand you are usually correct, so please enlighten me.

    Note that at this point I'm not looking to make the code thread safe, that's a later worry.

    ReplyDelete
  2. Stefan GlienkeDecember 4, 2017 at 2:22 AM

    Johan Bontes My mistake - I meant if the type has a weak reference you need to manually assign to cause the weak reference address to be updated (if I don't forget anything this can just be the case for records).

    Also you don't need to call Finalize, just assign Default(T).

    Imo no need to be smart and premature optimize. Just assigning a handful of fields is hardly any slower than a System.Move

    ReplyDelete
  3. Johan BontesDecember 4, 2017 at 2:50 AM

    Stefan Glienke I'll add a test using HasWeakRef. Thanks for the heads up, and thanks again for suggesting the bucket storage. It's really a winner performance wise.

    The FreeNode function now looks like:

    procedure TBinaryTreeBase.FreeSingleNode(const Node: PNode);
    var
    Index: TBucketIndex;
    LastNode: PNode;
    begin
    {TODO -oJB -cTBinaryTreeBase.FreeSingleNode : Lock in MultiThreading mode}
    Assert(Assigned(Node));
    Dec(fCount);
    if not(HasWeakRef(T)) then Finalize(Node.fKey);
    if (fCount > 0) then begin
    index:= BucketIndex(fCount);
    Assert((Index.Key + Index.Value) > 0);
    LastNode:= @fStorage[index.Key, index.Value];
    //After the move node now points to the new node
    //Fix up the anything that points to the new node.
    if (Node = LastNode) then Exit;
    if (Assigned(LastNode.Parent)) then begin
    if (LastNode.Parent.Left = LastNode) then LastNode.Parent.Left:= Node
    else LastNode.Parent.Right:= Node;
    end else begin
    fRoot:= Node;
    end;
    if Assigned(LastNode.Left) then LastNode.Left.Parent:= Node;
    if Assigned(LastNode.Right) then LastNode.Right.Parent:= Node;
    {$if CompilerVersion >= 28.0} //XE7 or higher
    if (HasWeakRef(T)) then begin
    {$else}
    if System.TypInfo.HasWeakRef(TypeInfo(T)) then begin
    {$endif}
    Node.Parent:= LastNode.Parent;
    Node.fLeft:= LastNode.fLeft;
    Node.fRight:= LastNode.fRight;
    Node.fIsBlack:= LastNode.fIsBlack;
    Node.fKey:= LastNode.fKey; //Node.fKey is destroyed here.
    Finalize(LastNode.fKey); //Release LastNode.fKey, otherwise the refcount will be off by one.
    end else begin
    Move(LastNode^, Node^, SizeOf(TNode));
    end;
    if (Index.Value = 0) then begin
    SetLength(fStorage[index.Key],0);
    SetLength(fStorage, Index.Key);
    end;
    end;
    end;

    I hope that covers all use cases..

    ReplyDelete

Post a Comment