void GrResourceCache::printStats() {
    int locked = 0;
    int scratch = 0;

    EntryList::Iter iter;

    GrResourceCacheEntry* entry = iter.init(fList, EntryList::Iter::kTail_IterStart);

    for ( ; entry; entry = iter.prev()) {
        if (!entry->fResource->isPurgable()) {
            ++locked;
        }
        if (entry->fResource->cacheAccess().isScratch()) {
            ++scratch;
        }
    }

    float countUtilization = (100.f * fEntryCount) / fMaxCount;
    float byteUtilization = (100.f * fEntryBytes) / fMaxBytes;

    SkDebugf("Budget: %d items %d bytes\n", fMaxCount, fMaxBytes);
    SkDebugf("\t\tEntry Count: current %d (%d locked, %d scratch %.2g%% full), high %d\n",
                fEntryCount, locked, scratch, countUtilization, fHighWaterEntryCount);
    SkDebugf("\t\tEntry Bytes: current %d (%.2g%% full) high %d\n",
                fEntryBytes, byteUtilization, fHighWaterEntryBytes);
}

/**
 * Destroying a resource may potentially trigger the unlock of additional
 * resources which in turn will trigger a nested purge. We block the nested
 * purge using the fPurging variable. However, the initial purge will keep
 * looping until either all resources in the cache are unlocked or we've met
 * the budget. There is an assertion in createAndLock to check against a
 * resource's destructor inserting new resources into the cache. If these
 * new resources were unlocked before purgeAsNeeded completed it could
 * potentially make purgeAsNeeded loop infinitely.
 */
void GrResourceCache::purgeAsNeeded() {
    if (!fPurging) {
        fPurging = true;
        bool withinBudget = false;
        bool changed = false;

        // The purging process is repeated several times since one pass
        // may free up other resources
        do {
            EntryList::Iter iter;

            changed = false;

            // Note: the following code relies on the fact that the
            // doubly linked list doesn't invalidate its data/pointers
            // outside of the specific area where a deletion occurs (e.g.,
            // in internalDetach)
            GrResourceEntry* entry = iter.init(fList, EntryList::Iter::kTail_IterStart);

            while (NULL != entry) {
                GrAutoResourceCacheValidate atcv(this);

                if (fEntryCount <= fMaxCount && fEntryBytes <= fMaxBytes) {
                    withinBudget = true;
                    break;
                }

                GrResourceEntry* prev = iter.prev();
                if (1 == entry->fResource->getRefCnt()) {
                    changed = true;

                    // remove from our cache
                    fCache.remove(entry->key(), entry);

                    // remove from our llist
                    this->internalDetach(entry);

        #if GR_DUMP_TEXTURE_UPLOAD
                    GrPrintf("--- ~resource from cache %p [%d %d]\n",
                             entry->resource(),
                             entry->resource()->width(),
                             entry->resource()->height());
        #endif

                    delete entry;
                }
                entry = prev;
            }
        } while (!withinBudget && changed);
        fPurging = false;
    }
}

size_t GrResourceCache::countBytes(const EntryList& list) {
    size_t bytes = 0;

    EntryList::Iter iter;

    const GrResourceEntry* entry = iter.init(const_cast<EntryList&>(list),
                                             EntryList::Iter::kTail_IterStart);

    for ( ; NULL != entry; entry = iter.prev()) {
        bytes += entry->resource()->sizeInBytes();
    }
    return bytes;
}

void GrResourceCache::validate() const {
    fList.validate();
    fExclusiveList.validate();
    GrAssert(both_zero_or_nonzero(fEntryCount, fEntryBytes));
    GrAssert(both_zero_or_nonzero(fClientDetachedCount, fClientDetachedBytes));
    GrAssert(fClientDetachedBytes <= fEntryBytes);
    GrAssert(fClientDetachedCount <= fEntryCount);
    GrAssert((fEntryCount - fClientDetachedCount) == fCache.count());

    fCache.validate();


    EntryList::Iter iter;

    // check that the exclusively held entries are okay
    const GrResourceEntry* entry = iter.init(const_cast<EntryList&>(fExclusiveList),
                                             EntryList::Iter::kHead_IterStart);

    for ( ; NULL != entry; entry = iter.next()) {
        entry->validate();
    }

    // check that the shareable entries are okay
    entry = iter.init(const_cast<EntryList&>(fList), EntryList::Iter::kHead_IterStart);

    int count = 0;
    for ( ; NULL != entry; entry = iter.next()) {
        entry->validate();
        GrAssert(fCache.find(entry->key()));
        count += 1;
    }
    GrAssert(count == fEntryCount - fClientDetachedCount);

    size_t bytes = countBytes(fList);
    GrAssert(bytes == fEntryBytes  - fClientDetachedBytes);

    bytes = countBytes(fExclusiveList);
    GrAssert(bytes == fClientDetachedBytes);

    GrAssert(fList.countEntries() == fEntryCount - fClientDetachedCount);

    GrAssert(fExclusiveList.countEntries() == fClientDetachedCount);
}

void GrResourceCache::validate() const {
    fList.validate();
    SkASSERT(both_zero_or_nonzero(fEntryCount, fEntryBytes));

    EntryList::Iter iter;

    // check that the shareable entries are okay
    const GrResourceCacheEntry* entry = iter.init(const_cast<EntryList&>(fList),
                                                  EntryList::Iter::kHead_IterStart);

    int count = 0;
    for ( ; entry; entry = iter.next()) {
        entry->validate();
        count += 1;
    }
    SkASSERT(count == fEntryCount);

    size_t bytes = this->countBytes(fList);
    SkASSERT(bytes == fEntryBytes);
    SkASSERT(fList.countEntries() == fEntryCount);
}

void GrResourceCache::printStats() {
    int locked = 0;

    EntryList::Iter iter;

    GrResourceEntry* entry = iter.init(fList, EntryList::Iter::kTail_IterStart);

    for ( ; NULL != entry; entry = iter.prev()) {
        if (entry->fResource->getRefCnt() > 1) {
            ++locked;
        }
    }

    SkDebugf("Budget: %d items %d bytes\n", fMaxCount, fMaxBytes);
    SkDebugf("\t\tEntry Count: current %d (%d locked) high %d\n",
                fEntryCount, locked, fHighWaterEntryCount);
    SkDebugf("\t\tEntry Bytes: current %d high %d\n",
                fEntryBytes, fHighWaterEntryBytes);
    SkDebugf("\t\tDetached Entry Count: current %d high %d\n",
                fClientDetachedCount, fHighWaterClientDetachedCount);
    SkDebugf("\t\tDetached Bytes: current %d high %d\n",
                fClientDetachedBytes, fHighWaterClientDetachedBytes);
}

void GrResourceCache::internalPurge(int extraCount, size_t extraBytes) {
    SkASSERT(fPurging);

    bool withinBudget = false;
    bool changed = false;

    // The purging process is repeated several times since one pass
    // may free up other resources
    do {
        EntryList::Iter iter;

        changed = false;

        // Note: the following code relies on the fact that the
        // doubly linked list doesn't invalidate its data/pointers
        // outside of the specific area where a deletion occurs (e.g.,
        // in internalDetach)
        GrResourceCacheEntry* entry = iter.init(fList, EntryList::Iter::kTail_IterStart);

        while (entry) {
            GrAutoResourceCacheValidate atcv(this);

            if ((fEntryCount+extraCount) <= fMaxCount &&
                (fEntryBytes+extraBytes) <= fMaxBytes) {
                withinBudget = true;
                break;
            }

            GrResourceCacheEntry* prev = iter.prev();
            if (entry->fResource->isPurgable()) {
                changed = true;
                this->deleteResource(entry);
            }
            entry = prev;
        }
    } while (!withinBudget && changed);
}