1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrTBSearch.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,44 @@
1.4 +/*
1.5 + * Copyright 2010 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef GrTBSearch_DEFINED
1.12 +#define GrTBSearch_DEFINED
1.13 +
1.14 +#include "SkTypes.h"
1.15 +
1.16 +template <typename ELEM, typename KEY>
1.17 +int GrTBSearch(const ELEM array[], int count, KEY target) {
1.18 + SkASSERT(count >= 0);
1.19 + if (0 == count) {
1.20 + // we should insert it at 0
1.21 + return ~0;
1.22 + }
1.23 +
1.24 + int high = count - 1;
1.25 + int low = 0;
1.26 + while (high > low) {
1.27 + int index = (low + high) >> 1;
1.28 + if (LT(array[index], target)) {
1.29 + low = index + 1;
1.30 + } else {
1.31 + high = index;
1.32 + }
1.33 + }
1.34 +
1.35 + // check if we found it
1.36 + if (EQ(array[high], target)) {
1.37 + return high;
1.38 + }
1.39 +
1.40 + // now return the ~ of where we should insert it
1.41 + if (LT(array[high], target)) {
1.42 + high += 1;
1.43 + }
1.44 + return ~high;
1.45 +}
1.46 +
1.47 +#endif
