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#pragma once
27
28#include <wtf/Bag.h>
29#include <wtf/HashMap.h>
30#include <wtf/Noncopyable.h>
31#include <wtf/SentinelLinkedList.h>
32
33namespace WTF {
34
35// This is a collection that is meant to be used for building up lists in a certain order. It's
36// not an efficient data structure for storing lists, but if you need to build a list by doing
37// operations like insertBefore(existingValue, newValue), then this class is a good intermediate
38// helper. Note that the type it operates on must be usable as a HashMap key.
39template<typename T>
40class OrderMaker {
41 WTF_MAKE_NONCOPYABLE(OrderMaker);
42
43 struct Node : BasicRawSentinelNode<Node> {
44 Node(SentinelTag)
45 {
46 }
47
48 Node()
49 {
50 }
51
52 T payload { };
53 };
54
55public:
56 OrderMaker()
57 {
58 }
59
60 void prepend(T value)
61 {
62 m_list.push(newNode(value));
63 }
64
65 void append(T value)
66 {
67 m_list.append(newNode(value));
68 }
69
70 void insertBefore(T existingValue, T newValue)
71 {
72 Node* node = m_map.get(existingValue);
73 ASSERT(node);
74 node->prepend(newNode(newValue));
75 }
76
77 void insertAfter(T existingValue, T newValue)
78 {
79 Node* node = m_map.get(existingValue);
80 ASSERT(node);
81 node->append(newNode(newValue));
82 }
83
84 class iterator {
85 public:
86 iterator()
87 {
88 }
89
90 iterator(Node* node)
91 : m_node(node)
92 {
93 }
94
95 const T& operator*()
96 {
97 return m_node->payload;
98 }
99
100 iterator& operator++()
101 {
102 m_node = m_node->next();
103 return *this;
104 }
105
106 bool operator==(const iterator& other) const
107 {
108 return m_node == other.m_node;
109 }
110
111 bool operator!=(const iterator& other) const
112 {
113 return !(*this == other);
114 }
115
116 private:
117 Node* m_node { nullptr };
118 };
119
120 iterator begin() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).begin()); }
121 iterator end() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).end()); }
122
123private:
124 Node* newNode(T value)
125 {
126 Node* result = m_nodes.add();
127 result->payload = value;
128 m_map.set(value, result);
129 return result;
130 }
131
132 HashMap<T, Node*> m_map;
133 Bag<Node> m_nodes; // FIXME: We could just manually free the contents of the linked list.
134 SentinelLinkedList<Node> m_list;
135};
136
137} // namespace WTF
138
139using WTF::OrderMaker;
140