1 | /* |
---|---|

2 | * Copyright (C) 2011 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 DoublyLinkedList_h |

27 | #define DoublyLinkedList_h |

28 | |

29 | namespace WTF { |

30 | |

31 | // This class allows nodes to share code without dictating data member layout. |

32 | template<typename T> class DoublyLinkedListNode { |

33 | public: |

34 | DoublyLinkedListNode(); |

35 | |

36 | void setPrev(T*); |

37 | void setNext(T*); |

38 | |

39 | T* prev() const; |

40 | T* next() const; |

41 | }; |

42 | |

43 | template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode() |

44 | { |

45 | setPrev(0); |

46 | setNext(0); |

47 | } |

48 | |

49 | template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev) |

50 | { |

51 | static_cast<T*>(this)->m_prev = prev; |

52 | } |

53 | |

54 | template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next) |

55 | { |

56 | static_cast<T*>(this)->m_next = next; |

57 | } |

58 | |

59 | template<typename T> inline T* DoublyLinkedListNode<T>::prev() const |

60 | { |

61 | return static_cast<const T*>(this)->m_prev; |

62 | } |

63 | |

64 | template<typename T> inline T* DoublyLinkedListNode<T>::next() const |

65 | { |

66 | return static_cast<const T*>(this)->m_next; |

67 | } |

68 | |

69 | template<typename T> class DoublyLinkedList { |

70 | public: |

71 | DoublyLinkedList(); |

72 | |

73 | bool isEmpty() const; |

74 | size_t size() const; // This is O(n). |

75 | void clear(); |

76 | |

77 | T* head() const; |

78 | T* removeHead(); |

79 | |

80 | T* tail() const; |

81 | |

82 | void push(T*); |

83 | void append(T*); |

84 | void remove(T*); |

85 | void append(DoublyLinkedList<T>&); |

86 | |

87 | private: |

88 | T* m_head; |

89 | T* m_tail; |

90 | }; |

91 | |

92 | template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList() |

93 | : m_head(0) |

94 | , m_tail(0) |

95 | { |

96 | } |

97 | |

98 | template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const |

99 | { |

100 | return !m_head; |

101 | } |

102 | |

103 | template<typename T> inline size_t DoublyLinkedList<T>::size() const |

104 | { |

105 | size_t size = 0; |

106 | for (T* node = m_head; node; node = node->next()) |

107 | ++size; |

108 | return size; |

109 | } |

110 | |

111 | template<typename T> inline void DoublyLinkedList<T>::clear() |

112 | { |

113 | m_head = 0; |

114 | m_tail = 0; |

115 | } |

116 | |

117 | template<typename T> inline T* DoublyLinkedList<T>::head() const |

118 | { |

119 | return m_head; |

120 | } |

121 | |

122 | template<typename T> inline T* DoublyLinkedList<T>::tail() const |

123 | { |

124 | return m_tail; |

125 | } |

126 | |

127 | template<typename T> inline void DoublyLinkedList<T>::push(T* node) |

128 | { |

129 | if (!m_head) { |

130 | ASSERT(!m_tail); |

131 | m_head = node; |

132 | m_tail = node; |

133 | node->setPrev(0); |

134 | node->setNext(0); |

135 | return; |

136 | } |

137 | |

138 | ASSERT(m_tail); |

139 | m_head->setPrev(node); |

140 | node->setNext(m_head); |

141 | node->setPrev(0); |

142 | m_head = node; |

143 | } |

144 | |

145 | template<typename T> inline void DoublyLinkedList<T>::append(T* node) |

146 | { |

147 | if (!m_tail) { |

148 | ASSERT(!m_head); |

149 | m_head = node; |

150 | m_tail = node; |

151 | node->setPrev(0); |

152 | node->setNext(0); |

153 | return; |

154 | } |

155 | |

156 | ASSERT(m_head); |

157 | m_tail->setNext(node); |

158 | node->setPrev(m_tail); |

159 | node->setNext(0); |

160 | m_tail = node; |

161 | } |

162 | |

163 | template<typename T> inline void DoublyLinkedList<T>::remove(T* node) |

164 | { |

165 | if (node->prev()) { |

166 | ASSERT(node != m_head); |

167 | node->prev()->setNext(node->next()); |

168 | } else { |

169 | ASSERT(node == m_head); |

170 | m_head = node->next(); |

171 | } |

172 | |

173 | if (node->next()) { |

174 | ASSERT(node != m_tail); |

175 | node->next()->setPrev(node->prev()); |

176 | } else { |

177 | ASSERT(node == m_tail); |

178 | m_tail = node->prev(); |

179 | } |

180 | } |

181 | |

182 | template<typename T> inline T* DoublyLinkedList<T>::removeHead() |

183 | { |

184 | T* node = head(); |

185 | if (node) |

186 | remove(node); |

187 | return node; |

188 | } |

189 | |

190 | template<typename T> inline void DoublyLinkedList<T>::append(DoublyLinkedList<T>& other) |

191 | { |

192 | if (!other.head()) |

193 | return; |

194 | |

195 | if (!head()) { |

196 | m_head = other.head(); |

197 | m_tail = other.tail(); |

198 | other.clear(); |

199 | return; |

200 | } |

201 | |

202 | ASSERT(tail()); |

203 | ASSERT(other.head()); |

204 | T* otherHead = other.head(); |

205 | T* otherTail = other.tail(); |

206 | other.clear(); |

207 | |

208 | ASSERT(!m_tail->next()); |

209 | m_tail->setNext(otherHead); |

210 | ASSERT(!otherHead->prev()); |

211 | otherHead->setPrev(m_tail); |

212 | m_tail = otherTail; |

213 | } |

214 | |

215 | } // namespace WTF |

216 | |

217 | using WTF::DoublyLinkedListNode; |

218 | using WTF::DoublyLinkedList; |

219 | |

220 | #endif |

221 |