Queue: Add policies to queues

Policies give a convenient place to hook into the queue operations
and notify something that there is new space free in the queue or
new units added.

Signed-off-by: Anton Staaf <robotboy@chromium.org>

BRANCH=None
BUG=None
TEST=make buildall -j

Change-Id: I94b2aa94b8e8d07911191bc19a39fa827623b117
Reviewed-on: https://chromium-review.googlesource.com/271791
Reviewed-by: Bill Richardson <wfrichar@chromium.org>
Reviewed-by: Anton Staaf <robotboy@chromium.org>
Commit-Queue: Anton Staaf <robotboy@chromium.org>
Trybot-Ready: Anton Staaf <robotboy@chromium.org>
Tested-by: Anton Staaf <robotboy@chromium.org>

9 files changed, 84 insertions, 31 deletions

diff --git a/board/discovery-stm32f072/echo.c b/board/discovery-stm32f072/echo.c
index 56fbef7bbe..8b1c60314c 100644
--- a/board/discovery-stm32f072/echo.c
+++ b/board/discovery-stm32f072/echo.c
@@ -37,8 +37,10 @@ static void out_ready(struct out_stream const *stream)
 			    IN_READY,					\
 			    OUT_READY)					\
 									\
-	QUEUE_CONFIG(CONCAT2(NAME, _rx_queue), RX_SIZE, uint8_t);	\
-	QUEUE_CONFIG(CONCAT2(NAME, _tx_queue), TX_SIZE, uint8_t);	\
+	static struct queue const CONCAT2(NAME, _rx_queue) =		\
+		QUEUE_NULL(RX_SIZE, uint8_t);				\
+	static struct queue const CONCAT2(NAME, _tx_queue) =		\
+		QUEUE_NULL(TX_SIZE, uint8_t);				\
 									\
 	struct usart_config const NAME;					\
 									\
@@ -63,8 +65,8 @@ USART_STREAM_CONFIG(usart1, usart1_hw, 115200, 64, 64, in_ready, NULL);
 USART_STREAM_CONFIG(usart3, usart3_hw, 115200, 64, 64, in_ready, NULL);
 USART_STREAM_CONFIG(usart4, usart4_hw, 115200, 64, 64, in_ready, NULL);
 
-QUEUE_CONFIG(usb_rx_queue, 256, uint8_t);
-QUEUE_CONFIG(usb_tx_queue, 256, uint8_t);
+static struct queue const usb_rx_queue = QUEUE_NULL(256, uint8_t);
+static struct queue const usb_tx_queue = QUEUE_NULL(256, uint8_t);
 
 struct usb_stream_config const usb_stream1;
 
diff --git a/board/ryu/board.c b/board/ryu/board.c
index 7218a9f8fc..5c4755633b 100644
--- a/board/ryu/board.c
+++ b/board/ryu/board.c
@@ -211,10 +211,10 @@ BUILD_ASSERT(ARRAY_SIZE(usb_strings) == USB_STR_COUNT);
  * stream endpoints.
  */
 
-QUEUE_CONFIG(ap_usart_to_usb, 64, uint8_t);
-QUEUE_CONFIG(usb_to_ap_usart, 64, uint8_t);
-QUEUE_CONFIG(sh_usart_to_usb, 64, uint8_t);
-QUEUE_CONFIG(usb_to_sh_usart, 64, uint8_t);
+static struct queue const ap_usart_to_usb = QUEUE_NULL(64, uint8_t);
+static struct queue const usb_to_ap_usart = QUEUE_NULL(64, uint8_t);
+static struct queue const sh_usart_to_usb = QUEUE_NULL(64, uint8_t);
+static struct queue const usb_to_sh_usart = QUEUE_NULL(64, uint8_t);
 
 struct usb_stream_config const usb_ap_stream;
 struct usb_stream_config const usb_sh_stream;
diff --git a/board/ryu_p4p5/board.c b/board/ryu_p4p5/board.c
index 6694612210..d32e2dd4eb 100644
--- a/board/ryu_p4p5/board.c
+++ b/board/ryu_p4p5/board.c
@@ -209,10 +209,10 @@ BUILD_ASSERT(ARRAY_SIZE(usb_strings) == USB_STR_COUNT);
  * stream endpoints.
  */
 
-QUEUE_CONFIG(ap_usart_to_usb, 64, uint8_t);
-QUEUE_CONFIG(usb_to_ap_usart, 64, uint8_t);
-QUEUE_CONFIG(sh_usart_to_usb, 64, uint8_t);
-QUEUE_CONFIG(usb_to_sh_usart, 64, uint8_t);
+static struct queue const ap_usart_to_usb = QUEUE_NULL(64, uint8_t);
+static struct queue const usb_to_ap_usart = QUEUE_NULL(64, uint8_t);
+static struct queue const sh_usart_to_usb = QUEUE_NULL(64, uint8_t);
+static struct queue const usb_to_sh_usart = QUEUE_NULL(64, uint8_t);
 
 struct usb_stream_config const usb_ap_stream;
 struct usb_stream_config const usb_sh_stream;
diff --git a/chip/host/uart.c b/chip/host/uart.c
index afde763747..989112be80 100644
--- a/chip/host/uart.c
+++ b/chip/host/uart.c
@@ -26,7 +26,7 @@ static pthread_t input_thread;
 #define INPUT_BUFFER_SIZE 16
 static int char_available;
 
-QUEUE_CONFIG(cached_char, INPUT_BUFFER_SIZE, char);
+static struct queue const cached_char = QUEUE_NULL(INPUT_BUFFER_SIZE, char);
 
 #define CONSOLE_CAPTURE_SIZE 2048
 static char capture_buf[CONSOLE_CAPTURE_SIZE];
diff --git a/common/keyboard_8042.c b/common/keyboard_8042.c
index d21b4ceae5..8affac4d8b 100644
--- a/common/keyboard_8042.c
+++ b/common/keyboard_8042.c
@@ -68,7 +68,7 @@ enum scancode_set_list {
  */
 static struct mutex to_host_mutex;
 
-QUEUE_CONFIG(to_host, 16, uint8_t);
+static struct queue const to_host = QUEUE_NULL(16, uint8_t);
 
 /* Queue command/data from the host */
 enum {
@@ -91,7 +91,7 @@ struct host_byte {
  *
  * Hence, 5 (actually 4 plus one spare) is large enough, but use 8 for safety.
  */
-QUEUE_CONFIG(from_host, 8, struct host_byte);
+static struct queue const from_host = QUEUE_NULL(8, struct host_byte);
 
 static int i8042_irq_enabled;
 
diff --git a/common/queue.c b/common/queue.c
index 70b4bd40d0..6e5e9e65ad 100644
--- a/common/queue.c
+++ b/common/queue.c
@@ -7,9 +7,21 @@
 #include "queue.h"
 #include "util.h"
 
+static void queue_action_null(struct queue_policy const *policy, size_t count)
+{
+}
+
+struct queue_policy const queue_policy_null = {
+	.add    = queue_action_null,
+	.remove = queue_action_null,
+};
+
 void queue_init(struct queue const *q)
 {
 	ASSERT(POWER_OF_TWO(q->buffer_units));
+	ASSERT(q->policy);
+	ASSERT(q->policy->add);
+	ASSERT(q->policy->remove);
 
 	q->state->head = 0;
 	q->state->tail = 0;
@@ -44,6 +56,8 @@ size_t queue_add_unit(struct queue const *q, void const *src)
 
 	q->state->tail += 1;
 
+	q->policy->add(q->policy, 1);
+
 	return 1;
 }
 
@@ -74,6 +88,8 @@ size_t queue_add_memcpy(struct queue const *q,
 
 	q->state->tail += transfer;
 
+	q->policy->add(q->policy, transfer);
+
 	return transfer;
 }
 
@@ -111,6 +127,8 @@ size_t queue_remove_unit(struct queue const *q, void *dest)
 
 	q->state->head += 1;
 
+	q->policy->remove(q->policy, 1);
+
 	return 1;
 }
 
@@ -133,6 +151,8 @@ size_t queue_remove_memcpy(struct queue const *q,
 
 	q->state->head += transfer;
 
+	q->policy->remove(q->policy, transfer);
+
 	return transfer;
 }
 
diff --git a/driver/mcdp28x0.c b/driver/mcdp28x0.c
index e7245bd2a5..afcb6f8e71 100644
--- a/driver/mcdp28x0.c
+++ b/driver/mcdp28x0.c
@@ -37,8 +37,8 @@ static inline void print_buffer(uint8_t *buf, int cnt)
 static inline void print_buffer(uint8_t *buf, int cnt) {}
 #endif
 
-QUEUE_CONFIG(rx_queue, MCDP_INBUF_MAX,  uint8_t);
-QUEUE_CONFIG(tx_queue, MCDP_OUTBUF_MAX, uint8_t);
+struct queue const rx_queue = QUEUE_NULL(MCDP_INBUF_MAX,  uint8_t);
+struct queue const tx_queue = QUEUE_NULL(MCDP_OUTBUF_MAX, uint8_t);
 
 struct usart_config const usart_mcdp;
 
diff --git a/include/queue.h b/include/queue.h
index c38e5313f5..a893b58194 100644
--- a/include/queue.h
+++ b/include/queue.h
@@ -15,6 +15,37 @@
 /* Generic queue container. */
 
 /*
+ * Queue policies describe how a queue behaves (who it notifies, in what
+ * contexts) when units are added or removed from the queue.
+ *
+ * The queue_policy structure is a table of virtual function pointers.  Each
+ * policy will implement the add and remove functions.  Each policy also
+ * optionally defines a new structure that contains the queue_policy struct by
+ * value any any additional data needed to implement the policy.  This
+ * structure is then initialized using the policy specific functions and the
+ * additional data.
+ *
+ * If a policy is so simple that it doesn't require any additional data then
+ * the queue_policy structure can just be used directly, as queue_policy_null
+ * does below.
+ */
+struct queue_policy {
+	void (*add)(struct queue_policy const *queue_policy, size_t count);
+	void (*remove)(struct queue_policy const *queue_policy, size_t count);
+};
+
+/*
+ * The NULL policy does no notification when units are added or removed from
+ * the queue.  Since the NULL policy doesn't do anything it doesn't actually
+ * need to extend the queue_policy interface and can just use it directly.
+ *
+ * The QUEUE_NULL macro constructs a queue that uses the NULL policy.
+ */
+extern struct queue_policy const queue_policy_null;
+
+#define QUEUE_NULL(SIZE, TYPE) QUEUE(SIZE, TYPE, queue_policy_null)
+
+/*
  * RAM state for a queue.
  */
 struct queue_state {
@@ -41,6 +72,8 @@ struct queue_state {
 struct queue {
 	struct queue_state volatile *state;
 
+	struct queue_policy const *policy;
+
 	size_t  buffer_units; /* size of buffer (in units) */
 	size_t  unit_bytes;   /* size of unit   (in byte) */
 	uint8_t *buffer;
@@ -48,19 +81,17 @@ struct queue {
 
 /*
  * Convenience macro for construction of a Queue along with its backing buffer
- * and state structure.
+ * and state structure.  This macro creates a compound literal that can be used
+ * to statically initialize a queue.
  */
-#define QUEUE_CONFIG(NAME, SIZE, TYPE)					\
-	static TYPE CONCAT2(NAME, _buffer)[SIZE];			\
-									\
-	static struct queue_state CONCAT2(NAME, _state);		\
-	struct queue const NAME =					\
-	{								\
-		.state        = &CONCAT2(NAME, _state),			\
-		.buffer_units = SIZE,					\
-		.unit_bytes   = sizeof(TYPE),				\
-		.buffer       = (uint8_t *) CONCAT2(NAME, _buffer),	\
-	};
+#define QUEUE(SIZE, TYPE, POLICY)				\
+	((struct queue) {					\
+		.state        = &((struct queue_state){}),	\
+		.policy       = &POLICY,			\
+		.buffer_units = SIZE,				\
+		.unit_bytes   = sizeof(TYPE),			\
+		.buffer       = (uint8_t *) &((TYPE[SIZE]){}),	\
+	})
 
 /* Initialize the queue to empty state. */
 void queue_init(struct queue const *q);
diff --git a/test/queue.c b/test/queue.c
index d5d499377b..7196663943 100644
--- a/test/queue.c
+++ b/test/queue.c
@@ -12,8 +12,8 @@
 #include "timer.h"
 #include "util.h"
 
-QUEUE_CONFIG(test_queue8, 8, char)
-QUEUE_CONFIG(test_queue2, 2, int16_t)
+static struct queue const test_queue8 = QUEUE_NULL(8, char);
+static struct queue const test_queue2 = QUEUE_NULL(2, int16_t);
 
 static int test_queue8_empty(void)
 {