xref: /aosp_15_r20/external/llvm-libc/src/__support/intrusive_list.h (revision 71db0c75aadcf003ffe3238005f61d7618a3fead)
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