[webkit-reviews] review denied: [Bug 45059] Add red-black tree capable of holding plain old data (POD) : [Attachment 66269] Revised patch
bugzilla-daemon at webkit.org
bugzilla-daemon at webkit.org
Wed Sep 1 16:22:21 PDT 2010
Chris Marrin <cmarrin at apple.com> has denied Kenneth Russell <kbr at google.com>'s
request for review:
Bug 45059: Add red-black tree capable of holding plain old data (POD)
https://bugs.webkit.org/show_bug.cgi?id=45059
Attachment 66269: Revised patch
https://bugs.webkit.org/attachment.cgi?id=66269&action=review
------- Additional Comments from Chris Marrin <cmarrin at apple.com>
> Index: WebCore/platform/PODArena.h
> ===================================================================
> --- WebCore/platform/PODArena.h (revision 0)
> +++ WebCore/platform/PODArena.h (revision 0)
> ...
> +private:
> + enum {
> + DefaultArenaSize = 16384
This seems like an odd default, not necessarily appropriate for all uses of
this type. Also you don't allow a size to be passed into PODArena, so this
isn't a "default", it's the only allowable size. I'm not even sure there is a
default size that would be appropriate for "most things". It would be better to
just add a size parameter to the ctor and not have a default at all.
> + };
> +
> + PODArena()
> + {
> + // Initialize the arena pool
> + INIT_ARENA_POOL(&m_pool, "PODArena", DefaultArenaSize);
> + }
> +
> + // Underlying arena pool
> + ArenaPool m_pool;
> +};
> +
> +} // namespace WebCore
> +
> +#endif // PODArena_h
> Index: WebCore/platform/PODRedBlackTree.h
> ===================================================================
> --- WebCore/platform/PODRedBlackTree.h (revision 0)
> +++ WebCore/platform/PODRedBlackTree.h (revision 0)
> @@ -0,0 +1,755 @@
> ...
> +//
> +// The data type T that is stored in this red-black tree must be only
> +// Plain Old Data (POD), or bottom out into POD. It must _not_ rely on
> +// having its destructor called. This implementation internally
> +// allocates storage in large chunks and does not call the destructor
> +// on each object.
> +//
> +// Type T must supply a default constructor, a copy constructor, and
> +// the "<" and "==" operators.
If T is always a POD, isn't the above rule true of all PODs? And if the only
issue is that you're not calling the dtor, why not just add the logic to call
the dtor? Is it complex?
> +//
> +// In debug mode, printing of the data contained in the tree is
> +// enabled. This requires the following function to be available:
> +//
> +// String valueToString(const T&);
> +//
> +// Note that when complex types are stored in this red/black tree, it
> +// is possible that single invocations of the "<" and "==" operators
> +// will be insufficient to describe the ordering of elements in the
> +// tree during queries. As a concrete example, consider the case where
> +// intervals are stored in the tree sorted by low endpoint. The "<"
> +// operator on the Interval class only compares the low endpoint, but
> +// the "==" operator takes into account the high endpoint as well.
> +// This makes the necessary logic for querying and deletion somewhat
> +// more complex. In order to properly handle such situations, the
> +// property "needsFullOrderingComparisons" must be set to true on
> +// the tree.
But I thought this class only handles POD types. Why the info about complex
types?
> +//
> +// This red-black tree is designed to be _augmented_; subclasses can
> +// add additional and summary information to each node to efficiently
> +// store and index more complex data structures. A concrete example is
> +// the IntervalTree, which extends each node with a summary statistic
> +// to efficiently store one-dimensional intervals.
> +//
> +// The design of this red-black tree comes from Cormen, Leiserson,
> +// and Rivest, _Introduction to Algorithms_, MIT Press, 1990.
> +
> +#ifndef PODRedBlackTree_h
> +#define PODRedBlackTree_h
> +
> +#ifndef NDEBUG
> +#include "Logging.h"
> +#include "PlatformString.h"
> +#endif
> +#include "PODArena.h"
> +#ifndef DEBUG
> +#include "StringBuilder.h"
> +#endif
> +#include <wtf/Assertions.h>
> +#include <wtf/Noncopyable.h>
> +#include <wtf/RefPtr.h>
> +#ifndef NDEBUG
> +#include <wtf/text/CString.h>
> +#endif
> +
> +namespace WebCore {
> +
> +template<class T>
> +class PODRedBlackTree {
> +public:
> + // Visitor interface for walking all of the tree's elements.
> + class Visitor {
> + public:
> + virtual void visit(const T& data) = 0;
> + protected:
> + virtual ~Visitor() { }
> + };
> +
> + // Constructs a new red-black tree, allocating temporary objects
> + // from a newly constructed PODArena.
> + PODRedBlackTree()
> + : m_arena(PODArena::create())
> + , m_root(0)
> + , m_needsFullOrderingComparisons(false)
> +#ifndef NDEBUG
> + , m_verboseDebugging(false)
> +#endif
> + {
> + }
> +
> + // Constructs a new red-black tree, allocating temporary objects
> + // from the given PODArena.
> + explicit PODRedBlackTree(PODArena* arena)
> + : m_arena(arena)
> + , m_root(0)
> + , m_needsFullOrderingComparisons(false)
> +#ifndef NDEBUG
> + , m_verboseDebugging(false)
> +#endif
> + {
> + }
> +
> + virtual ~PODRedBlackTree() { }
> +
> + void insert(const T& data)
> + {
> + Node* node = new Node(data);
> + insertNode(node);
> + }
> +
> + // Removes the given datum from the tree. Returns true if the datum
> + // was found in the tree.
> + bool remove(const T& data)
> + {
> + Node* node = treeSearch(data);
> + if (node) {
> + deleteNode(node);
> + return true;
> + }
> + return false;
> + }
> +
> + bool contains(const T& data) { return treeSearch(data); }
> +
> + void visitInorder(Visitor* visitor)
> + {
> + if (!m_root)
> + return;
> + visitInorderImpl(m_root, visitor);
> + }
> +
> + int numElements()
> + {
> + Counter counter;
> + visitInorder(&counter);
> + return counter.count();
> + }
You should use the same terminology as HashTable, size() rather than
numElements(), add() rather than insert(),
> +
> + // See the class documentation for an explanation of this property.
> + void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)
> + {
> + m_needsFullOrderingComparisons = needsFullOrderingComparisons;
> + }
> +
> + virtual bool checkInvariants()
> + {
> + int blackCount;
> + return checkInvariantsFromNode(m_root, &blackCount);
> + }
> +
> +#ifndef NDEBUG
> + // Dumps the tree's contents to the logging info stream for
> + // debugging purposes.
> + void dump()
> + {
> + dumpFromNode(m_root, 0);
> + }
> +
> + // Turns on or off verbose debugging of the tree, causing many
> + // messages to be logged during insertion and other operations in
> + // debug mode.
> + void setVerboseDebugging(bool onOrOff)
> + {
> + m_verboseDebugging = onOrOff;
> + }
> +#endif
> +
> +protected:
> + enum Color {
> + kRed = 1,
> + kBlack
> + };
> +
> + // The base Node class which is stored in the tree. Nodes are only
> + // an internal concept; users of the tree deal only with the data
> + // they store in it.
> + class Node : public Noncopyable {
> + public:
> + // Constructor. Newly-created nodes are colored red.
> + explicit Node(const T& data)
> + : m_left(0)
> + , m_right(0)
> + , m_parent(0)
> + , m_color(kRed)
> + , m_data(data)
> + {
> + }
> +
> + virtual ~Node() { }
> +
> + Color color() const { return m_color; }
> + void setColor(Color color) { m_color = color; }
> +
> + // Fetches the user data.
> + T& data() { return m_data; }
> +
> + // Copies all user-level fields from the source node, but not
> + // internal fields. For example, the base implementation of this
> + // method copies the "m_data" field, but not the child or parent
> + // fields. Any augmentation information also does not need to be
> + // copied, as it will be recomputed. Subclasses must call the
> + // superclass implementation.
> + virtual void copyFrom(Node* src) { m_data = src->data(); }
> +
> + Node* left() const { return m_left; }
> + void setLeft(Node* node) { m_left = node; }
> +
> + Node* right() const { return m_right; }
> + void setRight(Node* node) { m_right = node; }
> +
> + Node* parent() const { return m_parent; }
> + void setParent(Node* node) { m_parent = node; }
> +
> + private:
> + Node* m_left;
> + Node* m_right;
> + Node* m_parent;
> + Color m_color;
> + T m_data;
> + };
> +
> + // Returns the root of the tree, which is needed by some subclasses.
> + Node* root() const { return m_root; }
> +
> +private:
> + // This virtual method is the hook that subclasses should use when
> + // augmenting the red-black tree with additional per-node summary
> + // information. For example, in the case of an interval tree, this
> + // is used to compute the maximum endpoint of the subtree below the
> + // given node based on the values in the left and right children. It
> + // is guaranteed that this will be called in the correct order to
> + // properly update such summary information based only on the values
> + // in the left and right children. This method should return true if
> + // the node's summary information changed.
> + virtual bool updateNode(Node* node) { return false; }
> +
> + //----------------------------------------------------------------------
> + // Generic binary search tree operations
> + //
> +
> + // Searches the tree for the given datum.
> + Node* treeSearch(const T& data)
> + {
> + if (m_needsFullOrderingComparisons)
> + return treeSearchFullComparisons(m_root, data);
> +
> + return treeSearchNormal(m_root, data);
> + }
> +
> + // Searches the tree using the normal comparison operations,
> + // suitable for simple data types such as numbers.
> + Node* treeSearchNormal(Node* current, const T& data)
> + {
> + while (current) {
> + if (current->data() == data)
> + return current;
> + if (data < current->data())
> + current = current->left();
> + else
> + current = current->right();
> + }
> + return 0;
> + }
> +
> + // Searches the tree using multiple comparison operations, required
> + // for data types with more complex behavior such as intervals.
> + Node* treeSearchFullComparisons(Node* current, const T& data)
> + {
> + if (!current)
> + return 0;
> + if (data < current->data())
> + return treeSearchFullComparisons(current->left(), data);
> + if (current->data() < data)
> + return treeSearchFullComparisons(current->right(), data);
> + if (data == current->data())
> + return current;
> +
> + // We may need to traverse both the left and right subtrees.
> + Node* result = treeSearchFullComparisons(current->left(), data);
> + if (!result)
> + result = treeSearchFullComparisons(current->right(), data);
> + return result;
> + }
> +
> + void treeInsert(Node* z)
> + {
> + Node* y = 0;
> + Node* x = m_root;
> + while (x) {
> + y = x;
> + if (z->data() < x->data())
> + x = x->left();
> + else
> + x = x->right();
> + }
> + z->setParent(y);
> + if (!y)
> + m_root = z;
> + else {
> + if (z->data() < y->data())
> + y->setLeft(z);
> + else
> + y->setRight(z);
> + }
> + }
> +
> + // Finds the node following the given one in sequential ordering of
> + // their data, or null if none exists.
> + Node* treeSuccessor(Node* x)
> + {
> + if (x->right())
> + return treeMinimum(x->right());
> + Node* y = x->parent();
> + while (y && x == y->right()) {
> + x = y;
> + y = y->parent();
> + }
> + return y;
> + }
> +
> + // Finds the minimum element in the sub-tree rooted at the given
> + // node.
> + Node* treeMinimum(Node* x)
> + {
> + while (x->left())
> + x = x->left();
> + return x;
> + }
> +
> + // Helper for maintaining the augmented red-black tree.
> + void propagateUpdates(Node* start)
> + {
> + bool shouldContinue = true;
> + while (start && shouldContinue) {
> + shouldContinue = updateNode(start);
> + start = start->parent();
> + }
> + }
> +
> + //----------------------------------------------------------------------
> + // Red-Black tree operations
> + //
> +
> + // Left-rotates the subtree rooted at x.
> + void leftRotate(Node* x)
> + {
> + // Set y.
> + Node* y = x->right();
> + // Turn y's left subtree into x's right subtree.
> + x->setRight(y->left());
> + if (y->left())
> + y->left()->setParent(x);
> + // Link x's parent to y.
> + y->setParent(x->parent());
> + if (!x->parent())
> + m_root = y;
> + else {
> + if (x == x->parent()->left())
> + x->parent()->setLeft(y);
> + else
> + x->parent()->setRight(y);
> + }
> + // Put x on y's left.
> + y->setLeft(x);
> + x->setParent(y);
Blank line before comment would make this more readable, here and other places.
Sam has said he thought all this was going into WTF and thinks Arena.h should
go there, too. That made me look at Arena.h and I think it is full of cruft and
should not even exist. I've started a thread to discuss it on webkit-dev. Let's
give that a day to pan out before the next step.
More information about the webkit-reviews
mailing list