1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
#include "SubAllocatorVariantG.h"
#include <stdlib.h>
#include <string.h>
#define N1 4
#define N2 4
#define N3 4
#define N4 ((128+3-1*N1-2*N2-3*N3)/4)
#define UNIT_SIZE 12
#define N_INDEXES (N1+N2+N3+N4)
static void InsertNode(PPMdSubAllocatorVariantG *self,void *p,int index);
static void *RemoveNode(PPMdSubAllocatorVariantG *self,int index);
static unsigned int I2B(PPMdSubAllocatorVariantG *self,int index);
static void SplitBlock(PPMdSubAllocatorVariantG *self,void *pv,int oldindex,int newindex);
static uint32_t GetUsedMemory(PPMdSubAllocatorVariantG *self);
static void InitVariantG(PPMdSubAllocatorVariantG *self);
static uint32_t AllocContextVariantG(PPMdSubAllocatorVariantG *self);
static uint32_t AllocUnitsVariantG(PPMdSubAllocatorVariantG *self,int num);
static uint32_t ExpandUnitsVariantG(PPMdSubAllocatorVariantG *self,uint32_t oldoffs,int oldnum);
static uint32_t ShrinkUnitsVariantG(PPMdSubAllocatorVariantG *self,uint32_t oldoffs,int oldnum,int newnum);
static void FreeUnitsVariantG(PPMdSubAllocatorVariantG *self,uint32_t offs,int num);
PPMdSubAllocatorVariantG *CreateSubAllocatorVariantG(int size)
{
PPMdSubAllocatorVariantG *self=malloc(sizeof(PPMdSubAllocatorVariantG)+size);
if(!self) return NULL;
self->core.Init=(void *)InitVariantG;
self->core.AllocContext=(void *)AllocContextVariantG;
self->core.AllocUnits=(void *)AllocUnitsVariantG;
self->core.ExpandUnits=(void *)ExpandUnitsVariantG;
self->core.ShrinkUnits=(void *)ShrinkUnitsVariantG;
self->core.FreeUnits=(void *)FreeUnitsVariantG;
self->SubAllocatorSize=size;
return self;
}
void FreeSubAllocatorVariantG(PPMdSubAllocatorVariantG *self)
{
free(self);
}
static void InitVariantG(PPMdSubAllocatorVariantG *self)
{
memset(self->FreeList,0,sizeof(self->FreeList));
self->LowUnit=self->HeapStart;
self->HighUnit=self->HeapStart+UNIT_SIZE*(self->SubAllocatorSize/UNIT_SIZE);
self->LastBreath=self->LowUnit;
self->LowUnit+=128*128*UNIT_SIZE;
for(int i=0;i<N1;i++) self->Index2Units[i]=1+i;
for(int i=0;i<N2;i++) self->Index2Units[N1+i]=2+N1+i*2;
for(int i=0;i<N3;i++) self->Index2Units[N1+N2+i]=3+N1+2*N2+i*3;
for(int i=0;i<N4;i++) self->Index2Units[N1+N2+N3+i]=4+N1+2*N2+3*N3+i*4;
int i=0;
for(int k=0;k<128;k++)
{
if(self->Index2Units[i]<k+1) i++;
self->Units2Index[k]=i;
}
}
static uint32_t AllocContextVariantG(PPMdSubAllocatorVariantG *self)
{
if(self->HighUnit!=self->LowUnit)
{
self->HighUnit-=UNIT_SIZE;
return PointerToOffset(self,self->HighUnit);
}
return AllocUnitsVariantG(self,1);
}
static uint32_t AllocUnitsVariantG(PPMdSubAllocatorVariantG *self,int num)
{
int index=self->Units2Index[num-1];
if(self->FreeList[index].next) return PointerToOffset(self,RemoveNode(self,index));
void *units=self->LowUnit;
self->LowUnit+=I2B(self,index);
if(self->LowUnit<=self->HighUnit) return PointerToOffset(self,units);
if(self->LastBreath)
{
uint8_t *ptr=self->LastBreath;
for(int i=0;i<128;i++)
{
InsertNode(self,ptr,N_INDEXES-1);
ptr+=128*UNIT_SIZE;
}
self->LastBreath=NULL;
}
self->LowUnit-=I2B(self,index);
for(int i=index+1;i<N_INDEXES;i++)
{
if(self->FreeList[i].next)
{
void *units=RemoveNode(self,i);
SplitBlock(self,units,i,index);
return PointerToOffset(self,units);
}
}
return 0;
}
static uint32_t ExpandUnitsVariantG(PPMdSubAllocatorVariantG *self,uint32_t oldoffs,int oldnum)
{
void *oldptr=OffsetToPointer(self,oldoffs);
int oldindex=self->Units2Index[oldnum-1];
int newindex=self->Units2Index[oldnum];
if(oldindex==newindex) return oldoffs;
uint32_t offs=AllocUnitsVariantG(self,oldnum+1);
if(offs)
{
memcpy(OffsetToPointer(self,offs),oldptr,I2B(self,oldindex));
InsertNode(self,oldptr,oldindex);
}
return offs;
}
static uint32_t ShrinkUnitsVariantG(PPMdSubAllocatorVariantG *self,uint32_t oldoffs,int oldnum,int newnum)
{
void *oldptr=OffsetToPointer(self,oldoffs);
int oldindex=self->Units2Index[oldnum-1];
int newindex=self->Units2Index[newnum-1];
if(oldindex==newindex) return oldoffs;
if(self->FreeList[newindex].next)
{
void *ptr=RemoveNode(self,newindex);
memcpy(ptr,oldptr,I2B(self,newindex));
InsertNode(self,oldptr,oldindex);
return PointerToOffset(self,ptr);
}
else
{
SplitBlock(self,oldptr,oldindex,newindex);
return oldoffs;
}
}
static void FreeUnitsVariantG(PPMdSubAllocatorVariantG *self,uint32_t offs,int num)
{
InsertNode(self,OffsetToPointer(self,offs),self->Units2Index[num-1]);
}
static void InsertNode(PPMdSubAllocatorVariantG *self,void *p,int index)
{
((struct PPMAllocatorNodeVariantG *)p)->next=self->FreeList[index].next;
self->FreeList[index].next=p;
}
static void *RemoveNode(PPMdSubAllocatorVariantG *self,int index)
{
struct PPMAllocatorNodeVariantG *node=self->FreeList[index].next;
self->FreeList[index].next=node->next;
return node;
}
static unsigned int I2B(PPMdSubAllocatorVariantG *self,int index) { return UNIT_SIZE*self->Index2Units[index]; }
static void SplitBlock(PPMdSubAllocatorVariantG *self,void *pv,int oldindex,int newindex)
{
uint8_t *p=((uint8_t *)pv)+I2B(self,newindex);
int diff=self->Index2Units[oldindex]-self->Index2Units[newindex];
int i=self->Units2Index[diff-1];
if(self->Index2Units[i]!=diff)
{
InsertNode(self,p,i-1);
p+=I2B(self,i-1);
diff-=self->Index2Units[i-1];
}
InsertNode(self,p,self->Units2Index[diff-1]);
}
|
