/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

 * vim: set ts=8 sts=4 et sw=4 tw=99:

 * This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this

 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef gc_ArenaList_inl_h

#define gc_ArenaList_inl_h

#include "gc/ArenaList.h"

#include "gc/Heap.h"

void

js::gc::SortedArenaListSegment::append(Arena* arena)

{

    MOZ_ASSERT(arena);

    MOZ_ASSERT_IF(head, head->getAllocKind() == arena->getAllocKind());

    *tailp = arena;

    tailp = &arena->next;

}

inline

js::gc::ArenaList::ArenaList()

{

    clear();

}

void

js::gc::ArenaList::copy(const ArenaList& other)

{

    other.check();

    head_ = other.head_;

    cursorp_ = other.isCursorAtHead() ? &head_ : other.cursorp_;

    check();

}

inline

js::gc::ArenaList::ArenaList(const ArenaList& other)

{

    copy(other);

}

js::gc::ArenaList&

js::gc::ArenaList::operator=(const ArenaList& other)

{

    copy(other);

    return *this;

}

inline

js::gc::ArenaList::ArenaList(const SortedArenaListSegment& segment)

{

    head_ = segment.head;

    cursorp_ = segment.isEmpty() ? &head_ : segment.tailp;

    check();

}

// This does checking just of |head_| and |cursorp_|.

void

js::gc::ArenaList::check() const

{

#ifdef DEBUG

    // If the list is empty, it must have this form.

    MOZ_ASSERT_IF(!head_, cursorp_ == &head_);

    // If there's an arena following the cursor, it must not be full.

    Arena* cursor = *cursorp_;

    MOZ_ASSERT_IF(cursor, cursor->hasFreeThings());

#endif

}

void

js::gc::ArenaList::clear()

{

    head_ = nullptr;

    cursorp_ = &head_;

    check();

}

js::gc::ArenaList

js::gc::ArenaList::copyAndClear()

{

    ArenaList result = *this;

    clear();

    return result;

}

bool

js::gc::ArenaList::isEmpty() const

{

    check();

    return !head_;

}

js::gc::Arena*

js::gc::ArenaList::head() const

{

    check();

    return head_;

}

bool

js::gc::ArenaList::isCursorAtHead() const

{

    check();

    return cursorp_ == &head_;

}

bool

js::gc::ArenaList::isCursorAtEnd() const

{

    check();

    return !*cursorp_;

}

void

js::gc::ArenaList::moveCursorToEnd()

{

    while (!isCursorAtEnd()) {

        cursorp_ = &(*cursorp_)->next;

    }

}

js::gc::Arena*

js::gc::ArenaList::arenaAfterCursor() const

{

    check();

    return *cursorp_;

}

js::gc::Arena*

js::gc::ArenaList::takeNextArena()

{

    check();

    Arena* arena = *cursorp_;

    if (!arena) {

        return nullptr;

    }

    cursorp_ = &arena->next;

    check();

    return arena;

}

void

js::gc::ArenaList::insertAtCursor(Arena* a)

{

    check();

    a->next = *cursorp_;

    *cursorp_ = a;

    // At this point, the cursor is sitting before |a|. Move it after |a|

    // if necessary.

    if (!a->hasFreeThings()) {

        cursorp_ = &a->next;

    }

    check();

}

void

js::gc::ArenaList::insertBeforeCursor(Arena* a)

{

    check();

    a->next = *cursorp_;

    *cursorp_ = a;

    cursorp_ = &a->next;

    check();

}

js::gc::ArenaList&

js::gc::ArenaList::insertListWithCursorAtEnd(const ArenaList& other)

{

    check();

    other.check();

    MOZ_ASSERT(other.isCursorAtEnd());

    if (other.isCursorAtHead()) {

        return *this;

    }

    // Insert the full arenas of |other| after those of |this|.

    *other.cursorp_ = *cursorp_;

    *cursorp_ = other.head_;

    cursorp_ = other.cursorp_;

    check();

    return *this;

}

js::gc::SortedArenaList::SortedArenaList(size_t thingsPerArena)

{

    reset(thingsPerArena);

}

void

js::gc::SortedArenaList::setThingsPerArena(size_t thingsPerArena)

{

    MOZ_ASSERT(thingsPerArena && thingsPerArena <= MaxThingsPerArena);

    thingsPerArena_ = thingsPerArena;

}

void

js::gc::SortedArenaList::reset(size_t thingsPerArena)

{

    setThingsPerArena(thingsPerArena);

    // Initialize the segments.

    for (size_t i = 0; i <= thingsPerArena; ++i) {

        segments[i].clear();

    }

}

void

js::gc::SortedArenaList::insertAt(Arena* arena, size_t nfree)

{

    MOZ_ASSERT(nfree <= thingsPerArena_);

    segments[nfree].append(arena);

}

void

js::gc::SortedArenaList::extractEmpty(Arena** empty)

{

    SortedArenaListSegment& segment = segments[thingsPerArena_];

    if (segment.head) {

        *segment.tailp = *empty;

        *empty = segment.head;

        segment.clear();

    }

}

js::gc::ArenaList

js::gc::SortedArenaList::toArenaList()

{

    // Link the non-empty segment tails up to the non-empty segment heads.

    size_t tailIndex = 0;

    for (size_t headIndex = 1; headIndex <= thingsPerArena_; ++headIndex) {

        if (headAt(headIndex)) {

            segments[tailIndex].linkTo(headAt(headIndex));

            tailIndex = headIndex;

        }

    }

    // Point the tail of the final non-empty segment at null. Note that if

    // the list is empty, this will just set segments[0].head to null.

    segments[tailIndex].linkTo(nullptr);

    // Create an ArenaList with head and cursor set to the head and tail of

    // the first segment (if that segment is empty, only the head is used).

    return ArenaList(segments[0]);

}

#ifdef DEBUG

bool

js::gc::FreeLists::allEmpty() const

{

    for (auto i : AllAllocKinds()) {

        if (!isEmpty(i)) {

            return false;

        }

    }

    return true;

}

bool

js::gc::FreeLists::isEmpty(AllocKind kind) const

{

    return freeLists_[kind]->isEmpty();

}

#endif

void

js::gc::FreeLists::clear()

{

    for (auto i : AllAllocKinds()) {

#ifdef DEBUG

        auto old = freeLists_[i];

        if (!old->isEmpty()) {

            old->getArena()->checkNoMarkedFreeCells();

        }

#endif

        freeLists_[i] = &emptySentinel;

    }

}

js::gc::TenuredCell*

js::gc::FreeLists::allocate(AllocKind kind)

{

    return freeLists_[kind]->allocate(Arena::thingSize(kind));

}

void

js::gc::FreeLists::unmarkPreMarkedFreeCells(AllocKind kind)

{

    FreeSpan* freeSpan = freeLists_[kind];

    if (!freeSpan->isEmpty()) {

        freeSpan->getArena()->unmarkPreMarkedFreeCells();

    }

}

JSRuntime*

js::gc::ArenaLists::runtime()

{

    return zone_->runtimeFromMainThread();

}

JSRuntime*

js::gc::ArenaLists::runtimeFromAnyThread()

{

    return zone_->runtimeFromAnyThread();

}

js::gc::Arena*

js::gc::ArenaLists::getFirstArena(AllocKind thingKind) const

{

    return arenaLists(thingKind).head();

}

js::gc::Arena*

js::gc::ArenaLists::getFirstArenaToSweep(AllocKind thingKind) const

{

    return arenaListsToSweep(thingKind);

}

js::gc::Arena*

js::gc::ArenaLists::getFirstSweptArena(AllocKind thingKind) const

{

    if (thingKind != incrementalSweptArenaKind.ref()) {

        return nullptr;

    }

    return incrementalSweptArenas.ref().head();

}

js::gc::Arena*

js::gc::ArenaLists::getArenaAfterCursor(AllocKind thingKind) const

{

    return arenaLists(thingKind).arenaAfterCursor();

}

bool

js::gc::ArenaLists::arenaListsAreEmpty() const

{

    for (auto i : AllAllocKinds()) {

        /*

         * The arena cannot be empty if the background finalization is not yet

         * done.

         */

        if (concurrentUse(i) == ConcurrentUse::BackgroundFinalize) {

            return false;

        }

        if (!arenaLists(i).isEmpty()) {

            return false;

        }

    }

    return true;

}

void

js::gc::ArenaLists::unmarkAll()

{

    for (auto i : AllAllocKinds()) {

        /* The background finalization must have stopped at this point. */

        MOZ_ASSERT(concurrentUse(i) == ConcurrentUse::None);

        for (Arena* arena = arenaLists(i).head(); arena; arena = arena->next) {

            arena->unmarkAll();

        }

    }

}

bool

js::gc::ArenaLists::doneBackgroundFinalize(AllocKind kind) const

{

    return concurrentUse(kind) != ConcurrentUse::BackgroundFinalize;

}

bool

js::gc::ArenaLists::needBackgroundFinalizeWait(AllocKind kind) const

{

    return concurrentUse(kind) == ConcurrentUse::BackgroundFinalize;

}

void

js::gc::ArenaLists::clearFreeLists()

{

    freeLists().clear();

}

MOZ_ALWAYS_INLINE js::gc::TenuredCell*

js::gc::ArenaLists::allocateFromFreeList(AllocKind thingKind)

{

    return freeLists().allocate(thingKind);

}

void

js::gc::ArenaLists::unmarkPreMarkedFreeCells()

{

    for (auto i : AllAllocKinds()) {

        freeLists().unmarkPreMarkedFreeCells(i);

    }

}

void

js::gc::ArenaLists::checkEmptyFreeLists()

{

    MOZ_ASSERT(freeLists().allEmpty());

}

bool

js::gc::ArenaLists::checkEmptyArenaLists()

{

    bool empty = true;

#ifdef DEBUG

    for (auto i : AllAllocKinds()) {

        if (!checkEmptyArenaList(i)) {

            empty = false;

        }

    }

#endif

    return empty;

}

#endif // gc_ArenaList_inl_h