1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "verifier/dex_gc_map.h"
18
19#include "base/logging.h"
20
21namespace art {
22namespace verifier {
23
24const uint8_t* DexPcToReferenceMap::FindBitMap(uint16_t dex_pc, bool error_if_not_present) const {
25  size_t num_entries = NumEntries();
26  // Do linear or binary search?
27  static const size_t kSearchThreshold = 8;
28  if (num_entries < kSearchThreshold) {
29    for (size_t i = 0; i < num_entries; i++)  {
30      if (GetDexPc(i) == dex_pc) {
31        return GetBitMap(i);
32      }
33    }
34  } else {
35    int lo = 0;
36    int hi = num_entries -1;
37    while (hi >= lo) {
38      int mid = (hi + lo) / 2;
39      int mid_pc = GetDexPc(mid);
40      if (dex_pc > mid_pc) {
41        lo = mid + 1;
42      } else if (dex_pc < mid_pc) {
43        hi = mid - 1;
44      } else {
45        return GetBitMap(mid);
46      }
47    }
48  }
49  if (error_if_not_present) {
50    LOG(ERROR) << "Didn't find reference bit map for dex_pc " << dex_pc;
51  }
52  return nullptr;
53}
54
55}  // namespace verifier
56}  // namespace art
57