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 struct _RT_LIST_ENTRY *Next; ///< Entry's next element 60 struct _RT_LIST_ENTRY *Prev; ///< Entry's previous element 61 } RT_LIST_ENTRY, *PRT_LIST_ENTRY; 62 63 /// List head would be another name of list entry, and it points to the list header 64 typedef RT_LIST_ENTRY RT_LIST_HEAD, *PRT_LIST_HEAD; 65 66 /*---------------------------------------------------------------------------------- 67 EXTERNAL FUNCTION 68 ----------------------------------------------------------------------------------*/ 69 70 /// Initialize a list with its header 71 void ListInitializeHeader(PRT_LIST_HEAD ListHead); 72 73 /** 74 Add a new entry to the list. 75 Insert a new entry after the specified head. This is good for implementing stacks. 76 \param [IN] ListNew <RT_LIST_ENTRY> : new entry to be added 77 \param [IN OUT] ListHead <RT_LIST_ENTRY> : List header after which to add new entry 78 */ 79 void ListAddToHead(PRT_LIST_ENTRY ListNew, PRT_LIST_HEAD ListHead); 80 81 /** 82 Add a new entry to the list. 83 Insert a new entry before the specified head. This is good for implementing queues. 84 \param [IN] ListNew <RT_LIST_ENTRY> : new entry to be added 85 \param [IN OUT] ListHead <RT_LIST_ENTRY> : List header before which to add new entry 86 */ 87 void ListAddToTail(PRT_LIST_ENTRY ListNew, PRT_LIST_HEAD ListHead); 88 89 /** 90 Get entry in the head of the list 91 \param [IN ] ListHead <RT_LIST_ENTRY> : List header 92 \return entry in the head , otherwise NULL 93 */ 94 RT_LIST_ENTRY *ListGetTop(PRT_LIST_HEAD ListHead); 95 96 /** 97 Get entry in the tail of the list 98 \param [IN ] ListHead <RT_LIST_ENTRY> : List header 99 \return entry in the tail , otherwise NULL 100 */ 101 RT_LIST_ENTRY *ListGetTail(PRT_LIST_HEAD ListHead); 102 103 /** 104 Delete entry from the list 105 Note: ListIsEmpty() on this list entry would not return true, since its state is undefined 106 \param [IN] ListToDelete <RT_LIST_ENTRY> : list entry to be deleted 107 */ 108 void ListDeleteNode(PRT_LIST_ENTRY ListToDelete); 109 110 /** 111 Tell whether the list is empty 112 \param [IN] ListHead <RT_LIST_ENTRY> : List header of which to be test 113 */ 114 unsigned char ListIsEmpty(PRT_LIST_HEAD ListHead); 115 116 void ListAdd(PRT_LIST_ENTRY New, PRT_LIST_ENTRY Prev, PRT_LIST_ENTRY Next); 117 118 /*---------------------------------------------------------------------------------- 119 MACRO 120 ----------------------------------------------------------------------------------*/ 121 122 /** 123 Macros to iterate over the list. 124 \param _Iter : struct PRT_LIST_ENTRY type iterator to use as a loop cursor 125 \param _ListHead : List head of which to be iterated 126 */ 127 #define LIST_FOR_EACH(_Iter, _ListHead) \ 128 for ((_Iter) = (_ListHead)->Next; (_Iter) != (_ListHead); (_Iter) = (_Iter)->Next) 129 130 /** 131 Macros to iterate over the list safely against removal of list entry. 132 If you would delete any list entry from the list while iterating the list, should use this macro 133 \param _Iter : Struct PRT_LIST_ENTRY type iterator to use as a loop cursor 134 \param _Temp : Another Struct PRT_LIST_ENTRY type to use as a temporary storage 135 \param _ListHead : List head of which to be iterated 136 */ 137 #define LIST_FOR_EACH_SAFELY(_Iter, _Temp, _ListHead) \ 138 for ((_Iter) = (_ListHead)->Next, (_Temp) = (_Iter)->Next; (_Iter) != (_ListHead); \ 139 (_Iter) = (_Temp), (_Temp) = (_Iter)->Next) 140 141 /** 142 Macros to get the struct pointer of this list entry 143 You could make every RT_LIST_ENTRY at the first place of your structure to avoid the macro, which will be 144 dangerouse. Copy from winnt.h. BUG:if offset of field in type larger than 32 bit integer, which is not likely to 145 happen, it will error \param _Ptr : Struct RT_LIST_ENTRY type pointer \param _Type : The 146 type of structure in which the RT_LIST_ENTRY embedded in \param _Field : the name of the RT_LIST_ENTRY 147 within the struct 148 */ 149 #define LIST_ENTRY(_Ptr, _Type, _Field) ((_Type *)((char *)(_Ptr) - (unsigned long)(&((_Type *)0)->_Field))) 150 151 #endif /* BT_LIST_H */ 152