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 "absl/strings/string_view.h"
19 #include "api/array_view.h"
20 #include "api/sequence_checker.h"
21 #include "rtc_base/synchronization/mutex.h"
22 #include "rtc_base/system/no_unique_address.h"
23
24 namespace rtc {
25
26 // This class will generate numbers. A common use case is for identifiers.
27 // The generated numbers will be unique, in the local scope of the generator.
28 // This means that a generator will never generate the same number twice.
29 // The generator can also be initialized with a sequence of known ids.
30 // In such a case, it will never generate an id from that list.
31 // Recommendedations:
32 // * Prefer unsigned types.
33 // * Prefer larger types (uint8_t will run out quickly).
34 template <typename TIntegral>
35 class UniqueNumberGenerator {
36 public:
37 typedef TIntegral value_type;
38 UniqueNumberGenerator();
39 // Creates a generator that will never return any value from the given list.
40 explicit UniqueNumberGenerator(ArrayView<TIntegral> known_ids);
41 ~UniqueNumberGenerator();
42
43 // Generates a number that this generator has never produced before.
44 // If there are no available numbers to generate, this method will fail
45 // with an `RTC_CHECK`.
46 TIntegral GenerateNumber();
operator()47 TIntegral operator()() { return GenerateNumber(); }
48
49 // Adds an id that this generator should no longer generate.
50 // Return value indicates whether the ID was hitherto unknown.
51 bool AddKnownId(TIntegral value);
52
53 private:
54 RTC_NO_UNIQUE_ADDRESS webrtc::SequenceChecker sequence_checker_;
55 static_assert(std::is_integral<TIntegral>::value, "Must be integral type.");
56 TIntegral counter_ RTC_GUARDED_BY(sequence_checker_);
57 std::set<TIntegral> known_ids_ RTC_GUARDED_BY(sequence_checker_);
58 };
59
60 // This class will generate unique ids. Ids are 32 bit unsigned integers.
61 // The generated ids will be unique, in the local scope of the generator.
62 // This means that a generator will never generate the same id twice.
63 // The generator can also be initialized with a sequence of known ids.
64 // In such a case, it will never generate an id from that list.
65 class UniqueRandomIdGenerator {
66 public:
67 typedef uint32_t value_type;
68 UniqueRandomIdGenerator();
69 // Create a generator that will never return any value from the given list.
70 explicit UniqueRandomIdGenerator(ArrayView<uint32_t> known_ids);
71 ~UniqueRandomIdGenerator();
72
73 // Generates a random id that this generator has never produced before.
74 // This method becomes more expensive with each use, as the probability of
75 // collision for the randomly generated numbers increases.
76 uint32_t GenerateId();
operator()77 uint32_t operator()() { return GenerateId(); }
78
79 // Adds an id that this generator should no longer generate.
80 // Return value indicates whether the ID was hitherto unknown.
81 bool AddKnownId(uint32_t value);
82
83 private:
84 // TODO(bugs.webrtc.org/12666): This lock is needed due to an instance in
85 // SdpOfferAnswerHandler being shared between threads.
86 webrtc::Mutex mutex_;
87 std::set<uint32_t> known_ids_ RTC_GUARDED_BY(&mutex_);
88 };
89
90 // This class will generate strings. A common use case is for identifiers.
91 // The generated strings will be unique, in the local scope of the generator.
92 // This means that a generator will never generate the same string twice.
93 // The generator can also be initialized with a sequence of known ids.
94 // In such a case, it will never generate an id from that list.
95 class UniqueStringGenerator {
96 public:
97 typedef std::string value_type;
98 UniqueStringGenerator();
99 explicit UniqueStringGenerator(ArrayView<std::string> known_ids);
100 ~UniqueStringGenerator();
101
102 std::string GenerateString();
operator()103 std::string operator()() { return GenerateString(); }
104
105 // Adds an id that this generator should no longer generate.
106 // Return value indicates whether the ID was hitherto unknown.
107 bool AddKnownId(absl::string_view value);
108
109 private:
110 // This implementation will be simple and will generate "0", "1", ...
111 UniqueNumberGenerator<uint32_t> unique_number_generator_;
112 };
113
114 template <typename TIntegral>
UniqueNumberGenerator()115 UniqueNumberGenerator<TIntegral>::UniqueNumberGenerator() : counter_(0) {
116 sequence_checker_.Detach();
117 }
118
119 template <typename TIntegral>
UniqueNumberGenerator(ArrayView<TIntegral> known_ids)120 UniqueNumberGenerator<TIntegral>::UniqueNumberGenerator(
121 ArrayView<TIntegral> known_ids)
122 : counter_(0), known_ids_(known_ids.begin(), known_ids.end()) {
123 sequence_checker_.Detach();
124 }
125
126 template <typename TIntegral>
~UniqueNumberGenerator()127 UniqueNumberGenerator<TIntegral>::~UniqueNumberGenerator() {}
128
129 template <typename TIntegral>
GenerateNumber()130 TIntegral UniqueNumberGenerator<TIntegral>::GenerateNumber() {
131 RTC_DCHECK_RUN_ON(&sequence_checker_);
132 while (true) {
133 RTC_CHECK_LT(counter_, std::numeric_limits<TIntegral>::max());
134 auto pair = known_ids_.insert(counter_++);
135 if (pair.second) {
136 return *pair.first;
137 }
138 }
139 }
140
141 template <typename TIntegral>
AddKnownId(TIntegral value)142 bool UniqueNumberGenerator<TIntegral>::AddKnownId(TIntegral value) {
143 RTC_DCHECK_RUN_ON(&sequence_checker_);
144 return known_ids_.insert(value).second;
145 }
146 } // namespace rtc
147
148 #endif // RTC_BASE_UNIQUE_ID_GENERATOR_H_
149