1 /*****************************************************************
2 |
3 | AP4 - Lists
4 |
5 | Copyright 2002-2008 Axiomatic Systems, LLC
6 |
7 |
8 | This file is part of Bento4/AP4 (MP4 Atom Processing Library).
9 |
10 | Unless you have obtained Bento4 under a difference license,
11 | this version of Bento4 is Bento4|GPL.
12 | Bento4|GPL is free software; you can redistribute it and/or modify
13 | it under the terms of the GNU General Public License as published by
14 | the Free Software Foundation; either version 2, or (at your option)
15 | any later version.
16 |
17 | Bento4|GPL is distributed in the hope that it will be useful,
18 | but WITHOUT ANY WARRANTY; without even the implied warranty of
19 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 | GNU General Public License for more details.
21 |
22 | You should have received a copy of the GNU General Public License
23 | along with Bento4|GPL; see the file COPYING. If not, write to the
24 | Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 | 02111-1307, USA.
26 |
27 ****************************************************************/
28
29 #ifndef _AP4_LIST_H_
30 #define _AP4_LIST_H_
31
32 /*----------------------------------------------------------------------
33 | includes
34 +---------------------------------------------------------------------*/
35 #include "Ap4Types.h"
36 #include "Ap4Results.h"
37
38 /*----------------------------------------------------------------------
39 | forward references
40 +---------------------------------------------------------------------*/
41 template <typename T> class AP4_List;
42
43 /*----------------------------------------------------------------------
44 | AP4_List
45 +---------------------------------------------------------------------*/
46 template <typename T>
47 class AP4_List
48 {
49 public:
50 // types
51 class Item
52 {
53 public:
54 // types
55 class Operator
56 {
57 public:
58 // methods
~Operator()59 virtual ~Operator() {}
60 virtual AP4_Result Action(T* data) const = 0;
61 };
62
63 class Finder
64 {
65 public:
66 // methods
~Finder()67 virtual ~Finder() {}
68 virtual AP4_Result Test(T* data) const = 0;
69 };
70
71 // methods
Item(T * data)72 Item(T* data) : m_Data(data), m_Next(0), m_Prev(0) {}
~Item()73 ~Item() {}
GetNext()74 Item* GetNext() { return m_Next; }
GetPrev()75 Item* GetPrev() { return m_Prev; }
GetData()76 T* GetData() { return m_Data; }
77
78 private:
79 // members
80 T* m_Data;
81 Item* m_Next;
82 Item* m_Prev;
83
84 // friends
85 friend class AP4_List;
86 };
87
88 // methods
89 AP4_List<T>(): m_ItemCount(0), m_Head(0), m_Tail(0) {}
90 virtual ~AP4_List<T>();
91 AP4_Result Clear();
92 AP4_Result Add(T* data);
93 AP4_Result Add(AP4_List<T> &data);
94 AP4_Result Add(Item* item);
95 AP4_Result Remove(Item* item);
96 AP4_Result Remove(T* data);
97 AP4_Result Insert(Item* where, T* data);
98 AP4_Result Get(AP4_Ordinal idx, T*& data) const;
99 AP4_Result PopHead(T*& data);
100 AP4_Result Apply(const typename Item::Operator& op) const;
101 AP4_Result ApplyUntilFailure(const typename Item::Operator& op) const;
102 AP4_Result ApplyUntilSuccess(const typename Item::Operator& op) const ;
103 AP4_Result ReverseApply(const typename Item::Operator& op) const;
104 AP4_Result Find(const typename Item::Finder& finder, T*& data) const;
105 AP4_Result ReverseFind(const typename Item::Finder& finder, T*& data) const;
106 AP4_Result DeleteReferences();
ItemCount()107 AP4_Cardinal ItemCount() const { return m_ItemCount; }
FirstItem()108 Item* FirstItem() const { return m_Head; }
LastItem()109 Item* LastItem() const { return m_Tail; }
110
111 protected:
112 // members
113 AP4_Cardinal m_ItemCount;
114 Item* m_Head;
115 Item* m_Tail;
116
117 private:
118 // these cannot be used
119 AP4_List<T>(const AP4_List<T>&);
120 AP4_List<T>& operator=(const AP4_List<T>&);
121 };
122
123 /*----------------------------------------------------------------------
124 | AP4_List<T>::~AP4_List<T>
125 +---------------------------------------------------------------------*/
126 template <typename T>
~AP4_List()127 AP4_List<T>::~AP4_List()
128 {
129 Clear();
130 }
131
132 /*----------------------------------------------------------------------
133 | AP4_List<T>::Clear
134 +---------------------------------------------------------------------*/
135 template <typename T>
136 inline
137 AP4_Result
Clear()138 AP4_List<T>::Clear()
139 {
140 Item* item = m_Head;
141
142 while (item) {
143 Item* next = item->m_Next;
144 delete item;
145 item = next;
146 }
147 m_ItemCount = 0;
148 m_Head = m_Tail = NULL;
149
150 return AP4_SUCCESS;
151 }
152
153 /*----------------------------------------------------------------------
154 | AP4_List<T>::Add
155 +---------------------------------------------------------------------*/
156 template <typename T>
157 inline
158 AP4_Result
Add(T * data)159 AP4_List<T>::Add(T* data)
160 {
161 return Add(new Item(data));
162 }
163
164 template <typename T>
165 inline
166 AP4_Result
Add(AP4_List<T> & data)167 AP4_List<T>::Add(AP4_List<T> &data)
168 {
169 Item* item = data.m_Head;
170 while (item) {
171 Add(new Item(item->GetData()));
172 item->m_Data = NULL;
173 item = item->m_Next;
174 }
175 return AP4_SUCCESS;
176 }
177
178 /*----------------------------------------------------------------------
179 | AP4_List<T>::Add
180 +---------------------------------------------------------------------*/
181 template <typename T>
182 AP4_Result
Add(Item * item)183 AP4_List<T>::Add(Item* item)
184 {
185 // add element at the tail
186 if (m_Tail) {
187 item->m_Prev = m_Tail;
188 item->m_Next = NULL;
189 m_Tail->m_Next = item;
190 m_Tail = item;
191 } else {
192 m_Head = item;
193 m_Tail = item;
194 item->m_Next = NULL;
195 item->m_Prev = NULL;
196 }
197
198 // one more item in the list now
199 m_ItemCount++;
200
201 return AP4_SUCCESS;
202 }
203
204 /*----------------------------------------------------------------------
205 | AP4_List<T>::Remove
206 +---------------------------------------------------------------------*/
207 template <typename T>
208 AP4_Result
Remove(Item * item)209 AP4_List<T>::Remove(Item* item)
210 {
211 if (item->m_Prev) {
212 // item is not the head
213 if (item->m_Next) {
214 // item is not the tail
215 item->m_Next->m_Prev = item->m_Prev;
216 item->m_Prev->m_Next = item->m_Next;
217 } else {
218 // item is the tail
219 m_Tail = item->m_Prev;
220 m_Tail->m_Next = NULL;
221 }
222 } else {
223 // item is the head
224 m_Head = item->m_Next;
225 if (m_Head) {
226 // item is not the tail
227 m_Head->m_Prev = NULL;
228 } else {
229 // item is also the tail
230 m_Tail = NULL;
231 }
232 }
233
234 // delete the item
235 delete item;
236
237 // one less item in the list now
238 m_ItemCount--;
239
240 return AP4_SUCCESS;
241 }
242
243 /*----------------------------------------------------------------------
244 | AP4_List<T>::Remove
245 +---------------------------------------------------------------------*/
246 template <typename T>
247 AP4_Result
Remove(T * data)248 AP4_List<T>::Remove(T* data)
249 {
250 Item* item = m_Head;
251
252 while (item) {
253 if (item->m_Data == data) {
254 // delete item
255 return Remove(item);
256 }
257 item = item->m_Next;
258 }
259
260 return AP4_ERROR_NO_SUCH_ITEM;
261 }
262
263 /*----------------------------------------------------------------------
264 | AP4_List<T>::Insert
265 +---------------------------------------------------------------------*/
266 template <typename T>
267 AP4_Result
Insert(Item * where,T * data)268 AP4_List<T>::Insert(Item* where, T* data)
269 {
270 Item* item = new Item(data);
271
272 if (where == NULL) {
273 // insert as the head
274 if (m_Head) {
275 // replace the current head
276 item->m_Prev = NULL;
277 item->m_Next = m_Head;
278 m_Head->m_Prev = item;
279 m_Head = item;
280 } else {
281 // this item becomes the head and tail
282 m_Head = item;
283 m_Tail = item;
284 item->m_Next = NULL;
285 item->m_Prev = NULL;
286 }
287 } else {
288 // insert after the 'where' item
289 if (where == m_Tail) {
290 // add the item at the end
291 return Add(item);
292 } else {
293 // update the links
294 item->m_Prev = where;
295 item->m_Next = where->m_Next;
296 where->m_Next->m_Prev = item;
297 where->m_Next = item;
298 }
299 }
300
301 // one more item in the list now
302 ++m_ItemCount;
303
304 return AP4_SUCCESS;
305 }
306
307 /*----------------------------------------------------------------------
308 | AP4_List<T>::Get
309 +---------------------------------------------------------------------*/
310 template <typename T>
311 AP4_Result
Get(AP4_Ordinal idx,T * & data)312 AP4_List<T>::Get(AP4_Ordinal idx, T*& data) const
313 {
314 Item* item = m_Head;
315
316 if (idx < m_ItemCount) {
317 while (idx--) item = item->m_Next;
318 data = item->m_Data;
319 return AP4_SUCCESS;
320 } else {
321 data = NULL;
322 return AP4_ERROR_NO_SUCH_ITEM;
323 }
324 }
325
326 /*----------------------------------------------------------------------
327 | AP4_List<T>::PopHead
328 +---------------------------------------------------------------------*/
329 template <typename T>
330 AP4_Result
PopHead(T * & data)331 AP4_List<T>::PopHead(T*& data)
332 {
333 // check that we have at least one item
334 if (m_Head == NULL) {
335 return AP4_ERROR_LIST_EMPTY;
336 }
337
338 // remove the item and return it
339 data = m_Head->m_Data;
340 Item* head = m_Head;
341 m_Head = m_Head->m_Next;
342 if (m_Head) {
343 m_Head->m_Prev = NULL;
344 } else {
345 m_Tail = NULL;
346 }
347
348 // delete item
349 delete head;
350
351 // one less item in the list now
352 m_ItemCount--;
353
354 return AP4_SUCCESS;
355 }
356
357 /*----------------------------------------------------------------------
358 | AP4_List<T>::Apply
359 +---------------------------------------------------------------------*/
360 template <typename T>
361 inline
362 AP4_Result
Apply(const typename Item::Operator & op)363 AP4_List<T>::Apply(const typename Item::Operator& op) const
364 {
365 Item* item = m_Head;
366
367 while (item) {
368 op.Action(item->m_Data);
369 item = item->m_Next;
370 }
371
372 return AP4_SUCCESS;
373 }
374
375 /*----------------------------------------------------------------------
376 | AP4_List<T>::ApplyUntilFailure
377 +---------------------------------------------------------------------*/
378 template <typename T>
379 inline
380 AP4_Result
ApplyUntilFailure(const typename Item::Operator & op)381 AP4_List<T>::ApplyUntilFailure(const typename Item::Operator& op) const
382 {
383 Item* item = m_Head;
384
385 while (item) {
386 AP4_Result result;
387 result = op.Action(item->m_Data);
388 if (result != AP4_SUCCESS) return result;
389 item = item->m_Next;
390 }
391
392 return AP4_SUCCESS;
393 }
394
395 /*----------------------------------------------------------------------
396 | AP4_List<T>::ApplyUntilSuccess
397 +---------------------------------------------------------------------*/
398 template <typename T>
399 inline
400 AP4_Result
ApplyUntilSuccess(const typename Item::Operator & op)401 AP4_List<T>::ApplyUntilSuccess(const typename Item::Operator& op) const
402 {
403 Item* item = m_Head;
404
405 while (item) {
406 AP4_Result result;
407 result = op.Action(item->m_Data);
408 if (result == AP4_SUCCESS) return AP4_SUCCESS;
409 item = item->m_Next;
410 }
411
412 return AP4_FAILURE;
413 }
414
415 /*----------------------------------------------------------------------
416 | AP4_List<T>::ReverseApply
417 +---------------------------------------------------------------------*/
418 template <typename T>
419 inline
420 AP4_Result
ReverseApply(const typename Item::Operator & op)421 AP4_List<T>::ReverseApply(const typename Item::Operator& op) const
422 {
423 Item* item = m_Tail;
424
425 while (item) {
426 if (op.Action(item->m_Data) != AP4_SUCCESS) {
427 return AP4_ERROR_LIST_OPERATION_ABORTED;
428 }
429 item = item->m_Prev;
430 }
431
432 return AP4_SUCCESS;
433 }
434
435 /*----------------------------------------------------------------------
436 | AP4_List<T>::Find
437 +---------------------------------------------------------------------*/
438 template <typename T>
439 inline
440 AP4_Result
Find(const typename Item::Finder & finder,T * & data)441 AP4_List<T>::Find(const typename Item::Finder& finder, T*& data) const
442 {
443 Item* item = m_Head;
444
445 while (item) {
446 if (finder.Test(item->m_Data) == AP4_SUCCESS) {
447 data = item->m_Data;
448 return AP4_SUCCESS;
449 }
450 item = item->m_Next;
451 }
452
453 data = NULL;
454 return AP4_ERROR_NO_SUCH_ITEM;
455 }
456
457 /*----------------------------------------------------------------------
458 | AP4_List<T>::ReverseFind
459 +---------------------------------------------------------------------*/
460 template <typename T>
461 inline
462 AP4_Result
ReverseFind(const typename Item::Finder & finder,T * & data)463 AP4_List<T>::ReverseFind(const typename Item::Finder& finder, T*& data) const
464 {
465 Item* item = m_Tail;
466
467 while (item) {
468 if (finder.Test(item->m_Data) == AP4_SUCCESS) {
469 data = item->m_Data;
470 return AP4_SUCCESS;
471 }
472 item = item->m_Prev;
473 }
474
475 data = NULL;
476 return AP4_ERROR_NO_SUCH_ITEM;
477 }
478
479 /*----------------------------------------------------------------------
480 | AP4_List<T>::DeleteReferences
481 +---------------------------------------------------------------------*/
482 template <typename T>
483 inline
484 AP4_Result
DeleteReferences()485 AP4_List<T>::DeleteReferences()
486 {
487 Item* item = m_Head;
488
489 while (item) {
490 Item* next = item->m_Next;
491 delete item->m_Data;
492 delete item;
493 item = next;
494 }
495
496 // no more items
497 m_Head = m_Tail = NULL;
498 m_ItemCount = 0;
499
500 return AP4_SUCCESS;
501 }
502
503 #endif // _AP4_LIST_H_
504
505
506
507
508
509
510
511
512
513
514
515
516
517