一个不错的队列代码，发给大家看看 (amobbs.com 阿莫电子技术论坛) -

cyj_0220 发表于 2013-5-15 21:50:21

一个不错的队列代码，发给大家看看

本帖最后由 cyj_0220 于 2013-5-16 09:15 编辑

从书上抄下来的，觉得不错，发给大家看看
/*******************************************************************************
**File Name : queue.c
**MCU Chip :
**FOSC    :
**CCLK    :
**Description :
**Author    :
**Version :
*******************************************************************************/
#include "queue.h"

/*==============================================================================
**                                                                         **
**                      FUNCTION PROTOTYPES                            **
**                                                                         **
==============================================================================*/
__STATIC_INLINE void CopyToNode(Node_Type *pq,ITEM item);
__STATIC_INLINE void CopyToItem(ITEM *pitem,Node_Type *pq);
voidQueueInit(Queue_Type *pq);
BOOLQueueIsFull(const Queue_Type *pq);
BOOLQueueIsEmpty(const Queue_Type *pq);
UINT8 QueueItemCnt(const Queue_Type *pq);
BOOLEnQueue(Queue_Type *pq,ITEM item);
BOOLDeQueue(Queue_Type *pq,ITEM *pitem);
voidEmptyTheQueue(Queue_Type *pq);

/*==============================================================================
**                                                                         **
**                      GLOBAL VARIABLES                                  **
**                                                                         **
==============================================================================*/

/*==============================================================================
**                                                                         **
**                   LOCAL GLOBAL VARIABLES                            **
**                                                                         **
==============================================================================*/

/******************************************************************************
**Function Name : QueueInit
**Input Parameters: none
**Output Parameters : none
**Returned Value : none
**Descrition    : initialize queue
******************************************************************************/
void QueueInit(Queue_Type *pq)
{
pq->pfront = NULL;
pq->prear = NULL;
pq->ucItemCnt = 0;
}
/******************************************************************************
**Function Name : QueueIsFull
**Input Parameters: the queue base pointer
**Output Parameters : none
**Returned Value : 1->full
**                0->not full
**Descrition    : initialize queue
******************************************************************************/
BOOL QueueIsFull(const Queue_Type *pq)
{
return (QUEUE_SIZE == pq->ucItemCnt);
}
/******************************************************************************
**Function Name : QueueIsEmpty
**Input Parameters: the queue base pointer
**Output Parameters : none
**Returned Value : 1 -> empty
**                0 -> not empty
**Descrition    : initialize queue
******************************************************************************/
BOOL QueueIsEmpty(const Queue_Type *pq)
{
return (0 == pq->ucItemCnt);
}
/******************************************************************************
**Function Name : QueueGetItemCnt
**Input Parameters: the queue base pointer
**Output Parameters : none
**Returned Value : 1 -> empty
**                0 -> not empty
**Descrition    : initialize queue
******************************************************************************/
UINT8 QueueItemCnt(const Queue_Type *pq)
{
return (pq->ucItemCnt);
}
/******************************************************************************
**Function Name : CopyToNode
**Input Parameters: Queue_Type *pq -> the queue base pointer
**                ITEM item    -> the value of item
**Output Parameters : none
**Returned Value : none
**Descrition    : initialize queue
******************************************************************************/
__STATIC_INLINE void CopyToNode(Node_Type *pq,ITEM item)
{
pq->item = item;
}
/******************************************************************************
**Function Name : EnQueue
**Input Parameters: Queue_Type *pq -> the queue base pointer
**                ITEM item    -> the value of item
**Output Parameters : none
**Returned Value : 1 -> enqueue successful
**                0 -> enqueue failure
**Descrition    : initialize queue
******************************************************************************/
BOOL EnQueue(Queue_Type *pq,ITEM item)
{
Node_Type *pnew;

if(QueueIsFull(pq))
{
   return FALSE;
}
pnew = (Node_Type *)malloc(sizeof(Node_Type));    //obtain a memory space
if(pnew == NULL)                //obtain a memory space fail ?
{
   return FALSE;
}
CopyToNode(pnew,item);       //copy to node
pnew->pnext = NULL;             //restore pointer
if(QueueIsEmpty(pq))
{
   pq->pfront = pnew;          //the new node is the first one
}
else
{
   pq->prear->pnext = pnew;    //add to the tail
}
pq->prear = pnew;             //the new node is the last one
pq->ucItemCnt++;                //increase the item counter
return TRUE;
}
/******************************************************************************
**Function Name : CopyToNode
**Input Parameters: Queue_Type *pq -> the queue base pointer
**                ITEM item    -> the value of item
**Output Parameters : none
**Returned Value : none
**Descrition    : initialize queue
******************************************************************************/
__STATIC_INLINE void CopyToItem(ITEM *pitem,Node_Type *pq)
{
*pitem = pq->item;
}
/******************************************************************************
**Function Name : DeQueue
**Input Parameters: Queue_Type *pq -> the queue base pointer
**                ITEM item    -> the value of item
**Output Parameters : none
**Returned Value : 1 -> dequeue successful
**                0 -> dequeue failure
**Descrition    : initialize queue
******************************************************************************/
BOOL DeQueue(Queue_Type *pq,ITEM *pitem)
{
Node_Type *pt;

if(QueueIsEmpty(pq))          //the queue is empty ?
{
   return FALSE;
}
CopyToItem(pitem,pq->pfront); //copy the node to item
pt = pq->pfront;                //get the basic point of the first node
pq->pfront = pq->pfront->pnext; //now the next node is the first node
free(pt);                      //free the space
pq->ucItemCnt--;
if(0 == pq->ucItemCnt)          //the queue is empty?
{
   pq->prear = NULL;
}
return TRUE;
}
/******************************************************************************
**Function Name : EmptyTheQueue
**Input Parameters: Queue_Type *pq -> the queue base pointer
**                ITEM item    -> the value of item
**Output Parameters : none
**Returned Value : 1 -> dequeue successful
**                0 -> dequeue failure
**Descrition    : initialize queue
******************************************************************************/
void EmptyTheQueue(Queue_Type *pq)
{
ITEM dummy;
while(!(QueueIsEmpty(pq)))
{
   DeQueue(pq,&dummy);
}
}

#ifndef _queue_h
#define _queue_h

#include "type.h"
#include "string.h"
#include "stdlib.h"
/*==============================================================================
**                                                                         **
**                      IO DEFINITION                                  **
**                                                                         **
==============================================================================*/

/*==============================================================================
**                                                                         **
**                      CONSTANT DEFINITION                            **
**                                                                         **
==============================================================================*/
#define QUEUE_SIZE 10

/*==============================================================================
**                                                                         **
**                      TYPEDEF DEFINITION                            **
**                                                                         **
==============================================================================*/
typedef unsigned char ITEM ;
typedef struct node{
ITEM    item;
struct node *pnext;
}Node_Type;

typedef struct queue{
Node_Type *pfront; //指向队列首的指针
Node_Type *prear;    //指向队列尾的指针
UINT8 ucItemCnt; //队列中项目的个数
}Queue_Type;

/*==============================================================================
**                                                                         **
**                      FUNCTION PROTOTYPES                            **
**                                                                         **
==============================================================================*/
voidQueueInit(Queue_Type *pq);
BOOLQueueIsFull(const Queue_Type *pq);
BOOLQueueIsEmpty(const Queue_Type *pq);
UINT8 QueueItemCnt(const Queue_Type *pq);
BOOLEnQueue(Queue_Type *pq,ITEM item);
BOOLDeQueue(Queue_Type *pq,ITEM *pitem);
voidEmptyTheQueue(Queue_Type *pq);

#endif

墨非发表于 2013-5-16 09:25:15

MASK，收藏了，慢慢看

IT农民工 发表于 2013-5-16 10:03:00

{:lol:}有时间再静下心来看看

ilovemysel 发表于 2013-5-24 18:10:08

静下心,以后看。

515135896 发表于 2013-5-26 08:47:31

beautiful！！！！

yujietangying 发表于 2013-7-31 17:42:10

mark!!!!{:smile:}{:smile:}

Excellence 发表于 2013-8-2 17:29:59

MARK.

xiefy21 发表于 2013-8-12 14:54:22

mark……
顶一个…

JeffreyARM 发表于 2013-8-30 19:57:10

mark..........

rejoice818 发表于 2013-8-31 14:11:13

这两本书有讲，代码用这种任务时调用，效率挺高的
http://smartmcu.com/uploads/ckeditor/pictures/6/content_cf8ac091d9bcb9330a5cb7f200195690.jpg
http://smartmcu.com/uploads/ckeditor/pictures/5/content_2ec4e6e6768520addbac4e089e2bce5d.jpg

追寻cheney 发表于 2013-9-21 13:21:40

mark！！！{:smile:}

Rain0805 发表于 2013-11-14 14:56:58

好样的...........

Constance 发表于 2013-11-14 15:25:06

学习~~~~

dragonbbc 发表于 2013-11-14 15:28:41

代码风格不错，学习了

lihui_mc 发表于 2014-2-25 06:22:51

mask, 谢谢分享

lrzxc 发表于 2014-2-25 06:53:21

代码看着不错，谢谢了

DevLabs 发表于 2014-2-25 07:37:51

Linux下的KFIFO. 限制是缓存区大小必须为2的整数次幂.
在Linux内核中, 程序会将用户输入的缓存区自动圆整到2的整数次幂.

/**
******************************************************************************
* @file kfifo.c
* @authorDevLabs
* @version V0.1
* @date 2013-12-30 20:44
* @brief
******************************************************************************
* @attention
*
* <br />Copyright 2013
* <br />http://www.DevLabs.cn
*
* <h2><center>© COPYRIGHT 2013 DevLabs </center></h2>
******************************************************************************
*/

/* Includes ------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* Private typedef -----------------------------------------------------------*/
typedef struct
{
uint8_t *buffer;    //!< 缓存区指针
uint32_t size;       //!< 缓存区大小
uint32_t in;          //!< 写偏移(in % size)
uint32_t out;       //!< 读偏移(out % size)
} KFIFO;

/* Private define ------------------------------------------------------------*/
#ifndef BOOL
#define BOOL unsigned int
#endif

#ifndef FALSE
#define FALSE (0)
#endif

#ifndef TRUE
#define TRUE (!FALSE)
#endif

#define FIFO_BUF_SIZE 32

/* Private macro -------------------------------------------------------------*/
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) < (b) ? (b) : (a))

/* Private variables ---------------------------------------------------------*/
/* Private function prototypes -----------------------------------------------*/
/* Private functions ---------------------------------------------------------*/

/**
* @brief判断一个数是否为2的整数次幂
*
* @paramn 要判断的数
*
* @retval TRUE
* @retval FALSE
*/
BOOL is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}

/**
* @brieffifo初始化
*
* @paramfifo 要初始化的fifo
* @parambuffer fifo的缓冲区
* @paramsizefifo缓冲大小
*
* @retval TRUE 初始化成功
* @retval FALSE 初始化失败
*/
BOOL kfifo_init(KFIFO *fifo, uint8_t *buffer, uint32_t size)
{
if (!is_power_of_2(size))
{
   printf("file: %s, line: %d size must be power of 2!", __FILE__, __LINE__);

   return FALSE;
}

fifo->buffer = buffer;
fifo->size = size;
fifo->in = fifo->out = 0;

return TRUE;
}

/**
* @brief向FIFO写入数据
*
* @paramfifo 待写入的FIFO
* @parambuffer 待写入的数据
* @paramlen 待写入的数据长度
*
* @return 实际写入的数据
*/
uint16_t kfifo_put(KFIFO *fifo, uint8_t *buffer, uint32_t len)
{
uint32_t l;

len = MIN(len, fifo->size - (fifo->in - fifo->out));
l = MIN(len, fifo->size - (fifo->in & (fifo->size - 1)));

memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
memcpy(fifo->buffer, buffer + l, len - l);

fifo->in += len;

return len;
}

/**
* @brief从FIFO取出数据
*
* @paramfifo 要取出数据的FIFO
* @parambuffer 存储取出数据的缓存
* @paramlen 要取出数据的长度
*
* @return 实际取出的数据长度
*/
uint16_t kfifo_get(KFIFO *fifo, uint8_t *buffer, uint32_t len)
{
uint32_t l;

len = MIN(len, fifo->in - fifo->out);
l = MIN(len, fifo->size - (fifo->out & (fifo->size - 1)));

memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
memcpy(buffer + l, fifo->buffer, len - l);

fifo->out += len;

return len;
}

/**
* @brief打印缓冲区
*
* @parambuf 缓冲区指针
* @paramlen 要打印的数据长度
*/
void put_buf(const uint8_t *buf, uint32_t len)
{
while (len != 0)
{
   putchar(*buf);
   len--;
   buf++;
}
printf("\n");

return;
}

int main(void)
{
KFIFO kfifo;
uint32_t i;
uint8_t fifo_buf;
uint8_t get_buf;
uint8_t *str1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
uint8_t *str2 = "abcdefghijklmhopqrstuvwxyz";

for (i = 0; i < FIFO_BUF_SIZE; i++)
{
   fifo_buf = '*';
}

for (i = 0; i < FIFO_BUF_SIZE; i++)
{
   get_buf = '#';
}

// FIFO初始化
kfifo_init(&kfifo, fifo_buf, FIFO_BUF_SIZE);
// 向FIFO写入26个数据
kfifo_put(&kfifo, str1, strlen(str1));

printf("fifo_buf: ");
put_buf((const uint8_t *)&fifo_buf, FIFO_BUF_SIZE);

// 取出10个数据
kfifo_get(&kfifo, get_buf, 10);

printf(" get_buf: ");
put_buf((const uint8_t *)&get_buf, FIFO_BUF_SIZE);

// 这次写入会使FIFO回绕
kfifo_put(&kfifo, str2, strlen(str2));

printf("fifo_buf: ");
put_buf((const uint8_t *)&fifo_buf, FIFO_BUF_SIZE);

return 0;
}

/******************* (C) COPYRIGHT 2013 DevLabs **********END OF FILE**********/

xyz2008 发表于 2014-2-25 08:44:51

这种代码风格，看着很舒服！

MINI2440 发表于 2014-2-25 08:49:01

MARK以后也许会用上。

ijlc1314 发表于 2014-2-25 09:08:52

标记一下，需要学习

wolyond 发表于 2014-2-25 09:51:13

mark一下，日后再看！

棋间卒 发表于 2014-2-25 10:26:34

收藏，看着很清晰

pldjn 发表于 2016-4-1 10:25:20

DevLabs 发表于 2014-2-25 07:37
Linux下的KFIFO. 限制是缓存区大小必须为2的整数次幂.
在Linux内核中, 程序会将用户输入的缓存区自动圆整到 ...

还是Linux的代码看着舒服

qq78929709 发表于 2016-4-1 10:26:46

感谢分享

leon...... 发表于 2016-4-1 10:29:34

mask 一下，有空再来细品

一杯茶2009 发表于 2016-4-22 14:02:28

收藏，静心细看

qianshan 发表于 2016-4-22 14:05:45

楼主厉害！

ALUMEI 发表于 2016-4-22 15:38:27

看风格有点像傻孩子的啊？是不？

ALUMEI 发表于 2016-4-22 15:45:50

Kfifo 的代码简单明了。我想用c++实现，KFIFO 这结构体里边的buffer 对应不同的类型，比如char intstruct 等等。请高人指导下！

flamma 发表于 2016-4-22 17:57:56

第一种就是普通的双向链表吧，Kfifo是效率比较高的FIFO实现，这种实现方法还有用于ringbuff的，特点就是判断首尾指针是否碰到非常快捷。而且这种方式用在两个线程一个读一个写的环境中，可以不用加任何锁或者同步。

一匹狼 发表于 2016-7-6 20:52:17

mark

warrenyan7251 发表于 2016-7-12 08:53:19

收藏了，学习下

guyong2012 发表于 2016-11-3 17:32:42

MASK，收藏了，慢慢看

晚枫发表于 2016-12-1 13:58:46

粗略看了一下，没看懂。先MARK一下，有空慢慢看。

cdtlzhou 发表于 2016-12-1 17:04:43

先MARK一下，有空慢慢看

xin 发表于 2016-12-2 17:34:08

MARK，谢谢分享

XUEPENGBIN 发表于 2017-7-21 07:32:03

最近有用收藏慢慢看

20zjie 发表于 2018-5-26 16:59:04

mark 谢谢楼主分享！

let8011 发表于 2018-5-27 14:39:25

MASK，收藏了，慢慢看

chendy6868 发表于 2023-1-8 15:59:23

mark, 最近有用

页: [1]

amobbs.com 阿莫电子技术论坛's Archiver

一个不错的队列代码，发给大家看看