1 /****************************************************************************** 2 * 3 * Copyright (C) 2009-2018 Realtek Corporation. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at: 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 ******************************************************************************/ 18 /****************************************************************************** 19 * 20 * Module Name: 21 * bt_list.h 22 * 23 * Abstract: 24 * To implement list data structure 25 * 26 * Major Change History: 27 * When Who What 28 * -------------------------------------------------------------- 29 * 2010-06-04 W.Bi Created 30 * 31 * Notes: 32 * 33 ******************************************************************************/ 34 35 #ifndef BT_LIST_H 36 #define BT_LIST_H 37 38 /** 39 \file bt_list.h 40 \brief Implement bluetooth list data structure. Has referred to Linux list implementation 41 You could add your new list manipulation here. 42 */ 43 44 /** 45 List entry structure, could be header or node. 46 47 Prev<-----Header---->Next 48 49 Every List has an additional header, and list tail will be list header's previous node. 50 You can use list to form a queue or a stack data structure 51 queue: 52 ListAddToTail----->LIST_FOR_EACH iterate--->manipulate on the list entry 53 Stack: 54 ListAddToHead--- >LIST_FOR_EACH iterate--->manipulate on the list entry 55 */ 56 57 /// RT list structure definition 58 typedef struct _RT_LIST_ENTRY 59 { 60 struct _RT_LIST_ENTRY *Next; ///< Entry's next element 61 struct _RT_LIST_ENTRY *Prev; ///< Entry's previous element 62 } RT_LIST_ENTRY, *PRT_LIST_ENTRY; 63 64 /// List head would be another name of list entry, and it points to the list header 65 typedef RT_LIST_ENTRY RT_LIST_HEAD, *PRT_LIST_HEAD; 66 67 /*---------------------------------------------------------------------------------- 68 EXTERNAL FUNCTION 69 ----------------------------------------------------------------------------------*/ 70 71 /// Initialize a list with its header 72 void ListInitializeHeader(PRT_LIST_HEAD ListHead); 73 74 /** 75 Add a new entry to the list. 76 Insert a new entry after the specified head. This is good for implementing stacks. 77 \param [IN] ListNew <RT_LIST_ENTRY> : new entry to be added 78 \param [IN OUT] ListHead <RT_LIST_ENTRY> : List header after which to add new entry 79 */ 80 void ListAddToHead(PRT_LIST_ENTRY ListNew, PRT_LIST_HEAD ListHead); 81 82 /** 83 Add a new entry to the list. 84 Insert a new entry before the specified head. This is good for implementing queues. 85 \param [IN] ListNew <RT_LIST_ENTRY> : new entry to be added 86 \param [IN OUT] ListHead <RT_LIST_ENTRY> : List header before which to add new entry 87 */ 88 void ListAddToTail(PRT_LIST_ENTRY ListNew, PRT_LIST_HEAD ListHead); 89 90 /** 91 Get entry in the head of the list 92 \param [IN ] ListHead <RT_LIST_ENTRY> : List header 93 \return entry in the head , otherwise NULL 94 */ 95 RT_LIST_ENTRY *ListGetTop(PRT_LIST_HEAD ListHead); 96 97 /** 98 Get entry in the tail of the list 99 \param [IN ] ListHead <RT_LIST_ENTRY> : List header 100 \return entry in the tail , otherwise NULL 101 */ 102 RT_LIST_ENTRY * 103 ListGetTail( 104 PRT_LIST_HEAD ListHead); 105 106 /** 107 Delete entry from the list 108 Note: ListIsEmpty() on this list entry would not return true, since its state is undefined 109 \param [IN] ListToDelete <RT_LIST_ENTRY> : list entry to be deleted 110 */ 111 void ListDeleteNode(PRT_LIST_ENTRY ListToDelete); 112 113 /** 114 Tell whether the list is empty 115 \param [IN] ListHead <RT_LIST_ENTRY> : List header of which to be test 116 */ 117 unsigned char ListIsEmpty(PRT_LIST_HEAD ListHead); 118 119 // EXTERN void ListEmpty(PRT_LIST_HEAD ListHead); 120 121 void ListAdd( 122 PRT_LIST_ENTRY New, 123 PRT_LIST_ENTRY Prev, 124 PRT_LIST_ENTRY Next); 125 126 /*---------------------------------------------------------------------------------- 127 MACRO 128 ----------------------------------------------------------------------------------*/ 129 130 /** 131 Macros to iterate over the list. 132 \param _Iter : struct PRT_LIST_ENTRY type iterator to use as a loop cursor 133 \param _ListHead : List head of which to be iterated 134 */ 135 #define LIST_FOR_EACH(_Iter, _ListHead) \ 136 for ((_Iter) = (_ListHead)->Next; (_Iter) != (_ListHead); (_Iter) = (_Iter)->Next) 137 138 /** 139 Macros to iterate over the list safely against removal of list entry. 140 If you would delete any list entry from the list while iterating the list, should use this macro 141 \param _Iter : Struct PRT_LIST_ENTRY type iterator to use as a loop cursor 142 \param _Temp : Another Struct PRT_LIST_ENTRY type to use as a temporary storage 143 \param _ListHead : List head of which to be iterated 144 */ 145 #define LIST_FOR_EACH_SAFELY(_Iter, _Temp, _ListHead) \ 146 for ((_Iter) = (_ListHead)->Next, (_Temp) = (_Iter)->Next; (_Iter) != (_ListHead); \ 147 (_Iter) = (_Temp), (_Temp) = (_Iter)->Next) 148 149 /** 150 Macros to get the struct pointer of this list entry 151 You could make every RT_LIST_ENTRY at the first place of your structure to avoid the macro, which will be dangerouse. 152 Copy from winnt.h. 153 BUG:if offset of field in type larger than 32 bit integer, which is not likely to happen, it will error 154 \param _Ptr : Struct RT_LIST_ENTRY type pointer 155 \param _Type : The type of structure in which the RT_LIST_ENTRY embedded in 156 \param _Field : the name of the RT_LIST_ENTRY within the struct 157 */ 158 #define LIST_ENTRY(_Ptr, _Type, _Field) ((_Type *)((char *)(_Ptr) - (unsigned long)(&((_Type *)0)->_Field))) 159 160 #endif /*BT_LIST_H*/ 161