Changeset 66704 in webkit


Ignore:
Timestamp:
Sep 2, 2010 7:10:37 PM (14 years ago)
Author:
kbr@google.com
Message:

2010-09-02 Kenneth Russell <kbr@google.com>

Reviewed by Darin Fisher.

Add red-black tree capable of holding plain old data (POD)
https://bugs.webkit.org/show_bug.cgi?id=45059

Adding an augmentable red-black tree capable of holding Plain Old
Data (POD), or classes bottoming out into only POD, and an
associated PODArena. 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.

These classes are being placed under WebCore/platform/graphics/gpu
for the time being. If they are generalized to hold even data
types which internally perform dynamic memory allocation, we may
consider moving them to WTF in the future.

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

  • WebCore.gypi:
  • platform/graphics/gpu/PODArena.h: Added. (WebCore::PODArena::Allocator::~Allocator): (WebCore::PODArena::FastMallocAllocator::create): (WebCore::PODArena::FastMallocAllocator::allocate): (WebCore::PODArena::FastMallocAllocator::free): (WebCore::PODArena::FastMallocAllocator::FastMallocAllocator): (WebCore::PODArena::create): (WebCore::PODArena::allocateObject): (WebCore::PODArena::~PODArena): (WebCore::PODArena::PODArena): (WebCore::PODArena::minAlignment): (WebCore::PODArena::roundUp): (WebCore::PODArena::Chunk::Chunk): (WebCore::PODArena::Chunk::~Chunk): (WebCore::PODArena::Chunk::allocate):
  • platform/graphics/gpu/PODRedBlackTree.h: Added. (WebCore::PODRedBlackTree::Visitor::~Visitor): (WebCore::PODRedBlackTree::PODRedBlackTree): (WebCore::PODRedBlackTree::~PODRedBlackTree): (WebCore::PODRedBlackTree::add): (WebCore::PODRedBlackTree::remove): (WebCore::PODRedBlackTree::contains): (WebCore::PODRedBlackTree::visitInorder): (WebCore::PODRedBlackTree::size): (WebCore::PODRedBlackTree::setNeedsFullOrderingComparisons): (WebCore::PODRedBlackTree::checkInvariants): (WebCore::PODRedBlackTree::dump): (WebCore::PODRedBlackTree::setVerboseDebugging): (WebCore::PODRedBlackTree::Node::Node): (WebCore::PODRedBlackTree::Node::~Node): (WebCore::PODRedBlackTree::Node::color): (WebCore::PODRedBlackTree::Node::setColor): (WebCore::PODRedBlackTree::Node::data): (WebCore::PODRedBlackTree::Node::copyFrom): (WebCore::PODRedBlackTree::Node::left): (WebCore::PODRedBlackTree::Node::setLeft): (WebCore::PODRedBlackTree::Node::right): (WebCore::PODRedBlackTree::Node::setRight): (WebCore::PODRedBlackTree::Node::parent): (WebCore::PODRedBlackTree::Node::setParent): (WebCore::PODRedBlackTree::root): (WebCore::PODRedBlackTree::updateNode): (WebCore::PODRedBlackTree::treeSearch): (WebCore::PODRedBlackTree::treeSearchNormal): (WebCore::PODRedBlackTree::treeSearchFullComparisons): (WebCore::PODRedBlackTree::treeInsert): (WebCore::PODRedBlackTree::treeSuccessor): (WebCore::PODRedBlackTree::treeMinimum): (WebCore::PODRedBlackTree::propagateUpdates): (WebCore::PODRedBlackTree::leftRotate): (WebCore::PODRedBlackTree::rightRotate): (WebCore::PODRedBlackTree::insertNode): (WebCore::PODRedBlackTree::deleteFixup): (WebCore::PODRedBlackTree::deleteNode): (WebCore::PODRedBlackTree::visitInorderImpl): (WebCore::PODRedBlackTree::Counter::Counter): (WebCore::PODRedBlackTree::Counter::visit): (WebCore::PODRedBlackTree::Counter::count): (WebCore::PODRedBlackTree::checkInvariantsFromNode): (WebCore::PODRedBlackTree::logIfVerbose): (WebCore::PODRedBlackTree::dumpFromNode):
Location:
trunk/WebCore
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/WebCore/ChangeLog

    r66700 r66704  
     12010-09-02  Kenneth Russell  <kbr@google.com>
     2
     3        Reviewed by Darin Fisher.
     4
     5        Add red-black tree capable of holding plain old data (POD)
     6        https://bugs.webkit.org/show_bug.cgi?id=45059
     7
     8        Adding an augmentable red-black tree capable of holding Plain Old
     9        Data (POD), or classes bottoming out into only POD, and an
     10        associated PODArena. Note that the PODArena will be used by other
     11        classes to allocate temporary structures, which is why it is not
     12        just an implementation detail of the red-black tree.
     13
     14        These classes are being placed under WebCore/platform/graphics/gpu
     15        for the time being. If they are generalized to hold even data
     16        types which internally perform dynamic memory allocation, we may
     17        consider moving them to WTF in the future.
     18
     19        Unit tests for the PODRedBlackTree will be integrated separately
     20        under bug 45060.
     21
     22        * WebCore.gypi:
     23        * platform/graphics/gpu/PODArena.h: Added.
     24        (WebCore::PODArena::Allocator::~Allocator):
     25        (WebCore::PODArena::FastMallocAllocator::create):
     26        (WebCore::PODArena::FastMallocAllocator::allocate):
     27        (WebCore::PODArena::FastMallocAllocator::free):
     28        (WebCore::PODArena::FastMallocAllocator::FastMallocAllocator):
     29        (WebCore::PODArena::create):
     30        (WebCore::PODArena::allocateObject):
     31        (WebCore::PODArena::~PODArena):
     32        (WebCore::PODArena::PODArena):
     33        (WebCore::PODArena::minAlignment):
     34        (WebCore::PODArena::roundUp):
     35        (WebCore::PODArena::Chunk::Chunk):
     36        (WebCore::PODArena::Chunk::~Chunk):
     37        (WebCore::PODArena::Chunk::allocate):
     38        * platform/graphics/gpu/PODRedBlackTree.h: Added.
     39        (WebCore::PODRedBlackTree::Visitor::~Visitor):
     40        (WebCore::PODRedBlackTree::PODRedBlackTree):
     41        (WebCore::PODRedBlackTree::~PODRedBlackTree):
     42        (WebCore::PODRedBlackTree::add):
     43        (WebCore::PODRedBlackTree::remove):
     44        (WebCore::PODRedBlackTree::contains):
     45        (WebCore::PODRedBlackTree::visitInorder):
     46        (WebCore::PODRedBlackTree::size):
     47        (WebCore::PODRedBlackTree::setNeedsFullOrderingComparisons):
     48        (WebCore::PODRedBlackTree::checkInvariants):
     49        (WebCore::PODRedBlackTree::dump):
     50        (WebCore::PODRedBlackTree::setVerboseDebugging):
     51        (WebCore::PODRedBlackTree::Node::Node):
     52        (WebCore::PODRedBlackTree::Node::~Node):
     53        (WebCore::PODRedBlackTree::Node::color):
     54        (WebCore::PODRedBlackTree::Node::setColor):
     55        (WebCore::PODRedBlackTree::Node::data):
     56        (WebCore::PODRedBlackTree::Node::copyFrom):
     57        (WebCore::PODRedBlackTree::Node::left):
     58        (WebCore::PODRedBlackTree::Node::setLeft):
     59        (WebCore::PODRedBlackTree::Node::right):
     60        (WebCore::PODRedBlackTree::Node::setRight):
     61        (WebCore::PODRedBlackTree::Node::parent):
     62        (WebCore::PODRedBlackTree::Node::setParent):
     63        (WebCore::PODRedBlackTree::root):
     64        (WebCore::PODRedBlackTree::updateNode):
     65        (WebCore::PODRedBlackTree::treeSearch):
     66        (WebCore::PODRedBlackTree::treeSearchNormal):
     67        (WebCore::PODRedBlackTree::treeSearchFullComparisons):
     68        (WebCore::PODRedBlackTree::treeInsert):
     69        (WebCore::PODRedBlackTree::treeSuccessor):
     70        (WebCore::PODRedBlackTree::treeMinimum):
     71        (WebCore::PODRedBlackTree::propagateUpdates):
     72        (WebCore::PODRedBlackTree::leftRotate):
     73        (WebCore::PODRedBlackTree::rightRotate):
     74        (WebCore::PODRedBlackTree::insertNode):
     75        (WebCore::PODRedBlackTree::deleteFixup):
     76        (WebCore::PODRedBlackTree::deleteNode):
     77        (WebCore::PODRedBlackTree::visitInorderImpl):
     78        (WebCore::PODRedBlackTree::Counter::Counter):
     79        (WebCore::PODRedBlackTree::Counter::visit):
     80        (WebCore::PODRedBlackTree::Counter::count):
     81        (WebCore::PODRedBlackTree::checkInvariantsFromNode):
     82        (WebCore::PODRedBlackTree::logIfVerbose):
     83        (WebCore::PODRedBlackTree::dumpFromNode):
     84
    1852010-09-02  Rafael Antognolli  <antognolli@profusion.mobi>
    286
  • trunk/WebCore/WebCore.gypi

    r66586 r66704  
    23422342            'platform/graphics/filters/SourceGraphic.cpp',
    23432343            'platform/graphics/filters/SourceGraphic.h',
     2344            'platform/graphics/gpu/PODArena.h',
     2345            'platform/graphics/gpu/PODRedBlackTree.h',
    23442346            'platform/graphics/gpu/Shader.cpp',
    23452347            'platform/graphics/gpu/Shader.h',
Note: See TracChangeset for help on using the changeset viewer.