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