1 /** @file

2 Linked List Library Functions.

4 Copyright (c) 2006, Intel Corporation<BR>

5 All rights reserved. This program and the accompanying materials

6 are licensed and made available under the terms and conditions of the BSD License

7 which accompanies this distribution. The full text of the license may be found at

8 http://opensource.org/licenses/bsd-license.php

10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,

11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.

13 Module Name: LinkedList.c

15 **/

17 BOOLEAN

18 EFIAPI

21 IN CONST LIST_ENTRY *Node

22 )

23 {

24 UINTN Count;

26 BOOLEAN Found;

28 //

29 // Test the validity of List and Node

30 //

38 Count++;

39 }

44 Count--;

51 Count--;

52 }

54 }

57 }

59 /**

60 Initializes the head node of a doubly linked list, and returns the pointer to

61 the head node of the doubly linked list.

63 Initializes the forward and backward links of a new linked list. After

64 initializing a linked list with this function, the other linked list

65 functions may be used to add and remove nodes from the linked list. It is up

66 to the caller of this function to allocate the memory for ListHead.

68 If ListHead is NULL, then ASSERT().

70 @param ListHead A pointer to the head node of a new doubly linked list.

72 @return ListHead

74 **/

75 LIST_ENTRY *

76 EFIAPI

78 IN OUT LIST_ENTRY *List

79 )

81 {

87 }

89 /**

90 Adds a node to the beginning of a doubly linked list, and returns the pointer

91 to the head node of the doubly linked list.

93 Adds the node Entry at the beginning of the doubly linked list denoted by

94 ListHead, and returns ListHead.

96 If ListHead is NULL, then ASSERT().

97 If Entry is NULL, then ASSERT().

98 If ListHead was not initialized with InitializeListHead(), then ASSERT().

99 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number

100 of nodes in ListHead, including the ListHead node, is greater than or

101 equal to PcdMaximumLinkedListLength, then ASSERT().

103 @param ListHead A pointer to the head node of a doubly linked list.

104 @param Entry A pointer to a node that is to be inserted at the beginning

105 of a doubly linked list.

107 @return ListHead

109 **/

110 LIST_ENTRY *

111 EFIAPI

114 IN OUT LIST_ENTRY *Entry

115 )

116 {

117 //

118 // ASSERT List not too long and Entry is not one of the nodes of List

119 //

127 }

129 /**

130 Adds a node to the end of a doubly linked list, and returns the pointer to

131 the head node of the doubly linked list.

133 Adds the node Entry to the end of the doubly linked list denoted by ListHead,

134 and returns ListHead.

136 If ListHead is NULL, then ASSERT().

137 If Entry is NULL, then ASSERT().

138 If ListHead was not initialized with InitializeListHead(), then ASSERT().

139 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number

140 of nodes in ListHead, including the ListHead node, is greater than or

141 equal to PcdMaximumLinkedListLength, then ASSERT().

143 @param ListHead A pointer to the head node of a doubly linked list.

144 @param Entry A pointer to a node that is to be added at the end of the

145 doubly linked list.

147 @return ListHead

149 **/

150 LIST_ENTRY *

151 EFIAPI

154 IN OUT LIST_ENTRY *Entry

155 )

156 {

157 //

158 // ASSERT List not too long and Entry is not one of the nodes of List

159 //

167 }

169 /**

170 Retrieves the first node of a doubly linked list.

172 Returns the first node of a doubly linked list. List must have been

173 initialized with InitializeListHead(). If List is empty, then NULL is

174 returned.

176 If List is NULL, then ASSERT().

177 If List was not initialized with InitializeListHead(), then ASSERT().

178 If PcdMaximumLinkedListLenth is not zero, and the number of nodes

179 in List, including the List node, is greater than or equal to

180 PcdMaximumLinkedListLength, then ASSERT().

182 @param List A pointer to the head node of a doubly linked list.

184 @return The first node of a doubly linked list.

185 @retval NULL The list is empty.

187 **/

188 LIST_ENTRY *

189 EFIAPI

191 IN CONST LIST_ENTRY *List

192 )

193 {

194 //

195 // ASSERT List not too long

196 //

200 }

202 /**

203 Retrieves the next node of a doubly linked list.

205 Returns the node of a doubly linked list that follows Node. List must have

206 been initialized with InitializeListHead(). If List is empty, then List is

207 returned.

209 If List is NULL, then ASSERT().

210 If Node is NULL, then ASSERT().

211 If List was not initialized with InitializeListHead(), then ASSERT().

212 If PcdMaximumLinkedListLenth is not zero, and List contains more than

213 PcdMaximumLinkedListLenth nodes, then ASSERT().

214 If Node is not a node in List, then ASSERT().

216 @param List A pointer to the head node of a doubly linked list.

217 @param Node A pointer to a node in the doubly linked list.

219 @return Pointer to the next node if one exists. Otherwise a null value which

220 is actually List is returned.

222 **/

223 LIST_ENTRY *

224 EFIAPI

227 IN CONST LIST_ENTRY *Node

228 )

229 {

230 //

231 // ASSERT List not too long and Node is one of the nodes of List

232 //

236 }

238 /**

239 Checks to see if a doubly linked list is empty or not.

241 Checks to see if the doubly linked list is empty. If the linked list contains

242 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.

244 If ListHead is NULL, then ASSERT().

245 If ListHead was not initialized with InitializeListHead(), then ASSERT().

246 If PcdMaximumLinkedListLenth is not zero, and the number of nodes

247 in List, including the List node, is greater than or equal to

248 PcdMaximumLinkedListLength, then ASSERT().

250 @param ListHead A pointer to the head node of a doubly linked list.

252 @retval TRUE The linked list is empty.

253 @retval FALSE The linked list is not empty.

255 **/

256 BOOLEAN

257 EFIAPI

259 IN CONST LIST_ENTRY *List

260 )

261 {

262 //

263 // ASSERT List not too long

264 //

268 }

270 /**

271 Determines if a node in a doubly linked list is null.

273 Returns FALSE if Node is one of the nodes in the doubly linked list specified

274 by List. Otherwise, TRUE is returned. List must have been initialized with

275 InitializeListHead().

277 If List is NULL, then ASSERT().

278 If Node is NULL, then ASSERT().

279 If List was not initialized with InitializeListHead(), then ASSERT().

280 If PcdMaximumLinkedListLenth is not zero, and the number of nodes

281 in List, including the List node, is greater than or equal to

282 PcdMaximumLinkedListLength, then ASSERT().

283 If Node is not a node in List and Node is not equal to List, then ASSERT().

285 @param List A pointer to the head node of a doubly linked list.

286 @param Node A pointer to a node in the doubly linked list.

288 @retval TRUE Node is one of the nodes in the doubly linked list.

289 @retval FALSE Node is not one of the nodes in the doubly linked list.

291 **/

292 BOOLEAN

293 EFIAPI

296 IN CONST LIST_ENTRY *Node

297 )

298 {

299 //

300 // ASSERT List not too long and Node is one of the nodes of List

301 //

305 }

307 /**

308 Determines if a node the last node in a doubly linked list.

310 Returns TRUE if Node is the last node in the doubly linked list specified by

311 List. Otherwise, FALSE is returned. List must have been initialized with

312 InitializeListHead().

314 If List is NULL, then ASSERT().

315 If Node is NULL, then ASSERT().

316 If List was not initialized with InitializeListHead(), then ASSERT().

317 If PcdMaximumLinkedListLenth is not zero, and the number of nodes

318 in List, including the List node, is greater than or equal to

319 PcdMaximumLinkedListLength, then ASSERT().

320 If Node is not a node in List, then ASSERT().

322 @param List A pointer to the head node of a doubly linked list.

323 @param Node A pointer to a node in the doubly linked list.

325 @retval TRUE Node is the last node in the linked list.

326 @retval FALSE Node is not the last node in the linked list.

328 **/

329 BOOLEAN

330 EFIAPI

333 IN CONST LIST_ENTRY *Node

334 )

335 {

336 //

337 // ASSERT List not too long and Node is one of the nodes of List

338 //

342 }

344 /**

345 Swaps the location of two nodes in a doubly linked list, and returns the

346 first node after the swap.

348 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.

349 Otherwise, the location of the FirstEntry node is swapped with the location

350 of the SecondEntry node in a doubly linked list. SecondEntry must be in the

351 same double linked list as FirstEntry and that double linked list must have

352 been initialized with InitializeListHead(). SecondEntry is returned after the

353 nodes are swapped.

355 If FirstEntry is NULL, then ASSERT().

356 If SecondEntry is NULL, then ASSERT().

357 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().

358 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the

359 linked list containing the FirstEntry and SecondEntry nodes, including

360 the FirstEntry and SecondEntry nodes, is greater than or equal to

361 PcdMaximumLinkedListLength, then ASSERT().

363 @param FirstEntry A pointer to a node in a linked list.

364 @param SecondEntry A pointer to another node in the same linked list.

366 **/

367 LIST_ENTRY *

368 EFIAPI

371 IN OUT LIST_ENTRY *SecondEntry

372 )

373 {

378 }

380 //

381 // ASSERT Entry1 and Entry2 are in the same linked list

382 //

385 //

386 // Ptr is the node pointed to by FirstEntry->ForwardLink

387 //

390 //

391 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed

392 // immediately in front of SecondEntry

393 //

396 }

398 //

399 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,

400 // then there are no further steps necessary

401 //

404 }

406 //

407 // Move SecondEntry to the front of Ptr

408 //

412 }

414 /**

415 Removes a node from a doubly linked list, and returns the node that follows

416 the removed node.

418 Removes the node Entry from a doubly linked list. It is up to the caller of

419 this function to release the memory used by this node if that is required. On

420 exit, the node following Entry in the doubly linked list is returned. If

421 Entry is the only node in the linked list, then the head node of the linked

422 list is returned.

424 If Entry is NULL, then ASSERT().

425 If Entry is the head node of an empty list, then ASSERT().

426 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the

427 linked list containing Entry, including the Entry node, is greater than

428 or equal to PcdMaximumLinkedListLength, then ASSERT().

430 @param Entry A pointer to a node in a linked list

432 @return Entry

434 **/

435 LIST_ENTRY *

436 EFIAPI

438 IN CONST LIST_ENTRY *Entry

439 )

440 {

446 }