Integer overflow in fx_basic.h and fx_memory.h
[pdfium.git] / core / include / fxcrt / fx_basic.h
1 // Copyright 2014 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4  
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7 #ifndef _FX_BASIC_H_
8 #define _FX_BASIC_H_
9 #ifndef _STDINT_H_ 
10 #define _STDINT_H_
11 #include <stdint.h>
12 #endif
13 #ifndef _FX_SYSTEM_H_
14 #include "fx_system.h"
15 #endif
16 #ifndef _FX_MEMORY_H_
17 #include "fx_memory.h"
18 #endif
19 #ifndef _FX_STRING_H_
20 #include "fx_string.h"
21 #endif
22 #ifndef _FX_STREAM_H_
23 #include "fx_stream.h"
24 #endif
25  
26 class CFX_BinaryBuf : public CFX_Object
27 {
28 public:
29
30     CFX_BinaryBuf(IFX_Allocator* pAllocator = NULL);
31
32     CFX_BinaryBuf(FX_STRSIZE size, IFX_Allocator* pAllocator = NULL);
33
34     ~CFX_BinaryBuf();
35
36     void                                        Clear();
37
38     void                                        EstimateSize(FX_STRSIZE size, FX_STRSIZE alloc_step = 0);
39
40     void                                        AppendBlock(const void* pBuf, FX_STRSIZE size);
41
42     void                                        AppendFill(FX_BYTE byte, FX_STRSIZE count);
43
44     void                                        AppendString(FX_BSTR str)
45     {
46         AppendBlock(str.GetPtr(), str.GetLength());
47     }
48
49     inline void                         AppendByte(FX_BYTE byte)
50     {
51         if (m_AllocSize <= m_DataSize) {
52             ExpandBuf(1);
53         }
54         m_pBuffer[m_DataSize++] = byte;
55     }
56
57     void                                        InsertBlock(FX_STRSIZE pos, const void* pBuf, FX_STRSIZE size);
58
59     void                                        AttachData(void* pBuf, FX_STRSIZE size);
60
61     void                                        CopyData(const void* pBuf, FX_STRSIZE size);
62
63     void                                        TakeOver(CFX_BinaryBuf& other);
64
65     void                                        Delete(int start_index, int count);
66
67     FX_LPBYTE                           GetBuffer() const
68     {
69         return m_pBuffer;
70     }
71
72     FX_STRSIZE                          GetSize() const
73     {
74         return m_DataSize;
75     }
76
77     CFX_ByteStringC                     GetByteString() const;
78     void                                        GetByteStringL(CFX_ByteStringL &str) const;
79
80     void                                        DetachBuffer();
81
82     IFX_Allocator*                      m_pAllocator;
83 protected:
84
85     FX_STRSIZE                          m_AllocStep;
86
87     FX_LPBYTE                           m_pBuffer;
88
89     FX_STRSIZE                          m_DataSize;
90
91     FX_STRSIZE                          m_AllocSize;
92
93     void                                        ExpandBuf(FX_STRSIZE size);
94 };
95 class CFX_ByteTextBuf : public CFX_BinaryBuf
96 {
97 public:
98
99     CFX_ByteTextBuf(IFX_Allocator* pAllocator = NULL) : CFX_BinaryBuf(pAllocator) {}
100
101     void                                        operator = (FX_BSTR str);
102
103     void                                        AppendChar(int ch)
104     {
105         AppendByte((FX_BYTE)ch);
106     }
107
108     CFX_ByteTextBuf&            operator << (int i);
109
110     CFX_ByteTextBuf&            operator << (FX_DWORD i);
111
112     CFX_ByteTextBuf&            operator << (double f);
113
114     CFX_ByteTextBuf&            operator << (FX_BSTR lpsz);
115
116     CFX_ByteTextBuf&            operator << (const CFX_ByteTextBuf& buf);
117
118     FX_STRSIZE                          GetLength() const
119     {
120         return m_DataSize;
121     }
122 };
123 class CFX_WideTextBuf : public CFX_BinaryBuf
124 {
125 public:
126
127     CFX_WideTextBuf(IFX_Allocator* pAllocator = NULL) : CFX_BinaryBuf(pAllocator) {}
128
129     void                                        operator = (FX_LPCWSTR lpsz);
130
131     void                                        operator = (FX_WSTR str);
132
133     void                                        AppendChar(FX_WCHAR wch);
134
135     CFX_WideTextBuf&            operator << (int i);
136
137     CFX_WideTextBuf&            operator << (double f);
138
139     CFX_WideTextBuf&            operator << (FX_LPCWSTR lpsz);
140
141     CFX_WideTextBuf&            operator << (FX_WSTR str);
142     CFX_WideTextBuf&            operator << (const CFX_WideString &str);
143
144     CFX_WideTextBuf&            operator << (const CFX_WideTextBuf& buf);
145
146     FX_STRSIZE                          GetLength() const
147     {
148         return m_DataSize / sizeof(FX_WCHAR);
149     }
150
151     FX_LPWSTR                           GetBuffer() const
152     {
153         return (FX_LPWSTR)m_pBuffer;
154     }
155
156     void                                        Delete(int start_index, int count)
157     {
158         CFX_BinaryBuf::Delete(start_index * sizeof(FX_WCHAR), count * sizeof(FX_WCHAR));
159     }
160
161     CFX_WideStringC                     GetWideString() const;
162     void                                        GetWideStringL(CFX_WideStringL& wideText) const;
163 };
164 class CFX_ArchiveSaver : public CFX_Object
165 {
166 public:
167
168     CFX_ArchiveSaver(IFX_Allocator* pAllocator = NULL) : m_SavingBuf(pAllocator), m_pStream(NULL) {}
169
170     CFX_ArchiveSaver&           operator << (FX_BYTE i);
171
172     CFX_ArchiveSaver&           operator << (int i);
173
174     CFX_ArchiveSaver&           operator << (FX_DWORD i);
175
176     CFX_ArchiveSaver&           operator << (FX_FLOAT i);
177
178     CFX_ArchiveSaver&           operator << (double i);
179
180     CFX_ArchiveSaver&           operator << (FX_BSTR bstr);
181
182     CFX_ArchiveSaver&           operator << (FX_LPCWSTR bstr);
183
184     CFX_ArchiveSaver&           operator << (const CFX_WideString& wstr);
185
186     void                                        Write(const void* pData, FX_STRSIZE dwSize);
187
188     FX_INTPTR                           GetLength()
189     {
190         return m_SavingBuf.GetSize();
191     }
192
193     FX_LPCBYTE                          GetBuffer()
194     {
195         return m_SavingBuf.GetBuffer();
196     }
197
198     void                                        SetStream(IFX_FileStream* pStream)
199     {
200         m_pStream = pStream;
201     }
202 protected:
203
204     CFX_BinaryBuf                       m_SavingBuf;
205
206     IFX_FileStream*                     m_pStream;
207 };
208 class CFX_ArchiveLoader : public CFX_Object
209 {
210 public:
211
212     CFX_ArchiveLoader(FX_LPCBYTE pData, FX_DWORD dwSize);
213
214     CFX_ArchiveLoader&          operator >> (FX_BYTE& i);
215
216     CFX_ArchiveLoader&          operator >> (int& i);
217
218     CFX_ArchiveLoader&          operator >> (FX_DWORD& i);
219
220     CFX_ArchiveLoader&          operator >> (FX_FLOAT& i);
221
222     CFX_ArchiveLoader&          operator >> (double& i);
223
224     CFX_ArchiveLoader&          operator >> (CFX_ByteString& bstr);
225
226     CFX_ArchiveLoader&          operator >> (CFX_WideString& wstr);
227
228     FX_BOOL                                     IsEOF();
229
230     FX_BOOL                                     Read(void* pBuf, FX_DWORD dwSize);
231 protected:
232
233     FX_DWORD                            m_LoadingPos;
234
235     FX_LPCBYTE                          m_pLoadingBuf;
236
237     FX_DWORD                            m_LoadingSize;
238 };
239 class IFX_BufferArchive
240 {
241 public:
242
243     IFX_BufferArchive(FX_STRSIZE size, IFX_Allocator* pAllocator = NULL);
244
245
246     virtual void                        Clear();
247
248
249     FX_BOOL                                     Flush();
250
251
252     FX_INT32                            AppendBlock(const void* pBuf, size_t size);
253
254     FX_INT32                            AppendByte(FX_BYTE byte);
255
256     FX_INT32                            AppendDWord(FX_DWORD i);
257
258
259     FX_INT32                            AppendString(FX_BSTR lpsz);
260
261 protected:
262
263     virtual     FX_BOOL                 DoWork(const void* pBuf, size_t size) = 0;
264
265
266     IFX_Allocator*                      m_pAllocator;
267
268     FX_STRSIZE                          m_BufSize;
269
270     FX_LPBYTE                           m_pBuffer;
271
272     FX_STRSIZE                          m_Length;
273 };
274 class CFX_FileBufferArchive : public IFX_BufferArchive, public CFX_Object
275 {
276 public:
277     CFX_FileBufferArchive(FX_STRSIZE size = 32768, IFX_Allocator* pAllocator = NULL);
278     ~CFX_FileBufferArchive();
279     virtual void                        Clear();
280
281     FX_BOOL                                     AttachFile(IFX_StreamWrite *pFile, FX_BOOL bTakeover = FALSE);
282
283     FX_BOOL                                     AttachFile(FX_LPCWSTR filename);
284
285     FX_BOOL                                     AttachFile(FX_LPCSTR filename);
286 private:
287
288     virtual FX_BOOL                     DoWork(const void* pBuf, size_t size);
289
290     IFX_StreamWrite                     *m_pFile;
291
292     FX_BOOL                                     m_bTakeover;
293 };
294 struct CFX_CharMap {
295
296     static CFX_CharMap*         GetDefaultMapper(FX_INT32 codepage = 0);
297
298
299     CFX_WideString      (*m_GetWideString)(CFX_CharMap* pMap, const CFX_ByteString& bstr);
300
301     CFX_ByteString      (*m_GetByteString)(CFX_CharMap* pMap, const CFX_WideString& wstr);
302
303     FX_INT32            (*m_GetCodePage)();
304 };
305 class CFX_UTF8Decoder
306 {
307 public:
308
309     CFX_UTF8Decoder(IFX_Allocator* pAllocator = NULL) : m_Buffer(pAllocator)
310     {
311         m_PendingBytes = 0;
312     }
313
314     void                        Clear();
315
316     void                        Input(FX_BYTE byte);
317
318     void                        AppendChar(FX_DWORD ch);
319
320     void                        ClearStatus()
321     {
322         m_PendingBytes = 0;
323     }
324
325     CFX_WideStringC     GetResult() const
326     {
327         return m_Buffer.GetWideString();
328     }
329     void                        GetResult(CFX_WideStringL &result) const
330     {
331         m_Buffer.GetWideStringL(result);
332     }
333 protected:
334
335     int                         m_PendingBytes;
336
337     FX_DWORD            m_PendingChar;
338
339     CFX_WideTextBuf     m_Buffer;
340 };
341 class CFX_UTF8Encoder
342 {
343 public:
344
345     CFX_UTF8Encoder(IFX_Allocator* pAllocator = NULL) : m_Buffer(pAllocator)
346     {
347         m_UTF16First = 0;
348     }
349
350     void                        Input(FX_WCHAR unicode);
351
352     void                        AppendStr(FX_BSTR str)
353     {
354         m_UTF16First = 0;
355         m_Buffer << str;
356     }
357
358     CFX_ByteStringC     GetResult() const
359     {
360         return m_Buffer.GetByteString();
361     }
362     void                        GetResult(CFX_ByteStringL &result) const
363     {
364         m_Buffer.GetByteStringL(result);
365     }
366 protected:
367
368     CFX_ByteTextBuf     m_Buffer;
369
370     FX_DWORD            m_UTF16First;
371 };
372 CFX_ByteString FX_UrlEncode(const CFX_WideString& wsUrl);
373 CFX_WideString FX_UrlDecode(const CFX_ByteString& bsUrl);
374 CFX_ByteString FX_EncodeURI(const CFX_WideString& wsURI);
375 CFX_WideString FX_DecodeURI(const CFX_ByteString& bsURI);
376 class CFX_BasicArray : public CFX_Object
377 {
378 public:
379
380     IFX_Allocator*      m_pAllocator;
381 protected:
382
383     CFX_BasicArray(int unit_size, IFX_Allocator* pAllocator = NULL);
384
385     ~CFX_BasicArray();
386
387     FX_BOOL                     SetSize(int nNewSize, int nGrowBy);
388
389     FX_BOOL                     Append(const CFX_BasicArray& src);
390
391     FX_BOOL                     Copy(const CFX_BasicArray& src);
392
393     FX_LPBYTE           InsertSpaceAt(int nIndex, int nCount);
394
395     FX_BOOL                     RemoveAt(int nIndex, int nCount);
396
397     FX_BOOL                     InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray);
398
399     const void*         GetDataPtr(int index) const;
400 protected:
401
402     FX_LPBYTE           m_pData;
403
404     int                         m_nSize;
405
406     int                         m_nMaxSize;
407
408     int                         m_nGrowBy;
409
410     int                         m_nUnitSize;
411 };
412 template<class TYPE>
413 class CFX_ArrayTemplate : public CFX_BasicArray
414 {
415 public:
416
417     CFX_ArrayTemplate(IFX_Allocator* pAllocator = NULL) : CFX_BasicArray(sizeof(TYPE), pAllocator) {}
418
419     int                 GetSize() const
420     {
421         return m_nSize;
422     }
423
424     int                 GetUpperBound() const
425     {
426         return m_nSize - 1;
427     }
428
429     FX_BOOL             SetSize(int nNewSize, int nGrowBy = -1)
430     {
431         return CFX_BasicArray::SetSize(nNewSize, nGrowBy);
432     }
433
434     void                RemoveAll()
435     {
436         SetSize(0, -1);
437     }
438
439     const TYPE  GetAt(int nIndex) const
440     {
441         if (nIndex < 0 || nIndex >= m_nSize) {
442             return (const TYPE&)(*(volatile const TYPE*)NULL);
443         }
444         return ((const TYPE*)m_pData)[nIndex];
445     }
446
447     FX_BOOL             SetAt(int nIndex, TYPE newElement)
448     {
449         if (nIndex < 0 || nIndex >= m_nSize) {
450             return FALSE;
451         }
452         ((TYPE*)m_pData)[nIndex] = newElement;
453         return TRUE;
454     }
455
456     TYPE&               ElementAt(int nIndex)
457     {
458         if (nIndex < 0 || nIndex >= m_nSize) {
459             return *(TYPE*)NULL;
460         }
461         return ((TYPE*)m_pData)[nIndex];
462     }
463
464     const TYPE* GetData() const
465     {
466         return (const TYPE*)m_pData;
467     }
468
469     TYPE*               GetData()
470     {
471         return (TYPE*)m_pData;
472     }
473
474     FX_BOOL             SetAtGrow(int nIndex, TYPE newElement)
475     {
476         if (nIndex < 0) {
477             return FALSE;
478         }
479         if (nIndex >= m_nSize)
480             if (!SetSize(nIndex + 1, -1)) {
481                 return FALSE;
482             }
483         ((TYPE*)m_pData)[nIndex] = newElement;
484         return TRUE;
485     }
486
487     FX_BOOL             Add(TYPE newElement)
488     {
489         if (m_nSize < m_nMaxSize) {
490             m_nSize ++;
491         } else if (!SetSize(m_nSize + 1, -1)) {
492             return FALSE;
493         }
494         ((TYPE*)m_pData)[m_nSize - 1] = newElement;
495         return TRUE;
496     }
497
498     FX_BOOL             Append(const CFX_ArrayTemplate& src)
499     {
500         return CFX_BasicArray::Append(src);
501     }
502
503     FX_BOOL             Copy(const CFX_ArrayTemplate& src)
504     {
505         return CFX_BasicArray::Copy(src);
506     }
507
508     TYPE*               GetDataPtr(int index)
509     {
510         return (TYPE*)CFX_BasicArray::GetDataPtr(index);
511     }
512
513     TYPE*               AddSpace()
514     {
515         return (TYPE*)CFX_BasicArray::InsertSpaceAt(m_nSize, 1);
516     }
517
518     TYPE*               InsertSpaceAt(int nIndex, int nCount)
519     {
520         return (TYPE*)CFX_BasicArray::InsertSpaceAt(nIndex, nCount);
521     }
522
523     const TYPE  operator[](int nIndex) const
524     {
525         if (nIndex < 0 || nIndex >= m_nSize) {
526             *(volatile char*)0 = '\0';
527         }
528         return ((const TYPE*)m_pData)[nIndex];
529     }
530
531     TYPE&               operator[](int nIndex)
532     {
533         if (nIndex < 0 || nIndex >= m_nSize) {
534             *(volatile char*)0 = '\0';
535         }
536         return ((TYPE*)m_pData)[nIndex];
537     }
538
539     FX_BOOL             InsertAt(int nIndex, TYPE newElement, int nCount = 1)
540     {
541         if (!InsertSpaceAt(nIndex, nCount)) {
542             return FALSE;
543         }
544         while (nCount--) {
545             ((TYPE*)m_pData)[nIndex++] = newElement;
546         }
547         return TRUE;
548     }
549
550     FX_BOOL             RemoveAt(int nIndex, int nCount = 1)
551     {
552         return CFX_BasicArray::RemoveAt(nIndex, nCount);
553     }
554
555     FX_BOOL             InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray)
556     {
557         return CFX_BasicArray::InsertAt(nStartIndex, pNewArray);
558     }
559
560     int                 Find(TYPE data, int iStart = 0) const
561     {
562         if (iStart < 0) {
563             return -1;
564         }
565         for (; iStart < (int)m_nSize; iStart ++)
566             if (((TYPE*)m_pData)[iStart] == data) {
567                 return iStart;
568             }
569         return -1;
570     }
571 };
572 typedef CFX_ArrayTemplate<FX_BYTE>              CFX_ByteArray;
573 typedef CFX_ArrayTemplate<FX_WORD>              CFX_WordArray;
574 typedef CFX_ArrayTemplate<FX_DWORD>             CFX_DWordArray;
575 typedef CFX_ArrayTemplate<void*>                CFX_PtrArray;
576 typedef CFX_ArrayTemplate<FX_FILESIZE>  CFX_FileSizeArray;
577 typedef CFX_ArrayTemplate<FX_FLOAT>             CFX_FloatArray;
578 typedef CFX_ArrayTemplate<FX_INT32>             CFX_Int32Array;
579 template <class ObjectClass>
580 class CFX_ObjectArray : public CFX_BasicArray
581 {
582 public:
583
584     CFX_ObjectArray(IFX_Allocator* pAllocator = NULL) : CFX_BasicArray(sizeof(ObjectClass), pAllocator) {}
585
586     ~CFX_ObjectArray()
587     {
588         RemoveAll();
589     }
590
591     void                        Add(const ObjectClass& data)
592     {
593         new ((void*)InsertSpaceAt(m_nSize, 1)) ObjectClass(data);
594     }
595
596     ObjectClass&        Add()
597     {
598         return *(ObjectClass*) new ((void*)InsertSpaceAt(m_nSize, 1)) ObjectClass();
599     }
600
601     void*                       AddSpace()
602     {
603         return InsertSpaceAt(m_nSize, 1);
604     }
605
606     FX_INT32            Append(const CFX_ObjectArray& src, FX_INT32 nStart = 0, FX_INT32 nCount = -1)
607     {
608         if (nCount == 0) {
609             return 0;
610         }
611         FX_INT32 nSize = src.GetSize();
612         if (!nSize) {
613             return 0;
614         }
615         FXSYS_assert(nStart > -1 && nStart < nSize);
616         if (nCount < 0) {
617             nCount = nSize;
618         }
619         if (nStart + nCount > nSize) {
620             nCount = nSize - nStart;
621         }
622         if (nCount < 1) {
623             return 0;
624         }
625         nSize = m_nSize;
626         InsertSpaceAt(m_nSize, nCount);
627         ObjectClass* pStartObj = (ObjectClass*)GetDataPtr(nSize);
628         nSize = nStart + nCount;
629         for (FX_INT32 i = nStart; i < nSize; i ++, pStartObj++) {
630             new ((void*)pStartObj) ObjectClass(src[i]);
631         }
632         return nCount;
633     }
634
635     FX_INT32            Copy(const CFX_ObjectArray& src, FX_INT32 nStart = 0, FX_INT32 nCount = -1)
636     {
637         if (nCount == 0) {
638             return 0;
639         }
640         FX_INT32 nSize = src.GetSize();
641         if (!nSize) {
642             return 0;
643         }
644         FXSYS_assert(nStart > -1 && nStart < nSize);
645         if (nCount < 0) {
646             nCount = nSize;
647         }
648         if (nStart + nCount > nSize) {
649             nCount = nSize - nStart;
650         }
651         if (nCount < 1) {
652             return 0;
653         }
654         RemoveAll();
655         SetSize(nCount, -1);
656         ObjectClass* pStartObj = (ObjectClass*)m_pData;
657         nSize = nStart + nCount;
658         for (FX_INT32 i = nStart; i < nSize; i ++, pStartObj++) {
659             new ((void*)pStartObj) ObjectClass(src[i]);
660         }
661         return nCount;
662     }
663
664     int                         GetSize() const
665     {
666         return m_nSize;
667     }
668
669     ObjectClass&        operator[] (int index) const
670     {
671         FXSYS_assert(index < m_nSize);
672         return *(ObjectClass*)CFX_BasicArray::GetDataPtr(index);
673     }
674
675     ObjectClass*        GetDataPtr(int index)
676     {
677         return (ObjectClass*)CFX_BasicArray::GetDataPtr(index);
678     }
679
680     void                        RemoveAt(int index)
681     {
682         FXSYS_assert(index < m_nSize);
683         ((ObjectClass*)GetDataPtr(index))->~ObjectClass();
684         CFX_BasicArray::RemoveAt(index, 1);
685     }
686
687     void                        RemoveAll()
688     {
689         for (int i = 0; i < m_nSize; i ++) {
690             ((ObjectClass*)GetDataPtr(i))->~ObjectClass();
691         }
692         CFX_BasicArray::SetSize(0, -1);
693     }
694 };
695 typedef CFX_ObjectArray<CFX_ByteString> CFX_ByteStringArray;
696 typedef CFX_ObjectArray<CFX_WideString> CFX_WideStringArray;
697 class CFX_BaseSegmentedArray : public CFX_Object
698 {
699 public:
700
701     CFX_BaseSegmentedArray(int unit_size = 1, int segment_units = 512, int index_size = 8, IFX_Allocator* pAllocator = NULL);
702
703     ~CFX_BaseSegmentedArray();
704
705     void        SetUnitSize(int unit_size, int segment_units, int index_size = 8);
706
707     void*       Add();
708
709     void*       GetAt(int index) const;
710
711     void        RemoveAll();
712
713     void        Delete(int index, int count = 1);
714
715     int         GetSize() const
716     {
717         return m_DataSize;
718     }
719
720     int         GetSegmentSize() const
721     {
722         return m_SegmentSize;
723     }
724
725     int         GetUnitSize() const
726     {
727         return m_UnitSize;
728     }
729
730     void*       Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const;
731
732     IFX_Allocator*      m_pAllocator;
733 private:
734
735     int                         m_UnitSize;
736
737     short                       m_SegmentSize;
738
739     FX_BYTE                     m_IndexSize;
740
741     FX_BYTE                     m_IndexDepth;
742
743     int                         m_DataSize;
744
745     void*                       m_pIndex;
746     void**      GetIndex(int seg_index) const;
747     void*       IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const;
748     void*       IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const;
749 };
750 template <class ElementType>
751 class CFX_SegmentedArray : public CFX_BaseSegmentedArray
752 {
753 public:
754
755     CFX_SegmentedArray(int segment_units, int index_size = 8, IFX_Allocator* pAllocator = NULL)
756         : CFX_BaseSegmentedArray(sizeof(ElementType), segment_units, index_size, pAllocator)
757     {}
758
759     void        Add(ElementType data)
760     {
761         *(ElementType*)CFX_BaseSegmentedArray::Add() = data;
762     }
763
764     ElementType& operator [] (int index)
765     {
766         return *(ElementType*)CFX_BaseSegmentedArray::GetAt(index);
767     }
768 };
769 template <class DataType, int FixedSize>
770 class CFX_FixedBufGrow : public CFX_Object
771 {
772 public:
773     CFX_FixedBufGrow(IFX_Allocator* pAllocator = NULL)
774         : m_pAllocator(pAllocator)
775         , m_pData(NULL)
776     {}
777     CFX_FixedBufGrow(int data_size, IFX_Allocator* pAllocator = NULL)
778         : m_pAllocator(pAllocator)
779         , m_pData(NULL)
780     {
781         if (data_size > FixedSize) {
782             m_pData = FX_Allocator_Alloc(m_pAllocator, DataType, data_size);
783         } else {
784             if (FixedSize > SIZE_MAX/sizeof(DataType))
785                 return;
786
787             FXSYS_memset32(m_Data, 0, sizeof(DataType)*FixedSize);
788         }
789     }
790     void SetDataSize(int data_size)
791     {
792         if (m_pData) {
793             FX_Allocator_Free(m_pAllocator, m_pData);
794         }
795         m_pData = NULL;
796         if (data_size > FixedSize) {
797             m_pData = FX_Allocator_Alloc(m_pAllocator, DataType, data_size);
798         } else {
799
800             if (FixedSize > SIZE_MAX/sizeof(DataType))
801                 return;
802
803             FXSYS_memset32(m_Data, 0, sizeof(DataType)*FixedSize);
804         }
805     }
806     ~CFX_FixedBufGrow()
807     {
808         if (m_pData) {
809             FX_Allocator_Free(m_pAllocator, m_pData);
810         }
811     }
812     operator DataType*()
813     {
814         return m_pData ? m_pData : m_Data;
815     }
816 private:
817     IFX_Allocator*      m_pAllocator;
818     DataType            m_Data[FixedSize];
819     DataType*           m_pData;
820 };
821 template <class DataType>
822 class CFX_TempBuf
823 {
824 public:
825     CFX_TempBuf(int size, IFX_Allocator* pAllocator = NULL) : m_pAllocator(pAllocator)
826     {
827         m_pData = FX_Allocator_Alloc(m_pAllocator, DataType, size);
828     }
829     ~CFX_TempBuf()
830     {
831         if (m_pData) {
832             FX_Allocator_Free(m_pAllocator, m_pData);
833         }
834     }
835     DataType&   operator[](int i)
836     {
837         FXSYS_assert(m_pData != NULL);
838         return m_pData[i];
839     }
840     operator DataType*()
841     {
842         return m_pData;
843     }
844 private:
845     IFX_Allocator*      m_pAllocator;
846     DataType*           m_pData;
847 };
848 class CFX_MapPtrToPtr : public CFX_Object
849 {
850 protected:
851
852     struct CAssoc {
853
854         CAssoc* pNext;
855
856         void* key;
857
858         void* value;
859     };
860 public:
861
862     CFX_MapPtrToPtr(int nBlockSize = 10, IFX_Allocator* pAllocator = NULL);
863
864     ~CFX_MapPtrToPtr();
865
866     int GetCount() const
867     {
868         return m_nCount;
869     }
870
871     FX_BOOL IsEmpty() const
872     {
873         return m_nCount == 0;
874     }
875
876     FX_BOOL Lookup(void* key, void*& rValue) const;
877
878     void* GetValueAt(void* key) const;
879
880     void*& operator[](void* key);
881
882     void SetAt(void* key, void* newValue)
883     {
884         (*this)[key] = newValue;
885     }
886
887     FX_BOOL RemoveKey(void* key);
888
889     void RemoveAll();
890
891     FX_POSITION GetStartPosition() const
892     {
893         return (m_nCount == 0) ? NULL : (FX_POSITION) - 1;
894     }
895
896     void GetNextAssoc(FX_POSITION& rNextPosition, void*& rKey, void*& rValue) const;
897
898     FX_DWORD GetHashTableSize() const
899     {
900         return m_nHashTableSize;
901     }
902
903     void InitHashTable(FX_DWORD hashSize, FX_BOOL bAllocNow = TRUE);
904 protected:
905
906     IFX_Allocator*      m_pAllocator;
907
908     CAssoc** m_pHashTable;
909
910     FX_DWORD m_nHashTableSize;
911
912     int m_nCount;
913
914     CAssoc* m_pFreeList;
915
916     struct CFX_Plex* m_pBlocks;
917
918     int m_nBlockSize;
919
920     FX_DWORD HashKey(void* key) const;
921
922     CAssoc* NewAssoc();
923
924     void FreeAssoc(CAssoc* pAssoc);
925
926     CAssoc* GetAssocAt(void* key, FX_DWORD& hash) const;
927 };
928 template <class KeyType, class ValueType>
929 class CFX_MapPtrTemplate : public CFX_MapPtrToPtr
930 {
931 public:
932
933     CFX_MapPtrTemplate(IFX_Allocator* pAllocator = NULL) : CFX_MapPtrToPtr(10, pAllocator) {}
934
935     FX_BOOL     Lookup(KeyType key, ValueType& rValue) const
936     {
937         FX_LPVOID pValue = NULL;
938         if (!CFX_MapPtrToPtr::Lookup((void*)(FX_UINTPTR)key, pValue)) {
939             return FALSE;
940         }
941         rValue = (ValueType)(FX_UINTPTR)pValue;
942         return TRUE;
943     }
944
945     ValueType& operator[](KeyType key)
946     {
947         return (ValueType&)CFX_MapPtrToPtr::operator []((void*)(FX_UINTPTR)key);
948     }
949
950     void SetAt(KeyType key, ValueType newValue)
951     {
952         CFX_MapPtrToPtr::SetAt((void*)(FX_UINTPTR)key, (void*)(FX_UINTPTR)newValue);
953     }
954
955     FX_BOOL     RemoveKey(KeyType key)
956     {
957         return CFX_MapPtrToPtr::RemoveKey((void*)(FX_UINTPTR)key);
958     }
959
960     void GetNextAssoc(FX_POSITION& rNextPosition, KeyType& rKey, ValueType& rValue) const
961     {
962         void* pKey = NULL;
963         void* pValue = NULL;
964         CFX_MapPtrToPtr::GetNextAssoc(rNextPosition, pKey, pValue);
965         rKey = (KeyType)(FX_UINTPTR)pKey;
966         rValue = (ValueType)(FX_UINTPTR)pValue;
967     }
968 };
969 class CFX_CMapDWordToDWord : public CFX_Object
970 {
971 public:
972
973     CFX_CMapDWordToDWord(IFX_Allocator* pAllocator = NULL) : m_Buffer(pAllocator) {}
974
975     FX_BOOL                     Lookup(FX_DWORD key, FX_DWORD& value) const;
976
977     void                        SetAt(FX_DWORD key, FX_DWORD value);
978
979     void                        EstimateSize(FX_DWORD size, FX_DWORD grow_by);
980
981     FX_POSITION         GetStartPosition() const;
982
983     void                        GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const;
984 protected:
985
986     CFX_BinaryBuf       m_Buffer;
987 };
988 class CFX_MapByteStringToPtr : public CFX_Object
989 {
990 protected:
991
992     struct CAssoc {
993
994         CAssoc* pNext;
995
996         FX_DWORD nHashValue;
997
998         CFX_ByteString key;
999
1000         void* value;
1001     };
1002 public:
1003
1004     CFX_MapByteStringToPtr(int nBlockSize = 10, IFX_Allocator* pAllocator = NULL);
1005
1006     int GetCount() const
1007     {
1008         return m_nCount;
1009     }
1010
1011     FX_BOOL IsEmpty() const
1012     {
1013         return m_nCount == 0;
1014     }
1015
1016     FX_BOOL Lookup(FX_BSTR key, void*& rValue) const;
1017
1018     void*& operator[](FX_BSTR key);
1019
1020     void SetAt(FX_BSTR key, void* newValue)
1021     {
1022         (*this)[key] = newValue;
1023     }
1024
1025     FX_BOOL RemoveKey(FX_BSTR key);
1026
1027     void RemoveAll();
1028
1029     FX_POSITION GetStartPosition() const
1030     {
1031         return (m_nCount == 0) ? NULL : (FX_POSITION) - 1;
1032     }
1033
1034     void GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const;
1035
1036     FX_LPVOID           GetNextValue(FX_POSITION& rNextPosition) const;
1037
1038     FX_DWORD GetHashTableSize() const
1039     {
1040         return m_nHashTableSize;
1041     }
1042
1043     void InitHashTable(FX_DWORD hashSize, FX_BOOL bAllocNow = TRUE);
1044
1045     FX_DWORD HashKey(FX_BSTR key) const;
1046 protected:
1047
1048     IFX_Allocator*      m_pAllocator;
1049
1050     CAssoc** m_pHashTable;
1051
1052     FX_DWORD m_nHashTableSize;
1053
1054     int m_nCount;
1055
1056     CAssoc* m_pFreeList;
1057
1058     struct CFX_Plex* m_pBlocks;
1059
1060     int m_nBlockSize;
1061
1062     CAssoc* NewAssoc();
1063
1064     void FreeAssoc(CAssoc* pAssoc);
1065
1066     CAssoc* GetAssocAt(FX_BSTR key, FX_DWORD& hash) const;
1067 public:
1068
1069     ~CFX_MapByteStringToPtr();
1070 };
1071 class CFX_CMapByteStringToPtr : public CFX_Object
1072 {
1073 public:
1074
1075     CFX_CMapByteStringToPtr(IFX_Allocator* pAllocator = NULL);
1076
1077     ~CFX_CMapByteStringToPtr();
1078
1079     void                        RemoveAll();
1080
1081     FX_POSITION         GetStartPosition() const;
1082
1083     void                        GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const;
1084
1085     FX_LPVOID           GetNextValue(FX_POSITION& rNextPosition) const;
1086
1087     FX_BOOL                     Lookup(FX_BSTR key, void*& rValue) const;
1088
1089     void                        SetAt(FX_BSTR key, void* value);
1090
1091     void                        RemoveKey(FX_BSTR key);
1092
1093     int                         GetCount() const;
1094
1095     void                        AddValue(FX_BSTR key, void* pValue);
1096 private:
1097
1098     CFX_BaseSegmentedArray                      m_Buffer;
1099 };
1100 class CFX_PtrList : public CFX_Object
1101 {
1102 protected:
1103
1104     struct CNode {
1105
1106         CNode* pNext;
1107
1108         CNode* pPrev;
1109
1110         void* data;
1111     };
1112 public:
1113
1114     CFX_PtrList(int nBlockSize = 10, IFX_Allocator* pAllocator = NULL);
1115
1116     FX_POSITION GetHeadPosition() const
1117     {
1118         return (FX_POSITION)m_pNodeHead;
1119     }
1120
1121     FX_POSITION GetTailPosition() const
1122     {
1123         return (FX_POSITION)m_pNodeTail;
1124     }
1125
1126     void*       GetNext(FX_POSITION& rPosition) const
1127     {
1128         CNode* pNode = (CNode*) rPosition;
1129         rPosition = (FX_POSITION) pNode->pNext;
1130         return pNode->data;
1131     }
1132
1133     void*       GetPrev(FX_POSITION& rPosition) const
1134     {
1135         CNode* pNode = (CNode*) rPosition;
1136         rPosition = (FX_POSITION) pNode->pPrev;
1137         return pNode->data;
1138     }
1139
1140     FX_POSITION GetNextPosition(FX_POSITION pos) const
1141     {
1142         return ((CNode*)pos)->pNext;
1143     }
1144
1145     FX_POSITION GetPrevPosition(FX_POSITION pos) const
1146     {
1147         return ((CNode*)pos)->pPrev;
1148     }
1149
1150     void*       GetAt(FX_POSITION rPosition) const
1151     {
1152         CNode* pNode = (CNode*) rPosition;
1153         return pNode->data;
1154     }
1155
1156     int         GetCount() const
1157     {
1158         return m_nCount;
1159     }
1160
1161     FX_POSITION AddTail(void* newElement);
1162
1163     FX_POSITION AddHead(void* newElement);
1164
1165     void        SetAt(FX_POSITION pos, void* newElement)
1166     {
1167         CNode* pNode = (CNode*) pos;
1168         pNode->data = newElement;
1169     }
1170
1171     FX_POSITION InsertAfter(FX_POSITION pos, void* newElement);
1172
1173     FX_POSITION Find(void* searchValue, FX_POSITION startAfter = NULL ) const;
1174
1175     FX_POSITION FindIndex(int index) const;
1176
1177     void        RemoveAt(FX_POSITION pos);
1178
1179     void        RemoveAll();
1180 protected:
1181
1182     IFX_Allocator*      m_pAllocator;
1183
1184     CNode* m_pNodeHead;
1185
1186     CNode* m_pNodeTail;
1187
1188     int m_nCount;
1189
1190     CNode* m_pNodeFree;
1191
1192     struct CFX_Plex* m_pBlocks;
1193
1194     int m_nBlockSize;
1195
1196     CNode* NewNode(CNode* pPrev, CNode* pNext);
1197
1198     void FreeNode(CNode* pNode);
1199 public:
1200
1201     ~CFX_PtrList();
1202 };
1203 typedef void (*PD_CALLBACK_FREEDATA)(FX_LPVOID pData);
1204 struct FX_PRIVATEDATA {
1205
1206     void                                        FreeData();
1207
1208     FX_LPVOID                           m_pModuleId;
1209
1210     FX_LPVOID                           m_pData;
1211
1212     PD_CALLBACK_FREEDATA        m_pCallback;
1213
1214     FX_BOOL                                     m_bSelfDestruct;
1215 };
1216 class CFX_PrivateData
1217 {
1218 public:
1219
1220     CFX_PrivateData(IFX_Allocator* pAllocator = NULL) : m_DataList(pAllocator) {}
1221
1222     ~CFX_PrivateData();
1223
1224     void                                        ClearAll();
1225
1226     void                                        SetPrivateData(FX_LPVOID module_id, FX_LPVOID pData, PD_CALLBACK_FREEDATA callback);
1227
1228     void                                        SetPrivateObj(FX_LPVOID module_id, CFX_DestructObject* pObj);
1229
1230     FX_LPVOID                           GetPrivateData(FX_LPVOID module_id);
1231
1232     FX_BOOL                                     LookupPrivateData(FX_LPVOID module_id, FX_LPVOID &pData) const
1233     {
1234         if (!module_id) {
1235             return FALSE;
1236         }
1237         FX_DWORD nCount = m_DataList.GetSize();
1238         for (FX_DWORD n = 0; n < nCount; n ++) {
1239             if (m_DataList[n].m_pModuleId == module_id) {
1240                 pData = m_DataList[n].m_pData;
1241                 return TRUE;
1242             }
1243         }
1244         return FALSE;
1245     }
1246
1247     FX_BOOL                                     RemovePrivateData(FX_LPVOID module_id);
1248 protected:
1249
1250     CFX_ArrayTemplate<FX_PRIVATEDATA>   m_DataList;
1251
1252     void                                        AddData(FX_LPVOID module_id, FX_LPVOID pData, PD_CALLBACK_FREEDATA callback, FX_BOOL bSelfDestruct);
1253 };
1254 class CFX_BitStream : public CFX_Object
1255 {
1256 public:
1257
1258     void                                Init(FX_LPCBYTE pData, FX_DWORD dwSize);
1259
1260
1261     FX_DWORD                    GetBits(FX_DWORD nBits);
1262
1263     void                                ByteAlign();
1264
1265     FX_BOOL                             IsEOF()
1266     {
1267         return m_BitPos >= m_BitSize;
1268     }
1269
1270     void                                SkipBits(FX_DWORD nBits)
1271     {
1272         m_BitPos += nBits;
1273     }
1274
1275     void                                Rewind()
1276     {
1277         m_BitPos = 0;
1278     }
1279 protected:
1280
1281     FX_DWORD                    m_BitPos;
1282
1283     FX_DWORD                    m_BitSize;
1284
1285     FX_LPCBYTE                  m_pData;
1286 };
1287 template <class ObjClass> class CFX_CountRef : public CFX_Object
1288 {
1289 public:
1290
1291     typedef CFX_CountRef<ObjClass> Ref;
1292
1293     class CountedObj : public ObjClass
1294     {
1295     public:
1296
1297         CountedObj() {}
1298
1299         CountedObj(const CountedObj& src) : ObjClass(src) {}
1300
1301         int                     m_RefCount;
1302     };
1303
1304     CFX_CountRef()
1305     {
1306         m_pObject = NULL;
1307     }
1308
1309     CFX_CountRef(const Ref& ref)
1310     {
1311         m_pObject = ref.m_pObject;
1312         if (m_pObject) {
1313             m_pObject->m_RefCount ++;
1314         }
1315     }
1316
1317     ~CFX_CountRef()
1318     {
1319         if (!m_pObject) {
1320             return;
1321         }
1322         m_pObject->m_RefCount --;
1323         if (m_pObject->m_RefCount <= 0) {
1324             delete m_pObject;
1325         }
1326     }
1327
1328     ObjClass*                   New()
1329     {
1330         if (m_pObject) {
1331             m_pObject->m_RefCount --;
1332             if (m_pObject->m_RefCount <= 0) {
1333                 delete m_pObject;
1334             }
1335             m_pObject = NULL;
1336         }
1337         m_pObject = FX_NEW CountedObj;
1338         if (!m_pObject) {
1339             return NULL;
1340         }
1341         m_pObject->m_RefCount = 1;
1342         return m_pObject;
1343     }
1344
1345     void                                operator = (const Ref& ref)
1346     {
1347         if (ref.m_pObject) {
1348             ref.m_pObject->m_RefCount ++;
1349         }
1350         if (m_pObject) {
1351             m_pObject->m_RefCount --;
1352             if (m_pObject->m_RefCount <= 0) {
1353                 delete m_pObject;
1354             }
1355         }
1356         m_pObject = ref.m_pObject;
1357     }
1358
1359     void                                operator = (void* p)
1360     {
1361         FXSYS_assert(p == 0);
1362         if (m_pObject == NULL) {
1363             return;
1364         }
1365         m_pObject->m_RefCount --;
1366         if (m_pObject->m_RefCount <= 0) {
1367             delete m_pObject;
1368         }
1369         m_pObject = NULL;
1370     }
1371
1372     const ObjClass*             GetObject() const
1373     {
1374         return m_pObject;
1375     }
1376
1377     operator                    const ObjClass*() const
1378     {
1379         return m_pObject;
1380     }
1381
1382     FX_BOOL                             IsNull() const
1383     {
1384         return m_pObject == NULL;
1385     }
1386
1387     FX_BOOL                             NotNull() const
1388     {
1389         return m_pObject != NULL;
1390     }
1391
1392     ObjClass*                   GetModify()
1393     {
1394         if (m_pObject == NULL) {
1395             m_pObject = FX_NEW CountedObj;
1396             if (m_pObject) {
1397                 m_pObject->m_RefCount = 1;
1398             }
1399         } else if (m_pObject->m_RefCount > 1) {
1400             m_pObject->m_RefCount --;
1401             CountedObj* pOldObject = m_pObject;
1402             m_pObject = NULL;
1403             m_pObject = FX_NEW CountedObj(*pOldObject);
1404             if (m_pObject) {
1405                 m_pObject->m_RefCount = 1;
1406             }
1407         }
1408         return m_pObject;
1409     }
1410
1411     void                                SetNull()
1412     {
1413         if (m_pObject == NULL) {
1414             return;
1415         }
1416         m_pObject->m_RefCount --;
1417         if (m_pObject->m_RefCount <= 0) {
1418             delete m_pObject;
1419         }
1420         m_pObject = NULL;
1421     }
1422
1423     FX_BOOL                             operator == (const Ref& ref) const
1424     {
1425         return m_pObject == ref.m_pObject;
1426     }
1427 protected:
1428
1429     CountedObj*                 m_pObject;
1430 };
1431 class IFX_Pause
1432 {
1433 public:
1434
1435     virtual FX_BOOL     NeedToPauseNow() = 0;
1436 };
1437 class CFX_DataFilter : public CFX_Object
1438 {
1439 public:
1440
1441     virtual ~CFX_DataFilter();
1442
1443     void                        SetDestFilter(CFX_DataFilter* pFilter);
1444
1445     FX_BOOL                     IsEOF() const
1446     {
1447         return m_bEOF;
1448     }
1449
1450     FX_DWORD            GetSrcPos()
1451     {
1452         return m_SrcPos;
1453     }
1454
1455     void                        FilterIn(FX_LPCBYTE src_buf, FX_DWORD src_size, CFX_BinaryBuf& dest_buf);
1456
1457     void                        FilterFinish(CFX_BinaryBuf& dest_buf);
1458 protected:
1459
1460     CFX_DataFilter();
1461     virtual void        v_FilterIn(FX_LPCBYTE src_buf, FX_DWORD src_size, CFX_BinaryBuf& dest_buf) = 0;
1462     virtual void        v_FilterFinish(CFX_BinaryBuf& dest_buf) = 0;
1463     void                        ReportEOF(FX_DWORD left_input);
1464
1465     FX_BOOL                     m_bEOF;
1466
1467     FX_DWORD            m_SrcPos;
1468
1469     CFX_DataFilter*     m_pDestFilter;
1470 };
1471 template <class T>
1472 class CFX_SmartPointer
1473 {
1474 public:
1475     CFX_SmartPointer(T *pObj) : m_pObj(pObj) {}
1476     ~CFX_SmartPointer()
1477     {
1478         m_pObj->Release();
1479     }
1480     operator T*(void)
1481     {
1482         return m_pObj;
1483     }
1484     T&          operator *(void)
1485     {
1486         return *m_pObj;
1487     }
1488     T*          operator ->(void)
1489     {
1490         return m_pObj;
1491     }
1492 protected:
1493     T *m_pObj;
1494 };
1495 #define FX_DATALIST_LENGTH      1024
1496 template<size_t unit>
1497 class CFX_SortListArray : public CFX_Object
1498 {
1499 protected:
1500
1501     struct DataList {
1502
1503         FX_INT32        start;
1504
1505         FX_INT32        count;
1506         FX_LPBYTE       data;
1507     };
1508 public:
1509
1510     CFX_SortListArray(IFX_Allocator* pAllocator = NULL) : m_CurList(0), m_DataLists(pAllocator) {}
1511
1512     ~CFX_SortListArray()
1513     {
1514         Clear();
1515     }
1516
1517
1518     void                        Clear()
1519     {
1520         IFX_Allocator* pAllocator = m_DataLists.m_pAllocator;
1521         for (FX_INT32 i = m_DataLists.GetUpperBound(); i >= 0; i--) {
1522             DataList list = m_DataLists.ElementAt(i);
1523             if (list.data) {
1524                 FX_Allocator_Free(pAllocator, list.data);
1525             }
1526         }
1527         m_DataLists.RemoveAll();
1528         m_CurList = 0;
1529     }
1530
1531     void                        Append(FX_INT32 nStart, FX_INT32 nCount)
1532     {
1533         if (nStart < 0) {
1534             return;
1535         }
1536         IFX_Allocator* pAllocator = m_DataLists.m_pAllocator;
1537         while (nCount > 0) {
1538             FX_INT32 temp_count = FX_MIN(nCount, FX_DATALIST_LENGTH);
1539             DataList list;
1540             list.data = FX_Allocator_Alloc(pAllocator, FX_BYTE, temp_count * unit);
1541             if (!list.data) {
1542                 break;
1543             }
1544             FXSYS_memset32(list.data, 0, temp_count * unit);
1545             list.start = nStart;
1546             list.count = temp_count;
1547             Append(list);
1548             nCount -= temp_count;
1549             nStart += temp_count;
1550         }
1551     }
1552
1553     FX_LPBYTE           GetAt(FX_INT32 nIndex)
1554     {
1555         if (nIndex < 0) {
1556             return NULL;
1557         }
1558         if (m_CurList < 0 || m_CurList >= m_DataLists.GetSize()) {
1559             return NULL;
1560         }
1561         DataList *pCurList = m_DataLists.GetDataPtr(m_CurList);
1562         if (!pCurList || nIndex < pCurList->start || nIndex >= pCurList->start + pCurList->count) {
1563             pCurList = NULL;
1564             FX_INT32 iStart = 0;
1565             FX_INT32 iEnd = m_DataLists.GetUpperBound();
1566             FX_INT32 iMid = 0;
1567             while (iStart <= iEnd) {
1568                 iMid = (iStart + iEnd) / 2;
1569                 DataList* list = m_DataLists.GetDataPtr(iMid);
1570                 if (nIndex < list->start) {
1571                     iEnd = iMid - 1;
1572                 } else if (nIndex >= list->start + list->count) {
1573                     iStart = iMid + 1;
1574                 } else {
1575                     pCurList = list;
1576                     m_CurList = iMid;
1577                     break;
1578                 }
1579             }
1580         }
1581         return pCurList ? pCurList->data + (nIndex - pCurList->start) * unit : NULL;
1582     }
1583 protected:
1584     void                        Append(const DataList& list)
1585     {
1586         FX_INT32 iStart = 0;
1587         FX_INT32 iEnd = m_DataLists.GetUpperBound();
1588         FX_INT32 iFind = 0;
1589         while (iStart <= iEnd) {
1590             FX_INT32 iMid = (iStart + iEnd) / 2;
1591             DataList* cur_list = m_DataLists.GetDataPtr(iMid);
1592             if (list.start < cur_list->start + cur_list->count) {
1593                 iEnd = iMid - 1;
1594             } else {
1595                 if (iMid == iEnd) {
1596                     iFind = iMid + 1;
1597                     break;
1598                 }
1599                 DataList* next_list = m_DataLists.GetDataPtr(iMid + 1);
1600                 if (list.start < next_list->start) {
1601                     iFind = iMid + 1;
1602                     break;
1603                 } else {
1604                     iStart = iMid + 1;
1605                 }
1606             }
1607         }
1608         m_DataLists.InsertAt(iFind, list);
1609     }
1610     FX_INT32            m_CurList;
1611     CFX_ArrayTemplate<DataList> m_DataLists;
1612 };
1613 template<typename T1, typename T2>
1614 class CFX_ListArrayTemplate : public CFX_Object
1615 {
1616 public:
1617
1618     void                        Clear()
1619     {
1620         m_Data.Clear();
1621     }
1622
1623     void                        Add(FX_INT32 nStart, FX_INT32 nCount)
1624     {
1625         m_Data.Append(nStart, nCount);
1626     }
1627
1628     T2&                         operator [] (FX_INT32 nIndex)
1629     {
1630         FX_LPBYTE data = m_Data.GetAt(nIndex);
1631         FXSYS_assert(data != NULL);
1632         return (T2&)(*(volatile T2*)data);
1633     }
1634
1635     T2*                         GetPtrAt(FX_INT32 nIndex)
1636     {
1637         return (T2*)m_Data.GetAt(nIndex);
1638     }
1639 protected:
1640     T1                  m_Data;
1641 };
1642 typedef CFX_ListArrayTemplate<CFX_SortListArray<sizeof(FX_FILESIZE)>, FX_FILESIZE>      CFX_FileSizeListArray;
1643 typedef CFX_ListArrayTemplate<CFX_SortListArray<sizeof(FX_DWORD)>, FX_DWORD>            CFX_DWordListArray;
1644 typedef enum {
1645     Ready,
1646     ToBeContinued,
1647     Found,
1648     NotFound,
1649     Failed,
1650     Done
1651 } FX_ProgressiveStatus;
1652 #define ProgressiveStatus       FX_ProgressiveStatus
1653 #define FX_NAMESPACE_DECLARE(namespace, type)       namespace::type
1654 #endif