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