11cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 20910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/* 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Copyright 2006 The Android Open Source Project 40910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Use of this source code is governed by a BSD-style license that can be 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * found in the LICENSE file. 70910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project */ 80910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 91cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifndef SkTSearch_DEFINED 110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define SkTSearch_DEFINED 120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "SkTypes.h" 140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projecttemplate <typename T> 160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkTSearch(const T* base, int count, const T& target, size_t elemSize) 170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project{ 180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(count >= 0); 190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (count <= 0) 200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return ~0; 210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(base != NULL); // base may be NULL if count is zero 230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int lo = 0; 250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int hi = count - 1; 260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (lo < hi) 280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int mid = (hi + lo) >> 1; 300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T* elem = (const T*)((const char*)base + mid * elemSize); 310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (*elem < target) 330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project lo = mid + 1; 340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project else 350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi = mid; 360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T* elem = (const T*)((const char*)base + hi * elemSize); 390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (*elem != target) 400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (*elem < target) 420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi += 1; 430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi = ~hi; 440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return hi; 460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projecttemplate <typename T> 490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkTSearch(const T* base, int count, const T& target, size_t elemSize, 500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int (*compare)(const T&, const T&)) 510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project{ 520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(count >= 0); 530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (count <= 0) { 540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return ~0; 550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(base != NULL); // base may be NULL if count is zero 580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int lo = 0; 600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int hi = count - 1; 610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (lo < hi) { 630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int mid = (hi + lo) >> 1; 640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T* elem = (const T*)((const char*)base + mid * elemSize); 650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if ((*compare)(*elem, target) < 0) 670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project lo = mid + 1; 680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project else 690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi = mid; 700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T* elem = (const T*)((const char*)base + hi * elemSize); 730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int pred = (*compare)(*elem, target); 740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (pred != 0) { 750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (pred < 0) 760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi += 1; 770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi = ~hi; 780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return hi; 800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projecttemplate <typename T> 830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkTSearch(const T** base, int count, const T* target, size_t elemSize, 840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int (*compare)(const T*, const T*)) 850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project{ 860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(count >= 0); 870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (count <= 0) 880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return ~0; 890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(base != NULL); // base may be NULL if count is zero 910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int lo = 0; 930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int hi = count - 1; 940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (lo < hi) 960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int mid = (hi + lo) >> 1; 980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T* elem = *(const T**)((const char*)base + mid * elemSize); 990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if ((*compare)(elem, target) < 0) 1010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project lo = mid + 1; 1020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project else 1030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi = mid; 1040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T* elem = *(const T**)((const char*)base + hi * elemSize); 1070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int pred = (*compare)(elem, target); 1080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (pred != 0) 1090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 1100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (pred < 0) 1110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi += 1; 1120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project hi = ~hi; 1130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return hi; 1150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkStrSearch(const char*const* base, int count, const char target[], 1180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t target_len, size_t elemSize); 1190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkStrSearch(const char*const* base, int count, const char target[], 1200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t elemSize); 1210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that 1230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project base points to a table of lower-case strings. 1240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/ 1250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkStrLCSearch(const char*const* base, int count, const char target[], 1260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t target_len, size_t elemSize); 1270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectint SkStrLCSearch(const char*const* base, int count, const char target[], 1280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t elemSize); 1290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/** Helper class to convert a string to lower-case, but only modifying the ascii 1310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project characters. This makes the routine very fast and never changes the string 1320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project length, but it is not suitable for linguistic purposes. Normally this is 1330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project used for buiding and searching string tables. 1340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/ 1350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectclass SkAutoAsciiToLC { 1360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectpublic: 1370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); 1380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project ~SkAutoAsciiToLC(); 1390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const char* lc() const { return fLC; } 1410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t length() const { return fLength; } 1420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectprivate: 1440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char* fLC; // points to either the heap or fStorage 1450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project size_t fLength; 1460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project enum { 1470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project STORAGE = 64 1480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project }; 1490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project char fStorage[STORAGE+1]; 1500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}; 1510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectextern "C" { 1530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project typedef int (*SkQSortCompareProc)(const void*, const void*); 1540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc); 1550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 1580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 159