summaryrefslogtreecommitdiff
path: root/noncore/apps/opie-reader/SubAlloc.h
Unidiff
Diffstat (limited to 'noncore/apps/opie-reader/SubAlloc.h') (more/less context) (show whitespace changes)
-rw-r--r--noncore/apps/opie-reader/SubAlloc.h201
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 @@
1/****************************************************************************
2 * This file is part of PPMd project *
3 * Written and distributed to public domain by Dmitry Shkarin 1997, *
4 * 1999-2001 *
5 * Contents: memory allocation routines *
6 ****************************************************************************/
7
8enum { UNIT_SIZE=12, N1=4, N2=4, N3=4, N4=(128+3-1*N1-2*N2-3*N3)/4,
9 N_INDEXES=N1+N2+N3+N4 };
10
11#pragma pack(1)
12struct BLK_NODE {
13 DWORD Stamp;
14 BLK_NODE* next;
15 BOOL avail() const { return (next != NULL); }
16 void link(BLK_NODE* p) { p->next=next; next=p; }
17 void unlink() { next=next->next; }
18 void* remove() {
19 BLK_NODE* p=next; unlink();
20 Stamp--; return p;
21 }
22 inline void insert(void* pv,int NU);
23} BList[N_INDEXES];
24struct MEM_BLK: public BLK_NODE { DWORD NU; } _PACK_ATTR;
25#pragma pack()
26
27static BYTE Indx2Units[N_INDEXES], Units2Indx[128]; // constants
28static DWORD GlueCount, SubAllocatorSize=0;
29static BYTE* HeapStart, * pText, * UnitsStart, * LoUnit, * HiUnit;
30
31inline void PrefetchData(void* Addr)
32{
33#if defined(_USE_PREFETCHING)
34 BYTE PrefetchByte = *(volatile BYTE*) Addr;
35#endif /* defined(_USE_PREFETCHING) */
36}
37inline void BLK_NODE::insert(void* pv,int NU) {
38 MEM_BLK* p=(MEM_BLK*) pv; link(p);
39 p->Stamp=~0UL; p->NU=NU;
40 Stamp++;
41}
42inline UINT U2B(UINT NU) { return 8*NU+4*NU; }
43inline void SplitBlock(void* pv,UINT OldIndx,UINT NewIndx)
44{
45 UINT i, k, UDiff=Indx2Units[OldIndx]-Indx2Units[NewIndx];
46 BYTE* p=((BYTE*) pv)+U2B(Indx2Units[NewIndx]);
47 if (Indx2Units[i=Units2Indx[UDiff-1]] != UDiff) {
48 k=Indx2Units[--i]; BList[i].insert(p,k);
49 p += U2B(k); UDiff -= k;
50 }
51 BList[Units2Indx[UDiff-1]].insert(p,UDiff);
52}
53DWORD _STDCALL GetUsedMemory()
54{
55 DWORD i, RetVal=SubAllocatorSize-(HiUnit-LoUnit)-(UnitsStart-pText);
56 for (i=0;i < N_INDEXES;i++)
57 RetVal -= UNIT_SIZE*Indx2Units[i]*BList[i].Stamp;
58 return RetVal;
59}
60void _STDCALL StopSubAllocator() {
61 if ( SubAllocatorSize ) {
62 SubAllocatorSize=0; delete[] HeapStart;
63 }
64}
65BOOL _STDCALL StartSubAllocator(UINT SASize)
66{
67 DWORD t=SASize << 19U;
68 if (SubAllocatorSize == t) return TRUE;
69 StopSubAllocator();
70 if ((HeapStart=new BYTE[t]) == NULL) return FALSE;
71 SubAllocatorSize=t; return TRUE;
72}
73static inline void InitSubAllocator()
74{
75 memset(BList,0,sizeof(BList));
76 HiUnit=(pText=HeapStart)+SubAllocatorSize;
77 UINT Diff=UNIT_SIZE*(SubAllocatorSize/8/UNIT_SIZE*7);
78 LoUnit=UnitsStart=HiUnit-Diff; GlueCount=0;
79}
80static void GlueFreeBlocks()
81{
82 UINT i, k, sz;
83 MEM_BLK s0, * p, * p0, * p1;
84 if (LoUnit != HiUnit) *LoUnit=0;
85 for (i=0, (p0=&s0)->next=NULL;i < N_INDEXES;i++)
86 while ( BList[i].avail() ) {
87 p=(MEM_BLK*) BList[i].remove();
88 if ( !p->NU ) continue;
89 while ((p1=p+p->NU)->Stamp == ~0UL) {
90 p->NU += p1->NU; p1->NU=0;
91 }
92 p0->link(p); p0=p;
93 }
94 while ( s0.avail() ) {
95 p=(MEM_BLK*) s0.remove(); sz=p->NU;
96 if ( !sz ) continue;
97 for ( ;sz > 128;sz -= 128, p += 128)
98 BList[N_INDEXES-1].insert(p,128);
99 if (Indx2Units[i=Units2Indx[sz-1]] != sz) {
100 k=sz-Indx2Units[--i]; BList[k-1].insert(p+(sz-k),k);
101 }
102 BList[i].insert(p,Indx2Units[i]);
103 }
104 GlueCount=1 << 13;
105}
106static void* _STDCALL AllocUnitsRare(UINT indx)
107{
108 UINT i=indx;
109 if ( !GlueCount ) {
110 GlueFreeBlocks();
111 if ( BList[i].avail() ) return BList[i].remove();
112 }
113 do {
114 if (++i == N_INDEXES) {
115 GlueCount--; i=U2B(Indx2Units[indx]);
116 return (UnitsStart-pText > i)?(UnitsStart -= i):(NULL);
117 }
118 } while ( !BList[i].avail() );
119 void* RetVal=BList[i].remove(); SplitBlock(RetVal,i,indx);
120 return RetVal;
121}
122inline void* AllocUnits(UINT NU)
123{
124 UINT indx=Units2Indx[NU-1];
125 if ( BList[indx].avail() ) return BList[indx].remove();
126 void* RetVal=LoUnit; LoUnit += U2B(Indx2Units[indx]);
127 if (LoUnit <= HiUnit) return RetVal;
128 LoUnit -= U2B(Indx2Units[indx]); return AllocUnitsRare(indx);
129}
130inline void* AllocContext()
131{
132 if (HiUnit != LoUnit) return (HiUnit -= UNIT_SIZE);
133 else if ( BList->avail() ) return BList->remove();
134 else return AllocUnitsRare(0);
135}
136inline void UnitsCpy(void* Dest,void* Src,UINT NU)
137{
138 DWORD* p1=(DWORD*) Dest, * p2=(DWORD*) Src;
139 do {
140 p1[0]=p2[0]; p1[1]=p2[1];
141 p1[2]=p2[2];
142 p1 += 3; p2 += 3;
143 } while ( --NU );
144}
145inline void* ExpandUnits(void* OldPtr,UINT OldNU)
146{
147 UINT i0=Units2Indx[OldNU-1], i1=Units2Indx[OldNU-1+1];
148 if (i0 == i1) return OldPtr;
149 void* ptr=AllocUnits(OldNU+1);
150 if ( ptr ) {
151 UnitsCpy(ptr,OldPtr,OldNU); BList[i0].insert(OldPtr,OldNU);
152 }
153 return ptr;
154}
155inline void* ShrinkUnits(void* OldPtr,UINT OldNU,UINT NewNU)
156{
157 UINT i0=Units2Indx[OldNU-1], i1=Units2Indx[NewNU-1];
158 if (i0 == i1) return OldPtr;
159 if ( BList[i1].avail() ) {
160 void* ptr=BList[i1].remove(); UnitsCpy(ptr,OldPtr,NewNU);
161 BList[i0].insert(OldPtr,Indx2Units[i0]);
162 return ptr;
163 } else {
164 SplitBlock(OldPtr,i0,i1); return OldPtr;
165 }
166}
167inline void FreeUnits(void* ptr,UINT NU) {
168 UINT indx=Units2Indx[NU-1];
169 BList[indx].insert(ptr,Indx2Units[indx]);
170}
171inline void SpecialFreeUnit(void* ptr)
172{
173 if ((BYTE*) ptr != UnitsStart) BList->insert(ptr,1);
174 else { *(DWORD*) ptr=~0UL; UnitsStart += UNIT_SIZE; }
175}
176inline void* MoveUnitsUp(void* OldPtr,UINT NU)
177{
178 UINT indx=Units2Indx[NU-1];
179 if ((BYTE*) OldPtr > UnitsStart+16*1024 || (BLK_NODE*) OldPtr > BList[indx].next)
180 return OldPtr;
181 void* ptr=BList[indx].remove();
182 UnitsCpy(ptr,OldPtr,NU); NU=Indx2Units[indx];
183 if ((BYTE*) OldPtr != UnitsStart) BList[indx].insert(OldPtr,NU);
184 else UnitsStart += U2B(NU);
185 return ptr;
186}
187static inline void ExpandTextArea()
188{
189 BLK_NODE* p;
190 UINT Count[N_INDEXES]; memset(Count,0,sizeof(Count));
191 while ((p=(BLK_NODE*) UnitsStart)->Stamp == ~0UL) {
192 MEM_BLK* pm=(MEM_BLK*) p; UnitsStart=(BYTE*) (pm+pm->NU);
193 Count[Units2Indx[pm->NU-1]]++; pm->Stamp=0;
194 }
195 for (UINT i=0;i < N_INDEXES;i++)
196 for (p=BList+i;Count[i] != 0;p=p->next)
197 while ( !p->next->Stamp ) {
198 p->unlink(); BList[i].Stamp--;
199 if ( !--Count[i] ) break;
200 }
201}