sgi-stl-2.91.57 之内存池

代码还是比较简单的，加个main函数多调试几次，自然就知道是什么意思了。

重点在于chunk_alloc这个函数里面的递归调用。
C++语言: Codee#25985001/

002简言之，一个链表数组加一个内存池

003先在数组中找，找不到就向内存池要，如果池子空了，再向系统申请

004/

005

006#include

007#include

008usingnamespacestd;

009

010enum

011{

012__ALIGN=8

013};

014

015enum

016{

017__MAX_BYTES=128

018};

019

020enum

021{

022__NFREELISTS=__MAX_BYTES/__ALIGN

023};

024

025template<boolthreads,intinst>

026class__default_alloc_template

027{

028private:

029staticsize_tROUND_UP(size_tbytes)

030{

031return(((bytes)+__ALIGN-1)&~(__ALIGN-1));

032}

033

034unionobj

035{

036unionobjfree_list_link;

037charclient_data[1];

038};

039

040/

041链表数组

042/

043staticobjvolatilefree_list[__NFREELISTS];

044

045staticsize_tFREELIST_INDEX(size_tbytes)

046{

047return(((bytes)+__ALIGN-1)/__ALIGN-1);

048}

049

050staticvoidrefill(size_tn);

051staticcharchunk_alloc(size_tsize,int&nobjs);

052

053

054staticcharstart_free;//内存池起始地址

055staticcharend_free;//内存池结束地址

056staticsize_theap_size;//堆大小（到目前为止总共向系统申请的内存）

057

058public:

059voidspecial_access(size_tsz,intn)

060{

061chunk_alloc(sz,n);

062}

063

064staticvoidallocate(size_tn)

065{

066objvolatilemy_free_list;

067objresult;

068

069if(n>(size_t)__MAX_BYTES)

070/

071return malloc_alloc::allocate(n);

072/

073returnmalloc((size_t)n);

074

075my_free_list=free_list+FREELIST_INDEX(n);

076result=my_free_list;

077/

078数组中对应项为空表

079/

080if(0==result)

081{

082/

083申请内存，并填充对应表项

084/

085voidr=refill(ROUND_UP(n));

086returnr;

087}

088

089/

090修改表项值

091/

092my_free_list=result->free_list_link;

093returnresult;

094}

095

096staticvoiddeallocate(voidp,size_tn)

097{

098objq=(obj)p;

099objvolatilemy_free_list;

100

101if(n>(size_t)__MAX_BYTES)

102{

103/

104malloc_alloc::deallocate(p, n);

105/

106free(p);

107return;

108}

109

110/

111归还内存，插入对应链表表头处

112/

113

114my_free_list=free_list+FREELIST_INDEX(n);

115q->free_list_link=my_free_list;

116my_free_list=q;

117}

118

119staticvoidreallocate(voidp,size_told_sz,size_tnew_sz);

120};

121

122template<boolthreads,intinst>

123char__default_alloc_template<threads,inst>::start_free=0;

124

125template<boolthreads,intinst>

126char__default_alloc_template<threads,inst>::end_free=0;

127

128template<boolthreads,intinst>

129size_t__default_alloc_template<threads,inst>::heap_size=0;

130

131/

132sgi-stl-2.91.57中原来的代码，现无法通过编译

133注意此处的typename 具体解释见此处：

134http://stackoverflow.com/questions/610245/

135where-and-why-do-i-have-to-put-the-template-and-typename-keywords

136/

137template<boolthreads,intinst>

138typename__default_alloc_template<threads,inst>::objvolatile

139__default_alloc_template<threads,inst>::free_list[__NFREELISTS]=

140{

1410,0,0,0,

1420,0,0,0,

1430,0,0,0,

1440,0,0,0

145};

146

147template<boolthreads,intinst>

148void__default_alloc_template<threads,inst>::refill(size_tn)

149{

150intnobjs=20;

151/

152申请内存块

153/

154charchunk=chunk_alloc(n,nobjs);

155objvolatilemy_free_list;

156objresult;

157objcurrent_obj,next_obj;

158inti;

159

160if(1==nobjs)

161returnchunk;

162my_free_list=free_list+FREELIST_INDEX(n);

163result=(obj)chunk;//第一块拿来用

164my_free_list=next_obj=(obj)(chunk+n);//剩下的插入到对应大小的链表中

165

166/

167建立链表，还是头插法

168/

169for(i=1;;++i)

170{

171current_obj=next_obj;

172next_obj=(obj)((char)next_obj+n);

173if(i==nobjs-1)

174{

175current_obj->free_list_link=0;

176break;

177}

178else

179current_obj->free_list_link=next_obj;

180}

181returnresult;

182}

183

184/

185/

186template<boolthreads,intinst>

187char__default_alloc_template<threads,inst>

188::chunk_alloc(size_tsize,int&nobjs)

189{

190/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~/

191charresult;

192size_ttotal_bytes=sizenobjs;

193size_tbytes_left=end_free-start_free;

194/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~/

195

196if(bytes_left>=total_bytes)

197{

198result=start_free;

199start_free+=total_bytes;

200return(result);

201}

202elseif(bytes_left>=size)

203{

204/

205nobjs引用传参

206为的就是内存只够1块以上又不够20块分配，

207在此处修改为实际上分配到的块数

208/

209

210nobjs=bytes_left/size;

211total_bytes=sizenobjs;

212result=start_free;

213start_free+=total_bytes;

214return(result);

215}

216else

217{

218/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~/

219size_tbytes_to_get=2total_bytes+ROUND_UP(heap_size>>4);

220/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~/

221

222/

223 Try to make use of the

224 left-over piece.

225/

226if(bytes_left>0)

227{

228objvolatilemy_free_list=free_list+FREELIST_INDEX(bytes_left);

229((obj)start_free)->free_list_link=my_free_list;

230my_free_list=(obj)start_free;

231}

232

233start_free=(char)malloc(bytes_to_get);

234if(0==start_free)

235{

236/~~/

237inti;

238/~~/

239

240objvolatilemy_free_list,p;

241

242/

243 Try to make do with

244 what we have. That

245 can't ;

246 hurt. We do not try

247 smaller requests,

248 since that tends ;

249 to result in disaster

250 on multi-process

251 machines.

252/

253/

254申请不到内存，只好在原来的链表中找找看

255有一点就用一点

256/

257for(i=size;i<=__MAX_BYTES;i+=__ALIGN)

258{

259my_free_list=free_list+FREELIST_INDEX(i);

260p=my_free_list;

261if(0!=p)

262{

263my_free_list=p->free_list_link;

264start_free=(char) p;

265end_free=start_free+i;

266return(chunk_alloc(size,nobjs));

267

268/

269 Any leftover

270 piece will

271 eventually

272 make it to the ;

273 right free

274 list.

275/

276}

277}

278

279end_free=0;/ In case of exception. /

280start_free=(char)malloc(bytes_to_get);

281

282/

283 This should either

284 throw an ;

285 exception or remedy

286 the situation. Thus we

287 assume it ;

288 succeeded.

289/

290}

291

292heap_size+=bytes_to_get;

293end_free=start_free+bytes_to_get;

294return(chunk_alloc(size,nobjs));

295}

296}

297

298intmain()

299{

300/

301 just test,debug to see how it works

302/

303__default_alloc_template<false,1>my_alloc;

304

305for(inti=0;i<1024;++i)

306{

307intx=rand()%128+1;

308my_alloc.allocate(x);

309}

310

311return0;

312}原文链接: https://www.cnblogs.com/invisible/archive/2012/04/09/2438474.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍