git.saurik.com Git - apple/xnu.git/blob

1 /*

3 *

4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@

5 *

6 * This file contains Original Code and/or Modifications of Original Code

7 * as defined in and that are subject to the Apple Public Source License

8 * Version 2.0 (the 'License'). You may not use this file except in

9 * compliance with the License. The rights granted to you under the License

10 * may not be used to create, or enable the creation or redistribution of,

11 * unlawful or unlicensed copies of an Apple operating system, or to

12 * circumvent, violate, or enable the circumvention or violation of, any

13 * terms of an Apple operating system software license agreement.

14 *

15 * Please obtain a copy of the License at

16 * http://www.opensource.apple.com/apsl/ and read it before using this file.

17 *

18 * The Original Code and all software distributed under the License are

19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER

20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,

21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,

22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.

23 * Please see the License for the specific language governing rights and

24 * limitations under the License.

25 *

26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@

27 */

28 /*

29 * @OSF_COPYRIGHT@

30 */

31 /*

32 * Mach Operating System

35 *

36 * Permission to use, copy, modify and distribute this software and its

37 * documentation is hereby granted, provided that both the copyright

38 * notice and this permission notice appear in all copies of the

39 * software, derivative works or modified versions, and any portions

40 * thereof, and that both notices appear in supporting documentation.

41 *

42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"

43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR

44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.

45 *

46 * Carnegie Mellon requests users of this software to return to

47 *

48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU

49 * School of Computer Science

50 * Carnegie Mellon University

51 * Pittsburgh PA 15213-3890

52 *

53 * any improvements or extensions that they make and grant Carnegie Mellon rights

54 * to redistribute these changes.

55 */

56 /*

57 */

58 /*

59 * File: queue.h

60 * Author: Avadis Tevanian, Jr.

61 * Date: 1985

62 *

63 * Type definitions for generic queues.

64 *

65 */

67 #ifndef _KERN_QUEUE_H_

68 #define _KERN_QUEUE_H_

70 #include <mach/mach_types.h>

71 #include <kern/macro_help.h>

73 #include <sys/cdefs.h>

74 #include <string.h>

76 __BEGIN_DECLS

78 /*

79 * Queue Management APIs

80 *

81 * There are currently two subtly different methods of maintining

82 * a queue of objects. Both APIs are contained in this file, and

83 * unfortunately overlap.

84 * (there is also a third way maintained in bsd/sys/queue.h)

85 *

86 * Both methods use a common queue head and linkage pattern:

87 * The head of a queue is declared as:

88 * queue_head_t q_head;

89 *

90 * Elements in this queue are chained together using

91 * struct queue_entry objects embedded within a structure:

92 * struct some_data {

93 * int field1;

94 * int field2;

95 * ...

96 * queue_chain_t link;

97 * ...

98 * int last_field;

99 * };

100 * struct some_data is referred to as the queue "element."

101 * (note that queue_chain_t is typedef'd to struct queue_entry)

102 *

103 * IMPORTANT: The two queue iteration methods described below are not

104 * compatible with one another. You must choose one and be careful

105 * to use only the supported APIs for that method.

106 *

107 * Method 1: chaining of queue_chain_t (linkage chains)

108 * This method uses the next and prev pointers of the struct queue_entry

109 * linkage object embedded in a queue element to point to the next or

110 * previous queue_entry structure in the chain. The head of the queue

111 * (the queue_head_t object) will point to the first and last

112 * struct queue_entry object, and both the next and prev pointer will

113 * point back to the head if the queue is empty.

114 *

115 * This method is the most flexible method of chaining objects together

116 * as it allows multiple chains through a given object, by embedding

117 * multiple queue_chain_t objects in the structure, while simultaneously

118 * providing fast removal and insertion into the queue using only

119 * struct queue_entry object pointers.

120 *

121 * ++ Valid APIs for this style queue ++

122 * -------------------------------------

123 * [C] queue_init

124 * [C] queue_first

125 * [C] queue_next

126 * [C] queue_last

127 * [C] queue_prev

128 * [C] queue_end

129 * [C] queue_empty

130 *

131 * [1] enqueue

132 * [1] dequeue

133 * [1] enqueue_head

134 * [1] enqueue_tail

135 * [1] dequeue_head

136 * [1] dequeue_tail

137 * [1] remqueue

138 * [1] insque

139 * [1] remque

140 * [1] re_queue_head

141 * [1] re_queue_tail

142 * [1] movqueue

143 * [1] qe_element

144 * [1] qe_foreach

145 * [1] qe_foreach_safe

146 * [1] qe_foreach_element

147 * [1] qe_foreach_element_safe

148 *

149 * Method 2: chaining of elements (element chains)

150 * This method uses the next and prev pointers of the struct queue_entry

151 * linkage object embedded in a queue element to point to the next or

152 * previous queue element (not another queue_entry). The head of the

153 * queue will point to the first and last queue element (struct some_data

154 * from the above example) NOT the embedded queue_entry structure. The

155 * first queue element will have a prev pointer that points to the

156 * queue_head_t, and the last queue element will have a next pointer

157 * that points to the queue_head_t.

158 *

159 * This method requires knowledge of the queue_head_t of the queue on

160 * which an element resides in order to remove the element. Iterating

161 * through the elements of the queue is also more cumbersome because

162 * a check against the head pointer plus a cast then offset operation

163 * must be performed at each step of the iteration.

164 *

165 * ++ Valid APIs for this style queue ++

166 * -------------------------------------

167 * [C] queue_init

168 * [C] queue_first

169 * [C] queue_next

170 * [C] queue_last

171 * [C] queue_prev

172 * [C] queue_end

173 * [C] queue_empty

174 *

175 * [2] queue_enter

176 * [2] queue_enter_first

177 * [2] queue_insert_before

178 * [2] queue_insert_after

179 * [2] queue_field

180 * [2] queue_remove

181 * [2] queue_remove_first

182 * [2] queue_remove_last

183 * [2] queue_assign

184 * [2] queue_new_head

185 * [2] queue_iterate

186 *

187 * Legend:

188 * [C] -> API common to both methods

189 * [1] -> API used only in method 1 (linkage chains)

190 * [2] -> API used only in method 2 (element chains)

191 */

192

193 /*

194 * A generic doubly-linked list (queue).

195 */

196

197 struct queue_entry {

198 struct queue_entry *next; /* next element */

199 struct queue_entry *prev; /* previous element */

200

201 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4)

202 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers

203 * are 32-bit:

204 * Since this type is so often cast to various 64-bit aligned types

205 * aligning it to 64-bits will avoid -wcast-align without needing

206 * to disable it entirely. The impact on memory footprint should be

207 * negligible.

208 */

 } __attribute__ ((aligned(8)));

210 #else

211 };

212 #endif

213

214 typedef struct queue_entry *queue_t;

215 typedef struct queue_entry queue_head_t;

216 typedef struct queue_entry queue_chain_t;

217 typedef struct queue_entry *queue_entry_t;

218

219 /*

220 * enqueue puts "elt" on the "queue".

221 * dequeue returns the first element in the "queue".

222 * remqueue removes the specified "elt" from its queue.

223 */

224

225 #define enqueue(queue, elt) enqueue_tail(queue, elt)

226 #define dequeue(queue) dequeue_head(queue)

227

228 #ifdef XNU_KERNEL_PRIVATE

229 #include <kern/debug.h>

230 static inline void

231 __QUEUE_ELT_VALIDATE(queue_entry_t elt)

232 {

233 queue_entry_t elt_next, elt_prev;

234

         if (__improbable(elt == (queue_entry_t)NULL)) {

                 panic("Invalid queue element %p", elt);

237 }

238

239 elt_next = elt->next;

240 elt_prev = elt->prev;

241

         if (__improbable(elt_next == (queue_entry_t)NULL || elt_prev == (queue_entry_t)NULL)) {

                 panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev);

244 }

         if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) {

                 panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p",

                     elt, elt_next, elt_next->prev, elt_prev, elt_prev->next);

248 }

249 }

250

251 static inline void

252 __DEQUEUE_ELT_CLEANUP(queue_entry_t elt)

253 {

         (elt)->next = (queue_entry_t)NULL;

         (elt)->prev = (queue_entry_t)NULL;

256 }

257 #else

258 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)

259 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)

260 #endif /* !XNU_KERNEL_PRIVATE */

261

262 static __inline__ void

263 enqueue_head(

264 queue_t que,

265 queue_entry_t elt)

266 {

267 queue_entry_t old_head;

268

269 __QUEUE_ELT_VALIDATE((queue_entry_t)que);

270 old_head = que->next;

271 elt->next = old_head;

272 elt->prev = que;

273 old_head->prev = elt;

274 que->next = elt;

275 }

276

277 static __inline__ void

278 enqueue_tail(

279 queue_t que,

280 queue_entry_t elt)

281 {

282 queue_entry_t old_tail;

283

284 __QUEUE_ELT_VALIDATE((queue_entry_t)que);

285 old_tail = que->prev;

286 elt->next = que;

287 elt->prev = old_tail;

288 old_tail->next = elt;

289 que->prev = elt;

290 }

291

292 static __inline__ queue_entry_t

293 dequeue_head(

294 queue_t que)

295 {

296 queue_entry_t elt = (queue_entry_t)NULL;

297 queue_entry_t new_head;

298

         if (que->next != que) {

300 elt = que->next;

301 __QUEUE_ELT_VALIDATE(elt);

302 new_head = elt->next; /* new_head may point to que if elt was the only element */

303 new_head->prev = que;

304 que->next = new_head;

305 __DEQUEUE_ELT_CLEANUP(elt);

306 }

307

308 return elt;

309 }

310

311 static __inline__ queue_entry_t

312 dequeue_tail(

313 queue_t que)

314 {

315 queue_entry_t elt = (queue_entry_t)NULL;

316 queue_entry_t new_tail;

317

         if (que->prev != que) {

319 elt = que->prev;

320 __QUEUE_ELT_VALIDATE(elt);

321 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */

322 new_tail->next = que;

323 que->prev = new_tail;

324 __DEQUEUE_ELT_CLEANUP(elt);

325 }

326

327 return elt;

328 }

329

330 static __inline__ void

331 remqueue(

332 queue_entry_t elt)

333 {

334 queue_entry_t next_elt, prev_elt;

335

336 __QUEUE_ELT_VALIDATE(elt);

337 next_elt = elt->next;

338 prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */

339 next_elt->prev = prev_elt;

340 prev_elt->next = next_elt;

341 __DEQUEUE_ELT_CLEANUP(elt);

342 }

343

344 static __inline__ void

345 insque(

346 queue_entry_t entry,

347 queue_entry_t pred)

348 {

349 queue_entry_t successor;

350

351 __QUEUE_ELT_VALIDATE(pred);

352 successor = pred->next;

353 entry->next = successor;

354 entry->prev = pred;

355 successor->prev = entry;

356 pred->next = entry;

357 }

358

359 static __inline__ void

360 remque(

361 queue_entry_t elt)

362 {

363 remqueue(elt);

364 }

365

366 /*

367 * Function: re_queue_head

368 * Parameters:

369 * queue_t que : queue onto which elt will be pre-pended

370 * queue_entry_t elt : element to re-queue

371 * Description:

372 * Remove elt from its current queue and put it onto the

373 * head of a new queue

374 * Note:

375 * This should only be used with Method 1 queue iteration (linkage chains)

376 */

377 static __inline__ void

378 re_queue_head(queue_t que, queue_entry_t elt)

379 {

380 queue_entry_t n_elt, p_elt;

381

382 __QUEUE_ELT_VALIDATE(elt);

383 __QUEUE_ELT_VALIDATE((queue_entry_t)que);

384

385 /* remqueue */

386 n_elt = elt->next;

387 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */

388 n_elt->prev = p_elt;

389 p_elt->next = n_elt;

390

391 /* enqueue_head */

392 n_elt = que->next;

393 elt->next = n_elt;

394 elt->prev = que;

395 n_elt->prev = elt;

396 que->next = elt;

397 }

398

399 /*

400 * Function: re_queue_tail

401 * Parameters:

402 * queue_t que : queue onto which elt will be appended

403 * queue_entry_t elt : element to re-queue

404 * Description:

405 * Remove elt from its current queue and put it onto the

406 * end of a new queue

407 * Note:

408 * This should only be used with Method 1 queue iteration (linkage chains)

409 */

410 static __inline__ void

411 re_queue_tail(queue_t que, queue_entry_t elt)

412 {

413 queue_entry_t n_elt, p_elt;

414

415 __QUEUE_ELT_VALIDATE(elt);

416 __QUEUE_ELT_VALIDATE((queue_entry_t)que);

417

418 /* remqueue */

419 n_elt = elt->next;

420 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */

421 n_elt->prev = p_elt;

422 p_elt->next = n_elt;

423

424 /* enqueue_tail */

425 p_elt = que->prev;

426 elt->next = que;

427 elt->prev = p_elt;

428 p_elt->next = elt;

429 que->prev = elt;

430 }

431

432 /*

433 * Macro: qe_element

434 * Function:

435 * Convert a queue_entry_t to a queue element pointer.

436 * Get a pointer to the user-defined element containing

437 * a given queue_entry_t

438 * Header:

439 * <type> * qe_element(queue_entry_t qe, <type>, field)

440 * qe - queue entry to convert

441 * <type> - what's in the queue (e.g., struct some_data)

442 * <field> - is the chain field in <type>

443 * Note:

444 * Do not use pointer types for <type>

445 */

446 #define qe_element(qe, type, field) __container_of(qe, type, field)

447

448 /*

449 * Macro: qe_foreach

450 * Function:

451 * Iterate over each queue_entry_t structure.

452 * Generates a 'for' loop, setting 'qe' to

453 * each queue_entry_t in the queue.

454 * Header:

455 * qe_foreach(queue_entry_t qe, queue_t head)

456 * qe - iteration variable

457 * head - pointer to queue_head_t (head of queue)

458 * Note:

459 * This should only be used with Method 1 queue iteration (linkage chains)

460 */

461 #define qe_foreach(qe, head) \

462 for (qe = (head)->next; qe != (head); qe = (qe)->next)

463

464 /*

465 * Macro: qe_foreach_safe

466 * Function:

467 * Safely iterate over each queue_entry_t structure.

468 *

469 * Use this iterator macro if you plan to remove the

470 * queue_entry_t, qe, from the queue during the

471 * iteration.

472 * Header:

473 * qe_foreach_safe(queue_entry_t qe, queue_t head)

474 * qe - iteration variable

475 * head - pointer to queue_head_t (head of queue)

476 * Note:

477 * This should only be used with Method 1 queue iteration (linkage chains)

478 */

479 #define qe_foreach_safe(qe, head) \

480 for (queue_entry_t _ne = ((head)->next)->next, \

481 __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \

482 qe != (head); \

483 qe = _ne, _ne = (qe)->next)

484

485 /*

486 * Macro: qe_foreach_element

487 * Function:

488 * Iterate over each _element_ in a queue

489 * where each queue_entry_t points to another

490 * queue_entry_t, i.e., managed by the [de|en]queue_head/

491 * [de|en]queue_tail / remqueue / etc. function.

492 * Header:

493 * qe_foreach_element(<type> *elt, queue_t head, <field>)

494 * elt - iteration variable

495 * <type> - what's in the queue (e.g., struct some_data)

496 * <field> - is the chain field in <type>

497 * Note:

498 * This should only be used with Method 1 queue iteration (linkage chains)

499 */

500 #define qe_foreach_element(elt, head, field) \

501 for (elt = qe_element((head)->next, typeof(*(elt)), field); \

502 &((elt)->field) != (head); \

503 elt = qe_element((elt)->field.next, typeof(*(elt)), field))

504

505 /*

506 * Macro: qe_foreach_element_safe

507 * Function:

508 * Safely iterate over each _element_ in a queue

509 * where each queue_entry_t points to another

510 * queue_entry_t, i.e., managed by the [de|en]queue_head/

511 * [de|en]queue_tail / remqueue / etc. function.

512 *

513 * Use this iterator macro if you plan to remove the

514 * element, elt, from the queue during the iteration.

515 * Header:

516 * qe_foreach_element_safe(<type> *elt, queue_t head, <field>)

517 * elt - iteration variable

518 * <type> - what's in the queue (e.g., struct some_data)

519 * <field> - is the chain field in <type>

520 * Note:

521 * This should only be used with Method 1 queue iteration (linkage chains)

522 */

523 #define qe_foreach_element_safe(elt, head, field) \

524 for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \

525 *__ ## elt ## _unused_shadow __unused = \

526 (elt = qe_element((head)->next, typeof(*(elt)), field)); \

527 &((elt)->field) != (head); \

528 elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \

529

530 #ifdef XNU_KERNEL_PRIVATE

531

532 /* Dequeue an element from head, or return NULL if the queue is empty */

533 #define qe_dequeue_head(head, type, field) ({ \

534 queue_entry_t _tmp_entry = dequeue_head((head)); \

535 type *_tmp_element = (type*) NULL; \

536 if (_tmp_entry != (queue_entry_t) NULL) \

537 _tmp_element = qe_element(_tmp_entry, type, field); \

538 _tmp_element; \

539 })

540

541 /* Dequeue an element from tail, or return NULL if the queue is empty */

542 #define qe_dequeue_tail(head, type, field) ({ \

543 queue_entry_t _tmp_entry = dequeue_tail((head)); \

544 type *_tmp_element = (type*) NULL; \

545 if (_tmp_entry != (queue_entry_t) NULL) \

546 _tmp_element = qe_element(_tmp_entry, type, field); \

547 _tmp_element; \

548 })

549

550 /* Peek at the first element, or return NULL if the queue is empty */

551 #define qe_queue_first(head, type, field) ({ \

552 queue_entry_t _tmp_entry = queue_first((head)); \

553 type *_tmp_element = (type*) NULL; \

554 if (_tmp_entry != (queue_entry_t) head) \

555 _tmp_element = qe_element(_tmp_entry, type, field); \

556 _tmp_element; \

557 })

558

559 /* Peek at the last element, or return NULL if the queue is empty */

560 #define qe_queue_last(head, type, field) ({ \

561 queue_entry_t _tmp_entry = queue_last((head)); \

562 type *_tmp_element = (type*) NULL; \

563 if (_tmp_entry != (queue_entry_t) head) \

564 _tmp_element = qe_element(_tmp_entry, type, field); \

565 _tmp_element; \

566 })

567

568 /* Peek at the next element, or return NULL if the next element is head (indicating queue_end) */

569 #define qe_queue_next(head, element, type, field) ({ \

570 queue_entry_t _tmp_entry = queue_next(&(element)->field); \

571 type *_tmp_element = (type*) NULL; \

572 if (_tmp_entry != (queue_entry_t) head) \

573 _tmp_element = qe_element(_tmp_entry, type, field); \

574 _tmp_element; \

575 })

576

577 /* Peek at the prev element, or return NULL if the prev element is head (indicating queue_end) */

578 #define qe_queue_prev(head, element, type, field) ({ \

579 queue_entry_t _tmp_entry = queue_prev(&(element)->field); \

580 type *_tmp_element = (type*) NULL; \

581 if (_tmp_entry != (queue_entry_t) head) \

582 _tmp_element = qe_element(_tmp_entry, type, field); \

583 _tmp_element; \

584 })

585

586 #endif /* XNU_KERNEL_PRIVATE */

587

588 /*

589 * Macro: QUEUE_HEAD_INITIALIZER()

590 * Function:

591 * Static queue head initializer

592 */

593 #define QUEUE_HEAD_INITIALIZER(name) \

594 { &name, &name }

595

596 /*

597 * Macro: queue_init

598 * Function:

599 * Initialize the given queue.

600 * Header:

601 * void queue_init(q)

602 * queue_t q; \* MODIFIED *\

603 */

604 #define queue_init(q) \

605 MACRO_BEGIN \

606 (q)->next = (q);\

607 (q)->prev = (q);\

608 MACRO_END

609

610 /*

611 * Macro: queue_head_init

612 * Function:

613 * Initialize the given queue head

614 * Header:

615 * void queue_head_init(q)

616 * queue_head_t q; \* MODIFIED *\

617 */

618 #define queue_head_init(q) \

619 queue_init(&(q))

620

621 /*

622 * Macro: queue_chain_init

623 * Function:

624 * Initialize the given queue chain element

625 * Header:

626 * void queue_chain_init(q)

627 * queue_chain_t q; \* MODIFIED *\

628 */

629 #define queue_chain_init(q) \

630 queue_init(&(q))

631

632 /*

633 * Macro: queue_first

634 * Function:

635 * Returns the first entry in the queue,

636 * Header:

637 * queue_entry_t queue_first(q)

638 * queue_t q; \* IN *\

639 */

640 #define queue_first(q) ((q)->next)

641

642 /*

643 * Macro: queue_next

644 * Function:

645 * Returns the entry after an item in the queue.

646 * Header:

647 * queue_entry_t queue_next(qc)

648 * queue_t qc;

649 */

650 #define queue_next(qc) ((qc)->next)

651

652 /*

653 * Macro: queue_last

654 * Function:

655 * Returns the last entry in the queue.

656 * Header:

657 * queue_entry_t queue_last(q)

658 * queue_t q; \* IN *\

659 */

660 #define queue_last(q) ((q)->prev)

661

662 /*

663 * Macro: queue_prev

664 * Function:

665 * Returns the entry before an item in the queue.

666 * Header:

667 * queue_entry_t queue_prev(qc)

668 * queue_t qc;

669 */

670 #define queue_prev(qc) ((qc)->prev)

671

672 /*

673 * Macro: queue_end

674 * Function:

675 * Tests whether a new entry is really the end of

676 * the queue.

677 * Header:

678 * boolean_t queue_end(q, qe)

679 * queue_t q;

680 * queue_entry_t qe;

681 */

682 #define queue_end(q, qe) ((q) == (qe))

683

684 /*

685 * Macro: queue_empty

686 * Function:

687 * Tests whether a queue is empty.

688 * Header:

689 * boolean_t queue_empty(q)

690 * queue_t q;

691 */

692 #define queue_empty(q) queue_end((q), queue_first(q))

693

694 /*

695 * Function: movqueue

696 * Parameters:

697 * queue_t _old : head of a queue whose items will be moved

698 * queue_t _new : new queue head onto which items will be moved

699 * Description:

700 * Rebase queue items in _old onto _new then re-initialize

701 * the _old object to an empty queue.

702 * Equivalent to the queue_new_head Method 2 macro

703 * Note:

704 * Similar to the queue_new_head macro, this macros is intented

705 * to function as an initializer method for '_new' and thus may

706 * leak any list items that happen to be on the '_new' list.

707 * This should only be used with Method 1 queue iteration (linkage chains)

708 */

709 static __inline__ void

710 movqueue(queue_t _old, queue_t _new)

711 {

712 queue_entry_t next_elt, prev_elt;

713

714 __QUEUE_ELT_VALIDATE((queue_entry_t)_old);

715

         if (queue_empty(_old)) {

717 queue_init(_new);

718 return;

719 }

720

721 /*

722 * move the queue at _old to _new

723 * and re-initialize _old

724 */

725 next_elt = _old->next;

726 prev_elt = _old->prev;

727

728 _new->next = next_elt;

729 _new->prev = prev_elt;

730 next_elt->prev = _new;

731 prev_elt->next = _new;

732

733 queue_init(_old);

734 }

735

736 /*----------------------------------------------------------------*/

737 /*

738 * Macros that operate on generic structures. The queue

739 * chain may be at any location within the structure, and there

740 * may be more than one chain.

741 */

742

743 /*

744 * Macro: queue_enter

745 * Function:

746 * Insert a new element at the tail of the queue.

747 * Header:

748 * void queue_enter(q, elt, type, field)

749 * queue_t q;

750 * <type> elt;

751 * <type> is what's in our queue

752 * <field> is the chain field in (*<type>)

753 * Note:

754 * This should only be used with Method 2 queue iteration (element chains)

755 *

756 * We insert a compiler barrier after setting the fields in the element

757 * to ensure that the element is updated before being added to the queue,

758 * which is especially important because stackshot, which operates from

759 * debugger context, iterates several queues that use this macro (the tasks

760 * lists and threads lists) without locks. Without this barrier, the

761 * compiler may re-order the instructions for this macro in a way that

762 * could cause stackshot to trip over an inconsistent queue during

763 * iteration.

764 */

765 #define queue_enter(head, elt, type, field) \

766 MACRO_BEGIN \

767 queue_entry_t __prev; \

768 \

769 __prev = (head)->prev; \

770 (elt)->field.prev = __prev; \

771 (elt)->field.next = head; \

772 __compiler_barrier(); \

773 if ((head) == __prev) { \

774 (head)->next = (queue_entry_t) (elt); \

775 } \

776 else { \

777 ((type)(void *)__prev)->field.next = \

778 (queue_entry_t)(elt); \

779 } \

780 (head)->prev = (queue_entry_t) elt; \

781 MACRO_END

782

783 /*

784 * Macro: queue_enter_first

785 * Function:

786 * Insert a new element at the head of the queue.

787 * Header:

788 * void queue_enter_first(q, elt, type, field)

789 * queue_t q;

790 * <type> elt;

791 * <type> is what's in our queue

792 * <field> is the chain field in (*<type>)

793 * Note:

794 * This should only be used with Method 2 queue iteration (element chains)

795 */

796 #define queue_enter_first(head, elt, type, field) \

797 MACRO_BEGIN \

798 queue_entry_t __next; \

799 \

800 __next = (head)->next; \

801 if ((head) == __next) { \

802 (head)->prev = (queue_entry_t) (elt); \

803 } \

804 else { \

805 ((type)(void *)__next)->field.prev = \

806 (queue_entry_t)(elt); \

807 } \

808 (elt)->field.next = __next; \

809 (elt)->field.prev = head; \

810 (head)->next = (queue_entry_t) elt; \

811 MACRO_END

812

813 /*

814 * Macro: queue_insert_before

815 * Function:

816 * Insert a new element before a given element.

817 * Header:

818 * void queue_insert_before(q, elt, cur, type, field)

819 * queue_t q;

820 * <type> elt;

821 * <type> cur;

822 * <type> is what's in our queue

823 * <field> is the chain field in (*<type>)

824 * Note:

825 * This should only be used with Method 2 queue iteration (element chains)

826 */

827 #define queue_insert_before(head, elt, cur, type, field) \

828 MACRO_BEGIN \

829 queue_entry_t __prev; \

830 \

831 if ((head) == (queue_entry_t)(cur)) { \

832 (elt)->field.next = (head); \

833 if ((head)->next == (head)) { /* only element */ \

834 (elt)->field.prev = (head); \

835 (head)->next = (queue_entry_t)(elt); \

836 } else { /* last element */ \

837 __prev = (elt)->field.prev = (head)->prev; \

838 ((type)(void *)__prev)->field.next = \

839 (queue_entry_t)(elt); \

840 } \

841 (head)->prev = (queue_entry_t)(elt); \

842 } else { \

843 (elt)->field.next = (queue_entry_t)(cur); \

844 if ((head)->next == (queue_entry_t)(cur)) { \

845 /* first element */ \

846 (elt)->field.prev = (head); \

847 (head)->next = (queue_entry_t)(elt); \

848 } else { /* middle element */ \

849 __prev = (elt)->field.prev = (cur)->field.prev; \

850 ((type)(void *)__prev)->field.next = \

851 (queue_entry_t)(elt); \

852 } \

853 (cur)->field.prev = (queue_entry_t)(elt); \

854 } \

855 MACRO_END

856

857 /*

858 * Macro: queue_insert_after

859 * Function:

860 * Insert a new element after a given element.

861 * Header:

862 * void queue_insert_after(q, elt, cur, type, field)

863 * queue_t q;

864 * <type> elt;

865 * <type> cur;

866 * <type> is what's in our queue

867 * <field> is the chain field in (*<type>)

868 * Note:

869 * This should only be used with Method 2 queue iteration (element chains)

870 */

871 #define queue_insert_after(head, elt, cur, type, field) \

872 MACRO_BEGIN \

873 queue_entry_t __next; \

874 \

875 if ((head) == (queue_entry_t)(cur)) { \

876 (elt)->field.prev = (head); \

877 if ((head)->next == (head)) { /* only element */ \

878 (elt)->field.next = (head); \

879 (head)->prev = (queue_entry_t)(elt); \

880 } else { /* first element */ \

881 __next = (elt)->field.next = (head)->next; \

882 ((type)(void *)__next)->field.prev = \

883 (queue_entry_t)(elt); \

884 } \

885 (head)->next = (queue_entry_t)(elt); \

886 } else { \

887 (elt)->field.prev = (queue_entry_t)(cur); \

888 if ((head)->prev == (queue_entry_t)(cur)) { \

889 /* last element */ \

890 (elt)->field.next = (head); \

891 (head)->prev = (queue_entry_t)(elt); \

892 } else { /* middle element */ \

893 __next = (elt)->field.next = (cur)->field.next; \

894 ((type)(void *)__next)->field.prev = \

895 (queue_entry_t)(elt); \

896 } \

897 (cur)->field.next = (queue_entry_t)(elt); \

898 } \

899 MACRO_END

900

901 /*

902 * Macro: queue_field [internal use only]

903 * Function:

904 * Find the queue_chain_t (or queue_t) for the

905 * given element (thing) in the given queue (head)

906 * Note:

907 * This should only be used with Method 2 queue iteration (element chains)

908 */

909 #define queue_field(head, thing, type, field) \

910 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)

911

912 /*

913 * Macro: queue_remove

914 * Function:

915 * Remove an arbitrary item from the queue.

916 * Header:

917 * void queue_remove(q, qe, type, field)

918 * arguments as in queue_enter

919 * Note:

920 * This should only be used with Method 2 queue iteration (element chains)

921 */

922 #define queue_remove(head, elt, type, field) \

923 MACRO_BEGIN \

924 queue_entry_t __next, __prev; \

925 \

926 __next = (elt)->field.next; \

927 __prev = (elt)->field.prev; \

928 \

929 if ((head) == __next) \

930 (head)->prev = __prev; \

931 else \

932 ((type)(void *)__next)->field.prev = __prev; \

933 \

934 if ((head) == __prev) \

935 (head)->next = __next; \

936 else \

937 ((type)(void *)__prev)->field.next = __next; \

938 \

939 (elt)->field.next = NULL; \

940 (elt)->field.prev = NULL; \

941 MACRO_END

942

943 /*

944 * Macro: queue_remove_first

945 * Function:

946 * Remove and return the entry at the head of

947 * the queue.

948 * Header:

949 * queue_remove_first(head, entry, type, field)

950 * entry is returned by reference

951 * Note:

952 * This should only be used with Method 2 queue iteration (element chains)

953 */

954 #define queue_remove_first(head, entry, type, field) \

955 MACRO_BEGIN \

956 queue_entry_t __next; \

957 \

958 (entry) = (type)(void *) ((head)->next); \

959 __next = (entry)->field.next; \

960 \

961 if ((head) == __next) \

962 (head)->prev = (head); \

963 else \

964 ((type)(void *)(__next))->field.prev = (head); \

965 (head)->next = __next; \

966 \

967 (entry)->field.next = NULL; \

968 (entry)->field.prev = NULL; \

969 MACRO_END

970

971 /*

972 * Macro: queue_remove_last

973 * Function:

974 * Remove and return the entry at the tail of

975 * the queue.

976 * Header:

977 * queue_remove_last(head, entry, type, field)

978 * entry is returned by reference

979 * Note:

980 * This should only be used with Method 2 queue iteration (element chains)

981 */

982 #define queue_remove_last(head, entry, type, field) \

983 MACRO_BEGIN \

984 queue_entry_t __prev; \

985 \

986 (entry) = (type)(void *) ((head)->prev); \

987 __prev = (entry)->field.prev; \

988 \

989 if ((head) == __prev) \

990 (head)->next = (head); \

991 else \

992 ((type)(void *)(__prev))->field.next = (head); \

993 (head)->prev = __prev; \

994 \

995 (entry)->field.next = NULL; \

996 (entry)->field.prev = NULL; \

997 MACRO_END

998

999 /*

1000 * Macro: queue_assign

1001 * Note:

1002 * This should only be used with Method 2 queue iteration (element chains)

1003 */

1004 #define queue_assign(to, from, type, field) \

1005 MACRO_BEGIN \

1006 ((type)(void *)((from)->prev))->field.next = (to); \

1007 ((type)(void *)((from)->next))->field.prev = (to); \

1008 *to = *from; \

1009 MACRO_END

1010

1011 /*

1012 * Macro: queue_new_head

1013 * Function:

1014 * rebase old queue to new queue head

1015 * Header:

1016 * queue_new_head(old, new, type, field)

1017 * queue_t old;

1018 * queue_t new;

1019 * <type> is what's in our queue

1020 * <field> is the chain field in (*<type>)

1021 * Note:

1022 * This should only be used with Method 2 queue iteration (element chains)

1023 */

1024 #define queue_new_head(old, new, type, field) \

1025 MACRO_BEGIN \

1026 if (!queue_empty(old)) { \

1027 *(new) = *(old); \

1028 ((type)(void *)((new)->next))->field.prev = \

1029 (new); \

1030 ((type)(void *)((new)->prev))->field.next = \

1031 (new); \

1032 } else { \

1033 queue_init(new); \

1034 } \

1035 MACRO_END

1036

1037 /*

1038 * Macro: queue_iterate

1039 * Function:

1040 * iterate over each item in the queue.

1041 * Generates a 'for' loop, setting elt to

1042 * each item in turn (by reference).

1043 * Header:

1044 * queue_iterate(q, elt, type, field)

1045 * queue_t q;

1046 * <type> elt;

1047 * <type> is what's in our queue

1048 * <field> is the chain field in (*<type>)

1049 * Note:

1050 * This should only be used with Method 2 queue iteration (element chains)

1051 */

1052 #define queue_iterate(head, elt, type, field) \

1053 for ((elt) = (type)(void *) queue_first(head); \

1054 !queue_end((head), (queue_entry_t)(elt)); \

1055 (elt) = (type)(void *) queue_next(&(elt)->field))

1056

1057

1058 __END_DECLS

1059

1060 #endif /* _KERN_QUEUE_H_ */