diff options
author | 2025-03-11 10:39:48 -0700 | |
---|---|---|
committer | 2025-03-11 10:39:48 -0700 | |
commit | fdbf19f4c09baffc00d00cbf3cbcdec8264c751c (patch) | |
tree | 6695332e11c511235e79a7cfab213c8bd803b01b | |
parent | 659908adc6eceed81b3e5c4f98ce94c5dcbc97ea (diff) | |
parent | 0c3c5d2ad8ea0d81d4b2de3b65dff797571ecea2 (diff) |
Merge "system/common: Remove unused headers lru.h, id_generator.h" into main
-rw-r--r-- | system/common/Android.bp | 2 | ||||
-rw-r--r-- | system/common/id_generator.h | 48 | ||||
-rw-r--r-- | system/common/id_generator_unittest.cc | 37 | ||||
-rw-r--r-- | system/common/lru.h | 187 | ||||
-rw-r--r-- | system/common/lru_unittest.cc | 250 |
5 files changed, 0 insertions, 524 deletions
diff --git a/system/common/Android.bp b/system/common/Android.bp index 98e99e6d7b..c192613dbc 100644 --- a/system/common/Android.bp +++ b/system/common/Android.bp @@ -77,9 +77,7 @@ cc_test { srcs: [ "address_obfuscator_unittest.cc", "base_bind_unittest.cc", - "id_generator_unittest.cc", "leaky_bonded_queue_unittest.cc", - "lru_unittest.cc", "message_loop_thread_unittest.cc", "repeating_timer_unittest.cc", "state_machine_unittest.cc", diff --git a/system/common/id_generator.h b/system/common/id_generator.h deleted file mode 100644 index 7c6425aeef..0000000000 --- a/system/common/id_generator.h +++ /dev/null @@ -1,48 +0,0 @@ -/* - * Copyright 2019 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#pragma once - -#include <array> - -/* Helper class generating N unique ids, from 0 to N-1 */ -template <std::size_t N> -class IdGenerator { -public: - static int ALL_USED; - - IdGenerator() : in_use_{} {} - - /* Returns next free id, or ALL_USED if no ids left */ - int GetNext() { - for (std::size_t i = 0; i < N; i++) { - if (!in_use_[i]) { - in_use_[i] = true; - return i; - } - } - return ALL_USED; - } - - /* Release given ID */ - void Release(int id) { in_use_[id] = false; } - -private: - std::array<bool, N> in_use_; -}; - -template <std::size_t N> -int IdGenerator<N>::ALL_USED = -1; diff --git a/system/common/id_generator_unittest.cc b/system/common/id_generator_unittest.cc deleted file mode 100644 index 7b090cf365..0000000000 --- a/system/common/id_generator_unittest.cc +++ /dev/null @@ -1,37 +0,0 @@ -/* - * Copyright 2019 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "common/id_generator.h" - -#include <gtest/gtest.h> - -TEST(IdGeneratorTest, sanity_test) { - IdGenerator<5> generator; - ASSERT_EQ(0, generator.GetNext()); - ASSERT_EQ(1, generator.GetNext()); - ASSERT_EQ(2, generator.GetNext()); - ASSERT_EQ(3, generator.GetNext()); - ASSERT_EQ(4, generator.GetNext()); - ASSERT_EQ(generator.ALL_USED, generator.GetNext()); - - generator.Release(3); - ASSERT_EQ(3, generator.GetNext()); - - generator.Release(0); - generator.Release(2); - ASSERT_EQ(0, generator.GetNext()); - ASSERT_EQ(2, generator.GetNext()); -} diff --git a/system/common/lru.h b/system/common/lru.h deleted file mode 100644 index ca0a5a1c35..0000000000 --- a/system/common/lru.h +++ /dev/null @@ -1,187 +0,0 @@ -/****************************************************************************** - * - * Copyright 2020 Google, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - ******************************************************************************/ - -#pragma once - -#include <bluetooth/log.h> - -#include <functional> -#include <iterator> -#include <list> -#include <mutex> -#include <optional> -#include <thread> -#include <unordered_map> - -namespace bluetooth { - -namespace common { - -template <typename K, typename V> -class LegacyLruCache { -public: - using Node = std::pair<K, V>; - /** - * Constructor of the cache - * - * @param capacity maximum size of the cache - * @param log_tag, keyword to put at the head of log. - */ - LegacyLruCache(const size_t& capacity, const std::string& log_tag) : capacity_(capacity) { - if (capacity_ == 0) { - // don't allow invalid capacity - log::fatal("{} unable to have 0 LRU Cache capacity", log_tag); - } - } - - // delete copy constructor - LegacyLruCache(LegacyLruCache const&) = delete; - LegacyLruCache& operator=(LegacyLruCache const&) = delete; - - ~LegacyLruCache() { Clear(); } - - /** - * Clear the cache - */ - void Clear() { - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - lru_map_.clear(); - node_list_.clear(); - } - - /** - * Same as Get, but return an iterator to the accessed element - * - * Modifying the returned iterator does not warm up the cache - * - * @param key - * @return pointer to the underlying value to allow in-place modification - * nullptr when not found, will be invalidated when the key is evicted - */ - V* Find(const K& key) { - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - auto map_iterator = lru_map_.find(key); - if (map_iterator == lru_map_.end()) { - return nullptr; - } - node_list_.splice(node_list_.begin(), node_list_, map_iterator->second); - return &(map_iterator->second->second); - } - - /** - * Get the value of a key, and move the key to the head of cache, if there is - * one - * - * @param key - * @param value, output parameter of value of the key - * @return true if the cache has the key - */ - bool Get(const K& key, V* value) { - log::assert_that(value != nullptr, "assert failed: value != nullptr"); - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - auto value_ptr = Find(key); - if (value_ptr == nullptr) { - return false; - } - *value = *value_ptr; - return true; - } - - /** - * Check if the cache has the input key, move the key to the head - * if there is one - * - * @param key - * @return true if the cache has the key - */ - bool HasKey(const K& key) { - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - return Find(key) != nullptr; - } - - /** - * Put a key-value pair to the head of cache - * - * @param key - * @param value - * @return evicted node if tail value is popped, std::nullopt if no value - * is popped. std::optional can be treated as a boolean as well - */ - std::optional<Node> Put(const K& key, V value) { - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - auto value_ptr = Find(key); - if (value_ptr != nullptr) { - // hasKey() calls get(), therefore already move the node to the head - *value_ptr = std::move(value); - return std::nullopt; - } - - // remove tail - std::optional<Node> ret = std::nullopt; - if (lru_map_.size() == capacity_) { - lru_map_.erase(node_list_.back().first); - ret = std::move(node_list_.back()); - node_list_.pop_back(); - } - // insert to dummy next; - node_list_.emplace_front(key, std::move(value)); - lru_map_.emplace(key, node_list_.begin()); - return ret; - } - - /** - * Delete a key from cache - * - * @param key - * @return true if deleted successfully - */ - bool Remove(const K& key) { - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - auto map_iterator = lru_map_.find(key); - if (map_iterator == lru_map_.end()) { - return false; - } - - // remove from the list - node_list_.erase(map_iterator->second); - - // delete key from map - lru_map_.erase(map_iterator); - - return true; - } - - /** - * Return size of the cache - * - * @return size of the cache - */ - int Size() const { - std::lock_guard<std::recursive_mutex> lock(lru_mutex_); - return lru_map_.size(); - } - -private: - std::list<Node> node_list_; - size_t capacity_; - std::unordered_map<K, typename std::list<Node>::iterator> lru_map_; - mutable std::recursive_mutex lru_mutex_; -}; - -} // namespace common -} // namespace bluetooth diff --git a/system/common/lru_unittest.cc b/system/common/lru_unittest.cc deleted file mode 100644 index 7b41143ec5..0000000000 --- a/system/common/lru_unittest.cc +++ /dev/null @@ -1,250 +0,0 @@ -/****************************************************************************** - * - * Copyright 2020 Google, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - ******************************************************************************/ - -#include "common/lru.h" - -#include <gmock/gmock.h> -#include <gtest/gtest.h> - -#include <chrono> -#include <limits> - -namespace testing { - -using bluetooth::common::LegacyLruCache; - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheMainTest1) { - int* value = new int(0); - LegacyLruCache<int, int> cache(3, "testing"); // capacity = 3; - cache.Put(1, 10); - EXPECT_EQ(cache.Size(), 1); - EXPECT_FALSE(cache.Put(2, 20)); - EXPECT_FALSE(cache.Put(3, 30)); - EXPECT_EQ(cache.Size(), 3); - - // 1, 2, 3 should be in cache - EXPECT_TRUE(cache.Get(1, value)); - EXPECT_EQ(*value, 10); - EXPECT_TRUE(cache.Get(2, value)); - EXPECT_EQ(*value, 20); - EXPECT_TRUE(cache.Get(3, value)); - EXPECT_EQ(*value, 30); - EXPECT_EQ(cache.Size(), 3); - - EXPECT_THAT(cache.Put(4, 40), Optional(Pair(1, 10))); - // 2, 3, 4 should be in cache, 1 is evicted - EXPECT_FALSE(cache.Get(1, value)); - EXPECT_TRUE(cache.Get(4, value)); - EXPECT_EQ(*value, 40); - EXPECT_TRUE(cache.Get(2, value)); - EXPECT_EQ(*value, 20); - EXPECT_TRUE(cache.Get(3, value)); - EXPECT_EQ(*value, 30); - - EXPECT_THAT(cache.Put(5, 50), Optional(Pair(4, 40))); - EXPECT_EQ(cache.Size(), 3); - // 2, 3, 5 should be in cache, 4 is evicted - - EXPECT_TRUE(cache.Remove(3)); - EXPECT_FALSE(cache.Put(6, 60)); - // 2, 5, 6 should be in cache - - EXPECT_FALSE(cache.Get(3, value)); - EXPECT_FALSE(cache.Get(4, value)); - EXPECT_TRUE(cache.Get(2, value)); - EXPECT_EQ(*value, 20); - EXPECT_TRUE(cache.Get(5, value)); - EXPECT_EQ(*value, 50); - EXPECT_TRUE(cache.Get(6, value)); - EXPECT_EQ(*value, 60); -} - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheMainTest2) { - int* value = new int(0); - LegacyLruCache<int, int> cache(2, "testing"); // size = 2; - EXPECT_FALSE(cache.Put(1, 10)); - EXPECT_FALSE(cache.Put(2, 20)); - EXPECT_THAT(cache.Put(3, 30), Optional(Pair(1, 10))); - EXPECT_FALSE(cache.Put(2, 200)); - EXPECT_EQ(cache.Size(), 2); - // 3, 2 should be in cache - - EXPECT_FALSE(cache.HasKey(1)); - EXPECT_TRUE(cache.Get(2, value)); - EXPECT_EQ(*value, 200); - EXPECT_TRUE(cache.Get(3, value)); - EXPECT_EQ(*value, 30); - - EXPECT_THAT(cache.Put(4, 40), Optional(Pair(2, 200))); - // 3, 4 should be in cache - - EXPECT_FALSE(cache.HasKey(2)); - EXPECT_TRUE(cache.Get(3, value)); - EXPECT_EQ(*value, 30); - EXPECT_TRUE(cache.Get(4, value)); - EXPECT_EQ(*value, 40); - - EXPECT_TRUE(cache.Remove(4)); - EXPECT_EQ(cache.Size(), 1); - cache.Put(2, 2000); - // 3, 2 should be in cache - - EXPECT_FALSE(cache.HasKey(4)); - EXPECT_TRUE(cache.Get(3, value)); - EXPECT_EQ(*value, 30); - EXPECT_TRUE(cache.Get(2, value)); - EXPECT_EQ(*value, 2000); - - EXPECT_TRUE(cache.Remove(2)); - EXPECT_TRUE(cache.Remove(3)); - cache.Put(5, 50); - cache.Put(1, 100); - cache.Put(1, 1000); - EXPECT_EQ(cache.Size(), 2); - // 1, 5 should be in cache - - EXPECT_FALSE(cache.HasKey(2)); - EXPECT_FALSE(cache.HasKey(3)); - EXPECT_TRUE(cache.Get(1, value)); - EXPECT_EQ(*value, 1000); - EXPECT_TRUE(cache.Get(5, value)); - EXPECT_EQ(*value, 50); -} - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheFindTest) { - LegacyLruCache<int, int> cache(10, "testing"); - cache.Put(1, 10); - cache.Put(2, 20); - int value = 0; - EXPECT_TRUE(cache.Get(1, &value)); - EXPECT_EQ(value, 10); - auto value_ptr = cache.Find(1); - EXPECT_NE(value_ptr, nullptr); - *value_ptr = 20; - EXPECT_TRUE(cache.Get(1, &value)); - EXPECT_EQ(value, 20); - cache.Put(1, 40); - EXPECT_EQ(*value_ptr, 40); - EXPECT_EQ(cache.Find(10), nullptr); -} - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheGetTest) { - LegacyLruCache<int, int> cache(10, "testing"); - cache.Put(1, 10); - cache.Put(2, 20); - int value = 0; - EXPECT_TRUE(cache.Get(1, &value)); - EXPECT_EQ(value, 10); - EXPECT_TRUE(cache.HasKey(1)); - EXPECT_TRUE(cache.HasKey(2)); - EXPECT_FALSE(cache.HasKey(3)); - EXPECT_FALSE(cache.Get(3, &value)); - EXPECT_EQ(value, 10); -} - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheRemoveTest) { - LegacyLruCache<int, int> cache(10, "testing"); - for (int key = 0; key <= 30; key++) { - cache.Put(key, key * 100); - } - for (int key = 0; key <= 20; key++) { - EXPECT_FALSE(cache.HasKey(key)); - } - for (int key = 21; key <= 30; key++) { - EXPECT_TRUE(cache.HasKey(key)); - } - for (int key = 21; key <= 30; key++) { - EXPECT_TRUE(cache.Remove(key)); - } - for (int key = 21; key <= 30; key++) { - EXPECT_FALSE(cache.HasKey(key)); - } -} - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCacheClearTest) { - LegacyLruCache<int, int> cache(10, "testing"); - for (int key = 0; key < 10; key++) { - cache.Put(key, key * 100); - } - for (int key = 0; key < 10; key++) { - EXPECT_TRUE(cache.HasKey(key)); - } - cache.Clear(); - for (int key = 0; key < 10; key++) { - EXPECT_FALSE(cache.HasKey(key)); - } - - for (int key = 0; key < 10; key++) { - cache.Put(key, key * 1000); - } - for (int key = 0; key < 10; key++) { - EXPECT_TRUE(cache.HasKey(key)); - } -} - -TEST(BluetoothLegacyLruCacheTest, LegacyLruCachePressureTest) { - int max_size = 0xFFFFF; // 2^20 = 1M - LegacyLruCache<int, int> cache(static_cast<size_t>(max_size), "testing"); - - // fill the cache - for (int key = 0; key < max_size; key++) { - cache.Put(key, key); - } - - // make sure the cache is full - for (int key = 0; key < max_size; key++) { - EXPECT_TRUE(cache.HasKey(key)); - } - - // refresh the entire cache - for (int key = 0; key < max_size; key++) { - int new_key = key + max_size; - cache.Put(new_key, new_key); - EXPECT_FALSE(cache.HasKey(key)); - EXPECT_TRUE(cache.HasKey(new_key)); - } - - // clear the entire cache - int* value = new int(0); - for (int key = max_size; key < 2 * max_size; key++) { - EXPECT_TRUE(cache.Get(key, value)); - EXPECT_EQ(*value, key); - EXPECT_TRUE(cache.Remove(key)); - } - EXPECT_EQ(cache.Size(), 0); -} - -TEST(BluetoothLegacyLruCacheTest, BluetoothLruMultiThreadPressureTest) { - LegacyLruCache<int, int> cache(100, "testing"); - auto pointer = &cache; - // make sure no deadlock - std::vector<std::thread> workers; - for (int key = 0; key < 100; key++) { - workers.push_back(std::thread([key, pointer]() { - pointer->Put(key, key); - EXPECT_TRUE(pointer->HasKey(key)); - EXPECT_TRUE(pointer->Remove(key)); - })); - } - for (auto& worker : workers) { - worker.join(); - } - EXPECT_EQ(cache.Size(), 0); -} - -} // namespace testing |