Demarcate code added due to lack of NSDMI for aggregates
[WebKit-https.git] / Source / bmalloc / bmalloc / List.h
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef List_h
27 #define List_h
28
29 namespace bmalloc {
30
31 template<typename T>
32 struct ListNode {
33 #if !BCOMPILER_SUPPORTS(NSDMI_FOR_AGGREGATES)
34     ListNode() = default;
35     ListNode(ListNode<T>* prev, ListNode<T>* next)
36         : prev { prev }
37         , next { next }
38     {
39     }
40 #endif
41
42     ListNode<T>* prev { nullptr };
43     ListNode<T>* next { nullptr };
44 };
45
46 template<typename T>
47 class List {
48     static_assert(std::is_trivially_destructible<T>::value, "List must have a trivial destructor.");
49
50     struct iterator {
51 #if !BCOMPILER_SUPPORTS(NSDMI_FOR_AGGREGATES)
52         iterator() = default;
53         iterator(ListNode<T>* node)
54             : m_node(node)
55         {
56         }
57 #endif
58
59         T* operator*() { return static_cast<T*>(m_node); }
60         T* operator->() { return static_cast<T*>(m_node); }
61
62         bool operator!=(const iterator& other) { return m_node != other.m_node; }
63
64         iterator& operator++()
65         {
66             m_node = m_node->next;
67             return *this;
68         }
69         
70         ListNode<T>* m_node { nullptr };
71     };
72
73 public:
74     List() { }
75
76     bool isEmpty() { return m_root.next == &m_root; }
77
78     T* head() { return static_cast<T*>(m_root.next); }
79     T* tail() { return static_cast<T*>(m_root.prev); }
80     
81     iterator begin() { return iterator { m_root.next }; }
82     iterator end() { return iterator { &m_root }; }
83
84     void push(T* node)
85     {
86         ListNode<T>* it = tail();
87         insertAfter(it, node);
88     }
89
90     void pushFront(T* node)
91     {
92         ListNode<T>* it = &m_root;
93         insertAfter(it, node);
94     }
95
96     T* pop()
97     {
98         ListNode<T>* result = tail();
99         remove(result);
100         return static_cast<T*>(result);
101     }
102
103     T* popFront()
104     {
105         ListNode<T>* result = head();
106         remove(result);
107         return static_cast<T*>(result);
108     }
109
110     static void insertAfter(ListNode<T>* it, ListNode<T>* node)
111     {
112         ListNode<T>* prev = it;
113         ListNode<T>* next = it->next;
114
115         node->next = next;
116         next->prev = node;
117
118         node->prev = prev;
119         prev->next = node;
120     }
121
122     static void remove(ListNode<T>* node)
123     {
124         ListNode<T>* next = node->next;
125         ListNode<T>* prev = node->prev;
126
127         next->prev = prev;
128         prev->next = next;
129         
130         node->prev = nullptr;
131         node->next = nullptr;
132     }
133
134 private:
135     ListNode<T> m_root { &m_root, &m_root };
136 };
137
138 } // namespace bmalloc
139
140 #endif // List_h