Cleanup: Remove unused CPDF_Stream::Clone().
[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  public:
32   CFX_BinaryBuf();
33   CFX_BinaryBuf(FX_STRSIZE size);
34
35   ~CFX_BinaryBuf();
36
37   void Clear();
38
39   void EstimateSize(FX_STRSIZE size, FX_STRSIZE alloc_step = 0);
40
41   void AppendBlock(const void* pBuf, FX_STRSIZE size);
42
43   void AppendFill(uint8_t byte, FX_STRSIZE count);
44
45   void AppendString(const CFX_ByteStringC& str) {
46     AppendBlock(str.GetPtr(), str.GetLength());
47   }
48
49   inline void AppendByte(uint8_t byte) {
50     if (m_AllocSize <= m_DataSize) {
51       ExpandBuf(1);
52     }
53     m_pBuffer[m_DataSize++] = byte;
54   }
55
56   void InsertBlock(FX_STRSIZE pos, const void* pBuf, FX_STRSIZE size);
57
58   void AttachData(void* pBuf, FX_STRSIZE size);
59
60   void CopyData(const void* pBuf, FX_STRSIZE size);
61
62   void TakeOver(CFX_BinaryBuf& other);
63
64   void Delete(int start_index, int count);
65
66   uint8_t* GetBuffer() const { return m_pBuffer; }
67
68   FX_STRSIZE GetSize() const { return m_DataSize; }
69
70   CFX_ByteStringC GetByteString() const;
71
72   void DetachBuffer();
73
74  protected:
75   FX_STRSIZE m_AllocStep;
76
77   uint8_t* m_pBuffer;
78
79   FX_STRSIZE m_DataSize;
80
81   FX_STRSIZE m_AllocSize;
82
83   void ExpandBuf(FX_STRSIZE size);
84 };
85 class CFX_ByteTextBuf : public CFX_BinaryBuf {
86  public:
87   void operator=(const CFX_ByteStringC& str);
88
89   void AppendChar(int ch) { AppendByte((uint8_t)ch); }
90
91   CFX_ByteTextBuf& operator<<(int i);
92
93   CFX_ByteTextBuf& operator<<(FX_DWORD i);
94
95   CFX_ByteTextBuf& operator<<(double f);
96
97   CFX_ByteTextBuf& operator<<(const CFX_ByteStringC& lpsz);
98
99   CFX_ByteTextBuf& operator<<(const CFX_ByteTextBuf& buf);
100
101   FX_STRSIZE GetLength() const { return m_DataSize; }
102 };
103 class CFX_WideTextBuf : public CFX_BinaryBuf {
104  public:
105   void operator=(const FX_WCHAR* lpsz);
106
107   void operator=(const CFX_WideStringC& str);
108
109   void AppendChar(FX_WCHAR wch);
110
111   CFX_WideTextBuf& operator<<(int i);
112
113   CFX_WideTextBuf& operator<<(double f);
114
115   CFX_WideTextBuf& operator<<(const FX_WCHAR* lpsz);
116
117   CFX_WideTextBuf& operator<<(const CFX_WideStringC& str);
118   CFX_WideTextBuf& operator<<(const CFX_WideString& str);
119
120   CFX_WideTextBuf& operator<<(const CFX_WideTextBuf& buf);
121
122   FX_STRSIZE GetLength() const { return m_DataSize / sizeof(FX_WCHAR); }
123
124   FX_WCHAR* GetBuffer() const { return (FX_WCHAR*)m_pBuffer; }
125
126   void Delete(int start_index, int count) {
127     CFX_BinaryBuf::Delete(start_index * sizeof(FX_WCHAR),
128                           count * sizeof(FX_WCHAR));
129   }
130
131   CFX_WideStringC GetWideString() const;
132 };
133
134 class IFX_BufferArchive {
135  public:
136   IFX_BufferArchive(FX_STRSIZE size);
137   virtual ~IFX_BufferArchive() {}
138
139   virtual void Clear();
140
141   FX_BOOL Flush();
142
143   int32_t AppendBlock(const void* pBuf, size_t size);
144
145   int32_t AppendByte(uint8_t byte);
146
147   int32_t AppendDWord(FX_DWORD i);
148
149   int32_t AppendString(const CFX_ByteStringC& lpsz);
150
151  protected:
152   virtual FX_BOOL DoWork(const void* pBuf, size_t size) = 0;
153
154   FX_STRSIZE m_BufSize;
155
156   uint8_t* m_pBuffer;
157
158   FX_STRSIZE m_Length;
159 };
160
161 class CFX_FileBufferArchive : public IFX_BufferArchive {
162  public:
163   CFX_FileBufferArchive(FX_STRSIZE size = 32768);
164   ~CFX_FileBufferArchive() override;
165
166   void Clear() override;
167   FX_BOOL AttachFile(IFX_StreamWrite* pFile, FX_BOOL bTakeover = FALSE);
168
169  private:
170   FX_BOOL DoWork(const void* pBuf, size_t size) override;
171
172   IFX_StreamWrite* m_pFile;
173   FX_BOOL m_bTakeover;
174 };
175
176 struct CFX_CharMap {
177   static CFX_CharMap* GetDefaultMapper(int32_t codepage = 0);
178
179   CFX_WideString (*m_GetWideString)(CFX_CharMap* pMap,
180                                     const CFX_ByteString& bstr);
181
182   CFX_ByteString (*m_GetByteString)(CFX_CharMap* pMap,
183                                     const CFX_WideString& wstr);
184
185   int32_t (*m_GetCodePage)();
186 };
187 class CFX_UTF8Decoder {
188  public:
189   CFX_UTF8Decoder() { m_PendingBytes = 0; }
190
191   void Clear();
192
193   void Input(uint8_t byte);
194
195   void AppendChar(FX_DWORD ch);
196
197   void ClearStatus() { m_PendingBytes = 0; }
198
199   CFX_WideStringC GetResult() const { return m_Buffer.GetWideString(); }
200
201  protected:
202   int m_PendingBytes;
203
204   FX_DWORD m_PendingChar;
205
206   CFX_WideTextBuf m_Buffer;
207 };
208 class CFX_UTF8Encoder {
209  public:
210   CFX_UTF8Encoder() { m_UTF16First = 0; }
211
212   void Input(FX_WCHAR unicode);
213
214   void AppendStr(const CFX_ByteStringC& str) {
215     m_UTF16First = 0;
216     m_Buffer << str;
217   }
218
219   CFX_ByteStringC GetResult() const { return m_Buffer.GetByteString(); }
220
221  protected:
222   CFX_ByteTextBuf m_Buffer;
223
224   FX_DWORD m_UTF16First;
225 };
226 CFX_ByteString FX_UrlEncode(const CFX_WideString& wsUrl);
227 CFX_WideString FX_UrlDecode(const CFX_ByteString& bsUrl);
228 CFX_ByteString FX_EncodeURI(const CFX_WideString& wsURI);
229 CFX_WideString FX_DecodeURI(const CFX_ByteString& bsURI);
230 class CFX_BasicArray {
231  protected:
232   CFX_BasicArray(int unit_size);
233
234   ~CFX_BasicArray();
235
236   FX_BOOL SetSize(int nNewSize);
237
238   FX_BOOL Append(const CFX_BasicArray& src);
239
240   FX_BOOL Copy(const CFX_BasicArray& src);
241
242   uint8_t* InsertSpaceAt(int nIndex, int nCount);
243
244   FX_BOOL RemoveAt(int nIndex, int nCount);
245
246   FX_BOOL InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray);
247
248   const void* GetDataPtr(int index) const;
249
250  protected:
251   uint8_t* m_pData;
252
253   int m_nSize;
254
255   int m_nMaxSize;
256
257   int m_nUnitSize;
258 };
259 template <class TYPE>
260 class CFX_ArrayTemplate : public CFX_BasicArray {
261  public:
262   CFX_ArrayTemplate() : CFX_BasicArray(sizeof(TYPE)) {}
263
264   int GetSize() const { return m_nSize; }
265
266   int GetUpperBound() const { return m_nSize - 1; }
267
268   FX_BOOL SetSize(int nNewSize) { return CFX_BasicArray::SetSize(nNewSize); }
269
270   void RemoveAll() { SetSize(0); }
271
272   const TYPE GetAt(int nIndex) const {
273     if (nIndex < 0 || nIndex >= m_nSize) {
274       return (const TYPE&)(*(volatile const TYPE*)NULL);
275     }
276     return ((const TYPE*)m_pData)[nIndex];
277   }
278
279   FX_BOOL SetAt(int nIndex, TYPE newElement) {
280     if (nIndex < 0 || nIndex >= m_nSize) {
281       return FALSE;
282     }
283     ((TYPE*)m_pData)[nIndex] = newElement;
284     return TRUE;
285   }
286
287   TYPE& ElementAt(int nIndex) {
288     if (nIndex < 0 || nIndex >= m_nSize) {
289       return *(TYPE*)NULL;
290     }
291     return ((TYPE*)m_pData)[nIndex];
292   }
293
294   const TYPE* GetData() const { return (const TYPE*)m_pData; }
295
296   TYPE* GetData() { return (TYPE*)m_pData; }
297
298   FX_BOOL SetAtGrow(int nIndex, TYPE newElement) {
299     if (nIndex < 0) {
300       return FALSE;
301     }
302     if (nIndex >= m_nSize)
303       if (!SetSize(nIndex + 1)) {
304         return FALSE;
305       }
306     ((TYPE*)m_pData)[nIndex] = newElement;
307     return TRUE;
308   }
309
310   FX_BOOL Add(TYPE newElement) {
311     if (m_nSize < m_nMaxSize) {
312       m_nSize++;
313     } else if (!SetSize(m_nSize + 1)) {
314       return FALSE;
315     }
316     ((TYPE*)m_pData)[m_nSize - 1] = newElement;
317     return TRUE;
318   }
319
320   FX_BOOL Append(const CFX_ArrayTemplate& src) {
321     return CFX_BasicArray::Append(src);
322   }
323
324   FX_BOOL Copy(const CFX_ArrayTemplate& src) {
325     return CFX_BasicArray::Copy(src);
326   }
327
328   TYPE* GetDataPtr(int index) {
329     return (TYPE*)CFX_BasicArray::GetDataPtr(index);
330   }
331
332   TYPE* AddSpace() { return (TYPE*)CFX_BasicArray::InsertSpaceAt(m_nSize, 1); }
333
334   TYPE* InsertSpaceAt(int nIndex, int nCount) {
335     return (TYPE*)CFX_BasicArray::InsertSpaceAt(nIndex, nCount);
336   }
337
338   const TYPE operator[](int nIndex) const {
339     if (nIndex < 0 || nIndex >= m_nSize) {
340       *(volatile char*)0 = '\0';
341     }
342     return ((const TYPE*)m_pData)[nIndex];
343   }
344
345   TYPE& operator[](int nIndex) {
346     if (nIndex < 0 || nIndex >= m_nSize) {
347       *(volatile char*)0 = '\0';
348     }
349     return ((TYPE*)m_pData)[nIndex];
350   }
351
352   FX_BOOL InsertAt(int nIndex, TYPE newElement, int nCount = 1) {
353     if (!InsertSpaceAt(nIndex, nCount)) {
354       return FALSE;
355     }
356     while (nCount--) {
357       ((TYPE*)m_pData)[nIndex++] = newElement;
358     }
359     return TRUE;
360   }
361
362   FX_BOOL RemoveAt(int nIndex, int nCount = 1) {
363     return CFX_BasicArray::RemoveAt(nIndex, nCount);
364   }
365
366   FX_BOOL InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray) {
367     return CFX_BasicArray::InsertAt(nStartIndex, pNewArray);
368   }
369
370   int Find(TYPE data, int iStart = 0) const {
371     if (iStart < 0) {
372       return -1;
373     }
374     for (; iStart < (int)m_nSize; iStart++)
375       if (((TYPE*)m_pData)[iStart] == data) {
376         return iStart;
377       }
378     return -1;
379   }
380 };
381 typedef CFX_ArrayTemplate<uint8_t> CFX_ByteArray;
382 typedef CFX_ArrayTemplate<FX_WORD> CFX_WordArray;
383 typedef CFX_ArrayTemplate<FX_DWORD> CFX_DWordArray;
384 typedef CFX_ArrayTemplate<void*> CFX_PtrArray;
385 typedef CFX_ArrayTemplate<FX_FILESIZE> CFX_FileSizeArray;
386 typedef CFX_ArrayTemplate<FX_FLOAT> CFX_FloatArray;
387 typedef CFX_ArrayTemplate<int32_t> CFX_Int32Array;
388 template <class ObjectClass>
389 class CFX_ObjectArray : public CFX_BasicArray {
390  public:
391   CFX_ObjectArray() : CFX_BasicArray(sizeof(ObjectClass)) {}
392
393   ~CFX_ObjectArray() { RemoveAll(); }
394
395   void Add(const ObjectClass& data) {
396     new ((void*)InsertSpaceAt(m_nSize, 1)) ObjectClass(data);
397   }
398
399   ObjectClass& Add() {
400     return *(ObjectClass*)new ((void*)InsertSpaceAt(m_nSize, 1)) ObjectClass();
401   }
402
403   void* AddSpace() { return InsertSpaceAt(m_nSize, 1); }
404
405   int32_t Append(const CFX_ObjectArray& src,
406                  int32_t nStart = 0,
407                  int32_t nCount = -1) {
408     if (nCount == 0) {
409       return 0;
410     }
411     int32_t nSize = src.GetSize();
412     if (!nSize) {
413       return 0;
414     }
415     FXSYS_assert(nStart > -1 && nStart < nSize);
416     if (nCount < 0) {
417       nCount = nSize;
418     }
419     if (nStart + nCount > nSize) {
420       nCount = nSize - nStart;
421     }
422     if (nCount < 1) {
423       return 0;
424     }
425     nSize = m_nSize;
426     InsertSpaceAt(m_nSize, nCount);
427     ObjectClass* pStartObj = (ObjectClass*)GetDataPtr(nSize);
428     nSize = nStart + nCount;
429     for (int32_t i = nStart; i < nSize; i++, pStartObj++) {
430       new ((void*)pStartObj) ObjectClass(src[i]);
431     }
432     return nCount;
433   }
434
435   int32_t Copy(const CFX_ObjectArray& src,
436                int32_t nStart = 0,
437                int32_t nCount = -1) {
438     if (nCount == 0) {
439       return 0;
440     }
441     int32_t nSize = src.GetSize();
442     if (!nSize) {
443       return 0;
444     }
445     FXSYS_assert(nStart > -1 && nStart < nSize);
446     if (nCount < 0) {
447       nCount = nSize;
448     }
449     if (nStart + nCount > nSize) {
450       nCount = nSize - nStart;
451     }
452     if (nCount < 1) {
453       return 0;
454     }
455     RemoveAll();
456     SetSize(nCount);
457     ObjectClass* pStartObj = (ObjectClass*)m_pData;
458     nSize = nStart + nCount;
459     for (int32_t i = nStart; i < nSize; i++, pStartObj++) {
460       new ((void*)pStartObj) ObjectClass(src[i]);
461     }
462     return nCount;
463   }
464
465   int GetSize() const { return m_nSize; }
466
467   ObjectClass& operator[](int index) const {
468     FXSYS_assert(index < m_nSize);
469     return *(ObjectClass*)CFX_BasicArray::GetDataPtr(index);
470   }
471
472   ObjectClass* GetDataPtr(int index) {
473     return (ObjectClass*)CFX_BasicArray::GetDataPtr(index);
474   }
475
476   void RemoveAt(int index) {
477     FXSYS_assert(index < m_nSize);
478     ((ObjectClass*)GetDataPtr(index))->~ObjectClass();
479     CFX_BasicArray::RemoveAt(index, 1);
480   }
481
482   void RemoveAll() {
483     for (int i = 0; i < m_nSize; i++) {
484       ((ObjectClass*)GetDataPtr(i))->~ObjectClass();
485     }
486     CFX_BasicArray::SetSize(0);
487   }
488 };
489 typedef CFX_ObjectArray<CFX_ByteString> CFX_ByteStringArray;
490 typedef CFX_ObjectArray<CFX_WideString> CFX_WideStringArray;
491 class CFX_BaseSegmentedArray {
492  public:
493   CFX_BaseSegmentedArray(int unit_size = 1,
494                          int segment_units = 512,
495                          int index_size = 8);
496
497   ~CFX_BaseSegmentedArray();
498
499   void SetUnitSize(int unit_size, int segment_units, int index_size = 8);
500
501   void* Add();
502
503   void* GetAt(int index) const;
504
505   void RemoveAll();
506
507   void Delete(int index, int count = 1);
508
509   int GetSize() const { return m_DataSize; }
510
511   int GetSegmentSize() const { return m_SegmentSize; }
512
513   int GetUnitSize() const { return m_UnitSize; }
514
515   void* Iterate(FX_BOOL (*callback)(void* param, void* pData),
516                 void* param) const;
517
518  private:
519   int m_UnitSize;
520
521   short m_SegmentSize;
522
523   uint8_t m_IndexSize;
524
525   uint8_t m_IndexDepth;
526
527   int m_DataSize;
528
529   void* m_pIndex;
530   void** GetIndex(int seg_index) const;
531   void* IterateIndex(int level,
532                      int& start,
533                      void** pIndex,
534                      FX_BOOL (*callback)(void* param, void* pData),
535                      void* param) const;
536   void* IterateSegment(const uint8_t* pSegment,
537                        int count,
538                        FX_BOOL (*callback)(void* param, void* pData),
539                        void* param) const;
540 };
541 template <class ElementType>
542 class CFX_SegmentedArray : public CFX_BaseSegmentedArray {
543  public:
544   CFX_SegmentedArray(int segment_units, int index_size = 8)
545       : CFX_BaseSegmentedArray(sizeof(ElementType), segment_units, index_size) {
546   }
547
548   void Add(ElementType data) {
549     *(ElementType*)CFX_BaseSegmentedArray::Add() = data;
550   }
551
552   ElementType& operator[](int index) {
553     return *(ElementType*)CFX_BaseSegmentedArray::GetAt(index);
554   }
555 };
556 template <class DataType, int FixedSize>
557 class CFX_FixedBufGrow {
558  public:
559   CFX_FixedBufGrow() : m_pData(NULL) {}
560   CFX_FixedBufGrow(int data_size) : m_pData(NULL) {
561     if (data_size > FixedSize) {
562       m_pData = FX_Alloc(DataType, data_size);
563     } else {
564       FXSYS_memset(m_Data, 0, sizeof(DataType) * FixedSize);
565     }
566   }
567   void SetDataSize(int data_size) {
568     if (m_pData) {
569       FX_Free(m_pData);
570     }
571     m_pData = NULL;
572     if (data_size > FixedSize) {
573       m_pData = FX_Alloc(DataType, data_size);
574     } else {
575       FXSYS_memset(m_Data, 0, sizeof(DataType) * FixedSize);
576     }
577   }
578   ~CFX_FixedBufGrow() {
579     if (m_pData) {
580       FX_Free(m_pData);
581     }
582   }
583   operator DataType*() { return m_pData ? m_pData : m_Data; }
584
585  private:
586   DataType m_Data[FixedSize];
587   DataType* m_pData;
588 };
589 class CFX_MapPtrToPtr {
590  protected:
591   struct CAssoc {
592     CAssoc* pNext;
593
594     void* key;
595
596     void* value;
597   };
598
599  public:
600   CFX_MapPtrToPtr(int nBlockSize = 10);
601
602   ~CFX_MapPtrToPtr();
603
604   int GetCount() const { return m_nCount; }
605
606   FX_BOOL IsEmpty() const { return m_nCount == 0; }
607
608   FX_BOOL Lookup(void* key, void*& rValue) const;
609
610   void* GetValueAt(void* key) const;
611
612   void*& operator[](void* key);
613
614   void SetAt(void* key, void* newValue) { (*this)[key] = newValue; }
615
616   FX_BOOL RemoveKey(void* key);
617
618   void RemoveAll();
619
620   FX_POSITION GetStartPosition() const {
621     return (m_nCount == 0) ? NULL : (FX_POSITION)-1;
622   }
623
624   void GetNextAssoc(FX_POSITION& rNextPosition,
625                     void*& rKey,
626                     void*& rValue) const;
627
628   FX_DWORD GetHashTableSize() const { return m_nHashTableSize; }
629
630   void InitHashTable(FX_DWORD hashSize, FX_BOOL bAllocNow = TRUE);
631
632  protected:
633   CAssoc** m_pHashTable;
634
635   FX_DWORD m_nHashTableSize;
636
637   int m_nCount;
638
639   CAssoc* m_pFreeList;
640
641   struct CFX_Plex* m_pBlocks;
642
643   int m_nBlockSize;
644
645   FX_DWORD HashKey(void* key) const;
646
647   CAssoc* NewAssoc();
648
649   void FreeAssoc(CAssoc* pAssoc);
650
651   CAssoc* GetAssocAt(void* key, FX_DWORD& hash) const;
652 };
653
654 class CFX_CMapDWordToDWord {
655  public:
656   FX_BOOL Lookup(FX_DWORD key, FX_DWORD& value) const;
657
658   void SetAt(FX_DWORD key, FX_DWORD value);
659
660   void EstimateSize(FX_DWORD size, FX_DWORD grow_by);
661
662   FX_POSITION GetStartPosition() const;
663
664   void GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const;
665
666  protected:
667   CFX_BinaryBuf m_Buffer;
668 };
669 class CFX_MapByteStringToPtr {
670  protected:
671   struct CAssoc {
672     CAssoc* pNext;
673
674     FX_DWORD nHashValue;
675
676     CFX_ByteString key;
677
678     void* value;
679   };
680
681  public:
682   CFX_MapByteStringToPtr(int nBlockSize = 10);
683
684   int GetCount() const { return m_nCount; }
685
686   FX_BOOL IsEmpty() const { return m_nCount == 0; }
687
688   FX_BOOL Lookup(const CFX_ByteStringC& key, void*& rValue) const;
689
690   void*& operator[](const CFX_ByteStringC& key);
691
692   void SetAt(const CFX_ByteStringC& key, void* newValue) {
693     (*this)[key] = newValue;
694   }
695
696   FX_BOOL RemoveKey(const CFX_ByteStringC& key);
697
698   void RemoveAll();
699
700   FX_POSITION GetStartPosition() const {
701     return (m_nCount == 0) ? NULL : (FX_POSITION)-1;
702   }
703
704   void GetNextAssoc(FX_POSITION& rNextPosition,
705                     CFX_ByteString& rKey,
706                     void*& rValue) const;
707
708   void* GetNextValue(FX_POSITION& rNextPosition) const;
709
710   FX_DWORD GetHashTableSize() const { return m_nHashTableSize; }
711
712   void InitHashTable(FX_DWORD hashSize, FX_BOOL bAllocNow = TRUE);
713
714   FX_DWORD HashKey(const CFX_ByteStringC& key) const;
715
716  protected:
717   CAssoc** m_pHashTable;
718
719   FX_DWORD m_nHashTableSize;
720
721   int m_nCount;
722
723   CAssoc* m_pFreeList;
724
725   struct CFX_Plex* m_pBlocks;
726
727   int m_nBlockSize;
728
729   CAssoc* NewAssoc();
730
731   void FreeAssoc(CAssoc* pAssoc);
732
733   CAssoc* GetAssocAt(const CFX_ByteStringC& key, FX_DWORD& hash) const;
734
735  public:
736   ~CFX_MapByteStringToPtr();
737 };
738 class CFX_CMapByteStringToPtr {
739  public:
740   CFX_CMapByteStringToPtr();
741
742   ~CFX_CMapByteStringToPtr();
743
744   void RemoveAll();
745
746   FX_POSITION GetStartPosition() const;
747
748   void GetNextAssoc(FX_POSITION& rNextPosition,
749                     CFX_ByteString& rKey,
750                     void*& rValue) const;
751
752   void* GetNextValue(FX_POSITION& rNextPosition) const;
753
754   FX_BOOL Lookup(const CFX_ByteStringC& key, void*& rValue) const;
755
756   void SetAt(const CFX_ByteStringC& key, void* value);
757
758   void RemoveKey(const CFX_ByteStringC& key);
759
760   int GetCount() const;
761
762   void AddValue(const CFX_ByteStringC& key, void* pValue);
763
764  private:
765   CFX_BaseSegmentedArray m_Buffer;
766 };
767 class CFX_PtrList {
768  protected:
769   struct CNode {
770     CNode* pNext;
771
772     CNode* pPrev;
773
774     void* data;
775   };
776
777  public:
778   CFX_PtrList(int nBlockSize = 10);
779
780   FX_POSITION GetHeadPosition() const { return (FX_POSITION)m_pNodeHead; }
781
782   FX_POSITION GetTailPosition() const { return (FX_POSITION)m_pNodeTail; }
783
784   void* GetNext(FX_POSITION& rPosition) const {
785     CNode* pNode = (CNode*)rPosition;
786     rPosition = (FX_POSITION)pNode->pNext;
787     return pNode->data;
788   }
789
790   void* GetPrev(FX_POSITION& rPosition) const {
791     CNode* pNode = (CNode*)rPosition;
792     rPosition = (FX_POSITION)pNode->pPrev;
793     return pNode->data;
794   }
795
796   FX_POSITION GetNextPosition(FX_POSITION pos) const {
797     return ((CNode*)pos)->pNext;
798   }
799
800   FX_POSITION GetPrevPosition(FX_POSITION pos) const {
801     return ((CNode*)pos)->pPrev;
802   }
803
804   void* GetAt(FX_POSITION rPosition) const {
805     CNode* pNode = (CNode*)rPosition;
806     return pNode->data;
807   }
808
809   int GetCount() const { return m_nCount; }
810
811   FX_POSITION AddTail(void* newElement);
812
813   FX_POSITION AddHead(void* newElement);
814
815   void SetAt(FX_POSITION pos, void* newElement) {
816     CNode* pNode = (CNode*)pos;
817     pNode->data = newElement;
818   }
819
820   FX_POSITION InsertAfter(FX_POSITION pos, void* newElement);
821
822   FX_POSITION Find(void* searchValue, FX_POSITION startAfter = NULL) const;
823
824   FX_POSITION FindIndex(int index) const;
825
826   void RemoveAt(FX_POSITION pos);
827
828   void RemoveAll();
829
830  protected:
831   CNode* m_pNodeHead;
832
833   CNode* m_pNodeTail;
834
835   int m_nCount;
836
837   CNode* m_pNodeFree;
838
839   struct CFX_Plex* m_pBlocks;
840
841   int m_nBlockSize;
842
843   CNode* NewNode(CNode* pPrev, CNode* pNext);
844
845   void FreeNode(CNode* pNode);
846
847  public:
848   ~CFX_PtrList();
849 };
850 typedef void (*PD_CALLBACK_FREEDATA)(void* pData);
851 struct FX_PRIVATEDATA {
852   void FreeData();
853
854   void* m_pModuleId;
855
856   void* m_pData;
857
858   PD_CALLBACK_FREEDATA m_pCallback;
859
860   FX_BOOL m_bSelfDestruct;
861 };
862 class CFX_PrivateData {
863  public:
864   ~CFX_PrivateData();
865
866   void ClearAll();
867
868   void SetPrivateData(void* module_id,
869                       void* pData,
870                       PD_CALLBACK_FREEDATA callback);
871
872   void SetPrivateObj(void* module_id, CFX_DestructObject* pObj);
873
874   void* GetPrivateData(void* module_id);
875
876   FX_BOOL LookupPrivateData(void* module_id, void*& pData) const {
877     if (!module_id) {
878       return FALSE;
879     }
880     FX_DWORD nCount = m_DataList.GetSize();
881     for (FX_DWORD n = 0; n < nCount; n++) {
882       if (m_DataList[n].m_pModuleId == module_id) {
883         pData = m_DataList[n].m_pData;
884         return TRUE;
885       }
886     }
887     return FALSE;
888   }
889
890   FX_BOOL RemovePrivateData(void* module_id);
891
892  protected:
893   CFX_ArrayTemplate<FX_PRIVATEDATA> m_DataList;
894
895   void AddData(void* module_id,
896                void* pData,
897                PD_CALLBACK_FREEDATA callback,
898                FX_BOOL bSelfDestruct);
899 };
900 class CFX_BitStream {
901  public:
902   void Init(const uint8_t* pData, FX_DWORD dwSize);
903
904   FX_DWORD GetBits(FX_DWORD nBits);
905
906   void ByteAlign();
907
908   FX_BOOL IsEOF() { return m_BitPos >= m_BitSize; }
909
910   void SkipBits(FX_DWORD nBits) { m_BitPos += nBits; }
911
912   void Rewind() { m_BitPos = 0; }
913
914  protected:
915   FX_DWORD m_BitPos;
916
917   FX_DWORD m_BitSize;
918
919   const uint8_t* m_pData;
920 };
921 template <class ObjClass>
922 class CFX_CountRef {
923  public:
924   typedef CFX_CountRef<ObjClass> Ref;
925
926   class CountedObj : public ObjClass {
927    public:
928     CountedObj() {}
929
930     CountedObj(const CountedObj& src) : ObjClass(src) {}
931
932     int m_RefCount;
933   };
934
935   CFX_CountRef() { m_pObject = NULL; }
936
937   CFX_CountRef(const Ref& ref) {
938     m_pObject = ref.m_pObject;
939     if (m_pObject) {
940       m_pObject->m_RefCount++;
941     }
942   }
943
944   ~CFX_CountRef() {
945     if (!m_pObject) {
946       return;
947     }
948     m_pObject->m_RefCount--;
949     if (m_pObject->m_RefCount <= 0) {
950       delete m_pObject;
951     }
952   }
953
954   ObjClass* New() {
955     if (m_pObject) {
956       m_pObject->m_RefCount--;
957       if (m_pObject->m_RefCount <= 0) {
958         delete m_pObject;
959       }
960     }
961     m_pObject = new CountedObj;
962     m_pObject->m_RefCount = 1;
963     return m_pObject;
964   }
965
966   void operator=(const Ref& ref) {
967     if (ref.m_pObject) {
968       ref.m_pObject->m_RefCount++;
969     }
970     if (m_pObject) {
971       m_pObject->m_RefCount--;
972       if (m_pObject->m_RefCount <= 0) {
973         delete m_pObject;
974       }
975     }
976     m_pObject = ref.m_pObject;
977   }
978
979   void operator=(void* p) {
980     FXSYS_assert(p == 0);
981     if (m_pObject == NULL) {
982       return;
983     }
984     m_pObject->m_RefCount--;
985     if (m_pObject->m_RefCount <= 0) {
986       delete m_pObject;
987     }
988     m_pObject = NULL;
989   }
990
991   const ObjClass* GetObject() const { return m_pObject; }
992
993   operator const ObjClass*() const { return m_pObject; }
994
995   FX_BOOL IsNull() const { return m_pObject == NULL; }
996
997   FX_BOOL NotNull() const { return m_pObject != NULL; }
998
999   ObjClass* GetModify() {
1000     if (m_pObject == NULL) {
1001       m_pObject = new CountedObj;
1002       m_pObject->m_RefCount = 1;
1003     } else if (m_pObject->m_RefCount > 1) {
1004       m_pObject->m_RefCount--;
1005       CountedObj* pOldObject = m_pObject;
1006       m_pObject = new CountedObj(*pOldObject);
1007       m_pObject->m_RefCount = 1;
1008     }
1009     return m_pObject;
1010   }
1011
1012   void SetNull() {
1013     if (m_pObject == NULL) {
1014       return;
1015     }
1016     m_pObject->m_RefCount--;
1017     if (m_pObject->m_RefCount <= 0) {
1018       delete m_pObject;
1019     }
1020     m_pObject = NULL;
1021   }
1022
1023   FX_BOOL operator==(const Ref& ref) const {
1024     return m_pObject == ref.m_pObject;
1025   }
1026
1027  protected:
1028   CountedObj* m_pObject;
1029 };
1030 class IFX_Pause {
1031  public:
1032   virtual ~IFX_Pause() {}
1033   virtual FX_BOOL NeedToPauseNow() = 0;
1034 };
1035
1036 template <typename T>
1037 class CFX_AutoRestorer {
1038  public:
1039   explicit CFX_AutoRestorer(T* location) {
1040     m_Location = location;
1041     m_OldValue = *location;
1042   }
1043   ~CFX_AutoRestorer() { *m_Location = m_OldValue; }
1044
1045  private:
1046   T* m_Location;
1047   T m_OldValue;
1048 };
1049
1050 template <class T>
1051 class CFX_SmartPointer {
1052  public:
1053   CFX_SmartPointer(T* pObj) : m_pObj(pObj) {}
1054   ~CFX_SmartPointer() { m_pObj->Release(); }
1055   T* Get(void) { return m_pObj; }
1056   T& operator*(void) { return *m_pObj; }
1057   T* operator->(void) { return m_pObj; }
1058
1059  protected:
1060   T* m_pObj;
1061 };
1062 #define FX_DATALIST_LENGTH 1024
1063 template <size_t unit>
1064 class CFX_SortListArray {
1065  protected:
1066   struct DataList {
1067     int32_t start;
1068
1069     int32_t count;
1070     uint8_t* data;
1071   };
1072
1073  public:
1074   CFX_SortListArray() : m_CurList(0) {}
1075
1076   ~CFX_SortListArray() { Clear(); }
1077
1078   void Clear() {
1079     for (int32_t i = m_DataLists.GetUpperBound(); i >= 0; i--) {
1080       DataList list = m_DataLists.ElementAt(i);
1081       if (list.data) {
1082         FX_Free(list.data);
1083       }
1084     }
1085     m_DataLists.RemoveAll();
1086     m_CurList = 0;
1087   }
1088
1089   void Append(int32_t nStart, int32_t nCount) {
1090     if (nStart < 0) {
1091       return;
1092     }
1093     while (nCount > 0) {
1094       int32_t temp_count = FX_MIN(nCount, FX_DATALIST_LENGTH);
1095       DataList list;
1096       list.data = FX_Alloc2D(uint8_t, temp_count, unit);
1097       list.start = nStart;
1098       list.count = temp_count;
1099       Append(list);
1100       nCount -= temp_count;
1101       nStart += temp_count;
1102     }
1103   }
1104
1105   uint8_t* GetAt(int32_t nIndex) {
1106     if (nIndex < 0) {
1107       return NULL;
1108     }
1109     if (m_CurList < 0 || m_CurList >= m_DataLists.GetSize()) {
1110       return NULL;
1111     }
1112     DataList* pCurList = m_DataLists.GetDataPtr(m_CurList);
1113     if (!pCurList || nIndex < pCurList->start ||
1114         nIndex >= pCurList->start + pCurList->count) {
1115       pCurList = NULL;
1116       int32_t iStart = 0;
1117       int32_t iEnd = m_DataLists.GetUpperBound();
1118       int32_t iMid = 0;
1119       while (iStart <= iEnd) {
1120         iMid = (iStart + iEnd) / 2;
1121         DataList* list = m_DataLists.GetDataPtr(iMid);
1122         if (nIndex < list->start) {
1123           iEnd = iMid - 1;
1124         } else if (nIndex >= list->start + list->count) {
1125           iStart = iMid + 1;
1126         } else {
1127           pCurList = list;
1128           m_CurList = iMid;
1129           break;
1130         }
1131       }
1132     }
1133     return pCurList ? pCurList->data + (nIndex - pCurList->start) * unit : NULL;
1134   }
1135
1136  protected:
1137   void Append(const DataList& list) {
1138     int32_t iStart = 0;
1139     int32_t iEnd = m_DataLists.GetUpperBound();
1140     int32_t iFind = 0;
1141     while (iStart <= iEnd) {
1142       int32_t iMid = (iStart + iEnd) / 2;
1143       DataList* cur_list = m_DataLists.GetDataPtr(iMid);
1144       if (list.start < cur_list->start + cur_list->count) {
1145         iEnd = iMid - 1;
1146       } else {
1147         if (iMid == iEnd) {
1148           iFind = iMid + 1;
1149           break;
1150         }
1151         DataList* next_list = m_DataLists.GetDataPtr(iMid + 1);
1152         if (list.start < next_list->start) {
1153           iFind = iMid + 1;
1154           break;
1155         } else {
1156           iStart = iMid + 1;
1157         }
1158       }
1159     }
1160     m_DataLists.InsertAt(iFind, list);
1161   }
1162   int32_t m_CurList;
1163   CFX_ArrayTemplate<DataList> m_DataLists;
1164 };
1165 template <typename T1, typename T2>
1166 class CFX_ListArrayTemplate {
1167  public:
1168   void Clear() { m_Data.Clear(); }
1169
1170   void Add(int32_t nStart, int32_t nCount) { m_Data.Append(nStart, nCount); }
1171
1172   T2& operator[](int32_t nIndex) {
1173     uint8_t* data = m_Data.GetAt(nIndex);
1174     FXSYS_assert(data != NULL);
1175     return (T2&)(*(volatile T2*)data);
1176   }
1177
1178   T2* GetPtrAt(int32_t nIndex) { return (T2*)m_Data.GetAt(nIndex); }
1179
1180  protected:
1181   T1 m_Data;
1182 };
1183 typedef CFX_ListArrayTemplate<CFX_SortListArray<sizeof(FX_FILESIZE)>,
1184                               FX_FILESIZE> CFX_FileSizeListArray;
1185 typedef CFX_ListArrayTemplate<CFX_SortListArray<sizeof(FX_DWORD)>, FX_DWORD>
1186     CFX_DWordListArray;
1187 typedef enum {
1188   Ready,
1189   ToBeContinued,
1190   Found,
1191   NotFound,
1192   Failed,
1193   Done
1194 } FX_ProgressiveStatus;
1195 #define ProgressiveStatus FX_ProgressiveStatus
1196 #define FX_NAMESPACE_DECLARE(namespace, type) namespace ::type
1197
1198 class CFX_Vector_3by1 {
1199  public:
1200   CFX_Vector_3by1() : a(0.0f), b(0.0f), c(0.0f) {}
1201
1202   CFX_Vector_3by1(FX_FLOAT a1, FX_FLOAT b1, FX_FLOAT c1)
1203       : a(a1), b(b1), c(c1) {}
1204
1205   FX_FLOAT a;
1206   FX_FLOAT b;
1207   FX_FLOAT c;
1208 };
1209 class CFX_Matrix_3by3 {
1210  public:
1211   CFX_Matrix_3by3()
1212       : a(0.0f),
1213         b(0.0f),
1214         c(0.0f),
1215         d(0.0f),
1216         e(0.0f),
1217         f(0.0f),
1218         g(0.0f),
1219         h(0.0f),
1220         i(0.0f) {}
1221
1222   CFX_Matrix_3by3(FX_FLOAT a1,
1223                   FX_FLOAT b1,
1224                   FX_FLOAT c1,
1225                   FX_FLOAT d1,
1226                   FX_FLOAT e1,
1227                   FX_FLOAT f1,
1228                   FX_FLOAT g1,
1229                   FX_FLOAT h1,
1230                   FX_FLOAT i1)
1231       : a(a1), b(b1), c(c1), d(d1), e(e1), f(f1), g(g1), h(h1), i(i1) {}
1232
1233   CFX_Matrix_3by3 Inverse();
1234
1235   CFX_Matrix_3by3 Multiply(const CFX_Matrix_3by3& m);
1236
1237   CFX_Vector_3by1 TransformVector(const CFX_Vector_3by1& v);
1238
1239   FX_FLOAT a;
1240   FX_FLOAT b;
1241   FX_FLOAT c;
1242   FX_FLOAT d;
1243   FX_FLOAT e;
1244   FX_FLOAT f;
1245   FX_FLOAT g;
1246   FX_FLOAT h;
1247   FX_FLOAT i;
1248 };
1249
1250 #endif  // CORE_INCLUDE_FXCRT_FX_BASIC_H_