Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / OrderMaker.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. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef WTF_OrderMaker_h
27 #define WTF_OrderMaker_h
28
29 #include <wtf/Bag.h>
30 #include <wtf/HashMap.h>
31 #include <wtf/Noncopyable.h>
32 #include <wtf/SentinelLinkedList.h>
33
34 namespace WTF {
35
36 // This is a collection that is meant to be used for building up lists in a certain order. It's
37 // not an efficient data structure for storing lists, but if you need to build a list by doing
38 // operations like insertBefore(existingValue, newValue), then this class is a good intermediate
39 // helper. Note that the type it operates on must be usable as a HashMap key.
40 template<typename T>
41 class OrderMaker {
42     WTF_MAKE_NONCOPYABLE(OrderMaker);
43     
44     struct Node : BasicRawSentinelNode<Node> {
45         Node(SentinelTag)
46         {
47         }
48
49         Node()
50         {
51         }
52
53         T payload { };
54     };
55     
56 public:
57     OrderMaker()
58     {
59     }
60
61     void prepend(T value)
62     {
63         m_list.push(newNode(value));
64     }
65
66     void append(T value)
67     {
68         m_list.append(newNode(value));
69     }
70
71     void insertBefore(T existingValue, T newValue)
72     {
73         Node* node = m_map.get(existingValue);
74         ASSERT(node);
75         node->prepend(newNode(newValue));
76     }
77     
78     void insertAfter(T existingValue, T newValue)
79     {
80         Node* node = m_map.get(existingValue);
81         ASSERT(node);
82         node->append(newNode(newValue));
83     }
84
85     class iterator {
86     public:
87         iterator()
88         {
89         }
90
91         iterator(Node* node)
92             : m_node(node)
93         {
94         }
95
96         const T& operator*()
97         {
98             return m_node->payload;
99         }
100
101         iterator& operator++()
102         {
103             m_node = m_node->next();
104             return *this;
105         }
106
107         bool operator==(const iterator& other) const
108         {
109             return m_node == other.m_node;
110         }
111
112         bool operator!=(const iterator& other) const
113         {
114             return !(*this == other);
115         }
116         
117     private:
118         Node* m_node { nullptr };
119     };
120
121     iterator begin() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).begin()); }
122     iterator end() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).end()); }
123     
124 private:
125     Node* newNode(T value)
126     {
127         Node* result = m_nodes.add();
128         result->payload = value;
129         m_map.set(value, result);
130         return result;
131     }
132     
133     HashMap<T, Node*> m_map;
134     Bag<Node> m_nodes; // FIXME: We could just manually free the contents of the linked list.
135     SentinelLinkedList<Node> m_list;
136 };
137
138 } // namespace WTF
139
140 using WTF::OrderMaker;
141
142 #endif // WTF_OrderMaker_h
143