Add red-black tree capable of holding plain old data (POD)

[Kenneth Russell]

A red-black tree capable of holding plain old data (POD) is needed in support of some graphics algorithms currently being integrated. The implementation uses an arena (built using Arena.h) which is being added at the same time.

[Kenneth Russell]

Created attachment 66264 [details]
Patch

From the ChangeLog:

Adding a red-black tree capable of holding Plain Old Data (POD) and an associated PODArena which is built on Arena.h. Note that the PODArena will be used by other classes to allocate temporary structures, which is why it is not just an implementation detail of the red-black tree.

To address earlier review feedback, PODArena and PODRedBlackTree can not currently be placed in WTF because Arena.h is in WebCore/platform.

Unit tests for the PODRedBlackTree will be integrated separately under bug 45060.

[Kenneth Russell]

Created attachment 66269 [details]
Revised patch

Addressed a couple of missed portions of abarth's earlier review feedback.

[Chris Marrin]

Comment on attachment 66269 [details]
Revised patch

> 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.

[Jeremy Orlow]

Probably a stupid question: is there any reason why the AVLTree in wtf won't work for what you need?

[Chris Marrin]

(In reply to comment #4)
> Probably a stupid question: is there any reason why the AVLTree in wtf won't work for what you need?

This comment made me look up comparisons between the two. Interesting info. Here's a Dr Dobbs article that was interesting:

    http://www.drdobbs.com/184410531

This of course points out that STL uses RB trees. In particular it seems like std::multiset might fit the bill, since it stores its data in an RB tree and can have duplicate values.

Looking at the STL implementation on Mac, map, multimap, set and multiset are all based on stl_tree, which is a RB tree implementation. I assume this is true on all platforms.

[Kenneth Russell]

(In reply to comment #4)
> Probably a stupid question: is there any reason why the AVLTree in wtf won't work for what you need?

An AVL tree could be used, but would need to be modified to support augmenting the data structure. This specifically means allowing the recomputation of summary statistics while rebalancing the tree. This red-black tree has been specifically designed for this purpose, and is why it can so easily be subclassed into an efficient IntervalTree. I'm certainly amenable to merging these data structures, but only after checkpointing an initial working version of this code.

[Kenneth Russell]

(In reply to comment #3)
> 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.

The semantics of this enum have changed now that PODArena does not depend on Arena.h any more. It is entirely an implementation detail now.

> > +// 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?

T may be a class which bottoms out into only POD; i.e., does not perform dynamic memory allocation requiring its destructor to be called. It is potentially complex to call the destructors properly of the nodes in the tree. I am willing to investigate doing so, which would generalize the tree, but not before an initial checkin of this code. It is complicated and I need a baseline to work against when making changes of this nature.

> > +// 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?

No, it handles POD or classes bottoming out into POD, such as an Interval whose endpoints are floats. This will become clear in the next patch which augments this PODRedBlackTree into a PODIntervalTree.

> You should use the same terminology as HashTable, size() rather than numElements(), add() rather than insert(), 

Done.

> Blank line before comment would make this more readable, here and other places. 

Done.

> 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.

Per that discussion I am resubmitting this patch adding these classes into platform/graphics/gpu for the time being.

[Kenneth Russell]

Created attachment 66391 [details]
Revised patch

Per review comments above and discussion on webkit-dev:

 - Made PODArena self-contained again rather than relying on Arena.h.
 - Adding PODArena and PODRedBlackTree into platform/graphics/gpu for the time being. If the red/black tree and forthcoming interval tree are generalized to hold fully arbitrary data types, we can consider moving them.
 - Changed red-black tree's numElements to size and insert to add.

[Chris Marrin]

(In reply to comment #7)
> ...
> > > +// 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?
> 
> No, it handles POD or classes bottoming out into POD, such as an Interval whose endpoints are floats. This will become clear in the next patch which augments this PODRedBlackTree into a PODIntervalTree.

Then this explanation is confusing. I've always hated the phrase "bottoms out in POD". I think what that means (in your case) is that all the member variables of the class must be POD, so you should say that. It would also be nice if there were some way to ensure so it fails at compile time if you violate this rule. I'm not sure how to go about doing that though. But you should at least make this description more clear about the rules for contained classes.

[Kenneth Russell]

(In reply to comment #9)
> Then this explanation is confusing. I've always hated the phrase "bottoms out in POD". I think what that means (in your case) is that all the member variables of the class must be POD, so you should say that. It would also be nice if there were some way to ensure so it fails at compile time if you violate this rule. I'm not sure how to go about doing that though. But you should at least make this description more clear about the rules for contained classes.

It doesn't mean that -- the contained class can contain data members of class types. The requirement is that none of those contained classes dynamically allocate memory and therefore require their destructors to be run. I think the comment is pretty clear.

Ideally I would also like to enforce this with compile time checking but I don't know how to do that yet. I am interested in investigating how this might be done. However, I need to checkpoint this code first.

[Darin Fisher (:fishd, Google)]

Comment on attachment 66391 [details]
Revised patch

View in context: https://bugs.webkit.org/attachment.cgi?id=66391&action=prettypatch

> WebCore/platform/graphics/gpu/PODArena.h:41
> +#include <wtf/Vector.h>
perhaps you should explicitly include <stdint.h> since you use uint8_t below.

> WebCore/platform/graphics/gpu/PODArena.h:56
> +        virtual ~Allocator() { }
nit: though it may not be that common in WebCore, I find it helpful
when destructors on classes that inherit from RefCounted are made
protected.  To do that you need a friend declaration:

  friend class WTF::RefCounted<Allocator>;

This way no one else can delete the object.  Only the RefCounted
base class can delete the object.

(Ditto for PODArena itself.)

> WebCore/platform/graphics/gpu/PODArena.h:84
> +    static PassRefPtr<PODArena> create(Allocator* allocator)
nit: this should take a PassRefPtr<Allocator> argument

> WebCore/platform/graphics/gpu/PODArena.h:90
> +    template<class T>
nit: on member functions, it seems more common in webkit code to
put the template keyword on the same line as the function name:

  template<class T> T* alloc()

nit: perhaps allocateObject would be a better name for this method.

> WebCore/platform/graphics/gpu/PODArena.h:141
> +    static size_t minAlignment()
wtf/Vector.h defines a macro named WTF_ALIGN_OF which can be used to
determine the alignment requirements for a type using a compiler
specific mechanism.

perhaps minAlignment() could be rewritten like so:

  static size_t minAlignment()
  {
      return WTF_ALIGN_OF(T);
  }

> WebCore/platform/graphics/gpu/PODArena.h:153
> +    RefPtr<Allocator> m_allocator;
nit: i think it is best to put all of the member variables together.
so, i would put this member variable below the Chunk definition.

> WebCore/platform/graphics/gpu/PODArena.h:200
> +    size_t m_currentChunkSize;
why have m_currentChunkSize and not just a size() member function
on the Chunk class?  (if you want to keep m_currentChunkSize, then
perhaps it should at least be listed next to m_current since it is
so closely related.)

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:53
> +//   String valueToString(const T&);
nit: valueToString should probably be a const method

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:79
> +#ifndef NDEBUG
nit: I'd just make a separate section below the main set of includes
for the debug-only includes.  that way there will be fewer #ifndefs.

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:121
> +    explicit PODRedBlackTree(PODArena* arena)
nit: use PassRefPtr<PODArena> here

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:150
> +    bool contains(const T& data) { return treeSearch(data); }
it seems like you could slap a const on contains, visitInorder and size

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:189
> +    void setVerboseDebugging(bool onOrOff)
nit: normally, in webkit a parameter name like this is named like the
method, so:  void setVerboseDebugging(bool verboseDebugging)

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:197
> +        kRed = 1,
nit: enum values should be named with the "k" prefix

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:446
> +            LOG_ERROR("  PODRedBlackTree::InsertNode");
why LOG_ERROR?  wouldn't LOG(PODRedBlackTree, "InsertNode") be better?
you can see an example of using LOG this way in RefCountedLeakCounter.cpp

also how about writing an inline helper function that can have an empty
implementation in NDEBUG builds but otherwise call LOG(...).  that way
the code in this function will not need #ifdefs.

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:688
> +        Counter()
nit: no line break here

> WebCore/platform/graphics/gpu/PODRedBlackTree.h:750
> +        LOG_ERROR("%s", builder.toString().ascii().data());
ditto about using LOG instead

I know there was some discussion before about the use of x, y, z, and
w variable names, but I didn't find them to be a problem.  I'm not sure
that calling them "node" or "newNode" or "tempNode" would really help
improve readability at all.

[Chris Marrin]

(In reply to comment #10)
> (In reply to comment #9)
> > Then this explanation is confusing. I've always hated the phrase "bottoms out in POD". I think what that means (in your case) is that all the member variables of the class must be POD, so you should say that. It would also be nice if there were some way to ensure so it fails at compile time if you violate this rule. I'm not sure how to go about doing that though. But you should at least make this description more clear about the rules for contained classes.
> 
> It doesn't mean that -- the contained class can contain data members of class types. The requirement is that none of those contained classes dynamically allocate memory and therefore require their destructors to be run. I think the comment is pretty clear.

Sorry, but it's still not clear. There are more reasons to call a destructor than freeing of allocated memory. Any resources that need to be released (I/O ports, threads, sockets, etc.) can require the destructor to be called. Really POD has nothing to do with this constraint. By definition a POD doesn't have a constructor or a destructor. In fact according to http://en.wikipedia.org/wiki/Plain_old_data_structure, a POD class cannot contain a copy constructor, but you are requiring one. You're really just saying that you can use any class as long as it doesn't have a destructor.

Since you do intend on making this class fully object aware at some point, it's probably not even a good idea to call this PODRedBlackTree. Just call it RedBlackTree and note the current restriction.

[Darin Fisher (:fishd, Google)]

(In reply to comment #12)
> Since you do intend on making this class fully object aware at some point, it's probably not even a good idea to call this PODRedBlackTree. Just call it RedBlackTree and note the current restriction.

I'm not sure why we need to generalize this class to handle types with destructors.  It seems like premature optimization to write code that has no intended consumer.

I suggested to Ken that he add the POD prefix to these types instead of using the gpu:: namespace (to avoid collision with platform/Arena.h).  So you can blame me for the strictly incorrect name.  While it is true that requiring a copy-constructor means that the types used with these data structures would not be strictly POD, the POD prefix does help convey the fact that destructors will not be called.

We could avoid the operators and the copy constructors by using a Traits template class.  Then, the types could be strictly POD, and we could keep the POD* naming convention.  Or, we could come up with a different naming convention.

Anyways, one thing seems clear to me:  It is nice to not have to keep track of individual allocations in the arena.  That simplifies the code.  Let's find a way to preserve that simplification since it meets are requirements today.  Perhaps by renaming the classes or by using the Traits solution that I mentioned above.

[Chris Marrin]

(In reply to comment #13)
> (In reply to comment #12)
> > Since you do intend on making this class fully object aware at some point, it's probably not even a good idea to call this PODRedBlackTree. Just call it RedBlackTree and note the current restriction.
> 
> I'm not sure why we need to generalize this class to handle types with destructors.  It seems like premature optimization to write code that has no intended consumer.

Sure, if this is always going to be an purpose written class then I think it's fine to be "incomplete" (not in a judgmental way, but in a C++ strictness way).

> 
> I suggested to Ken that he add the POD prefix to these types instead of using the gpu:: namespace (to avoid collision with platform/Arena.h).  So you can blame me for the strictly incorrect name.  While it is true that requiring a copy-constructor means that the types used with these data structures would not be strictly POD, the POD prefix does help convey the fact that destructors will not be called.
> 
> We could avoid the operators and the copy constructors by using a Traits template class.  Then, the types could be strictly POD, and we could keep the POD* naming convention.  Or, we could come up with a different naming convention.

I think Traits would add complexity without much benefit over simply accepting the contract that classes can't require a dtor. It would be awfully nice if we could come up a way to generate a compile time error to keep future users from stepping into the briar patch.

> 
> Anyways, one thing seems clear to me:  It is nice to not have to keep track of individual allocations in the arena.  That simplifies the code.  Let's find a way to preserve that simplification since it meets are requirements today.  Perhaps by renaming the classes or by using the Traits solution that I mentioned above.

I think just renaming it would be fine. I have no problem simply calling it RedBlackTree as long as there is a clear warning about how (not) to use it.

[Kenneth Russell]

(In reply to comment #14)
> I think just renaming it would be fine. I have no problem simply calling it RedBlackTree as long as there is a clear warning about how (not) to use it.

After reading the definition of POD, you're right, I'm misusing the term. We thought here about a different naming convention but weren't able to come up with one ("Simple", ...).

I do not want to name it simply RedBlackTree while it has its current restrictions.

I would like to land PODArena, PODRedBlackTree and the forthcoming PODIntervalTree with these names for now, because they are nicely grouped with the prefix.

[Kenneth Russell]

Created attachment 66421 [details]
Revised patch

Addressed review feedback from fishd:
 - include stdint.h.
 - Made destructors protected and WTF::RefCounted<T> a friend.
 - Renamed alloc to allocateObject.
 - Used WTF_ALIGN_OF in minAlignment.
 - Added const to all conceptually const methods.
 - Grouped NDEBUG includes.
 - Renamed kRed and kBlack.
 - Added helper function for LOG_ERROR with m_verboseDebugging on.

[Chris Marrin]

(In reply to comment #15)
> (In reply to comment #14)
> > I think just renaming it would be fine. I have no problem simply calling it RedBlackTree as long as there is a clear warning about how (not) to use it.
> 
> After reading the definition of POD, you're right, I'm misusing the term. We thought here about a different naming convention but weren't able to come up with one ("Simple", ...).
> 
> I do not want to name it simply RedBlackTree while it has its current restrictions.
> 
> I would like to land PODArena, PODRedBlackTree and the forthcoming PODIntervalTree with these names for now, because they are nicely grouped with the prefix.

I think that's a mistake. Of all the many things a POD is, this class only adheres to one, no dtor. If nothing else you should give these classes a prefix that says "these are for the accelerated 2D renderer, everyone else stay away". It's better to use a meaningless prefix, or no prefix at all, than one that has a specific but wrong meaning.

[Kenneth Russell]

(In reply to comment #11)
> (From update of attachment 66391 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=66391&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/PODArena.h:41
> > +#include <wtf/Vector.h>
> perhaps you should explicitly include <stdint.h> since you use uint8_t below.

Done.

> > WebCore/platform/graphics/gpu/PODArena.h:56
> > +        virtual ~Allocator() { }
> nit: though it may not be that common in WebCore, I find it helpful
> when destructors on classes that inherit from RefCounted are made
> protected.  To do that you need a friend declaration:
> 
>   friend class WTF::RefCounted<Allocator>;
> 
> This way no one else can delete the object.  Only the RefCounted
> base class can delete the object.
> 
> (Ditto for PODArena itself.)

Done.

> > WebCore/platform/graphics/gpu/PODArena.h:84
> > +    static PassRefPtr<PODArena> create(Allocator* allocator)
> nit: this should take a PassRefPtr<Allocator> argument

I don't think so according to http://webkit.org/coding/RefPtr.html under "Function arguments". Ownership isn't being transferred to the PODArena; it merely increments the reference count of the Allocator.

> > WebCore/platform/graphics/gpu/PODArena.h:90
> > +    template<class T>
> nit: on member functions, it seems more common in webkit code to
> put the template keyword on the same line as the function name:
> 
>   template<class T> T* alloc()
> 
> nit: perhaps allocateObject would be a better name for this method.

Done.

> > WebCore/platform/graphics/gpu/PODArena.h:141
> > +    static size_t minAlignment()
> wtf/Vector.h defines a macro named WTF_ALIGN_OF which can be used to
> determine the alignment requirements for a type using a compiler
> specific mechanism.
> 
> perhaps minAlignment() could be rewritten like so:
> 
>   static size_t minAlignment()
>   {
>       return WTF_ALIGN_OF(T);
>   }

Done.

> > WebCore/platform/graphics/gpu/PODArena.h:153
> > +    RefPtr<Allocator> m_allocator;
> nit: i think it is best to put all of the member variables together.
> so, i would put this member variable below the Chunk definition.

Done.

> > WebCore/platform/graphics/gpu/PODArena.h:200
> > +    size_t m_currentChunkSize;
> why have m_currentChunkSize and not just a size() member function
> on the Chunk class?  (if you want to keep m_currentChunkSize, then
> perhaps it should at least be listed next to m_current since it is
> so closely related.)

Because initially there is no Chunk, but we need to know what size it should be allocated with.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:53
> > +//   String valueToString(const T&);
> nit: valueToString should probably be a const method

It isn't a method but a function visible at the global scope.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:79
> > +#ifndef NDEBUG
> nit: I'd just make a separate section below the main set of includes
> for the debug-only includes.  that way there will be fewer #ifndefs.

I didn't think this would pass check-webkit-style, but it does. Done.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:121
> > +    explicit PODRedBlackTree(PODArena* arena)
> nit: use PassRefPtr<PODArena> here

See above. I think this is supposed to be a raw pointer.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:150
> > +    bool contains(const T& data) { return treeSearch(data); }
> it seems like you could slap a const on contains, visitInorder and size

Made these and some other functions const correct.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:189
> > +    void setVerboseDebugging(bool onOrOff)
> nit: normally, in webkit a parameter name like this is named like the
> method, so:  void setVerboseDebugging(bool verboseDebugging)

Done.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:197
> > +        kRed = 1,
> nit: enum values should be named with the "k" prefix

s/should be/should not be. Done.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:446
> > +            LOG_ERROR("  PODRedBlackTree::InsertNode");
> why LOG_ERROR?  wouldn't LOG(PODRedBlackTree, "InsertNode") be better?
> you can see an example of using LOG this way in RefCountedLeakCounter.cpp

Currently there's no .cpp associated with this class and so no good place to put the WTFLogChannel. I don't think it's worth adding a lot of mechanism just for this debugging output.

> also how about writing an inline helper function that can have an empty
> implementation in NDEBUG builds but otherwise call LOG(...).  that way
> the code in this function will not need #ifdefs.

Done with logIfVerbose.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:688
> > +        Counter()
> nit: no line break here

All of the other code I've seen where the constructor is single-line breaks at the colon.

> > WebCore/platform/graphics/gpu/PODRedBlackTree.h:750
> > +        LOG_ERROR("%s", builder.toString().ascii().data());
> ditto about using LOG instead

I left this alone per above.

> I know there was some discussion before about the use of x, y, z, and
> w variable names, but I didn't find them to be a problem.  I'm not sure
> that calling them "node" or "newNode" or "tempNode" would really help
> improve readability at all.

OK.

[Kenneth Russell]

(In reply to comment #17)
> (In reply to comment #15)
> > (In reply to comment #14)
> > > I think just renaming it would be fine. I have no problem simply calling it RedBlackTree as long as there is a clear warning about how (not) to use it.
> > 
> > After reading the definition of POD, you're right, I'm misusing the term. We thought here about a different naming convention but weren't able to come up with one ("Simple", ...).
> > 
> > I do not want to name it simply RedBlackTree while it has its current restrictions.
> > 
> > I would like to land PODArena, PODRedBlackTree and the forthcoming PODIntervalTree with these names for now, because they are nicely grouped with the prefix.
> 
> I think that's a mistake. Of all the many things a POD is, this class only adheres to one, no dtor. If nothing else you should give these classes a prefix that says "these are for the accelerated 2D renderer, everyone else stay away". It's better to use a meaningless prefix, or no prefix at all, than one that has a specific but wrong meaning.

I don't have a good idea right now for another prefix. If you do, please suggest one, but I'm going to aim to land these classes in their current form. We can svn rename them later, but continual renamings in my own workspaces are making it difficult to land this and subsequent patches.

[Darin Fisher (:fishd, Google)]

(In reply to comment #18)
> > > WebCore/platform/graphics/gpu/PODArena.h:84
> > > +    static PassRefPtr<PODArena> create(Allocator* allocator)
> > nit: this should take a PassRefPtr<Allocator> argument
> 
> I don't think so according to http://webkit.org/coding/RefPtr.html under "Function arguments". Ownership isn't being transferred to the PODArena; it merely increments the reference count of the Allocator.

Because you are storing the pointer into a RefPtr, you are technically giving ownership of the argument to the PODArena.  (The ownership is shared.)


> > > WebCore/platform/graphics/gpu/PODArena.h:200
> > > +    size_t m_currentChunkSize;
> > why have m_currentChunkSize and not just a size() member function
> > on the Chunk class?  (if you want to keep m_currentChunkSize, then
> > perhaps it should at least be listed next to m_current since it is
> > so closely related.)
> 
> Because initially there is no Chunk, but we need to know what size it should be allocated with.

Makes sense.


> > > WebCore/platform/graphics/gpu/PODRedBlackTree.h:53
> > > +//   String valueToString(const T&);
> > nit: valueToString should probably be a const method
> 
> It isn't a method but a function visible at the global scope.

Ah, right.


> > > WebCore/platform/graphics/gpu/PODRedBlackTree.h:121
> > > +    explicit PODRedBlackTree(PODArena* arena)
> > nit: use PassRefPtr<PODArena> here
> 
> See above. I think this is supposed to be a raw pointer.

Ditto.


> > > WebCore/platform/graphics/gpu/PODRedBlackTree.h:446
> > > +            LOG_ERROR("  PODRedBlackTree::InsertNode");
> > why LOG_ERROR?  wouldn't LOG(PODRedBlackTree, "InsertNode") be better?
> > you can see an example of using LOG this way in RefCountedLeakCounter.cpp
> 
> Currently there's no .cpp associated with this class and so no good place to put the WTFLogChannel. I don't think it's worth adding a lot of mechanism just for this debugging output.

OK


> > also how about writing an inline helper function that can have an empty
> > implementation in NDEBUG builds but otherwise call LOG(...).  that way
> > the code in this function will not need #ifdefs.
> 
> Done with logIfVerbose.

Thanks.

[Kenneth Russell]

Created attachment 66425 [details]
Revised patch

Fixed RefCounted arguments to PODArena and PODRedBlackTree's constructors and creation functions to use PassRefPtr.

[Kenneth Russell]

(In reply to comment #20)
> (In reply to comment #18)
> > > > WebCore/platform/graphics/gpu/PODArena.h:84
> > > > +    static PassRefPtr<PODArena> create(Allocator* allocator)
> > > nit: this should take a PassRefPtr<Allocator> argument
> > 
> > I don't think so according to http://webkit.org/coding/RefPtr.html under "Function arguments". Ownership isn't being transferred to the PODArena; it merely increments the reference count of the Allocator.
> 
> Because you are storing the pointer into a RefPtr, you are technically giving ownership of the argument to the PODArena.  (The ownership is shared.)

I see. Revised patch posted.

[Darin Fisher (:fishd, Google)]

Comment on attachment 66425 [details]
Revised patch

R=me modulo the naming discussion.  I think it is reasonable to land this code
as-is to check point it.  Any renaming patch that we settle on will be trivial
to handle as a follow-up patch.

[Darin Fisher (:fishd, Google)]

Just for completeness, if we were to rename PODRedBlackTree to RedBlackTree as Chris suggested, then it would mean renaming PODArena to something other than Arena.  One idea I had for that is to call this class ObjectArena since it is designed to vend objects of type T.  I am still a bit concerned about having no prefix given the destructors-are-not-called constraint.  Another idea is to call these LeakyArena and LeakyRedBlackTree ;-)

[Chris Marrin]

(In reply to comment #24)
> Just for completeness, if we were to rename PODRedBlackTree to RedBlackTree as Chris suggested, then it would mean renaming PODArena to something other than Arena.  One idea I had for that is to call this class ObjectArena since it is designed to vend objects of type T.  I am still a bit concerned about having no prefix given the destructors-are-not-called constraint.  Another idea is to call these LeakyArena and LeakyRedBlackTree ;-)

Seems like the Arena could pretty easily be made to ensure dtors get called

[Kenneth Russell]

Committed r66704: <http://trac.webkit.org/changeset/66704>

[Kenneth Russell]

(In reply to comment #25)
> (In reply to comment #24)
> > Just for completeness, if we were to rename PODRedBlackTree to RedBlackTree as Chris suggested, then it would mean renaming PODArena to something other than Arena.  One idea I had for that is to call this class ObjectArena since it is designed to vend objects of type T.  I am still a bit concerned about having no prefix given the destructors-are-not-called constraint.  Another idea is to call these LeakyArena and LeakyRedBlackTree ;-)
> 
> Seems like the Arena could pretty easily be made to ensure dtors get called

I don't think that is easily possible, but it may turn out to be easy to make the red/black tree and forthcoming interval tree properly call destructors on the data they contain, thereby generalizing them. We can discuss this more after all of the initial code is checkpointed.

[WebKit Review Bot]

http://trac.webkit.org/changeset/66704 might have broken Leopard Intel Debug (Tests)
The following changes are on the blame list:
http://trac.webkit.org/changeset/66704
http://trac.webkit.org/changeset/66705