本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 & V! m0 K) h- _$ ]/ }9 ` 队列的概念: ], A' W8 g0 o' j' }* o( P. ^; X 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。/ w. R x( n( |1 p% f5 P% { 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 6 B2 N7 `: S( |! A( u& t队列的常见两种形式 8 K2 e2 Z, M4 j# m 普通队列3 Z) N# Z- [, A& A/ u: V , c4 I5 b5 h/ J. ~; {/ ? 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。$ O; Q, V$ t9 @% P 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。4 u( N+ R+ R9 L 环形队列 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 - Q/ H! ~) @0 E' m, b/ A 队列头 (Head) :允许进行删除的一端称为队首。 队列尾 (Tail) :允许进行插入的一端称为队尾。 ) V4 @. I( O' Q' v2 X* M 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。) _ r3 \! l. a$ h4 y3 }3 S& N/ h5 Y 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 9 p4 }$ h* l) v- ~5 E 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现% D% h D( G4 q6 w串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。5 X0 ^8 ^) ^$ C- J! b 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:0 K) v/ ?7 L/ A7 F& p/ n( J ①定义一个结构体: 1typedef struct 2{ 3 u16 Head; & `+ \* K/ P9 O+ e0 M1 k+ q/ B: A 4 u16 Tail;) Z4 L% ^9 B( I& u6 @ 5 u16 Lenght;4 z) h6 V5 x$ b, n6 V& r 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t;, X, x2 Y7 V- x' Y, f 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区( O; j# I7 S9 u. s ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/** 2* @brief RingBuff_Init# n$ L- N8 o7 ?' c 3* @param void 4* @return void# a1 F: A4 }) S 5* @author 杰杰 6* @date 2018: x8 ~4 V: f) j6 |3 g5 j3 x 7* @version v1.0 D9 a: f' D% d% Z* e 8* @note 初始化环形缓冲区3 y( X5 a0 R$ M3 T% x+ W 9*/ 10void RingBuff_Init(void)( X) t6 p$ a& z; i) d2 D! V 11{ 12 //初始化相关信息+ g! \0 Q, k. f6 { 13 ringBuff.Head = 0;- Q' w/ G+ r( V5 E* ` 14 ringBuff.Tail = 0;1 q0 l& m0 V: a$ N) b: T6 q6 N0 s 15 ringBuff.Lenght = 0;# d3 d, \- V: ^+ G8 ?( u 16} 初始化效果如下: % u& ]7 t# }# M7 \$ \9 `( T 写入环形缓冲区的代码实现: 1/**2 _+ S2 f. Y) T: \( Z. l5 M 2* @brief Write_RingBuff0 X0 D% k1 D9 b& H' H% P 3* @param u8 data 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰1 u- v9 i5 ]' E; R& M$ Z& R 6* @date 2018 7* @version v1.0% W' T/ U! d5 V+ W0 j( @; m 8* @note 往环形缓冲区写入u8类型的数据 9*/: [1 _6 R6 D9 A" W6 U# | 10u8 Write_RingBuff(u8 data) 11{' f: p: Q1 q C% s5 I$ r 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满 13 {; Z. G7 E; Z+ @8 ^ 14 return FLASE; 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght++; 20 return TRUE; 21}- g: \+ {% E+ a! r: X 读取缓冲区的数据的代码实现: 1/**! ?; F7 r- K$ c; D7 U& p' y9 d# { 2* @brief Read_RingBuff, S$ C# R4 l* @ 3* @param u8 *rData,用于保存读取的数据 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功& u2 H* y; U! o3 @5 F% D- Q 5* @author 杰杰+ x0 T7 b, Q$ m, r3 W% W. N 6* @date 2018 7* @version v1.04 U* R" ?* p! R8 v 8* @note 从环形缓冲区读取一个u8类型的数据& f/ z+ n3 d e/ c& t 9*// L0 C3 w1 E! B- q% R 10u8 Read_RingBuff(u8 *rData) 11{$ H& ?1 E) v* N+ }3 ~ 12 if(ringBuff.Lenght == 0)//判断非空 13 { 14 return FLASE;! V* o- f8 S( c, h 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++;# d, b6 |$ K$ H$ S9 p% S 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问9 s; r. y6 d F' o) f+ W 19 ringBuff.Lenght--;8 B& ]3 \: Z1 e" p, K5 ?! K 20 return TRUE; 21}对于读写操作需要注意的地方有两个:4 i; P$ S; l2 u9 A 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。 那么在串口接收函数中:* o5 M5 T9 z( ]( l7 d2 j5 [# y 1void USART1_IRQHandler(void) 2{ 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断( t6 q: }: S7 s! a 4 {/ M. {+ K9 ^% f2 _ 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据7 z3 W0 j! G2 c/ H8 b c1 l( p$ E 7 } 8} 测试效果$ F1 e0 v! k q, ] 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。$ o: w# y; d4 \/ w 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据 2#if USER_RINGBUFF; Q7 [" |( d% r7 I& {; C 3/**如果使用环形缓冲形式接收串口数据***/6 ~0 ]- ~" o3 K! @, U 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 5#define FLASE 1 1 ]4 s3 L& T, X* L+ x, P 6#define TRUE 0 . |- \, I5 s/ p( t 7void RingBuff_Init(void);9 G! M" W9 N1 u& w8 n- |! f: q7 [ 8u8 Write_RingBuff(u8 data);# Z ~3 t ~0 s0 g! N 9u8 Read_RingBuff(u8 *rData);; ?' y7 \9 n* z1 I* @. p 10#endif7 ^- _# e: N3 T8 x6 g 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾创客: 创客飞梦空间是开源公众号$ t6 _" f! U6 S3 W% p/ j欢迎大家分享出去, M a7 c2 z; ^0 C 也欢迎大家投稿: v8 V' q2 n0 h* C( v0 z9 ` 0 X0 g( i! C. G$ U2 k7 O* R 0 S n' S4 O1 n0 H2 I3 _5 g, Z |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
( U' L" D6 m! Q; }8 l
2 u4 Z6 K8 ^1 b! _% Q
% j& A1 \% h0 b' @, ^( Z
: g$ i6 M7 F5 d% f
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)% X# g! M5 p" g, P
{
fifo->in = 0;
fifo->out = 0;
fifo->mask = 0;
fifo->data = buffer;
& c; V! ~ r0 B/ R ]- |
if (size < 2) {* ]5 S3 B$ m8 P! v7 I% a/ A
return -1;
}
' [+ Y# p% @5 f4 g2 _( V
if ((size & (size-1)) != 0)7 F! L/ L1 V! h3 }1 @( |$ k4 t2 y- [2 i
{' D) `1 I7 n' H# E8 f5 e
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/
}) [9 S5 ?, b0 ]& C
fifo->mask = size - 1;
& ^6 T) ] ~- r, ^5 }
return 0;
}
8 {5 Q7 h. h1 V
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)% N/ F8 l! y. z9 U1 s
{4 K$ {( X" C0 S- J- P F
/ X' L t. u5 K& x/ p
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{/ p& i- X7 D5 T% I
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;$ \1 s8 X: U6 t4 F5 v% Z: C
) C7 K* e# B& @
return 1;7 R+ l! t- z' N& Q/ K7 ~
}% \4 h8 ^: }$ R4 t
return 0;
}
! O3 B: P$ @1 U
- Q* l# K# _( n- H1 r6 l* w0 G
8 m+ |2 T8 {9 Z
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )
{
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;5 q) p7 N( t& v B7 Z
return 1;5 I+ b9 A) o& x; o1 m* c1 j# P. [
}
return 0;
}1 U+ h6 Z# A' ~; n5 H% [
z% x5 J7 B3 e+ Q* W: c: N' d
_& K7 ]" ^7 W
; g& v: K6 s$ _9 m
ok, 了解了解
=========================================
看了源代码,
5 J4 u) Q+ K# [7 X# o6 f9 ]+ D
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.' Q# ?7 E0 D I/ H R X
$ M. R1 P6 G. ^( C' O
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。! [8 Y Z! B/ t, x& z( P
一个暑假自学完一本数据结构课本,做完一本题库。
, q- t: S: {! G2 R( M R; s8 q+ N
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!