gfx/skia/skia/src/core/SkTSearch.cpp
author Wes Kocher <wkocher@mozilla.com>
Wed, 10 May 2017 10:01:18 -0700
changeset 407965 ce2218406119c36a551e3faea4e192186ee46cc5
parent 407937 af6f19870b2a00759ac1d83dedc3db57213abfee
child 408167 0ded74baeaf23d7985401fe9bbabdb3d9385ac22
permissions -rw-r--r--
Backed out 9 changesets (bug 1340627) for graphical glitches a=backout Backed out changeset 0b1371055c7f (bug 1340627) Backed out changeset f152be1fadb7 (bug 1340627) Backed out changeset c691e2ab6a0c (bug 1340627) Backed out changeset 3cb4bceb8d79 (bug 1340627) Backed out changeset 026aadd76d06 (bug 1340627) Backed out changeset fdbd5d281287 (bug 1340627) Backed out changeset 75fb0d9858a9 (bug 1340627) Backed out changeset 0d4ec7d38a00 (bug 1340627) Backed out changeset af6f19870b2a (bug 1340627) MozReview-Commit-ID: 9dHr7xMZezY

/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */


#include "SkTSearch.h"
#include <ctype.h>

static inline const char* index_into_base(const char*const* base, int index,
                                          size_t elemSize)
{
    return *(const char*const*)((const char*)base + index * elemSize);
}

int SkStrSearch(const char*const* base, int count, const char target[],
                size_t target_len, size_t elemSize)
{
    if (count <= 0)
        return ~0;

    SkASSERT(base != nullptr);

    int lo = 0;
    int hi = count - 1;

    while (lo < hi)
    {
        int mid = (hi + lo) >> 1;
        const char* elem = index_into_base(base, mid, elemSize);

        int cmp = strncmp(elem, target, target_len);
        if (cmp < 0)
            lo = mid + 1;
        else if (cmp > 0 || strlen(elem) > target_len)
            hi = mid;
        else
            return mid;
    }

    const char* elem = index_into_base(base, hi, elemSize);
    int cmp = strncmp(elem, target, target_len);
    if (cmp || strlen(elem) > target_len)
    {
        if (cmp < 0)
            hi += 1;
        hi = ~hi;
    }
    return hi;
}

int SkStrSearch(const char*const* base, int count, const char target[],
                size_t elemSize)
{
    return SkStrSearch(base, count, target, strlen(target), elemSize);
}

int SkStrLCSearch(const char*const* base, int count, const char target[],
                  size_t len, size_t elemSize)
{
    SkASSERT(target);

    SkAutoAsciiToLC tolc(target, len);

    return SkStrSearch(base, count, tolc.lc(), len, elemSize);
}

int SkStrLCSearch(const char*const* base, int count, const char target[],
                  size_t elemSize)
{
    return SkStrLCSearch(base, count, target, strlen(target), elemSize);
}

//////////////////////////////////////////////////////////////////////////////

SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
{
    // see if we need to compute the length
    if ((long)len < 0) {
        len = strlen(str);
    }
    fLength = len;

    // assign lc to our preallocated storage if len is small enough, or allocate
    // it on the heap
    char*   lc;
    if (len <= STORAGE) {
        lc = fStorage;
    } else {
        lc = (char*)sk_malloc_throw(len + 1);
    }
    fLC = lc;

    // convert any asii to lower-case. we let non-ascii (utf8) chars pass
    // through unchanged
    for (int i = (int)(len - 1); i >= 0; --i) {
        int c = str[i];
        if ((c & 0x80) == 0) {   // is just ascii
            c = tolower(c);
        }
        lc[i] = c;
    }
    lc[len] = 0;
}

SkAutoAsciiToLC::~SkAutoAsciiToLC()
{
    if (fLC != fStorage) {
        sk_free(fLC);
    }
}