| /* |
| * 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 |