bmalloc: Small and large objects should share memory
[WebKit.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<T>* prev { nullptr };
34     ListNode<T>* next { nullptr };
35 };
36
37 template<typename T>
38 class List {
39     static_assert(std::is_trivially_destructible<T>::value, "List must have a trivial destructor.");
40
41     struct iterator {
42         T* operator*() { return static_cast<T*>(m_node); }
43         T* operator->() { return static_cast<T*>(m_node); }
44
45         bool operator!=(const iterator& other) { return m_node != other.m_node; }
46
47         iterator& operator++()
48         {
49             m_node = m_node->next;
50             return *this;
51         }
52         
53         ListNode<T>* m_node;
54     };
55
56 public:
57     bool isEmpty() { return m_root.next == &m_root; }
58
59     T* head() { return static_cast<T*>(m_root.next); }
60     T* tail() { return static_cast<T*>(m_root.prev); }
61     
62     iterator begin() { return iterator { m_root.next }; }
63     iterator end() { return iterator { &m_root }; }
64
65     void push(T* node)
66     {
67         ListNode<T>* it = tail();
68         insertAfter(it, node);
69     }
70
71     void pushFront(T* node)
72     {
73         ListNode<T>* it = &m_root;
74         insertAfter(it, node);
75     }
76
77     T* pop()
78     {
79         ListNode<T>* result = tail();
80         remove(result);
81         return static_cast<T*>(result);
82     }
83
84     T* popFront()
85     {
86         ListNode<T>* result = head();
87         remove(result);
88         return static_cast<T*>(result);
89     }
90
91     void insertAfter(ListNode<T>* it, ListNode<T>* node)
92     {
93         ListNode<T>* prev = it;
94         ListNode<T>* next = it->next;
95
96         node->next = next;
97         next->prev = node;
98
99         node->prev = prev;
100         prev->next = node;
101     }
102
103     void remove(ListNode<T>* node)
104     {
105         ListNode<T>* next = node->next;
106         ListNode<T>* prev = node->prev;
107
108         next->prev = prev;
109         prev->next = next;
110         
111         node->prev = nullptr;
112         node->next = nullptr;
113     }
114
115 private:
116     ListNode<T> m_root { &m_root, &m_root };
117 };
118
119 } // namespace bmalloc
120
121 #endif // List_h