← Back to branch summary

~ubuntu-branches/ubuntu/wily/sflphone/wily

« back to all changes in this revision

Viewing changes to daemon/libs/pjproject-2.1.0/third_party/BaseClasses/wxlist.cpp

  • Committer: Package Import Robot
  • Author(s): Francois Marier, Francois Marier, Mark Purcell
  • Date: 2014-10-18 15:08:50 UTC
  • mfrom: (1.1.12)
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20141018150850-2exfk34ckb15pcwi
Tags: 1.4.1-0.1
http://bugs.debian.org/759576
http://bugs.debian.org/741130
[ Francois Marier ]
* Non-maintainer upload
* New upstream release (closes: #759576, #741130)
  - debian/rules +PJPROJECT_VERSION := 2.2.1
  - add upstream patch to fix broken TLS support
  - add patch to fix pjproject regression

[ Mark Purcell ]
* Build-Depends:
  - sflphone-daemon + libavformat-dev, libavcodec-dev, libswscale-dev,
  libavdevice-dev, libavutil-dev
  - sflphone-gnome + libclutter-gtk-1.0-dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject-2.1.0/third_party/BaseClasses/wxlist.cpp
1
 
//------------------------------------------------------------------------------
2
 
// File: WXList.cpp
3
 
//
4
 
// Desc: DirectShow base classes - implements a non-MFC based generic list
5
 
//       template class.
6
 
// Copyright (c) 1992-2001 Microsoft Corporation.  All rights reserved.
7
 
//------------------------------------------------------------------------------
8
 
 
9
 
#include <pjmedia-videodev/config.h>
10
 
 
11
 
#if defined(PJMEDIA_VIDEO_DEV_HAS_DSHOW) && PJMEDIA_VIDEO_DEV_HAS_DSHOW != 0
12
 
 
13
 
/* A generic list of pointers to objects.
14
 
   Objectives: avoid using MFC libraries in ndm kernel mode and
15
 
   provide a really useful list type.
16
 
 
17
 
   The class is thread safe in that separate threads may add and
18
 
   delete items in the list concurrently although the application
19
 
   must ensure that constructor and destructor access is suitably
20
 
   synchronised.
21
 
 
22
 
   The list name must not conflict with MFC classes as an
23
 
   application may use both
24
 
 
25
 
   The nodes form a doubly linked, NULL terminated chain with an anchor
26
 
   block (the list object per se) holding pointers to the first and last
27
 
   nodes and a count of the nodes.
28
 
   There is a node cache to reduce the allocation and freeing overhead.
29
 
   It optionally (determined at construction time) has an Event which is
30
 
   set whenever the list becomes non-empty and reset whenever it becomes
31
 
   empty.
32
 
   It optionally (determined at construction time) has a Critical Section
33
 
   which is entered during the important part of each operation.  (About
34
 
   all you can do outside it is some parameter checking).
35
 
 
36
 
   The node cache is a repository of nodes that are NOT in the list to speed
37
 
   up storage allocation.  Each list has its own cache to reduce locking and
38
 
   serialising.  The list accesses are serialised anyway for a given list - a
39
 
   common cache would mean that we would have to separately serialise access
40
 
   of all lists within the cache.  Because the cache only stores nodes that are
41
 
   not in the list, releasing the cache does not release any list nodes.  This
42
 
   means that list nodes can be copied or rechained from one list to another
43
 
   without danger of creating a dangling reference if the original cache goes
44
 
   away.
45
 
 
46
 
   Questionable design decisions:
47
 
   1. Retaining the warts for compatibility
48
 
   2. Keeping an element count -i.e. counting whenever we do anything
49
 
      instead of only when we want the count.
50
 
   3. Making the chain pointers NULL terminated.  If the list object
51
 
      itself looks just like a node and the list is kept as a ring then
52
 
      it reduces the number of special cases.  All inserts look the same.
53
 
*/
54
 
 
55
 
 
56
 
#include <streams.h>
57
 
 
58
 
/* set cursor to the position of each element of list in turn  */
59
 
#define INTERNALTRAVERSELIST(list, cursor)               \
60
 
for ( cursor = (list).GetHeadPositionI()           \
61
 
    ; cursor!=NULL                               \
62
 
    ; cursor = (list).Next(cursor)                \
63
 
    )
64
 
 
65
 
 
66
 
/* set cursor to the position of each element of list in turn
67
 
   in reverse order
68
 
*/
69
 
#define INTERNALREVERSETRAVERSELIST(list, cursor)        \
70
 
for ( cursor = (list).GetTailPositionI()           \
71
 
    ; cursor!=NULL                               \
72
 
    ; cursor = (list).Prev(cursor)                \
73
 
    )
74
 
 
75
 
/* Constructor calls a separate initialisation function that
76
 
   creates a node cache, optionally creates a lock object
77
 
   and optionally creates a signaling object.
78
 
 
79
 
   By default we create a locking object, a DEFAULTCACHE sized
80
 
   cache but no event object so the list cannot be used in calls
81
 
   to WaitForSingleObject
82
 
*/
83
 
CBaseList::CBaseList(__in_opt LPCTSTR pName,    // Descriptive list name
84
 
                     INT iItems) :    // Node cache size
85
 
#ifdef DEBUG
86
 
    CBaseObject(pName),
87
 
#endif
88
 
    m_pFirst(NULL),
89
 
    m_pLast(NULL),
90
 
    m_Count(0),
91
 
    m_Cache(iItems)
92
 
{
93
 
} // constructor
94
 
 
95
 
CBaseList::CBaseList(__in_opt LPCTSTR pName) :  // Descriptive list name
96
 
#ifdef DEBUG
97
 
    CBaseObject(pName),
98
 
#endif
99
 
    m_pFirst(NULL),
100
 
    m_pLast(NULL),
101
 
    m_Count(0),
102
 
    m_Cache(DEFAULTCACHE)
103
 
{
104
 
} // constructor
105
 
 
106
 
#ifdef UNICODE
107
 
CBaseList::CBaseList(__in_opt LPCSTR pName,    // Descriptive list name
108
 
                     INT iItems) :    // Node cache size
109
 
#ifdef DEBUG
110
 
    CBaseObject(pName),
111
 
#endif
112
 
    m_pFirst(NULL),
113
 
    m_pLast(NULL),
114
 
    m_Count(0),
115
 
    m_Cache(iItems)
116
 
{
117
 
} // constructor
118
 
 
119
 
CBaseList::CBaseList(__in_opt LPCSTR pName) :  // Descriptive list name
120
 
#ifdef DEBUG
121
 
    CBaseObject(pName),
122
 
#endif
123
 
    m_pFirst(NULL),
124
 
    m_pLast(NULL),
125
 
    m_Count(0),
126
 
    m_Cache(DEFAULTCACHE)
127
 
{
128
 
} // constructor
129
 
 
130
 
#endif
131
 
 
132
 
/* The destructor enumerates all the node objects in the list and
133
 
   in the cache deleting each in turn. We do not do any processing
134
 
   on the objects that the list holds (i.e. points to) so if they
135
 
   represent interfaces for example the creator of the list should
136
 
   ensure that each of them is released before deleting us
137
 
*/
138
 
CBaseList::~CBaseList()
139
 
{
140
 
    /* Delete all our list nodes */
141
 
 
142
 
    RemoveAll();
143
 
 
144
 
} // destructor
145
 
 
146
 
/* Remove all the nodes from the list but don't do anything
147
 
   with the objects that each node looks after (this is the
148
 
   responsibility of the creator).
149
 
   Aa a last act we reset the signalling event
150
 
   (if available) to indicate to clients that the list
151
 
   does not have any entries in it.
152
 
*/
153
 
void CBaseList::RemoveAll()
154
 
{
155
 
    /* Free up all the CNode objects NOTE we don't bother putting the
156
 
       deleted nodes into the cache as this method is only really called
157
 
       in serious times of change such as when we are being deleted at
158
 
       which point the cache will be deleted anway */
159
 
 
160
 
    CNode *pn = m_pFirst;
161
 
    while (pn) {
162
 
        CNode *op = pn;
163
 
        pn = pn->Next();
164
 
        delete op;
165
 
    }
166
 
 
167
 
    /* Reset the object count and the list pointers */
168
 
 
169
 
    m_Count = 0;
170
 
    m_pFirst = m_pLast = NULL;
171
 
 
172
 
} // RemoveAll
173
 
 
174
 
 
175
 
 
176
 
/* Return a position enumerator for the entire list.
177
 
   A position enumerator is a pointer to a node object cast to a
178
 
   transparent type so all we do is return the head/tail node
179
 
   pointer in the list.
180
 
   WARNING because the position is a pointer to a node there is
181
 
   an implicit assumption for users a the list class that after
182
 
   deleting an object from the list that any other position
183
 
   enumerators that you have may be invalid (since the node
184
 
   may be gone).
185
 
*/
186
 
__out_opt POSITION CBaseList::GetHeadPositionI() const
187
 
{
188
 
    return (POSITION) m_pFirst;
189
 
} // GetHeadPosition
190
 
 
191
 
 
192
 
 
193
 
__out_opt POSITION CBaseList::GetTailPositionI() const
194
 
{
195
 
    return (POSITION) m_pLast;
196
 
} // GetTailPosition
197
 
 
198
 
 
199
 
 
200
 
/* Get the number of objects in the list,
201
 
   Get the lock before accessing the count.
202
 
   Locking may not be entirely necessary but it has the side effect
203
 
   of making sure that all operations are complete before we get it.
204
 
   So for example if a list is being added to this list then that
205
 
   will have completed in full before we continue rather than seeing
206
 
   an intermediate albeit valid state
207
 
*/
208
 
int CBaseList::GetCountI() const
209
 
{
210
 
    return m_Count;
211
 
} // GetCount
212
 
 
213
 
 
214
 
 
215
 
/* Return the object at rp, update rp to the next object from
216
 
   the list or NULL if you have moved over the last object.
217
 
   You may still call this function once we return NULL but
218
 
   we will continue to return a NULL position value
219
 
*/
220
 
__out void *CBaseList::GetNextI(__inout POSITION& rp) const
221
 
{
222
 
    /* have we reached the end of the list */
223
 
 
224
 
    if (rp == NULL) {
225
 
        return NULL;
226
 
    }
227
 
 
228
 
    /* Lock the object before continuing */
229
 
 
230
 
    void *pObject;
231
 
 
232
 
    /* Copy the original position then step on */
233
 
 
234
 
    CNode *pn = (CNode *) rp;
235
 
    ASSERT(pn != NULL);
236
 
    rp = (POSITION) pn->Next();
237
 
 
238
 
    /* Get the object at the original position from the list */
239
 
 
240
 
    pObject = pn->GetData();
241
 
    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
242
 
    return pObject;
243
 
} //GetNext
244
 
 
245
 
 
246
 
 
247
 
/* Return the object at p.
248
 
   Asking for the object at NULL ASSERTs then returns NULL
249
 
   The object is NOT locked.  The list is not being changed
250
 
   in any way.  If another thread is busy deleting the object
251
 
   then locking would only result in a change from one bad
252
 
   behaviour to another.
253
 
*/
254
 
__out_opt void *CBaseList::GetI(__in_opt POSITION p) const
255
 
{
256
 
    if (p == NULL) {
257
 
        return NULL;
258
 
    }
259
 
 
260
 
    CNode * pn = (CNode *) p;
261
 
    void *pObject = pn->GetData();
262
 
    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
263
 
    return pObject;
264
 
} //Get
265
 
 
266
 
__out void *CBaseList::GetValidI(__in POSITION p) const
267
 
{
268
 
    CNode * pn = (CNode *) p;
269
 
    void *pObject = pn->GetData();
270
 
    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
271
 
    return pObject;
272
 
} //Get
273
 
 
274
 
 
275
 
/* Return the first position in the list which holds the given pointer.
276
 
   Return NULL if it's not found.
277
 
*/
278
 
__out_opt POSITION CBaseList::FindI( __in void * pObj) const
279
 
{
280
 
    POSITION pn;
281
 
    INTERNALTRAVERSELIST(*this, pn){
282
 
        if (GetI(pn)==pObj) {
283
 
            return pn;
284
 
        }
285
 
    }
286
 
    return NULL;
287
 
} // Find
288
 
 
289
 
 
290
 
 
291
 
/* Remove the first node in the list (deletes the pointer to its object
292
 
   from the list, does not free the object itself).
293
 
   Return the pointer to its object or NULL if empty
294
 
*/
295
 
__out_opt void *CBaseList::RemoveHeadI()
296
 
{
297
 
    /* All we do is get the head position and ask for that to be deleted.
298
 
       We could special case this since some of the code path checking
299
 
       in Remove() is redundant as we know there is no previous
300
 
       node for example but it seems to gain little over the
301
 
       added complexity
302
 
    */
303
 
 
304
 
    return RemoveI((POSITION)m_pFirst);
305
 
} // RemoveHead
306
 
 
307
 
 
308
 
 
309
 
/* Remove the last node in the list (deletes the pointer to its object
310
 
   from the list, does not free the object itself).
311
 
   Return the pointer to its object or NULL if empty
312
 
*/
313
 
__out_opt void *CBaseList::RemoveTailI()
314
 
{
315
 
    /* All we do is get the tail position and ask for that to be deleted.
316
 
       We could special case this since some of the code path checking
317
 
       in Remove() is redundant as we know there is no previous
318
 
       node for example but it seems to gain little over the
319
 
       added complexity
320
 
    */
321
 
 
322
 
    return RemoveI((POSITION)m_pLast);
323
 
} // RemoveTail
324
 
 
325
 
 
326
 
 
327
 
/* Remove the pointer to the object in this position from the list.
328
 
   Deal with all the chain pointers
329
 
   Return a pointer to the object removed from the list.
330
 
   The node object that is freed as a result
331
 
   of this operation is added to the node cache where
332
 
   it can be used again.
333
 
   Remove(NULL) is a harmless no-op - but probably is a wart.
334
 
*/
335
 
__out_opt void *CBaseList::RemoveI(__in_opt POSITION pos)
336
 
{
337
 
    /* Lock the critical section before continuing */
338
 
 
339
 
    // ASSERT (pos!=NULL);     // Removing NULL is to be harmless!
340
 
    if (pos==NULL) return NULL;
341
 
 
342
 
 
343
 
    CNode *pCurrent = (CNode *) pos;
344
 
    ASSERT(pCurrent != NULL);
345
 
 
346
 
    /* Update the previous node */
347
 
 
348
 
    CNode *pNode = pCurrent->Prev();
349
 
    if (pNode == NULL) {
350
 
        m_pFirst = pCurrent->Next();
351
 
    } else {
352
 
        pNode->SetNext(pCurrent->Next());
353
 
    }
354
 
 
355
 
    /* Update the following node */
356
 
 
357
 
    pNode = pCurrent->Next();
358
 
    if (pNode == NULL) {
359
 
        m_pLast = pCurrent->Prev();
360
 
    } else {
361
 
        pNode->SetPrev(pCurrent->Prev());
362
 
    }
363
 
 
364
 
    /* Get the object this node was looking after */
365
 
 
366
 
    void *pObject = pCurrent->GetData();
367
 
 
368
 
    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
369
 
 
370
 
    /* Try and add the node object to the cache -
371
 
       a NULL return code from the cache means we ran out of room.
372
 
       The cache size is fixed by a constructor argument when the
373
 
       list is created and defaults to DEFAULTCACHE.
374
 
       This means that the cache will have room for this many
375
 
       node objects. So if you have a list of media samples
376
 
       and you know there will never be more than five active at
377
 
       any given time of them for example then override the default
378
 
       constructor
379
 
    */
380
 
 
381
 
    m_Cache.AddToCache(pCurrent);
382
 
 
383
 
    /* If the list is empty then reset the list event */
384
 
 
385
 
    --m_Count;
386
 
    ASSERT(m_Count >= 0);
387
 
    return pObject;
388
 
} // Remove
389
 
 
390
 
 
391
 
 
392
 
/* Add this object to the tail end of our list
393
 
   Return the new tail position.
394
 
*/
395
 
 
396
 
__out_opt POSITION CBaseList::AddTailI(__in void *pObject)
397
 
{
398
 
    /* Lock the critical section before continuing */
399
 
 
400
 
    CNode *pNode;
401
 
    // ASSERT(pObject);   // NULL pointers in the list are allowed.
402
 
 
403
 
    /* If there is a node objects in the cache then use
404
 
       that otherwise we will have to create a new one */
405
 
 
406
 
    pNode = (CNode *) m_Cache.RemoveFromCache();
407
 
    if (pNode == NULL) {
408
 
        pNode = new CNode;
409
 
    }
410
 
 
411
 
    /* Check we have a valid object */
412
 
 
413
 
    if (pNode == NULL) {
414
 
        return NULL;
415
 
    }
416
 
 
417
 
    /* Initialise all the CNode object
418
 
       just in case it came from the cache
419
 
    */
420
 
 
421
 
    pNode->SetData(pObject);
422
 
    pNode->SetNext(NULL);
423
 
    pNode->SetPrev(m_pLast);
424
 
 
425
 
    if (m_pLast == NULL) {
426
 
        m_pFirst = pNode;
427
 
    } else {
428
 
        m_pLast->SetNext(pNode);
429
 
    }
430
 
 
431
 
    /* Set the new last node pointer and also increment the number
432
 
       of list entries, the critical section is unlocked when we
433
 
       exit the function
434
 
    */
435
 
 
436
 
    m_pLast = pNode;
437
 
    ++m_Count;
438
 
 
439
 
    return (POSITION) pNode;
440
 
} // AddTail(object)
441
 
 
442
 
 
443
 
 
444
 
/* Add this object to the head end of our list
445
 
   Return the new head position.
446
 
*/
447
 
__out_opt POSITION CBaseList::AddHeadI(__in void *pObject)
448
 
{
449
 
    CNode *pNode;
450
 
    // ASSERT(pObject);  // NULL pointers in the list are allowed.
451
 
 
452
 
    /* If there is a node objects in the cache then use
453
 
       that otherwise we will have to create a new one */
454
 
 
455
 
    pNode = (CNode *) m_Cache.RemoveFromCache();
456
 
    if (pNode == NULL) {
457
 
        pNode = new CNode;
458
 
    }
459
 
 
460
 
    /* Check we have a valid object */
461
 
 
462
 
    if (pNode == NULL) {
463
 
        return NULL;
464
 
    }
465
 
 
466
 
    /* Initialise all the CNode object
467
 
       just in case it came from the cache
468
 
    */
469
 
 
470
 
    pNode->SetData(pObject);
471
 
 
472
 
    /* chain it in (set four pointers) */
473
 
    pNode->SetPrev(NULL);
474
 
    pNode->SetNext(m_pFirst);
475
 
 
476
 
    if (m_pFirst == NULL) {
477
 
        m_pLast = pNode;
478
 
    } else {
479
 
        m_pFirst->SetPrev(pNode);
480
 
    }
481
 
    m_pFirst = pNode;
482
 
 
483
 
    ++m_Count;
484
 
 
485
 
    return (POSITION) pNode;
486
 
} // AddHead(object)
487
 
 
488
 
 
489
 
 
490
 
/* Add all the elements in *pList to the tail of this list.
491
 
   Return TRUE if it all worked, FALSE if it didn't.
492
 
   If it fails some elements may have been added.
493
 
*/
494
 
BOOL CBaseList::AddTail(__in CBaseList *pList)
495
 
{
496
 
    /* lock the object before starting then enumerate
497
 
       each entry in the source list and add them one by one to
498
 
       our list (while still holding the object lock)
499
 
       Lock the other list too.
500
 
    */
501
 
    POSITION pos = pList->GetHeadPositionI();
502
 
 
503
 
    while (pos) {
504
 
       if (NULL == AddTailI(pList->GetNextI(pos))) {
505
 
           return FALSE;
506
 
       }
507
 
    }
508
 
    return TRUE;
509
 
} // AddTail(list)
510
 
 
511
 
 
512
 
 
513
 
/* Add all the elements in *pList to the head of this list.
514
 
   Return TRUE if it all worked, FALSE if it didn't.
515
 
   If it fails some elements may have been added.
516
 
*/
517
 
BOOL CBaseList::AddHead(__in CBaseList *pList)
518
 
{
519
 
    /* lock the object before starting then enumerate
520
 
       each entry in the source list and add them one by one to
521
 
       our list (while still holding the object lock)
522
 
       Lock the other list too.
523
 
 
524
 
       To avoid reversing the list, traverse it backwards.
525
 
    */
526
 
 
527
 
    POSITION pos;
528
 
 
529
 
    INTERNALREVERSETRAVERSELIST(*pList, pos) {
530
 
        if (NULL== AddHeadI(pList->GetValidI(pos))){
531
 
            return FALSE;
532
 
        }
533
 
    }
534
 
    return TRUE;
535
 
} // AddHead(list)
536
 
 
537
 
 
538
 
 
539
 
/* Add the object after position p
540
 
   p is still valid after the operation.
541
 
   AddAfter(NULL,x) adds x to the start - same as AddHead
542
 
   Return the position of the new object, NULL if it failed
543
 
*/
544
 
__out_opt POSITION  CBaseList::AddAfterI(__in_opt POSITION pos, __in void * pObj)
545
 
{
546
 
    if (pos==NULL)
547
 
        return AddHeadI(pObj);
548
 
 
549
 
    /* As someone else might be furkling with the list -
550
 
       Lock the critical section before continuing
551
 
    */
552
 
    CNode *pAfter = (CNode *) pos;
553
 
    ASSERT(pAfter != NULL);
554
 
    if (pAfter==m_pLast)
555
 
        return AddTailI(pObj);
556
 
 
557
 
    /* set pnode to point to a new node, preferably from the cache */
558
 
 
559
 
    CNode *pNode = (CNode *) m_Cache.RemoveFromCache();
560
 
    if (pNode == NULL) {
561
 
        pNode = new CNode;
562
 
    }
563
 
 
564
 
    /* Check we have a valid object */
565
 
 
566
 
    if (pNode == NULL) {
567
 
        return NULL;
568
 
    }
569
 
 
570
 
    /* Initialise all the CNode object
571
 
       just in case it came from the cache
572
 
    */
573
 
 
574
 
    pNode->SetData(pObj);
575
 
 
576
 
    /* It is to be added to the middle of the list - there is a before
577
 
       and after node.  Chain it after pAfter, before pBefore.
578
 
    */
579
 
    CNode * pBefore = pAfter->Next();
580
 
    ASSERT(pBefore != NULL);
581
 
 
582
 
    /* chain it in (set four pointers) */
583
 
    pNode->SetPrev(pAfter);
584
 
    pNode->SetNext(pBefore);
585
 
    pBefore->SetPrev(pNode);
586
 
    pAfter->SetNext(pNode);
587
 
 
588
 
    ++m_Count;
589
 
 
590
 
    return (POSITION) pNode;
591
 
 
592
 
} // AddAfter(object)
593
 
 
594
 
 
595
 
 
596
 
BOOL CBaseList::AddAfter(__in_opt POSITION p, __in CBaseList *pList)
597
 
{
598
 
    POSITION pos;
599
 
    INTERNALTRAVERSELIST(*pList, pos) {
600
 
        /* p follows along the elements being added */
601
 
        p = AddAfterI(p, pList->GetValidI(pos));
602
 
        if (p==NULL) return FALSE;
603
 
    }
604
 
    return TRUE;
605
 
} // AddAfter(list)
606
 
 
607
 
 
608
 
 
609
 
/* Mirror images:
610
 
   Add the element or list after position p.
611
 
   p is still valid after the operation.
612
 
   AddBefore(NULL,x) adds x to the end - same as AddTail
613
 
*/
614
 
__out_opt POSITION CBaseList::AddBeforeI(__in_opt POSITION pos, __in void * pObj)
615
 
{
616
 
    if (pos==NULL)
617
 
        return AddTailI(pObj);
618
 
 
619
 
    /* set pnode to point to a new node, preferably from the cache */
620
 
 
621
 
    CNode *pBefore = (CNode *) pos;
622
 
    ASSERT(pBefore != NULL);
623
 
    if (pBefore==m_pFirst)
624
 
        return AddHeadI(pObj);
625
 
 
626
 
    CNode * pNode = (CNode *) m_Cache.RemoveFromCache();
627
 
    if (pNode == NULL) {
628
 
        pNode = new CNode;
629
 
    }
630
 
 
631
 
    /* Check we have a valid object */
632
 
 
633
 
    if (pNode == NULL) {
634
 
        return NULL;
635
 
    }
636
 
 
637
 
    /* Initialise all the CNode object
638
 
       just in case it came from the cache
639
 
    */
640
 
 
641
 
    pNode->SetData(pObj);
642
 
 
643
 
    /* It is to be added to the middle of the list - there is a before
644
 
       and after node.  Chain it after pAfter, before pBefore.
645
 
    */
646
 
 
647
 
    CNode * pAfter = pBefore->Prev();
648
 
    ASSERT(pAfter != NULL);
649
 
 
650
 
    /* chain it in (set four pointers) */
651
 
    pNode->SetPrev(pAfter);
652
 
    pNode->SetNext(pBefore);
653
 
    pBefore->SetPrev(pNode);
654
 
    pAfter->SetNext(pNode);
655
 
 
656
 
    ++m_Count;
657
 
 
658
 
    return (POSITION) pNode;
659
 
 
660
 
} // Addbefore(object)
661
 
 
662
 
 
663
 
 
664
 
BOOL CBaseList::AddBefore(__in_opt POSITION p, __in CBaseList *pList)
665
 
{
666
 
    POSITION pos;
667
 
    INTERNALREVERSETRAVERSELIST(*pList, pos) {
668
 
        /* p follows along the elements being added */
669
 
        p = AddBeforeI(p, pList->GetValidI(pos));
670
 
        if (p==NULL) return FALSE;
671
 
    }
672
 
    return TRUE;
673
 
} // AddBefore(list)
674
 
 
675
 
 
676
 
 
677
 
/* Split *this after position p in *this
678
 
   Retain as *this the tail portion of the original *this
679
 
   Add the head portion to the tail end of *pList
680
 
   Return TRUE if it all worked, FALSE if it didn't.
681
 
 
682
 
   e.g.
683
 
      foo->MoveToTail(foo->GetHeadPosition(), bar);
684
 
          moves one element from the head of foo to the tail of bar
685
 
      foo->MoveToTail(NULL, bar);
686
 
          is a no-op
687
 
      foo->MoveToTail(foo->GetTailPosition, bar);
688
 
          concatenates foo onto the end of bar and empties foo.
689
 
 
690
 
   A better, except excessively long name might be
691
 
       MoveElementsFromHeadThroughPositionToOtherTail
692
 
*/
693
 
BOOL CBaseList::MoveToTail
694
 
        (__in_opt POSITION pos, __in CBaseList *pList)
695
 
{
696
 
    /* Algorithm:
697
 
       Note that the elements (including their order) in the concatenation
698
 
       of *pList to the head of *this is invariant.
699
 
       1. Count elements to be moved
700
 
       2. Join *pList onto the head of this to make one long chain
701
 
       3. Set first/Last pointers in *this and *pList
702
 
       4. Break the chain at the new place
703
 
       5. Adjust counts
704
 
       6. Set/Reset any events
705
 
    */
706
 
 
707
 
    if (pos==NULL) return TRUE;  // no-op.  Eliminates special cases later.
708
 
 
709
 
 
710
 
    /* Make cMove the number of nodes to move */
711
 
    CNode * p = (CNode *)pos;
712
 
    int cMove = 0;            // number of nodes to move
713
 
    while(p!=NULL) {
714
 
       p = p->Prev();
715
 
       ++cMove;
716
 
    }
717
 
 
718
 
 
719
 
    /* Join the two chains together */
720
 
    if (pList->m_pLast!=NULL)
721
 
        pList->m_pLast->SetNext(m_pFirst);
722
 
    if (m_pFirst!=NULL)
723
 
        m_pFirst->SetPrev(pList->m_pLast);
724
 
 
725
 
 
726
 
    /* set first and last pointers */
727
 
    p = (CNode *)pos;
728
 
 
729
 
    if (pList->m_pFirst==NULL)
730
 
        pList->m_pFirst = m_pFirst;
731
 
    m_pFirst = p->Next();
732
 
    if (m_pFirst==NULL)
733
 
        m_pLast = NULL;
734
 
    pList->m_pLast = p;
735
 
 
736
 
 
737
 
    /* Break the chain after p to create the new pieces */
738
 
    if (m_pFirst!=NULL)
739
 
        m_pFirst->SetPrev(NULL);
740
 
    p->SetNext(NULL);
741
 
 
742
 
 
743
 
    /* Adjust the counts */
744
 
    m_Count -= cMove;
745
 
    pList->m_Count += cMove;
746
 
 
747
 
    return TRUE;
748
 
 
749
 
} // MoveToTail
750
 
 
751
 
 
752
 
 
753
 
/* Mirror image of MoveToTail:
754
 
   Split *this before position p in *this.
755
 
   Retain in *this the head portion of the original *this
756
 
   Add the tail portion to the start (i.e. head) of *pList
757
 
   Return TRUE if it all worked, FALSE if it didn't.
758
 
 
759
 
   e.g.
760
 
      foo->MoveToHead(foo->GetTailPosition(), bar);
761
 
          moves one element from the tail of foo to the head of bar
762
 
      foo->MoveToHead(NULL, bar);
763
 
          is a no-op
764
 
      foo->MoveToHead(foo->GetHeadPosition, bar);
765
 
          concatenates foo onto the start of bar and empties foo.
766
 
*/
767
 
BOOL CBaseList::MoveToHead
768
 
        (__in_opt POSITION pos, __in CBaseList *pList)
769
 
{
770
 
 
771
 
    /* See the comments on the algorithm in MoveToTail */
772
 
 
773
 
    if (pos==NULL) return TRUE;  // no-op.  Eliminates special cases later.
774
 
 
775
 
    /* Make cMove the number of nodes to move */
776
 
    CNode * p = (CNode *)pos;
777
 
    int cMove = 0;            // number of nodes to move
778
 
    while(p!=NULL) {
779
 
       p = p->Next();
780
 
       ++cMove;
781
 
    }
782
 
 
783
 
 
784
 
    /* Join the two chains together */
785
 
    if (pList->m_pFirst!=NULL)
786
 
        pList->m_pFirst->SetPrev(m_pLast);
787
 
    if (m_pLast!=NULL)
788
 
        m_pLast->SetNext(pList->m_pFirst);
789
 
 
790
 
 
791
 
    /* set first and last pointers */
792
 
    p = (CNode *)pos;
793
 
 
794
 
 
795
 
    if (pList->m_pLast==NULL)
796
 
        pList->m_pLast = m_pLast;
797
 
 
798
 
    m_pLast = p->Prev();
799
 
    if (m_pLast==NULL)
800
 
        m_pFirst = NULL;
801
 
    pList->m_pFirst = p;
802
 
 
803
 
 
804
 
    /* Break the chain after p to create the new pieces */
805
 
    if (m_pLast!=NULL)
806
 
        m_pLast->SetNext(NULL);
807
 
    p->SetPrev(NULL);
808
 
 
809
 
 
810
 
    /* Adjust the counts */
811
 
    m_Count -= cMove;
812
 
    pList->m_Count += cMove;
813
 
 
814
 
    return TRUE;
815
 
 
816
 
} // MoveToHead
817
 
 
818
 
 
819
 
 
820
 
/* Reverse the order of the [pointers to] objects in *this
821
 
*/
822
 
void CBaseList::Reverse()
823
 
{
824
 
    /* algorithm:
825
 
       The obvious booby trap is that you flip pointers around and lose
826
 
       addressability to the node that you are going to process next.
827
 
       The easy way to avoid this is do do one chain at a time.
828
 
 
829
 
       Run along the forward chain,
830
 
       For each node, set the reverse pointer to the one ahead of us.
831
 
       The reverse chain is now a copy of the old forward chain, including
832
 
       the NULL termination.
833
 
 
834
 
       Run along the reverse chain (i.e. old forward chain again)
835
 
       For each node set the forward pointer of the node ahead to point back
836
 
       to the one we're standing on.
837
 
       The first node needs special treatment,
838
 
       it's new forward pointer is NULL.
839
 
       Finally set the First/Last pointers
840
 
 
841
 
    */
842
 
    CNode * p;
843
 
 
844
 
    // Yes we COULD use a traverse, but it would look funny!
845
 
    p = m_pFirst;
846
 
    while (p!=NULL) {
847
 
        CNode * q;
848
 
        q = p->Next();
849
 
        p->SetNext(p->Prev());
850
 
        p->SetPrev(q);
851
 
        p = q;
852
 
    }
853
 
 
854
 
    p = m_pFirst;
855
 
    m_pFirst = m_pLast;
856
 
    m_pLast = p;
857
 
 
858
 
 
859
 
#if 0     // old version
860
 
 
861
 
    if (m_pFirst==NULL) return;          // empty list
862
 
    if (m_pFirst->Next()==NULL) return;  // single node list
863
 
 
864
 
 
865
 
    /* run along forward chain */
866
 
    for ( p = m_pFirst
867
 
        ; p!=NULL
868
 
        ; p = p->Next()
869
 
        ){
870
 
        p->SetPrev(p->Next());
871
 
    }
872
 
 
873
 
 
874
 
    /* special case first element */
875
 
    m_pFirst->SetNext(NULL);     // fix the old first element
876
 
 
877
 
 
878
 
    /* run along new reverse chain i.e. old forward chain again */
879
 
    for ( p = m_pFirst           // start at the old first element
880
 
        ; p->Prev()!=NULL        // while there's a node still to be set
881
 
        ; p = p->Prev()          // work in the same direction as before
882
 
        ){
883
 
        p->Prev()->SetNext(p);
884
 
    }
885
 
 
886
 
 
887
 
    /* fix forward and reverse pointers
888
 
       - the triple XOR swap would work but all the casts look hideous */
889
 
    p = m_pFirst;
890
 
    m_pFirst = m_pLast;
891
 
    m_pLast = p;
892
 
#endif
893
 
 
894
 
} // Reverse
895
 
 
896
 
#endif /* PJMEDIA_VIDEO_DEV_HAS_DSHOW */