Debian Codegraph @

srtcore/list.h

raw
1 /*
2 * SRT - Secure, Reliable, Transport
3 * Copyright (c) 2018 Haivision Systems Inc.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 */
10
11 /*****************************************************************************
12 Copyright (c) 2001 - 2011, The Board of Trustees of the University of Illinois.
13 All rights reserved.
14
15 Redistribution and use in source and binary forms, with or without
16 modification, are permitted provided that the following conditions are
17 met:
18
19 * Redistributions of source code must retain the above
20 copyright notice, this list of conditions and the
21 following disclaimer.
22
23 * Redistributions in binary form must reproduce the
24 above copyright notice, this list of conditions
25 and the following disclaimer in the documentation
26 and/or other materials provided with the distribution.
27
28 * Neither the name of the University of Illinois
29 nor the names of its contributors may be used to
30 endorse or promote products derived from this
31 software without specific prior written permission.
32
33 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
34 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
35 THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
36 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
37 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
38 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
39 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
40 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
41 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
42 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
43 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 *****************************************************************************/
45
46 /*****************************************************************************
47 written by
48 Yunhong Gu, last updated 01/22/2011
49 modified by
50 Haivision Systems Inc.
51 *****************************************************************************/
52
53 #ifndef INC_SRT_LIST_H
54 #define INC_SRT_LIST_H
55
56 #include <deque>
57
58 #include "udt.h"
59 #include "common.h"
60
61 namespace srt {
62
63 class CSndLossList
64 {
65 public:
66 CSndLossList(int size = 1024);
67 ~CSndLossList();
68
69 /// Insert a seq. no. into the sender loss list.
70 /// @param [in] seqno1 sequence number starts.
71 /// @param [in] seqno2 sequence number ends.
72 /// @return number of packets that are not in the list previously.
73 int insert(int32_t seqno1, int32_t seqno2);
74
75 /// Remove the given sequence number and all numbers that precede it.
76 /// @param [in] seqno sequence number.
77 void removeUpTo(int32_t seqno);
78
79 /// Read the loss length.∏
80 /// @return The length of the list.
81 int getLossLength() const;
82
83 /// Read the first (smallest) loss seq. no. in the list and remove it.
84 /// @return The seq. no. or -1 if the list is empty.
85 int32_t popLostSeq();
86
87 template <class Stream>
88 Stream& traceState(Stream& sout) const
89 {
90 int pos = m_iHead;
91 while (pos != SRT_SEQNO_NONE)
92 {
93 sout << "[" << pos << "]:" << m_caSeq[pos].seqstart;
94 if (m_caSeq[pos].seqend != SRT_SEQNO_NONE)
95 sout << ":" << m_caSeq[pos].seqend;
96 if (m_caSeq[pos].inext == -1)
97 sout << "=|";
98 else
99 sout << "->[" << m_caSeq[pos].inext << "]";
100 sout << ", ";
101 pos = m_caSeq[pos].inext;
102 }
103 sout << " {len:" << m_iLength << " head:" << m_iHead << " last:" << m_iLastInsertPos << "}";
104 return sout;
105 }
106 void traceState() const;
107
108 // Debug/unittest support.
109
110 int head() const { return m_iHead; }
111 int next(int loc) const { return m_caSeq[loc].inext; }
112 int last() const { return m_iLastInsertPos; }
113
114 private:
115 struct Seq
116 {
117 int32_t seqstart; // sequence number starts
118 int32_t seqend; // sequence number ends
119 int inext; // index of the next node in the list
120 } * m_caSeq;
121
122 int m_iHead; // first node
123 int m_iLength; // loss length
124 const int m_iSize; // size of the static array
125 int m_iLastInsertPos; // position of last insert node
126
127 mutable srt::sync::Mutex m_ListLock; // used to synchronize list operation
128
129 private:
130 /// Inserts an element to the beginning and updates head pointer.
131 /// No lock.
132 void insertHead(int pos, int32_t seqno1, int32_t seqno2);
133
134 /// Inserts an element after previous element.
135 /// No lock.
136 void insertAfter(int pos, int pos_after, int32_t seqno1, int32_t seqno2);
137
138 /// Check if it is possible to coalesce element at loc with further elements.
139 /// @param loc - last changed location
140 void coalesce(int loc);
141
142 /// Update existing element with the new range (increase only)
143 /// @param pos position of the element being updated
144 /// @param seqno1 first sequence number in range
145 /// @param seqno2 last sequence number in range (SRT_SEQNO_NONE if no range)
146 bool updateElement(int pos, int32_t seqno1, int32_t seqno2);
147
148 static const int LOC_NONE = -1;
149
150 private:
151 CSndLossList(const CSndLossList&);
152 CSndLossList& operator=(const CSndLossList&);
153 };
154
155 ////////////////////////////////////////////////////////////////////////////////
156
157 class CRcvLossList
158 {
159 public:
160 CRcvLossList(int size = 1024);
161 ~CRcvLossList();
162
163 /// Insert a series of loss seq. no. between "seqno1" and "seqno2" into the receiver's loss list.
164 /// @param [in] seqno1 sequence number starts.
165 /// @param [in] seqno2 sequence number ends.
166 /// @return length of the loss record inserted (seqlen(seqno1, seqno2)), -1 on error.
167 int insert(int32_t seqno1, int32_t seqno2);
168
169 /// Remove a loss seq. no. from the receiver's loss list.
170 /// @param [in] seqno sequence number.
171 /// @return if the packet is removed (true) or no such lost packet is found (false).
172
173 bool remove(int32_t seqno);
174
175 /// Remove all packets between seqno1 and seqno2.
176 /// @param [in] seqno1 start sequence number.
177 /// @param [in] seqno2 end sequence number.
178 /// @return if the packet is removed (true) or no such lost packet is found (false).
179
180 bool remove(int32_t seqno1, int32_t seqno2);
181
182
183 /// Remove all numbers that precede the given sequence number.
184 /// @param [in] seqno sequence number.
185 /// @return the first removed sequence number
186 int32_t removeUpTo(int32_t seqno);
187
188 /// Find if there is any lost packets whose sequence number falling seqno1 and seqno2.
189 /// @param [in] seqno1 start sequence number.
190 /// @param [in] seqno2 end sequence number.
191 /// @return True if found; otherwise false.
192
193 bool find(int32_t seqno1, int32_t seqno2) const;
194
195 /// Read the loss length.
196 /// @return the length of the list.
197
198 int getLossLength() const;
199
200 /// Read the first (smallest) seq. no. in the list.
201 /// @return the sequence number or -1 if the list is empty.
202
203 int32_t getFirstLostSeq() const;
204
205 /// Get a encoded loss array for NAK report.
206 /// @param [out] array the result list of seq. no. to be included in NAK.
207 /// @param [out] len physical length of the result array.
208 /// @param [in] limit maximum length of the array.
209
210 void getLossArray(int32_t* array, int& len, int limit);
211
212 private:
213 struct Seq
214 {
215 int32_t seqstart; // sequence number starts
216 int32_t seqend; // sequence number ends
217 int inext; // index of the next node in the list
218 int iprior; // index of the previous node in the list
219 } * m_caSeq;
220
221 int m_iHead; // first node in the list
222 int m_iTail; // last node in the list;
223 int m_iLength; // loss length
224 int m_iSize; // size of the static array
225 int m_iLargestSeq; // largest seq ever seen
226
227 private:
228 CRcvLossList(const CRcvLossList&);
229 CRcvLossList& operator=(const CRcvLossList&);
230
231 public:
232 struct iterator
233 {
234 int32_t head;
235 Seq* seq;
236
237 iterator(Seq* str, int32_t v)
238 : head(v)
239 , seq(str)
240 {
241 }
242
243 iterator next() const
244 {
245 if (head == -1)
246 return *this; // should report error, but we can only throw exception, so simply ignore it.
247
248 return iterator(seq, seq[head].inext);
249 }
250
251 iterator& operator++()
252 {
253 *this = next();
254 return *this;
255 }
256
257 iterator operator++(int)
258 {
259 iterator old(seq, head);
260 *this = next();
261 return old;
262 }
263
264 bool operator==(const iterator& second) const
265 {
266 // Ignore seq - should be the same and this is only a sanity check.
267 return head == second.head;
268 }
269
270 bool operator!=(const iterator& second) const { return !(*this == second); }
271
272 std::pair<int32_t, int32_t> operator*() { return std::make_pair(seq[head].seqstart, seq[head].seqend); }
273 };
274
275 iterator begin() { return iterator(m_caSeq, m_iHead); }
276 iterator end() { return iterator(m_caSeq, -1); }
277 };
278
279 struct CRcvFreshLoss
280 {
281 int32_t seq[2];
282 int ttl;
283 srt::sync::steady_clock::time_point timestamp;
284
285 CRcvFreshLoss(int32_t seqlo, int32_t seqhi, int initial_ttl);
286
287 // Don't WTF when looking at this. The Windows system headers define
288 // a publicly visible preprocessor macro with that name. REALLY!
289 #ifdef DELETE
290 #undef DELETE
291 #endif
292 enum Emod
293 {
294 NONE, //< the given sequence was not found in this range
295 STRIPPED, //< it was equal to first or last, already taken care of
296 SPLIT, //< found in the middle, you have to split this range into two
297 DELETE //< This was a range of one element exactly equal to sequence. Simply delete it.
298 };
299
300 Emod revoke(int32_t sequence);
301 Emod revoke(int32_t lo, int32_t hi);
302
303 static bool removeOne(std::deque<CRcvFreshLoss>& w_container, int32_t sequence, int* had_ttl = NULL);
304 };
305
306 } // namespace srt
307
308 #endif