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