[Webkit-unassigned] [Bug 66203] New: WTF does not have a balanced tree implementation that would be suitable for use in a memory allocator

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=66203

           Summary: WTF does not have a balanced tree implementation that
                    would be suitable for use in a memory allocator
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: Normal
          Priority: P2
         Component: JavaScriptCore
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: fpizlo at apple.com


WTF has an AVL tree implementation, but it does not allow for the removal of specific nodes - only the removal of keys.  Hence, if the user wishes to remove a specific node, which may have a key equal to any number of other nodes in the tree, then the AVLTree code is not particularly useful.  Furthermore, AVL trees are somewhat less efficient than red-black trees, so it would be preferable to have a red-black tree instead.  WebCore has a red-black tree implementation (PODRedBlackTree), but it internally manages nodes and assumes that it is fine to copy one node into another.  Hence, if a pointer to a node is also placed into other data structures, then PODRedBlackTree operations may lead to the pointers being invalidated.  As well, PODRedBlackTree makes it impossible to place a node inside of the free space that it would represent, if a red-black tree was used for free space management.

WTF should have a red-black tree implementation that allows the user to decide how nodes are allocated, ensures that pointers into nodes in the tree remain valid regardless of operations on other nodes in the tree, and allows for specific nodes to be removed instead of just removal by key.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.