1/*
2 * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "Collector.h"
28
29#ifndef CollectorHeapIterator_h
30#define CollectorHeapIterator_h
31
32namespace JSC {
33
34    class CollectorHeapIterator {
35    public:
36        bool operator!=(const CollectorHeapIterator& other);
37        JSCell* operator*() const;
38
39    protected:
40        CollectorHeapIterator(CollectorHeap&, size_t startBlock, size_t startCell);
41        void advance(size_t max);
42
43        CollectorHeap& m_heap;
44        size_t m_block;
45        size_t m_cell;
46    };
47
48    class LiveObjectIterator : public CollectorHeapIterator {
49    public:
50        LiveObjectIterator(CollectorHeap&, size_t startBlock, size_t startCell = 0);
51        LiveObjectIterator& operator++();
52    };
53
54    class DeadObjectIterator : public CollectorHeapIterator {
55    public:
56        DeadObjectIterator(CollectorHeap&, size_t startBlock, size_t startCell = 0);
57        DeadObjectIterator& operator++();
58    };
59
60    class ObjectIterator : public CollectorHeapIterator {
61    public:
62        ObjectIterator(CollectorHeap&, size_t startBlock, size_t startCell = 0);
63        ObjectIterator& operator++();
64    };
65
66    inline CollectorHeapIterator::CollectorHeapIterator(CollectorHeap& heap, size_t startBlock, size_t startCell)
67        : m_heap(heap)
68        , m_block(startBlock)
69        , m_cell(startCell)
70    {
71    }
72
73    inline bool CollectorHeapIterator::operator!=(const CollectorHeapIterator& other)
74    {
75        return m_block != other.m_block || m_cell != other.m_cell;
76    }
77
78    inline JSCell* CollectorHeapIterator::operator*() const
79    {
80        return reinterpret_cast<JSCell*>(m_heap.blocks[m_block]->cells + m_cell);
81    }
82
83    // Iterators advance up to the next-to-last -- and not the last -- cell in a
84    // block, since the last cell is a dummy sentinel.
85    inline void CollectorHeapIterator::advance(size_t max)
86    {
87        ++m_cell;
88        if (m_cell == max) {
89            m_cell = 0;
90            ++m_block;
91        }
92    }
93
94    inline LiveObjectIterator::LiveObjectIterator(CollectorHeap& heap, size_t startBlock, size_t startCell)
95        : CollectorHeapIterator(heap, startBlock, startCell - 1)
96    {
97        ++(*this);
98    }
99
100    inline LiveObjectIterator& LiveObjectIterator::operator++()
101    {
102        advance(HeapConstants::cellsPerBlock - 1);
103        if (m_block < m_heap.nextBlock || (m_block == m_heap.nextBlock && m_cell < m_heap.nextCell))
104            return *this;
105
106        while (m_block < m_heap.usedBlocks && !m_heap.blocks[m_block]->marked.get(m_cell))
107            advance(HeapConstants::cellsPerBlock - 1);
108        return *this;
109    }
110
111    inline DeadObjectIterator::DeadObjectIterator(CollectorHeap& heap, size_t startBlock, size_t startCell)
112        : CollectorHeapIterator(heap, startBlock, startCell - 1)
113    {
114        ++(*this);
115    }
116
117    inline DeadObjectIterator& DeadObjectIterator::operator++()
118    {
119        do {
120            advance(HeapConstants::cellsPerBlock - 1);
121            ASSERT(m_block > m_heap.nextBlock || (m_block == m_heap.nextBlock && m_cell >= m_heap.nextCell));
122        } while (m_block < m_heap.usedBlocks && m_heap.blocks[m_block]->marked.get(m_cell));
123        return *this;
124    }
125
126    inline ObjectIterator::ObjectIterator(CollectorHeap& heap, size_t startBlock, size_t startCell)
127        : CollectorHeapIterator(heap, startBlock, startCell - 1)
128    {
129        ++(*this);
130    }
131
132    inline ObjectIterator& ObjectIterator::operator++()
133    {
134        advance(HeapConstants::cellsPerBlock - 1);
135        return *this;
136    }
137
138} // namespace JSC
139
140#endif // CollectorHeapIterator_h
141