/// /// Copyright (c) 2014 xseekerj, All Rights Reserved. /// #include <stdlib.h> #include <stdio.h> #include <time.h> #include <math.h> #include <stdint.h> #include <string.h> #include <mutex> #define nullptr 0 inline int rrand(int min, int max) { return ( rand() % ((max) - (min)) + (min) ); } /* * size in bytes constant: SZ Definition */ #ifndef _POL_SZ #define _POL_SZ static const uint64_t __B__ = (1); static const uint64_t __KB__ = (1024 * __B__) ; static const uint64_t __MB__ = (1024 * __KB__); static const uint64_t __GB__ = (1024 * __MB__); static const uint64_t __TB__ = (1024 * __GB__); static const uint64_t __PB__ = (1024 * __TB__); static const uint64_t __EB__ = (1024 * __PB__); #define __b__ __B__ #define __k__ __K__ #define __m__ __M__ #define __g__ __G__ #define __t__ __T__ #define __e__ __E__ #define __K__ __KB__ #define __M__ __MB__ #define __G__ __GB__ #define __T__ __TB__ #define __P__ __PB__ #define __E__ __EB__ #define SZ(n, u) ( (n) * __##u##__ ) static const uint8_t __MAX_UINT8 = SZ(256, B) - 1; static const uint16_t __MAX_UINT16 = SZ(64, KB) - 1; static const uint32_t __MAX_UINT32 = SZ(4, GB) - 1; static const uint64_t __MAX_UINT64 = SZ(15, EB) + (SZ(1, EB) - 1); #endif /* _POL_SZ */ #define sz_align(d,a) (((d) + (a - 1)) & ~(a - 1)) // #define EANBLE_MULTI_THREAD 1 class mempool { struct memblock_head_t { memblock_head_t* prev; memblock_head_t* next; size_t size; bool unused; }; struct memblock_foot_t { memblock_head_t* uplink; }; static const size_t reserved_size = sizeof(memblock_head_t) + sizeof(memblock_foot_t); static const size_t min_size = sizeof(void*) * 2; static const size_t min_block_size = reserved_size + min_size; #define FOOT_LOC(h) ((memblock_foot_t*)( (char*)h + h->size - sizeof(memblock_foot_t) ) ) #define HEAD_LOC(pu) ( (memblock_head_t*)( (char*)pu - sizeof(memblock_head_t) ) ) #define UPDATE_FOOT(h) ( FOOT_LOC(h)->uplink = h ) #define LEFT_FOOT_LOC(h) ( (memblock_foot_t*)( (char*)h - sizeof(memblock_foot_t) ) ) #define RIGHT_HEAD_LOC(h) ( (memblock_head_t*)( (char*)h + h->size ) ) #define REMAIN_SIZE(blk,n) (blk->size - reserved_size - (n) ) // calculate remain size after n bytes allocated. public: mempool(size_t size = SZ(64, k)) { init(size); } ~mempool(void) { free(memory_); } void init(size_t size) { size = sz_align(size, SZ(64, k)); memory_ = malloc(size); memblock_head_t* header = (memblock_head_t*)(memory_); header->size = size; header->unused = true; header->prev = header; header->next = header; this->freelist_ = FOOT_LOC(header)->uplink = header; this->memory_size_ = size; } void* allocate(size_t size) { #ifdef EANBLE_MULTI_THREAD std::unique_lock<std::mutex> guard(this->mtx_); #endif size_t n = sz_align(size, min_size); memblock_head_t* blk = freelist_; for(; blk != nullptr && blk->size - reserved_size < n && blk->next != freelist_; blk = blk->next){;} if(blk == nullptr || blk->size - reserved_size < n) { return malloc(size); } else { blk->unused = false; char* p = (char*)blk + sizeof(memblock_head_t); if( REMAIN_SIZE(blk, n) < min_block_size ) /* can't construct the new memory block to respond any alloc request. */ { // blk->size = if(blk == freelist_) { freelist_ = nullptr; } else { freelist_->prev = blk->next; blk->next->prev = freelist_; } } else { /* remain block */ memblock_head_t* reblock = (memblock_head_t*)(p + n + sizeof(memblock_foot_t)); reblock->unused = true; reblock->size = (char*)blk + blk->size - (char*)reblock; UPDATE_FOOT(reblock); blk->size = (char*)reblock - (char*)blk; UPDATE_FOOT(blk); if(blk->next == blk) { // self blk->next = reblock; blk->prev = reblock; reblock->prev = blk; reblock->next = blk; } else { // insert reblock->prev = blk; reblock->next = blk->next; blk->next->prev = reblock; blk->next = reblock; // ptr->prev = reblock; } freelist_ = reblock; } return p; } } void deallocte(void* pUserData) { if(!belong_to(pUserData)) { free(pUserData); return; } #ifdef EANBLE_MULTI_THREAD std::unique_lock<std::mutex> guard(this->mtx_); #endif memblock_head_t* curh = HEAD_LOC(pUserData); memblock_foot_t* lf = LEFT_FOOT_LOC(curh); memblock_head_t* rh = RIGHT_HEAD_LOC(curh); bool vlf = is_valid_leftf(lf); bool vrh = is_valid_righth(rh); #ifdef _DEBUG memset(pUserData, 0x0, curh->size - reserved_size); #endif if( ( vlf && lf->uplink->unused ) && (!vrh || !rh->unused) ) { // merge curret to left block lf->uplink->next = curh->next; if(curh->next != nullptr) curh->next->prev = lf->uplink; lf->uplink->size += curh->size; UPDATE_FOOT(lf->uplink); this->freelist_ = lf->uplink; } else if( (vrh && rh->unused) && (!vlf || !lf->uplink->unused ) ) { // merge right to current block curh->unused = true; curh->next = rh->next; if(rh->next != nullptr) rh->next->prev = curh; curh->size += rh->size; UPDATE_FOOT(curh); this->freelist_ = curh; } else if( (vlf && lf->uplink->unused) && (vrh && rh->unused) ) { // merge current and right to left block lf->uplink->next = rh->next; if(rh->next != nullptr) rh->next->prev = lf->uplink; lf->uplink->size += (curh->size + rh->size); UPDATE_FOOT(lf->uplink); this->freelist_ = lf->uplink; } else { // no need merge curh->unused = true; this->freelist_ = curh; } } bool belong_to(void* p) { return p >= this->memory_ && p < ( (char*)this->memory_ + this->memory_size_ ); } bool is_valid_leftf(void* lf) { return ((char*)lf > ( (char*)this->memory_ + sizeof(memblock_head_t)) ); } bool is_valid_righth(void* rh) { return (char*)rh < ((char*)this->memory_ + memory_size_ - sizeof(memblock_foot_t) ); } |
