TencentOS-tiny中環(huán)形隊列的實現(xiàn)
1. 什么是隊列隊列（queue）是一種只能在一端插入元素、在另一端刪除元素的數(shù)據(jù)結(jié)構(gòu)，遵循「先入先出」（FIFO）的規(guī)則。
隊列中有兩個基本概念：
隊頭指針（可變）：永遠(yuǎn)指向此隊列的第一個數(shù)據(jù)元素；
隊尾指針（可變）：永遠(yuǎn)指向此隊列的最后一個數(shù)據(jù)元素；
隊列中的數(shù)據(jù)存儲方式有兩種：
① 基于靜態(tài)連續(xù)內(nèi)存（數(shù)組）存儲，如圖：② 基于動態(tài)內(nèi)存（鏈表節(jié)點）存儲，如圖：
?
后續(xù)都使用基于靜態(tài)內(nèi)存存儲的隊列講解。
?隊列提供兩個統(tǒng)一的操作：
「入隊（enqueue）」
入隊將一個元素添加到隊尾，并將隊尾指針+1后移，如圖：
「出隊（dequeue）」
出隊將從隊頭中取出一個元素，并將隊頭指針+1后移，如圖：
2. 環(huán)形隊列2.1. 環(huán)形隊列的特點
普通隊列的入隊操作將隊尾指針后移+1，出隊操作將隊頭指針后移+1，操作幾次之后會發(fā)現(xiàn)隊頭指針和隊尾指針都跑到緩沖區(qū)的尾部去了：這就導(dǎo)致了前面的內(nèi)存空間全被浪費，如果要重新恢復(fù)使用，則需要進(jìn)行元素和指針的移動：顯然這種隊列使用方式太不方便了，所以就誕生了環(huán)形隊列：「不用搬移元素和指針，一直可以重復(fù)利用這段內(nèi)存空間」。
2.2. 環(huán)形隊列的實現(xiàn)
TencentOS-tiny中環(huán)形隊列的實現(xiàn)在tos_ring_queue.h和tos_ring_queue.c中。
typedef struct k_ring_queue_st {
knl_obj_t knl_obj;
uint16_t head; //隊頭指針
uint16_t tail; //隊尾指針
size_t total; //記錄隊列中元素的個數(shù)
uint8_t *pool; //隊列底層的存儲結(jié)構(gòu)（一個數(shù)組）
size_t item_size; //隊列中每個元素的大小，單位：字節(jié)
size_t item_cnt; //隊列中可以容納的元素數(shù)量
} k_ring_q_t;
環(huán)形隊列初始化，將隊頭指針和隊尾置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)形隊列是否為滿或者為空：
__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)形隊列入隊操作的API如下：
__API__ k_err_t tos_ring_q_enqueue（k_ring_q_t *ring_q， void *item， size_t item_size）;
在此API中，入隊操作的實現(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)形隊列出隊操作的API如下：
__API__ k_err_t tos_ring_q_dequeue（k_ring_q_t *ring_q， void *item， size_t *item_size）;
在此API中，出隊操作的實現(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;
}
在入隊和出隊操作的時候都使用了 RING_NEXT 宏，用來獲取在環(huán)形隊列中的下一個位置：
#define RING_NEXT（ring_q， index） （（index + 1） % ring_q-》item_cnt）
2.3. 環(huán)形隊列使用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)形隊列
tos_ring_q_create（&ring_q， ring_q_buffer， RING_QUEUE_ITEM_MAX， sizeof（item_t））;
//數(shù)據(jù)入隊
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）;
}
}
//隊列滿之后，繼續(xù)入隊
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ù)出隊
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ù)出隊
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）;
}
}
運行結(jié)果如下：
3. 優(yōu)先級隊列3.1. 優(yōu)先級隊列的特點
優(yōu)先級隊列也是一種基于隊列的數(shù)據(jù)結(jié)構(gòu)，但是它「不遵循FIFO」，而是按照每個元素的優(yōu)先級進(jìn)行出隊：「最高優(yōu)先級的先出隊」。
3.2. 優(yōu)先級隊列的實現(xiàn)
TencentOS-tiny中環(huán)形隊列的實現(xiàn)在tos_prio_queue.h和tos_prio_queue.c中。
優(yōu)先級隊列在數(shù)據(jù)入隊的時候，會按照入隊元素的優(yōu)先級進(jìn)行一次排序，「將優(yōu)先級值最?。▋?yōu)先級最高的元素）放在隊頭」，出隊的時候只需要取第一個元素即可。
正是因為這種特性，優(yōu)先級隊列的底層存儲結(jié)構(gòu)不能使用數(shù)組（排序太麻煩），而是使用了二項堆的數(shù)據(jù)結(jié)構(gòu)。
?
二項堆是一種二叉樹集合的數(shù)據(jù)結(jié)構(gòu)，在本文中不再深入講解，有興趣的讀者可以自己搜索閱讀。
?下面只給出優(yōu)先級隊列的API，「理解其規(guī)則，會用即可」。
創(chuàng)建優(yōu)先級隊列
__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)先級隊列控制塊指針
mgr_array提供一塊緩沖區(qū)用于內(nèi)部管理
pool隊列的緩沖區(qū)
item_cnt隊列可容納的元素數(shù)量
item_size每個元素的大小，單位字節(jié)
其中用于內(nèi)部管理的緩存區(qū)大小可以使用宏定義來計算，比如有5個元素的管理緩沖區(qū)大?。?/p>
uint8_t mgr_pool［TOS_PRIO_Q_MGR_ARRAY_SIZE（5）］;
元素入隊
__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)先級越高。
元素出隊
__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需要傳入一個地址，用于記錄出隊元素的優(yōu)先級。
3.3. 優(yōu)先級隊列使用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)先級隊列
tos_prio_q_create（&prio_q， mgr_pool， prio_q_buffer， PRIO_QUEUE_ITEM_MAX， sizeof（item_t））;
//數(shù)據(jù)入隊
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）;
}
}
//隊列滿之后，繼續(xù)入隊
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ù)出隊
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ù)出隊
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é)① 普通隊列是一種只能在一端入隊，在一端出隊的數(shù)據(jù)結(jié)構(gòu)，規(guī)則：FIFO。
② 環(huán)形隊列對內(nèi)存空間的利用率最高，使用最多，規(guī)則：FIFO。
③ 優(yōu)先級隊列不遵循FIFO，每個元素都有自己的優(yōu)先級，規(guī)則：優(yōu)先級最高的元素先出隊。
責(zé)任編輯：haq
-
數(shù)據(jù)
+關(guān)注
關(guān)注
8文章
7297瀏覽量
93500 -
存儲
+關(guān)注
關(guān)注
13文章
4633瀏覽量
89127 -
TencentOS
+關(guān)注
關(guān)注
0文章
8瀏覽量
7514
原文標(biāo)題：TencentOS-tiny中隊列、環(huán)形隊列、優(yōu)先級隊列的實現(xiàn)及使用
文章出處：【微信號：strongerHuang，微信公眾號：strongerHuang】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
【RA4M2-SENSOR】—— 13.串口實現(xiàn)循環(huán)隊列
NVMe高速傳輸之?dāng)[脫XDMA設(shè)計九：隊列管理模塊設(shè)計（上）
RabbitMQ消息隊列解決方案
JCMsuite應(yīng)用：光學(xué)環(huán)形諧振腔模擬
NVME控制器之隊列管理模塊
NVME控制器之隊列管理模塊
淺談環(huán)形鐵心兼談環(huán)形變壓器
OptiSystem應(yīng)用：環(huán)形通量仿真
將Yolo V3-Tiny模型轉(zhuǎn)換為IR格式遇到錯誤怎么解決？
JCMsuite應(yīng)用：光學(xué)環(huán)形諧振腔模擬
TCL中環(huán)榮獲標(biāo)普全球“行業(yè)最佳進(jìn)步企業(yè)”表彰
助力AIoT應(yīng)用：在米爾FPGA開發(fā)板上實現(xiàn)Tiny YOLO V4
環(huán)形器的特點和應(yīng)用
JavaWeb消息隊列使用指南
分享一個嵌入式通用FIFO環(huán)形緩沖區(qū)實現(xiàn)庫
工商網(wǎng)監(jiān)
評論