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 18 namespace LIBC_NAMESPACE { 19 namespace internal { 20 21 class IntrusiveList { 22 struct IntrusiveNodeHeader { 23 IntrusiveNodeHeader *next; 24 IntrusiveNodeHeader *prev; 25 }; 26 27 public: insert(void * elem,void * prev)28 LIBC_INLINE static void insert(void *elem, void *prev) { 29 auto elem_header = static_cast<IntrusiveNodeHeader *>(elem); 30 auto prev_header = static_cast<IntrusiveNodeHeader *>(prev); 31 32 if (!prev_header) { 33 // The list is linear and elem will be the only element. 34 elem_header->next = nullptr; 35 elem_header->prev = nullptr; 36 return; 37 } 38 39 auto next = prev_header->next; 40 41 elem_header->next = next; 42 elem_header->prev = prev_header; 43 44 prev_header->next = elem_header; 45 if (next) 46 next->prev = elem_header; 47 } 48 remove(void * elem)49 LIBC_INLINE static void remove(void *elem) { 50 auto elem_header = static_cast<IntrusiveNodeHeader *>(elem); 51 52 auto prev = elem_header->prev; 53 auto next = elem_header->next; 54 55 if (prev) 56 prev->next = next; 57 if (next) 58 next->prev = prev; 59 } 60 }; 61 62 } // namespace internal 63 } // namespace LIBC_NAMESPACE 64 65 #endif // LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H 66