1 //===-- Intrusive queue implementation. -------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // An intrusive list that implements the insque and remque semantics. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H 14 #define LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H 15 16 #include "common.h" 17 #include "src/__support/macros/config.h" 18 19 namespace LIBC_NAMESPACE_DECL { 20 namespace internal { 21 22 class IntrusiveList { 23 struct IntrusiveNodeHeader { 24 IntrusiveNodeHeader *next; 25 IntrusiveNodeHeader *prev; 26 }; 27 28 public: insert(void * elem,void * prev)29 LIBC_INLINE static void insert(void *elem, void *prev) { 30 auto elem_header = static_cast<IntrusiveNodeHeader *>(elem); 31 auto prev_header = static_cast<IntrusiveNodeHeader *>(prev); 32 33 if (!prev_header) { 34 // The list is linear and elem will be the only element. 35 elem_header->next = nullptr; 36 elem_header->prev = nullptr; 37 return; 38 } 39 40 auto next = prev_header->next; 41 42 elem_header->next = next; 43 elem_header->prev = prev_header; 44 45 prev_header->next = elem_header; 46 if (next) 47 next->prev = elem_header; 48 } 49 remove(void * elem)50 LIBC_INLINE static void remove(void *elem) { 51 auto elem_header = static_cast<IntrusiveNodeHeader *>(elem); 52 53 auto prev = elem_header->prev; 54 auto next = elem_header->next; 55 56 if (prev) 57 prev->next = next; 58 if (next) 59 next->prev = prev; 60 } 61 }; 62 63 } // namespace internal 64 } // namespace LIBC_NAMESPACE_DECL 65 66 #endif // LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H 67