309-STL的空间配置器(2)

客官°小女子只卖身不卖艺 2023-01-21 11:15 9阅读 0赞

## <alloc.h>的实现代码 ##

#ifndef YHP_ALLOC_H
    #define YHP_ALLOC_H
    #include<iostream>
    namespace yhp
    {
        
    #if 0
    #include<new>
    #define __THROW_BAD_ALLOC throw std::bad_alloc;
    #elif !defined(__THREAD_BAD_ALLOC)
    //#include<iostream>
    #define __THROW_BAD_ALLOC std::cerr<<"out of memory"<<std::endl; exit(1)
    #endif
    
    template<int inst>
    class __malloc_alloc_template
    {
        
    private:
    	static void *oom_malloc(size_t n)
    	{
        
    		void * result = NULL;
    		void (*my_malloc_handler)() = NULL;
    		for(;;)
    		{
        
    			my_malloc_handler = __malloc_alloc_oom_handler;
    			if(NULL == my_malloc_handler)
    			{
        
    				__THROW_BAD_ALLOC;
    			}
    			(*my_malloc_handler)();
    			result = malloc(n);
    			if(result != NULL)
    			{
        
    				return result;
    			}
    		}
    	}
    	static void *oom_realloc(void *p,size_t new_sz)
    	{
        
    		void * result = NULL;
    		void (*my_malloc_handler)() = NULL;
    		for(;;)
    		{
        
    			my_malloc_handler = __malloc_alloc_oom_handler;
    			if(NULL == my_malloc_handler)
    			{
        
    				__THROW_BAD_ALLOC;
    			}
    			(*my_malloc_handler)();
    			result = realloc(p,new_sz);
    			if(result != NULL)
    			{
        
    				return result;
    			}
    		}
    	}
    	static void (*__malloc_alloc_oom_handler)();
    public:
    	static void *allocate(size_t n) // n字节个数，不是元素的个数
    	{
        
    		void *result = malloc(n);
    		if(NULL == result)
    		{
        
    			result = oom_malloc(n);
    		}
    		return result;
    	}
    	static void deallocate(void *p,size_t n)
    	{
        
    		free(p);
    	}
    	static void *reallocate(void *p,size_t old_sz,size_t new_sz)
    	{
        
    		void *result = realloc(p,new_sz);
    		if(NULL == result)
    		{
        
    			result = oom_realloc(p,new_sz);
    		}
    		return result;
    	}
    	static void (*set_malloc_handler(void (*f)()) )() 
    	{
        
    		void (*old)() = __malloc_alloc_oom_handler;
    		__malloc_alloc_oom_handler = f;
    		return old;
    	}
    };
    
    template<int inst>
    void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = NULL;
    ///
    typedef __malloc_alloc_template<0>   malloc_alloc;
    
    /
    
    enum {
         __ALIGN = 8};
    enum {
         __MAX_BYTES = 128};
    enum {
         __NFREELISTS = __MAX_BYTES / __ALIGN }; // 16
    
    template<bool threads,int ints>
    class __default_alloc_template
    {
        
    private:
    	union obj
    	{
        
    		union obj * free_list_link;  // next;
    		char client_data[1];
    	};
    private:
    	static obj * volatile free_list[__NFREELISTS];// 0 1 ... 15
    	static char *start_free;
    	static char *end_free;
    	static size_t heap_size; 
    
    	static size_t ROUND_UP(size_t bytes)
    	{
        
    		return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
    	}
    	static size_t FREELIST_INDEX(size_t bytes)
    	{
        
    		return (bytes + __ALIGN -1) / __ALIGN  - 1;
    	}
    	
    	static char *chunk_alloc(size_t size,int &nobjs)
    	{
        //                              16       20
    		char *result = NULL;
    		size_t total_bytes = size * nobjs; //总的空间大小 
    		size_t bytes_left = end_free - start_free;
    		if(bytes_left >= total_bytes) // 20 块
    		{
        
    			result = start_free;
    			start_free = start_free + total_bytes;
    			return result;
    		}else if(bytes_left >= size) // 1 块
    		{
        
    			nobjs = bytes_left / size;
    			total_bytes = size*nobjs; // nobjs;
    			result = start_free;
    			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;
    			}
    			start_free = (char*)malloc(bytes_to_get);// 
    			if(NULL == start_free)
    			{
        
    				obj * volatile * my_free_list = NULL;
    				for(int i = size ; i <= __MAX_BYTES; i += __ALIGN )
    				{
        
    					my_free_list = free_list + FREELIST_INDEX(i);
    					obj * p = *my_free_list;
    					if(p != NULL)
    					{
        
    						*my_free_list = p->free_list_link;
    						start_free = (char*)p;
    						end_free = start_free + i;
    						return chunk_alloc(size,nobjs);
    					}
    				}
    				start_free = (char*)malloc_alloc::allocate(bytes_to_get);
    			}
    			end_free = start_free + bytes_to_get;
    			heap_size += bytes_to_get;
    			return chunk_alloc(size,nobjs);
    		}
    	}
    	static void *refill(size_t n) // n byte num ; n % 8 == 0;
    	{
        
    		int nobjs = 20;//填充20个块 
    		char *chunk = chunk_alloc(n,nobjs);//申请 
    		if(1 == nobjs)
    		{
        
    			return chunk;
    		}
    		obj * volatile * my_free_list = NULL;
    		obj * result = (obj*)chunk;
    		obj * current_obj = NULL, *next_obj = NULL;
    		int i = 0;
    		my_free_list = free_list + FREELIST_INDEX(n);
    		*my_free_list = next_obj = (obj*)(chunk + n);
    		for(i = 1; ; ++i)
    		{
        
    			current_obj = next_obj;
    			next_obj = (obj*)((char*)next_obj + n);
    			if(i == nobjs - 1)
    			{
        
    				current_obj->free_list_link = NULL;
    				break;
    			}
    			current_obj->free_list_link = next_obj;//一个一个串起来 
    		}
    		return result;
    	}
    
    public:
    	static void *allocate(size_t n)// n byte num;
    	{
        
    		if(n > (size_t)__MAX_BYTES)
    		{
        
    			return malloc_alloc::allocate(n);
    		}
    		obj * volatile * my_free_list = NULL;
    		obj * result = NULL;
    
    		my_free_list = free_list + FREELIST_INDEX(n);
    		result = *my_free_list;
    		if(NULL == result)
    		{
        
    			void *r = refill(ROUND_UP(n));// n 12 = 16
    			return r;
    		}
    		*my_free_list = result->free_list_link;//指向后继 
    		return result;
    	}
    	static void deallocate(void *p,size_t n)
    	{
        
    		if(n > (size_t) __MAX_BYTES)
    		{
        
    			malloc_alloc::deallocate(p,n);
    			return ;
    		}
    		obj *q = (obj*)p;
    		obj * volatile * my_free_list = free_list + FREELIST_INDEX(n);// 12  // 16
    		q->free_list_link = *my_free_list;//头插 
    		*my_free_list = q;
    		return ;
    	} // malloc realloc , 
    	static void *reallocate(void *p,size_t old_sz,size_t new_sz)
    	{
        
    		if(old_sz > __MAX_BYTES && new_sz > __MAX_BYTES)
    		{
        
    			return malloc_alloc::reallocate(p,old_sz,new_sz);
    		}
    		if(ROUND_UP(old_sz) == ROUND_UP(new_sz))// 12 14 // 16
    		{
        
    			return p;
    		}
    		// old_sz < 128  new_sz < 128;
    		//    >               <
    		//   <                >
    		size_t sz = old_sz < new_sz ? old_sz:new_sz;
    		void *s = allocate(new_sz);
    		memmove(s,p,sz);
    		deallocate(p,old_sz);
    		return s;
    	}
    };
    template<bool threads,int ints>
    typename __default_alloc_template<threads,ints>::obj * volatile
    __default_alloc_template<threads,ints>::free_list[__NFREELISTS]={
        NULL};
    
    template<bool threads,int ints>
    char * __default_alloc_template<threads,ints>::start_free = NULL;
    
    template<bool threads,int ints>
    char * __default_alloc_template<threads,ints>::end_free = NULL;
    
    template<bool threads,int ints>
    size_t __default_alloc_template<threads,ints>::heap_size = 0;
    //
    
    #ifdef __USE_MALLOC   // 开关 
    typedef __malloc_alloc_template<0> malloc_alloc;
    typedef malloc_alloc               alloc;
    #else
    typedef __default_alloc_template<0,0> alloc;//开关 ，默认使用二级配置器 
    #endif
    
    template<class T, class Alloc>
    class simple_alloc//
    {
        
    public:
    	static T * allocate(size_t n)  /// n 个T type元素 num ;
    	{
        
    		return (T*)Alloc::allocate(sizeof(T)*n); // array;相当于模拟new [] 开辟一组元素 
    	}
    	static T * allocate()//无参 
    	{
        
    		return (T*)Alloc::allocate(sizeof(T)); // 开辟1个元素    //相当于模拟 new 
    	}
    	static void deallocate(T *p,size_t n)//释放元素  相当于operator delete[] 
    	{
        
    		if(NULL == p) return ;
    		Alloc::deallocate(p,sizeof(T)*n);
    	}
    	static void deallocate(T *p)//释放 相当于delete 
    	{
        
    		if(NULL == p) return ;
    		Alloc::deallocate(p,sizeof(T));
    	}
    };
    
    }
    #endif

## <construct.h>的实现 ##

#ifndef YHP_CONSTRUCT_H
    #define YHP_CONSTRUCT_H
    #include"yhp_iterator.h"
    #include"yhp_type_traits.h"
    namespace yhp
    {
        
    template<class T1,class T2>
    inline void construct(T1 *p,const T2 &val)
    {
        
    	new(p) T1(val);
    }
    template<class T>
    inline void construct(T *p)
    {
        
    	new(p)  T();
    }
    
    template<class T>
    inline void destroy(T *p)
    {
        
    	p->~T();
    }
    
    template<class _FI>
    inline void destroy(_FI _F, _FI _L)
    {
        
    	__destroy(_F,_L,value_type(_F));
    }
    template<class _FI,class T>
    inline void __destroy(_FI _F,_FI _L , T *)
    {
        
    	__type_traits<T>();
    	typedef typename __type_traits<T>::has_trivial_destructor  dest;
    	__destroy_aux(_F,_L,dest());
    }
    template<class _FI>
    inline void __destroy_aux(_FI _F,_FI _L , __true_type)
    {
        }
    
    template<class _FI>
    inline void __destroy_aux(_FI _F,_FI _L , __false_type)
    {
        
    	for(; _F != _L; ++_F)
    	{
        
    		destroy(&*_F);
    	}
    }
    
    }
    #endif

## 仿写双链表list， <list.h> ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**\_A就是我们的一级配置器。**  
**通过包装识别出购买结点的类型的大小自动进行购买**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**双链表的插入图示如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]

#pragma once
    
    #include"yhp_alloc.h"//开空间 
    #include"yhp_construct.h"//构造对象 
    
    namespace yhp
    {
        
    template<class _Ty,class _A = yhp::alloc>
    
    class list
    {
        
    private:
    	struct _Node;
    	typedef struct _Node* _Nodeptr;
    	struct _Node
    	{
        
    		_Nodeptr _Prev, _Next;//前驱，后继 
    		_Ty _Value;//值域 
    	};
    
    	struct _Acc;
    	struct _Acc
    	{
        
    		typedef struct _Node*& _Nodepref;//引用 指针类型 
    		typedef _Ty& _Vref;//值的引用类型 
    		static _Vref _Value(_Nodeptr _P)
    		{
        
    			return (*_P)._Value;
    		}
    		static _Nodepref _Prev(_Nodeptr _P)
    		{
        
    			return (*_P)._Prev;
    		}
    		static _Nodepref _Next(_Nodeptr _P)
    		{
        
    			return (*_P)._Next;
    		}
    
    	};
    
    public: 
        //进行分解 
    	typedef _Ty value_type;
    	typedef _Ty& reference;
    	typedef _Ty* pointer;
    	typedef const _Ty& const_reference;
    	typedef const _Ty* const_pointer;
        //以上做法是 为以后对list的萃取类型 
    	typedef _A  allocator_type;
    	typedef yhp::simple_alloc<_Node, _A> data_allocate;//进一步的说明 
    public:
    	class iterator;//普通迭代器，可以取值或者赋值 
    	class const_iterator;//常性迭代器，只能取值，不能赋值 
    
    	friend class iterator;
    	friend class const_iterator;
    
    	class const_iterator
    	{
        
    	public:
    		const_iterator(_Nodeptr _P = nullptr) :_Ptr(_P) {
        }//构造函数 
    		const_reference operator*() const//重载*，把迭代器所指之物返回 
    		{
        
    			return _Acc::_Value(_Ptr);
    		}
    		const_pointer operator->() const//重载-> 迭代器访问的数据的地址 
    		{
        
    			return (&**this);
    		}
    		const_iterator operator++()//重载前置++ 
    		{
        
    			_Ptr = _Acc::_Next(_Ptr);
    			return *this;
    		}
    		const_iterator operator++(int)//重载后置++ 
    		{
        
    			const_iterator  _Tmp = *this;
    			++* this;
    			return _Tmp;
    		}
    		const_iterator operator--()//重载前置-- 
    		{
        
    			_Ptr = _Acc::_Prev(_Ptr);
    			return *this;
    		}
    		const_iterator operator--(int)//重载后置-- 
    		{
        
    			const_iterator  _Tmp = *this;
    			--* this;
    			return _Tmp;
    		}
    		bool operator==(const const_iterator _X) const//重载== 
    		{
        
    			return this->_Ptr == _X._Ptr;
    		}
    		bool operator!=(const const_iterator _X) const//重载！= 
    		{
        
    			return !(*this == _X);
    		}
    
    		_Nodeptr _Mynode() const//获取指针 
    		{
        
    			return _Ptr;
    		}
    	protected:
    		_Nodeptr _Ptr;
    	};
    
    	
    	class iterator : public const_iterator//普通迭代器 
    	{
        
    	public:
    		iterator(_Nodeptr _P = nullptr) :const_iterator(_P) {
        }
    		reference operator*() const
    		{
        
    			return _Acc::_Value(this->_Ptr);
    		}
    		pointer operator->() const
    		{
        
    			return (&**this);
    		}
    		iterator operator++()
    		{
        
    			this->_Ptr = _Acc::_Next(this->_Ptr);
    			return *this;
    		}
    		iterator operator++(int)
    		{
        
    			iterator  _Tmp = *this;
    			++* this;
    			return _Tmp;
    		}
    		iterator operator--()
    		{
        
    			this->_Ptr = _Acc::_Prev(this->_Ptr);
    			return *this;
    		}
    		iterator operator--(int)
    		{
        
    			iterator  _Tmp = *this;
    			--*this;
    			return _Tmp;
    		}
    		bool operator==(const iterator _X) const
    		{
        
    			return this->_Ptr == _X._Ptr;
    		}
    		bool operator!=(const iterator _X) const
    		{
        
    			return !(*this == _X);
    		}
    	};
    
    public:
    	iterator begin() {
         return iterator(_Acc::_Next(_Head)); }//获取第一个数据结点 
    	iterator end() {
         return iterator(_Head); }//最后一个结点的后继，也就是头 
    	const_iterator begin() const {
         return const_iterator(_Acc::_Next(_Head)); }
    	const_iterator end() const {
         return const_iterator(_Head); }
    public:
    	typedef const_iterator _It;//常性迭代器的别名 
    	list() :_Size(0), _Head(_Buynode()) {
        }//构造函数 
    	~list() {
        }//析构函数 
    
    	reference front() {
         return *begin(); }//取得链表的第一个元素 
    	const_reference front() const {
         return *begin(); }//取得链表的第一个元素，常性 
    	reference back() {
         return *--end(); }//取得链表的最后一个元素 
    	const_reference back() const {
         return *--end(); }//取得链表的最后一个元素，常性 
    
    	iterator insert(iterator _P, const _Ty& _X)//插入函数，数据的插入，在_p之前插入_x 
    	{
        
    		_Nodeptr _S = _P._Mynode();
    		_Acc::_Prev(_S) = _Buynode(_Acc::_Prev(_S), _S);
    		_S = _Acc::_Prev(_S);
    		_Acc::_Next(_Acc::_Prev(_S)) = _S;
    		yhp::construct(&_Acc::_Value(_S), _X);
    		_Size += 1;
    		return iterator(_S);
    	}
    
    	void push_front(const _Ty& _X)//头插 
    	{
        
    		insert(begin(), _X);
    	}
    	void push_back(const _Ty& _X)//尾插 
    	{
        
    		insert(end(), _X);
    	}
    	void insert(iterator _P, size_t _N, const _Ty& _X)//在_p位置插入_N个_x 
    	{
        
    		for (int i = 0; i < _N; ++i)
    		{
        
    			insert(_P, _X);
    		}
    	}
    	void insert(iterator _P, const _Ty* _F, const _Ty* _L)//把*_F到*_ L的连续空间插入到_p的位置 
    	{
        
    		for (; _F != _L; ++_F)
    		{
        
    			insert(_P, *_F);
    		}
    	}
    	void insert(iterator _P, _It _F, _It _L)//把另一个链表的_F到_L插入到这条链表的_p的位置 
    	{
        
    		for (; _F != _L; ++_F)
    		{
        
    			insert(_P, *_F);
    		}
    	}	
    
    private:  
    	_Nodeptr _Buynode(_Nodeptr _Parg = nullptr, _Nodeptr _Narg = nullptr)//购买结点 
    	{
        
    		_Nodeptr _S = data_allocate::allocate(1);
    		_Acc::_Prev(_S) = _Parg == nullptr ? _S : _Parg;
    		_Acc::_Next(_S) = _Narg == nullptr ? _S : _Narg;
    		return _S;
    	}
    	void _Freenode(_Nodeptr _P)//释放结点 
    	{
        
    		data_allocate::deallocate(_P, 1);
    	}
    	_Nodeptr _Head; 
    	size_t   _Size;
    	_A       allocator;
    };
    
    }

**测试代码如下**

int main()
    {
        
    	int ar[] = {
         12,23,34,45,56,67,78,89,90,100 };
    	int n = sizeof(ar) / sizeof(ar[0]);
    
    	yhp::list<int>  mylist;
    
    	mylist.insert(mylist.end(), ar, ar + n);
    
    	return 0;
    
    }

#include<iostream>
    #include<thread>
    using namespace std;
    #include"yhp_alloc.h"
    #include"yhp_list.h"
    yhp::list<int> mylist;
    
    
    void fun1()
    {
        
    	for (int i = 0; i < 20; i += 2)
    	{
        
    		mylist.push_back(i);
    	}
    }
    void fun2()
    {
        
    	for (int i = 51; i < 70; i += 2)
    	{
        
    		mylist.push_back(i);
    	}
    }
    int main()
    {
        
    	thread thd1(fun1);
    	thread thd2(fun2);
    
    	thd1.join();
    	thd2.join();
    	return 0;
    }

**参考谷歌的内存池**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/a32c996db12a4856a478663ae3b3fe14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221020/6ea6ef5a0c5b464dbf803290097a4053.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221020/7f957d2ab5e244adb37464eea0d74d9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221020/aad7d29ccbc54e23a5e4893808b02b99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221020/1fb0eadae2bb4a06b8c2a178424a9fc0.png