Bug 66203
| Summary: | WTF does not have a balanced tree implementation that would be suitable for use in a memory allocator | ||
|---|---|---|---|
| Product: | WebKit | Reporter: | Filip Pizlo <fpizlo> |
| Component: | JavaScriptCore | Assignee: | Nobody <webkit-unassigned> |
| Status: | RESOLVED DUPLICATE | ||
| Severity: | Normal | CC: | barraclough, fpizlo, sam |
| Priority: | P2 | ||
| Version: | 528+ (Nightly build) | ||
| Hardware: | All | ||
| OS: | All | ||
Filip Pizlo
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.
| Attachments | ||
|---|---|---|
| Add attachment proposed patch, testcase, etc. |
Gavin Barraclough
We generally don't accept patches that only check in unused code. As such, if this bug intends to just check in the tree unused, I'm afraid it is likely to be r-'ed. :-(
Filip Pizlo
(In reply to comment #1)
> We generally don't accept patches that only check in unused code. As such, if this bug intends to just check in the tree unused, I'm afraid it is likely to be r-'ed. :-(
Tests don't count?
Filip Pizlo
Closing this since
*** This bug has been marked as a duplicate of bug 66363 ***
Filip Pizlo
(In reply to comment #3)
> Closing this since
>
> *** This bug has been marked as a duplicate of bug 66363 ***
Closing this since it is a work-in-progress prerequisite of bug 66363. It would be better to have a single patch in this case, rather than smaller patches that by themselves don't do anything.