Bug #: 3831
[WebKit-https.git] / WebCore / kwq / KWQListImpl.mm
1 /*
2  * Copyright (C) 2003 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 #import "KWQListImpl.h"
27
28 #import <cstddef>
29 #import <algorithm>
30 #import <CoreFoundation/CFArray.h>
31 #import "KWQAssertions.h"
32 #import "misc/main_thread_malloc.h"
33
34 class KWQListNode
35 {
36 public:
37     KWQListNode(void *d) : data(d), next(NULL), prev(NULL) { }
38
39     MAIN_THREAD_ALLOCATED;
40
41     void *data;
42     KWQListNode *next;
43     KWQListNode *prev;
44 };
45
46
47 static KWQListNode *copyList(KWQListNode *l, KWQListNode *&tail)
48 {
49     KWQListNode *node = l;
50     KWQListNode *copyHead = NULL;
51     KWQListNode *last = NULL;
52
53     while (node != NULL) {
54         KWQListNode *copy = new KWQListNode(node->data);
55         if (last != NULL) {
56             last->next = copy;
57         } else {
58             copyHead = copy;
59         }
60
61         copy->prev = last;
62         
63         last = copy;
64         node = node->next;
65     }
66
67     tail = last;
68     return copyHead;
69 }
70
71
72 KWQListImpl::KWQListImpl(void (*deleteFunc)(void *)) :
73     head(NULL),
74     tail(NULL),
75     cur(NULL),
76     nodeCount(0),
77     deleteItem(deleteFunc),
78     iterators(NULL)
79 {
80 }
81
82 KWQListImpl::KWQListImpl(const KWQListImpl &impl) :
83     cur(NULL),
84     nodeCount(impl.nodeCount),
85     deleteItem(impl.deleteItem),
86     iterators(NULL)
87 {
88     head = copyList(impl.head, tail);
89 }
90
91 KWQListImpl::~KWQListImpl()
92 {
93     clear(false);
94     
95     KWQListIteratorImpl *next;
96     for (KWQListIteratorImpl *it = iterators; it != NULL; it = next) {
97         next = it->next;
98         it->list = NULL;
99         ASSERT(it->node == NULL);
100         it->next = NULL;
101         it->prev = NULL;
102     }
103 }
104      
105 void KWQListImpl::clear(bool deleteItems)
106 {
107     KWQListNode *next;
108     
109     for (KWQListNode *node = head; node != NULL; node = next) {
110         next = node->next;
111         if (deleteItems) {
112             deleteItem(node->data);
113         }
114         delete node;
115     }
116
117     head = NULL;
118     tail = NULL;
119     cur = NULL;
120     nodeCount = 0;
121
122     for (KWQListIteratorImpl *it = iterators; it != NULL; it = it->next) {
123         it->node = NULL;
124     }
125 }
126
127 void KWQListImpl::sort(int (*compareFunc)(void *a, void *b, void *data), void *data)
128 {
129     // no sorting for 0 or 1-element lists
130     if (nodeCount <= 1) {
131         return;
132     }
133
134     // special case for 2-element lists
135     if (nodeCount == 2) {
136         void *a = head->data;
137         void *b = head->next->data;
138         if (compareFunc(a, b, data) <= 0) {
139             return;
140         }
141         head->next->data = a;
142         head->data = b;
143         return;
144     }
145
146     // insertion sort for most common sizes
147     const uint cutoff = 32;
148     if (nodeCount <= cutoff) {
149         // Straight out of Sedgewick's Algorithms in C++.
150
151         // put all the elements into an array
152         void *a[cutoff];
153         uint i = 0;
154         for (KWQListNode *node = head; node != NULL; node = node->next) {
155             a[i++] = node->data;
156         }
157
158         // move the smallest element to the start to serve as a sentinel
159         for (i = nodeCount - 1; i > 0; i--) {
160             if (compareFunc(a[i-1], a[i], data) > 0) {
161                 void *t = a[i-1];
162                 a[i-1] = a[i];
163                 a[i] = t;
164             }
165         }
166
167         // move other items to the right and put a[i] into position
168         for (i = 2; i < nodeCount; i++) {
169             void *v = a[i];
170             uint j = i;
171             while (compareFunc(v, a[j-1], data) < 0) {
172                 a[j] = a[j-1];
173                 j--;
174             }
175             a[j] = v;
176         }
177
178         // finally, put everything back into the list
179         i = 0;
180         for (KWQListNode *node = head; node != NULL; node = node->next) {
181             node->data = a[i++];
182         }
183         return;
184     }
185
186     // CFArray sort for larger lists
187     
188     CFMutableArrayRef array = CFArrayCreateMutable(NULL, nodeCount, NULL);
189
190     for (KWQListNode *node = head; node != NULL; node = node->next) {
191         CFArrayAppendValue(array, node->data);
192     }
193
194     CFArraySortValues(array, CFRangeMake(0, nodeCount), (CFComparatorFunction) compareFunc, data);
195
196     int i = 0;
197     for (KWQListNode *node = head; node != NULL; node = node->next) {
198         node->data = const_cast<void *>(CFArrayGetValueAtIndex(array, i++));
199     }
200
201     CFRelease(array);
202 }
203
204 void *KWQListImpl::at(uint n)
205 {
206     KWQListNode *node;
207     if (n >= nodeCount - 1) {
208         node = tail;
209     } else {
210         node = head;
211         for (uint i = 0; i < n && node != NULL; i++) {
212             node = node->next;
213         }
214     }
215
216     cur = node;
217     return node ? node->data : 0;
218 }
219
220 bool KWQListImpl::insert(uint n, const void *item)
221 {
222     if (n > nodeCount) {
223         return false;
224     }
225
226     KWQListNode *node = new KWQListNode((void *)item);
227
228     if (n == 0) {
229         // inserting at head
230         node->next = head;
231         if (head != NULL) {
232             head->prev = node;
233         }
234         head = node;
235         if (tail == NULL) {
236             tail = node;
237         }
238     } else if (n == nodeCount) {
239         // inserting at tail
240         node->prev = tail;
241         if (tail != NULL) {
242             tail->next = node;
243         }
244         tail = node;
245     } else {
246         // general insertion
247         
248         // iterate to one node before the insertion point, can't be null
249         // since we know n > 0 and n < nodeCount
250         KWQListNode *prevNode = head;
251
252         for (uint i = 0; i < n - 1; i++) {
253             prevNode = prevNode->next;
254         }
255         node->prev = prevNode;
256         node->next = prevNode->next;
257         if (node->next != NULL) {
258             node->next->prev = node;
259         }
260         prevNode->next = node;
261     }
262
263     nodeCount++;
264     cur = node;
265     return true;
266 }
267
268 bool KWQListImpl::remove(bool shouldDeleteItem)
269 {
270     KWQListNode *node = cur;
271     if (node == NULL) {
272         return false;
273     }
274
275     if (node->prev == NULL) {
276         head = node->next;
277     } else {
278         node->prev->next = node->next;
279     }
280
281     if (node->next == NULL) {
282         tail = node->prev;
283     } else {
284         node->next->prev = node->prev;
285     }
286
287     if (node->next != NULL) {
288         cur = node->next;
289     } else {
290         cur = node->prev;
291     }
292
293     for (KWQListIteratorImpl *it = iterators; it != NULL; it = it->next) {
294         if (it->node == node) {
295             it->node = cur;
296         }
297     }
298
299     if (shouldDeleteItem) {
300         deleteItem(node->data);
301     }
302     delete node;
303
304     nodeCount--;
305
306     return true;
307 }
308
309 bool KWQListImpl::remove(uint n, bool deleteItem)
310 {
311     if (n >= nodeCount) {
312         return false;
313     }
314
315     at(n);
316     return remove(deleteItem);
317 }
318
319 bool KWQListImpl::removeFirst(bool deleteItem)
320 {
321     return remove(0, deleteItem);
322 }
323
324 bool KWQListImpl::removeLast(bool deleteItem)
325 {
326     return remove(nodeCount - 1, deleteItem);
327 }
328
329 bool KWQListImpl::remove(const void *item, bool deleteItem, int (*compareFunc)(void *a, void *b, void *data), void *data)
330 {
331     KWQListNode *node;
332
333     node = head;
334
335     while (node != NULL && compareFunc((void *)item, node->data, data) != 0) {
336         node = node->next;
337     }
338     
339     if (node == NULL) {
340         return false;
341     }
342
343     cur = node;
344
345     return remove(deleteItem);
346 }
347
348 bool KWQListImpl::removeRef(const void *item, bool deleteItem)
349 {
350     KWQListNode *node;
351
352     node = head;
353
354     while (node != NULL && item != node->data) {
355         node = node->next;
356     }
357     
358     if (node == NULL) {
359         return false;
360     }
361
362     cur = node;
363
364     return remove(deleteItem);
365 }
366
367 void *KWQListImpl::getFirst() const
368 {
369     return head ? head->data : 0;
370 }
371
372 void *KWQListImpl::getLast() const
373 {
374     return tail ? tail->data : 0;
375 }
376
377 void *KWQListImpl::current() const
378 {
379     if (cur != NULL) {
380         return cur->data;
381     } else {
382         return NULL;
383     }
384 }
385
386 void *KWQListImpl::first()
387 {
388     cur = head;
389     return current();
390 }
391
392 void *KWQListImpl::last()
393 {
394     cur = tail;
395     return current();
396 }
397
398 void *KWQListImpl::next()
399 {
400     if (cur != NULL) {
401         cur = cur->next;
402     }
403     return current();
404 }
405
406 void *KWQListImpl::prev()
407 {
408     if (cur != NULL) {
409         cur = cur->prev;
410     }
411     return current();
412 }
413
414 void *KWQListImpl::take(uint n)
415 {
416     void *retval = at(n);
417     remove(false);
418     return retval;
419 }
420
421 void *KWQListImpl::take()
422 {
423     void *retval = current();
424     remove(false);
425     return retval;
426 }
427
428 void KWQListImpl::append(const void *item)
429 {
430     insert(nodeCount, item);
431 }
432
433 void KWQListImpl::prepend(const void *item)
434 {
435     insert(0, item);
436 }
437
438 uint KWQListImpl::containsRef(const void *item) const
439 {
440     uint count = 0;
441     
442     for (KWQListNode *node = head; node != NULL; node = node->next) {
443         if (item == node->data) {
444             ++count;
445         }
446     }
447     
448     return count;
449 }
450
451 // Only used for KDOM::NodeImpl::compareDocumentPosition(NodeImpl *other)
452 // remove when no longer needed.
453 int KWQListImpl::findRef(const void *item)
454 {
455     KWQListNode *node = head;
456     int index = 0;
457     
458     while (node != NULL && item != node->data) {
459         node = node->next;
460         index++;
461     }
462     
463     cur = node;
464     
465     if (node == NULL) {
466         return -1;
467     }
468     
469     return index;
470 }
471
472 KWQListImpl &KWQListImpl::assign(const KWQListImpl &impl, bool deleteItems)
473 {
474     clear(deleteItems);
475     KWQListImpl(impl).swap(*this);
476     return *this;
477 }
478
479 void KWQListImpl::addIterator(KWQListIteratorImpl *iter) const
480 {
481     iter->next = iterators;
482     iter->prev = NULL;
483     
484     if (iterators != NULL) {
485         iterators->prev = iter;
486     }
487     iterators = iter;
488 }
489
490 void KWQListImpl::removeIterator(KWQListIteratorImpl *iter) const
491 {
492     if (iter->prev == NULL) {
493         iterators = iter->next;
494     } else {
495         iter->prev->next = iter->next;
496     }
497
498     if (iter->next != NULL) {
499         iter->next->prev = iter->prev;
500     }
501 }
502
503 void KWQListImpl::swap(KWQListImpl &other)
504 {
505     using std::swap;
506     
507     ASSERT(iterators == NULL);
508     ASSERT(other.iterators == NULL);
509     
510     swap(head, other.head);
511     swap(tail, other.tail);
512     swap(cur, other.cur);
513     swap(nodeCount, other.nodeCount);
514     swap(deleteItem, other.deleteItem);
515 }
516
517
518 KWQListIteratorImpl::KWQListIteratorImpl() :
519     list(NULL),
520     node(NULL)
521 {
522 }
523
524 KWQListIteratorImpl::KWQListIteratorImpl(const KWQListImpl &impl)  :
525     list(&impl),
526     node(impl.head)
527 {
528     impl.addIterator(this);
529 }
530
531 KWQListIteratorImpl::~KWQListIteratorImpl()
532 {
533     if (list != NULL) {
534         list->removeIterator(this);
535     }
536 }
537
538 KWQListIteratorImpl::KWQListIteratorImpl(const KWQListIteratorImpl &impl) :
539     list(impl.list),
540     node(impl.node)
541 {
542     if (list != NULL) {
543         list->addIterator(this);
544     }
545 }
546
547 uint KWQListIteratorImpl::count() const
548 {
549     return list == NULL ? 0 : list->count();
550 }
551
552 void *KWQListIteratorImpl::toFirst()
553 {
554     if (list != NULL) {
555         node = list->head;
556     }
557     return current();
558 }
559
560 void *KWQListIteratorImpl::toLast()
561 {
562     if (list != NULL) {
563         node = list->tail;
564     }
565     return current();
566 }
567
568 void *KWQListIteratorImpl::current() const
569 {
570     return node == NULL ? NULL : node->data;
571 }
572
573 void *KWQListIteratorImpl::operator--()
574 {
575     if (node != NULL) {
576         node = node->prev;
577     }
578     return current();
579 }
580
581 void *KWQListIteratorImpl::operator++()
582 {
583     if (node != NULL) {
584         node = node->next;
585     }
586     return current();
587 }
588
589 KWQListIteratorImpl &KWQListIteratorImpl::operator=(const KWQListIteratorImpl &impl)
590 {
591     if (list != NULL) {
592         list->removeIterator(this);
593     }
594     
595     list = impl.list;
596     node = impl.node;
597     
598     if (list != NULL) {
599         list->addIterator(this);
600     }
601
602     return *this;
603 }