Changeset 87408 in webkit


Ignore:
Timestamp:
May 26, 2011 11:54:25 AM (13 years ago)
Author:
ggaren@apple.com
Message:

2011-05-26 Geoffrey Garen <​ggaren@apple.com>

Reviewed by Oliver Hunt.

Filled out some features in DoublyLinkedList
​https://bugs.webkit.org/show_bug.cgi?id=61549

  • heap/MarkedBlock.h: Use DoublyLinkedListNode to simplify our class definition.
  • wtf/DoublyLinkedList.h: (WTF::::DoublyLinkedListNode): (WTF::::setPrev): (WTF::::setNext): (WTF::::prev): (WTF::::next): Added a helper base class for being a node in a list. The odd idioms here allow subclasses to choose their own data member layout, which is sometimes important for performance.

(WTF::::DoublyLinkedList):
(WTF::::isEmpty):
(WTF::::size):
(WTF::::clear):
(WTF::::head):
(WTF::::append):
(WTF::::remove):
(WTF::::removeHead): Change "Node" to "T" to be more idiomatic, and added
clear(), removeHead(), and size() functions.

Location:
trunk/Source/JavaScriptCore
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r87406 r87408  
     12011-05-26  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Reviewed by Oliver Hunt.
     4
     5        Filled out some features in DoublyLinkedList
     6        https://bugs.webkit.org/show_bug.cgi?id=61549
     7
     8        * heap/MarkedBlock.h: Use DoublyLinkedListNode to simplify our class
     9        definition.
     10
     11        * wtf/DoublyLinkedList.h:
     12        (WTF::::DoublyLinkedListNode):
     13        (WTF::::setPrev):
     14        (WTF::::setNext):
     15        (WTF::::prev):
     16        (WTF::::next): Added a helper base class for being a node in a list.
     17        The odd idioms here allow subclasses to choose their own data member
     18        layout, which is sometimes important for performance.
     19
     20        (WTF::::DoublyLinkedList):
     21        (WTF::::isEmpty):
     22        (WTF::::size):
     23        (WTF::::clear):
     24        (WTF::::head):
     25        (WTF::::append):
     26        (WTF::::remove):
     27        (WTF::::removeHead): Change "Node" to "T" to be more idiomatic, and added
     28        clear(), removeHead(), and size() functions.
     29
    1302011-05-26  Geoffrey Garen  <ggaren@apple.com>
    231

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.cpp

    r86974 r87408  
    5353    , m_allocation(allocation)
    5454    , m_heap(&globalData->heap)
    55     , m_prev(0)
    56     , m_next(0)
    5755{
    5856    m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r86974 r87408  
    2424
    2525#include <wtf/Bitmap.h>
     26#include <wtf/DoublyLinkedList.h>
    2627#include <wtf/PageAllocationAligned.h>
    2728#include <wtf/StdLibExtras.h>
    … …  
    3738    static const size_t KB = 1024;
    3839
    39     class MarkedBlock {
     40    class MarkedBlock : public DoublyLinkedListNode<MarkedBlock> {
     41        friend class DoublyLinkedListNode<MarkedBlock>;
    4042    public:
    4143        static const size_t atomSize = sizeof(double); // Ensures natural alignment for all built-in types.
    … …  
    5052        Heap* heap() const;
    5153
    52         void setPrev(MarkedBlock*);
    53         void setNext(MarkedBlock*);
    54         MarkedBlock* prev() const;
    55         MarkedBlock* next() const;
    56        
    5754        void* allocate();
    5855        void reset();
    … …  
    125122    }
    126123
    127     inline void MarkedBlock::setPrev(MarkedBlock* prev)
    128     {
    129         m_prev = prev;
    130     }
    131 
    132     inline void MarkedBlock::setNext(MarkedBlock* next)
    133     {
    134         m_next = next;
    135     }
    136 
    137     inline MarkedBlock* MarkedBlock::prev() const
    138     {
    139         return m_prev;
    140     }
    141 
    142     inline MarkedBlock* MarkedBlock::next() const
    143     {
    144         return m_next;
    145     }
    146 
    147124    inline void MarkedBlock::reset()
    148125    {

  • trunk/Source/JavaScriptCore/wtf/DoublyLinkedList.h

    r79472 r87408  
    2929namespace WTF {
    3030
    31 template <typename Node> class DoublyLinkedList {
     31// This class allows nodes to share code without dictating data member layout.
     32template<typename T> class DoublyLinkedListNode {
     33public:
     34    DoublyLinkedListNode();
     35   
     36    void setPrev(T*);
     37    void setNext(T*);
     38   
     39    T* prev() const;
     40    T* next() const;
     41};
     42
     43template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode()
     44{
     45    setPrev(0);
     46    setNext(0);
     47}
     48
     49template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev)
     50{
     51    static_cast<T*>(this)->m_prev = prev;
     52}
     53
     54template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next)
     55{
     56    static_cast<T*>(this)->m_next = next;
     57}
     58
     59template<typename T> inline T* DoublyLinkedListNode<T>::prev() const
     60{
     61    return static_cast<const T*>(this)->m_prev;
     62}
     63
     64template<typename T> inline T* DoublyLinkedListNode<T>::next() const
     65{
     66    return static_cast<const T*>(this)->m_next;
     67}
     68
     69template<typename T> class DoublyLinkedList {
    3270public:
    3371    DoublyLinkedList();
    3472   
    35     bool isEmpty();
     73    bool isEmpty() const;
     74    size_t size() const; // This is O(n).
     75    void clear();
    3676
    37     Node* head();
     77    T* head() const;
     78    T* removeHead();
    3879
    39     void append(Node*);
    40     void remove(Node*);
     80    void append(T*);
     81    void remove(T*);
    4182
    4283private:
    43     Node* m_head;
    44     Node* m_tail;
     84    T* m_head;
     85    T* m_tail;
    4586};
    4687
    47 template <typename Node> inline DoublyLinkedList<Node>::DoublyLinkedList()
     88template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList()
    4889    : m_head(0)
    4990    , m_tail(0)
    … …  
    5192}
    5293
    53 template <typename Node> inline bool DoublyLinkedList<Node>::isEmpty()
     94template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const
    5495{
    5596    return !m_head;
    5697}
    5798
    58 template <typename Node> inline Node* DoublyLinkedList<Node>::head()
     99template<typename T> inline size_t DoublyLinkedList<T>::size() const
     100{
     101    size_t size = 0;
     102    for (T* node = m_head; node; node = node->next())
     103        ++size;
     104    return size;
     105}
     106
     107template<typename T> inline void DoublyLinkedList<T>::clear()
     108{
     109    m_head = 0;
     110    m_tail = 0;
     111}
     112
     113template<typename T> inline T* DoublyLinkedList<T>::head() const
    59114{
    60115    return m_head;
    61116}
    62117
    63 template <typename Node> inline void DoublyLinkedList<Node>::append(Node* node)
     118template<typename T> inline void DoublyLinkedList<T>::append(T* node)
    64119{
    65120    if (!m_tail) {
    … …  
    79134}
    80135
    81 template <typename Node> inline void DoublyLinkedList<Node>::remove(Node* node)
     136template<typename T> inline void DoublyLinkedList<T>::remove(T* node)
    82137{
    83138    if (node->prev()) {
    … …  
    98153}
    99154
     155template<typename T> inline T* DoublyLinkedList<T>::removeHead()
     156{
     157    T* node = head();
     158    if (node)
     159        remove(node);
     160    return node;
     161}
     162
    100163} // namespace WTF
    101164
     165using WTF::DoublyLinkedListNode;
    102166using WTF::DoublyLinkedList;
    103167
Note: See TracChangeset for help on using the changeset viewer.