234 lines
6.6 KiB
C++
234 lines
6.6 KiB
C++
/*
|
|
* Copyright (C) 2000 Lars Knoll (knoll@kde.org)
|
|
* Copyright (C) 2003, 2004, 2006, 2007, 2008 Apple Inc. All right reserved.
|
|
* Copyright (C) 2011 Google, Inc. All rights reserved.
|
|
*
|
|
* This library is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU Library General Public
|
|
* License as published by the Free Software Foundation; either
|
|
* version 2 of the License, or (at your option) any later version.
|
|
*
|
|
* This library is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
* Library General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU Library General Public License
|
|
* along with this library; see the file COPYING.LIB. If not, write to
|
|
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
|
|
* Boston, MA 02110-1301, USA.
|
|
*
|
|
*/
|
|
|
|
#ifndef BidiRunList_h
|
|
#define BidiRunList_h
|
|
|
|
#include <wtf/Noncopyable.h>
|
|
|
|
namespace WebCore {
|
|
|
|
template <class Run>
|
|
class BidiRunList {
|
|
WTF_MAKE_NONCOPYABLE(BidiRunList);
|
|
public:
|
|
BidiRunList()
|
|
: m_lastRun(nullptr)
|
|
, m_logicallyLastRun(nullptr)
|
|
, m_runCount(0)
|
|
{
|
|
}
|
|
|
|
// FIXME: Once BidiResolver no longer owns the BidiRunList,
|
|
// then ~BidiRunList should call deleteRuns() automatically.
|
|
|
|
Run* firstRun() const { return m_firstRun.get(); }
|
|
Run* lastRun() const { return m_lastRun; }
|
|
Run* logicallyLastRun() const { return m_logicallyLastRun; }
|
|
unsigned runCount() const { return m_runCount; }
|
|
|
|
void appendRun(std::unique_ptr<Run>&&);
|
|
void prependRun(std::unique_ptr<Run>&&);
|
|
|
|
void moveRunToEnd(Run*);
|
|
void moveRunToBeginning(Run*);
|
|
|
|
void clear();
|
|
void reverseRuns(unsigned start, unsigned end);
|
|
void reorderRunsFromLevels();
|
|
|
|
void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; }
|
|
|
|
void replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns);
|
|
|
|
private:
|
|
|
|
// The runs form a singly-linked-list, where the links (Run::m_next) imply ownership (and are of type std::unique_ptr).
|
|
// The raw pointers below point into the singly-linked-list.
|
|
std::unique_ptr<Run> m_firstRun; // The head of the list
|
|
Run* m_lastRun;
|
|
Run* m_logicallyLastRun;
|
|
unsigned m_runCount;
|
|
};
|
|
|
|
template <class Run>
|
|
inline void BidiRunList<Run>::appendRun(std::unique_ptr<Run>&& run)
|
|
{
|
|
if (!m_firstRun) {
|
|
m_firstRun = WTFMove(run);
|
|
m_lastRun = m_firstRun.get();
|
|
} else {
|
|
m_lastRun->setNext(WTFMove(run));
|
|
m_lastRun = m_lastRun->next();
|
|
}
|
|
m_runCount++;
|
|
}
|
|
|
|
template <class Run>
|
|
inline void BidiRunList<Run>::prependRun(std::unique_ptr<Run>&& run)
|
|
{
|
|
ASSERT(!run->next());
|
|
|
|
if (!m_lastRun)
|
|
m_lastRun = run.get();
|
|
else
|
|
run->setNext(WTFMove(m_firstRun));
|
|
m_firstRun = WTFMove(run);
|
|
m_runCount++;
|
|
}
|
|
|
|
template <class Run>
|
|
inline void BidiRunList<Run>::moveRunToEnd(Run* run)
|
|
{
|
|
ASSERT(m_firstRun);
|
|
ASSERT(m_lastRun);
|
|
ASSERT(run->next());
|
|
|
|
Run* previous = nullptr;
|
|
Run* current = m_firstRun.get();
|
|
while (current != run) {
|
|
previous = current;
|
|
current = previous->next();
|
|
}
|
|
|
|
if (!previous) {
|
|
ASSERT(m_firstRun.get() == run);
|
|
std::unique_ptr<Run> originalFirstRun = WTFMove(m_firstRun);
|
|
m_firstRun = originalFirstRun->takeNext();
|
|
m_lastRun->setNext(WTFMove(originalFirstRun));
|
|
} else {
|
|
std::unique_ptr<Run> target = previous->takeNext();
|
|
previous->setNext(current->takeNext());
|
|
m_lastRun->setNext(WTFMove(target));
|
|
}
|
|
}
|
|
|
|
template <class Run>
|
|
inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
|
|
{
|
|
ASSERT(m_firstRun);
|
|
ASSERT(m_lastRun);
|
|
ASSERT(run != m_firstRun.get());
|
|
|
|
Run* previous = m_firstRun.get();
|
|
Run* current = previous->next();
|
|
while (current != run) {
|
|
previous = current;
|
|
current = previous->next();
|
|
}
|
|
|
|
std::unique_ptr<Run> target = previous->takeNext();
|
|
previous->setNext(run->takeNext());
|
|
if (run == m_lastRun)
|
|
m_lastRun = previous;
|
|
|
|
target->setNext(WTFMove(m_firstRun));
|
|
m_firstRun = WTFMove(target);
|
|
}
|
|
|
|
template <class Run>
|
|
void BidiRunList<Run>::replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns)
|
|
{
|
|
ASSERT(newRuns.runCount());
|
|
ASSERT(m_firstRun);
|
|
ASSERT(toReplace);
|
|
|
|
m_runCount += newRuns.runCount() - 1; // We are adding the new runs and removing toReplace.
|
|
|
|
// Fix up any pointers which may end up stale.
|
|
if (m_lastRun == toReplace)
|
|
m_lastRun = newRuns.lastRun();
|
|
if (m_logicallyLastRun == toReplace)
|
|
m_logicallyLastRun = newRuns.logicallyLastRun();
|
|
|
|
if (m_firstRun.get() == toReplace) {
|
|
newRuns.m_lastRun->setNext(m_firstRun->takeNext());
|
|
m_firstRun = WTFMove(newRuns.m_firstRun);
|
|
} else {
|
|
// Find the run just before "toReplace" in the list of runs.
|
|
Run* previousRun = m_firstRun.get();
|
|
while (previousRun->next() != toReplace)
|
|
previousRun = previousRun->next();
|
|
ASSERT(previousRun);
|
|
|
|
std::unique_ptr<Run> target = previousRun->takeNext();
|
|
previousRun->setNext(WTFMove(newRuns.m_firstRun));
|
|
newRuns.m_lastRun->setNext(target->takeNext());
|
|
}
|
|
|
|
newRuns.clear();
|
|
}
|
|
|
|
template <class Run>
|
|
void BidiRunList<Run>::clear()
|
|
{
|
|
m_firstRun = nullptr;
|
|
m_lastRun = nullptr;
|
|
m_logicallyLastRun = nullptr;
|
|
m_runCount = 0;
|
|
}
|
|
|
|
template <class Run>
|
|
void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
|
|
{
|
|
if (start >= end)
|
|
return;
|
|
|
|
ASSERT_WITH_SECURITY_IMPLICATION(end < m_runCount);
|
|
|
|
// Get the item before the start of the runs to reverse and put it in
|
|
// |beforeStart|. |curr| should point to the first run to reverse.
|
|
Run* curr = m_firstRun.get();
|
|
Run* beforeStart = nullptr;
|
|
unsigned i = 0;
|
|
for (; i < start; ++i) {
|
|
beforeStart = curr;
|
|
curr = curr->next();
|
|
}
|
|
Run* startRun = curr;
|
|
|
|
for (; i < end; ++i)
|
|
curr = curr->next();
|
|
|
|
if (!curr->next())
|
|
m_lastRun = startRun;
|
|
|
|
// Standard "sliding window" of 3 pointers
|
|
std::unique_ptr<Run> previous = curr->takeNext();
|
|
std::unique_ptr<Run> current = beforeStart ? beforeStart->takeNext() : WTFMove(m_firstRun);
|
|
while (current) {
|
|
std::unique_ptr<Run> next = current->takeNext();
|
|
current->setNext(WTFMove(previous));
|
|
previous = WTFMove(current);
|
|
current = WTFMove(next);
|
|
}
|
|
|
|
if (beforeStart)
|
|
beforeStart->setNext(WTFMove(previous));
|
|
else
|
|
m_firstRun = WTFMove(previous);
|
|
}
|
|
|
|
} // namespace WebCore
|
|
|
|
#endif // BidiRunList
|