311-STL的alloc.h的实现

约定不等于承诺〃 2022-10-20 05:23 57阅读 0赞

## STL的alloc.h的实现 ##

#ifdef YHP_ALLOC_H
    #define YHP_ALLOC_H
    #include<iostream>
    #include<thread> 
    #include<mutex>
    #include<shared_mutex>
    namespace yhp
    {
        
    
    #ifdef __STL_PTHREADS	
    #include<pthread.h>
    class _Lock
    {
        
    private:
    	pthread_mutex_lock *ps;
    public:
        _Lock(pthread_mutex_t& _S):ps(&_S)
    	{
        
    		pthread_mutex_lock(*ps);
    	}
    	~_Lock()
    	{
        
    		pthread_mutex_unlock(*ps);
    	}	 
    };
    #endif
    
    #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
    
    std::mutex m_lock;
    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;
    	#ifdef __STL_PTHREADS
    	static pthread_mutex_t _S_node_allocator_lock;
    	#endif
        static std::mutex m_lock;
    	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;
    		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);
    		_Lock _lock(_S_node_allocator_lock);
    		std::lock_guard<std::mutex> lock(m_lock);
    		//std::shared_lock<std::mutex> lock(m_lock);
    	    //std::unique_lock<std::mutex> lock(m_lock);
    		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
    		//_Lock _lock(_S_node_allocator_lock);//Linux加锁方案 
    		//std::lock_guard<std::mutex> lock(m_lock);
    		std::shared_lock<std::mutex> lock(m_lock);
    		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 __STL_PTHREADS
    template<bool threads,int ints>
    pthread_mutex_t __default_alloc_template<threads,inst>::_S_node_allocator_lock=
    PTHREAD_MUTEX_INITALIZER;
    
    template<bool threads,int ints>
    std:: __default_alloc_template<threads,inst>::mutex m_lock;
    
    #endif
    
    #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)
    	{
        
    		if(NULL == p) return ;
    		Alloc::deallocate(p,sizeof(T)*n);
    	}
    	static void deallocate(T *p)
    	{
        
    		if(NULL == p) return ;
    		Alloc::deallocate(p,sizeof(T));
    	}
    };
    
    
    }
    
    #endif