本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 e' \# L7 P4 Y: Y; R9 s 队列的概念 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。7 v# {. Y, s7 c# n8 q# ~# h; f 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式 普通队列! r& \" [" [/ i 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。$ f, `) L2 ~4 m 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。) H8 {0 g' m: c8 Y0 V8 ^* V) F 环形队列9 K- s2 L. ~3 k+ d6 _* T, b 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 * L+ Y: s1 y1 V# S t& |. I. l. Z 队列头 (Head) :允许进行删除的一端称为队首。, x- v; g$ w$ I, O 队列尾 (Tail) :允许进行插入的一端称为队尾。 , A! j* g& \* `$ T7 \' U ~& n 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。( R/ A+ U5 @$ U) {, |7 I0 \1 c& n& N 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 . m$ g8 v+ @9 |2 N) {, C 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现5 o$ v1 _2 C* y: I E串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。 * l+ E4 X6 t! q! ~9 P% W ) H, E$ R! i S) K |; L 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:) l2 n6 t) f5 k8 n+ O! x/ j & V' }" w) f' {8 X1 ~. I ①定义一个结构体: 1typedef struct 2{7 l7 N3 y9 J! }, F 3 u16 Head; % t5 s4 T$ j' b 4 u16 Tail;3 \1 n; w1 e) n( F7 |) N x$ E+ |8 q 5 u16 Lenght; 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t;3 H& S; U& n; n/ \- r 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区' n# S; {0 `4 l' n) e' R# ] ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。% G/ h5 p. O; m7 d4 N 1/** 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author 杰杰 6* @date 2018 7* @version v1.0 8* @note 初始化环形缓冲区5 G" h! t/ P/ I3 e' o! U 9*/6 p9 i* c! u' W! s0 N5 U 10void RingBuff_Init(void) 11{ 12 //初始化相关信息8 E1 H& r/ y) _ Y; P; @ 13 ringBuff.Head = 0;4 D0 B. z8 _2 j 14 ringBuff.Tail = 0;. r) u5 g+ H$ l; q7 A) E2 \! ^0 o: ]/ n 15 ringBuff.Lenght = 0;7 A: Y: {4 f% c, f, G3 h: M 16}" [6 }8 S3 T+ b& k0 U1 d 初始化效果如下:* I- _& R- s2 f 写入环形缓冲区的代码实现: 1/** q' c. c; [( i& W# L2 g1 ~ 2* @brief Write_RingBuff 3* @param u8 data 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰 6* @date 2018. B! e" v& L0 W& N+ i& b! r 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据( C) W! W4 u+ l1 S. s! t* _, ? 9*/5 O8 q) Z; {/ }5 m6 y9 F5 K& G 10u8 Write_RingBuff(u8 data) 11{ t" I7 O9 Y( H- p- u 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满! k2 H# F0 H2 k+ Q% L+ G8 U( X1 t8 ` 13 {7 B0 A) S. a6 W4 y 14 return FLASE; 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++;4 @* [5 ?7 F# s" k1 E8 ^7 Z 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght++; 20 return TRUE; 21}' w) l- [8 C1 f1 q( U2 n+ F! I 读取缓冲区的数据的代码实现: 1/**9 P- ], }% ^1 b- K8 L, M9 W. _) U 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据& Y F, z( w: @9 [/ q# Q 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰' k8 @3 y5 S: l3 k& @, b 6* @date 2018 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/# w6 f2 z7 D& f: k 10u8 Read_RingBuff(u8 *rData)9 ?9 I& @$ j* S1 w 11{ 12 if(ringBuff.Lenght == 0)//判断非空 L9 i3 L9 V" C2 J/ V 13 { 14 return FLASE; 15 }+ K8 j+ A5 F8 J3 O9 y9 i 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出% q6 k! e, B# W- Z" V 17// ringBuff.Head++;+ l6 {( V& y. F3 y) C+ w/ E: Y 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问7 \3 s4 v, \) M# @/ X! k; L 19 ringBuff.Lenght--;; k' Z) Y. S: \+ C5 g 20 return TRUE; 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。: @6 e* o3 S7 }$ X/ B 那么在串口接收函数中: 1void USART1_IRQHandler(void) , N# j2 D4 V2 s; y, a2 k/ a 2{1 M' ]# k) V9 ]* G* q 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断. \3 S. E8 Y, l4 n0 | 4 { 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据0 d9 Q2 ^1 }! ?- ~4 t, R 7 } 8} 测试效果" c y \) A ` 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据$ J& ^- X1 F2 l. a0 F* c; K% f' _ 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/# w" d6 y6 ^4 Q2 S) M t 4#define RINGBUFF_LEN 200 //定义最大接收字节数 2009 s7 V$ w' J# G( \- j$ h 5#define FLASE 1 1 f0 J6 v8 r) `( i 6#define TRUE 0 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData);8 ^6 @3 D% b; Z8 Y6 Q 10#endif 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。* v0 Q7 r' E' T4 [+ j# n8 Z 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS" i% }) e9 W P; p' | 创客: 创客飞梦空间是开源公众号6 U0 J* S- n% H7 b3 i& C1 H2 Q欢迎大家分享出去9 t) E4 S' Q: D; ]6 | 也欢迎大家投稿 |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
. q+ Z' V& o$ r! w5 C
$ n. y" g% L" y1 D1 r/ C
: \; o' _5 z( m* |
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)
{
fifo->in = 0;8 t1 | d; J8 R" ^& s2 X
fifo->out = 0;1 ?) Z9 |- P4 j$ n- [
fifo->mask = 0;
fifo->data = buffer;0 ^$ T- K3 Y2 B; s& M- m
7 q" P$ d1 ~! }9 A. d+ r
if (size < 2) {: ?7 [3 z5 ~- |3 K2 O- \
return -1;2 n$ |8 A6 n) g9 ]/ a/ D
}
if ((size & (size-1)) != 0)
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/
}
fifo->mask = size - 1;
" B4 `& p, K) M, @2 Q2 r
return 0;
}
, J3 X% ^ m* H
! L/ [% r% a3 d- s B1 |: _/ n) _" ~! ]
; ?- u8 G) t! t+ _- `" U1 e, r
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p). E+ k5 ]# q' d+ E& }
{! k8 z2 v- M! S, s
' d7 p; P, o9 P$ p2 i: H
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{) ` p$ Q; h6 ]) [1 e4 C! X
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;1 B! d7 ^# \) V1 ~) _1 @; Z
7 ^/ {2 A: F4 z4 k v7 O6 |
return 1;4 n+ P5 M* C! b7 V- z0 u0 U) F3 V
}5 w0 m( W$ ^. e1 [# a& ~
return 0;! U- R: j7 b9 R% |6 \
}! y4 ^ Z8 g( ~4 P7 I/ V$ {+ M
+ @. e5 ^4 P& o O! ?
7 P$ W; w$ u! R1 L# m+ O' K
z. M$ I. o2 D/ V& }
3 A9 N$ U: |( x0 o5 M5 g- V
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )) `- k. o# A/ I/ h! O
{5 _) i) r ^1 p" }! I, t- Z
if( fifo->in != fifo->out )
{" I) m5 R! K4 P6 R$ e" l
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;5 s$ N# t* L6 H3 J
V+ Q& I1 z% D
return 1;
}
return 0;
}
, I' T; f2 B8 y# l% N, B
8 S0 c# Q4 ~. Q3 Y7 k# f* q0 {
ok, 了解了解
=========================================! I- S% L0 e; k: z/ H: Q& j7 l
看了源代码, 4 Q1 k0 R7 l1 N- X" s
0 T) |0 a1 Z% `0 b' E/ D! k/ ?
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.
7 q3 K2 s- s! y& N' U1 Q
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。+ Y l* C/ _/ p. c7 w6 x& q
一个暑假自学完一本数据结构课本,做完一本题库。# H- w- m% r7 i( F9 S
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
3 i, J8 J$ P# t4 R; n2 B; R
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!