move SkTDict and SkTSearch into private

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1558923002

TBR=

Review URL: https://codereview.chromium.org/1558923002

2 files changed, 292 insertions, 0 deletions

diff --git a/include/private/SkTDict.h b/include/private/SkTDict.h
new file mode 100644
index 0000000000..106cace2f2
--- /dev/null
+++ b/include/private/SkTDict.h
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+
+#ifndef SkTDict_DEFINED
+#define SkTDict_DEFINED
+
+#include "SkChunkAlloc.h"
+#include "SkTSearch.h"
+#include "SkTDArray.h"
+
+template <typename T> class SkTDict : SkNoncopyable {
+public:
+    SkTDict(size_t minStringAlloc) : fStrings(minStringAlloc) {}
+
+    void reset() {
+        fArray.reset();
+        fStrings.reset();
+    }
+
+    int count() const { return fArray.count(); }
+
+    bool set(const char name[], const T& value) {
+        return set(name, strlen(name), value);
+    }
+
+    bool set(const char name[], size_t len, const T& value) {
+        SkASSERT(name);
+
+        int index = this->find_index(name, len);
+
+        if (index >= 0) {
+            fArray[index].fValue = value;
+            return false;
+        } else {
+            Pair*   pair = fArray.insert(~index);
+            char*   copy = (char*)fStrings.alloc(len + 1, SkChunkAlloc::kThrow_AllocFailType);
+            memcpy(copy, name, len);
+            copy[len] = '\0';
+            pair->fName = copy;
+            pair->fValue = value;
+            return true;
+        }
+    }
+
+    bool find(const char name[]) const {
+        return this->find_index(name) >= 0;
+    }
+
+    bool find(const char name[], size_t len) const {
+        return this->find_index(name, len) >= 0;
+    }
+
+    bool find(const char name[], T* value) const {
+        return find(name, strlen(name), value);
+    }
+
+    bool find(const char name[], size_t len, T* value) const {
+        int index = this->find_index(name, len);
+
+        if (index >= 0) {
+            if (value) {
+                *value = fArray[index].fValue;
+            }
+            return true;
+        }
+        return false;
+    }
+
+    bool findKey(T& value, const char** name) const {
+        const Pair* end = fArray.end();
+        for (const Pair* pair = fArray.begin(); pair < end; pair++) {
+            if (pair->fValue != value) {
+                continue;
+            }
+            *name = pair->fName;
+            return true;
+        }
+        return false;
+    }
+
+public:
+    struct Pair {
+        const char* fName;
+        T           fValue;
+
+        friend int operator<(const Pair& a, const Pair& b) {
+            return strcmp(a.fName, b.fName);
+        }
+
+        friend int operator!=(const Pair& a, const Pair& b) {
+            return strcmp(a.fName, b.fName);
+        }
+    };
+    friend class Iter;
+
+public:
+    class Iter {
+    public:
+        Iter(const SkTDict<T>& dict) {
+            fIter = dict.fArray.begin();
+            fStop = dict.fArray.end();
+        }
+
+        const char* next(T* value) {
+            const char* name = NULL;
+            if (fIter < fStop) {
+                name = fIter->fName;
+                if (value) {
+                    *value = fIter->fValue;
+                }
+                fIter += 1;
+            }
+            return name;
+        }
+    private:
+        const Pair*   fIter;
+        const Pair*   fStop;
+    };
+
+private:
+    SkTDArray<Pair> fArray;
+    SkChunkAlloc    fStrings;
+
+    int find_index(const char name[]) const {
+        return find_index(name, strlen(name));
+    }
+
+    int find_index(const char name[], size_t len) const {
+        SkASSERT(name);
+
+        int count = fArray.count();
+        int index = ~0;
+
+        if (count) {
+            index = SkStrSearch(&fArray.begin()->fName, count, name, len, sizeof(Pair));
+        }
+        return index;
+    }
+    friend class Iter;
+};
+
+#endif
diff --git a/include/private/SkTSearch.h b/include/private/SkTSearch.h
new file mode 100644
index 0000000000..549bcfd7c8
--- /dev/null
+++ b/include/private/SkTSearch.h
@@ -0,0 +1,146 @@
+
+/*
+ * 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.
+ */
+
+
+#ifndef SkTSearch_DEFINED
+#define SkTSearch_DEFINED
+
+#include "SkTypes.h"
+
+/**
+ *  All of the SkTSearch variants want to return the index (0...N-1) of the
+ *  found element, or the bit-not of where to insert the element.
+ *
+ *  At a simple level, if the return value is negative, it was not found.
+ *
+ *  For clients that want to insert the new element if it was not found, use
+ *  the following logic:
+ *
+ *  int index = SkTSearch(...);
+ *  if (index >= 0) {
+ *      // found at index
+ *  } else {
+ *      index = ~index; // now we are positive
+ *      // insert at index
+ *  }
+ */
+
+
+// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
+// used to perform comparisons. It has two function operators:
+//      bool operator() (const T& t, const K& k)
+//      bool operator() (const K& t, const T& k)
+template <typename T, typename K, typename LESS>
+int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
+{
+    SkASSERT(count >= 0);
+    if (count <= 0) {
+        return ~0;
+    }
+
+    SkASSERT(base != NULL); // base may be NULL if count is zero
+
+    int lo = 0;
+    int hi = count - 1;
+
+    while (lo < hi) {
+        int mid = lo + ((hi - lo) >> 1);
+        const T* elem = (const T*)((const char*)base + mid * elemSize);
+
+        if (less(*elem, key))
+            lo = mid + 1;
+        else
+            hi = mid;
+    }
+
+    const T* elem = (const T*)((const char*)base + hi * elemSize);
+    if (less(*elem, key)) {
+        hi += 1;
+        hi = ~hi;
+    } else if (less(key, *elem)) {
+        hi = ~hi;
+    }
+    return hi;
+}
+
+// Adapts a less-than function to a functor.
+template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor {
+    bool operator()(const T& a, const T& b) { return LESS(a, b); }
+};
+
+// Specialization for case when T==K and the caller wants to use a function rather than functor.
+template <typename T, bool (LESS)(const T&, const T&)>
+int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
+    static SkTLessFunctionToFunctorAdaptor<T, LESS> functor;
+    return SkTSearch(base, count, target, elemSize, functor);
+}
+
+// Adapts operator < to a functor.
+template <typename T> struct SkTLessFunctor {
+    bool operator()(const T& a, const T& b) { return a < b; }
+};
+
+// Specialization for T==K, compare using op <.
+template <typename T>
+int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
+    static SkTLessFunctor<T> functor;
+    return SkTSearch(base, count, target, elemSize, functor);
+}
+
+// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
+template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor {
+    bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
+};
+
+// Specialization for case where domain is an array of T* and the key value is a T*, and you want
+// to compare the T objects, not the pointers.
+template <typename T, bool (LESS)(const T&, const T&)>
+int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
+    static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor;
+    return SkTSearch(base, count, target, elemSize, functor);
+}
+
+int SkStrSearch(const char*const* base, int count, const char target[],
+                size_t target_len, size_t elemSize);
+int SkStrSearch(const char*const* base, int count, const char target[],
+                size_t elemSize);
+
+/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
+    base points to a table of lower-case strings.
+*/
+int SkStrLCSearch(const char*const* base, int count, const char target[],
+                  size_t target_len, size_t elemSize);
+int SkStrLCSearch(const char*const* base, int count, const char target[],
+                  size_t elemSize);
+
+/** Helper class to convert a string to lower-case, but only modifying the ascii
+    characters. This makes the routine very fast and never changes the string
+    length, but it is not suitable for linguistic purposes. Normally this is
+    used for buiding and searching string tables.
+*/
+class SkAutoAsciiToLC {
+public:
+    SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
+    ~SkAutoAsciiToLC();
+
+    const char* lc() const { return fLC; }
+    size_t      length() const { return fLength; }
+
+private:
+    char*   fLC;    // points to either the heap or fStorage
+    size_t  fLength;
+    enum {
+        STORAGE = 64
+    };
+    char    fStorage[STORAGE+1];
+};
+
+// Helper when calling qsort with a compare proc that has typed its arguments
+#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
+
+#endif