用阶梯数组实现固定块缓存池

    每次在设计新的网络服务器时，都会愁于反复为各种对象实现内存池，特别是最常用的链表、哈希表、IO缓存块，总无法平衡扩展性、性能、内存占用，红黑树或定长块都不顶用。最近再次研究apache及nginx的池设计，一下子好像想通了。

    无论链表、哈希表、IO缓存块，实现起来都不外是增删改查，效率瓶颈都是在malloc调用以及定位目标块的速度，只要能减少结点规模增长下的malloc次数，再能用位操作来直接定位，一定会很块。

    考虑用阶梯式的二维数组来存储块，阶级之间两倍块数增长，并用同样的阶梯数组来存储空闲指针，这样即使基数用1024字节，在第20阶也能存储2^29个结点了，总2^30-1约10亿结点，总共malloc才20次解决了内存申请的瓶颈；

    在阶梯数组里，定位第n个块，需要找出n作为二进制时最高为1的位置x，它就是梯级号。然后n减去前x项和，就是它所在梯级里的块偏移y.这都好实现。

    后面附上实现，在本人的T42上测试，用它来实现双向链表，1千万条int记录插入约用时600毫秒，占用内存约180M，遍历并间断删除2百万条约用时200毫秒，析构约用时200毫秒。而stl的list，上述几个数据分别约为1700ms，235M, 600ms，1800ms.用来实现hash表时，其插入差距更大，基本上够用了。

#ifndef _BPOOL_H_
#define _BPOOL_H_

#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

#ifdef __cplusplus
extern "C" {
#endif

#ifdef _MSC_VER
#define inline _inline
#endif

#define SIZE_AUTO_EXPAND 0 ///自由增长
#define ARRAY_ALLOC_BASE 10 ///表示第一阶梯数组的块数是1024
#define MAX_ARRAY_INDEX 18 ///最大阶梯数

typedef struct bpool_t {
    int maxcount; //最大块数支持
    int nblock; //使用中的块数
    int nfreeblock; //空闲块数
    int nallblock; //已申请块数
    int nindex; //已使用到的梯级号
    int bsize; //每块字节数
    void **freeits[MAX_ARRAY_INDEX]; //空闲指针阶梯数组
    void *allits[MAX_ARRAY_INDEX]; //块所在的阶梯数组
} bpool_t;

static inline void bpool_init (bpool_t *bp, int maxcount, int bsize)
{
    assert (bp);
    memset (bp, 0, sizeof(bpool_t));
    bp->maxcount = maxcount;
    bp->bsize = bsize;
}

static inline void bpool_clear (bpool_t *bp)
{
    int i;
    assert (bp);
    for (i=0; i<bp->nindex; i++) {
        //if (bp->allits[i]) free (bp->allits[i]);
        if (bp->freeits[i]) free ((void*)bp->freeits[i]);
    }
}

//计算32位前导0数，抄的
static inline int nlz(unsigned x)
{
   int n = 1;
   if (x == 0) return(32);
   if ((x >> 16) == 0) {n = n +16; x = x <<16;}
   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
   if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
   if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
   n = n - (x >> 31);
   return n;
}

// 1 2 4 8 16...2^19
static inline void *bpool_locat_block (void *head[], int offset, int isize)
{
    //第几个索引数组,先除以基数，再取最高为1的位的位置
    //前加1是保证为0或全1时进位，后减1是为了从0开始取索引
    //对于freeits和allits阶梯数组，第i个数组有base*(i^2)个项
    //则对于第n个，其梯级号是
    int x = 32 - nlz((offset>>ARRAY_ALLOC_BASE) + 1) - 1;
    //数组内偏移, 减去前x个之和
    int y = offset - (((1<<x)-1) << ARRAY_ALLOC_BASE); //前x个之和
    char *arr = head[x];
    assert (x < MAX_ARRAY_INDEX);
    assert (y < ((1<<x)<<ARRAY_ALLOC_BASE));
    return (void*)(arr+y*isize);
}

static inline void *bpool_alloc_block(bpool_t *bp)
{
    int len = 0;
    int ncount = 0;
    void *node, **pret=NULL;
    char *mem = NULL;

    if (bp->nfreeblock > 0)
     goto __found;

    ncount = (1<<bp->nindex)<<ARRAY_ALLOC_BASE;
    if (bp->maxcount!=SIZE_AUTO_EXPAND && ncount > bp->maxcount - bp->nallblock)
        ncount = bp->maxcount-bp->nallblock;

    if (ncount<=0 || bp->nindex == MAX_ARRAY_INDEX)
        return NULL;//到限制了

    //新增加数组
    mem = (char*)malloc ((sizeof(void*) + bp->bsize) * ncount);
    if (!mem)
        return NULL;

    len = sizeof(void*)*ncount;
    bp->freeits[bp->nindex] = (void**)mem;
    bp->allits[bp->nindex] = (void*)(mem+len);

    //只需要初始化freeits
    memset (bp->freeits[bp->nindex], 0, len);
    bp->nindex++;

    //freeits里有itemcount个未确定其真实空闲void内存的位置.为NULL
    //allits里有itemcount个未作任何挂接的位置
    //除了第一个要返回使用，其它空闲要加到free里
    //每次申请时再动态挂接上
    bp->nallblock += ncount;
    bp->nfreeblock += ncount;

__found:
    //目标是取me->nfreeblock--的位置
    bp->nfreeblock--;
    pret = (void**)bpool_locat_block ((void**)bp->freeits, bp->nfreeblock, sizeof(void*));
    if (!*pret)
        //原先未放有void内存，这个时候再挂接上去
        //挂谁上去？此时满足count+ not_mount =nallblock
        //例如第3次时，cnt=3，应挂第3个
        //如果归还过，则直到用完以前归还的item，才会进本分支
        *pret = (void*)bpool_locat_block ((void**)bp->allits, bp->nblock, bp->bsize);

    bp->nblock++;
    //拿走后要设置这个位置为空，否则若再扩展就会污染
    node = *pret;
    *pret = NULL;
    return node;
}

static inline void bpool_free_block (bpool_t *bp, void *p)
{
    //直接将此void*挂接到freeits的最后可用结点上
    void **pret = (void**)bpool_locat_block ((void**)bp->freeits, bp->nfreeblock, sizeof(void*));
    assert (pret && bp->nfreeblock < bp->nallblock);
    *pret = p;
    bp->nblock--;
    bp->nfreeblock++;
}

#ifdef __cplusplus
}
#endif

#endif //_BPOOL_H_