????????????????????c++?????????????У????????????????Bug
///
/// 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) );
}