Embedded System 程式開發， queue 是很常用的資料結構： UART 在接收及傳輸資料時，通常各需要一個 character queue；在處理 keypad 的按鍵輸入時需要一個 key queue ；task 間的溝通，也可能要用到某種 event queue 。
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 還可以用來幫助我們確認模組的介面。
