#ifndef ALLOC_H
#define ALLOC_H
#include<cstdlib>
namespace EASYSTL{
class alloc{
public:
static void* allocate(size_t n);
static void deallocate(void *p,size_t n);
static void* reallocate(void *p, size_t old_sz, size_t new_sz);
private:
enum{_ALLIGN = 8};//小型区块上调的边界
enum{_MAX_BYTES = 128};//一二级配置器的边界
enum{_NFREELISTS = _MAX_BYTES/_ALLIGN};//free-lists 个数
//enum{_NOBJS = 20};//每次增加的节点个数
union obj{ //free-lists 结点结构
union obj* free_list_link;
char client_data[1];
};
//将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes){
return ((bytes + _ALLIGN - 1)&~(_ALLIGN - 1));
}
//16个free-lists
static obj* volatile free_list[_NFREELISTS];
//以下函数根据区块大小，决定使用第n号free-lists n从0开始
static size_t FREELIST_INDEX(size_t bytes){
return ((bytes + _ALLIGN-1)/_ALLIGN -1);
}
//Chunk allocate state
static char *start_free;//内存池起始位置
static char *end_free;//内存池结束位置
static size_t heap_size;
//返回一个大小为n的对象，并可能加入大小为n的其他区块到freefree_list
static void *refill(size_t bytes);
//配置一大块空间，可容纳nobjs个大小为"size"的区块
static char *chunk_alloc(size_t bytes, int &nobjs);
};
}
#endif
#include "alloc.h"
namespace EASYSTL{
char *alloc::start_free = 0;
char *alloc::end_free = 0;
size_t alloc::heap_size=0;
alloc::obj* volatile alloc::free_list[alloc::_NFREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
void* alloc::allocate(size_t n)
{
if(n > _MAX_BYTES)return malloc(n);
obj* volatile * my_free_list;
//寻找16个free-lists中适当的一个
my_free_list = free_list + FREELIST_INDEX(n);
obj *result = *my_free_list;
if(result == 0){
//没找到可用的free list，准备重新填充free-list
void *r=refill(ROUND_UP(n));
return r;
}
*my_free_list=result->fress_list_link;
return(result);
}
void alloc::deallocate(void *p, size_t bytes)
{
if(bytes > _MAX_BYTES)free(p);
obj* q=(obj*)p;
obj *volatile *my_free_list;
my_free_list = free_list + FREELIST_INDEX(n);
q->free_list_link=*my_free_list;
*my_free_list=q;
}
void* alloc::reallocate(void *p, size_t old_sz, size_t new_sz)
{
deallocate(p,old_sz);
p = allocate(new_sz);
return p;
}
void *alloc::refill(size_t bytes)
{
int nobjs =20;
char *chunk=chunk_alloc(bytes,nobjs);
obj * volatile *my_free_list;
obj *result;
obj* current_obj,*next_obj;
int i;
//如果只获得一个区块，这个区块就分配给调用者用，free-list无新节点
if(nobjs == 1)return (chunk);
//否则准备调整free-list，纳入新节点
//以下在chunk空间内建立free list
result = (obj*)chunk;
//以下导引free-list指向新配置的空间
*my_free_list = (obj *)(chunk + bytes);
next_obj = (obj *)(chunk + bytes);
//以下将free-list的各节点串接起来
for(int i = 1; ; i++){
current_obj = next_obj;
current_obj = (obj *)((char *)next_obj + bytes);
if(nobjs - 1 == i){
current_obj -> free_list_link=0;
break;
}
else
{
current_obj -> free_list_link = next_obj;
}
}
return (result);
}
char *alloc::chunk_alloc(size_t bytes, int &nobjs)
{
char *result;
size_t total_bytes = bytes * nobjs;
size_t bytes_left = end_free - start_free;//内存池剩余空间
if(bytes_left > = total_bytes){
//内存池剩余空间完全满足需求量
result = start_free;
start_free +=total_bytes;
return (result);
}
else if(bytes_left >= bytes){
//内存池剩余空间不能完全满足需求量，但足够供应一个以上的区块
nobjs = bytes_left/bytes;
total_bytes = bytes * nobjs;
result = start_free;
start_free += total_bytes;
return (result);
}else{
//内存池剩余空间连一个区块的大小都不能提供
size_t bytes_to_get = 2 * total_bytes +ROUND_UP(heap_size >> 4);
if(bytes_left > 0){
obj * volatile *my_free_list =free_list + FREELIST_INDEX(bytes_left);
((obj *)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
//配置heap空间，用来补充内存池
start_free =(char *)malloc(bytes_to_get);
if(start_free == 0){
obj * volatile *my_free_list = 0,*p;
int i;
for(i = bytes; i <= _MAX_BYTES; i+=_ALLIGN){
my_free_list =free_list + FREELIST_INDEX(i);
p = *my_free_list;
if(p != 0){
*my_free_list = p -> free_list_link;
start_free = start_free +i;
//递归调用自己 为了修正nobjs
return (chunk_alloc(bytes,nobjs));
}
}
end_free = 0;
}
heap_size +=bytes_to_get;
end_free = start_free + bytes_to_get;
return chunk_alloc(bytes,nobjs);
}
}
}
#ifndef CONSTRUCT_H
#define CONSTRUCT_H
#include <new>
namespace EASYSTL{
template<class T1,class T2>
inline void construct(T1* p,const T2& value){
new(p) T1(value);
}
//destroy()的第一版本，接受一个指针
template<class T>
inline void destroy(T* p){
p->~T();
}
//destroy()第二版本，接受两个迭代器。此函数设法找出元素的数值型别
template<class ForwardItator>
inline void destroy(ForwardItator first, ForwardItator end){
_destroy(first, end, value_type(first));
}
//判断元素的数值型别是否有trivial destructor
template<class ForwardItator, class T>
inline void destroy(ForwardItator first, ForwardItator end, T*){
typedef typename _TYPE_TRAITS_<T>::has_trivial_destructor trivial_destructor;
_destroy_aux(first, end, trivial_destructor());
}
//如果元素的数值型别有non-trivial destructor
template<class ForwardItator>
inline void destroy(ForwardItator first, ForwardItator end, _false_type){
for( ;first!=end;first++){
destroy(&*first);
}
}
//如果元素的数值型别有trivial destructor
template<class ForwardItator>
inline void destroy(ForwardItator first, ForwardItator end, _true_type){}
//以下是destroy第二版本针对迭代器为char* 和wchar_t*的特化版
inline void destroy(char* , char*){}
inline void destroy(wchar_t* , wchar_t*);
}
#endif
#ifndef _ALLOCATOR_H_
#define _ALLOCATOR_H_
#include "alloc.h"
#include "construct.h"
#include <cassert>
#include <new>
namespace EasySTL {
template<class T, class Alloc>
class simple_alloc {
public:
static T *allocate(size_t n)
{ return 0 == n ? 0 : (T*) Alloc::allocate(n * sizeof(T));}
static T *allocate(void)
{ return (T*) Alloc::allocate( sizeof(T) );}
static void deallocate(T *p, size_t n)
{ if(0 != n) Alloc::deallocate(p, n * sizeof(T));}
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T));}
};
}
#endif
![C语言第四章自述2第四章 选择结构程序设计[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)