1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2010 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com */ 7ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 8ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#ifndef GrTBSearch_DEFINED 9ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#define GrTBSearch_DEFINED 10ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 11bbff20855ff28d377e9ca2e76bd35810ea46994dtfarina@chromium.org#include "SkTypes.h" 12bbff20855ff28d377e9ca2e76bd35810ea46994dtfarina@chromium.org 13ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.comtemplate <typename ELEM, typename KEY> 14ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.comint GrTBSearch(const ELEM array[], int count, KEY target) { 15f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(count >= 0); 16ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (0 == count) { 17ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // we should insert it at 0 18ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return ~0; 19ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 20d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 21ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com int high = count - 1; 22ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com int low = 0; 23ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com while (high > low) { 24ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com int index = (low + high) >> 1; 25ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (LT(array[index], target)) { 26ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com low = index + 1; 27ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 28ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com high = index; 29ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 30ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 31d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 32ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // check if we found it 33ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (EQ(array[high], target)) { 34ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return high; 35ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 36d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 37ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // now return the ~ of where we should insert it 38ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (LT(array[high], target)) { 39ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com high += 1; 40ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 41ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return ~high; 42ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com} 43ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 44ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#endif 45