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 }