Diffstat (limited to 'noncore/apps/opie-reader/SubAlloc.h') (more/less context) (show 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 @@ | |||
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 | |||
8 | enum { 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) | ||
12 | struct 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]; | ||
24 | struct MEM_BLK: public BLK_NODE { DWORD NU; } _PACK_ATTR; | ||
25 | #pragma pack() | ||
26 | |||
27 | static BYTE Indx2Units[N_INDEXES], Units2Indx[128]; // constants | ||
28 | static DWORD GlueCount, SubAllocatorSize=0; | ||
29 | static BYTE* HeapStart, * pText, * UnitsStart, * LoUnit, * HiUnit; | ||
30 | |||
31 | inline void PrefetchData(void* Addr) | ||
32 | { | ||
33 | #if defined(_USE_PREFETCHING) | ||
34 | BYTE PrefetchByte = *(volatile BYTE*) Addr; | ||
35 | #endif /* defined(_USE_PREFETCHING) */ | ||
36 | } | ||
37 | inline 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 | } | ||
42 | inline UINT U2B(UINT NU) { return 8*NU+4*NU; } | ||
43 | inline 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 | } | ||
53 | DWORD _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 | } | ||
60 | void _STDCALL StopSubAllocator() { | ||
61 | if ( SubAllocatorSize ) { | ||
62 | SubAllocatorSize=0; delete[] HeapStart; | ||
63 | } | ||
64 | } | ||
65 | BOOL _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 | } | ||
73 | static 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 | } | ||
80 | static 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 | } | ||
106 | static 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 | } | ||
122 | inline 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 | } | ||
130 | inline 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 | } | ||
136 | inline 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 | } | ||
145 | inline 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 | } | ||
155 | inline 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 | } | ||
167 | inline void FreeUnits(void* ptr,UINT NU) { | ||
168 | UINT indx=Units2Indx[NU-1]; | ||
169 | BList[indx].insert(ptr,Indx2Units[indx]); | ||
170 | } | ||
171 | inline void SpecialFreeUnit(void* ptr) | ||
172 | { | ||
173 | if ((BYTE*) ptr != UnitsStart) BList->insert(ptr,1); | ||
174 | else { *(DWORD*) ptr=~0UL; UnitsStart += UNIT_SIZE; } | ||
175 | } | ||
176 | inline 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 | } | ||
187 | static 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 | } | ||