| // Copyright 2018 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "crazy_linker_pointer_set.h" |
| |
| namespace crazy { |
| |
| static SearchResult BinarySearch(const Vector<const void*>& items, |
| const void* key) { |
| auto key_val = reinterpret_cast<uintptr_t>(key); |
| size_t min = 0, max = items.GetCount(); |
| while (min < max) { |
| size_t mid = min + ((max - min) >> 1); |
| auto mid_val = reinterpret_cast<uintptr_t>(items[mid]); |
| if (mid_val == key_val) { |
| return {true, mid}; |
| } |
| if (mid_val < key_val) |
| min = mid + 1; |
| else |
| max = mid; |
| } |
| return {false, min}; |
| } |
| |
| bool PointerSet::Add(const void* item) { |
| SearchResult ret = BinarySearch(items_, item); |
| if (ret.found) |
| return true; |
| |
| items_.InsertAt(ret.pos, item); |
| return false; |
| } |
| |
| bool PointerSet::Remove(const void* item) { |
| SearchResult ret = BinarySearch(items_, item); |
| if (!ret.found) |
| return false; |
| |
| items_.RemoveAt(ret.pos); |
| return true; |
| } |
| |
| bool PointerSet::Has(const void* item) const { |
| SearchResult ret = BinarySearch(items_, item); |
| return ret.found; |
| } |
| |
| } // namespace crazy |