← 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): Mark Purcell
  • Date: 2014-01-28 18:23:36 UTC
  • mfrom: (1.1.11)
  • mto: This revision was merged to the branch mainline in revision 24.
  • Revision ID: package-import@ubuntu.com-20140128182336-3xenud1kbnwmf3mz
http://bugs.debian.org/735846
http://bugs.debian.org/727164
http://bugs.debian.org/718178
http://bugs.debian.org/736583
http://bugs.debian.org/722040
http://bugs.debian.org/736746
* New upstream release 
  - Fixes "New Upstream Release" (Closes: #735846)
  - Fixes "Ringtone does not stop" (Closes: #727164)
  - Fixes "[sflphone-kde] crash on startup" (Closes: #718178)
  - Fixes "sflphone GUI crashes when call is hung up" (Closes: #736583)
* Build-Depends: ensure GnuTLS 2.6
  - libucommon-dev (>= 6.0.7-1.1), libccrtp-dev (>= 2.0.6-3)
  - Fixes "FTBFS Build-Depends libgnutls{26,28}-dev" (Closes: #722040)
* Fix "boost 1.49 is going away" unversioned Build-Depends: (Closes: #736746)
* Add Build-Depends: libsndfile-dev, nepomuk-core-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 */