1/* 2 * Copyright (C) 2017 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 "src/tracing/core/id_allocator.h" 18 19#include "gtest/gtest.h" 20 21namespace perfetto { 22namespace { 23 24TEST(IdAllocatorTest, IdAllocation) { 25 using IdType = uint32_t; 26 const IdType kMaxId = 1023; 27 IdAllocator<IdType> id_allocator(kMaxId); 28 29 for (int repetition = 0; repetition < 3; repetition++) { 30 std::set<IdType> ids; 31 for (IdType i = 1; i <= kMaxId; i++) { 32 auto id = id_allocator.Allocate(); 33 EXPECT_NE(0u, id); 34 ASSERT_EQ(0u, ids.count(id)); 35 ids.insert(id); 36 } 37 38 // A further call should fail as we exhausted IDs. 39 ASSERT_EQ(0u, id_allocator.Allocate()); 40 41 // Removing one ID should be enough to make room for another one. 42 for (int i = 0; i < 3; i++) { 43 id_allocator.Free(42); 44 auto id = id_allocator.Allocate(); 45 ASSERT_EQ(42u, id); 46 } 47 48 // Remove the IDs at the boundaries and saturate again. 49 id_allocator.Free(1); 50 id_allocator.Free(kMaxId); 51 ASSERT_EQ(kMaxId, id_allocator.Allocate()); 52 ASSERT_EQ(1u, id_allocator.Allocate()); 53 54 // Should be saturated again. 55 ASSERT_EQ(0u, id_allocator.Allocate()); 56 57 // Release IDs in reverse order. 58 for (IdType i = 0; i < kMaxId; i++) 59 id_allocator.Free(kMaxId - i); 60 } 61} 62 63// Tests corner cases that might be caused by using all 2 ** sizeof(T) - 1 IDs. 64TEST(IdAllocatorTest, IdAllocation_U8) { 65 IdAllocator<uint8_t> id_allocator(0xff); 66 for (size_t i = 0; i < 0xff; i++) { 67 uint8_t id = id_allocator.Allocate(); 68 ASSERT_EQ(i + 1, id); 69 } 70 ASSERT_EQ(0u, id_allocator.Allocate()); 71 id_allocator.Free(0xff); 72 ASSERT_EQ(0xff, id_allocator.Allocate()); 73} 74 75} // namespace 76} // namespace perfetto 77