Yukuan's Blog: An Array Implementation of Queue

Embedded System 程式開發， queue 是很常用的資料結構： UART 在接收及傳輸資料時，通常各需要一個 character queue；在處理 keypad 的按鍵輸入時需要一個 key queue ；task 間的溝通，也可能要用到某種 event queue 。

除了提供一個這樣的 queue 的實作外，在〈A Unit Testing Toy〉中曾經提出的 ToyUnit ，也剛好藉這次，展示其實際的應用：

Architecture

這麼簡單的程式，我們只要分成下列三個 source files 就可以了：

Queue.h -> interface
Queue.c -> implementation
Queue_test.c -> unit test

Writing Test Code First

在真正實作 queue 時，我們可以先利用先前提過的 ToyUnit 來為它寫 test code 。

Queue_test.c 程式片段如下：

 8: #include "Queue.h"
 9: #include "ToyUnit.h"
10: 
11: enum {
12:     BUF_SIZE= 3
13: };
14: 
15: char buf[BUF_SIZE];
16: 
17: int main()
18: {
19:     Queue q;
20: 
21:     Q_init( &q, buf, BUF_SIZE );
22:     TU_ASSERT("03", Q_empty(&q));
23:     TU_ASSERT("04", !Q_full(&q));
24:     TU_ASSERT("05", Q_size(&q) == 0);
25: 
26:     Q_put(&q, 'a');
27:     TU_ASSERT("12", Q_first(&q)=='a');
28:     TU_ASSERT("13", !Q_empty(&q));
29:     TU_ASSERT("14", !Q_full(&q));
30:     TU_ASSERT("15", Q_size(&q) == 1);
31:     TU_ASSERT("16", Q_last(&q)=='a');
32: 
33:     Q_put(&q, 'b');
34:     TU_ASSERT("22", Q_first(&q)=='a');
35:     TU_ASSERT("23", !Q_empty(&q));
36:     TU_ASSERT("24", !Q_full(&q));
37:     TU_ASSERT("25", Q_size(&q) == 2);
38:     TU_ASSERT("26", Q_last(&q)=='b');
39: 
40:     Q_put(&q, 'c');
41:     TU_ASSERT("32", Q_first(&q)=='a');
42:     TU_ASSERT("33", !Q_empty(&q));
43:     TU_ASSERT("34", Q_full(&q));
44:     TU_ASSERT("35", Q_size(&q) == 3);
45:     TU_ASSERT("36", Q_last(&q)=='c');
46: 
47:     TU_ASSERT("41", Q_get(&q)=='a');
48:     TU_ASSERT("42", Q_first(&q)=='b');
49:     TU_ASSERT("43", !Q_empty(&q));
50:     TU_ASSERT("44", !Q_full(&q));
51:     TU_ASSERT("45", Q_size(&q) == 2);
52:     TU_ASSERT("46", Q_last(&q)=='c');
53: 
54:     TU_ASSERT("51", Q_get(&q)=='b');
55:     TU_ASSERT("52", Q_first(&q)=='c');
56:     TU_ASSERT("53", !Q_empty(&q));
57:     TU_ASSERT("54", !Q_full(&q));
58:     TU_ASSERT("55", Q_size(&q) == 1);
59:     TU_ASSERT("56", Q_last(&q)=='c');
60: 
61:     TU_ASSERT("61", Q_get(&q)=='c');
62:     TU_ASSERT("63", Q_empty(&q));
63:     TU_ASSERT("64", !Q_full(&q));
64:     TU_ASSERT("65", Q_size(&q) == 0);
65: 
66:     Q_put(&q, 'd');
67:     TU_ASSERT("72", Q_first(&q)=='d');
68:     TU_ASSERT("73", !Q_empty(&q));
69:     TU_ASSERT("74", !Q_full(&q));
70:     TU_ASSERT("75", Q_size(&q) == 1);
71:     TU_ASSERT("76", Q_last(&q)=='d');
72: 
73:     TU_ASSERT("81", Q_get(&q)=='d');
74:     TU_ASSERT("83", Q_empty(&q));
75:     TU_ASSERT("84", !Q_full(&q));
76:     TU_ASSERT("85", Q_size(&q) == 0);
77: 
78:     TU_ASSERT("91", Q_unget(&q)=='d');
79:     TU_ASSERT("92", Q_first(&q)=='d');
80:     TU_ASSERT("93", !Q_empty(&q));
81:     TU_ASSERT("94", !Q_full(&q));
82:     TU_ASSERT("95", Q_size(&q) == 1);
83:     TU_ASSERT("96", Q_last(&q)=='d');
84: 
85:     Q_clear(&q);
86:     TU_ASSERT("103", Q_empty(&q));
87:     TU_ASSERT("104", !Q_full(&q));
88:     TU_ASSERT("105", Q_size(&q) == 0);
89: 
90:     TU_RESULT();
91: 
92:     return 0;
93: }

算一算，這裡總共寫了 52 個測試。

Compiling -> 一大堆錯誤 -> failure

當然啦，因為根本還沒真正開始寫這個 queue :p

為了記憶體的使用是可預期的，這個 queue 不使用動態記憶體分配，改而讓 client 在 initialize queue 時自己提供 buffer，通常這個 buffer 是一個靜態的 array。

Extracts the Interface

根據先前那個無法編譯過關的 unit test code ，我們已經知道怎麼使用這個 queue 了，從中可以很直覺地抽出 queue 的介面。

Queue.h 程式片段如下：

12: #include <stdlib.h>
13: #include "platform.h"
14: 
15: 
16: typedef char QueueItem; ///< the item type in a queue
17: 
18: typedef struct {
19:     Index first;    ///< index of the first (front) item of a queue.
20:     Index end;      ///< index of the end (last+1) of a queue.
21:     size_t count;   ///< the number of items in a queue.
22:     QueueItem* buf; ///< a pointer that indicates the buffer of a queue.
23:     size_t buf_size;///< buffer size.
24: } Queue;
25: 
26: 
27: void Q_init( Queue* q, QueueItem* buf, size_t buf_size );
28: void Q_clear( Queue* );
29: 
30: void Q_put( Queue*, QueueItem );
31: QueueItem Q_get( Queue* );
32: 
33: QueueItem Q_unget( Queue* );
34: 
35: QueueItem Q_first( const Queue* );
36: QueueItem Q_last( const Queue* );
37: 
38: size_t Q_size( const Queue* );
39: bool Q_empty( const Queue* );
40: bool Q_full( const Queue* );

在一連串的往返，敲定介面的過程中，Compiling 終於過了。

但是 Linking 時又出錯，應該不令人意外吧。 :)

Done the Implementation

現在就來為 queue 補上血肉。如果實作沒出錯，期望看到的 unit test 執行結果如下：

./Queue_test
....................................................
Tests [Pass-Fail]: [52-0]

每 pass 一個 test ，console 畫面上就會打一個點，否則會印出 fail 的訊息。

畫面上有 52 個點，看起來乾乾淨淨、清清爽爽，真讓人覺得愉快！

TU_RESULT(.) 會為我們秀出簡單的測試總結：這個例子顯示，共有 52 個 tests ， pass 52 個， fail 0 個。

這裡再次顯現這類 UnitTest framework 的設計哲學：

讓電腦幫我們比對「預期的執行結果」及「實際的執行結果」間是否一致。
如果測試沒出錯，就不要秀一堆有的沒的東西，擾亂視覺。
執行測試變得簡單、直覺，就會鼓勵我們多測試，這是良性的循環。

Queue.c 完整的實作如下：

  1: /**
  2:  * @file queue.c
  3:  *      Implementes a queue module, and that uses a circular array.
  4:  * @author Jiang Yu-Kuan
  5:  * @date 2006/05/07 (initial version)
  6:  * @date 2006/05/18 (last revision)
  7:  * @version 2.0
  8:  */
  9: #include "Queue.h"
 10: #include <assert.h>
 11: 
 12: 
 13: /** Initilizes a queue.
 14:  * @param[in,out] q the queue to be initialized.
 15:  * @param[in] buf the buffer to store items.
 16:  * @param[in] buf_size the buffer size.
 17:  */
 18: void Q_init( Queue* q, QueueItem* buf, size_t buf_size )
 19: {
 20:     q->first= 0;
 21:     q->end= 0;
 22:     q->count= 0;
 23:     q->buf= buf;
 24:     q->buf_size= buf_size;
 25: }
 26: 
 27: 
 28: /** Clear the queue */
 29: void Q_clear( Queue* q )
 30: {
 31:     q->first= 0;
 32:     q->end= 0;
 33:     q->count= 0;
 34: }
 35: 
 36: 
 37: /** Puts an item to the end of a queue.
 38:  * @param[in,out] q the queue to add an item.
 39:  * @param[in] i the added item.
 40:  */
 41: void Q_put( Queue* q, QueueItem i )
 42: {
 43:     assert (!Q_full(q));
 44: 
 45:     ++q->count;
 46:     q->buf[q->end]= i;
 47:     q->end= (q->end+1) % q->buf_size;
 48: }
 49: 
 50: 
 51: /** Gets the first item of a queue.
 52:  * @param[in,out] q the queue to get an item.
 53:  * @return the gotton item
 54:  */
 55: QueueItem Q_get( Queue* q )
 56: {
 57:     QueueItem i;
 58:     assert (!Q_empty(q));
 59: 
 60:     --q->count;
 61:     i= q->buf[q->first];
 62:     q->first= (q->first+1) % q->buf_size;
 63:     return i;
 64: }
 65: 
 66: 
 67: /** Rolls back a "get" operation.
 68:  * This cannot work correctly next to 'clear' operation.
 69:  * @return the previous character
 70:  */
 71: QueueItem Q_unget( Queue* q )
 72: {
 73:     ++q->count;
 74:     if (q->first == 0)
 75:         q->first= q->buf_size - 1;
 76:     else
 77:         --q->first;
 78:     return q->buf[q->first];
 79: }
 80: 
 81: 
 82: /** Peeks the first item of a queue.
 83:  * @param[in] q the queue to get an item.
 84:  * @return the peeked item
 85:  */
 86: QueueItem Q_first( const Queue* q )
 87: {
 88:     assert (!Q_empty(q));
 89: 
 90:     return q->buf[q->first];
 91: }
 92: 
 93: 
 94: /** Peeks the last item of a queue.
 95:  * @param[in] q the queue to get an item.
 96:  * @return the peeked item
 97:  */
 98: QueueItem Q_last( const Queue* q )
 99: {
100:     Index i;
101:     assert (!Q_empty(q));
102: 
103:     if (q->end == 0)
104:         i= q->buf_size - 1;
105:     else
106:         i= q->end - 1;
107:     return q->buf[i];
108: }
109: 
110: 
111: /** Gets the size of a queue at the moment. */
112: size_t Q_size( const Queue* q )
113: {
114:     return q->count;
115: }
116: 
117: 
118: /** Determines if a queue is empty. */
119: bool Q_empty( const Queue* q )
120: {
121:     return q->count == 0;
122: }
123: 
124: 
125: /** Determines if an queue is full */
126: bool Q_full( const Queue* q )
127: {
128:     return q->count == q->buf_size;
129: }

Afterword

前面三個步驟，通常我並不會很明確地去區隔它們，而是多次往返、反覆，確保這三個部份能維持同步。

實際上，我習慣先把最基本的 interface 及 implementation 完成，再寫對應的 unit test，然後一個一個擴充介面、單元測試、及實作。

Unit test 主要目的有：

最基本的，它是強大的 bug 偵測器，我們要確保程式能通過測試，以證明它目前為止，還沒出錯。
日後如果還發生 bug ，我們就為它補上新的 test 來捕抓這個新的 bug 。
如果 module 有作任何修改，例如新增介面，改變演算法，調整結構等，我們寫的 unit test code 更可以發揮它的作用，讓我們在修改時無後顧之憂，因為 unit test 會捕捉這個過程所衍生的錯誤。
很重要的一點，unit test 還可以用來幫助我們確認模組的介面。