code.vuplus.com Git - vuplus_xbmc/blob - lib/UnrarXLib/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=(uint)(SASize) << 20;
  70   if ((uint)SubAllocatorSize == t)
  71     return TRUE;
  72   StopSubAllocator();
  73   uint AllocSize=t/FIXED_UNIT_SIZE*UNIT_SIZE+UNIT_SIZE;
  74 #ifdef XBOX
  75   if ((HeapStart=(byte *)rarmalloc(AllocSize)) == NULL)
  76   {
  77     ErrHandler.MemoryError();
  78     return FALSE;
  79   }
  80 #else
  81   // this is uggly, we keep halfing the size till
  82   // we manage to alloc, it's likely that we
  83   // fail to alloc
  84   uint AllocSize2 = AllocSize;
  85   while(AllocSize2 && (HeapStart=(byte *)rarmalloc(AllocSize2)) == NULL)
  86     AllocSize2<<=1;
  87
  88   if(HeapStart == NULL)
  89   {
  90     ErrHandler.MemoryError();
  91     return FALSE;
  92   }
  93
  94   if(AllocSize != AllocSize2)
  95     OutputDebugString("ERROR - had to allocate smaller data than required, extract can very well fail");
  96
  97 #endif
  98   HeapEnd=HeapStart+AllocSize-UNIT_SIZE;
  99   SubAllocatorSize=t;
 100   return TRUE;
 101 }
 102
 103
 104 void SubAllocator::InitSubAllocator()
 105 {
 106   int i, k;
 107   memset(FreeList,0,sizeof(FreeList));
 108   pText=HeapStart;
 109   uint Size2=FIXED_UNIT_SIZE*(SubAllocatorSize/8/FIXED_UNIT_SIZE*7);
 110   uint RealSize2=Size2/FIXED_UNIT_SIZE*UNIT_SIZE;
 111   uint Size1=SubAllocatorSize-Size2;
 112   uint RealSize1=Size1/FIXED_UNIT_SIZE*UNIT_SIZE+Size1%FIXED_UNIT_SIZE;
 113   HiUnit=HeapStart+SubAllocatorSize;
 114   LoUnit=UnitsStart=HeapStart+RealSize1;
 115   FakeUnitsStart=HeapStart+Size1;
 116   HiUnit=LoUnit+RealSize2;
 117   for (i=0,k=1;i < N1     ;i++,k += 1)
 118     Indx2Units[i]=k;
 119   for (k++;i < N1+N2      ;i++,k += 2)
 120     Indx2Units[i]=k;
 121   for (k++;i < N1+N2+N3   ;i++,k += 3)
 122     Indx2Units[i]=k;
 123   for (k++;i < N1+N2+N3+N4;i++,k += 4)
 124     Indx2Units[i]=k;
 125   for (GlueCount=k=i=0;k < 128;k++)
 126   {
 127     i += (Indx2Units[i] < k+1);
 128     Units2Indx[k]=i;
 129   }
 130 }
 131
 132
 133 inline void SubAllocator::GlueFreeBlocks()
 134 {
 135   RAR_MEM_BLK s0, * p, * p1;
 136   int i, k, sz;
 137   if (LoUnit != HiUnit)
 138     *LoUnit=0;
 139   for (i=0, s0.next=s0.prev=&s0;i < N_INDEXES;i++)
 140     while ( FreeList[i].next )
 141     {
 142       p=(RAR_MEM_BLK*)RemoveNode(i);
 143       p->insertAt(&s0);
 144       p->Stamp=0xFFFF;
 145       p->NU=Indx2Units[i];
 146     }
 147   for (p=s0.next;p != &s0;p=p->next)
 148     while ((p1=p+p->NU)->Stamp == 0xFFFF && int(p->NU)+p1->NU < 0x10000)
 149     {
 150       p1->remove();
 151       p->NU += p1->NU;
 152     }
 153   while ((p=s0.next) != &s0)
 154   {
 155     for (p->remove(), sz=p->NU;sz > 128;sz -= 128, p += 128)
 156       InsertNode(p,N_INDEXES-1);
 157     if (Indx2Units[i=Units2Indx[sz-1]] != sz)
 158     {
 159       k=sz-Indx2Units[--i];
 160       InsertNode(p+(sz-k),k-1);
 161     }
 162     InsertNode(p,i);
 163   }
 164 }
 165
 166 void* SubAllocator::AllocUnitsRare(int indx)
 167 {
 168   if ( !GlueCount )
 169   {
 170     GlueCount = 255;
 171     GlueFreeBlocks();
 172     if ( FreeList[indx].next )
 173       return RemoveNode(indx);
 174   }
 175   int i=indx;
 176   do
 177   {
 178     if (++i == N_INDEXES)
 179     {
 180       GlueCount--;
 181       i=U2B(Indx2Units[indx]);
 182       int j=12*Indx2Units[indx];
 183       if (FakeUnitsStart-pText > j)
 184       {
 185         FakeUnitsStart-=j;
 186         UnitsStart -= i;
 187         return(UnitsStart);
 188       }
 189       return(NULL);
 190     }
 191   } while ( !FreeList[i].next );
 192   void* RetVal=RemoveNode(i);
 193   SplitBlock(RetVal,i,indx);
 194   return RetVal;
 195 }
 196
 197
 198 inline void* SubAllocator::AllocUnits(int NU)
 199 {
 200   int indx=Units2Indx[NU-1];
 201   if ( FreeList[indx].next )
 202     return RemoveNode(indx);
 203   void* RetVal=LoUnit;
 204   LoUnit += U2B(Indx2Units[indx]);
 205   if (LoUnit <= HiUnit)
 206     return RetVal;
 207   LoUnit -= U2B(Indx2Units[indx]);
 208   return AllocUnitsRare(indx);
 209 }
 210
 211
 212 void* SubAllocator::AllocContext()
 213 {
 214   if (HiUnit != LoUnit)
 215     return (HiUnit -= UNIT_SIZE);
 216   if ( FreeList->next )
 217     return RemoveNode(0);
 218   return AllocUnitsRare(0);
 219 }
 220
 221
 222 void* SubAllocator::ExpandUnits(void* OldPtr,int OldNU)
 223 {
 224   int i0=Units2Indx[OldNU-1], i1=Units2Indx[OldNU-1+1];
 225   if (i0 == i1)
 226     return OldPtr;
 227   void* ptr=AllocUnits(OldNU+1);
 228   if ( ptr )
 229   {
 230     memcpy(ptr,OldPtr,U2B(OldNU));
 231     InsertNode(OldPtr,i0);
 232   }
 233   return ptr;
 234 }
 235
 236
 237 void* SubAllocator::ShrinkUnits(void* OldPtr,int OldNU,int NewNU)
 238 {
 239   int i0=Units2Indx[OldNU-1], i1=Units2Indx[NewNU-1];
 240   if (i0 == i1)
 241     return OldPtr;
 242   if ( FreeList[i1].next )
 243   {
 244     void* ptr=RemoveNode(i1);
 245     memcpy(ptr,OldPtr,U2B(NewNU));
 246     InsertNode(OldPtr,i0);
 247     return ptr;
 248   }
 249   else
 250   {
 251     SplitBlock(OldPtr,i0,i1);
 252     return OldPtr;
 253   }
 254 }
 255
 256
 257 void SubAllocator::FreeUnits(void* ptr,int OldNU)
 258 {
 259   InsertNode(ptr,Units2Indx[OldNU-1]);
 260 }