/*
 * Copyright 2019 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkCharToGlyphCache.h"
#include "../private/SkTFitsIn.h"

// TODO: consider faster ways to search big arrays
//       bsearch
//       slope-based (since we can compute a slope from first and last values)
//
//       Also, consider adding sentinels to key arrays so we don't have to check that
//       index is in rage.
//
template <typename T> int find_index(const T* base, int count, T value) {
    for (int index = 0; index < count; ++index) {
        if (value <= base[index]) {
            if (value < base[index]) {
                index = ~index; // not found
            }
            return index;
        }
    }
    return ~count;    // append at the end
}

SkCharToGlyphCache::SkCharToGlyphCache() {}

SkCharToGlyphCache::~SkCharToGlyphCache() {}

int SkCharToGlyphCache::findGlyphIndex(SkUnichar unichar) const {
    int index;
    if (SkTFitsIn<uint16_t>(unichar)) {
        int count = f1616.count() >> 1;
        index = find_index(f1616.begin(), count, SkToU16(unichar));
        if (index >= 0) {
            return f1616[count + index];
        }
    } else {
        int count = fKey32.count();
        index = find_index(fKey32.begin(), count, unichar);
        if (index >= 0) {
            return fValue16[index];
        }
    }
    SkASSERT(index < 0);
    return index;
}

void SkCharToGlyphCache::insertCharAndGlyph(int index, SkUnichar unichar, SkGlyphID glyph) {
    if (SkTFitsIn<uint16_t>(unichar)) {
        // count is the logical count, since our array is really two arrays back-to-back
        size_t count = f1616.size() >> 1;
        SkASSERT((unsigned)index <= count);

        f1616.setCount(f1616.size() + 2); // make room for key and value
        uint16_t* base = f1616.begin();

        // now slide twice, to make room for the new key and value
        uint16_t* src = base + count + index;
        size_t    amt = count - index;
        sk_careful_memmove(src + 2, src, amt * sizeof(uint16_t));

        src = base + index;
        amt = count;
        sk_careful_memmove(src + 1, src, amt * sizeof(uint16_t));

        // now store the new values
        base[index] = SkToU16(unichar);
        base[count + 1 + index] = glyph;
    } else {
        SkASSERT(fKey32.size() == fValue16.size());
        SkASSERT((unsigned)index <= fKey32.size());

        *fKey32.insert(index) = unichar;
        *fValue16.insert(index) = glyph;
    }
    this->validate();
}

void SkCharToGlyphCache::validate() const {
#ifdef SK_DEBUG
    SkASSERT((f1616.count() & 1) == 0);
    for (int i = 1; i < f1616.count() >> 1; ++i) {
        SkASSERT(f1616[i - 1] < f1616[i]);
    }

    SkASSERT(fKey32.size() == fValue16.size());
    for (int i = 1; i < fKey32.count(); ++i) {
        SkASSERT(fKey32[i - 1] < fKey32[i]);
    }
#endif
}