几种常用数据结构的C语言实现

队列

/**
  ******************************************************************************
  * @file           : myfifo.c
  * @brief          : 先入先出队列实现
  * @author         : huanglidi
  ******************************************************************************
  */
#include "myfifo.h"
#include "rtthread.h"

typedef struct
{
    void * queue;
    uint8_t fifo_size;
    uint8_t item_size;

    int16_t wIndex;
    int16_t rIndex;
}myfifo_t;

void InitFifo(myfifo_t* handle, uint8_t size, uint8_t item_size)
{
    if (!handle) return;

    handle->fifo_size = size;
    handle->item_size = item_size;
    handle->wIndex = 0;
    handle->rIndex = 0;
    handle->isFull = 0;
    handle->isEmpty = 1;
    handle->queue = rt_malloc(size * item_size);
}

void ReleaseFifo(myfifo_t* handle)
{
    if (!handle) return;
    rt_free(handle->queue);
    handle->queue = NULL;
    handle->wIndex = 0;
    handle->rIndex = -1;
    handle->fifo_size = 0;
    handle->item_size = 0;
}

bool FifoPush(myfifo_t* handle, void* data)
{
    uint8_t size        = handle->fifo_size;
    uint8_t item_size   = handle->item_size;

    if (!handle) return false;
    if (handle->wIndex == handle->rIndex){  //队列满
        retrun false;
    }

    int offset = item_size*handle->wIndex;
    memcpy(handle->queue+offset, data, item_size);
    handle->wIndex = (handle->wIndex+1)%size;

}

bool FifoPop(myfifo_t* handle, void* data)
{
   uint8_t size        = handle->fifo_size;
   uint8_t item_size   = handle->item_size;

   if (!handle) return false;

   if (-1 == handle->rIndex){
      handle->rIndex = 0;
   }

   if (handle->rIndex == handle->wIndex){
       return false;
   }

   int offset = item_size*handle->rIndex;
   memcpy(data, handle->queue+offset, item_size);
   handle->rIndex = (handle->rIndex+1)%size;;
}

uint8_t GetQueueRealSize(myfifo_t* handle)
{
    if (handle->wIndex >= handle->rIndex) {
        return (handle->wIndex - handle->rIndex);
    }
    else if(handle->wIndex < handle->rIndex){
        retrun (handle->fifo_size - handle->rIndex + 1 + handle->rIndex);
    }

}

bool IsFull()
{
    return (handle->wIndex == handle->rIndex);
}

bool IsEmpty()
{
    return ((handle->rIndex+1)%size == handle->wIndex);
}

内存池

typedef struct {
    DevMsg_List_t** m_arrMsgList;
    uint8_t* m_freeFlag;
    uint16_t m_poorUseSize;
    uint16_t m_poorMaxSize;
    uint16_t m_poorIndex;
}Mem_PoorHandle_t;

/*******消息队列内存池 add by: huanglidi*******/
bool GetNodeFlag(Mem_PoorHandle_t *pHandle, uint16_t index)
{
    if (NULL == pHandle || NULL == pHandle->m_freeFlag)
    {
        return false;
    }
    if (index < 0 || index > pHandle->m_poorMaxSize)
    {
        return false;
    }

    return pHandle->m_freeFlag[index/8] & (1 << (index%8));
}

void SetNodeFlag(Mem_PoorHandle_t *pHandle, uint16_t index, bool set)
{
    if (NULL == pHandle || NULL == pHandle->m_freeFlag)
    {
        return;
    }
    if (index < 0 || index > pHandle->m_poorMaxSize)
    {
        return;
    }

    if (set)
    {
        pHandle->m_freeFlag[index/8] |= (1 << (index%8));
        if (pHandle->m_poorUseSize < pHandle->m_poorMaxSize)
            pHandle->m_poorUseSize++;
    }
    else
    {
        pHandle->m_freeFlag[index/8] &= ~(1 << (index%8));
        if (pHandle->m_poorUseSize > 0)
            pHandle->m_poorUseSize--;
    }
}

void RealeseMsgNodePoor(Mem_PoorHandle_t* pHandle);

//初始化内存池
void InitMsgNodePoor(Mem_PoorHandle_t *pHandle, uint16_t size)
{
    if (!pHandle)
    {
        return;
    }

    if (NULL != pHandle->m_arrMsgList || NULL != pHandle->m_freeFlag)
    {
        RealeseMsgNodePoor(pHandle);
    }

    pHandle->m_poorUseSize   = 0;
    pHandle->m_poorIndex     = 0;
    pHandle->m_poorMaxSize   = size;

    //
    pHandle->m_arrMsgList = rt_malloc(size*sizeof(DevMsg_List_t *));
    for(int i = 0; i < size; i++)
    {
        pHandle->m_arrMsgList[i] = rt_malloc(sizeof(DevMsg_List_t));
    }
    pHandle->m_freeFlag = rt_malloc(size/8+1);

    memset(pHandle->m_freeFlag, 0, size/8+1);
}

//释放内存池
void RealeseMsgNodePoor(Mem_PoorHandle_t* pHandle)
{
   if (!pHandle) return;

   for(int i = 0; i < pHandle->m_poorMaxSize; i++)
   {
       rt_free(pHandle->m_arrMsgList[i]);
   }
   rt_free(pHandle->m_arrMsgList);
   rt_free(pHandle->m_freeFlag);

   pHandle->m_arrMsgList     = NULL;
   pHandle->m_freeFlag       = NULL;
   pHandle->m_poorUseSize    = 0;
   pHandle->m_poorMaxSize    = 0;
   pHandle->m_poorIndex      = 0;

}
//从内存池获取一个节点
DevMsg_List_t* GetOneFreeNode(Mem_PoorHandle_t *pHandle)
{
    if (!pHandle || pHandle->m_poorUseSize >= pHandle->m_poorMaxSize)    //已经没有空闲节点了
    {
        return NULL;
    }
    uint16_t last = pHandle->m_poorIndex;

    do{
        if (!GetNodeFlag(pHandle, pHandle->m_poorIndex))
        {
            SetNodeFlag(pHandle, pHandle->m_poorIndex, true);   //设置使用标志
            return pHandle->m_arrMsgList[pHandle->m_poorIndex];
        }
        pHandle->m_poorIndex = (pHandle->m_poorIndex+1)%pHandle->m_poorMaxSize;
    }while(pHandle->m_poorIndex != last);

    return NULL;
}

//释放一个内存池节点, 以便其他人继续继续使用, 注意: 节点内存不会释放
void FreePoorNode(Mem_PoorHandle_t *pHandle, DevMsg_List_t* node)
{
    if (NULL == pHandle || NULL == pHandle->m_arrMsgList) return;
    for(int i = 0; i < pHandle->m_poorMaxSize; i++)
    {
       if (pHandle->m_arrMsgList[i] && pHandle->m_arrMsgList[i] == node)
       {
           SetNodeFlag(pHandle, i, false);
           break;
       }
    }
}
/**********************内存池**************************/

这里是项目中用到的一些常用数据结构，后面会继续补充！

负数补码形式

正数，本身就是补码。负数，就用它的正数，减一取反，即可得到补码。如，已知：＋9 的二进制是：0000 1001。下面求－9 补码：先减一：0000 1001 - 1 = 0000 1000；再取反：1111 0111。