amobbs.com 阿莫电子技术论坛
标题:
一个不错的队列代码,发给大家看看
[打印本页]
作者:
cyj_0220
时间:
2013-5-15 21:50
标题:
一个不错的队列代码,发给大家看看
本帖最后由 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);
void QueueInit(Queue_Type *pq);
BOOL QueueIsFull(const Queue_Type *pq);
BOOL QueueIsEmpty(const Queue_Type *pq);
UINT8 QueueItemCnt(const Queue_Type *pq);
BOOL EnQueue(Queue_Type *pq,ITEM item);
BOOL DeQueue(Queue_Type *pq,ITEM *pitem);
void EmptyTheQueue(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 **
** **
==============================================================================*/
void QueueInit(Queue_Type *pq);
BOOL QueueIsFull(const Queue_Type *pq);
BOOL QueueIsEmpty(const Queue_Type *pq);
UINT8 QueueItemCnt(const Queue_Type *pq);
BOOL EnQueue(Queue_Type *pq,ITEM item);
BOOL DeQueue(Queue_Type *pq,ITEM *pitem);
void EmptyTheQueue(Queue_Type *pq);
#endif
复制代码
作者:
墨非
时间:
2013-5-16 09:25
MASK,收藏了,慢慢看
作者:
IT农民工
时间:
2013-5-16 10:03
有时间再静下心来看看
作者:
ilovemysel
时间:
2013-5-24 18:10
静下心,以后看。
作者:
515135896
时间:
2013-5-26 08:47
beautiful!!!!
作者:
yujietangying
时间:
2013-7-31 17:42
mark!!!!
作者:
Excellence
时间:
2013-8-2 17:29
MARK.
作者:
xiefy21
时间:
2013-8-12 14:54
mark……
顶一个…
作者:
JeffreyARM
时间:
2013-8-30 19:57
mark..........
作者:
rejoice818
时间:
2013-8-31 14:11
这两本书有讲,代码用这种任务时调用,效率挺高的
作者:
追寻cheney
时间:
2013-9-21 13:21
mark!!!
作者:
Rain0805
时间:
2013-11-14 14:56
好样的...........
作者:
Constance
时间:
2013-11-14 15:25
学习~~~~
作者:
dragonbbc
时间:
2013-11-14 15:28
代码风格不错,学习了
作者:
lihui_mc
时间:
2014-2-25 06:22
mask, 谢谢分享
作者:
lrzxc
时间:
2014-2-25 06:53
代码看着不错,谢谢了
作者:
DevLabs
时间:
2014-2-25 07:37
Linux下的KFIFO. 限制是缓存区大小必须为2的整数次幂.
在Linux内核中, 程序会将用户输入的缓存区自动圆整到2的整数次幂.
/**
******************************************************************************
* @file kfifo.c
* @author DevLabs
* @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的整数次幂
*
* @param n 要判断的数
*
* @retval TRUE
* @retval FALSE
*/
BOOL is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
/**
* @brief fifo初始化
*
* @param fifo 要初始化的fifo
* @param buffer fifo的缓冲区
* @param size fifo缓冲大小
*
* @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写入数据
*
* @param fifo 待写入的FIFO
* @param buffer 待写入的数据
* @param len 待写入的数据长度
*
* @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取出数据
*
* @param fifo 要取出数据的FIFO
* @param buffer 存储取出数据的缓存
* @param len 要取出数据的长度
*
* @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 打印缓冲区
*
* @param buf 缓冲区指针
* @param len 要打印的数据长度
*/
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[FIFO_BUF_SIZE];
uint8_t get_buf[FIFO_BUF_SIZE];
uint8_t *str1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
uint8_t *str2 = "abcdefghijklmhopqrstuvwxyz";
for (i = 0; i < FIFO_BUF_SIZE; i++)
{
fifo_buf[i] = '*';
}
for (i = 0; i < FIFO_BUF_SIZE; i++)
{
get_buf[i] = '#';
}
// 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
这种代码风格,看着很舒服!
作者:
MINI2440
时间:
2014-2-25 08:49
MARK 以后也许会用上。
作者:
ijlc1314
时间:
2014-2-25 09:08
标记一下,需要学习
作者:
wolyond
时间:
2014-2-25 09:51
mark一下,日后再看!
作者:
棋间卒
时间:
2014-2-25 10:26
收藏,看着很清晰
作者:
pldjn
时间:
2016-4-1 10:25
DevLabs 发表于 2014-2-25 07:37
Linux下的KFIFO. 限制是缓存区大小必须为2的整数次幂.
在Linux内核中, 程序会将用户输入的缓存区自动圆整到 ...
还是Linux的代码 看着舒服
作者:
qq78929709
时间:
2016-4-1 10:26
感谢分享
作者:
leon......
时间:
2016-4-1 10:29
mask 一下,有空再来细品
作者:
一杯茶2009
时间:
2016-4-22 14:02
收藏,静心细看
作者:
qianshan
时间:
2016-4-22 14:05
楼主厉害!
作者:
ALUMEI
时间:
2016-4-22 15:38
看风格有点像傻孩子的啊?是不?
作者:
ALUMEI
时间:
2016-4-22 15:45
Kfifo 的代码简单明了。我想用c++实现,KFIFO 这结构体里边的buffer 对应不同的类型,比如char int struct 等等。请高人指导下!
作者:
flamma
时间:
2016-4-22 17:57
第一种就是普通的双向链表吧,Kfifo是效率比较高的FIFO实现,这种实现方法还有用于ringbuff的,特点就是判断首尾指针是否碰到非常快捷。而且这种方式用在两个线程一个读一个写的环境中,可以不用加任何锁或者同步。
作者:
一匹狼
时间:
2016-7-6 20:52
mark
作者:
warrenyan7251
时间:
2016-7-12 08:53
收藏了,学习下
作者:
guyong2012
时间:
2016-11-3 17:32
MASK,收藏了,慢慢看
作者:
晚枫
时间:
2016-12-1 13:58
粗略看了一下,没看懂。先MARK一下,有空慢慢看。
作者:
cdtlzhou
时间:
2016-12-1 17:04
先MARK一下,有空慢慢看
作者:
xin
时间:
2016-12-2 17:34
MARK,谢谢分享
作者:
XUEPENGBIN
时间:
2017-7-21 07:32
最近有用 收藏慢慢看
作者:
20zjie
时间:
2018-5-26 16:59
mark 谢谢楼主分享!
作者:
let8011
时间:
2018-5-27 14:39
MASK,收藏了,慢慢看
作者:
chendy6868
时间:
2023-1-8 15:59
mark, 最近有用
欢迎光临 amobbs.com 阿莫电子技术论坛 (https://www.amobbs.com/)
Powered by Discuz! X3.4