//------------------------------------------------------------------------------
// <copyright file="demxutil.h" company="Microsoft">
//  Copyright (c) Microsoft Corporation.  All rights reserved.
//
//    The use and distribution terms for this software are covered by the
//    Microsoft Limited Public License (Ms-LPL) 
//    which can be found in the file MS-LPL.txt at the root of this distribution.
//    By using this software in any fashion, you are agreeing to be bound by
//    the terms of this license.
//
//    The software is licensed “as-is.”
//
//    You must not remove this notice, or any other, from this software.
// </copyright>
// 
// <summary>
//    Demux code for Windows CE
// </summary>
//-------------------------------------------------------------------------
//======================================================================
// Demux code for Windows CE
//======================================================================

/*++


    Module Name:

        demxutil.h

    Abstract:

        This module contains the utilities, etc... that are used throughout
        the demux

    Revision History:

        27-Aug-1999           created
        07-Jan-2000           added LIST_ENTRY macros
                                    added LIST_ENTRY_CONTAINER template struct
                                    added TListEntryContainerPool template class
                                    added BSearch template function
                                    added BSearchBracket template function
        25-Jan-2000           added CMovingAverage object
        11-May-2000           rewrote CGenericMap, CGenericMultimap to
                                      remove STL dependency
                                    added CGenericSingleMap

    Notes:

--*/

#ifndef __mp2demux_demxutil_h
#define __mp2demux_demxutil_h

#ifdef UNDER_CE
#ifdef HEAP_GENERATE_EXCEPTIONS
#undef HEAP_GENERATE_EXCEPTIONS
#endif
#define HEAP_GENERATE_EXCEPTIONS    0
#endif // UNDER_CE

//  prototypes
LONG
RegGetValIfExist (
    IN  HKEY    hkeyRoot,
    IN  LPCTSTR szValName,
    IN  BOOL    fCreateKey,
    OUT DWORD * pdw
    ) ;

WCHAR *
ToUnicode (
    IN  TCHAR * sztInTCHARString,
    IN  WCHAR * szwInWCHARString,
    IN  DWORD   dwWCHARStringMax
    ) ;

LPWSTR
AnsiToUnicode (
    IN  LPCSTR  string,
    OUT LPWSTR  buffer,
    IN  DWORD   buffer_len
    ) ;

LPSTR
UnicodeToAnsi (
    IN  LPCWSTR string,
    OUT LPSTR   buffer,
    IN  DWORD   buffer_len
    ) ;

HRESULT
EnableStats (
    IN      TCHAR * pszRegRoot,
    IN OUT  BOOL *  pfEnable
    ) ;

BOOL
StatsEnabled (
    IN  TCHAR * pszRegRoot
    ) ;

//  list macros (defined in ntrtl.h)

//
//  VOID
//  InitializeListHead(
//      PLIST_ENTRY ListHead
//      );
//

#ifndef InitializeListHead
#define InitializeListHead(ListHead) (\
    (ListHead)->Flink = (ListHead)->Blink = (ListHead))
#endif //   InitializeListHead

//
//  BOOLEAN
//  IsListEmpty(
//      PLIST_ENTRY ListHead
//      );
//

#ifndef IsListEmpty
#define IsListEmpty(ListHead) \
    ((ListHead)->Flink == (ListHead))
#endif  //  IsListEmpty

//
//  PLIST_ENTRY
//  RemoveHeadList(
//      PLIST_ENTRY ListHead
//      );
//

#ifndef RemoveHeadList
#define RemoveHeadList(ListHead) \
    (ListHead)->Flink;\
    {RemoveEntryList((ListHead)->Flink)}
#endif  //  RemoveHeadList

//
//  PLIST_ENTRY
//  RemoveTailList(
//      PLIST_ENTRY ListHead
//      );
//

#ifndef RemoveTailList
#define RemoveTailList(ListHead) \
    (ListHead)->Blink;\
    {RemoveEntryList((ListHead)->Blink)}
#endif  //  RemoveTailList

//
//  VOID
//  RemoveEntryList(
//      PLIST_ENTRY Entry
//      );
//

#ifndef RemoveEntryList
#define RemoveEntryList(Entry) {\
    PLIST_ENTRY _EX_Blink;\
    PLIST_ENTRY _EX_Flink;\
    _EX_Flink = (Entry)->Flink;\
    _EX_Blink = (Entry)->Blink;\
    _EX_Blink->Flink = _EX_Flink;\
    _EX_Flink->Blink = _EX_Blink;\
    }
#endif  //  RemoveEntryList

//
//  VOID
//  InsertTailList(
//      PLIST_ENTRY ListHead,
//      PLIST_ENTRY Entry
//      );
//

#ifndef InsertTailList
#define InsertTailList(ListHead,Entry) {\
    PLIST_ENTRY _EX_Blink;\
    PLIST_ENTRY _EX_ListHead;\
    _EX_ListHead = (ListHead);\
    _EX_Blink = _EX_ListHead->Blink;\
    (Entry)->Flink = _EX_ListHead;\
    (Entry)->Blink = _EX_Blink;\
    _EX_Blink->Flink = (Entry);\
    _EX_ListHead->Blink = (Entry);\
    }
#endif  //  InsertTailList

//
//  VOID
//  InsertHeadList(
//      PLIST_ENTRY ListHead,
//      PLIST_ENTRY Entry
//      );
//

#ifndef InsertHeadList
#define InsertHeadList(ListHead,Entry) {\
    PLIST_ENTRY _EX_Flink;\
    PLIST_ENTRY _EX_ListHead;\
    _EX_ListHead = (ListHead);\
    _EX_Flink = _EX_ListHead->Flink;\
    (Entry)->Flink = _EX_Flink;\
    (Entry)->Blink = _EX_ListHead;\
    _EX_Flink->Blink = (Entry);\
    _EX_ListHead->Flink = (Entry);\
    }
#endif  //  InsertHeadList

//
//  inserts NewListEntry after ListEntry
//
//  VOID
//  InsertListEntry (
//      PLIST_ENTRY ListEntry,
//      PLIST_ENTRY NewListEntry
//      ) ;
//

#define InsertListEntry(ListEntry,Entry) {\
    PLIST_ENTRY _EX_Flink;\
    PLIST_ENTRY _EX_ListEntry;\
    _EX_ListEntry = (ListEntry);\
    _EX_Flink = _EX_ListEntry->Flink;\
    (Entry)->Flink = _EX_Flink;\
    (Entry)->Blink = _EX_ListEntry;\
    _EX_Flink->Blink = (Entry);\
    _EX_ListEntry->Flink = (Entry);\
    }

//
//  moves entire contents of FromListHead list to ToListHead list,
//  preserving order
//
//  VOID
//  MoveEntryList (
//      PLIST_ENTRY FromListHead,
//      PLIST_ENTRY ToListHead
//      ) ;
//

#define MoveEntryList(FromListHead,ToListHead) {\
    PLIST_ENTRY _EX_FromListHead;\
    PLIST_ENTRY _EX_ToListHead;\
    _EX_FromListHead = (FromListHead);\
    _EX_ToListHead = (ToListHead);\
    _EX_ToListHead->Flink = _EX_FromListHead->Flink;\
    _EX_ToListHead->Blink = _EX_FromListHead->Blink;\
    _EX_ToListHead->Flink->Blink = _EX_ToListHead;\
    _EX_ToListHead->Blink->Flink = _EX_ToListHead;\
    (FromListHead)->Flink = (FromListHead)->Blink = (FromListHead);\
    }


//
//
//  PSINGLE_LIST_ENTRY
//  PopEntryList(
//      PSINGLE_LIST_ENTRY ListHead
//      );
//

#ifndef PopEntryList
#define PopEntryList(ListHead) \
    (ListHead)->Next;\
    {\
        PSINGLE_LIST_ENTRY FirstEntry;\
        FirstEntry = (ListHead)->Next;\
        if (FirstEntry != NULL) {     \
            (ListHead)->Next = FirstEntry->Next;\
        }                             \
    }
#endif  //  PopEntryList

//
//  VOID
//  PushEntryList(
//      PSINGLE_LIST_ENTRY ListHead,
//      PSINGLE_LIST_ENTRY Entry
//      );
//

#ifndef PushEntryList
#define PushEntryList(ListHead,Entry) \
    (Entry)->Next = (ListHead)->Next; \
    (ListHead)->Next = (Entry)
#endif  //  PushEntryList

//  ---------------------------------------------------------------------------
//      templates

template <class T> T Min (T a, T b) { return (a < b ? a : b) ; }
template <class T> T Max (T a, T b) { return (a > b ? a : b) ; }
template <class T> T Abs (T t)      { return (t >= 0 ? t : -t) ; }

//  ---------------------------------------------------------------------------
//  CIAsyncReader
//  ---------------------------------------------------------------------------

template <LONG lBufferLength>
class CIAsyncReader
/*++
    Wraps an IAsyncReader COM interface pointer.  Moves a window along the file
    returning a BYTE * pointer with valid length.
--*/
{
    LONGLONG        m_llFileTotalLength ;
    BYTE            m_Buffer [lBufferLength] ;
    LONGLONG        m_llBufferOffset ;
    LONG            m_lBufferValid ;
    IAsyncReader *  m_pIAsyncReader ;

    LONG
    Read_ (
        IN  LONGLONG    llFileOffset
        )
    {
        HRESULT     hr ;
#ifndef UNDER_CE
        LONGLONG    llAvailable ;
        LONGLONG    llTotal ;
#endif //UNDER_CE
        LONG        lRead ;

        //  should have already verified that the offset is valid
        ASSERT (llFileOffset < m_llFileTotalLength) ;

        //  we may have more buffer left than file;
        lRead = (LONG) Min <LONGLONG> (m_llFileTotalLength - llFileOffset, lBufferLength) ;

        //  need to read something in
        if (lRead > 0) {
            hr = m_pIAsyncReader -> SyncRead (
                    llFileOffset,
                    lRead,
                    m_Buffer
                    ) ;
            if (SUCCEEDED (hr)) {
                //  update member variables
                m_lBufferValid      = lRead ;
                m_llBufferOffset    = llFileOffset ;
            }
            else {
                lRead = 0 ;
            }
        }
        else {
            //  ran out of file
            lRead = 0 ;
        }

        return lRead ;
    }

    BOOL
    InCurrentWindow_ (
        IN      LONGLONG    llFileOffset,
        IN OUT  LONG *      plLength
        )
    {
        BOOL    r ;
#ifndef UNDER_CE
        LONG    lBufferRemaining ;
#endif //UNDER_CE

        //  if we have a window
        r = HaveWindow_ () ;
        if (r) {
            //  check the starting offset
            if (llFileOffset >= m_llBufferOffset) {
                //  check endpoint; may need to shrink the length
                (* plLength) = (LONG) Max <LONGLONG> (m_lBufferValid - (llFileOffset - m_llBufferOffset), 0) ;
                r = ((* plLength) > 0) ;
            }
            else {
                r = FALSE ;
            }
        }

        return r ;
    }

    BOOL
    HaveWindow_ (
        )
    {
        return (m_llBufferOffset != UNDEFINED ? TRUE : FALSE) ;
    }

    public :

        CIAsyncReader (
            IN  IAsyncReader *  pIAsyncReader
            ) : m_pIAsyncReader     (pIAsyncReader),
                m_llFileTotalLength (0),
                m_llBufferOffset    (UNDEFINED),
                m_lBufferValid      (0)
        {
            ASSERT (m_pIAsyncReader) ;
            m_pIAsyncReader -> AddRef () ;
        }

        virtual
        ~CIAsyncReader (
            )
        {
            m_pIAsyncReader -> Release () ;
        }

        LONGLONG
        GetFileTotalLength (
            )
        {
            HRESULT     hr ;
            LONGLONG    llAvailable ;

            if (m_llFileTotalLength == 0) {
                hr = m_pIAsyncReader -> Length (
                        & m_llFileTotalLength,
                        & llAvailable
                        ) ;
                if (FAILED (hr)) {
                    //  make sure it's still undefined
                    m_llFileTotalLength = 0 ;
                }
            }

            return m_llFileTotalLength ;
        }

        //  assumption is that we are moving forward; so if there's a read
        //   it will at the specified offset
        BYTE * const
        SetWindow (
            IN      LONGLONG    llFileOffset,
            IN OUT  LONG *      plWindowLength  //  IN = 0 -> read in max/fill in
                                                //   what's available
            )
        {
            LONGLONG    llOffset ;
            LONG        lLength ;
            BYTE *      pb ;
            BOOL        r ;

            ASSERT (plWindowLength) ;

            if (GetFileTotalLength () > llFileOffset) {
                //  valid request - window starts within the file

                //  length is either specified, or want to have max
                lLength = ((* plWindowLength) == 0 ? lBufferLength : (* plWindowLength)) ;

                r = InCurrentWindow_ (
                        llFileOffset,
                        & lLength
                        ) ;
                if (!r ||
                    ((* plWindowLength) > 0 && lLength < (* plWindowLength))) {
                    //  either the starting point is out of bounds, or the caller
                    //   specified a length and it's not within the window;
                    //   either way we need to read something in
                    llOffset    = llFileOffset ;
                    lLength     = lBufferLength ;       //  try to read as much as possible

                    lLength = Read_ (llOffset) ;
                    if (lLength == 0) {
                        //  failed to read anything in
                        return NULL ;
                    }
                }

                ASSERT (llFileOffset >= m_llBufferOffset) ;
                ASSERT (llFileOffset + lLength <= m_llBufferOffset + m_lBufferValid) ;

                //  set outgoing
                pb = & (m_Buffer [0]) + (llFileOffset - m_llBufferOffset) ;
                (* plWindowLength) = lLength ;
            }
            else {
                //  invalid request
                pb = NULL ;
            }

            return pb ;
        }

        BYTE * const
        GetCurrentWindow (
            OUT LONGLONG *  pllFileOffset,
            OUT LONG *      plWindowLength
            )
        {
            BYTE *  pb ;

            if (m_llBufferOffset != UNDEFINED) {
                pb = & (m_Buffer [0]) ;

                (* pllFileOffset)   = m_llBufferOffset ;
                (* plWindowLength)  = m_lBufferValid ;
            }
            else {
                pb = NULL ;
            }

            return pb ;
        }
} ;

//  ---------------------------------------------------------------------------
//      CMpeg2ProgramStreamSniffer
//  ---------------------------------------------------------------------------

class CMpeg2ProgramStreamSniffer
/*++
    Performs program stream parsing on an IAsyncReader pointer.  Allows frame
    seeking, frame stepping.  Also provides static helper methods to determine
    frame length, header length, etc..
--*/
{
    enum {
        //  --------------------------------------------------------------------
        //  this is the read buffer size; we read multiple of these obviously,
        //  but we keep this small so we don't have drag MBs of data all over
        //  the place like the old one did
        SCRATCH_BUFFER_LENGTH       = MAX_PS_PES_PACKET_LENGTH + 3
    } ;

    CIAsyncReader <SCRATCH_BUFFER_LENGTH>   m_CIAsyncReader ;

    public :

        CMpeg2ProgramStreamSniffer (
            IN  IAsyncReader *  pIAsyncReader
            ) : m_CIAsyncReader (pIAsyncReader) {}

        virtual
        ~CMpeg2ProgramStreamSniffer (
            ) {}

        //  --------------------------------------------------------------------
        //  static helper methods

        static LONG PESHeaderLength  (IN BYTE * pbPESHeader) ;
        static LONG PESPacketLength  (IN BYTE * pbPESPacket) ;
        static LONGLONG PackSCR      (IN BYTE * pbPackHeader) ;
        static DWORD PackMuxRate     (IN BYTE * pbPackHeader) ;
        static BOOL IsVideoStartCode (IN BYTE bStartCode) { return (STREAM_ID_VIDEO_STREAM_MIN <= bStartCode &&
                                                                    bStartCode <= STREAM_ID_VIDEO_STREAM_MAX) ; }
        static BOOL IsAudioStartCode (IN BYTE bStartCode) { return (STREAM_ID_AUDIO_STREAM_MIN <= bStartCode &&
                                                                    bStartCode <= STREAM_ID_AUDIO_STREAM_MAX) ; }
        static BOOL IsPrivateStream1 (IN BYTE bStartCode) { return (bStartCode == STREAM_ID_PRIVATE_STREAM_1) ; }

        //  --------------------------------------------------------------------

        LONGLONG ProgramStreamLength () { return m_CIAsyncReader.GetFileTotalLength () ; }

        //  --------------------------------------------------------------------

        //  llStartingOffset may/may not be on a prefix boundary
        HRESULT
        SeekToNextPacket (
            IN OUT  LONGLONG *  pllStreamOffset,    //  IN: [start; OUT: found
            OUT     BYTE **     ppbPESPacket,       //  pointer to a buffer with the packet
            OUT     LONG *      plBufferLength      //  available buffer
            ) ;

        //  llStartingOffset must be on a prefix boundary; fails if the
        //   stepping forward by the length of the PES packet (as specified
        //   in the PES header), does not point to a prefix boundary
        HRESULT
        StepToNextPacketStrict (
            IN OUT  LONGLONG *  pllStreamOffset,    //  IN: [start; OUT: found
            OUT     BYTE **     ppbPESPacket,       //  pointer to a buffer with the packet
            OUT     LONG *      plBufferLength      //  available buffer
            ) ;

        //  llStartingOffset must be on a prefix boundary; does not fail if
        //   stepping forward by the length of the PES packet (as specified
        //   in the PES header), does not point to a prefix boundary; if it does
        //   not, a seek forward to the next prefix is made; the call if fails
        //   if no prefix is found anywhere
        HRESULT
        StepToNextPacketNonStrict (
            IN OUT  LONGLONG *  pllStreamOffset,    //  IN: [start; OUT: found
            OUT     BYTE **     ppbPESPacket,       //  pointer to a buffer with the packet
            OUT     LONG *      plBufferLength      //  available buffer
            ) ;
} ;

//  ---------------------------------------------------------------------------
//      CRefCountedCritSec
//  ---------------------------------------------------------------------------

class CRefCountedCritSec
    : public CCritSec
/*++
    Independent object that lives/dies by refcounts.  We use it when we have
    disparate refcounted objects that must make use of a common lock for
    synchronization purposes.
--*/
{
    LONG    m_cRefcount ;

    public :

        CRefCountedCritSec (
            ) : m_cRefcount (1)
        {
            TRACE_CONSTRUCTOR (TEXT ("CRefCountedCritSec")) ;
        }

        ~CRefCountedCritSec (
            )
        {
            TRACE_DESTRUCTOR (TEXT ("CRefCountedCritSec")) ;
        }

        ULONG
        AddRef (
            )
        {
            return InterlockedIncrement (& m_cRefcount) ;
        }

        ULONG
        Release (
            )
        {
            if (InterlockedDecrement (& m_cRefcount) == 0) {
                delete this ;
                return 0 ;
            }

            ASSERT (m_cRefcount > 0) ;
            return m_cRefcount ;
        }
} ;

//  ----------------------------------------------------------------------------
//      CTStickyVal
//  ----------------------------------------------------------------------------

template <class T>
class CTStickyVal
/*++
    This class stores a 1-way value i.e. once the value is set, it cannot be
    set to another value without resetting.  The sticky value is specified
    when the object is created.

    This allows various callers to set the value, but if any of them sets the
    the value, subsequents settings will not erase the sticky value that was
    set previously.
--*/
{
    T   m_StickyVal ;
    T   m_CurrentVal ;

    public :

        CTStickyVal (
            IN  T   StickyVal
            ) : m_StickyVal     (StickyVal),
                m_CurrentVal    (StickyVal) {}

        void Init (IN T tVal)   { m_CurrentVal = tVal ; }
        void Set (IN T tVal)    { m_CurrentVal = (m_CurrentVal == m_StickyVal ? m_CurrentVal : tVal) ; }
        BOOL IsSet ()           { return (m_CurrentVal == m_StickyVal ? TRUE : FALSE) ; }
} ;

//  ----------------------------------------------------------------------------
//      CDataCache
//  ----------------------------------------------------------------------------

class CDataCache
{
    BYTE *  m_pbCache ;
    BYTE *  m_pbCurrent ;
    int     m_iCacheSize ;

    public :

        CDataCache (
            IN  BYTE *  pbCache,
            IN  int     iCacheSize
            ) : m_pbCache       (pbCache),
                m_iCacheSize    (iCacheSize),
                m_pbCurrent     (pbCache) {}

        int CurCacheSize ()     { return (int) (m_pbCurrent - m_pbCache) ; }
        int CacheRemaining ()   { return m_iCacheSize - CurCacheSize () ; }
        BYTE * Get ()           { return m_pbCache ; }
        void Reset ()           { m_pbCurrent = m_pbCache ; }
        BOOL IsEmpty ()         { return CurCacheSize () == 0 ; }

        BOOL
        Append (
            IN  BYTE *  pb,
            IN  int     iLength
            )
        {
            if (iLength <= CacheRemaining ()) {
                CopyMemory (
                    m_pbCurrent,
                    pb,
                    iLength
                    ) ;

                m_pbCurrent += iLength ;
                return TRUE ;
            }
            else {
                return FALSE ;
            }
        }
} ;

template <int iCacheSize>
class TSizedDataCache :
    public CDataCache
{
    BYTE    m_pbCache [iCacheSize] ;

    public :

        TSizedDataCache (
            ) : CDataCache (
                    m_pbCache,
                    iCacheSize
                    ) {}
} ;

//  ----------------------------------------------------------------------------
//      lookup table
//  ----------------------------------------------------------------------------

template <class T>
class TLookupTableBase
{
    protected :

        struct LOOKUP_RECORD {
            DWORD   dwFilterIndex ;     //  index for the lookup record
            T       Object ;            //  storage
        } ;

    private :

        BYTE *          m_pFilter ;
        LOOKUP_RECORD * m_pLookup ;
        DWORD           m_cLookup ;
        DWORD           m_dwLookupSize ;
        DWORD           m_dwMax ;

    public :

        TLookupTableBase (
            IN  DWORD           dwLookupSize,
            IN  DWORD           dwMax,
            IN  BYTE *          pbFilter,
            IN  LOOKUP_RECORD * pLookup
            ) : m_dwLookupSize  (dwLookupSize),
                m_dwMax         (dwMax),
                m_cLookup       (0),
                m_pFilter       (pbFilter),
                m_pLookup       (pLookup)
        {
            ASSERT (dwMax <= MAXBYTE) ;

            ZeroMemory (m_pFilter, m_dwLookupSize * sizeof BYTE) ;
            ZeroMemory (m_pLookup, m_dwMax * sizeof LOOKUP_RECORD) ;
        }

        ~TLookupTableBase (
            )
        {
            ASSERT (m_cLookup == 0) ;
        }

        HRESULT
        Add (
            IN  DWORD   dwId,
            IN  T       t
            )
        {
            ASSERT (dwId < m_dwLookupSize) ;
            ASSERT (Exists (dwId) == FALSE) ;

            if (m_cLookup < m_dwMax) {
                //  set the indirect fields up
                m_pLookup [m_cLookup].Object        = t ;
                m_pLookup [m_cLookup].dwFilterIndex = dwId ;

                //  and the  filter
                m_pFilter [dwId] = (BYTE) (m_cLookup + 1) ;  //  1-based index; 0 means there's no  Lookup

                //  one more  Lookup
                m_cLookup++ ;

                //  success
                return S_OK ;
            }
            else {
                //  no more room left
                return E_FAIL ;
            }
        }

        T
        Remove (
            IN  DWORD   dwId
            )
        {
            T       tRet ;
            DWORD   RemoveIndex ;

            if (Exists (dwId)) {
                //  save off the index of the Lookup we are deleting
                RemoveIndex = m_pFilter [dwId] - 1 ;

                //  get a pointer to the context
                tRet = Get (dwId) ;

                //  erase the Lookupping
                m_pFilter [dwId] = 0 ;

                //  -------------------------------------------------------------------
                //  we want all the entries in m_pLookup to be densely packed,
                //  so we fill the slot we just opened, by moving the last entry into
                //  it

                //  only copy if we didn't remove the last one
                if (RemoveIndex < m_cLookup - 1) {

                    //  move the last  Lookup down (m_cLookup indexes the next
                    //  slot slated to be filled, so we subtract 1)
                    m_pLookup [RemoveIndex].Object        = m_pLookup [m_cLookup - 1].Object ;
                    m_pLookup [RemoveIndex].dwFilterIndex = m_pLookup [m_cLookup - 1].dwFilterIndex ;

                    //  update the filter to the new index (1-based)
                    m_pFilter [m_pLookup [RemoveIndex].dwFilterIndex] = (BYTE) (RemoveIndex + 1) ;
                }

                //  last, update the counter/index
                m_cLookup-- ;

                return tRet ;
            }
            else {
                return 0 ;
            }
        }

        BOOL
        Exists (
            IN  DWORD   dwId
            )
        {
            ASSERT (dwId < m_dwLookupSize) ;
            return m_pFilter [dwId] != 0 ;
        }

        T
        Get (
            IN  DWORD   dwId
            )
        {
            return Exists (dwId) ? m_pLookup [m_pFilter [dwId] - 1].Object : 0 ;
        }

        T
        operator [] (
            IN  DWORD   dwId
            )
        {
            return Get (dwId) ;
        }

        T
        GetIndexed (
            IN  DWORD   dwIndex
            )
        //  returns the dwIndex (0-based) object, or NULL if dwIndex is beyond
        //  the scope of what's in the table
        {
            if (dwIndex < m_cLookup) {
                return m_pLookup [dwIndex].Object ;
            }
            else {
                return NULL ;
            }
        }
} ;

template <
    DWORD   dwLookupSize,
    DWORD   dwMax,
    class   T
    >
class TLookupTable :
    public TLookupTableBase <T>
{
    BYTE            m_Filter [dwLookupSize] ;
    LOOKUP_RECORD   m_Lookup [dwMax] ;

    public :

        TLookupTable (
            ) : TLookupTableBase <T> (
                    dwLookupSize,
                    dwMax,
                    m_Filter,
                    m_Lookup
                    ) {}
} ;

//  ----------------------------------------------------------------------------
//  ObjectPool
//
//  non-serialized object pool
//  ----------------------------------------------------------------------------

template <class T,
          DWORD dwAllocationQuantum = 5
          >
class ObjectPool
{
    template <class T>
    struct CONTAINER
    {
        LIST_ENTRY  ListEntry ;
        DWORD       dwIndex ;
        T           Object ;

        static
        CONTAINER <T> *
        RecoverContainer (
            IN  T * pObject
            )
        {
            CONTAINER <T> * pContainer ;
            pContainer = CONTAINING_RECORD (pObject, CONTAINER <T>, Object) ;
            return pContainer ;
        }
    } ;

    template <class T>
    struct ALLOCATION_UNIT {
        LIST_ENTRY      ListEntry ;
        DWORD           dwInUseCount ;
        CONTAINER <T>   Container [dwAllocationQuantum] ;
    } ;

    LIST_ENTRY          m_AllocationUnits ;
    LIST_ENTRY          m_FreeList ;
    LIST_ENTRY          m_InUseList ;
    DWORD               m_dwTotalFreeCount ;

    ALLOCATION_UNIT <T> *
    GetOwningAllocationUnit_ (
        IN  CONTAINER <T> * pContainer
        )
    {
        ALLOCATION_UNIT <T> * pAllocationUnit ;

        pAllocationUnit = CONTAINING_RECORD (pContainer, ALLOCATION_UNIT <T>, Container [pContainer -> dwIndex]) ;
        return pAllocationUnit ;
    }

    void
    InitializeAllocationUnit_ (
        IN  ALLOCATION_UNIT <T> *   pNewAllocationUnit
        )
    {
        DWORD   i ;

        for (i = 0; i < dwAllocationQuantum; i++) {
            pNewAllocationUnit -> Container [i].dwIndex = i ;
            InsertHeadList (& m_FreeList, & (pNewAllocationUnit -> Container [i].ListEntry)) ;
            m_dwTotalFreeCount++ ;
        }

        InsertHeadList (& m_AllocationUnits, & (pNewAllocationUnit -> ListEntry)) ;

        pNewAllocationUnit -> dwInUseCount = 0 ;
    }

    void
    MaybeRecycleAllocationUnit_ (
        IN  ALLOCATION_UNIT <T> *   pAllocationUnit
        )
    {
        DWORD   i ;

        if (pAllocationUnit -> dwInUseCount == 0 &&
            m_dwTotalFreeCount > dwAllocationQuantum) {

            for (i = 0; i < dwAllocationQuantum; i++) {
                FreeListPop_ (& (pAllocationUnit -> Container [i])) ;
            }

            RemoveEntryList (& (pAllocationUnit -> ListEntry)) ;

            delete pAllocationUnit ;
        }
    }

    void
    FreeListPush_ (
        IN  CONTAINER <T> * pContainer
        )
    {
        InsertHeadList (& m_FreeList, & (pContainer -> ListEntry)) ;
        m_dwTotalFreeCount++ ;
    }

    void
    FreeListPop_ (
        IN  CONTAINER <T> * pContainer
        )
    {
        RemoveEntryList (& (pContainer -> ListEntry)) ;
        m_dwTotalFreeCount-- ;
    }

    CONTAINER <T> *
    FreeListPop_ (
        )
    {
        LIST_ENTRY *    pListEntry ;
        CONTAINER <T> * pContainer ;

        if (IsListEmpty (& m_FreeList) == FALSE) {
            pListEntry = RemoveHeadList (& m_FreeList) ;
            m_dwTotalFreeCount-- ;

            pContainer = CONTAINING_RECORD (pListEntry, CONTAINER <T>, ListEntry) ;
            return pContainer ;
        }
        else {
            return NULL ;
        }
    }

    void
    InUseListPop_ (
        IN  CONTAINER <T> * pContainer
        )
    {
        RemoveEntryList (& pContainer -> ListEntry) ;
    }

    void
    InUseListPush_ (
        IN  CONTAINER <T> * pContainer
        )
    {
        InsertHeadList (& m_InUseList, & (pContainer -> ListEntry)) ;
    }

    public :

        ObjectPool (
            ) : m_dwTotalFreeCount (0)
        {
            InitializeListHead (& m_AllocationUnits) ;
            InitializeListHead (& m_FreeList) ;
            InitializeListHead (& m_InUseList) ;
        }

        ~ObjectPool (
            )
        {
            ALLOCATION_UNIT <T> *   pAllocationUnit ;
            LIST_ENTRY *            pListEntry ;

            while (IsListEmpty (& m_AllocationUnits) == FALSE) {
                pListEntry = RemoveHeadList (& m_AllocationUnits) ;
                pAllocationUnit = CONTAINING_RECORD (pListEntry, ALLOCATION_UNIT <T>, ListEntry) ;
                delete pAllocationUnit ;
            }
        }

        T *
        Get (
            )
        {
            ALLOCATION_UNIT <T> *   pAllocationUnit ;
            CONTAINER <T> *         pContainer ;

            pContainer = FreeListPop_ () ;
            if (pContainer == NULL) {

                pAllocationUnit = new ALLOCATION_UNIT <T> ;
                if (pAllocationUnit == NULL) {
                    return NULL ;
                }

                InitializeAllocationUnit_ (pAllocationUnit) ;
                ASSERT (IsListEmpty (& m_FreeList) == FALSE) ;

                pContainer = FreeListPop_ () ;
            }

            ASSERT (pContainer) ;

            GetOwningAllocationUnit_ (pContainer) -> dwInUseCount++ ;
            InUseListPush_ (pContainer) ;

            return & (pContainer -> Object) ;
        }

        void
        Recycle (
            IN  T * pObject
            )
        {
            CONTAINER <T> *         pContainer ;
            ALLOCATION_UNIT <T> *   pAllocationUnit ;

            pContainer = CONTAINER <T>::RecoverContainer (pObject) ;

            InUseListPop_ (pContainer) ;
            FreeListPush_ (pContainer) ;

            pAllocationUnit = GetOwningAllocationUnit_ (pContainer) ;
            pAllocationUnit -> dwInUseCount-- ;

            MaybeRecycleAllocationUnit_ (pAllocationUnit) ;
        }
} ;

#ifdef _DEBUG
#define DEBUG_ONLY(op)  { op ; }
#else
#define DEBUG_ONLY(op)
#endif  //  _DEBUG

#define OnList(Entry)    \
    ((Entry)->Flink != NULL && (Entry)->Blink != NULL)

#define NotOnList(Entry)   \
    (OnList(Entry) == FALSE)

#define NullOutListEntry(Entry)    {\
    (Entry)->Flink = (Entry)->Blink = NULL ; \
    }

//  ---------------------------------------------------------------------------
//      TGenericMap
//  ---------------------------------------------------------------------------

template <
    class T,                            //  objects to store in this map
    class K,                            //  hash key type
    BOOL  fDuplicatesAllowed,           //  TRUE/FALSE if duplicates are allowed
    int   iAllocationUnitCount,         //  allocation quantum
    int   ulTableSize                   //  table size; must be prime
    >
class TGenericMap
/*++
    fixed size hash table; very simple
--*/
{
    /*++

      2      3      5      7     11     13     17     19     23     29
     31     37     41     43     47     53     59     61     67     71
     73     79     83     89     97    101    103    107    109    113
    127    131    137    139    149    151    157    163    167    173
    179    181    191    193    197    199    211    223    227    229
    233    239    241    251    257    263    269    271    277    281
    283    293    307    311    313    317    331    337    347    349
    353    359    367    373    379    383    389    397    401    409
    419    421    431    433    439    443    449    457    461    463
    467    479    487    491    499    503    509    521    523    541
    547    557    563    569    571    577    587    593    599    601
    607    613    617    619    631    641    643    647    653    659
    661    673    677    683    691    701    709    719    727    733
    739    743    751    757    761    769    773    787    797    809
    811    821    823    827    829    839    853    857    859    863
    877    881    883    887    907    911    919    929    937    941
    947    953    967    971    977    983    991    997   1009   1013

    --*/

    //  this structure references 1 entry
    struct TABLE_ENTRY {
        K           HashKey ;               //  hash key (hashed to get index)
        T           Object ;                //  object
        int         iAllocUnitIndex ;      //  index in the allocation unit
        LIST_ENTRY  ListEntry ;             //  listentry for in-use or free list
        LIST_ENTRY  HashList ;              //  list of TABLE_ENTRY with a common hash, or that are empty
    } ;

    //  this structure references a list of TABLE_ENTRYs, each of which
    //  hashes to the same value
    struct HASH_BUCKET {
        LIST_ENTRY  HashListHead ;
    } ;

    ObjectPool <TABLE_ENTRY, iAllocationUnitCount> m_TableEntryPool ;

    HASH_BUCKET                     m_Table [ulTableSize] ;     //  table headers
    LIST_ENTRY                      m_EntryList ;               //  table entries in use
    CRITICAL_SECTION                m_crt ;                     //  crit sect for the lock

    void    Lock_ ()                { EnterCriticalSection (& m_crt) ; }
    void    Unlock_ ()              { LeaveCriticalSection (& m_crt) ; }
    BOOL    NoDuplicatesAllowed_ () { return fDuplicatesAllowed == FALSE ; }

    void
    HashListsPush_ (
        IN  ULONG           ulHashValue,
        IN  TABLE_ENTRY *   pTableEntry
        )
    {
        ASSERT (ulHashValue < ulTableSize) ;

        InsertHeadList (& (m_Table [ulHashValue].HashListHead), & (pTableEntry -> HashList)) ;
        InsertTailList (& m_EntryList, & (pTableEntry -> ListEntry)) ;
    }

    void
    HashListsPop_ (
        IN  TABLE_ENTRY *   pTableEntry
        )
    {
        RemoveEntryList (& (pTableEntry -> HashList)) ;
        RemoveEntryList (& (pTableEntry -> ListEntry)) ;
    }

    TABLE_ENTRY *
    FindInHashChain_ (
        IN  K               HashKey,                //  search for
        IN  LIST_ENTRY *    pListStartInclusive,    //  check this one
        IN  LIST_ENTRY *    pListStopExclusive      //  up to, but not including this one
        )
    //  if pListStartInclusive == pListStopExclusive, nothing is checked
    {
        TABLE_ENTRY *   pCurTableEntry ;
        TABLE_ENTRY *   pRetTableEntry ;
        LIST_ENTRY *    pListEntry ;

        pRetTableEntry = NULL ;

        for (pListEntry = pListStartInclusive ;
             pListEntry != pListStopExclusive ;
             pListEntry = pListEntry -> Flink) {

            pCurTableEntry = CONTAINING_RECORD (pListEntry, TABLE_ENTRY, HashList) ;
            if (pCurTableEntry -> HashKey == HashKey) {
                //  found a match
                pRetTableEntry = pCurTableEntry ;
                break ;
            }
        }

        return pRetTableEntry ;
    }

    TABLE_ENTRY *
    FindHashkey_ (
        IN  K       HashKey,
        IN  ULONG   ulHashValue
        )
    //  searches an entire list of the specified hashkey
    {
        return FindInHashChain_ (
                    HashKey,
                    m_Table [ulHashValue].HashListHead.Flink,   //  start
                    & (m_Table [ulHashValue].HashListHead)      //  end point
                    ) ;
    }

    TABLE_ENTRY *
    FindObject_ (
        IN  T       Object,
        IN  K       HashKey,
        IN  ULONG   ulHashValue
        )
    {
        TABLE_ENTRY *   pCurTableEntry ;
        LIST_ENTRY *    pTableHashListHead ;
        TABLE_ENTRY *   pRetTableEntry ;

        pRetTableEntry = NULL ;

        pTableHashListHead = & (m_Table [ulHashValue].HashListHead) ;

        pCurTableEntry = FindInHashChain_ (
                            HashKey,                        //  look for
                            pTableHashListHead -> Flink,    //  starting
                            pTableHashListHead              //  up to
                            ) ;

        while (pCurTableEntry) {

            ASSERT (pCurTableEntry -> HashKey == HashKey) ;

            if (pCurTableEntry -> Object == Object) {
                pRetTableEntry = pCurTableEntry ;
                break ;
            }

            //  find the next with same hashkey
            pCurTableEntry = FindInHashChain_ (
                                HashKey,                            //  look for
                                pCurTableEntry -> HashList.Flink,   //  starting with next
                                pTableHashListHead                  //  up to
                                ) ;
            }

        return pRetTableEntry ;
    }

    public :

        TGenericMap (
            )
        {
            ULONG   i ;

            InitializeCriticalSection (& m_crt) ;

            InitializeListHead (& m_EntryList) ;

            for (i = 0; i < ulTableSize; i++) {
                InitializeListHead (& (m_Table [i].HashListHead)) ;
            }
        }

        virtual
        ~TGenericMap (
            )
        {
            DeleteCriticalSection (& m_crt) ;
        }

        //  --------------------------------------------------------------------

        //  converts hashkey to a well-distributed ULONG value
        virtual ULONG   Value (IN K HashKey) = 0 ;

        //  --------------------------------------------------------------------

        ULONG
        Hash (
            IN  K HashKey
            )
        {
            return Value (HashKey) % ulTableSize ;
        }

        HRESULT
        Store (
            IN  T   Object,
            IN  K   HashKey
            )
        {
            ULONG           ulHashValue ;
            TABLE_ENTRY *   pTableEntry ;
            HRESULT         hr ;

            ulHashValue = Hash (HashKey) ;

            Lock_ () ;

            if (NoDuplicatesAllowed_ () &&
                FindHashkey_ (HashKey, ulHashValue) != NULL) {

                //  cannot have duplicates & one was found
                hr = E_FAIL ;
            }
            else {
                pTableEntry = m_TableEntryPool.Get () ;
                if (pTableEntry) {

                    pTableEntry -> Object   = Object ;
                    pTableEntry -> HashKey  = HashKey ;

                    HashListsPush_ (
                        ulHashValue,
                        pTableEntry
                        ) ;

                    //  success
                    hr = S_OK ;
                }
                else {
                    //  failure
                    hr = E_OUTOFMEMORY ;
                }
            }

            Unlock_ () ;

            return hr ;
        }

        HRESULT
        Find (
            IN  K   HashKey,
            OUT T * pObject
            )
        {
            ULONG           ulHashValue ;
            TABLE_ENTRY *   pTableEntry ;
            HRESULT         hr ;

            ASSERT (pObject) ;

            ulHashValue = Hash (HashKey) ;

            Lock_ () ;

            pTableEntry = FindHashkey_ (HashKey, ulHashValue) ;
            if (pTableEntry) {
                //  found
                * pObject = pTableEntry -> Object ;

                hr = S_OK ;
            }
            else {
                //  not found
                hr = E_FAIL ;
            }

            Unlock_ () ;

            return hr ;
        }

        HRESULT
        FindSpecific (
            IN  T   Object,
            IN  K   HashKey
            )
        {
            ULONG           ulHashValue ;
            TABLE_ENTRY *   pTableEntry ;
            HRESULT         hr ;

            ulHashValue = Hash (HashKey) ;

            Lock_ () ;

            pTableEntry = FindObject_ (Object, HashKey, ulHashValue) ;
            if (pTableEntry) {
                //  success
                hr = S_OK ;
            }
            else {
                //  specific object was not found
                hr = E_FAIL ;
            }

            Unlock_ () ;

            return hr ;
        }

        BOOL
        Exists (
            IN  K   HashKey
            )
        {
            HRESULT hr ;
            T       tTmp ;

            hr = Find (HashKey, & tTmp) ;

            return SUCCEEDED (hr) ;
        }

        HRESULT
        Remove (
            IN  K   HashKey,
            OUT T * pObject
            )
        {
            ULONG           ulHashValue ;
            TABLE_ENTRY *   pTableEntry ;
            HRESULT         hr ;

            ASSERT (pObject) ;

            ulHashValue = Hash (HashKey) ;

            Lock_ () ;

            pTableEntry = FindHashkey_ (HashKey, ulHashValue) ;
            if (pTableEntry) {
                * pObject = pTableEntry -> Object ;

                HashListsPop_ (pTableEntry) ;
                m_TableEntryPool.Recycle (pTableEntry) ;

                //  success
                hr = S_OK ;
            }
            else {
                //  nothing was found with the specified hashkey
                hr = E_FAIL ;
            }

            Unlock_ () ;

            return hr ;
        }

        HRESULT
        RemoveSpecific (
            IN  T   Object,
            IN  K   HashKey
            )
        {
            ULONG           ulHashValue ;
            TABLE_ENTRY *   pTableEntry ;
            HRESULT         hr ;

            ulHashValue = Hash (HashKey) ;

            Lock_ () ;

            pTableEntry = FindObject_ (Object, HashKey, ulHashValue) ;
            if (pTableEntry) {
                HashListsPop_ (pTableEntry) ;
                m_TableEntryPool.Recycle (pTableEntry) ;

                //  success
                hr = S_OK ;
            }
            else {
                //  not found
                hr = E_FAIL ;
            }

            Unlock_ () ;

            return hr ;
        }

        void
        Clear (
            )
        {
            T   tTmp ;

            Lock_ () ;
            while (SUCCEEDED (RemoveFirst (& tTmp))) ;
            Unlock_ () ;
        }

        BOOL
        IsEmpty (
            )
        {
            return IsListEmpty (& m_EntryList) ;
        }

        HRESULT
        RemoveFirst (
            OUT T *     pObject
            )
        {
            HRESULT         hr ;
            TABLE_ENTRY *   pTableEntry ;
            LIST_ENTRY *    pListEntry ;

            Lock_ () ;

            if (IsListEmpty (& m_EntryList) == FALSE) {
                pListEntry = m_EntryList.Flink ;
                pTableEntry = CONTAINING_RECORD (pListEntry, TABLE_ENTRY, ListEntry) ;

                * pObject = pTableEntry -> Object ;

                HashListsPop_ (pTableEntry ) ;
                m_TableEntryPool.Recycle (pTableEntry) ;

                hr = S_OK ;
            }
            else {
                hr = E_FAIL ;
            }

            Unlock_ () ;

            return hr ;
        }
} ;

//  ---------------------------------------------------------------------------
//      TListEntryBufferManager
//  ---------------------------------------------------------------------------

template <class T>
struct LIST_ENTRY_CONTAINER {
    LIST_ENTRY  ListEntry ;
    T           Payload ;
    LONG        lRef ;
} ;

template <class T, DWORD dwMaxBufferPool>
class TListEntryContainerPool
/*++
    This template provides a simple pool of LIST_ENTRY_CONTAINER structures.
    The maximum depth of the pool is specified in the dwMaxBufferPool
    template parameter.  The type of value that is held in the returned
    LIST_ENTRY_CONTAINER structs is specified by the template parameter
    "class T".

    When the pool is empty, new structs are allocated from the heap using
    "new".  When the a struct is recycled and the pool is full, its resources
    are freed via "delete".

    When a struct is requested, the pool is always checked first.

    When a struct has been passed out, there are NO references to it in
    this template class.  It must be returned before the class is destroyed
    in order for the memory not be leaked.  There is an outstanding count
    that is kept.  Debug builds will ASSERT when the class is destroyed with
    outstanding structs.

    After a struct is recycled, it must not be accessed again by the caller.
    Its resources may be returned to the system, or the ListEntry member will
    be used for the struct pool.

    When a struct has been obtained, the ListEntry field is available for any
    use that is required, until the struct is recycled.
--*/
{
    LIST_ENTRY          m_BufferPoolHead ;          //  head pointer to buffer pool
    DWORD               m_cCurrentBufferPool ;      //  depth of buffer pool currently
    DWORD               m_cOutstandingBuffers ;     //  count of outstanding buffers
    CRITICAL_SECTION    m_crt ;                     //  class lock

    void Lock_ ()       { EnterCriticalSection (& m_crt) ; }
    void Unlock_ ()     { LeaveCriticalSection (& m_crt) ; }

    public :

        TListEntryContainerPool (
            ) : m_cCurrentBufferPool    (0),
                m_cOutstandingBuffers   (0)
        {
            TRACE_CONSTRUCTOR (TEXT ("TListEntryContainerPool")) ;

            InitializeListHead (& m_BufferPoolHead) ;
            InitializeCriticalSection (& m_crt) ;
        }

        ~TListEntryContainerPool (
            )
        {
            LIST_ENTRY *                pListEntry ;
            LIST_ENTRY_CONTAINER <T> *  pContainer ;

            TRACE_DESTRUCTOR (TEXT ("TListEntryContainerPool")) ;

            //  should not be getting destroyed as long as there are outstanding buffers
            ASSERT (m_cOutstandingBuffers == 0) ;

            while (m_cCurrentBufferPool > 0) {

                ASSERT (IsListEmpty (& m_BufferPoolHead) == FALSE) ;

                pListEntry = RemoveHeadList (& m_BufferPoolHead) ;
                pContainer = CONTAINING_RECORD (pListEntry, LIST_ENTRY_CONTAINER <T>, ListEntry) ;

                delete pContainer ;

                m_cCurrentBufferPool-- ;
            }

            ASSERT (IsListEmpty (& m_BufferPoolHead) == TRUE) ;

            DeleteCriticalSection (& m_crt) ;
        }

        HRESULT
        Get (
            OUT LIST_ENTRY_CONTAINER <T> ** ppListEntryContainer
            )
        {
            LIST_ENTRY *    pListEntry ;

            Lock_ () ;

            if (m_cCurrentBufferPool > 0) {

                ASSERT (IsListEmpty (& m_BufferPoolHead) == FALSE) ;

                //  just pull one off the buffer pool

                pListEntry              = RemoveHeadList (& m_BufferPoolHead) ;
                * ppListEntryContainer  = CONTAINING_RECORD (pListEntry, LIST_ENTRY_CONTAINER <T>, ListEntry) ;

                m_cCurrentBufferPool-- ;
            }
            else {
                //  need to allocate a new one
                * ppListEntryContainer = new LIST_ENTRY_CONTAINER <T> ;
            }

            Unlock_ () ;

            if (* ppListEntryContainer == NULL) {

                //  failure
                return E_OUTOFMEMORY ;
            }

            //  1 more outstanding buffer
            m_cOutstandingBuffers++ ;

            //  success
            return S_OK ;
        }

        HRESULT
        Recycle (
            IN  LIST_ENTRY_CONTAINER <T> *  pListEntryContainer
            )
        {
            Lock_ () ;

            //  decide if we're going to free the resource or just recycle to the
            //  buffer pool
            if (m_cCurrentBufferPool < dwMaxBufferPool) {

                //  we have room in the buffer pool

                InsertHeadList (& m_BufferPoolHead, & pListEntryContainer -> ListEntry) ;
                m_cCurrentBufferPool++ ;
            }
            else {
                //  free the resource; our buffer pool is full

                delete pListEntryContainer ;
            }

            m_cOutstandingBuffers-- ;

            Unlock_ () ;

            return S_OK ;
        }
} ;

//  ---------------------------------------------------------------------------
//  generic unsorted dense vector
//  ---------------------------------------------------------------------------

template <class T>
class TSimpleVector
/*++
    simple dense vector template;
    allocates from a specified heap or the process heap (default);
    grows and shrinks (reallocates) as required, as values are added and
      deleted;
    does not sort in any manner;
    can add member randomly; appending is most efficient
    can remove members randomly; deleted from end is most efficient
--*/
{
    //  default values
    enum {
        DEF_INITIAL_SIZE        = 4,    //  initialize size
        DEF_RESIZE_MULTIPLIER   = 2     //  multiplier/divisor of size
    } ;

    T *                 m_pVector ;                 //  vector of objects
    DWORD               m_cElements ;               //  number of elements; <= m_dwMaxSize
    DWORD               m_dwResizeMultiplier ;      //  resize/shrink multiplier/divisor
    DWORD               m_dwInitialSize ;           //  first allocation
    HANDLE              m_hHeap ;                   //  heap handle (not duplicated !)
    DWORD               m_dwMaxSize ;               //  current max size of vector
    CRITICAL_SECTION    m_crt ;                     //  used in the Lock/Unlock methods

    void
    MaybeGrow_ (
        )
    /*++
    --*/
    {
        T *     pNewVector ;
        DWORD   dwNewSize ;

        ASSERT (m_hHeap) ;

        //  if we're maxed out, grow the vector
        if (m_cElements == m_dwMaxSize) {

            if (m_pVector) {
                //  we've been called before, time to realloc

                ASSERT (m_dwMaxSize > 0) ;
                dwNewSize = m_dwResizeMultiplier * m_dwMaxSize ;

                pNewVector = reinterpret_cast <T *> (HeapReAlloc (
                                                        m_hHeap,
                                                        HEAP_GENERATE_EXCEPTIONS,
                                                        m_pVector,
                                                        dwNewSize * sizeof T
                                                        )) ;
            }
            else {
                //  this is the first time we are allocating
                dwNewSize = m_dwInitialSize ;

                pNewVector = reinterpret_cast <T *> (HeapAlloc (
                                                        m_hHeap,
                                                        HEAP_GENERATE_EXCEPTIONS,
                                                        dwNewSize * sizeof T
                                                        )) ;
            }

            //  specifying HEAP_GENERATE_EXCEPTIONS in the above calls ensures
            //  that the system will have raised an exception if there's
            //  insufficient memory
            ASSERT (pNewVector) ;

            //  reset array pointer and set the max size
            m_pVector = pNewVector ;
            m_dwMaxSize = dwNewSize ;
        }

        return ;
    }

    void
    MaybeShrink_ (
        )
    {
        T *     pNewVector ;
        DWORD   dwNewSize ;

        ASSERT (m_pVector) ;
        ASSERT (m_dwMaxSize > 0) ;
        ASSERT (m_dwResizeMultiplier > 0) ;
        ASSERT (m_hHeap) ;

        //  if we fall below the threshold, but are bigger than smallest size,
        //  try to realloc
        if (m_cElements >= m_dwInitialSize &&
            m_cElements <= (m_dwMaxSize / m_dwResizeMultiplier)) {

            dwNewSize = m_dwMaxSize / m_dwResizeMultiplier ;

            pNewVector = reinterpret_cast <T *> (HeapReAlloc (
                                                    m_hHeap,
                                                    HEAP_GENERATE_EXCEPTIONS,
                                                    m_pVector,
                                                    dwNewSize * sizeof T
                                                    )) ;

            //  specifying HEAP_GENERATE_EXCEPTIONS in the above calls ensures
            //  that the system will have raised an exception if there's
            //  insufficient memory
            ASSERT (pNewVector) ;

            //  reset array pointer and set the max size
            m_dwMaxSize = dwNewSize ;
            m_pVector = pNewVector ;
        }

        return ;
    }

    public :

        TSimpleVector (
            IN  HANDLE      hHeap               = NULL,                     //  could specify the heap handle
            IN  DWORD       dwInitialSize       = DEF_INITIAL_SIZE,         //  initial entries allocation
            IN  DWORD       dwResizeMultiplier  = DEF_RESIZE_MULTIPLIER     //  resize multiplier/divisor
            ) : m_pVector               (NULL),
                m_dwResizeMultiplier    (dwResizeMultiplier),
                m_dwInitialSize         (dwInitialSize),
                m_dwMaxSize             (0),
                m_cElements             (0),
                m_hHeap                 (hHeap)
        {
            //  if no heap was specified, grab the process' heap handle
            if (m_hHeap == NULL) {
                m_hHeap = GetProcessHeap () ;
            }

            InitializeCriticalSection (& m_crt) ;

            ASSERT (m_hHeap) ;
            ASSERT (dwResizeMultiplier > 0) ;
            ASSERT (dwInitialSize > 0) ;
        }

        ~TSimpleVector (
            )
        {
            //  there's nothing in the docs that says m_pVector can be NULL
            //  when calling HeapFree..
            if (m_pVector) {
                ASSERT (m_hHeap != NULL) ;
                HeapFree (
                    m_hHeap,
                    NULL,
                    m_pVector
                    ) ;
            }

            DeleteCriticalSection (& m_crt) ;
        }

        _inline
        const
        DWORD
        GetCount (
            )
        //  returns the number of elements currently in the vector
        {
            return m_cElements ;
        }

        __inline
        T *
        const
        GetVector (
            )
        //  returns the vector itself; caller then has direct access to the
        //  memory
        {
            return m_pVector ;
        }

        __inline
        void
        GetVector (
            OUT T **    ppT,
            OUT DWORD * pcElements
            )
        {
            ASSERT (ppT) ;
            ASSERT (pcElements) ;

            * ppT = m_pVector ;
            * pcElements = m_cElements ;
        }

        T
        operator [] (
            IN  DWORD   dwIndex
            )
        {
            T       t ;
            HRESULT hr ;

            hr = Get (dwIndex, & t) ;
            if (SUCCEEDED (hr)) {
                return t ;
            }
            else {
                return 0 ;
            }
        }

        __inline
        void
        Lock (
            )
        {
            EnterCriticalSection (& m_crt) ;
        }

        __inline
        void
        Unlock (
            )
        {
            LeaveCriticalSection (& m_crt) ;
        }

        __inline
        HRESULT
        const
        Get (
            IN  DWORD   dwIndex,
            OUT T *     pValue
            )
        //  returns the dwIndex'th element in the vector
        {
            ASSERT (pValue) ;

            if (dwIndex >= m_cElements) {
                return E_INVALIDARG ;
            }

            * pValue = m_pVector [dwIndex] ;

            return S_OK ;
        }

        HRESULT
        Append (
            IN  T       Value,
            OUT DWORD * pcTotalElements = NULL
            )
        /*++
            Purpose:

                Appends a new value to the end of the vector.  Optionally returns
                the number of elements in the vector.

            Parameters:

                Value               new item

                pcTotalElements     optional OUT parameter to return the number
                                      of elements in the vector AFTER the call;
                                      valid only if the call is successfull

            Return Values:

                S_OK                success
                E_OUTOFMEMORY       the vector is maxed and the memory reallocation
                                      failed

        --*/
        {
            return Insert (m_cElements,
                           Value,
                           pcTotalElements) ;
        }

        HRESULT
        Insert (
            IN  DWORD   dwIndex,
            IN  T       Value,
            OUT DWORD * pcTotalElements = NULL
            )
        /*++
            Purpose:

                Insert a new value at the specified Index

            Parameters:

                dwIndex             0-based index to the position where the
                                      new item should be inserted

                Value               new item

                pcTotalElements     optional OUT parameter to return the number
                                      of elements in the vector after the call;
                                      valid only if successfull

            Return Values:

                S_OK                success

                E_OUTOFMEMORY       the vector is maxed and the memory
                                      reallocation failed

                E_INVALIDARG        the specified index is out of range of the
                                      current contents of the vector; the min
                                      valid value is 0, and the max valid value
                                      is after the last elemtn

        --*/
        {
            //  make sure we're not going to insert off the end of the vector;
            //  m_cElements is the max valid index for a new element (in which
            //  case we are appending)
            if (dwIndex > m_cElements) {
                return E_INVALIDARG ;
            }

            //  if we didn't get this when we instantiated, we try again
            if (m_hHeap == NULL) {
                m_hHeap = GetProcessHeap () ;
                if (m_hHeap == NULL) {
                    return E_OUTOFMEMORY ;
                }
            }

            //  frame this in a try-except block to catch out-of-memory
            //  exceptions
            __try {
                MaybeGrow_ () ;
            }
            __except (GetExceptionCode () == STATUS_NO_MEMORY ||
                      GetExceptionCode () == STATUS_ACCESS_VIOLATION ?
                      EXCEPTION_EXECUTE_HANDLER :
                      EXCEPTION_CONTINUE_SEARCH) {

                return E_OUTOFMEMORY ;
            }

            //  the only failure to MaybeGrow_ is a win32 exception, so if we
            //  get to here, we've got the memory we need
            ASSERT (m_cElements < m_dwMaxSize) ;
            ASSERT (m_pVector) ;

            //  if there are elements to move, and we're not just appending, move
            //  the remaining elements out to make room
            if (m_cElements > 0 &&
                dwIndex < m_cElements) {

                //  expand
                MoveMemory (
                    & m_pVector [dwIndex + 1],
                    & m_pVector [dwIndex],
                    (m_cElements - dwIndex) * sizeof T
                    ) ;
            }

            //  insert the new item
            m_pVector [dwIndex] = Value ;
            m_cElements++ ;

            //  if the caller wants to know size, set that now
            if (pcTotalElements) {
                * pcTotalElements = m_cElements ;
            }

            return S_OK ;
        }

        HRESULT
        Remove (
            IN  DWORD   dwIndex,
            OUT T *     pValue = NULL
            )
        /*++
            Purpose:

                Removes an item at the specified 0-based index.  Optionally returns
                the value in the [out] parameter.

            Parameters:

                dwIndex     0-based index

                pValue      optional pointer to a value to obtain what was removed

            Return Values:

                S_OK            success

                E_INVALIDARG    an out-of-range index was specified

        --*/
        {
            ASSERT (m_hHeap != NULL) ;

            //  dwIndex is 0-based
            if (dwIndex >= m_cElements) {
                return E_INVALIDARG ;
            }

            //  if caller wants to get the Remove'd value, set it now
            if (pValue) {
                * pValue = m_pVector [dwIndex] ;
            }

            //  compact the remaining elements, unless we're removing the last element
            //  check above ensures that subtracting 1 does not wrap
            if (dwIndex < m_cElements - 1) {

                //  compact
                MoveMemory (
                        & m_pVector [dwIndex],
                        & m_pVector [dwIndex + 1],
                        (m_cElements - 1 - dwIndex) * sizeof T
                        ) ;
            }

            m_cElements-- ;

            __try {
                MaybeShrink_ () ;
            }
            __except (GetExceptionCode () == STATUS_NO_MEMORY ||
                      GetExceptionCode () == STATUS_ACCESS_VIOLATION ?
                      EXCEPTION_EXECUTE_HANDLER :
                      EXCEPTION_CONTINUE_SEARCH) {

                //  fail silently; we still have the memory we had before
            }

            return S_OK ;
        }
} ;

//  ----------------------------------------------------------------------------
//  CTDynArray
//  ----------------------------------------------------------------------------

template <class T>
class CTDynArray
{
    //  FIFO: insert at "tail"; remove at "head"
    //  LIFO: insert at "top" remove at "top"

    enum {
        INIT_TABLE_SIZE = 5
    } ;

    T **    m_ppBlockTable ;
    LONG    m_lAllocatedTableSize ;
    LONG    m_lAllocatedBlocks ;
    LONG    m_lAllocQuantum ;
    LONG    m_lMaxArrayLen ;
    LONG    m_lCurArrayLen ;
    LONG    m_lLastInsertSlotIndex ;

    LONG AllocatedArrayLength_ ()           { return m_lAllocatedBlocks * m_lAllocQuantum ; }
    LONG TableIndex_ (IN LONG lArrayIndex)  { return lArrayIndex / m_lAllocQuantum ; }
    LONG BlockIndex_ (IN LONG lArrayIndex)  { return lArrayIndex % m_lAllocQuantum ; }

    LONG NextInsertSlotIndex_ ()
    {
        return (AllocatedArrayLength_ () > 0 ? (m_lLastInsertSlotIndex + m_lCurArrayLen) % AllocatedArrayLength_ () : 0) ;
    }

    LONG FIFO_HeadIndex_ ()
    {
        return m_lLastInsertSlotIndex ;
    }

    void FIFO_PopHead_ ()
    {
        ASSERT (m_lCurArrayLen > 0) ;
        m_lCurArrayLen-- ;
        m_lLastInsertSlotIndex = (m_lLastInsertSlotIndex + 1) % AllocatedArrayLength_ () ;
    }

    LONG LIFO_TopIndex_ ()
    {
        ASSERT (m_lCurArrayLen > 0) ;
        return (m_lLastInsertSlotIndex + m_lCurArrayLen - 1) % AllocatedArrayLength_ () ;
    }

    void LIFO_PopTop_ ()
    {
        ASSERT (m_lCurArrayLen > 0) ;
        m_lCurArrayLen-- ;
    }

    DWORD
    MaybeGrowTable_ (
        )
    {
        LONG    lNewSize ;
        T **    pptNew ;

        if (m_lAllocatedTableSize == m_lAllocatedBlocks) {
            //  need to allocate more table

            lNewSize = (m_lAllocatedTableSize > 0 ? m_lAllocatedTableSize * 2 : INIT_TABLE_SIZE) ;

            pptNew = AllocateTable_ (lNewSize) ;
            if (!pptNew) {
                return ERROR_NOT_ENOUGH_MEMORY ;
            }

            ZeroMemory (pptNew, lNewSize * sizeof (T *)) ;

            if (m_ppBlockTable) {
                ASSERT (m_lAllocatedTableSize > 0) ;
                CopyMemory (
                    pptNew,
                    m_ppBlockTable,
                    m_lAllocatedTableSize * sizeof (T *)
                    ) ;

                FreeTable_ (m_ppBlockTable) ;
            }

            m_ppBlockTable = pptNew ;
            m_lAllocatedTableSize = lNewSize ;
        }

        return NOERROR ;
    }

    T *
    Entry_ (
        IN  LONG    lIndex
        )
    {
        //  should not be asking if it's beyond
        ASSERT (lIndex < AllocatedArrayLength_ ()) ;

        ASSERT (TableIndex_ (lIndex) < m_lAllocatedTableSize) ;
        ASSERT (m_ppBlockTable [TableIndex_ (lIndex)]) ;

        return & m_ppBlockTable [TableIndex_ (lIndex)] [BlockIndex_ (lIndex)] ;
    }

    T
    Val_ (IN LONG lIndex)
    {
        return (* Entry_ (lIndex)) ;
    }

    DWORD
    Append_ (T tVal)
    {
        T *     ptNewBlock ;
        LONG    lNewBlockTableIndex ;
        DWORD   dw ;

        ASSERT (!ArrayMaxed ()) ;

        if ((NextInsertSlotIndex_ () == m_lLastInsertSlotIndex && m_lCurArrayLen > 0) ||
            AllocatedArrayLength_ () == 0) {

            //  table is full; need to allocate

            //  might need to extend the table to hold more blocks
            dw = MaybeGrowTable_ () ;
            if (dw != NOERROR) {
                return dw ;
            }

            ASSERT (m_lAllocatedTableSize > m_lAllocatedBlocks) ;

            //  allocate our new block
            ptNewBlock = AllocateBlock_ () ;
            if (!ptNewBlock) {
                return ERROR_NOT_ENOUGH_MEMORY ;
            }

            //  new block is inserted in table into OutSlotIndex's block; we'll
            //    then move out the OutSlotIndex
            lNewBlockTableIndex = TableIndex_ (m_lLastInsertSlotIndex) ;

            //  init the new block & make room for the new block (if there's
            //    something there now i.e. this is not our first time through)
            if (m_ppBlockTable [lNewBlockTableIndex]) {
                //  copy the contents of the block we're about to move out
                CopyMemory (
                    ptNewBlock,
                    m_ppBlockTable [lNewBlockTableIndex],
                    m_lAllocQuantum * sizeof T
                    ) ;

                //  shift the blocks that follow out
                MoveMemory (
                    & m_ppBlockTable [lNewBlockTableIndex + 1],
                    & m_ppBlockTable [lNewBlockTableIndex],
                    (m_lAllocatedBlocks - lNewBlockTableIndex) * sizeof (T *)
                    ) ;
            }

            //  insert into the table
            m_ppBlockTable [lNewBlockTableIndex] = ptNewBlock ;
            m_lAllocatedBlocks++ ;

            //  shift the OutSlot out, if this is not our first
            m_lLastInsertSlotIndex += (m_lAllocatedBlocks > 1 ? m_lAllocQuantum : 0) ;
        }

        //  append to tail
        (* Entry_ (NextInsertSlotIndex_ ())) = tVal ;
        m_lCurArrayLen++ ;

        return NOERROR ;
    }

    protected :

        T *
        AllocateBlock_ (
            )
        {
            return reinterpret_cast <T *> (malloc (m_lAllocQuantum * sizeof T)) ;
        }

        T **
        AllocateTable_ (
            IN  int iNumEntries
            )
        {
            return reinterpret_cast <T **> (malloc (iNumEntries * sizeof (T *))) ;
        }

        void
        FreeBlock_ (
            IN  T * pBlock
            )
        {
            free (pBlock) ;
        }

        void
        FreeTable_ (
            IN  T **    pptTable
            )
        {
            free (pptTable) ;
        }


        DWORD FIFOHeadVal_ (OUT T * pt)
        {
            DWORD   dw ;

            if (m_lCurArrayLen > 0) {
                (* pt) = Val_ (FIFO_HeadIndex_ ()) ;
                dw = NOERROR ;
            }
            else {
                dw = ERROR_GEN_FAILURE ;
            }

            return dw ;
        }

        DWORD PopFIFO_ (OUT T * pt)
        {
            DWORD   dw ;

            dw = FIFOHeadVal_ (pt) ;
            if (dw == NOERROR) {
                FIFO_PopHead_ () ;
            }

            return dw ;
        }

        DWORD LIFOTopVal_ (OUT T * pt)
        {
            DWORD   dw ;

            if (m_lCurArrayLen > 0) {
                (* pt) = Val_ (LIFO_TopIndex_ ()) ;
                dw = NOERROR ;
            }
            else {
                dw = ERROR_GEN_FAILURE ;
            }

            return dw ;
        }

        DWORD PopLIFO_ (OUT T * pt)
        {
            DWORD   dw ;

            dw = LIFOTopVal_ (pt) ;
            if (dw == NOERROR) {
                LIFO_PopTop_ () ;
            }

            return dw ;
        }

    public :

        CTDynArray (
            IN  LONG    lAllocQuantum,
            IN  LONG    lMaxArrayLen = LONG_MAX
            ) : m_lAllocQuantum         (lAllocQuantum),
                m_lAllocatedBlocks      (0),
                m_lAllocatedTableSize   (0),
                m_ppBlockTable          (NULL),
                m_lMaxArrayLen          (lMaxArrayLen),
                m_lCurArrayLen          (0),
                m_lLastInsertSlotIndex  (0) {}

        ~CTDynArray (
            )
        {
            LONG    l ;

            for (l = 0; l < m_lAllocatedBlocks; l++) {
                FreeBlock_ (m_ppBlockTable [l]) ;
            }

            FreeTable_ (m_ppBlockTable) ;
        }

        LONG Length ()      { return m_lCurArrayLen ; }
        BOOL ArrayMaxed ()  { return (m_lCurArrayLen < m_lMaxArrayLen ? FALSE : TRUE) ; }
        BOOL Empty ()       { return (Length () > 0 ? FALSE : TRUE) ; }
        void Reset ()       { m_lCurArrayLen = 0 ; }

        DWORD Push (IN T tVal)
        {
            DWORD   dw ;

            if (!ArrayMaxed ()) {
                dw = Append_ (tVal) ;
            }
            else {
                dw = ERROR_GEN_FAILURE ;
            }

            return dw ;
        }

        virtual
        DWORD
        Pop (
            OUT T * pt
            ) = 0 ;
} ;

//  ----------------------------------------------------------------------------
//  CTDynQueue
//  ----------------------------------------------------------------------------

template <class T>
class CTDynQueue :
    public CTDynArray <T>
{
    public :

        CTDynQueue (
            IN  LONG    lAllocQuantum,
            IN  LONG    lMaxQueueLen = LONG_MAX
            ) : CTDynArray <T> (lAllocQuantum,
                                lMaxQueueLen) {}

        virtual DWORD Pop (OUT T * pt)
        {
            return PopFIFO_ (pt) ;
        }

        DWORD Head (OUT T * pt)
        {
            return FIFOHeadVal_ (pt) ;
        }

        DWORD Tail (OUT T * pt)
        {
            return LIFOTopVal_ (pt) ;
        }
} ;

//  ----------------------------------------------------------------------------
//  CTDynStack
//  ----------------------------------------------------------------------------

template <class T>
class CTDynStack :
    public CTDynArray <T>
{
    public :

        CTDynStack (
            IN  LONG    lAllocQuantum,
            IN  LONG    lMaxQueueLen = LONG_MAX
            ) : CTDynArray <T> (lAllocQuantum,
                                lMaxQueueLen) {}

        virtual DWORD Pop (OUT T * pt)
        {
            return PopLIFO_ (pt) ;
        }

        DWORD Top (OUT T * pt)
        {
            return LIFOTopVal_ (pt) ;
        }
} ;

//  ---------------------------------------------------------------------------
//      CTMovingAverage
//  ---------------------------------------------------------------------------

template <class T>
class CTMovingAverage
{
    CTDynQueue <T>  m_EntryQueue ;
    T               m_Total ;
    LONG            m_lMaxWindowSize ;
    CCritSec        m_cs ;
    T               m_tCurAvg ;

    public :

        CTMovingAverage (
            IN  LONG lMaxWindowSize
            ) : m_EntryQueue        (lMaxWindowSize, lMaxWindowSize),
                m_lMaxWindowSize    (lMaxWindowSize),
                m_Total             (0) {}

        void    Reset ()        { m_EntryQueue.Empty () ; m_Total = 0 ; m_tCurAvg = 0 ; }
        DWORD   Entries ()      { return m_EntryQueue.Length () ; }
        T       Average ()      { return m_tCurAvg ; }

        DWORD
        NewEntry (
            IN  T   Val
            )
        {
            T           tHead ;
            CAutoLock   Lock (& m_cs) ;
            DWORD       dwRet ;

            if (m_EntryQueue.Length () == m_lMaxWindowSize) {
                m_EntryQueue.Pop (& tHead) ;
                m_Total -= tHead ;
            }

            dwRet = m_EntryQueue.Push (Val) ;
            if (dwRet == NOERROR) {
                m_Total += Val ;

                ASSERT (m_EntryQueue.Length ()) ;
                m_tCurAvg = m_Total / m_EntryQueue.Length () ;
            }

            return dwRet ;
        }

} ;

typedef int (__cdecl * PFN_QSORT_COMPARE) (const void *, const void *) ;

//  binary search of a vector; returns an index
template <class T>
HRESULT
BSearch (
    IN  TSimpleVector <T> * pVector,
    IN  T                   Search,
    IN  PFN_QSORT_COMPARE   pfnCompare,
    OUT DWORD *             pdwIndex
    )
{
    T *     p ;
    DWORD   c ;
    int     index, start, end, r ;

    pVector -> GetVector (& p, & c) ;
    if (p) {
        ASSERT (c > 0) ;

        start = 0 ;
        end = c - 1 ;

        while (start <= end) {

            index = (start + end) / 2 ;

            //  compare
            r = pfnCompare (
                    & p [index],
                    & Search
                    ) ;

            //  found it
            if (r == 0) {

                if (pdwIndex) {
                    * pdwIndex = index ;
                }

                return S_OK ;
            }
            //  search bracket moves up
            else if (r < 0) {
                start = index + 1 ;
            }
            //  search bracket moves down
            else {
                end = index - 1 ;
            }
        }


    }

    return E_FAIL ;
}

//  binary search of a vector; returns index of first element, and how many
//  there are in the bracket
template <class T>
HRESULT
BSearchBracket (
    IN  TSimpleVector <T> * pVector,            //  vector to search in
    IN  T                   Search,             //  what we're looking for
    IN  PFN_QSORT_COMPARE   pfnCompare,         //  comparison function
    OUT DWORD *             pdwFirstIndex,      //  index of first in bracket
    OUT DWORD *             pcInBracket         //  number of elements in the bracket
    )
{
    T *     p ;
    DWORD   cElements ;
    int     index, start, end, r ;

    ASSERT (pdwFirstIndex) ;
    ASSERT (pcInBracket) ;

    pVector -> GetVector (& p, & cElements) ;
    if (p) {
        ASSERT (cElements > 0) ;

        start = 0 ;
        end = cElements - 1 ;

        while (start <= end) {

            index = (start + end) / 2 ;

            //  compare
            r = pfnCompare (
                    & p [index],
                    & Search
                    ) ;

            //  found it
            if (r == 0) {

                ASSERT (pcInBracket) ;

                //  we now must discover the first and then count the number
                //  PID maps for this particular pin

                //  backup
                for (; index > 0 && pfnCompare (& p [index], & Search) == 0; index--) ;

                //  out of the failure condition

                if (index > 0) {

                    //  if we didn't stop because we were at the beginning of the vector,
                    //  increment the vector back to where the recorcs are equal
                    ASSERT (pfnCompare (& p [index], & Search) != 0) ;
                    index++ ;
                }
                else {

                    //  we're at the beginning of the vector; might be equal, or might
                    //  not; check here and increment the index back into the equal range
                    //  if they are equal
                    if (pfnCompare (& p [index], & Search) != 0) {
                        index++ ;
                    }
                }

                //  should now have the index to the first
                ASSERT (pfnCompare (& p [index], & Search) == 0) ;

                //  now seek up until we are out of the equal range or to the end of the vector
                for (* pcInBracket = 0;;) {

                    //  if we found another record
                    if (pfnCompare (& p [index + (* pcInBracket)], & Search) == 0) {

                        //  increment our counter
                        (* pcInBracket)++ ;
                    }
                    else {
                        //  otherwise break out
                        break ;
                    }

                    //  if we're to the end of the vector, break out
                    if (index + (* pcInBracket) == cElements) {
                        break ;
                    }
                }

                * pdwFirstIndex = index ;

                return S_OK ;
            }
            //  search bracket moves up
            else if (r < 0) {
                start = index + 1 ;
            }
            //  search bracket moves down
            else {
                end = index - 1 ;
            }
        }
    }

    return E_FAIL ;
}

//  external to internal
HRESULT
TransportMediaSampleContentEtoI (
    IN  DWORD   ExtMediaSampleContent,          //  transport
    OUT DWORD * pdwIntMediaSampleContent
    ) ;

HRESULT
ProgramMediaSampleContentEtoI (
    IN  DWORD   ExtMediaSampleContent,          //  program
    OUT DWORD * pdwIntMediaSampleContent
    ) ;

//  internal to external
HRESULT
TransportMediaSampleContentItoE (
    IN  DWORD   dwIntMediaSampleContent,
    OUT DWORD * pExtMediaSampleContent          //  transport
    ) ;

HRESULT
ProgramMediaSampleContentItoE (
    IN  DWORD   dwIntMediaSampleContent,
    OUT DWORD * pExtMediaSampleContent          //  program
    ) ;

BOOL
IsVideoMediaType (
    IN  AM_MEDIA_TYPE * pmt
    ) ;

BOOL
IsAudioMediaType (
    IN  AM_MEDIA_TYPE * pmt
    ) ;

BOOL
IsAVMediaType (
    IN  AM_MEDIA_TYPE * pmt
    ) ;

int
ParserArgSize (
    IN  DWORD   dwMediaSampleContent
    ) ;

__inline
BYTE
StartCode (
    IN BYTE *   pbStartCode
    )
{
    return pbStartCode [3] ;
}

__inline
BOOL
IsStartCodePrefix (
    IN  BYTE *  pbBuffer
    )
{
    return (pbBuffer [0] == 0x00 &&
            pbBuffer [1] == 0x00 &&
            pbBuffer [2] == 0x01) ;
}

//  TRUE :  (* ppbBuffer) points to prefix i.e. = {00,00,01}
//  FALSE:  (* piBufferLength) == 2
__inline
BOOL
SeekToPrefix (
    IN OUT  BYTE ** ppbBuffer,
    IN OUT  int *   piBufferLength
    )
{
    while ((* piBufferLength) >= START_CODE_PREFIX_LENGTH) {
        if (IsStartCodePrefix (* ppbBuffer)) {
            return TRUE ;
        }

        //  advance to next byte and decrement number of bytes left
        (* piBufferLength)-- ;
        (* ppbBuffer)++ ;
    }

    return FALSE ;
}


//  searches BACKWARDS through the past buffer
//  TRUE :  (* ppbBuffer) points to prefix i.e. = {00,00,01}
//  FALSE:  (* piBufferLength) == 2
__inline
BOOL
SeekBackFromEndForPrefix (
    IN OUT  BYTE ** ppbBuffer,          //  points to start of buffer
    IN OUT  int *   piBufferLength      //  length of buffer
    )
{
    BYTE *  pb ;

    if ((* piBufferLength) >= START_CODE_PREFIX_LENGTH) {

        //  must give ourselves room at the end
        (* piBufferLength) -= START_CODE_PREFIX_LENGTH ;

        //  set pbEnd to the last possible place we can determine if there's
        //   a prefix
        pb = (* ppbBuffer) + (* piBufferLength) ;

        while ((* piBufferLength) >= 0) {

            if (IsStartCodePrefix (pb)) {
                //  found one; set the outgoing pointer
                (* ppbBuffer) = pb ;
                return TRUE ;
            }

            //  advance to previous byte and decrement number of bytes left
            (* piBufferLength)-- ;
            pb-- ;
        }
    }

    return FALSE ;
}

static
__inline
LONGLONG
PCRToPTS (
    IN  LONGLONG    llPCR
    )
{
    return llPCR / 300 ;
}

static
__inline
LONGLONG
PTSToPCR (
    IN  LONGLONG    llPCR
    )
{
    return llPCR * 300 ;
}

__inline
ULONGLONG
PCRMinusPCR (
    IN  ULONGLONG   ullPCRLater,
    IN  ULONGLONG   ullPCREarlier
    )
//  returns ullVal1 - ullVal2, taking into consideration that PCRs are 48 bit values, and
//  that we are storing them in 64 bit types; don't include top 16 bits if there's an overflow
{
    return ullPCRLater - ullPCREarlier - (ullPCRLater < ullPCREarlier ? 0xffff000000000000 : 0) ;
}

__inline
DWORD
QPCToMillis (
    IN  LONGLONG    llQPC,
    IN  DWORD       dwQPCFreq
    )
{
    return (DWORD) ((1000 * llQPC) / dwQPCFreq) ;
}

__inline
REFERENCE_TIME
PCRToDShow (
    IN  LONGLONG    llPCR
    )
{
    //  safe to use since the top 16 bits are never set
    ASSERT ((llPCR & 0xffff000000000000) == 0x0000000000000000) ;
    return (REFERENCE_TIME) llMulDiv (llPCR, 10, 27, 0) ;
}

__inline
REFERENCE_TIME
SCRToDShow (
    IN  LONGLONG    llSCR
    )
{
    return PCRToDShow (llSCR) ;
}

__inline
REFERENCE_TIME
QPCToDShow (
    IN  LONGLONG    llQPC,
    IN  LONGLONG    llQPCFreq
    )
{
    double dRetval ;

    //  BUGBUG: this could wrap

    dRetval = llQPC * (10000000.0 / ((double) llQPCFreq)) ;
    return (REFERENCE_TIME) dRetval ;
}

__inline
REFERENCE_TIME
PTSToDShow (
    IN  ULONGLONG   ullPTS
    )
{
    ASSERT ((ullPTS & 0xffff000000000000) == 0x0000000000000000) ;
    return (REFERENCE_TIME) llMulDiv (ullPTS, 1000, 9, 0) ;
}

__inline
ULONGLONG
DShowToPTS (
    IN  REFERENCE_TIME  rtPTS
    )
{
    return (ULONGLONG) ::llMulDiv (rtPTS, 9, 1000, 0) ;
}

__inline
DWORD
DShowToMillis (
    IN  REFERENCE_TIME  rt
    )
{
    return (DWORD) (rt / (DSHOW_TICKS_PER_SECOND / MILLISECONDS_PER_SECOND)) ;
}

__inline
REFERENCE_TIME
MillisToDShow (
    IN  DWORD   dwMillis
    )
{
    return static_cast <REFERENCE_TIME> (dwMillis * (DSHOW_TICKS_PER_SECOND / MILLISECONDS_PER_SECOND)) ;
}

//  shameless stolen from DVDNAV
class CAnalogCopyProtection {

    public:
        CAnalogCopyProtection(IBaseFilter *pFilter) ;
        ~CAnalogCopyProtection(void) ;

        BOOL    IsAnyVRSuspected(void)       { return m_bVRNoKsPS ; } ;
        BOOL    IsACPFailIgnored(void)       { return m_bVerNT5 && !m_bDateExpired; } ;
        HRESULT MakeACPFilterList(void) ;
        HRESULT FreeACPFilterList(void) ;
        HRESULT DistributeAnalogCopyProtection(DWORD dwCPBits) ;
        void    ClearAnalogCopyProtectionLevel(void)  
                                             { m_dwLastCPBits = 0 ; } ;
        BYTE    GetACPLevel(void)            { return (BYTE) (m_dwLastCPBits & 0xFF) ; }

    private:
        CGenericList<IKsPropertySet>  m_KsPSList ; // List of filters for analog copy protection
        BOOL     m_bVRNoKsPS ;    // Any Video Renderer w/o IKsPropertySet interface?
        DWORD    m_dwLastCPBits ; // Last analog copy protection value distributed
        BOOL     m_bDateExpired ; // Has the date expired for this component?
        BOOL     m_bVerNT5 ;      // Is running under NT5.x?

        IBaseFilter *m_pFilter ;  // containing filter pointer
} ;

/*++
    smooths from 0 (after reset) to the target value; as the target value is
    updated, will tend towards it, but within the constraints of a max step
    value (per sec) specified; when reset, starts again at 0; target value
    can be updated anytime, but should be 0-based
--*/
template <class T>
class CTSmoothingFilter
{
    enum {
        DEF_BUCKET_MILLIS = 10
    } ;

    //  not serialized
    class CTimeBracket
    {
        DWORD       m_dwStartMillis ;
        const DWORD m_dwMaxAllowableElapsed ;

        public :

            CTimeBracket (
                IN  DWORD   dwMaxElapsed
                ) : m_dwStartMillis         (0),
                    m_dwMaxAllowableElapsed (dwMaxElapsed) {}

            void    Restart ()          { m_dwStartMillis = ::timeGetTime () ; }
            DWORD   ElapsedMillis ()    { return Min <DWORD> (m_dwMaxAllowableElapsed, ::timeGetTime () - m_dwStartMillis) ; }
    } ;

    T                   m_tTargetVal ;
    T                   m_tCurVal ;
    CRITICAL_SECTION    m_crt ;
    T                   m_tMaxStepPerMilli ;
    CTimeBracket        m_TimeBracket ;
    T                   m_tCurAllowableError ;
    double              m_dAllowableErrorDegradation ;

    void Lock_ ()       { ::EnterCriticalSection (& m_crt) ; }
    void Unlock_ ()     { ::LeaveCriticalSection (& m_crt) ; }

    public :

        CTSmoothingFilter (
            IN  T       tMaxStepPerMilli,
            IN  double  dAllowableErrorDegradation,
            IN  DWORD   dwBucketMillis = DEF_BUCKET_MILLIS
            ) : m_tMaxStepPerMilli              (tMaxStepPerMilli),
                m_dAllowableErrorDegradation    (dAllowableErrorDegradation),
                m_TimeBracket                   (dwBucketMillis)
        {
            ::InitializeCriticalSection (& m_crt) ;
            Reset () ;

            ASSERT (tMaxStepPerMilli != 0) ;
        }

        ~CTSmoothingFilter (
            )
        {
            ::DeleteCriticalSection (& m_crt) ;
        }

        void
        Reset (
            IN  T   tStartVal = 0
            )
        {
            Lock_ () ;

            m_tTargetVal            = tStartVal ;
            m_tCurVal               = tStartVal ;
            m_tCurAllowableError    = 0 ;

            m_TimeBracket.Restart () ;

            Unlock_ () ;
        }

        T TargetVal ()  { return m_tTargetVal ; }
        T CurVal ()     { return m_tCurVal ; }

        T
        AdjustCurVal (
            )
        {
            T       tCurVal ;
            T       tCurDelta ;
            T       tStep ;
            DWORD   dwElapsedMillis ;

            Lock_ () ;

            if (m_tCurVal != m_tTargetVal) {

                if (m_tTargetVal > m_tCurVal + m_tCurAllowableError) {
                    //  ----------------------------------------------------------------
                    //  adjust up

                    dwElapsedMillis = m_TimeBracket.ElapsedMillis () ;
                    if (dwElapsedMillis > 0) {

                        //  delta
                        tCurDelta = Abs <T> (m_tTargetVal - m_tCurVal) ;

                        //  step
                        tStep = Min <T> (tCurDelta, m_tMaxStepPerMilli * dwElapsedMillis) ;

                        //  adjust
                        m_tCurVal += tStep ;

                        //TRACE_4 (LOG_TIMING, 1, TEXT ("UP (elapsed = %u) CurDelta = %I64d; Step = %I64d; curval = %I64d ms"), dwElapsedMillis, tCurDelta, tStep, m_tCurVal/10000) ;

                        //  set our bracket
                        m_tCurAllowableError = Min <T> (tCurDelta, m_tCurAllowableError) ;

                        //  start our timer again
                        m_TimeBracket.Restart () ;
                    }
                }
                else if (m_tTargetVal < m_tCurVal - m_tCurAllowableError) {
                    //  ----------------------------------------------------------------
                    //  adjust down

                    dwElapsedMillis = m_TimeBracket.ElapsedMillis () ;
                    if (dwElapsedMillis > 0) {
                        //  delta
                        tCurDelta = Abs <T> (m_tCurVal - m_tTargetVal) ;

                        //  step
                        tStep = Min <T> (tCurDelta, m_tMaxStepPerMilli * dwElapsedMillis) ;

                        //TRACE_4 (LOG_TIMING, 1, TEXT ("DOWN (elapsed = %u) CurDelta = %I64d; Step = %I64d; curval = %I64d ms"), dwElapsedMillis, tCurDelta, tStep, m_tCurVal/10000) ;

                        //  adjust
                        m_tCurVal -= tStep ;

                        //  set our bracket
                        m_tCurAllowableError = Min <T> (tCurDelta, m_tCurAllowableError) ;

                        //  start our timer again
                        m_TimeBracket.Restart () ;
                    }
                }
                else {
                    //  ----------------------------------------------------------------
                    //  degrade our allowable error bracket

                    m_tCurAllowableError = (T) (m_dAllowableErrorDegradation * (double) m_tCurAllowableError) ;
                    //TRACE_1 (LOG_TIMING, 1, TEXT ("DEGRADE m_tCurAllowableError = %I64d"), m_tCurAllowableError) ;
                }
            }

            tCurVal = m_tCurVal ;

            Unlock_ () ;

            return tCurVal ;
        }

        void
        SetTargetVal (
            IN  T   tVal
            )
        {
            Lock_ () ;
            m_tTargetVal = tVal ;
            Unlock_ () ;
        }
} ;

#endif  //  __mp2demux_demxutil_h