1 /**************************************************************************** 2 * 3 * Copyright (c) 2023, Michael Becker (michael.f.becker@gmail.com) 4 * 5 * This file is part of the FreeRTOS Add-ons project. 6 * 7 * Source Code: 8 * https://github.com/michaelbecker/freertos-addons 9 * 10 * Project Page: 11 * http://michaelbecker.github.io/freertos-addons/ 12 * 13 * On-line Documentation: 14 * http://michaelbecker.github.io/freertos-addons/docs/html/index.html 15 * 16 * MIT License 17 * 18 * Permission is hereby granted, free of charge, to any person obtaining a 19 * copy of this software and associated documentation files 20 * (the "Software"), to deal in the Software without restriction, including 21 * without limitation the rights to use, copy, modify, merge, publish, 22 * distribute, sublicense, and/or sell copies of the Software, and to 23 * permit persons to whom the Software is furnished to do so,subject to the 24 * following conditions: 25 * 26 * + The above copyright notice and this permission notice shall be included 27 * in all copies or substantial portions of the Software. 28 * + Credit is appreciated, but not required, if you find this project 29 * useful enough to include in your application, product, device, etc. 30 * 31 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 32 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 33 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 34 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 35 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 36 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 37 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 38 * 39 ***************************************************************************/ 40 /* 41 * Copyright 2023-2024 NXP 42 * 43 * SPDX-License-Identifier: BSD-3-Clause 44 * 45 */ 46 47 #ifndef SLIST_H_ 48 #define SLIST_H_ 49 50 /** 51 * The singly linked list structure. 52 * 53 * This is designed to be embedded within your data 54 * structure(s). 55 * 56 * These lists offer the smallest storage overhead (one pointer per item), 57 * but many operations may take O(n) time. 58 */ 59 typedef struct SlNode_t_ 60 { 61 /** 62 * A pointer to ourselves. 63 */ 64 struct SlNode_t_ *Next; 65 66 } SlNode_t; 67 68 /** 69 * Macro to initialize a list head. 70 * 71 * @param _head A pointer to the list head. 72 */ 73 #define SlInitHead(_head) (_head)->Next = NULL; 74 75 /** 76 * Add a node to the list head. 77 * Runs in O(1) time. 78 * 79 * @param _head A pointer to the existing list head. 80 * @param _node A pointer to the node you are adding. 81 */ 82 #define SlAddNodeToHead(_head, _node) SlInsertNodeAfter(_head, _node) 83 84 /** 85 * Add a node to the list tail. 86 * Runs in O(n) time. 87 * 88 * @param Head A pointer to the existing list head. 89 * @param Node A pointer to the node you are adding. 90 */ 91 void SlAddNodeToTail(SlNode_t *Head, SlNode_t *Node); 92 93 /** 94 * Removes the node from the list head. 95 * Runs in O(1) time. 96 * 97 * @param Head A pointer to the existing list head. 98 * @return The node removed, or NULL for an empty list. 99 */ 100 SlNode_t *SlRemoveNodeFromHead(SlNode_t *Head); 101 102 /** 103 * Removes the node from the list tail. 104 * Runs in O(n) time. 105 * 106 * @param Head A pointer to the existing list head. 107 * @return The node removed, or NULL for an empty list. 108 */ 109 SlNode_t *SlRemoveNodeFromTail(SlNode_t *Head); 110 111 /** 112 * Check if the list is empty. 113 * 114 * @param _head A pointer to the existing list head. 115 * @return true if the list is empty, false otherwise. 116 */ 117 #define SlIsListEmpty(_head) ((_head)->Next == NULL) 118 119 /** 120 * Inserts a new node into the list right after the marker element. 121 * Runs in O(1) time. 122 * 123 * @param Marker The node you are inserting after. Cannot be NULL. 124 * @param Node The node you are inserting. Cannot be NULL. 125 */ 126 void SlInsertNodeAfter(SlNode_t *Marker, SlNode_t *Node); 127 128 /** 129 * Inserts a new node into the list right before the marker element. 130 * Runs in O(n) time. 131 * 132 * @param Head Pointer to the list head. 133 * @param Marker Node you are inserting before. Cannot be NULL. 134 * @param Node The node you are inserting. Cannot be NULL. 135 */ 136 void SlInsertNodeBefore(SlNode_t *Head, SlNode_t *Marker, SlNode_t *Node); 137 138 /** 139 * Removes a node from the list. 140 * Runs in O(n) time worst case. 141 * 142 * @param Head Pointer to the list head. 143 * @param Node The node you are removing. 144 */ 145 void SlRemoveNode(SlNode_t *Head, SlNode_t *Node); 146 147 /** 148 * Given here in case you do not have an equivalent macro. 149 * @param _type The structure type. 150 * @param _field The name of the field you want the offset to. 151 * @returns The offset into _type where _field starts, in bytes. 152 */ 153 #ifndef OFFSET_OF 154 #define OFFSET_OF(_type, _field) ((size_t) & ((_type *)0)->_field) 155 #endif 156 157 /** 158 * Given here in case you do not have an equivalent macro. 159 * @param _address The real address of the _field you have. 160 * @param _type The structure type. 161 * @param _field The name of the field you want the offset to. 162 * @returns A typed pointer to the structure containing the _field 163 * at _address. 164 */ 165 #ifndef CONTAINING_RECORD 166 #define CONTAINING_RECORD(_address, _type, _field) ((_type *)((unsigned char *)(_address)-OFFSET_OF(_type, _field))) 167 #endif 168 169 /** 170 * Macro to ease walking through all of the nodes in a list. 171 * Runs in O(n) time. 172 * 173 * This will work for an empty list. 174 * 175 * @param _head A pointer to the list head. Cannot be NULL. 176 * @param _node An SlNode_t pointer that you need to define before calling 177 * this macro. 178 */ 179 #define SlForEachNode(_head, _node) for ((_node) = (_head)->Next; (_node) != NULL; (_node) = (_node)->Next) 180 181 #endif 182
