Unreviewed, rolling in r197722.
[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     ListNode()
34         : prev(this)
35         , next(this)
36     {
37     }
38
39     ListNode<T>* prev;
40     ListNode<T>* next;
41 };
42
43 template<typename T>
44 class List {
45     static_assert(std::is_trivially_destructible<T>::value, "List must have a trivial destructor.");
46 public:
47     bool isEmpty() { return m_root.next == &m_root; }
48
49     T* head() { return static_cast<T*>(m_root.next); }
50     T* tail() { return static_cast<T*>(m_root.prev); }
51
52     void push(T* node)
53     {
54         ListNode<T>* it = tail();
55         insertAfter(it, node);
56     }
57
58     T* pop()
59     {
60         ListNode<T>* result = tail();
61         remove(result);
62         return static_cast<T*>(result);
63     }
64
65     void insertAfter(ListNode<T>* it, ListNode<T>* node)
66     {
67         ListNode<T>* prev = it;
68         ListNode<T>* next = it->next;
69
70         node->next = next;
71         next->prev = node;
72
73         node->prev = prev;
74         prev->next = node;
75     }
76
77     void remove(ListNode<T>* node)
78     {
79         ListNode<T>* next = node->next;
80         ListNode<T>* prev = node->prev;
81
82         next->prev = prev;
83         prev->next = next;
84     }
85
86 private:
87     ListNode<T> m_root;
88 };
89
90 } // namespace bmalloc
91
92 #endif // List_h