TencentOS-tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)
1. 什么是隊(duì)列隊(duì)列（queue）是一種只能在一端插入元素、在另一端刪除元素的數(shù)據(jù)結(jié)構(gòu)，遵循「先入先出」（FIFO）的規(guī)則。
隊(duì)列中有兩個基本概念：
隊(duì)頭指針（可變）：永遠(yuǎn)指向此隊(duì)列的第一個數(shù)據(jù)元素；
隊(duì)尾指針（可變）：永遠(yuǎn)指向此隊(duì)列的最后一個數(shù)據(jù)元素；
隊(duì)列中的數(shù)據(jù)存儲方式有兩種：
① 基于靜態(tài)連續(xù)內(nèi)存（數(shù)組）存儲，如圖：② 基于動態(tài)內(nèi)存（鏈表節(jié)點(diǎn)）存儲，如圖：
?
后續(xù)都使用基于靜態(tài)內(nèi)存存儲的隊(duì)列講解。
?隊(duì)列提供兩個統(tǒng)一的操作：
「入隊(duì)（enqueue）」
入隊(duì)將一個元素添加到隊(duì)尾，并將隊(duì)尾指針+1后移，如圖：
「出隊(duì)（dequeue）」
出隊(duì)將從隊(duì)頭中取出一個元素，并將隊(duì)頭指針+1后移，如圖：
2. 環(huán)形隊(duì)列2.1. 環(huán)形隊(duì)列的特點(diǎn)
普通隊(duì)列的入隊(duì)操作將隊(duì)尾指針后移+1，出隊(duì)操作將隊(duì)頭指針后移+1，操作幾次之后會發(fā)現(xiàn)隊(duì)頭指針和隊(duì)尾指針都跑到緩沖區(qū)的尾部去了：這就導(dǎo)致了前面的內(nèi)存空間全被浪費(fèi)，如果要重新恢復(fù)使用，則需要進(jìn)行元素和指針的移動：顯然這種隊(duì)列使用方式太不方便了，所以就誕生了環(huán)形隊(duì)列：「不用搬移元素和指針，一直可以重復(fù)利用這段內(nèi)存空間」。
2.2. 環(huán)形隊(duì)列的實(shí)現(xiàn)
TencentOS-tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)在tos_ring_queue.h和tos_ring_queue.c中。
typedef struct k_ring_queue_st {
knl_obj_t knl_obj;
uint16_t head; //隊(duì)頭指針
uint16_t tail; //隊(duì)尾指針
size_t total; //記錄隊(duì)列中元素的個數(shù)
uint8_t *pool; //隊(duì)列底層的存儲結(jié)構(gòu)（一個數(shù)組）
size_t item_size; //隊(duì)列中每個元素的大小，單位：字節(jié)
size_t item_cnt; //隊(duì)列中可以容納的元素?cái)?shù)量
} k_ring_q_t;
環(huán)形隊(duì)列初始化，將隊(duì)頭指針和隊(duì)尾置0：
__API__ k_err_t tos_ring_q_create（k_ring_q_t *ring_q， void *pool， size_t item_cnt， size_t item_size）
{
//省略了參數(shù)合法性檢查代碼
ring_q-》head = 0u;
ring_q-》tail = 0u;
ring_q-》total = 0;
ring_q-》pool = （uint8_t *）pool;
ring_q-》item_size = item_size;
ring_q-》item_cnt = item_cnt;
return K_ERR_NONE;
}
判斷環(huán)形隊(duì)列是否為滿或者為空：
__API__ int tos_ring_q_is_empty（k_ring_q_t *ring_q）
{
TOS_CPU_CPSR_ALLOC（）;
int is_empty = K_FALSE;
//省略了參數(shù)合法性檢查代碼
TOS_CPU_INT_DISABLE（）;
is_empty = （ring_q-》total == 0 ？ K_TRUE ： K_FALSE）;
TOS_CPU_INT_ENABLE（）;
return is_empty;
}
__API__ int tos_ring_q_is_full（k_ring_q_t *ring_q）
{
TOS_CPU_CPSR_ALLOC（）;
int is_full = K_FALSE;
//省略了參數(shù)合法性檢查代碼
TOS_CPU_INT_DISABLE（）;
is_full = （ring_q-》total == ring_q-》item_cnt ？ K_TRUE ： K_FALSE）;
TOS_CPU_INT_ENABLE（）;
return is_full;
}
環(huán)形隊(duì)列入隊(duì)操作的API如下：
__API__ k_err_t tos_ring_q_enqueue（k_ring_q_t *ring_q， void *item， size_t item_size）;
在此API中，入隊(duì)操作的實(shí)現(xiàn)如下：
__STATIC_INLINE__ void ring_q_item_increase（k_ring_q_t *ring_q）
{
ring_q-》tail = RING_NEXT（ring_q， ring_q-》tail）;
++ring_q-》total;
}
環(huán)形隊(duì)列出隊(duì)操作的API如下：
__API__ k_err_t tos_ring_q_dequeue（k_ring_q_t *ring_q， void *item， size_t *item_size）;
在此API中，出隊(duì)操作的實(shí)現(xiàn)如下：
__STATIC_INLINE__ void ring_q_item_decrease（k_ring_q_t *ring_q）
{
ring_q-》head = RING_NEXT（ring_q， ring_q-》head）;
--ring_q-》total;
}
在入隊(duì)和出隊(duì)操作的時候都使用了 RING_NEXT 宏，用來獲取在環(huán)形隊(duì)列中的下一個位置：
#define RING_NEXT（ring_q， index） （（index + 1） % ring_q-》item_cnt）
2.3. 環(huán)形隊(duì)列使用Demo
編寫如下的測試代碼：
#include 《tos_k.h》typedef struct item_st {
int a;
int b;
int c;
} item_t;
#define RING_QUEUE_ITEM_MAX 5uint8_t ring_q_buffer［RING_QUEUE_ITEM_MAX * sizeof（item_t）］;
k_ring_q_t ring_q;
void entry_task_demo（void *arg）
{
k_err_t err;
int i;
item_t item;
size_t item_size;
//創(chuàng)建環(huán)形隊(duì)列
tos_ring_q_create（&ring_q， ring_q_buffer， RING_QUEUE_ITEM_MAX， sizeof（item_t））;
//數(shù)據(jù)入隊(duì)
for（i = 0;i 《 RING_QUEUE_ITEM_MAX; i++）
{
item.a = i;
item.b = i;
item.c = i;
err = tos_ring_q_enqueue（&ring_q， &item， sizeof（item_t））;
if（err == K_ERR_NONE）
{
printf（“enqueue a item： %d %d %d
”， item.a， item.b， item.c）;
}
else
{
printf（“ring queue enqueue fail，err = %d
”， err）;
}
}
//隊(duì)列滿之后，繼續(xù)入隊(duì)
err = tos_ring_q_enqueue（&ring_q， &item， sizeof（item_t））;
if（err == K_ERR_RING_Q_FULL）
{
printf（“ring queue is full： %s
”， tos_ring_q_is_full（&ring_q） ？ “TRUE” ： “FALSE”）;
}
else
{
printf（“ring queue enqueue fail，err = %d
”， err）;
}
//數(shù)據(jù)出隊(duì)
for（i = 0; i 《 RING_QUEUE_ITEM_MAX; ++i）
{
err = tos_ring_q_dequeue（&ring_q， &item， &item_size）;
if（err == K_ERR_NONE）
{
printf（“dequeue a item（%d bytes）： %d %d %d
”， item_size， item.a， item.b， item.c）;
}
else
{
printf（“ring queue dequeue fail，err = %d
”， err）;
}
}
//沒有數(shù)據(jù)后繼續(xù)出隊(duì)
err = tos_ring_q_dequeue（&ring_q， &item， &item_size）;
if（err == K_ERR_RING_Q_EMPTY）
{
printf（“ring queue is empty： %s
”， tos_ring_q_is_empty（&ring_q） ？ “TRUE” ： “FALSE”）;
}
else
{
printf（“ring queue dequeue fail，err = %d
”， err）;
}
}
運(yùn)行結(jié)果如下：
3. 優(yōu)先級隊(duì)列3.1. 優(yōu)先級隊(duì)列的特點(diǎn)
優(yōu)先級隊(duì)列也是一種基于隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，但是它「不遵循FIFO」，而是按照每個元素的優(yōu)先級進(jìn)行出隊(duì)：「最高優(yōu)先級的先出隊(duì)」。
3.2. 優(yōu)先級隊(duì)列的實(shí)現(xiàn)
TencentOS-tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)在tos_prio_queue.h和tos_prio_queue.c中。
優(yōu)先級隊(duì)列在數(shù)據(jù)入隊(duì)的時候，會按照入隊(duì)元素的優(yōu)先級進(jìn)行一次排序，「將優(yōu)先級值最?。▋?yōu)先級最高的元素）放在隊(duì)頭」，出隊(duì)的時候只需要取第一個元素即可。
正是因?yàn)檫@種特性，優(yōu)先級隊(duì)列的底層存儲結(jié)構(gòu)不能使用數(shù)組（排序太麻煩），而是使用了二項(xiàng)堆的數(shù)據(jù)結(jié)構(gòu)。
?
二項(xiàng)堆是一種二叉樹集合的數(shù)據(jù)結(jié)構(gòu)，在本文中不再深入講解，有興趣的讀者可以自己搜索閱讀。
?下面只給出優(yōu)先級隊(duì)列的API，「理解其規(guī)則，會用即可」。
創(chuàng)建優(yōu)先級隊(duì)列
__API__ k_err_t tos_prio_q_create（k_prio_q_t *prio_q， void *mgr_array， void *pool， size_t item_cnt， size_t item_size）;
參數(shù)描述
prio_q優(yōu)先級隊(duì)列控制塊指針
mgr_array提供一塊緩沖區(qū)用于內(nèi)部管理
pool隊(duì)列的緩沖區(qū)
item_cnt隊(duì)列可容納的元素?cái)?shù)量
item_size每個元素的大小，單位字節(jié)
其中用于內(nèi)部管理的緩存區(qū)大小可以使用宏定義來計(jì)算，比如有5個元素的管理緩沖區(qū)大?。?/p>
uint8_t mgr_pool［TOS_PRIO_Q_MGR_ARRAY_SIZE（5）］;
元素入隊(duì)
__API__ k_err_t tos_prio_q_enqueue（k_prio_q_t *prio_q， void *item， size_t item_size， k_prio_t prio）;
其中優(yōu)先級的值遵循：數(shù)值越小，優(yōu)先級越高。
元素出隊(duì)
__API__ k_err_t tos_prio_q_dequeue（k_prio_q_t *prio_q， void *item， size_t *item_size， k_prio_t *prio）;
其中prio需要傳入一個地址，用于記錄出隊(duì)元素的優(yōu)先級。
3.3. 優(yōu)先級隊(duì)列使用Demo
#include 《tos_k.h》typedef struct item_st {
int a;
int b;
int c;
} item_t;
#define PRIO_QUEUE_ITEM_MAX 5uint8_t prio_q_buffer［PRIO_QUEUE_ITEM_MAX * sizeof（item_t）］;
uint8_t mgr_pool［TOS_PRIO_Q_MGR_ARRAY_SIZE（PRIO_QUEUE_ITEM_MAX）］;
k_prio_q_t prio_q;
void entry_task_demo（void *arg）
{
k_err_t err;
int i;
item_t item;
size_t item_size;
k_prio_t item_prio;
//創(chuàng)建優(yōu)先級隊(duì)列
tos_prio_q_create（&prio_q， mgr_pool， prio_q_buffer， PRIO_QUEUE_ITEM_MAX， sizeof（item_t））;
//數(shù)據(jù)入隊(duì)
for（i = PRIO_QUEUE_ITEM_MAX;i 》 0; i--）
{
item.a = i;
item.b = i;
item.c = i;
err = tos_prio_q_enqueue（&prio_q， &item， sizeof（item）， i）;
if（err == K_ERR_NONE）
{
printf（“enqueue a item： %d %d %d
”， item.a， item.b， item.c）;
}
else
{
printf（“prio queue enqueue fail，err = %d
”， err）;
}
}
//隊(duì)列滿之后，繼續(xù)入隊(duì)
err = tos_prio_q_enqueue（&prio_q， &item， sizeof（item_t）， i）;
if（err == K_ERR_PRIO_Q_FULL）
{
printf（“prio queue is full： %s
”， tos_prio_q_is_full（&prio_q） ？ “TRUE” ： “FALSE”）;
}
else
{
printf（“prio queue enqueue fail，err = %d
”， err）;
}
//數(shù)據(jù)出隊(duì)
for（i = 0; i 《 PRIO_QUEUE_ITEM_MAX; ++i）
{
err = tos_prio_q_dequeue（&prio_q， &item， &item_size， &item_prio）;
if（err == K_ERR_NONE）
{
printf（“dequeue a item［piro %d］： %d %d %d
”， item_prio， item.a， item.b， item.c）;
}
else
{
printf（“prio queue dequeue fail，err = %d
”， err）;
}
}
//沒有數(shù)據(jù)后繼續(xù)出隊(duì)
err = tos_prio_q_dequeue（&prio_q， &item， &item_size， &item_prio）;
if（err == K_ERR_PRIO_Q_EMPTY）
{
printf（“prio queue is empty： %s
”， tos_prio_q_is_empty（&prio_q） ？ “TRUE” ： “FALSE”）;
}
else
{
printf（“prio queue dequeue fail，err = %d
”， err）;
}
}
4. 總結(jié)① 普通隊(duì)列是一種只能在一端入隊(duì)，在一端出隊(duì)的數(shù)據(jù)結(jié)構(gòu)，規(guī)則：FIFO。
② 環(huán)形隊(duì)列對內(nèi)存空間的利用率最高，使用最多，規(guī)則：FIFO。
③ 優(yōu)先級隊(duì)列不遵循FIFO，每個元素都有自己的優(yōu)先級，規(guī)則：優(yōu)先級最高的元素先出隊(duì)。
責(zé)任編輯：haq
-
數(shù)據(jù)
+關(guān)注
關(guān)注
8文章
7002瀏覽量
88940 -
存儲
+關(guān)注
關(guān)注
13文章
4296瀏覽量
85798 -
TencentOS
+關(guān)注
關(guān)注
0文章
8瀏覽量
7318
原文標(biāo)題：TencentOS-tiny中隊(duì)列、環(huán)形隊(duì)列、優(yōu)先級隊(duì)列的實(shí)現(xiàn)及使用
文章出處：【微信號：strongerHuang，微信公眾號：strongerHuang】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
助力AIoT應(yīng)用：在米爾FPGA開發(fā)板上實(shí)現(xiàn)Tiny YOLO V4
JavaWeb消息隊(duì)列使用指南
分享一個嵌入式通用FIFO環(huán)形緩沖區(qū)實(shí)現(xiàn)庫
嵌入式環(huán)形隊(duì)列與消息隊(duì)列的實(shí)現(xiàn)原理
單片機(jī)中的幾種環(huán)形緩沖區(qū)的分析和實(shí)現(xiàn)
玩轉(zhuǎn)RT-Thread之消息隊(duì)列的應(yīng)用
基于Tiny AI技術(shù)的玻璃敲碎聲事件離線檢測方案
TCL中環(huán)備戰(zhàn)收購Maxeon，助力能源綠色低碳轉(zhuǎn)型
Tiny11 Builder優(yōu)化客戶體驗(yàn)，新增關(guān)閉遙測功能
MCU專屬隊(duì)列功能模塊之QueueForMcu應(yīng)用
裸機(jī)中環(huán)形隊(duì)列與RTOS中消息隊(duì)列有何區(qū)別呢？
工商網(wǎng)監(jiān)
評論