← Back to branch summary

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

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2015-01-07 14:51:16 UTC
  • mfrom: (4.3.5 sid)
  • Revision ID: package-import@ubuntu.com-20150107145116-yxnafinf4lrdvrmx
Tags: 1.4.1-0.1ubuntu1
* Merge with Debian, remaining changes:
 - Drop soprano, nepomuk build-dep
* Drop ubuntu patches, now upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject-2.1.0/third_party/BaseClasses/wxlist.h
1
 
//------------------------------------------------------------------------------
2
 
// File: WXList.h
3
 
//
4
 
// Desc: DirectShow base classes - defines a non-MFC generic template list
5
 
//       class.
6
 
//
7
 
// Copyright (c) 1992-2001 Microsoft Corporation.  All rights reserved.
8
 
//------------------------------------------------------------------------------
9
 
 
10
 
 
11
 
/* A generic list of pointers to objects.
12
 
   No storage management or copying is done on the objects pointed to.
13
 
   Objectives: avoid using MFC libraries in ndm kernel mode and
14
 
   provide a really useful list type.
15
 
 
16
 
   The class is thread safe in that separate threads may add and
17
 
   delete items in the list concurrently although the application
18
 
   must ensure that constructor and destructor access is suitably
19
 
   synchronised. An application can cause deadlock with operations
20
 
   which use two lists by simultaneously calling
21
 
   list1->Operation(list2) and list2->Operation(list1).  So don't!
22
 
 
23
 
   The names must not conflict with MFC classes as an application
24
 
   may use both.
25
 
   */
26
 
 
27
 
#ifndef __WXLIST__
28
 
#define __WXLIST__
29
 
 
30
 
   /* A POSITION represents (in some fashion that's opaque) a cursor
31
 
      on the list that can be set to identify any element.  NULL is
32
 
      a valid value and several operations regard NULL as the position
33
 
      "one step off the end of the list".  (In an n element list there
34
 
      are n+1 places to insert and NULL is that "n+1-th" value).
35
 
      The POSITION of an element in the list is only invalidated if
36
 
      that element is deleted.  Move operations may mean that what
37
 
      was a valid POSITION in one list is now a valid POSITION in
38
 
      a different list.
39
 
 
40
 
      Some operations which at first sight are illegal are allowed as
41
 
      harmless no-ops.  For instance RemoveHead is legal on an empty
42
 
      list and it returns NULL.  This allows an atomic way to test if
43
 
      there is an element there, and if so, get it.  The two operations
44
 
      AddTail and RemoveHead thus implement a MONITOR (See Hoare's paper).
45
 
 
46
 
      Single element operations return POSITIONs, non-NULL means it worked.
47
 
      whole list operations return a BOOL.  TRUE means it all worked.
48
 
 
49
 
      This definition is the same as the POSITION type for MFCs, so we must
50
 
      avoid defining it twice.
51
 
   */
52
 
#ifndef __AFX_H__
53
 
struct __POSITION { int unused; };
54
 
typedef __POSITION* POSITION;
55
 
#endif
56
 
 
57
 
const int DEFAULTCACHE = 10;    /* Default node object cache size */
58
 
 
59
 
/* A class representing one node in a list.
60
 
   Each node knows a pointer to it's adjacent nodes and also a pointer
61
 
   to the object that it looks after.
62
 
   All of these pointers can be retrieved or set through member functions.
63
 
*/
64
 
class CBaseList 
65
 
#ifdef DEBUG
66
 
    : public CBaseObject
67
 
#endif
68
 
{
69
 
    /* Making these classes inherit from CBaseObject does nothing
70
 
       functionally but it allows us to check there are no memory
71
 
       leaks in debug builds. 
72
 
    */
73
 
 
74
 
public:
75
 
 
76
 
#ifdef DEBUG
77
 
    class CNode : public CBaseObject {
78
 
#else
79
 
    class CNode {
80
 
#endif
81
 
 
82
 
        CNode *m_pPrev;         /* Previous node in the list */
83
 
        CNode *m_pNext;         /* Next node in the list */
84
 
        void *m_pObject;      /* Pointer to the object */
85
 
 
86
 
    public:
87
 
 
88
 
        /* Constructor - initialise the object's pointers */
89
 
        CNode()
90
 
#ifdef DEBUG
91
 
            : CBaseObject(NAME("List node"))
92
 
#endif
93
 
        {
94
 
        };
95
 
 
96
 
 
97
 
        /* Return the previous node before this one */
98
 
        __out CNode *Prev() const { return m_pPrev; };
99
 
 
100
 
 
101
 
        /* Return the next node after this one */
102
 
        __out CNode *Next() const { return m_pNext; };
103
 
 
104
 
 
105
 
        /* Set the previous node before this one */
106
 
        void SetPrev(__in_opt CNode *p) { m_pPrev = p; };
107
 
 
108
 
 
109
 
        /* Set the next node after this one */
110
 
        void SetNext(__in_opt CNode *p) { m_pNext = p; };
111
 
 
112
 
 
113
 
        /* Get the pointer to the object for this node */
114
 
        __out void *GetData() const { return m_pObject; };
115
 
 
116
 
 
117
 
        /* Set the pointer to the object for this node */
118
 
        void SetData(__in void *p) { m_pObject = p; };
119
 
    };
120
 
 
121
 
    class CNodeCache
122
 
    {
123
 
    public:
124
 
        CNodeCache(INT iCacheSize) : m_iCacheSize(iCacheSize),
125
 
                                     m_pHead(NULL),
126
 
                                     m_iUsed(0)
127
 
                                     {};
128
 
        ~CNodeCache() {
129
 
            CNode *pNode = m_pHead;
130
 
            while (pNode) {
131
 
                CNode *pCurrent = pNode;
132
 
                pNode = pNode->Next();
133
 
                delete pCurrent;
134
 
            }
135
 
        };
136
 
        void AddToCache(__inout CNode *pNode)
137
 
        {
138
 
            if (m_iUsed < m_iCacheSize) {
139
 
                pNode->SetNext(m_pHead);
140
 
                m_pHead = pNode;
141
 
                m_iUsed++;
142
 
            } else {
143
 
                delete pNode;
144
 
            }
145
 
        };
146
 
        CNode *RemoveFromCache()
147
 
        {
148
 
            CNode *pNode = m_pHead;
149
 
            if (pNode != NULL) {
150
 
                m_pHead = pNode->Next();
151
 
                m_iUsed--;
152
 
                ASSERT(m_iUsed >= 0);
153
 
            } else {
154
 
                ASSERT(m_iUsed == 0);
155
 
            }
156
 
            return pNode;
157
 
        };
158
 
    private:
159
 
        INT m_iCacheSize;
160
 
        INT m_iUsed;
161
 
        CNode *m_pHead;
162
 
    };
163
 
 
164
 
protected:
165
 
 
166
 
    CNode* m_pFirst;    /* Pointer to first node in the list */
167
 
    CNode* m_pLast;     /* Pointer to the last node in the list */
168
 
    LONG m_Count;       /* Number of nodes currently in the list */
169
 
 
170
 
private:
171
 
 
172
 
    CNodeCache m_Cache; /* Cache of unused node pointers */
173
 
 
174
 
private:
175
 
 
176
 
    /* These override the default copy constructor and assignment
177
 
       operator for all list classes. They are in the private class
178
 
       declaration section so that anybody trying to pass a list
179
 
       object by value will generate a compile time error of
180
 
       "cannot access the private member function". If these were
181
 
       not here then the compiler will create default constructors
182
 
       and assignment operators which when executed first take a
183
 
       copy of all member variables and then during destruction
184
 
       delete them all. This must not be done for any heap
185
 
       allocated data.
186
 
    */
187
 
    CBaseList(const CBaseList &refList);
188
 
    CBaseList &operator=(const CBaseList &refList);
189
 
 
190
 
public:
191
 
 
192
 
    CBaseList(__in_opt LPCTSTR pName,
193
 
              INT iItems);
194
 
 
195
 
    CBaseList(__in_opt LPCTSTR pName);
196
 
#ifdef UNICODE
197
 
    CBaseList(__in_opt LPCSTR pName,
198
 
              INT iItems);
199
 
 
200
 
    CBaseList(__in_opt LPCSTR pName);
201
 
#endif
202
 
    ~CBaseList();
203
 
 
204
 
    /* Remove all the nodes from *this i.e. make the list empty */
205
 
    void RemoveAll();
206
 
 
207
 
 
208
 
    /* Return a cursor which identifies the first element of *this */
209
 
    __out_opt POSITION GetHeadPositionI() const;
210
 
 
211
 
 
212
 
    /* Return a cursor which identifies the last element of *this */
213
 
    __out_opt POSITION GetTailPositionI() const;
214
 
 
215
 
 
216
 
    /* Return the number of objects in *this */
217
 
    int GetCountI() const;
218
 
 
219
 
protected:
220
 
    /* Return the pointer to the object at rp,
221
 
       Update rp to the next node in *this
222
 
       but make it NULL if it was at the end of *this.
223
 
       This is a wart retained for backwards compatibility.
224
 
       GetPrev is not implemented.
225
 
       Use Next, Prev and Get separately.
226
 
    */
227
 
    __out void *GetNextI(__inout POSITION& rp) const;
228
 
 
229
 
 
230
 
    /* Return a pointer to the object at p
231
 
       Asking for the object at NULL will return NULL harmlessly.
232
 
    */
233
 
    __out_opt void *GetI(__in_opt POSITION p) const;
234
 
    __out void *GetValidI(__in POSITION p) const;
235
 
 
236
 
public:
237
 
    /* return the next / prev position in *this
238
 
       return NULL when going past the end/start.
239
 
       Next(NULL) is same as GetHeadPosition()
240
 
       Prev(NULL) is same as GetTailPosition()
241
 
       An n element list therefore behaves like a n+1 element
242
 
       cycle with NULL at the start/end.
243
 
 
244
 
       !!WARNING!! - This handling of NULL is DIFFERENT from GetNext.
245
 
 
246
 
       Some reasons are:
247
 
       1. For a list of n items there are n+1 positions to insert
248
 
          These are conveniently encoded as the n POSITIONs and NULL.
249
 
       2. If you are keeping a list sorted (fairly common) and you
250
 
          search forward for an element to insert before and don't
251
 
          find it you finish up with NULL as the element before which
252
 
          to insert.  You then want that NULL to be a valid POSITION
253
 
          so that you can insert before it and you want that insertion
254
 
          point to mean the (n+1)-th one that doesn't have a POSITION.
255
 
          (symmetrically if you are working backwards through the list).
256
 
       3. It simplifies the algebra which the methods generate.
257
 
          e.g. AddBefore(p,x) is identical to AddAfter(Prev(p),x)
258
 
          in ALL cases.  All the other arguments probably are reflections
259
 
          of the algebraic point.
260
 
    */
261
 
    __out_opt POSITION Next(__in_opt POSITION pos) const
262
 
    {
263
 
        if (pos == NULL) {
264
 
            return (POSITION) m_pFirst;
265
 
        }
266
 
        CNode *pn = (CNode *) pos;
267
 
        return (POSITION) pn->Next();
268
 
    } //Next
269
 
 
270
 
    // See Next
271
 
    __out_opt POSITION Prev(__in_opt POSITION pos) const
272
 
    {
273
 
        if (pos == NULL) {
274
 
            return (POSITION) m_pLast;
275
 
        }
276
 
        CNode *pn = (CNode *) pos;
277
 
        return (POSITION) pn->Prev();
278
 
    } //Prev
279
 
 
280
 
 
281
 
    /* Return the first position in *this which holds the given
282
 
       pointer.  Return NULL if the pointer was not not found.
283
 
    */
284
 
protected:
285
 
    __out_opt POSITION FindI( __in void * pObj) const;
286
 
 
287
 
    // ??? Should there be (or even should there be only)
288
 
    // ??? POSITION FindNextAfter(void * pObj, POSITION p)
289
 
    // ??? And of course FindPrevBefore too.
290
 
    // ??? List.Find(&Obj) then becomes List.FindNextAfter(&Obj, NULL)
291
 
 
292
 
 
293
 
    /* Remove the first node in *this (deletes the pointer to its
294
 
       object from the list, does not free the object itself).
295
 
       Return the pointer to its object.
296
 
       If *this was already empty it will harmlessly return NULL.
297
 
    */
298
 
    __out_opt void *RemoveHeadI();
299
 
 
300
 
 
301
 
    /* Remove the last node in *this (deletes the pointer to its
302
 
       object from the list, does not free the object itself).
303
 
       Return the pointer to its object.
304
 
       If *this was already empty it will harmlessly return NULL.
305
 
    */
306
 
    __out_opt void *RemoveTailI();
307
 
 
308
 
 
309
 
    /* Remove the node identified by p from the list (deletes the pointer
310
 
       to its object from the list, does not free the object itself).
311
 
       Asking to Remove the object at NULL will harmlessly return NULL.
312
 
       Return the pointer to the object removed.
313
 
    */
314
 
    __out_opt void *RemoveI(__in_opt POSITION p);
315
 
 
316
 
    /* Add single object *pObj to become a new last element of the list.
317
 
       Return the new tail position, NULL if it fails.
318
 
       If you are adding a COM objects, you might want AddRef it first.
319
 
       Other existing POSITIONs in *this are still valid
320
 
    */
321
 
    __out_opt POSITION AddTailI(__in void * pObj);
322
 
public:
323
 
 
324
 
 
325
 
    /* Add all the elements in *pList to the tail of *this.
326
 
       This duplicates all the nodes in *pList (i.e. duplicates
327
 
       all its pointers to objects).  It does not duplicate the objects.
328
 
       If you are adding a list of pointers to a COM object into the list
329
 
       it's a good idea to AddRef them all  it when you AddTail it.
330
 
       Return TRUE if it all worked, FALSE if it didn't.
331
 
       If it fails some elements may have been added.
332
 
       Existing POSITIONs in *this are still valid
333
 
 
334
 
       If you actually want to MOVE the elements, use MoveToTail instead.
335
 
    */
336
 
    BOOL AddTail(__in CBaseList *pList);
337
 
 
338
 
 
339
 
    /* Mirror images of AddHead: */
340
 
 
341
 
    /* Add single object to become a new first element of the list.
342
 
       Return the new head position, NULL if it fails.
343
 
       Existing POSITIONs in *this are still valid
344
 
    */
345
 
protected:
346
 
    __out_opt POSITION AddHeadI(__in void * pObj);
347
 
public:
348
 
 
349
 
    /* Add all the elements in *pList to the head of *this.
350
 
       Same warnings apply as for AddTail.
351
 
       Return TRUE if it all worked, FALSE if it didn't.
352
 
       If it fails some of the objects may have been added.
353
 
 
354
 
       If you actually want to MOVE the elements, use MoveToHead instead.
355
 
    */
356
 
    BOOL AddHead(__in CBaseList *pList);
357
 
 
358
 
 
359
 
    /* Add the object *pObj to *this after position p in *this.
360
 
       AddAfter(NULL,x) adds x to the start - equivalent to AddHead
361
 
       Return the position of the object added, NULL if it failed.
362
 
       Existing POSITIONs in *this are undisturbed, including p.
363
 
    */
364
 
protected:
365
 
    __out_opt POSITION AddAfterI(__in_opt POSITION p, __in void * pObj);
366
 
public:
367
 
 
368
 
    /* Add the list *pList to *this after position p in *this
369
 
       AddAfter(NULL,x) adds x to the start - equivalent to AddHead
370
 
       Return TRUE if it all worked, FALSE if it didn't.
371
 
       If it fails, some of the objects may be added
372
 
       Existing POSITIONs in *this are undisturbed, including p.
373
 
    */
374
 
    BOOL AddAfter(__in_opt POSITION p, __in CBaseList *pList);
375
 
 
376
 
 
377
 
    /* Mirror images:
378
 
       Add the object *pObj to this-List after position p in *this.
379
 
       AddBefore(NULL,x) adds x to the end - equivalent to AddTail
380
 
       Return the position of the new object, NULL if it fails
381
 
       Existing POSITIONs in *this are undisturbed, including p.
382
 
    */
383
 
    protected:
384
 
    __out_opt POSITION AddBeforeI(__in_opt POSITION p, __in void * pObj);
385
 
    public:
386
 
 
387
 
    /* Add the list *pList to *this before position p in *this
388
 
       AddAfter(NULL,x) adds x to the start - equivalent to AddHead
389
 
       Return TRUE if it all worked, FALSE if it didn't.
390
 
       If it fails, some of the objects may be added
391
 
       Existing POSITIONs in *this are undisturbed, including p.
392
 
    */
393
 
    BOOL AddBefore(__in_opt POSITION p, __in CBaseList *pList);
394
 
 
395
 
 
396
 
    /* Note that AddAfter(p,x) is equivalent to AddBefore(Next(p),x)
397
 
       even in cases where p is NULL or Next(p) is NULL.
398
 
       Similarly for mirror images etc.
399
 
       This may make it easier to argue about programs.
400
 
    */
401
 
 
402
 
 
403
 
 
404
 
    /* The following operations do not copy any elements.
405
 
       They move existing blocks of elements around by switching pointers.
406
 
       They are fairly efficient for long lists as for short lists.
407
 
       (Alas, the Count slows things down).
408
 
 
409
 
       They split the list into two parts.
410
 
       One part remains as the original list, the other part
411
 
       is appended to the second list.  There are eight possible
412
 
       variations:
413
 
       Split the list {after/before} a given element
414
 
       keep the {head/tail} portion in the original list
415
 
       append the rest to the {head/tail} of the new list.
416
 
 
417
 
       Since After is strictly equivalent to Before Next
418
 
       we are not in serious need of the Before/After variants.
419
 
       That leaves only four.
420
 
 
421
 
       If you are processing a list left to right and dumping
422
 
       the bits that you have processed into another list as
423
 
       you go, the Tail/Tail variant gives the most natural result.
424
 
       If you are processing in reverse order, Head/Head is best.
425
 
 
426
 
       By using NULL positions and empty lists judiciously either
427
 
       of the other two can be built up in two operations.
428
 
 
429
 
       The definition of NULL (see Next/Prev etc) means that
430
 
       degenerate cases include
431
 
          "move all elements to new list"
432
 
          "Split a list into two lists"
433
 
          "Concatenate two lists"
434
 
          (and quite a few no-ops)
435
 
 
436
 
       !!WARNING!! The type checking won't buy you much if you get list
437
 
       positions muddled up - e.g. use a POSITION that's in a different
438
 
       list and see what a mess you get!
439
 
    */
440
 
 
441
 
    /* Split *this after position p in *this
442
 
       Retain as *this the tail portion of the original *this
443
 
       Add the head portion to the tail end of *pList
444
 
       Return TRUE if it all worked, FALSE if it didn't.
445
 
 
446
 
       e.g.
447
 
          foo->MoveToTail(foo->GetHeadPosition(), bar);
448
 
              moves one element from the head of foo to the tail of bar
449
 
          foo->MoveToTail(NULL, bar);
450
 
              is a no-op, returns NULL
451
 
          foo->MoveToTail(foo->GetTailPosition, bar);
452
 
              concatenates foo onto the end of bar and empties foo.
453
 
 
454
 
       A better, except excessively long name might be
455
 
           MoveElementsFromHeadThroughPositionToOtherTail
456
 
    */
457
 
    BOOL MoveToTail(__in_opt POSITION pos, __in CBaseList *pList);
458
 
 
459
 
 
460
 
    /* Mirror image:
461
 
       Split *this before position p in *this.
462
 
       Retain in *this the head portion of the original *this
463
 
       Add the tail portion to the start (i.e. head) of *pList
464
 
 
465
 
       e.g.
466
 
          foo->MoveToHead(foo->GetTailPosition(), bar);
467
 
              moves one element from the tail of foo to the head of bar
468
 
          foo->MoveToHead(NULL, bar);
469
 
              is a no-op, returns NULL
470
 
          foo->MoveToHead(foo->GetHeadPosition, bar);
471
 
              concatenates foo onto the start of bar and empties foo.
472
 
    */
473
 
    BOOL MoveToHead(__in_opt POSITION pos, __in CBaseList *pList);
474
 
 
475
 
 
476
 
    /* Reverse the order of the [pointers to] objects in *this
477
 
    */
478
 
    void Reverse();
479
 
 
480
 
 
481
 
    /* set cursor to the position of each element of list in turn  */
482
 
    #define TRAVERSELIST(list, cursor)               \
483
 
    for ( cursor = (list).GetHeadPosition()           \
484
 
        ; cursor!=NULL                               \
485
 
        ; cursor = (list).Next(cursor)                \
486
 
        )
487
 
 
488
 
 
489
 
    /* set cursor to the position of each element of list in turn
490
 
       in reverse order
491
 
    */
492
 
    #define REVERSETRAVERSELIST(list, cursor)        \
493
 
    for ( cursor = (list).GetTailPosition()           \
494
 
        ; cursor!=NULL                               \
495
 
        ; cursor = (list).Prev(cursor)                \
496
 
        )
497
 
 
498
 
}; // end of class declaration
499
 
 
500
 
template<class OBJECT> class CGenericList : public CBaseList
501
 
{
502
 
public:
503
 
    CGenericList(__in_opt LPCTSTR pName,
504
 
                 INT iItems,
505
 
                 BOOL bLock = TRUE,
506
 
                 BOOL bAlert = FALSE) :
507
 
                     CBaseList(pName, iItems) {
508
 
        UNREFERENCED_PARAMETER(bAlert);
509
 
        UNREFERENCED_PARAMETER(bLock);
510
 
    };
511
 
    CGenericList(__in_opt LPCTSTR pName) :
512
 
                     CBaseList(pName) {
513
 
    };
514
 
 
515
 
    __out_opt POSITION GetHeadPosition() const { return (POSITION)m_pFirst; }
516
 
    __out_opt POSITION GetTailPosition() const { return (POSITION)m_pLast; }
517
 
    int GetCount() const { return m_Count; }
518
 
 
519
 
    __out OBJECT *GetNext(__inout POSITION& rp) const { return (OBJECT *) GetNextI(rp); }
520
 
 
521
 
    __out_opt OBJECT *Get(__in_opt POSITION p) const { return (OBJECT *) GetI(p); }
522
 
    __out OBJECT *GetValid(__in POSITION p) const { return (OBJECT *) GetValidI(p); }
523
 
    __out_opt OBJECT *GetHead() const  { return Get(GetHeadPosition()); }
524
 
 
525
 
    __out_opt OBJECT *RemoveHead() { return (OBJECT *) RemoveHeadI(); }
526
 
 
527
 
    __out_opt OBJECT *RemoveTail() { return (OBJECT *) RemoveTailI(); }
528
 
 
529
 
    __out_opt OBJECT *Remove(__in_opt POSITION p) { return (OBJECT *) RemoveI(p); }
530
 
    __out_opt POSITION AddBefore(__in_opt POSITION p, __in OBJECT * pObj) { return AddBeforeI(p, pObj); }
531
 
    __out_opt POSITION AddAfter(__in_opt POSITION p, __in OBJECT * pObj)  { return AddAfterI(p, pObj); }
532
 
    __out_opt POSITION AddHead(__in OBJECT * pObj) { return AddHeadI(pObj); }
533
 
    __out_opt POSITION AddTail(__in OBJECT * pObj)  { return AddTailI(pObj); }
534
 
    BOOL AddTail(__in CGenericList<OBJECT> *pList)
535
 
            { return CBaseList::AddTail((CBaseList *) pList); }
536
 
    BOOL AddHead(__in CGenericList<OBJECT> *pList)
537
 
            { return CBaseList::AddHead((CBaseList *) pList); }
538
 
    BOOL AddAfter(__in_opt POSITION p, __in CGenericList<OBJECT> *pList)
539
 
            { return CBaseList::AddAfter(p, (CBaseList *) pList); };
540
 
    BOOL AddBefore(__in_opt POSITION p, __in CGenericList<OBJECT> *pList)
541
 
            { return CBaseList::AddBefore(p, (CBaseList *) pList); };
542
 
    __out_opt POSITION Find( __in OBJECT * pObj) const { return FindI(pObj); }
543
 
}; // end of class declaration
544
 
 
545
 
 
546
 
 
547
 
/* These define the standard list types */
548
 
 
549
 
typedef CGenericList<CBaseObject> CBaseObjectList;
550
 
typedef CGenericList<IUnknown> CBaseInterfaceList;
551
 
 
552
 
#endif /* __WXLIST__ */
553