intrusive-list-inlines.h File

C++ header file with the inline implementations for the intrusive_list_iterator and intrusive_list class templates. More...

Namespaces Index

namespace	micro_os_plus
	The primary namespace for the µOS++ framework. More...
namespace	utils
	The µOS++ utilities definitions. More...

Description

C++ header file with the inline implementations for the intrusive_list_iterator and intrusive_list class templates.

Class definitions are located in intrusive-list.h. Inline methods are separated into this file to improve project structure and maintainability.

File Listing

The file content with the documentation metadata removed is:

1/*

2 * This file is part of the µOS++ project (https://micro-os-plus.github.io/).

3 * Copyright (c) 2016-2026 Liviu Ionescu. All rights reserved.

4 *

5 * Permission to use, copy, modify, and/or distribute this software for any

6 * purpose is hereby granted, under the terms of the MIT license.

7 *

8 * If a copy of the license was not distributed with this file, it can be

9 * obtained from https://opensource.org/licenses/mit.

10 */

11

12// ----------------------------------------------------------------------------

13

14#if !defined(MICRO_OS_PLUS_UTILS_LISTS_INTRUSIVE_LIST_H_)

15#error \

16 "Do not include this file directly; use micro-os-plus/utils/intrusive-list.h."

17#endif // MICRO_OS_PLUS_UTILS_LISTS_INTRUSIVE_LIST_H_

18

29

30#ifndef MICRO_OS_PLUS_UTILS_LISTS_INLINES_INTRUSIVE_LIST_INLINES_H_

31#define MICRO_OS_PLUS_UTILS_LISTS_INLINES_INTRUSIVE_LIST_INLINES_H_

32

33// ----------------------------------------------------------------------------

34

35#if defined(__cplusplus)

36

37// ----------------------------------------------------------------------------

38

39#if defined(__GNUC__)

40#pragma GCC diagnostic push

41

42#pragma GCC diagnostic ignored "-Waggregate-return"

43#if defined(__clang__)

44#pragma clang diagnostic ignored "-Wc++98-compat"

45#endif // defined(__clang__)

46#endif // defined(__GNUC__)

47

48// ----------------------------------------------------------------------------

49

50namespace micro_os_plus::utils

51{

52 // ==========================================================================

53

66 template <class T, class N, N T::* MP, class U>

67 constexpr intrusive_list_iterator<T, N, MP,

68 U>::intrusive_list_iterator () noexcept

69 : node_{}

70 {

71 }

72

81 template <class T, class N, N T::* MP, class U>

82 constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator (

83 N* const node) noexcept

84 : node_{ node }

85 {

86 }

87

96 template <class T, class N, N T::* MP, class U>

97 constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator (

98 reference element) noexcept

99 requires std::derived_from<U, T>

100 : node_{ &(element.*MP) }

101 {

102 }

103

112 template <class T, class N, N T::* MP, class U>

113 inline typename intrusive_list_iterator<T, N, MP, U>::pointer

114 intrusive_list_iterator<T, N, MP, U>::operator->() const noexcept

115 {

116 return get_pointer ();

117 }

118

130 template <class T, class N, N T::* MP, class U>

131 inline typename intrusive_list_iterator<T, N, MP, U>::reference

132 intrusive_list_iterator<T, N, MP, U>::operator*() const noexcept

133 {

134 return *get_pointer ();

135 }

136

145 template <class T, class N, N T::* MP, class U>

146 constexpr intrusive_list_iterator<T, N, MP, U>&

147 intrusive_list_iterator<T, N, MP, U>::operator++() noexcept

148 {

149 node_ = static_cast<iterator_pointer> (node_->next ());

150 return *this;

151 }

152

161 template <class T, class N, N T::* MP, class U>

162 constexpr intrusive_list_iterator<T, N, MP, U>

163 intrusive_list_iterator<T, N, MP, U>::operator++(int) noexcept

164 {

165 const auto tmp = *this;

166 node_ = static_cast<iterator_pointer> (node_->next ());

167 return tmp;

168 }

169

178 template <class T, class N, N T::* MP, class U>

179 constexpr intrusive_list_iterator<T, N, MP, U>&

180 intrusive_list_iterator<T, N, MP, U>::operator--() noexcept

181 {

182 node_ = static_cast<iterator_pointer> (node_->previous ());

183 return *this;

184 }

185

194 template <class T, class N, N T::* MP, class U>

195 constexpr intrusive_list_iterator<T, N, MP, U>

196 intrusive_list_iterator<T, N, MP, U>::operator--(int) noexcept

197 {

198 const auto tmp = *this;

199 node_ = static_cast<iterator_pointer> (node_->previous ());

200 return tmp;

201 }

202

211 template <class T, class N, N T::* MP, class U>

212 constexpr bool

213 intrusive_list_iterator<T, N, MP, U>::operator==(

214 const intrusive_list_iterator& other) const noexcept

215 {

216 return node_ == other.node_;

217 }

218

228 template <class T, class N, N T::* MP, class U>

229 inline typename intrusive_list_iterator<T, N, MP, U>::pointer

230 intrusive_list_iterator<T, N, MP, U>::get_pointer (void) const noexcept

231 {

232 // static_assert(std::is_convertible<U, T>::value == true, "U must be

233 // implicitly convertible to T!");

234

235 // Compute the byte offset of the intrusive node member within T.

236 // Note: dereferencing a null pointer is formally undefined behaviour

237 // under the C++ standard. In practice, no known compiler miscompiles

238 // this idiom on any supported target; `offsetof` cannot be used here

239 // because `MP` is a template parameter (a pointer-to-member), not a

240 // literal member name.

241 const auto offset = reinterpret_cast<difference_type> (

242 &(static_cast<T*> (nullptr)->*MP));

243

244 // Compute the address of the object which includes the

245 // intrusive node, by adjusting down the node address.

246 return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node_)

247 - offset);

248 }

249

256 template <class T, class N, N T::* MP, class U>

257 constexpr typename intrusive_list_iterator<T, N, MP, U>::iterator_pointer

258 intrusive_list_iterator<T, N, MP, U>::get_iterator_pointer () const noexcept

259 {

260 return node_;

261 }

262

263 // ==========================================================================

264

280 template <class T, doubly_list_links_node N, N T::* MP,

281 doubly_list_links_node L, class U>

282 constexpr intrusive_list<T, N, MP, L, U>::intrusive_list () noexcept

283 {

284#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_CONSTRUCTORS_ENABLED)

285 trace::printf ("%s() @%p \n", __func__, static_cast<const void*> (this));

286#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_CONSTRUCTORS_ENABLED)

287 }

288

296 template <class T, doubly_list_links_node N, N T::* MP,

297 doubly_list_links_node L, class U>

298 constexpr intrusive_list<T, N, MP, L, U>::~intrusive_list ()

299 {

300#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_CONSTRUCTORS_ENABLED)

301 trace::printf ("%s() @%p \n", __func__, static_cast<const void*> (this));

302#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_CONSTRUCTORS_ENABLED)

303 }

304

316 template <class T, doubly_list_links_node N, N T::* MP,

317 doubly_list_links_node L, class U>

318 bool

319 intrusive_list<T, N, MP, L, U>::initialise_once (void) noexcept

320 {

321 return doubly_list<N, L>::initialise_once ();

322 }

323

331 template <class T, doubly_list_links_node N, N T::* MP,

332 doubly_list_links_node L, class U>

333 [[nodiscard]] constexpr bool

334 intrusive_list<T, N, MP, L, U>::empty (void) const noexcept

335 {

336 return doubly_list<N, L>::empty ();

337 }

338

348 template <class T, doubly_list_links_node N, N T::* MP,

349 doubly_list_links_node L, class U>

350 void

351 intrusive_list<T, N, MP, L, U>::link_tail (U& node) noexcept

352 {

353#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

354 trace::printf ("%s() @%p %p\n", __func__, static_cast<const void*> (this),

355 static_cast<const void*> (&node));

356#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

357

358 // The assert(links_.initialised()) is checked by the L class.

359

360 // Compute the byte offset of the intrusive node member within T.

361 // Note: see the comment in get_pointer() regarding the use of

362 // a null pointer dereference to obtain the member offset.

363 const auto offset = reinterpret_cast<difference_type> (

364 &(static_cast<T*> (nullptr)->*MP));

365

366 // Add thread intrusive node at the end of the list.

367 (const_cast<N*> (doubly_list<N, L>::tail ()))

368 ->link_next (reinterpret_cast<N*> (

369 reinterpret_cast<difference_type> (&node) + offset));

370 }

371

381 template <class T, doubly_list_links_node N, N T::* MP,

382 doubly_list_links_node L, class U>

383 void

384 intrusive_list<T, N, MP, L, U>::link_head (U& node) noexcept

385 {

386#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

387 trace::printf ("%s() @%p %p\n", __func__, static_cast<const void*> (this),

388 static_cast<const void*> (&node));

389#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

390

391 // The assert(links_.initialised()) is checked by the L class.

392

393 // Compute the byte offset of the intrusive node member within T.

394 // Note: see the comment in get_pointer() regarding the use of

395 // a null pointer dereference to obtain the member offset.

396 const auto offset = reinterpret_cast<difference_type> (

397 &(static_cast<T*> (nullptr)->*MP));

398

399 // Add thread intrusive node at the beginning of the list.

400 (const_cast<N*> (doubly_list<N, L>::head ()))

401 ->link_previous (reinterpret_cast<N*> (

402 reinterpret_cast<difference_type> (&node) + offset));

403 }

404

405#if defined(__GNUC__)

406#pragma GCC diagnostic push

407

408#pragma GCC diagnostic ignored "-Waggregate-return"

409#endif // defined(__GNUC__)

410

419 template <class T, doubly_list_links_node N, N T::* MP,

420 doubly_list_links_node L, class U>

421 inline typename intrusive_list<T, N, MP, L, U>::iterator

422 intrusive_list<T, N, MP, L, U>::begin () const noexcept

423 {

424#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

425 trace::printf ("%s() @%p\n", __func__, static_cast<const void*> (this));

426#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

427

428 // The assert(links_.initialised()) is checked by the L class.

429

430 return iterator{ static_cast<iterator_pointer> (

431 doubly_list<N, L>::links_.next ()) };

432 }

433

442 template <class T, doubly_list_links_node N, N T::* MP,

443 doubly_list_links_node L, class U>

444 inline typename intrusive_list<T, N, MP, L, U>::iterator

445 intrusive_list<T, N, MP, L, U>::end () const noexcept

446 {

447#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

448 trace::printf ("%s() @%p\n", __func__, static_cast<const void*> (this));

449#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

450

451 // The assert would probably be redundant, since it was

452 // already tested in `begin()`.

453

454 using links_type_ = typename doubly_list<N, L>::links_type;

455 return iterator{ reinterpret_cast<iterator_pointer> (

456 const_cast<links_type_*> (doubly_list<N, L>::links_pointer ())) };

457 }

458

465 template <class T, doubly_list_links_node N, N T::* MP,

466 doubly_list_links_node L, class U>

467 inline typename intrusive_list<T, N, MP, L, U>::reverse_iterator

468 intrusive_list<T, N, MP, L, U>::rbegin () const noexcept

469 {

470 return reverse_iterator{ end () };

471 }

472

479 template <class T, doubly_list_links_node N, N T::* MP,

480 doubly_list_links_node L, class U>

481 inline typename intrusive_list<T, N, MP, L, U>::reverse_iterator

482 intrusive_list<T, N, MP, L, U>::rend () const noexcept

483 {

484 return reverse_iterator{ begin () };

485 }

486

487#if defined(__GNUC__)

488#pragma GCC diagnostic pop

489#endif // defined(__GNUC__)

490

500 template <class T, doubly_list_links_node N, N T::* MP,

501 doubly_list_links_node L, class U>

502 inline typename intrusive_list<T, N, MP, L, U>::pointer

503 intrusive_list<T, N, MP, L, U>::get_pointer (

504 iterator_pointer node) const noexcept

505 {

506 // static_assert(std::is_convertible<U, T>::value == true, "U must be

507 // implicitly convertible to T!");

508

509 // Compute the byte offset of the intrusive node member within T.

510 // Note: see the comment in get_pointer() regarding the use of

511 // a null pointer dereference to obtain the member offset.

512 const auto offset = reinterpret_cast<difference_type> (

513 &(static_cast<T*> (nullptr)->*MP));

514

515 // Compute the address of the object which includes the

516 // intrusive node, by adjusting down the node address.

517 return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node)

518 - offset);

519 }

520

528 template <class T, doubly_list_links_node N, N T::* MP,

529 doubly_list_links_node L, class U>

530 [[nodiscard]] typename intrusive_list<T, N, MP, L, U>::pointer

531 intrusive_list<T, N, MP, L, U>::unlink_head (void) noexcept

532 {

533#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

534 trace::printf ("%s() @%p\n", __func__, static_cast<const void*> (this));

535#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

536

537 if (empty ())

538 {

539 return nullptr;

540 }

541

542 // The first element in the list.

543 iterator_pointer it

544 = static_cast<iterator_pointer> (doubly_list<N, L>::links_.next ());

545 it->unlink ();

546

547 return get_pointer (it);

548 }

549

557 template <class T, doubly_list_links_node N, N T::* MP,

558 doubly_list_links_node L, class U>

559 [[nodiscard]] typename intrusive_list<T, N, MP, L, U>::pointer

560 intrusive_list<T, N, MP, L, U>::unlink_tail (void) noexcept

561 {

562#if defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

563 trace::printf ("%s() @%p\n", __func__, static_cast<const void*> (this));

564#endif // defined(MICRO_OS_PLUS_UTILS_LISTS_TRACE_ENABLED)

565

566 if (empty ())

567 {

568 return nullptr;

569 }

570

571 // The last element in the list.

572 iterator_pointer it = static_cast<iterator_pointer> (

573 doubly_list<N, L>::links_.previous ());

574 it->unlink ();

575

576 return get_pointer (it);

577 }

578

579 // --------------------------------------------------------------------------

580} // namespace micro_os_plus::utils

581

582#if defined(__GNUC__)

583#pragma GCC diagnostic pop

584#endif // defined(__GNUC__)

585

586// ----------------------------------------------------------------------------

587

588#endif // defined(__cplusplus)

589

590// ----------------------------------------------------------------------------

591

592#endif // MICRO_OS_PLUS_UTILS_LISTS_INLINES_INTRUSIVE_LIST_INLINES_H_

593

594// ----------------------------------------------------------------------------

---

Generated via doxygen2docusaurus 2.2.2 by Doxygen 1.17.0.