1 /*
2 * Copyright 2018 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #ifndef RTC_BASE_UNIQUE_ID_GENERATOR_H_
12 #define RTC_BASE_UNIQUE_ID_GENERATOR_H_
13
14 #include <limits>
15 #include <set>
16 #include <string>
17
18 #include "api/array_view.h"
19
20 namespace rtc {
21
22 // This class will generate numbers. A common use case is for identifiers.
23 // The generated numbers will be unique, in the local scope of the generator.
24 // This means that a generator will never generate the same number twice.
25 // The generator can also be initialized with a sequence of known ids.
26 // In such a case, it will never generate an id from that list.
27 // Recommendedations:
28 // * Prefer unsigned types.
29 // * Prefer larger types (uint8_t will run out quickly).
30 template <typename TIntegral>
31 class UniqueNumberGenerator {
32 public:
33 typedef TIntegral value_type;
34 UniqueNumberGenerator();
35 // Creates a generator that will never return any value from the given list.
36 explicit UniqueNumberGenerator(ArrayView<TIntegral> known_ids);
37 ~UniqueNumberGenerator();
38
39 // Generates a number that this generator has never produced before.
40 // If there are no available numbers to generate, this method will fail
41 // with an |RTC_CHECK|.
42 TIntegral GenerateNumber();
operator()43 TIntegral operator()() { return GenerateNumber(); }
44
45 // Adds an id that this generator should no longer generate.
46 // Return value indicates whether the ID was hitherto unknown.
47 bool AddKnownId(TIntegral value);
48
49 private:
50 static_assert(std::is_integral<TIntegral>::value, "Must be integral type.");
51 TIntegral counter_;
52 std::set<TIntegral> known_ids_;
53 };
54
55 // This class will generate unique ids. Ids are 32 bit unsigned integers.
56 // The generated ids will be unique, in the local scope of the generator.
57 // This means that a generator will never generate the same id twice.
58 // The generator can also be initialized with a sequence of known ids.
59 // In such a case, it will never generate an id from that list.
60 class UniqueRandomIdGenerator {
61 public:
62 typedef uint32_t value_type;
63 UniqueRandomIdGenerator();
64 // Create a generator that will never return any value from the given list.
65 explicit UniqueRandomIdGenerator(ArrayView<uint32_t> known_ids);
66 ~UniqueRandomIdGenerator();
67
68 // Generates a random id that this generator has never produced before.
69 // This method becomes more expensive with each use, as the probability of
70 // collision for the randomly generated numbers increases.
71 uint32_t GenerateId();
operator()72 uint32_t operator()() { return GenerateId(); }
73
74 // Adds an id that this generator should no longer generate.
75 // Return value indicates whether the ID was hitherto unknown.
76 bool AddKnownId(uint32_t value);
77
78 private:
79 std::set<uint32_t> known_ids_;
80 };
81
82 // This class will generate strings. A common use case is for identifiers.
83 // The generated strings will be unique, in the local scope of the generator.
84 // This means that a generator will never generate the same string twice.
85 // The generator can also be initialized with a sequence of known ids.
86 // In such a case, it will never generate an id from that list.
87 class UniqueStringGenerator {
88 public:
89 typedef std::string value_type;
90 UniqueStringGenerator();
91 explicit UniqueStringGenerator(ArrayView<std::string> known_ids);
92 ~UniqueStringGenerator();
93
94 std::string GenerateString();
operator()95 std::string operator()() { return GenerateString(); }
96
97 // Adds an id that this generator should no longer generate.
98 // Return value indicates whether the ID was hitherto unknown.
99 bool AddKnownId(const std::string& value);
100
101 private:
102 // This implementation will be simple and will generate "0", "1", ...
103 UniqueNumberGenerator<uint32_t> unique_number_generator_;
104 };
105
106 template <typename TIntegral>
UniqueNumberGenerator()107 UniqueNumberGenerator<TIntegral>::UniqueNumberGenerator() : counter_(0) {}
108
109 template <typename TIntegral>
UniqueNumberGenerator(ArrayView<TIntegral> known_ids)110 UniqueNumberGenerator<TIntegral>::UniqueNumberGenerator(
111 ArrayView<TIntegral> known_ids)
112 : counter_(0), known_ids_(known_ids.begin(), known_ids.end()) {}
113
114 template <typename TIntegral>
~UniqueNumberGenerator()115 UniqueNumberGenerator<TIntegral>::~UniqueNumberGenerator() {}
116
117 template <typename TIntegral>
GenerateNumber()118 TIntegral UniqueNumberGenerator<TIntegral>::GenerateNumber() {
119 while (true) {
120 RTC_CHECK_LT(counter_, std::numeric_limits<TIntegral>::max());
121 auto pair = known_ids_.insert(counter_++);
122 if (pair.second) {
123 return *pair.first;
124 }
125 }
126 }
127
128 template <typename TIntegral>
AddKnownId(TIntegral value)129 bool UniqueNumberGenerator<TIntegral>::AddKnownId(TIntegral value) {
130 return known_ids_.insert(value).second;
131 }
132 } // namespace rtc
133
134 #endif // RTC_BASE_UNIQUE_ID_GENERATOR_H_
135