1 /*
2 * Copyright (C) 2003, 2006 Apple Computer, 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 COMPUTER, 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 COMPUTER, 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 #include "config.h"
27 #include "DeprecatedPtrListImpl.h"
28
29 #include <cstddef>
30 #include <algorithm>
31 #include <wtf/Assertions.h>
32
33 namespace WebCore {
34
35 class DeprecatedListNode
36 {
37 public:
DeprecatedListNode(void * d)38 DeprecatedListNode(void *d) : data(d), next(0), prev(0) { }
39
40 void *data;
41 DeprecatedListNode *next;
42 DeprecatedListNode *prev;
43 };
44
45
copyList(DeprecatedListNode * l,DeprecatedListNode * & tail)46 static DeprecatedListNode *copyList(DeprecatedListNode *l, DeprecatedListNode *&tail)
47 {
48 DeprecatedListNode *node = l;
49 DeprecatedListNode *copyHead = 0;
50 DeprecatedListNode *last = 0;
51
52 while (node != 0) {
53 DeprecatedListNode *copy = new DeprecatedListNode(node->data);
54 if (last != 0) {
55 last->next = copy;
56 } else {
57 copyHead = copy;
58 }
59
60 copy->prev = last;
61
62 last = copy;
63 node = node->next;
64 }
65
66 tail = last;
67 return copyHead;
68 }
69
70
DeprecatedPtrListImpl(void (* deleteFunc)(void *))71 DeprecatedPtrListImpl::DeprecatedPtrListImpl(void (*deleteFunc)(void *)) :
72 head(0),
73 tail(0),
74 cur(0),
75 nodeCount(0),
76 deleteItem(deleteFunc),
77 iterators(0)
78 {
79 }
80
DeprecatedPtrListImpl(const DeprecatedPtrListImpl & impl)81 DeprecatedPtrListImpl::DeprecatedPtrListImpl(const DeprecatedPtrListImpl &impl) :
82 cur(0),
83 nodeCount(impl.nodeCount),
84 deleteItem(impl.deleteItem),
85 iterators(0)
86 {
87 head = copyList(impl.head, tail);
88 }
89
~DeprecatedPtrListImpl()90 DeprecatedPtrListImpl::~DeprecatedPtrListImpl()
91 {
92 clear(false);
93
94 DeprecatedPtrListImplIterator *next;
95 for (DeprecatedPtrListImplIterator *it = iterators; it; it = next) {
96 next = it->next;
97 it->list = 0;
98 ASSERT(!it->node);
99 it->next = 0;
100 it->prev = 0;
101 }
102 }
103
clear(bool deleteItems)104 void DeprecatedPtrListImpl::clear(bool deleteItems)
105 {
106 DeprecatedListNode *next;
107
108 for (DeprecatedListNode *node = head; node; node = next) {
109 next = node->next;
110 if (deleteItems)
111 deleteItem(node->data);
112 delete node;
113 }
114
115 head = 0;
116 tail = 0;
117 cur = 0;
118 nodeCount = 0;
119
120 for (DeprecatedPtrListImplIterator *it = iterators; it; it = it->next)
121 it->node = 0;
122 }
123
at(unsigned n)124 void *DeprecatedPtrListImpl::at(unsigned n)
125 {
126 DeprecatedListNode *node;
127 if (n >= nodeCount - 1) {
128 node = tail;
129 } else {
130 node = head;
131 for (unsigned i = 0; i < n && node; i++) {
132 node = node->next;
133 }
134 }
135
136 cur = node;
137 return node ? node->data : 0;
138 }
139
insert(unsigned n,const void * item)140 bool DeprecatedPtrListImpl::insert(unsigned n, const void *item)
141 {
142 if (n > nodeCount) {
143 return false;
144 }
145
146 DeprecatedListNode *node = new DeprecatedListNode(const_cast<void*>(item));
147
148 if (n == 0) {
149 // inserting at head
150 node->next = head;
151 if (head) {
152 head->prev = node;
153 }
154 head = node;
155 if (tail == 0) {
156 tail = node;
157 }
158 } else if (n == nodeCount) {
159 // inserting at tail
160 node->prev = tail;
161 if (tail) {
162 tail->next = node;
163 }
164 tail = node;
165 } else {
166 // general insertion
167
168 // iterate to one node before the insertion point, can't be null
169 // since we know n > 0 and n < nodeCount
170 DeprecatedListNode *prevNode = head;
171
172 for (unsigned i = 0; i < n - 1; i++) {
173 prevNode = prevNode->next;
174 }
175 node->prev = prevNode;
176 node->next = prevNode->next;
177 if (node->next) {
178 node->next->prev = node;
179 }
180 prevNode->next = node;
181 }
182
183 nodeCount++;
184 cur = node;
185 return true;
186 }
187
remove(bool shouldDeleteItem)188 bool DeprecatedPtrListImpl::remove(bool shouldDeleteItem)
189 {
190 DeprecatedListNode *node = cur;
191 if (node == 0) {
192 return false;
193 }
194
195 if (node->prev == 0) {
196 head = node->next;
197 } else {
198 node->prev->next = node->next;
199 }
200
201 if (node->next == 0) {
202 tail = node->prev;
203 } else {
204 node->next->prev = node->prev;
205 }
206
207 if (node->next) {
208 cur = node->next;
209 } else {
210 cur = node->prev;
211 }
212
213 for (DeprecatedPtrListImplIterator *it = iterators; it; it = it->next) {
214 if (it->node == node) {
215 it->node = cur;
216 }
217 }
218
219 if (shouldDeleteItem) {
220 deleteItem(node->data);
221 }
222 delete node;
223
224 nodeCount--;
225
226 return true;
227 }
228
remove(unsigned n,bool deleteItem)229 bool DeprecatedPtrListImpl::remove(unsigned n, bool deleteItem)
230 {
231 if (n >= nodeCount) {
232 return false;
233 }
234
235 at(n);
236 return remove(deleteItem);
237 }
238
removeFirst(bool deleteItem)239 bool DeprecatedPtrListImpl::removeFirst(bool deleteItem)
240 {
241 return remove(0, deleteItem);
242 }
243
removeLast(bool deleteItem)244 bool DeprecatedPtrListImpl::removeLast(bool deleteItem)
245 {
246 return remove(nodeCount - 1, deleteItem);
247 }
248
removeRef(const void * item,bool deleteItem)249 bool DeprecatedPtrListImpl::removeRef(const void *item, bool deleteItem)
250 {
251 DeprecatedListNode *node;
252
253 node = head;
254
255 while (node && item != node->data) {
256 node = node->next;
257 }
258
259 if (node == 0) {
260 return false;
261 }
262
263 cur = node;
264
265 return remove(deleteItem);
266 }
267
getFirst() const268 void *DeprecatedPtrListImpl::getFirst() const
269 {
270 return head ? head->data : 0;
271 }
272
getLast() const273 void *DeprecatedPtrListImpl::getLast() const
274 {
275 return tail ? tail->data : 0;
276 }
277
getNext() const278 void *DeprecatedPtrListImpl::getNext() const
279 {
280 return cur && cur->next ? cur->next->data : 0;
281 }
282
getPrev() const283 void *DeprecatedPtrListImpl::getPrev() const
284 {
285 return cur && cur->prev ? cur->prev->data : 0;
286 }
287
current() const288 void *DeprecatedPtrListImpl::current() const
289 {
290 if (cur) {
291 return cur->data;
292 } else {
293 return 0;
294 }
295 }
296
first()297 void *DeprecatedPtrListImpl::first()
298 {
299 cur = head;
300 return current();
301 }
302
last()303 void *DeprecatedPtrListImpl::last()
304 {
305 cur = tail;
306 return current();
307 }
308
next()309 void *DeprecatedPtrListImpl::next()
310 {
311 if (cur) {
312 cur = cur->next;
313 }
314 return current();
315 }
316
prev()317 void *DeprecatedPtrListImpl::prev()
318 {
319 if (cur) {
320 cur = cur->prev;
321 }
322 return current();
323 }
324
take(unsigned n)325 void *DeprecatedPtrListImpl::take(unsigned n)
326 {
327 void *retval = at(n);
328 remove(false);
329 return retval;
330 }
331
take()332 void *DeprecatedPtrListImpl::take()
333 {
334 void *retval = current();
335 remove(false);
336 return retval;
337 }
338
append(const void * item)339 void DeprecatedPtrListImpl::append(const void *item)
340 {
341 insert(nodeCount, item);
342 }
343
prepend(const void * item)344 void DeprecatedPtrListImpl::prepend(const void *item)
345 {
346 insert(0, item);
347 }
348
containsRef(const void * item) const349 unsigned DeprecatedPtrListImpl::containsRef(const void *item) const
350 {
351 unsigned count = 0;
352
353 for (DeprecatedListNode *node = head; node; node = node->next) {
354 if (item == node->data) {
355 ++count;
356 }
357 }
358
359 return count;
360 }
361
findRef(const void * item)362 int DeprecatedPtrListImpl::findRef(const void *item)
363 {
364 DeprecatedListNode *node = head;
365 int index = 0;
366
367 while (node && item != node->data) {
368 node = node->next;
369 index++;
370 }
371
372 cur = node;
373
374 if (node == 0) {
375 return -1;
376 }
377
378 return index;
379 }
380
assign(const DeprecatedPtrListImpl & impl,bool deleteItems)381 DeprecatedPtrListImpl &DeprecatedPtrListImpl::assign(const DeprecatedPtrListImpl &impl, bool deleteItems)
382 {
383 clear(deleteItems);
384 DeprecatedPtrListImpl(impl).swap(*this);
385 return *this;
386 }
387
addIterator(DeprecatedPtrListImplIterator * iter) const388 void DeprecatedPtrListImpl::addIterator(DeprecatedPtrListImplIterator *iter) const
389 {
390 iter->next = iterators;
391 iter->prev = 0;
392
393 if (iterators) {
394 iterators->prev = iter;
395 }
396 iterators = iter;
397 }
398
removeIterator(DeprecatedPtrListImplIterator * iter) const399 void DeprecatedPtrListImpl::removeIterator(DeprecatedPtrListImplIterator *iter) const
400 {
401 if (iter->prev == 0) {
402 iterators = iter->next;
403 } else {
404 iter->prev->next = iter->next;
405 }
406
407 if (iter->next) {
408 iter->next->prev = iter->prev;
409 }
410 }
411
swap(DeprecatedPtrListImpl & other)412 void DeprecatedPtrListImpl::swap(DeprecatedPtrListImpl &other)
413 {
414 using std::swap;
415
416 ASSERT(iterators == 0);
417 ASSERT(other.iterators == 0);
418
419 swap(head, other.head);
420 swap(tail, other.tail);
421 swap(cur, other.cur);
422 swap(nodeCount, other.nodeCount);
423 swap(deleteItem, other.deleteItem);
424 }
425
426
DeprecatedPtrListImplIterator()427 DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator() :
428 list(0),
429 node(0)
430 {
431 }
432
DeprecatedPtrListImplIterator(const DeprecatedPtrListImpl & impl)433 DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator(const DeprecatedPtrListImpl &impl) :
434 list(&impl),
435 node(impl.head)
436 {
437 impl.addIterator(this);
438 }
439
~DeprecatedPtrListImplIterator()440 DeprecatedPtrListImplIterator::~DeprecatedPtrListImplIterator()
441 {
442 if (list) {
443 list->removeIterator(this);
444 }
445 }
446
DeprecatedPtrListImplIterator(const DeprecatedPtrListImplIterator & impl)447 DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator(const DeprecatedPtrListImplIterator &impl) :
448 list(impl.list),
449 node(impl.node)
450 {
451 if (list) {
452 list->addIterator(this);
453 }
454 }
455
count() const456 unsigned DeprecatedPtrListImplIterator::count() const
457 {
458 return list == 0 ? 0 : list->count();
459 }
460
toFirst()461 void *DeprecatedPtrListImplIterator::toFirst()
462 {
463 if (list) {
464 node = list->head;
465 }
466 return current();
467 }
468
toLast()469 void *DeprecatedPtrListImplIterator::toLast()
470 {
471 if (list) {
472 node = list->tail;
473 }
474 return current();
475 }
476
current() const477 void *DeprecatedPtrListImplIterator::current() const
478 {
479 return node == 0 ? 0 : node->data;
480 }
481
operator --()482 void *DeprecatedPtrListImplIterator::operator--()
483 {
484 if (node) {
485 node = node->prev;
486 }
487 return current();
488 }
489
operator ++()490 void *DeprecatedPtrListImplIterator::operator++()
491 {
492 if (node) {
493 node = node->next;
494 }
495 return current();
496 }
497
operator =(const DeprecatedPtrListImplIterator & impl)498 DeprecatedPtrListImplIterator &DeprecatedPtrListImplIterator::operator=(const DeprecatedPtrListImplIterator &impl)
499 {
500 if (list) {
501 list->removeIterator(this);
502 }
503
504 list = impl.list;
505 node = impl.node;
506
507 if (list) {
508 list->addIterator(this);
509 }
510
511 return *this;
512 }
513
514 }
515