diff options
author | Jim Laskey <jlaskey@mac.com> | 2005-08-25 13:32:25 +0000 |
---|---|---|
committer | Jim Laskey <jlaskey@mac.com> | 2005-08-25 13:32:25 +0000 |
commit | ab6c0a923f47944d78f34a1c494e4cee2f711b2d (patch) | |
tree | 979988c365731bcaaeb0716b23eef134a7a81d46 /include/llvm/Support | |
parent | 4e27d3a10ca1094703a3fc979c5417ee4e861d1e (diff) | |
download | external_llvm-ab6c0a923f47944d78f34a1c494e4cee2f711b2d.zip external_llvm-ab6c0a923f47944d78f34a1c494e4cee2f711b2d.tar.gz external_llvm-ab6c0a923f47944d78f34a1c494e4cee2f711b2d.tar.bz2 |
Added support for generic linear/binary search.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23044 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/Support')
-rw-r--r-- | include/llvm/Support/Search.h | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/include/llvm/Support/Search.h b/include/llvm/Support/Search.h new file mode 100644 index 0000000..3af723e --- /dev/null +++ b/include/llvm/Support/Search.h @@ -0,0 +1,78 @@ +//===- llvm/Support/Search.h - Support for searching algorithms -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// These templates impliment various generic search algorithms. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_SEARCH_H +#define LLVM_SUPPORT_SEARCH_H + +namespace llvm { + // SearchString - generalized string compare method container. Used for + // search templates. + struct SearchString { + static inline int Compare(const char *A, const char *B) { + return strcmp(A, B); + } + }; + + // LinearSearch - search an array of items for a match using linear search + // algorithm. Return find index or -1 if not found. + // ItemType - type of elements in array. + // CompareClass - container for compare method in form of + // static int Compare(ItemType A, ItemType B) + // returns < 0 for A < B + // > 0 for A > B + // == 0 for A == B + // Match - item to match in array. + // Array - an array of items to be searched. + // Size - size of array in bytes. + // + // Eg. LinearSearch<const char *, SearchString>("key", List, sizeof(List)); + // + template<typename ItemType, class CompareClass> + inline int LinearSearch(ItemType Match, ItemType Array[], size_t Size) { + unsigned N = Size / sizeof(ItemType); + for (unsigned Index = 0; Index < N; Index++) { + if (!CompareClass::Compare(Match, Array[Index])) return Index; + } + return -1; + } + + // BinarySearch - search an array of items for a match using binary search + // algorithm. Return find index or -1 if not found. + // ItemType - type of elements in array. + // CompareClass - container for compare method in form of + // static int Compare(ItemType A, ItemType B) + // returns < 0 for A < B + // > 0 for A > B + // == 0 for A == B + // Match - item to match in array. + // Array - a sorted array of items to be searched. + // Size - size of array in bytes. + // + // Eg. BinarySearch<const char *, SearchString>("key", List, sizeof(List)); + // + template<typename ItemType, class CompareClass> + inline int BinarySearch(ItemType Match, ItemType Array[], size_t Size) { + int Lo = 0, Hi = Size / sizeof(ItemType); + while (Lo <= Hi) { + unsigned Mid = (Lo + Hi) >> 1; + int Result = CompareClass::Compare(Match, Array[Mid]); + if (Result < 0) Hi = Mid - 1; + else if (Result > 0) Lo = Mid + 1; + else return Mid; + } + return -1; + } +} + +#endif + |