Mercurial > vba-linux

     1 // PpmdSubAlloc.h

     2 // This code is based on Dmitry Shkarin's PPMdH code

     3 

     4 #ifndef __COMPRESS_PPMD_SUB_ALLOC_H

     5 #define __COMPRESS_PPMD_SUB_ALLOC_H

     6 

     7 extern "C"

     8 {

     9 #include "../../../C/Alloc.h"

    10 }

    11 

    12 #include "PpmdType.h"

    13 

    14 const UINT N1=4, N2=4, N3=4, N4=(128+3-1*N1-2*N2-3*N3)/4;

    15 const UINT UNIT_SIZE=12, N_INDEXES=N1+N2+N3+N4;

    16 

    17 // Extra 1 * UNIT_SIZE for NULL support

    18 // Extra 2 * UNIT_SIZE for s0 in GlueFreeBlocks()

    19 const UInt32 kExtraSize = (UNIT_SIZE * 3);

    20 const UInt32 kMaxMemBlockSize = 0xFFFFFFFF - kExtraSize;

    21 

    22 struct MEM_BLK

    23 {

    24   UInt16 Stamp, NU;

    25   UInt32 Next, Prev;

    26   void InsertAt(Byte *Base, UInt32 p)

    27   {

    28     Prev = p;

    29     MEM_BLK *pp = (MEM_BLK *)(Base + p);

    30     Next = pp->Next;

    31     pp->Next = ((MEM_BLK *)(Base + Next))->Prev = (UInt32)((Byte *)this - Base);

    32   }

    33   void Remove(Byte *Base)

    34   {

    35     ((MEM_BLK *)(Base + Prev))->Next = Next;

    36     ((MEM_BLK *)(Base + Next))->Prev = Prev;

    37   }

    38 };

    39 

    40 

    41 class CSubAllocator

    42 {

    43   UInt32 SubAllocatorSize;

    44   Byte Indx2Units[N_INDEXES], Units2Indx[128], GlueCount;

    45   UInt32 FreeList[N_INDEXES];

    46 

    47   Byte *Base;

    48   Byte *HeapStart, *LoUnit, *HiUnit;

    49 public:

    50   Byte *pText, *UnitsStart;

    51   CSubAllocator():

    52     SubAllocatorSize(0),

    53     GlueCount(0),

    54     LoUnit(0),

    55     HiUnit(0),

    56     pText(0),

    57     UnitsStart(0)

    58   {

    59     memset(Indx2Units, 0, sizeof(Indx2Units));

    60     memset(FreeList, 0, sizeof(FreeList));

    61   }

    62   ~CSubAllocator()

    63   {

    64     StopSubAllocator();

    65   };

    66 

    67   void *GetPtr(UInt32 offset) const { return (offset == 0) ? 0 : (void *)(Base + offset); }

    68   void *GetPtrNoCheck(UInt32 offset) const { return (void *)(Base + offset); }

    69   UInt32 GetOffset(void *ptr) const { return (ptr == 0) ? 0 : (UInt32)((Byte *)ptr - Base); }

    70   UInt32 GetOffsetNoCheck(void *ptr) const { return (UInt32)((Byte *)ptr - Base); }

    71   MEM_BLK *GetBlk(UInt32 offset) const { return (MEM_BLK *)(Base + offset); }

    72   UInt32 *GetNode(UInt32 offset) const { return (UInt32 *)(Base + offset); }

    73 

    74   void InsertNode(void* p, int indx)

    75   {

    76     *(UInt32 *)p = FreeList[indx];

    77     FreeList[indx] = GetOffsetNoCheck(p);

    78   }

    79 

    80   void* RemoveNode(int indx)

    81   {

    82     UInt32 offset = FreeList[indx];

    83     UInt32 *p = GetNode(offset);

    84     FreeList[indx] = *p;

    85     return (void *)p;

    86   }

    87   

    88   UINT U2B(int NU) const { return (UINT)(NU) * UNIT_SIZE; }

    89   

    90   void SplitBlock(void* pv, int oldIndx, int newIndx)

    91   {

    92     int i, UDiff = Indx2Units[oldIndx] - Indx2Units[newIndx];

    93     Byte* p = ((Byte*)pv) + U2B(Indx2Units[newIndx]);

    94     if (Indx2Units[i = Units2Indx[UDiff-1]] != UDiff)

    95     {

    96       InsertNode(p, --i);

    97       p += U2B(i = Indx2Units[i]);

    98       UDiff -= i;

    99     }

   100     InsertNode(p, Units2Indx[UDiff - 1]);

   101   }

   102   

   103   UInt32 GetUsedMemory() const

   104   {

   105     UInt32 RetVal = SubAllocatorSize - (UInt32)(HiUnit - LoUnit) - (UInt32)(UnitsStart - pText);

   106     for (UInt32 i = 0; i < N_INDEXES; i++)

   107       for (UInt32 pn = FreeList[i]; pn != 0; RetVal -= (UInt32)Indx2Units[i] * UNIT_SIZE)

   108         pn = *GetNode(pn);

   109     return (RetVal >> 2);

   110   }

   111   

   112   UInt32 GetSubAllocatorSize() const { return SubAllocatorSize; }

   113 

   114   void StopSubAllocator()

   115   {

   116     if (SubAllocatorSize != 0)

   117     {

   118       BigFree(Base);

   119       SubAllocatorSize = 0;

   120       Base = 0;

   121     }

   122   }

   123 

   124   bool StartSubAllocator(UInt32 size)

   125   {

   126     if (SubAllocatorSize == size)

   127       return true;

   128     StopSubAllocator();

   129     if (size == 0)

   130       Base = 0;

   131     else

   132     {

   133       if ((Base = (Byte *)::BigAlloc(size + kExtraSize)) == 0)

   134         return false;

   135       HeapStart = Base + UNIT_SIZE; // we need such code to support NULL;

   136     }

   137     SubAllocatorSize = size;

   138     return true;

   139   }

   140 

   141   void InitSubAllocator()

   142   {

   143     int i, k;

   144     memset(FreeList, 0, sizeof(FreeList));

   145     HiUnit = (pText = HeapStart) + SubAllocatorSize;

   146     UINT Diff = UNIT_SIZE * (SubAllocatorSize / 8 / UNIT_SIZE * 7);

   147     LoUnit = UnitsStart = HiUnit - Diff;

   148     for (i = 0, k=1; i < N1 ; i++, k += 1)        Indx2Units[i] = (Byte)k;

   149     for (k++; i < N1 + N2      ;i++, k += 2)      Indx2Units[i] = (Byte)k;

   150     for (k++; i < N1 + N2 + N3   ;i++,k += 3)     Indx2Units[i] = (Byte)k;

   151     for (k++; i < N1 + N2 + N3 + N4; i++, k += 4) Indx2Units[i] = (Byte)k;

   152     GlueCount = 0;

   153     for (k = i = 0; k < 128; k++)

   154     {

   155       i += (Indx2Units[i] < k+1);

   156         Units2Indx[k] = (Byte)i;

   157     }

   158   }

   159   

   160   void GlueFreeBlocks()

   161   {

   162     UInt32 s0 = (UInt32)(HeapStart + SubAllocatorSize - Base);

   163 

   164     // We need add exta MEM_BLK with Stamp=0

   165     GetBlk(s0)->Stamp = 0;

   166     s0 += UNIT_SIZE;

   167     MEM_BLK *ps0 = GetBlk(s0);

   168 

   169     UInt32 p;

   170     int i;

   171     if (LoUnit != HiUnit)

   172       *LoUnit=0;

   173     ps0->Next = ps0->Prev = s0;

   174 

   175     for (i = 0; i < N_INDEXES; i++)

   176       while (FreeList[i] != 0)

   177       {

   178         MEM_BLK *pp = (MEM_BLK *)RemoveNode(i);

   179         pp->InsertAt(Base, s0);

   180         pp->Stamp = 0xFFFF;

   181         pp->NU = Indx2Units[i];

   182       }

   183     for (p = ps0->Next; p != s0; p = GetBlk(p)->Next)

   184     {

   185       for (;;)

   186       {

   187         MEM_BLK *pp = GetBlk(p);

   188         MEM_BLK *pp1 = GetBlk(p + pp->NU * UNIT_SIZE);

   189         if (pp1->Stamp != 0xFFFF || int(pp->NU) + pp1->NU >= 0x10000)

   190           break;

   191         pp1->Remove(Base);

   192         pp->NU = (UInt16)(pp->NU + pp1->NU);

   193       }

   194     }

   195     while ((p = ps0->Next) != s0)

   196     {

   197       MEM_BLK *pp = GetBlk(p);

   198       pp->Remove(Base);

   199       int sz;

   200       for (sz = pp->NU; sz > 128; sz -= 128, p += 128 * UNIT_SIZE)

   201         InsertNode(Base + p, N_INDEXES - 1);

   202       if (Indx2Units[i = Units2Indx[sz-1]] != sz)

   203       {

   204         int k = sz - Indx2Units[--i];

   205         InsertNode(Base + p + (sz - k) * UNIT_SIZE, k - 1);

   206       }

   207       InsertNode(Base + p, i);

   208     }

   209   }

   210   void* AllocUnitsRare(int indx)

   211   {

   212     if ( !GlueCount )

   213     {

   214       GlueCount = 255;

   215       GlueFreeBlocks();

   216       if (FreeList[indx] != 0)

   217         return RemoveNode(indx);

   218     }

   219     int i = indx;

   220     do

   221     {

   222       if (++i == N_INDEXES)

   223       {

   224         GlueCount--;

   225         i = U2B(Indx2Units[indx]);

   226         return (UnitsStart - pText > i) ? (UnitsStart -= i) : (NULL);

   227       }

   228     } while (FreeList[i] == 0);

   229     void* RetVal = RemoveNode(i);

   230     SplitBlock(RetVal, i, indx);

   231     return RetVal;

   232   }

   233   

   234   void* AllocUnits(int NU)

   235   {

   236     int indx = Units2Indx[NU - 1];

   237     if (FreeList[indx] != 0)

   238       return RemoveNode(indx);

   239     void* RetVal = LoUnit;

   240     LoUnit += U2B(Indx2Units[indx]);

   241     if (LoUnit <= HiUnit)

   242       return RetVal;

   243     LoUnit -= U2B(Indx2Units[indx]);

   244     return AllocUnitsRare(indx);

   245   }

   246   

   247   void* AllocContext()

   248   {

   249     if (HiUnit != LoUnit)

   250       return (HiUnit -= UNIT_SIZE);

   251     if (FreeList[0] != 0)

   252       return RemoveNode(0);

   253     return AllocUnitsRare(0);

   254   }

   255   

   256   void* ExpandUnits(void* oldPtr, int oldNU)

   257   {

   258     int i0=Units2Indx[oldNU - 1], i1=Units2Indx[oldNU - 1 + 1];

   259     if (i0 == i1)

   260       return oldPtr;

   261     void* ptr = AllocUnits(oldNU + 1);

   262     if (ptr)

   263     {

   264       memcpy(ptr, oldPtr, U2B(oldNU));

   265       InsertNode(oldPtr, i0);

   266     }

   267     return ptr;

   268   }

   269   

   270   void* ShrinkUnits(void* oldPtr, int oldNU, int newNU)

   271   {

   272     int i0 = Units2Indx[oldNU - 1], i1 = Units2Indx[newNU - 1];

   273     if (i0 == i1)

   274       return oldPtr;

   275     if (FreeList[i1] != 0)

   276     {

   277       void* ptr = RemoveNode(i1);

   278       memcpy(ptr, oldPtr, U2B(newNU));

   279       InsertNode(oldPtr,i0);

   280       return ptr;

   281     }

   282     else

   283     {

   284       SplitBlock(oldPtr, i0, i1);

   285       return oldPtr;

   286     }

   287   }

   288   

   289   void FreeUnits(void* ptr, int oldNU)

   290   {

   291     InsertNode(ptr, Units2Indx[oldNU - 1]);

   292   }

   293 };

   294 

   295 #endif
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children