• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 
2 /*
3  * Copyright 2006 The Android Open Source Project
4  *
5  * Use of this source code is governed by a BSD-style license that can be
6  * found in the LICENSE file.
7  */
8 
9 
10 #include "SkTSearch.h"
11 #include <ctype.h>
12 
index_into_base(const char * const * base,int index,size_t elemSize)13 static inline const char* index_into_base(const char*const* base, int index,
14                                           size_t elemSize)
15 {
16     return *(const char*const*)((const char*)base + index * elemSize);
17 }
18 
SkStrSearch(const char * const * base,int count,const char target[],size_t target_len,size_t elemSize)19 int SkStrSearch(const char*const* base, int count, const char target[],
20                 size_t target_len, size_t elemSize)
21 {
22     if (count <= 0)
23         return ~0;
24 
25     SkASSERT(base != nullptr);
26 
27     int lo = 0;
28     int hi = count - 1;
29 
30     while (lo < hi)
31     {
32         int mid = (hi + lo) >> 1;
33         const char* elem = index_into_base(base, mid, elemSize);
34 
35         int cmp = strncmp(elem, target, target_len);
36         if (cmp < 0)
37             lo = mid + 1;
38         else if (cmp > 0 || strlen(elem) > target_len)
39             hi = mid;
40         else
41             return mid;
42     }
43 
44     const char* elem = index_into_base(base, hi, elemSize);
45     int cmp = strncmp(elem, target, target_len);
46     if (cmp || strlen(elem) > target_len)
47     {
48         if (cmp < 0)
49             hi += 1;
50         hi = ~hi;
51     }
52     return hi;
53 }
54 
SkStrSearch(const char * const * base,int count,const char target[],size_t elemSize)55 int SkStrSearch(const char*const* base, int count, const char target[],
56                 size_t elemSize)
57 {
58     return SkStrSearch(base, count, target, strlen(target), elemSize);
59 }
60 
SkStrLCSearch(const char * const * base,int count,const char target[],size_t len,size_t elemSize)61 int SkStrLCSearch(const char*const* base, int count, const char target[],
62                   size_t len, size_t elemSize)
63 {
64     SkASSERT(target);
65 
66     SkAutoAsciiToLC tolc(target, len);
67 
68     return SkStrSearch(base, count, tolc.lc(), len, elemSize);
69 }
70 
SkStrLCSearch(const char * const * base,int count,const char target[],size_t elemSize)71 int SkStrLCSearch(const char*const* base, int count, const char target[],
72                   size_t elemSize)
73 {
74     return SkStrLCSearch(base, count, target, strlen(target), elemSize);
75 }
76 
77 //////////////////////////////////////////////////////////////////////////////
78 
SkAutoAsciiToLC(const char str[],size_t len)79 SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
80 {
81     // see if we need to compute the length
82     if ((long)len < 0) {
83         len = strlen(str);
84     }
85     fLength = len;
86 
87     // assign lc to our preallocated storage if len is small enough, or allocate
88     // it on the heap
89     char*   lc;
90     if (len <= STORAGE) {
91         lc = fStorage;
92     } else {
93         lc = (char*)sk_malloc_throw(len + 1);
94     }
95     fLC = lc;
96 
97     // convert any asii to lower-case. we let non-ascii (utf8) chars pass
98     // through unchanged
99     for (int i = (int)(len - 1); i >= 0; --i) {
100         int c = str[i];
101         if ((c & 0x80) == 0) {   // is just ascii
102             c = tolower(c);
103         }
104         lc[i] = c;
105     }
106     lc[len] = 0;
107 }
108 
~SkAutoAsciiToLC()109 SkAutoAsciiToLC::~SkAutoAsciiToLC()
110 {
111     if (fLC != fStorage) {
112         sk_free(fLC);
113     }
114 }
115