| /* Copyright (c) 2012 The Chromium OS Authors. All rights reserved. |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| * |
| * Queue data structure. |
| */ |
| #ifndef __CROS_EC_QUEUE_H |
| #define __CROS_EC_QUEUE_H |
| |
| #include "common.h" |
| |
| #include <stddef.h> |
| #include <stdint.h> |
| |
| /* 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 { |
| /* |
| * The queue head and tail pointers are not wrapped until they are |
| * needed to access the queue buffer. This has a number of advantages, |
| * the queue doesn't have to waste an entry to disambiguate full and |
| * empty for one. It also provides a convenient total enqueue/dequeue |
| * log (one that does wrap at the limit of a size_t however). |
| * |
| * Empty: |
| * head == tail |
| * |
| * Full: |
| * head - tail == buffer_units |
| */ |
| size_t head; /* head: next to dequeue */ |
| size_t tail; /* tail: next to enqueue */ |
| }; |
| |
| /* |
| * Queue configuration stored in flash. |
| */ |
| 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; |
| }; |
| |
| /* |
| * Convenience macro for construction of a Queue along with its backing buffer |
| * and state structure. This macro creates a compound literal that can be used |
| * to statically initialize a queue. |
| */ |
| #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); |
| |
| /* Return TRUE if the queue is empty. */ |
| int queue_is_empty(struct queue const *q); |
| |
| /* Return the number of units stored in the queue. */ |
| 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); |
| |
| /* Add multiple units to queue. */ |
| size_t queue_add_units(struct queue const *q, const void *src, size_t count); |
| |
| /* Add multiple units to queue using supplied memcpy. */ |
| size_t queue_add_memcpy(struct queue const *q, |
| const void *src, |
| size_t count, |
| void *(*memcpy)(void *dest, |
| const void *src, |
| size_t n)); |
| |
| /* Remove one unit from the begin of the queue. */ |
| size_t queue_remove_unit(struct queue const *q, void *dest); |
| |
| /* Remove multiple units from the begin of the queue. */ |
| size_t queue_remove_units(struct queue const *q, void *dest, size_t count); |
| |
| /* Remove multiple units from the begin of the queue using supplied memcpy. */ |
| size_t queue_remove_memcpy(struct queue const *q, |
| void *dest, |
| size_t count, |
| void *(*memcpy)(void *dest, |
| const void *src, |
| size_t n)); |
| |
| /* Peek (return but don't remove) the count elements starting with the i'th. */ |
| size_t queue_peek_units(struct queue const *q, |
| void *dest, |
| size_t i, |
| size_t count); |
| |
| /* Peek (return but don't remove) the count elements starting with the i'th. */ |
| size_t queue_peek_memcpy(struct queue const *q, |
| void *dest, |
| size_t i, |
| size_t count, |
| void *(*memcpy)(void *dest, |
| const void *src, |
| size_t n)); |
| |
| /* |
| * These macros will statically select the queue functions based on the number |
| * of units that are to be added or removed if they can. The single unit add |
| * and remove functions are much faster than calling the equivalent generic |
| * version with a count of one. |
| */ |
| #define QUEUE_ADD_UNITS(q, src, count) \ |
| ({ \ |
| size_t result; \ |
| \ |
| if (count == 1) \ |
| result = queue_add_unit(q, src); \ |
| else \ |
| result = queue_add_units(q, src, count); \ |
| \ |
| result; \ |
| }) |
| |
| #define QUEUE_REMOVE_UNITS(q, dest, count) \ |
| ({ \ |
| size_t result; \ |
| \ |
| if (count == 1) \ |
| result = queue_remove_unit(q, dest); \ |
| else \ |
| result = queue_remove_units(q, dest, count); \ |
| \ |
| result; \ |
| }) |
| |
| #endif /* __CROS_EC_QUEUE_H */ |