SkTSearch.cpp revision 1cab2921ab279367f8206cdadc9259d12e603548
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 13static 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 19int 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 != NULL); 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 55int 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 61int 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 71int 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 79SkAutoAsciiToLC::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 109SkAutoAsciiToLC::~SkAutoAsciiToLC() 110{ 111 if (fLC != fStorage) { 112 sk_free(fLC); 113 } 114} 115 116////////////////////////////////////////////////////////////////////////////// 117 118#define SK_QSortTempSize 16 119 120static inline void sk_qsort_swap(char a[], char b[], size_t elemSize) 121{ 122 char tmp[SK_QSortTempSize]; 123 124 while (elemSize > 0) 125 { 126 size_t size = elemSize; 127 if (size > SK_QSortTempSize) 128 size = SK_QSortTempSize; 129 elemSize -= size; 130 131 memcpy(tmp, a, size); 132 memcpy(a, b, size); 133 memcpy(b, tmp, size); 134 a += size; 135 b += size; 136 } 137} 138 139static void SkQSort_Partition(char* first, char* last, size_t elemSize, SkQSortCompareProc compare) 140{ 141 char* left = first; 142 char* rite = last; 143 char* pivot = left; 144 145 while (left <= rite) 146 { 147 while (left < last && compare(left, pivot) < 0) 148 left += elemSize; 149 while (first < rite && compare(rite, pivot) > 0) 150 rite -= elemSize; 151 if (left <= rite) 152 { 153 if (left < rite) 154 { 155 SkASSERT(compare(left, rite) >= 0); 156 sk_qsort_swap(left, rite, elemSize); 157 } 158 left += elemSize; 159 rite -= elemSize; 160 } 161 } 162 if (first < rite) 163 SkQSort_Partition(first, rite, elemSize, compare); 164 if (left < last) 165 SkQSort_Partition(left, last, elemSize, compare); 166} 167 168void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc compare) 169{ 170 SkASSERT(base); 171 SkASSERT(compare); 172 SkASSERT(elemSize > 0); 173 174 if (count <= 1) 175 return; 176 177 SkQSort_Partition((char*)base, (char*)base + (count - 1) * elemSize, elemSize, compare); 178} 179 180