diff options
| -rw-r--r-- | common/queue.c | 100 | ||||
| -rw-r--r-- | include/queue.h | 52 | ||||
| -rw-r--r-- | test/queue.c | 152 |
3 files changed, 284 insertions, 20 deletions
diff --git a/common/queue.c b/common/queue.c index e289584a85..67934ca74e 100644 --- a/common/queue.c +++ b/common/queue.c @@ -42,6 +42,82 @@ size_t queue_space(struct queue const *q) return q->buffer_units - queue_count(q); } +int queue_is_full(struct queue const *q) +{ + return (queue_space(q) == 0); +} + +/* + * These pictures make the logic below clearer. The H and T markers are the + * head and tail indicies after they have been modded by the queue size. The + * Empty and Full states are disambiguated by looking at the pre-modded + * indicies. + * + * Empty: T + * T == H H + * |----------------| + * + * Normal: H T + * H < T |---******-------| + * + * Wrapped: T H + * T < H |***----------***| + * + * Full: T + * T == H H + * |****************| + */ + +struct queue_chunk queue_get_write_chunk(struct queue const *q) +{ + size_t head = q->state->head & (q->buffer_units - 1); + size_t tail = q->state->tail & (q->buffer_units - 1); + size_t last = (queue_is_full(q) ? tail : /* Full */ + ((tail < head) ? head : /* Wrapped */ + q->buffer_units)); /* Normal | Empty */ + + return ((struct queue_chunk) { + .length = (last - tail) * q->unit_bytes, + .buffer = q->buffer + tail * q->unit_bytes, + }); +} + +struct queue_chunk queue_get_read_chunk(struct queue const *q) +{ + size_t head = q->state->head & (q->buffer_units - 1); + size_t tail = q->state->tail & (q->buffer_units - 1); + size_t last = (queue_is_empty(q) ? head : /* Empty */ + ((head < tail) ? tail : /* Normal */ + q->buffer_units)); /* Wrapped | Full */ + + return ((struct queue_chunk) { + .length = (last - head) * q->unit_bytes, + .buffer = q->buffer + head * q->unit_bytes, + }); +} + +size_t queue_advance_head(struct queue const *q, size_t count) +{ + size_t transfer = MIN(count, queue_count(q)); + + q->state->head += transfer; + + q->policy->remove(q->policy, transfer); + + return transfer; +} + +size_t queue_advance_tail(struct queue const *q, size_t count) +{ + size_t transfer = MIN(count, queue_space(q)); + + q->state->tail += transfer; + + q->policy->add(q->policy, transfer); + + return transfer; +} + size_t queue_add_unit(struct queue const *q, const void *src) { size_t tail = q->state->tail & (q->buffer_units - 1); @@ -54,11 +130,7 @@ size_t queue_add_unit(struct queue const *q, const void *src) else memcpy(q->buffer + tail * q->unit_bytes, src, q->unit_bytes); - q->state->tail += 1; - - q->policy->add(q->policy, 1); - - return 1; + return queue_advance_tail(q, 1); } size_t queue_add_units(struct queue const *q, const void *src, size_t count) @@ -86,11 +158,7 @@ size_t queue_add_memcpy(struct queue const *q, ((uint8_t const *) src) + first * q->unit_bytes, (transfer - first) * q->unit_bytes); - q->state->tail += transfer; - - q->policy->add(q->policy, transfer); - - return transfer; + return queue_advance_tail(q, transfer); } static void queue_read_safe(struct queue const *q, @@ -125,11 +193,7 @@ size_t queue_remove_unit(struct queue const *q, void *dest) else memcpy(dest, q->buffer + head * q->unit_bytes, q->unit_bytes); - q->state->head += 1; - - q->policy->remove(q->policy, 1); - - return 1; + return queue_advance_head(q, 1); } size_t queue_remove_units(struct queue const *q, void *dest, size_t count) @@ -149,11 +213,7 @@ size_t queue_remove_memcpy(struct queue const *q, queue_read_safe(q, dest, head, transfer, memcpy); - q->state->head += transfer; - - q->policy->remove(q->policy, transfer); - - return transfer; + return queue_advance_head(q, transfer); } size_t queue_peek_units(struct queue const *q, diff --git a/include/queue.h b/include/queue.h index db3c8fe4c4..ef7d001f47 100644 --- a/include/queue.h +++ b/include/queue.h @@ -105,6 +105,58 @@ size_t queue_count(struct queue const *q); /* Return the number of units worth of free space the queue has. */ size_t queue_space(struct queue const *q); +/* Return TRUE if the queue is full. */ +int queue_is_full(struct queue const *q); + +/* + * Chunk based queue access. A queue_chunk is a contiguous region of queue + * buffer bytes, not units. It may represent either free space in the queue + * or entries. + */ +struct queue_chunk { + size_t length; + uint8_t *buffer; +}; + +/* + * Return the largest contiguous block of free space from the tail of the + * queue. This may not be all of the available free space in the queue. Once + * some or all of the free space has been written to you must call + * queue_advance_tail to update the queue. You do not need to fill all of the + * free space returned before calling queue_advance_tail, and you may call + * queue_advance tail multiple times for a single chunk. But you must not + * advance the tail more than the length of the chunk, or more than the actual + * number of units that you have written to the free space represented by the + * chunk. + */ +struct queue_chunk queue_get_write_chunk(struct queue const *q); + +/* + * Return the largest contiguous block of units from the head of the queue. + * This may not be all of the available units in the queue. Similar rules to + * the above apply to reading from this chunk, you can call queue_advance_head + * after reading, and you can all it multiple times if you like. However, if + * you do not call queue_advance_head this chunk will effectively be a peek + * into the queue contents, and later calls to queue_remove_* will see the + * same units. + */ +struct queue_chunk queue_get_read_chunk(struct queue const *q); + +/* + * Move the queue head pointer forward count units. This discards count + * elements from the head of the queue. It will only discard up to the total + * number of elements in the queue, and it returns the number discarded. + */ +size_t queue_advance_head(struct queue const *q, size_t count); + +/* + * Move the queue tail pointer forward count units. This signals to the queue + * that count new elements have been added to the queue using a queue_chunk + * that was returned by queue_get_write_chunk. Make sure that count units have + * been added to the chunk before calling queue_advance_tail. + */ +size_t queue_advance_tail(struct queue const *q, size_t count); + /* Add one unit to queue. */ size_t queue_add_unit(struct queue const *q, const void *src); diff --git a/test/queue.c b/test/queue.c index 7196663943..16feb07129 100644 --- a/test/queue.c +++ b/test/queue.c @@ -153,6 +153,153 @@ static int test_queue2_odd_even(void) return EC_SUCCESS; } +static int test_queue8_chunks(void) +{ + static uint8_t const data[3] = {1, 2, 3}; + struct queue_chunk chunk; + + queue_init(&test_queue8); + + chunk = queue_get_write_chunk(&test_queue8); + + TEST_ASSERT(chunk.length == 8); + + memcpy(chunk.buffer, data, 3); + + TEST_ASSERT(queue_advance_tail(&test_queue8, 3) == 3); + + chunk = queue_get_read_chunk(&test_queue8); + + TEST_ASSERT(chunk.length == 3); + TEST_ASSERT_ARRAY_EQ(chunk.buffer, data, 3); + + TEST_ASSERT(queue_advance_head(&test_queue8, 3) == 3); + TEST_ASSERT(queue_is_empty(&test_queue8)); + + return EC_SUCCESS; +} + +static int test_queue8_chunks_wrapped(void) +{ + static uint8_t const data[3] = {1, 2, 3}; + + queue_init(&test_queue8); + + /* Move near the end of the queue */ + TEST_ASSERT(queue_advance_tail(&test_queue8, 6) == 6); + TEST_ASSERT(queue_advance_head(&test_queue8, 6) == 6); + + /* Add three units, causing the tail to wrap */ + TEST_ASSERT(queue_add_units(&test_queue8, data, 3) == 3); + + /* + * With a wrapped tail we should only be able to access the first two + * elements for reading, but all five free elements for writing. + */ + TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 2); + TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 5); + + /* Signal that we have read an element */ + TEST_ASSERT(queue_advance_head(&test_queue8, 1) == 1); + + /* + * Now we should only be able to see a single element for reading, but + * all six free element. + */ + TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 1); + TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 6); + + /* Signal that we have read the last two elements */ + TEST_ASSERT(queue_advance_head(&test_queue8, 2) == 2); + + /* + * Now there should be no elements available for reading, and only + * seven, not eight elements available for writing. This is because + * the head/tail pointers now point to the second unit in the array. + */ + TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 0); + TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 7); + + return EC_SUCCESS; +} + +static int test_queue8_chunks_full(void) +{ + static uint8_t const data[8] = {1, 2, 3, 4, 5, 6, 7, 8}; + struct queue_chunk chunk; + + queue_init(&test_queue8); + + /* Move near the end of the queue */ + TEST_ASSERT(queue_advance_tail(&test_queue8, 6) == 6); + TEST_ASSERT(queue_advance_head(&test_queue8, 6) == 6); + + /* Fill the queue */ + TEST_ASSERT(queue_add_units(&test_queue8, data, 8) == 8); + + /* With a full queue we shouldn't be able to write */ + TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 0); + + /* But we should be able to read, though only two entries at first */ + chunk = queue_get_read_chunk(&test_queue8); + + TEST_ASSERT(chunk.length == 2); + TEST_ASSERT_ARRAY_EQ(chunk.buffer, data, 2); + + /* Signal that we have read both units */ + TEST_ASSERT(queue_advance_head(&test_queue8, 2) == 2); + + /* Now we should only be able to see the rest */ + chunk = queue_get_read_chunk(&test_queue8); + + TEST_ASSERT(chunk.length == 6); + TEST_ASSERT_ARRAY_EQ(chunk.buffer, data + 2, 6); + + + return EC_SUCCESS; +} + +static int test_queue8_chunks_empty(void) +{ + queue_init(&test_queue8); + + /* With an empty queue we shouldn't be able to read */ + TEST_ASSERT(queue_get_read_chunk(&test_queue8).length == 0); + + /* But we should be able to write, everything */ + TEST_ASSERT(queue_get_write_chunk(&test_queue8).length == 8); + + return EC_SUCCESS; +} + +static int test_queue8_chunks_advance(void) +{ + queue_init(&test_queue8); + + /* + * We should only be able to advance the tail (add units) as many + * units as there are in an empty queue. + */ + TEST_ASSERT(queue_advance_tail(&test_queue8, 10) == 8); + + /* + * Similarly, we should only be able to advance the head (remove + * units) as many units as there are in the now full queue. + */ + TEST_ASSERT(queue_advance_head(&test_queue8, 10) == 8); + + /* + * And it shouldn't matter if we start in the middle of the queue. + */ + TEST_ASSERT(queue_advance_tail(&test_queue8, 3) == 3); + TEST_ASSERT(queue_advance_head(&test_queue8, 3) == 3); + + TEST_ASSERT(queue_advance_tail(&test_queue8, 10) == 8); + TEST_ASSERT(queue_advance_head(&test_queue8, 10) == 8); + + return EC_SUCCESS; +} + void run_test(void) { test_reset(); @@ -164,6 +311,11 @@ void run_test(void) RUN_TEST(test_queue8_removal); RUN_TEST(test_queue8_peek); RUN_TEST(test_queue2_odd_even); + RUN_TEST(test_queue8_chunks); + RUN_TEST(test_queue8_chunks_wrapped); + RUN_TEST(test_queue8_chunks_full); + RUN_TEST(test_queue8_chunks_empty); + RUN_TEST(test_queue8_chunks_advance); test_print_result(); } |