Loading...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | /*
* Copyright (c) 2016-2017 Nordic Semiconductor ASA
* Copyright (c) 2016 Vinayak Kariappa Chettimada
*
* SPDX-License-Identifier: Apache-2.0
*/
/**
* FIFO-style "memory queue" permitting enqueue at tail and dequeue from head.
* Element's payload is a pointer to arbitrary memory.
*
* Implemented as a singly-linked list, with always one-more element.
* The linked list must always contain at least one link-element, as emptiness
* is given by head == tail.
* For a queue to be valid, it must be initialized with an initial link-element.
*
* Invariant: The tail element's mem pointer is DontCare.
*
* Note that at enqueue, memory is not coupled with its accompanying
* link-element, but the link-element before it!
*
* Call | State after call
* ------------------------+-------------------------------
* memq_init(I,H,T) | H -> I[] <- T
* memq_enqueue(A,a,T); | H -> I[a] -> A[] <- T
* memq_enqueue(B,b,T); | H -> I[a] -> A[b] -> B[] <- T
* memq_dequeue(T,H,dest); | H -> A[b] -> B[] <- T # I and a as return and dest
*
* where H is the pointer to Head link-element (oldest element).
* where T is the pointer to Tail link-element (newest element).
* where I[] means the initial link-element, whose mem pointer is DontCare.
* where A[b] means the A'th link-element, whose mem pointer is b.
*/
#include <zephyr/types.h>
#include <stddef.h>
#include "memq.h"
/**
* @brief Initialize a memory queue to be empty and valid.
*
* @param link[in] Initial link-element. Not associated with any mem
* @param head[out] Head of queue. Will be updated
* @param tail[out] Tail of queue. Will be updated
* @return Initial link-element
*/
memq_link_t *memq_init(memq_link_t *link, memq_link_t **head, memq_link_t **tail)
{
/* Head and tail pointer to the initial link - forms an empty queue */
*head = *tail = link;
return link;
}
/**
* @brief De-initialize a memory queue to be empty and invalid.
*
* @param head[in,out] Head of queue. Will be updated
* @param tail[in,out] Tail of queue. Will be updated
* @return Head of queue before invalidation; NULL if queue was empty
*/
memq_link_t *memq_deinit(memq_link_t **head, memq_link_t **tail)
{
memq_link_t *old_head;
/* If head and tail are not equal, then queue is not empty */
if (*head != *tail) {
return NULL;
}
old_head = *head;
*head = *tail = NULL;
return old_head;
}
/**
* @brief Enqueue at the tail of the queue
* @details Enqueue is destructive so tail will change to new tail
* NOTE: The memory will not be associated with the link-element, but
* rather the second-to-last link-element.
*
* @param link[in] Element to be appended. Becomes new tail
* @param mem[in] The memory payload to be enqueued. Pointed to by old tail
* @param tail[in,out] Tail of queue. Will be updated to point to link
* @return New tail. Note: Does not point to the new mem
*/
memq_link_t *memq_enqueue(memq_link_t *link, void *mem, memq_link_t **tail)
{
/* Let the old tail element point to the new tail element */
(*tail)->next = link;
/* Let the old tail element point the the new memory */
(*tail)->mem = mem;
/* Update the tail-pointer to point to the new tail element.
* The new tail-element is not expected to point to anything sensible
*/
*tail = link;
return link;
}
/**
* @brief Non-destructive peek of head of queue.
*
* @param head[in] Pointer to head link-element of queue
* @param tail[in] Pointer to tail link-element of queue
* @param mem[out] The memory pointed to by head-element
* @return head or NULL if queue is empty
*/
memq_link_t *memq_peek(memq_link_t *head, memq_link_t *tail, void **mem)
{
/* If head and tail are equal, then queue empty */
if (head == tail) {
return NULL;
}
/* Extract the head link-element's memory */
if (mem) {
*mem = head->mem;
}
return head; /* queue was not empty */
}
/**
* @brief Remove and returns the head of queue.
* @details Dequeue is destructive so head will change to new head
*
* @param tail[in] Pointer to tail link-element of queue
* @param head[in,out] Pointer to head link-element of queue. Will be updated
* @param mem[out] The memory pointed to by head-element
* @return head or NULL if queue is empty
*/
memq_link_t *memq_dequeue(memq_link_t *tail, memq_link_t **head, void **mem)
{
memq_link_t *old_head;
/* Use memq peek to get the old head and its mem */
old_head = memq_peek(*head, tail, mem);
if (old_head == NULL) {
return NULL; /* queue is empty */
}
/* Update the head-pointer to point to the new head element */
*head = old_head->next;
return old_head;
}
|