diff options
Diffstat (limited to 'plugins/CommonLibs/TMyArray.h')
| -rw-r--r-- | plugins/CommonLibs/TMyArray.h | 353 |
1 files changed, 353 insertions, 0 deletions
diff --git a/plugins/CommonLibs/TMyArray.h b/plugins/CommonLibs/TMyArray.h new file mode 100644 index 0000000000..68ca908fe1 --- /dev/null +++ b/plugins/CommonLibs/TMyArray.h @@ -0,0 +1,353 @@ +/*
+ TMyArray.h - TMyArray template
+ Copyright (c) 2005-2008 Chervov Dmitry
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+#pragma once
+
+#include <stdlib.h>
+
+#define ARRAY_GROWBY 4
+// if there is more than ARRAY_FREETHRESHOLD free array elements, then we're reallocating the array
+#define ARRAY_FREETHRESHOLD 16
+
+template <class T, class ARG_T = const T&, int GrowBy = ARRAY_GROWBY, int FreeThreshold = ARRAY_FREETHRESHOLD>
+class TMyArray
+{
+public:
+ TMyArray();
+ TMyArray(const TMyArray<T, ARG_T, GrowBy, FreeThreshold> &A);
+ ~TMyArray();
+
+ int GetSize() const;
+ T* GetData() const;
+ int AddElem(ARG_T pElem);
+ int Add(const T *pItems, int nItems);
+ void InsertElem(ARG_T pElem, int nInsertAt);
+ void MoveElem(int nIndex, int nMoveTo);
+ T& SetAtGrow(int nIndex);
+ int Find(ARG_T pElem); // returns an index of the specified item, or -1 if the array doesn't contain the item
+ int BinarySearch(int (*CmpFunc)(ARG_T pItem, LPARAM lParam), LPARAM lParam, int *pIndex = NULL); // returns an index of the specified item, or -1 if the array doesn't contain the item;
+ // also it's possible to specify pIndex so that even if the array doesn't contain the item, the function will set *pIndex to a position where the item can be inserted;
+ // CmpFunc must return -1, 0 and 1 depending whether pItem is lesser, equal or greater than needed;
+ // BinarySearch() requires the array to be sorted in an ascending order
+ void RemoveElem(int nIndex, int nItems = 1);
+ void RemoveAll();
+ const T& operator[](int nIndex) const;
+ T& operator[](int nIndex);
+ TMyArray<T, ARG_T, GrowBy, FreeThreshold>& operator = (const TMyArray<T, ARG_T, GrowBy, FreeThreshold> &A);
+ TMyArray<T, ARG_T, GrowBy, FreeThreshold>& operator += (const TMyArray<T, ARG_T, GrowBy, FreeThreshold> &A);
+
+private:
+ int SetAllocNum(int nNewAllocNum);
+
+ T* pData;
+ int nElemNum;
+ int nAllocNum;
+};
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+TMyArray<T, ARG_T, GrowBy, FreeThreshold>::TMyArray()
+{
+ nElemNum = 0;
+ nAllocNum = 0;
+ pData = NULL;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+TMyArray<T, ARG_T, GrowBy, FreeThreshold>::TMyArray(const TMyArray<T, ARG_T, GrowBy, FreeThreshold> &A)//: TMyArray<T, ARG_T>()
+{
+ nElemNum = 0;
+ nAllocNum = 0;
+ pData = NULL;
+ *this = A;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+TMyArray<T, ARG_T, GrowBy, FreeThreshold>::~TMyArray()
+{
+ RemoveAll();
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline int TMyArray<T, ARG_T, GrowBy, FreeThreshold>::GetSize() const
+{
+ return nElemNum;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline T* TMyArray<T, ARG_T, GrowBy, FreeThreshold>::GetData() const
+{
+ return pData;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline int TMyArray<T, ARG_T, GrowBy, FreeThreshold>::SetAllocNum(int nNewAllocNum)
+{
+ _ASSERT(nNewAllocNum >= nElemNum);
+ T*pNewData = (nNewAllocNum) ? (T*)malloc(sizeof(T) * nNewAllocNum) : NULL;
+ if (pData)
+ {
+ if (pNewData)
+ {
+ memcpy(pNewData, pData, sizeof(T) * nElemNum);
+ }
+ free(pData);
+ }
+ pData = pNewData;
+ if (!pNewData)
+ {
+ nAllocNum = 0;
+ return -1; // not enough memory?
+ } else
+ {
+ nAllocNum = nNewAllocNum;
+ return 0; // everything's ok
+ }
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline int TMyArray<T, ARG_T, GrowBy, FreeThreshold>::AddElem(ARG_T pElem)
+{
+ if (nElemNum >= nAllocNum)
+ { // reallocate memory to fit new element
+ SetAllocNum(nAllocNum + GrowBy);
+ }
+ memset(pData + nElemNum, 0, sizeof(T));
+ pData[nElemNum] = pElem;
+ return nElemNum++;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline int TMyArray<T, ARG_T, GrowBy, FreeThreshold>::Add(const T *pItems, int nItems)
+{
+ if (nElemNum + nItems > nAllocNum)
+ { // reallocate memory to fit new items
+ SetAllocNum(nAllocNum + nElemNum + nItems - 1 - ((nElemNum + nItems - 1) % GrowBy) + GrowBy);
+ }
+ memset(pData + nElemNum, 0, sizeof(T) * nItems);
+ int I;
+ for (I = 0; I < nItems; I++)
+ {
+ pData[nElemNum++] = pItems[I];
+ }
+ return nElemNum - nItems; // returns an index of the first item added
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline void TMyArray<T, ARG_T, GrowBy, FreeThreshold>::InsertElem(ARG_T pElem, int nInsertAt)
+{
+ _ASSERT(nInsertAt >= 0 && nInsertAt <= nElemNum);
+ if (nElemNum >= nAllocNum)
+ { // reallocate memory to fit new items
+ SetAllocNum(nAllocNum + GrowBy);
+ }
+ memmove(pData + nInsertAt + 1, pData + nInsertAt, sizeof(T) * (nElemNum - nInsertAt));
+ memset(pData + nInsertAt, 0, sizeof(T));
+ pData[nInsertAt] = pElem;
+ nElemNum++;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline void TMyArray<T, ARG_T, GrowBy, FreeThreshold>::MoveElem(int nIndex, int nMoveTo)
+{
+ _ASSERT(nIndex >= 0 && nIndex < nElemNum && nMoveTo >= 0 && nMoveTo < nElemNum);
+ if (nIndex == nMoveTo)
+ {
+ return; // nothing to do
+ }
+ char Elem[sizeof(T)];
+ memmove(Elem, pData + nIndex, sizeof(T));
+ if (nIndex < nMoveTo)
+ {
+ memmove(pData + nIndex, pData + nIndex + 1, sizeof(T) * (nMoveTo - nIndex));
+ } else
+ {
+ memmove(pData + nMoveTo + 1, pData + nMoveTo, sizeof(T) * (nIndex - nMoveTo));
+ }
+ memmove(pData + nMoveTo, Elem, sizeof(T));
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline T& TMyArray<T, ARG_T, GrowBy, FreeThreshold>::SetAtGrow(int nIndex)
+{
+ _ASSERT(nIndex >= 0);
+ if (nIndex < nElemNum)
+ {
+ return pData[nIndex];
+ }
+ if (nIndex >= nAllocNum)
+ {
+ if (SetAllocNum(nIndex - (nIndex % GrowBy) + GrowBy))
+ { // if there was an error
+ nElemNum = 0;
+ return *pData;
+ }
+ }
+ memset(pData + nElemNum, 0, sizeof(T) * (nIndex - nElemNum + 1));
+ nElemNum = nIndex + 1;
+ return pData[nIndex];
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline int TMyArray<T, ARG_T, GrowBy, FreeThreshold>::Find(ARG_T pElem)
+{
+ int I;
+ for (I = 0; I < nElemNum; I++)
+ {
+ if (pData[I] == pElem)
+ {
+ return I;
+ }
+ }
+ return -1;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline int TMyArray<T, ARG_T, GrowBy, FreeThreshold>::BinarySearch(int (*CmpFunc)(ARG_T pItem, LPARAM lParam), LPARAM lParam, int *pIndex)
+{
+ int L, R;
+ int CmpResult;
+ if (!nElemNum)
+ {
+ if (pIndex)
+ {
+ *pIndex = -1;
+ }
+ return -1;
+ }
+ for (L = 0, R = nElemNum; R - L > 1;)
+ {
+ int C = (L + R) >> 1; // rounds always to a lesser index if L + R is odd
+ CmpResult = CmpFunc(pData[C], lParam); // usually, CmpFunc = pData[C] - lParam; i.e. CmpFunc > 0 when pData[C] is greater than necessary, < 0 when pData[C] is less, and = 0 when pData[C] is the item we search for
+ if (CmpResult < 0)
+ {
+ L = C;
+ } else if (CmpResult > 0)
+ {
+ R = C;
+ } else
+ { // CmpResult == 0
+ if (pIndex)
+ {
+ *pIndex = C;
+ }
+ return C;
+ }
+ }
+ if (pIndex)
+ {
+ *pIndex = L;
+ }
+ CmpResult = CmpFunc(pData[L], lParam);
+ if (!CmpResult)
+ {
+ return L;
+ }
+ if (CmpResult > 0)
+ { // we don't need to check pData[R], as pData[R] > pData[L] > lParam, i.e. there are no suitable item in the array
+ return -1;
+ }
+// CmpResult < 0, we have to check pData[R] too
+ if (pIndex)
+ {
+ *pIndex = R;
+ }
+ if (R >= nElemNum)
+ {
+ return -1;
+ }
+ return CmpFunc(pData[R], lParam) ? -1 : R;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline void TMyArray<T, ARG_T, GrowBy, FreeThreshold>::RemoveElem(int nIndex, int nItems)
+{
+ _ASSERT(nIndex >= 0 && nIndex + nItems <= nElemNum);
+ if (!nItems)
+ {
+ return;
+ }
+// delete pData[nIndex];
+// ~pData[nIndex];
+ int I;
+ for (I = nIndex; I < nIndex + nItems; I++)
+ {
+ (pData + I)->~T();
+ }
+ memmove(pData + nIndex, pData + nIndex + nItems, sizeof(T) * (nElemNum - nIndex - nItems));
+ nElemNum -= nItems;
+ if (nAllocNum - nElemNum >= FreeThreshold)
+ {
+ SetAllocNum(nAllocNum - FreeThreshold);
+ }/* else
+ {
+ memset(pData + nElemNum, 0, sizeof(T));
+ }*/
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline void TMyArray<T, ARG_T, GrowBy, FreeThreshold>::RemoveAll()
+{
+ int I;
+ for (I = 0; I < nElemNum; I++)
+ {
+ //delete pData[I];
+ (pData + I)->~T();
+ }
+ nElemNum = 0;
+ SetAllocNum(0);
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline const T& TMyArray<T, ARG_T, GrowBy, FreeThreshold>::operator[](int nIndex) const
+{
+ _ASSERT(nIndex >= 0 && nIndex < nElemNum);
+ return pData[nIndex];
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline T& TMyArray<T, ARG_T, GrowBy, FreeThreshold>::operator[](int nIndex)
+{
+ _ASSERT(nIndex >= 0 && nIndex < nElemNum);
+ return pData[nIndex];
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline TMyArray<T, ARG_T, GrowBy, FreeThreshold>& TMyArray<T, ARG_T, GrowBy, FreeThreshold>::operator = (const TMyArray<T, ARG_T, GrowBy, FreeThreshold> &A)
+{
+ RemoveAll();
+ int I;
+ for (I = 0; I < A.GetSize(); I++)
+ {
+ AddElem(A[I]);
+ }
+ return *this;
+}
+
+template <class T, class ARG_T, int GrowBy, int FreeThreshold>
+__forceinline TMyArray<T, ARG_T, GrowBy, FreeThreshold>& TMyArray<T, ARG_T, GrowBy, FreeThreshold>::operator += (const TMyArray<T, ARG_T, GrowBy, FreeThreshold> &A)
+{
+ int I;
+ for (I = 0; I < A.GetSize(); I++)
+ {
+ AddElem(A[I]);
+ }
+ return *this;
+}
+
+typedef TMyArray<char, const char&, 1024, 4096> CHARARRAY;
|