SkTSearch.cpp 2.8 KB

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