固定尺寸内存块的缓冲队列类及C++实现源码

--------------------------------------------------------------------------------
标题: 固定尺寸内存块的缓冲队列类及实现源码
作者: 叶飞虎
日期: 2014.10.21
--------------------------------------------------------------------------------

    在一般的线性操作应用中(如: 接收缓冲区), 可能需要频繁分配和释放内存块, 频繁操
作会给系统带来很大开销, 如何减少系统开销? 通过拉大分配和释放之间间距来降低操作的
频度, 从而达到减少系统开销。

    拉大分配和释放之间间距的方法有很多, 可以通过大内存块自己管理, 也可以通过内存
块缓冲队列。本文着重讲内存块缓冲队列, 涉及队列就会考虑到无锁进出队列, 即进队列和
出队列在二个线程中可以同时操作。无锁队列的实现方法有很多, 有数组方式的环形无锁队
列, 也有链接方式的无锁队列。数组方式在队列容量确定时比较适合, 而链接方式更适合于
队列容量可变情况, 适用性更好。

    数组方式无锁队列见我的博文 <在一读一写限制下，无锁环形队列如何实现？>
    链接方式无锁队列见我的博文 <一读一写情况下，无锁队列如何实现？>

    本文讲的缓冲队列为链接方式, 链接方式一般通过预分配一个结点作为接力点来实现无
锁队列, 优点是实现简单, 缺点是浪费一个结点的内存, 当结点内存块尺寸较大时浪费就大
了。如何不浪费一个结点内存的链接方式无锁队列? 当队列中只有一个结点时, 本缓冲队列
中使用了原子锁进行操作, 这是一种平衡策略, 若读者有更好方法不妨告之一下!

    固定尺寸内存块的缓冲队列类(TKYCache)源码如下:

// =======================================
// Unit   : 固定尺寸的内存块缓冲
// Version: 3.0.0.0 (build 2014.10.21)
// Author : Kyee Ye
// Email  : kyee_ye(at)126.com
// Copyright (C) Kyee workroom
// =======================================

#ifndef _KYCache_H_
#define _KYCache_H_

#include "KYObject.h"

// KYLib 2.0 开始使用 KYLib 命名空间
namespace KYLib
{

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* TKYCache - 固定尺寸的内存块缓冲类 */

// 注:
// 1. 为了多线程存取安全, New 和 Delete 分属二个线程时可以同时操作而不需要加锁,
//    但多线程 New 时必须用锁控制, 多线程 Delete 时必须用锁控制!
// 2. 此缓冲类一般应用于线性操作的类中, 以减少频繁分配和释放内存的缓冲使用.

class TKYCache
{
private:
   // 内存块的链接
   typedef struct
   {
      void*       Self;                // 内存块所属对象
      void*       Next;                // 下一块
   } TLink, *PLink;

public:
   // 构造函数
   // 1. ABlockSize  内存块的固定尺寸, 取值范围: [0x40..0x40000000]
   // 2. AMaxCount   内存块缓冲的最大个数
   TKYCache(long ABlockSize = 1024, long AMaxCount = 256);
   virtual ~TKYCache();

   // 属性
   long           Count() const        { return FPushCount - FPopCount; }
   long           MaxCount() const     { return FMaxCount; }   // default: AMaxCount
   long           BlockSize() const    { return FBlockSize; }  // default: ABlockSize

   // 设置内存块缓冲的最大个数
   void           SetMaxCount(long AMaxCount)
                  { FMaxCount = (AMaxCount >= 0) ? AMaxCount : 0; }

   // 分配固定尺寸的内存块
   void*          New()
                  {
                     TLink* pItem = DoNew();
                     return (pItem != NULL) ? (char*)pItem + sizeof(TLink) : NULL;
                  }

   // 释放固定尺寸的内存块
   void           Delete(void* ABlock)
                  {
                     if (ABlock != NULL)
                     {
                        TLink* pItem = (TLink*)((char*)ABlock - sizeof(TLink));
                        if (pItem->Self == this)
                           DoDelete(pItem);
                     }
                  }

private:
   // 执行分配/释放带链接的内存块
   TLink*         DoNew();
   void           DoDelete(TLink* ALink);

   // 执行清除缓冲队列
   void           DoClear(TLink* AHead);

private:
   TLink*         FHead;               // 缓冲的头链接
   TLink*         FTail;               // 缓冲的尾链接
   long           FFlag;               // 缓冲队列标志
   long           FMaxCount;           // 缓冲最大个数
   long           FBlockSize;          // 内存块的尺寸
   Longword       FPushCount;          // 压入缓冲计数
   Longword       FPopCount;           // 弹出缓冲计数
};

}

#endif

// =======================================
// Unit   : 固定尺寸的内存块缓冲
// Version: 3.0.0.0 (build 2014.10.21)
// Author : Kyee Ye
// Email  : kyee_ye(at)126.com
// Copyright (C) Kyee workroom
// =======================================

#include <malloc.h>
#include "KYCache.h"

// KYLib 2.0 开始使用 KYLib 命名空间
namespace KYLib
{

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* TKYCache - 固定尺寸的内存块缓冲类 */

// ---------------- 构造函数和析构函数 ----------------
// 构造函数
TKYCache::TKYCache(long ABlockSize, long AMaxCount)
{
   // 初始化
   FHead       = NULL;
   FTail       = NULL;
   FFlag       = 0;
   FPushCount  = 0;
   FPopCount   = 0;

   // 设置缓冲最大个数
   FMaxCount   = (AMaxCount >= 0) ? AMaxCount : 0;

   // 设置内存块的尺寸
   if (ABlockSize <= 0x40)
      FBlockSize  = 0x40;
   else if (ABlockSize <= 0x40000000)
      FBlockSize  = ABlockSize;
   else
      FBlockSize  = 0x40000000;
}

// 析构函数
TKYCache::~TKYCache()
{
   // 执行清除缓冲队列
   if (FPopCount != FPushCount)
   {
      FPopCount   = FPushCount;
      DoClear(FHead);
   }
}

// ---------------- 私有函数 ----------------
// 执行分配带链接的内存块
TKYCache::TLink* TKYCache::DoNew()
{
   // 初始化
   TLink* result = NULL;

   // 判断缓冲队列是否为空
   if (FPopCount == FPushCount)
      result = (TLink*)malloc(sizeof(TLink) + FBlockSize);
   else if (FPushCount - FPopCount != 1)
   {
      // 取第一项, 并且计数加 1
      result = FHead;
      FHead  = (TLink*)result->Next;
      FPopCount++;
   }
   else
   {
      // 取第一项
      result = FHead;

      // 判断是否需要等待, 防止 DoDelete 冲突
      if (InterlockedIncrement(&FFlag) == 1)
      {
         FPopCount++;
         if (FPopCount == FPushCount)
         {
            FHead  = NULL;
            FTail  = NULL;
         }
         InterlockedDecrement(&FFlag);
      }
      else
      {
         FPopCount++;
         InterlockedDecrement(&FFlag);

         // 循环等待 FPushCount 变化
         while (FPopCount == FPushCount)
            Sleep(1);
      }

      // 修改缓冲的头链接
      if (result->Next != NULL)
         FHead = (TLink*)result->Next;
   }

   // 初始化链接项
   if (result != NULL)
   {
      result->Self = this;
      result->Next = NULL;
   }

   // 返回结果
   return result;
}

// 执行释放带链接的内存块
void TKYCache::DoDelete(TLink* ALink)
{
   // 判断是否已满
   if (FPushCount - FPopCount >= (Longword)FMaxCount)
      free(ALink);
   else
   {
      // 置空
      ALink->Next = NULL;

      // 引用计数加 1, 若不等于 1 则等待 DoNew 变成 1
      if (InterlockedIncrement(&FFlag) != 1)
         while (FFlag != 1)
            Sleep(0);

      // 判断是否为第一项
      if (FTail == NULL)
      {
         FTail       = ALink;
         FHead       = ALink;
      }
      else
      {
         FTail->Next = ALink;
         FTail       = ALink;
      }

      // 计数加 1, 且引用计数减 1(注: 顺序不能改, 否则可能会导致DoNew死循环)
      FPushCount++;
      InterlockedDecrement(&FFlag);
   }
}

// 执行清除缓冲队列
void TKYCache::DoClear(TLink* AHead)
{
   // 初始化
   void* pCurr;

   // 循环释放
   while (AHead != NULL)
   {
      pCurr = AHead;
      AHead = (TLink*)AHead->Next;

      // 释放
      free(pCurr);
   }
}

}

--------------------------------------------------------------------------------