user/unrar/suballoc.cpp

   1 /****************************************************************************
   2  *  This file is part of PPMd project                                       *
   3  *  Written and distributed to public domain by Dmitry Shkarin 1997,        *
   4  *  1999-2000                                                               *
   5  *  Contents: memory allocation routines                                    *
   6  ****************************************************************************/
   7
   8 SubAllocator::SubAllocator()
   9 {
  10   Clean();
  11 }
  12
  13
  14 void SubAllocator::Clean()
  15 {
  16   SubAllocatorSize=0;
  17 }
  18
  19
  20 inline void SubAllocator::InsertNode(void* p,int indx)
  21 {
  22   ((RAR_NODE*) p)->next=FreeList[indx].next;
  23   FreeList[indx].next=(RAR_NODE*) p;
  24 }
  25
  26
  27 inline void* SubAllocator::RemoveNode(int indx)
  28 {
  29   RAR_NODE* RetVal=FreeList[indx].next;
  30   FreeList[indx].next=RetVal->next;
  31   return RetVal;
  32 }
  33
  34
  35 inline uint SubAllocator::U2B(int NU)
  36 {
  37   return /*8*NU+4*NU*/UNIT_SIZE*NU;
  38 }
  39
  40
  41 inline void SubAllocator::SplitBlock(void* pv,int OldIndx,int NewIndx)
  42 {
  43   int i, UDiff=Indx2Units[OldIndx]-Indx2Units[NewIndx];
  44   byte* p=((byte*) pv)+U2B(Indx2Units[NewIndx]);
  45   if (Indx2Units[i=Units2Indx[UDiff-1]] != UDiff)
  46   {
  47     InsertNode(p,--i);
  48     p += U2B(i=Indx2Units[i]);
  49     UDiff -= i;
  50   }
  51   InsertNode(p,Units2Indx[UDiff-1]);
  52 }
  53
  54
  55
  56
  57 void SubAllocator::StopSubAllocator()
  58 {
  59   if ( SubAllocatorSize )
  60   {
  61     SubAllocatorSize=0;
  62     rarfree(HeapStart);
  63   }
  64 }
  65
  66
  67 bool SubAllocator::StartSubAllocator(int SASize)
  68 {
  69   uint t=SASize << 20;
  70   if (SubAllocatorSize == t)
  71     return TRUE;
  72   StopSubAllocator();
  73   uint AllocSize=t/FIXED_UNIT_SIZE*UNIT_SIZE+UNIT_SIZE;
  74   if ((HeapStart=(byte *)rarmalloc(AllocSize)) == NULL)
  75   {
  76     ErrHandler.MemoryError();
  77     return FALSE;
  78   }
  79   HeapEnd=HeapStart+AllocSize-UNIT_SIZE;
  80   SubAllocatorSize=t;
  81   return TRUE;
  82 }
  83
  84
  85 void SubAllocator::InitSubAllocator()
  86 {
  87   int i, k;
  88   memset(FreeList,0,sizeof(FreeList));
  89   pText=HeapStart;
  90   uint Size2=FIXED_UNIT_SIZE*(SubAllocatorSize/8/FIXED_UNIT_SIZE*7);
  91   uint RealSize2=Size2/FIXED_UNIT_SIZE*UNIT_SIZE;
  92   uint Size1=SubAllocatorSize-Size2;
  93   uint RealSize1=Size1/FIXED_UNIT_SIZE*UNIT_SIZE+Size1%FIXED_UNIT_SIZE;
  94   HiUnit=HeapStart+SubAllocatorSize;
  95   LoUnit=UnitsStart=HeapStart+RealSize1;
  96   FakeUnitsStart=HeapStart+Size1;
  97   HiUnit=LoUnit+RealSize2;
  98   for (i=0,k=1;i < N1     ;i++,k += 1)
  99     Indx2Units[i]=k;
 100   for (k++;i < N1+N2      ;i++,k += 2)
 101     Indx2Units[i]=k;
 102   for (k++;i < N1+N2+N3   ;i++,k += 3)
 103     Indx2Units[i]=k;
 104   for (k++;i < N1+N2+N3+N4;i++,k += 4)
 105     Indx2Units[i]=k;
 106   for (GlueCount=k=i=0;k < 128;k++)
 107   {
 108     i += (Indx2Units[i] < k+1);
 109     Units2Indx[k]=i;
 110   }
 111 }
 112
 113
 114 inline void SubAllocator::GlueFreeBlocks()
 115 {
 116   RAR_MEM_BLK s0, * p, * p1;
 117   int i, k, sz;
 118   if (LoUnit != HiUnit)
 119     *LoUnit=0;
 120   for (i=0, s0.next=s0.prev=&s0;i < N_INDEXES;i++)
 121     while ( FreeList[i].next )
 122     {
 123       p=(RAR_MEM_BLK*)RemoveNode(i);
 124       p->insertAt(&s0);
 125       p->Stamp=0xFFFF;
 126       p->NU=Indx2Units[i];
 127     }
 128   for (p=s0.next;p != &s0;p=p->next)
 129     while ((p1=p+p->NU)->Stamp == 0xFFFF && int(p->NU)+p1->NU < 0x10000)
 130     {
 131       p1->remove();
 132       p->NU += p1->NU;
 133     }
 134   while ((p=s0.next) != &s0)
 135   {
 136     for (p->remove(), sz=p->NU;sz > 128;sz -= 128, p += 128)
 137       InsertNode(p,N_INDEXES-1);
 138     if (Indx2Units[i=Units2Indx[sz-1]] != sz)
 139     {
 140       k=sz-Indx2Units[--i];
 141       InsertNode(p+(sz-k),k-1);
 142     }
 143     InsertNode(p,i);
 144   }
 145 }
 146
 147 void* SubAllocator::AllocUnitsRare(int indx)
 148 {
 149   if ( !GlueCount )
 150   {
 151     GlueCount = 255;
 152     GlueFreeBlocks();
 153     if ( FreeList[indx].next )
 154       return RemoveNode(indx);
 155   }
 156   int i=indx;
 157   do
 158   {
 159     if (++i == N_INDEXES)
 160     {
 161       GlueCount--;
 162       i=U2B(Indx2Units[indx]);
 163       int j=12*Indx2Units[indx];
 164       if (FakeUnitsStart-pText > j)
 165       {
 166         FakeUnitsStart-=j;
 167         UnitsStart -= i;
 168         return(UnitsStart);
 169       }
 170       return(NULL);
 171     }
 172   } while ( !FreeList[i].next );
 173   void* RetVal=RemoveNode(i);
 174   SplitBlock(RetVal,i,indx);
 175   return RetVal;
 176 }
 177
 178
 179 inline void* SubAllocator::AllocUnits(int NU)
 180 {
 181   int indx=Units2Indx[NU-1];
 182   if ( FreeList[indx].next )
 183     return RemoveNode(indx);
 184   void* RetVal=LoUnit;
 185   LoUnit += U2B(Indx2Units[indx]);
 186   if (LoUnit <= HiUnit)
 187     return RetVal;
 188   LoUnit -= U2B(Indx2Units[indx]);
 189   return AllocUnitsRare(indx);
 190 }
 191
 192
 193 void* SubAllocator::AllocContext()
 194 {
 195   if (HiUnit != LoUnit)
 196     return (HiUnit -= UNIT_SIZE);
 197   if ( FreeList->next )
 198     return RemoveNode(0);
 199   return AllocUnitsRare(0);
 200 }
 201
 202
 203 void* SubAllocator::ExpandUnits(void* OldPtr,int OldNU)
 204 {
 205   int i0=Units2Indx[OldNU-1], i1=Units2Indx[OldNU-1+1];
 206   if (i0 == i1)
 207     return OldPtr;
 208   void* ptr=AllocUnits(OldNU+1);
 209   if ( ptr )
 210   {
 211     memcpy(ptr,OldPtr,U2B(OldNU));
 212     InsertNode(OldPtr,i0);
 213   }
 214   return ptr;
 215 }
 216
 217
 218 void* SubAllocator::ShrinkUnits(void* OldPtr,int OldNU,int NewNU)
 219 {
 220   int i0=Units2Indx[OldNU-1], i1=Units2Indx[NewNU-1];
 221   if (i0 == i1)
 222     return OldPtr;
 223   if ( FreeList[i1].next )
 224   {
 225     void* ptr=RemoveNode(i1);
 226     memcpy(ptr,OldPtr,U2B(NewNU));
 227     InsertNode(OldPtr,i0);
 228     return ptr;
 229   }
 230   else
 231   {
 232     SplitBlock(OldPtr,i0,i1);
 233     return OldPtr;
 234   }
 235 }
 236
 237
 238 void SubAllocator::FreeUnits(void* ptr,int OldNU)
 239 {
 240   InsertNode(ptr,Units2Indx[OldNU-1]);
 241 }