Diffstat (limited to 'noncore/apps/opie-reader/SubAlloc.h') (more/less context) (ignore whitespace changes)
| -rw-r--r-- | noncore/apps/opie-reader/SubAlloc.h | 201 |
1 files changed, 201 insertions, 0 deletions
diff --git a/noncore/apps/opie-reader/SubAlloc.h b/noncore/apps/opie-reader/SubAlloc.h new file mode 100644 index 0000000..ded2b73 --- a/dev/null +++ b/noncore/apps/opie-reader/SubAlloc.h @@ -0,0 +1,201 @@ +/****************************************************************************
+ * This file is part of PPMd project *
+ * Written and distributed to public domain by Dmitry Shkarin 1997, *
+ * 1999-2001 *
+ * Contents: memory allocation routines *
+ ****************************************************************************/
+
+enum { UNIT_SIZE=12, N1=4, N2=4, N3=4, N4=(128+3-1*N1-2*N2-3*N3)/4,
+ N_INDEXES=N1+N2+N3+N4 };
+
+#pragma pack(1)
+struct BLK_NODE {
+ DWORD Stamp;
+ BLK_NODE* next;
+ BOOL avail() const { return (next != NULL); }
+ void link(BLK_NODE* p) { p->next=next; next=p; }
+ void unlink() { next=next->next; }
+ void* remove() {
+ BLK_NODE* p=next; unlink();
+ Stamp--; return p;
+ }
+ inline void insert(void* pv,int NU);
+} BList[N_INDEXES];
+struct MEM_BLK: public BLK_NODE { DWORD NU; } _PACK_ATTR;
+#pragma pack()
+
+static BYTE Indx2Units[N_INDEXES], Units2Indx[128]; // constants
+static DWORD GlueCount, SubAllocatorSize=0;
+static BYTE* HeapStart, * pText, * UnitsStart, * LoUnit, * HiUnit;
+
+inline void PrefetchData(void* Addr)
+{
+#if defined(_USE_PREFETCHING)
+ BYTE PrefetchByte = *(volatile BYTE*) Addr;
+#endif /* defined(_USE_PREFETCHING) */
+}
+inline void BLK_NODE::insert(void* pv,int NU) {
+ MEM_BLK* p=(MEM_BLK*) pv; link(p);
+ p->Stamp=~0UL; p->NU=NU;
+ Stamp++;
+}
+inline UINT U2B(UINT NU) { return 8*NU+4*NU; }
+inline void SplitBlock(void* pv,UINT OldIndx,UINT NewIndx)
+{
+ UINT i, k, UDiff=Indx2Units[OldIndx]-Indx2Units[NewIndx];
+ BYTE* p=((BYTE*) pv)+U2B(Indx2Units[NewIndx]);
+ if (Indx2Units[i=Units2Indx[UDiff-1]] != UDiff) {
+ k=Indx2Units[--i]; BList[i].insert(p,k);
+ p += U2B(k); UDiff -= k;
+ }
+ BList[Units2Indx[UDiff-1]].insert(p,UDiff);
+}
+DWORD _STDCALL GetUsedMemory()
+{
+ DWORD i, RetVal=SubAllocatorSize-(HiUnit-LoUnit)-(UnitsStart-pText);
+ for (i=0;i < N_INDEXES;i++)
+ RetVal -= UNIT_SIZE*Indx2Units[i]*BList[i].Stamp;
+ return RetVal;
+}
+void _STDCALL StopSubAllocator() {
+ if ( SubAllocatorSize ) {
+ SubAllocatorSize=0; delete[] HeapStart;
+ }
+}
+BOOL _STDCALL StartSubAllocator(UINT SASize)
+{
+ DWORD t=SASize << 19U;
+ if (SubAllocatorSize == t) return TRUE;
+ StopSubAllocator();
+ if ((HeapStart=new BYTE[t]) == NULL) return FALSE;
+ SubAllocatorSize=t; return TRUE;
+}
+static inline void InitSubAllocator()
+{
+ memset(BList,0,sizeof(BList));
+ HiUnit=(pText=HeapStart)+SubAllocatorSize;
+ UINT Diff=UNIT_SIZE*(SubAllocatorSize/8/UNIT_SIZE*7);
+ LoUnit=UnitsStart=HiUnit-Diff; GlueCount=0;
+}
+static void GlueFreeBlocks()
+{
+ UINT i, k, sz;
+ MEM_BLK s0, * p, * p0, * p1;
+ if (LoUnit != HiUnit) *LoUnit=0;
+ for (i=0, (p0=&s0)->next=NULL;i < N_INDEXES;i++)
+ while ( BList[i].avail() ) {
+ p=(MEM_BLK*) BList[i].remove();
+ if ( !p->NU ) continue;
+ while ((p1=p+p->NU)->Stamp == ~0UL) {
+ p->NU += p1->NU; p1->NU=0;
+ }
+ p0->link(p); p0=p;
+ }
+ while ( s0.avail() ) {
+ p=(MEM_BLK*) s0.remove(); sz=p->NU;
+ if ( !sz ) continue;
+ for ( ;sz > 128;sz -= 128, p += 128)
+ BList[N_INDEXES-1].insert(p,128);
+ if (Indx2Units[i=Units2Indx[sz-1]] != sz) {
+ k=sz-Indx2Units[--i]; BList[k-1].insert(p+(sz-k),k);
+ }
+ BList[i].insert(p,Indx2Units[i]);
+ }
+ GlueCount=1 << 13;
+}
+static void* _STDCALL AllocUnitsRare(UINT indx)
+{
+ UINT i=indx;
+ if ( !GlueCount ) {
+ GlueFreeBlocks();
+ if ( BList[i].avail() ) return BList[i].remove();
+ }
+ do {
+ if (++i == N_INDEXES) {
+ GlueCount--; i=U2B(Indx2Units[indx]);
+ return (UnitsStart-pText > i)?(UnitsStart -= i):(NULL);
+ }
+ } while ( !BList[i].avail() );
+ void* RetVal=BList[i].remove(); SplitBlock(RetVal,i,indx);
+ return RetVal;
+}
+inline void* AllocUnits(UINT NU)
+{
+ UINT indx=Units2Indx[NU-1];
+ if ( BList[indx].avail() ) return BList[indx].remove();
+ void* RetVal=LoUnit; LoUnit += U2B(Indx2Units[indx]);
+ if (LoUnit <= HiUnit) return RetVal;
+ LoUnit -= U2B(Indx2Units[indx]); return AllocUnitsRare(indx);
+}
+inline void* AllocContext()
+{
+ if (HiUnit != LoUnit) return (HiUnit -= UNIT_SIZE);
+ else if ( BList->avail() ) return BList->remove();
+ else return AllocUnitsRare(0);
+}
+inline void UnitsCpy(void* Dest,void* Src,UINT NU)
+{
+ DWORD* p1=(DWORD*) Dest, * p2=(DWORD*) Src;
+ do {
+ p1[0]=p2[0]; p1[1]=p2[1];
+ p1[2]=p2[2];
+ p1 += 3; p2 += 3;
+ } while ( --NU );
+}
+inline void* ExpandUnits(void* OldPtr,UINT OldNU)
+{
+ UINT i0=Units2Indx[OldNU-1], i1=Units2Indx[OldNU-1+1];
+ if (i0 == i1) return OldPtr;
+ void* ptr=AllocUnits(OldNU+1);
+ if ( ptr ) {
+ UnitsCpy(ptr,OldPtr,OldNU); BList[i0].insert(OldPtr,OldNU);
+ }
+ return ptr;
+}
+inline void* ShrinkUnits(void* OldPtr,UINT OldNU,UINT NewNU)
+{
+ UINT i0=Units2Indx[OldNU-1], i1=Units2Indx[NewNU-1];
+ if (i0 == i1) return OldPtr;
+ if ( BList[i1].avail() ) {
+ void* ptr=BList[i1].remove(); UnitsCpy(ptr,OldPtr,NewNU);
+ BList[i0].insert(OldPtr,Indx2Units[i0]);
+ return ptr;
+ } else {
+ SplitBlock(OldPtr,i0,i1); return OldPtr;
+ }
+}
+inline void FreeUnits(void* ptr,UINT NU) {
+ UINT indx=Units2Indx[NU-1];
+ BList[indx].insert(ptr,Indx2Units[indx]);
+}
+inline void SpecialFreeUnit(void* ptr)
+{
+ if ((BYTE*) ptr != UnitsStart) BList->insert(ptr,1);
+ else { *(DWORD*) ptr=~0UL; UnitsStart += UNIT_SIZE; }
+}
+inline void* MoveUnitsUp(void* OldPtr,UINT NU)
+{
+ UINT indx=Units2Indx[NU-1];
+ if ((BYTE*) OldPtr > UnitsStart+16*1024 || (BLK_NODE*) OldPtr > BList[indx].next)
+ return OldPtr;
+ void* ptr=BList[indx].remove();
+ UnitsCpy(ptr,OldPtr,NU); NU=Indx2Units[indx];
+ if ((BYTE*) OldPtr != UnitsStart) BList[indx].insert(OldPtr,NU);
+ else UnitsStart += U2B(NU);
+ return ptr;
+}
+static inline void ExpandTextArea()
+{
+ BLK_NODE* p;
+ UINT Count[N_INDEXES]; memset(Count,0,sizeof(Count));
+ while ((p=(BLK_NODE*) UnitsStart)->Stamp == ~0UL) {
+ MEM_BLK* pm=(MEM_BLK*) p; UnitsStart=(BYTE*) (pm+pm->NU);
+ Count[Units2Indx[pm->NU-1]]++; pm->Stamp=0;
+ }
+ for (UINT i=0;i < N_INDEXES;i++)
+ for (p=BList+i;Count[i] != 0;p=p->next)
+ while ( !p->next->Stamp ) {
+ p->unlink(); BList[i].Stamp--;
+ if ( !--Count[i] ) break;
+ }
+}
|