Source/WTF/wtf/ListHashSet.h - Issue 14238015: Move Source/WTF/wtf to Source/wtf

Side by Side Diff: Source/WTF/wtf/ListHashSet.h

Issue 14238015: Move Source/WTF/wtf to Source/wtf (Closed) Base URL: svn://svn.chromium.org/blink/trunk

Patch Set: Created 7 years, 8 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch | Annotate | Revision Log

OLD	NEW
	(Empty)
1 /*

2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv ed.

3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>

4 *

5 * This library is free software; you can redistribute it and/or

6 * modify it under the terms of the GNU Library General Public

7 * License as published by the Free Software Foundation; either

8 * version 2 of the License, or (at your option) any later version.

9 *

10 * This library is distributed in the hope that it will be useful,

11 * but WITHOUT ANY WARRANTY; without even the implied warranty of

12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

13 * Library General Public License for more details.

14 *

15 * You should have received a copy of the GNU Library General Public License

16 * along with this library; see the file COPYING.LIB. If not, write to

17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

18 * Boston, MA 02110-1301, USA.

19 *

20 */

21

22 #ifndef WTF_ListHashSet_h

23 #define WTF_ListHashSet_h

24

25 #include <wtf/HashSet.h>

26 #include <wtf/OwnPtr.h>

27 #include <wtf/PassOwnPtr.h>

28

29 namespace WTF {

30

31 // ListHashSet: Just like HashSet, this class provides a Set

32 // interface - a collection of unique objects with O(1) insertion,

33 // removal and test for containership. However, it also has an

34 // order - iterating it will always give back values in the order

35 // in which they are added.

36

37 // Unlike iteration of most WTF Hash data structures, iteration is

38 // guaranteed safe against mutation of the ListHashSet, except for

39 // removal of the item currently pointed to by a given iterator.

40

41 template<typename Value, size_t inlineCapacity, typename HashFunctions> clas s ListHashSet;

42

43 template<typename Value, size_t inlineCapacity, typename HashFunctions>

44 void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions> &);

45

46 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetIterator;

47 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetConstIterator;

48 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetReverseIterator;

49 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetConstReverseIterator;

50

51 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;

52 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAll ocator;

53

54 template<typename HashArg> struct ListHashSetNodeHashFunctions;

55 template<typename HashArg> struct ListHashSetTranslator;

56

57 template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {

58 WTF_MAKE_FAST_ALLOCATED;

59 private:

60 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;

61 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator ;

62

63 typedef HashTraits<Node*> NodeTraits;

64 typedef ListHashSetNodeHashFunctions<HashArg> NodeHash;

65 typedef ListHashSetTranslator<HashArg> BaseTranslator;

66

67 typedef HashTable<Node, Node, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplType;

68 typedef HashTableIterator<Node, Node, IdentityExtractor, NodeHash, Nod eTraits, NodeTraits> ImplTypeIterator;

69 typedef HashTableConstIterator<Node, Node, IdentityExtractor, NodeHash , NodeTraits, NodeTraits> ImplTypeConstIterator;

70

71 typedef HashArg HashFunctions;

72

73 public:

74 typedef ValueArg ValueType;

75

76 typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator ;

77 typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> con st_iterator;

78 friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg >;

79

80 typedef ListHashSetReverseIterator<ValueType, inlineCapacity, HashArg> r everse_iterator;

81 typedef ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashA rg> const_reverse_iterator;

82 friend class ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg>;

83

84 typedef HashTableAddResult<iterator> AddResult;

85

86 ListHashSet();

87 ListHashSet(const ListHashSet&);

88 ListHashSet& operator=(const ListHashSet&);

89 ~ListHashSet();

90

91 void swap(ListHashSet&);

92

93 int size() const;

94 int capacity() const;

95 bool isEmpty() const;

96

97 size_t sizeInBytes() const;

98

99 iterator begin();

100 iterator end();

101 const_iterator begin() const;

102 const_iterator end() const;

103

104 reverse_iterator rbegin();

105 reverse_iterator rend();

106 const_reverse_iterator rbegin() const;

107 const_reverse_iterator rend() const;

108

109 ValueType& first();

110 const ValueType& first() const;

111 void removeFirst();

112

113 ValueType& last();

114 const ValueType& last() const;

115 void removeLast();

116

117 iterator find(const ValueType&);

118 const_iterator find(const ValueType&) const;

119 bool contains(const ValueType&) const;

120

121 // An alternate version of find() that finds the object by hashing and c omparing

122 // with some other type, to avoid the cost of type conversion.

123 // The HashTranslator interface is defined in HashSet.

124 // FIXME: We should reverse the order of the template arguments so that callers

125 // can just pass the translator let the compiler deduce T.

126 template<typename T, typename HashTranslator> iterator find(const T&);

127 template<typename T, typename HashTranslator> const_iterator find(const T&) const;

128 template<typename T, typename HashTranslator> bool contains(const T&) co nst;

129

130 // The return value of add is a pair of an iterator to the new value's l ocation,

131 // and a bool that is true if an new entry was added.

132 AddResult add(const ValueType&);

133

134 // Add the value to the end of the collection. If the value was already in

135 // the list, it is moved to the end.

136 AddResult appendOrMoveToLast(const ValueType&);

137

138 // Add the value to the beginning of the collection. If the value was al ready in

139 // the list, it is moved to the beginning.

140 AddResult prependOrMoveToFirst(const ValueType&);

141

142 AddResult insertBefore(const ValueType& beforeValue, const ValueType& ne wValue);

143 AddResult insertBefore(iterator, const ValueType&);

144

145 void remove(const ValueType&);

146 void remove(iterator);

147 void clear();

148

149 private:

150 void unlink(Node*);

151 void unlinkAndDelete(Node*);

152 void appendNode(Node*);

153 void prependNode(Node*);

154 void insertNodeBefore(Node* beforeNode, Node* newNode);

155 void deleteAllNodes();

156

157 iterator makeIterator(Node*);

158 const_iterator makeConstIterator(Node*) const;

159 reverse_iterator makeReverseIterator(Node*);

160 const_reverse_iterator makeConstReverseIterator(Node*) const;

161

162 friend void deleteAllValues<>(const ListHashSet&);

163

164 ImplType m_impl;

165 Node* m_head;

166 Node* m_tail;

167 OwnPtr<NodeAllocator> m_allocator;

168 };

169

170 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAll ocator {

171 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;

172 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator ;

173

174 ListHashSetNodeAllocator()

175 : m_freeList(pool())

176 , m_isDoneWithInitialFreeList(false)

177 {

178 memset(m_pool.pool, 0, sizeof(m_pool.pool));

179 }

180

181 Node* allocate()

182 {

183 Node* result = m_freeList;

184

185 if (!result)

186 return static_cast<Node*>(fastMalloc(sizeof(Node)));

187

188 ASSERT(!result->m_isAllocated);

189

190 Node* next = result->m_next;

191 ASSERT(!next \|\| !next->m_isAllocated);

192 if (!next && !m_isDoneWithInitialFreeList) {

193 next = result + 1;

194 if (next == pastPool()) {

195 m_isDoneWithInitialFreeList = true;

196 next = 0;

197 } else {

198 ASSERT(inPool(next));

199 ASSERT(!next->m_isAllocated);

200 }

201 }

202 m_freeList = next;

203

204 return result;

205 }

206

207 void deallocate(Node* node)

208 {

209 if (inPool(node)) {

210 #ifndef NDEBUG

211 node->m_isAllocated = false;

212 #endif

213 node->m_next = m_freeList;

214 m_freeList = node;

215 return;

216 }

217

218 fastFree(node);

219 }

220

221 bool inPool(Node* node)

222 {

223 return node >= pool() && node < pastPool();

224 }

225

226 private:

227 Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }

228 Node* pastPool() { return pool() + m_poolSize; }

229

230 Node* m_freeList;

231 bool m_isDoneWithInitialFreeList;

232 static const size_t m_poolSize = inlineCapacity;

233 union {

234 char pool[sizeof(Node) * m_poolSize];

235 double forAlignment;

236 } m_pool;

237 };

238

239 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {

240 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator ;

241

242 ListHashSetNode(ValueArg value)

243 : m_value(value)

244 , m_prev(0)

245 , m_next(0)

246 #ifndef NDEBUG

247 , m_isAllocated(true)

248 #endif

249 {

250 }

251

252 void* operator new(size_t, NodeAllocator* allocator)

253 {

254 return allocator->allocate();

255 }

256 void destroy(NodeAllocator* allocator)

257 {

258 this->~ListHashSetNode();

259 allocator->deallocate(this);

260 }

261

262 ValueArg m_value;

263 ListHashSetNode* m_prev;

264 ListHashSetNode* m_next;

265

266 #ifndef NDEBUG

267 bool m_isAllocated;

268 #endif

269 };

270

271 template<typename HashArg> struct ListHashSetNodeHashFunctions {

272 template<typename T> static unsigned hash(const T& key) { return HashArg ::hash(key->m_value); }

273 template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); }

274 static const bool safeToCompareToEmptyOrDeleted = false;

275 };

276

277 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetIterator {

278 private:

279 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;

280 typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;

281 typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> cons t_iterator;

282 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;

283 typedef ValueArg ValueType;

284 typedef ValueType& ReferenceType;

285 typedef ValueType* PointerType;

286

287 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

288

289 ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iter ator(set, position) { }

290

291 public:

292 ListHashSetIterator() { }

293

294 // default copy, assignment and destructor are OK

295

296 PointerType get() const { return const_cast<PointerType>(m_iterator.get( )); }

297 ReferenceType operator() const { return get(); }

298 PointerType operator->() const { return get(); }

299

300 iterator& operator++() { ++m_iterator; return *this; }

301

302 // postfix ++ intentionally omitted

303

304 iterator& operator--() { --m_iterator; return *this; }

305

306 // postfix -- intentionally omitted

307

308 // Comparison.

309 bool operator==(const iterator& other) const { return m_iterator == othe r.m_iterator; }

310 bool operator!=(const iterator& other) const { return m_iterator != othe r.m_iterator; }

311

312 operator const_iterator() const { return m_iterator; }

313

314 private:

315 Node* node() { return m_iterator.node(); }

316

317 const_iterator m_iterator;

318 };

319

320 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetConstIterator {

321 private:

322 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;

323 typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;

324 typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> cons t_iterator;

325 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;

326 typedef ValueArg ValueType;

327 typedef const ValueType& ReferenceType;

328 typedef const ValueType* PointerType;

329

330 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

331 friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;

332

333 ListHashSetConstIterator(const ListHashSetType* set, Node* position)

334 : m_set(set)

335 , m_position(position)

336 {

337 }

338

339 public:

340 ListHashSetConstIterator()

341 {

342 }

343

344 PointerType get() const

345 {

346 return &m_position->m_value;

347 }

348 ReferenceType operator() const { return get(); }

349 PointerType operator->() const { return get(); }

350

351 const_iterator& operator++()

352 {

353 ASSERT(m_position != 0);

354 m_position = m_position->m_next;

355 return *this;

356 }

357

358 // postfix ++ intentionally omitted

359

360 const_iterator& operator--()

361 {

362 ASSERT(m_position != m_set->m_head);

363 if (!m_position)

364 m_position = m_set->m_tail;

365 else

366 m_position = m_position->m_prev;

367 return *this;

368 }

369

370 // postfix -- intentionally omitted

371

372 // Comparison.

373 bool operator==(const const_iterator& other) const

374 {

375 return m_position == other.m_position;

376 }

377 bool operator!=(const const_iterator& other) const

378 {

379 return m_position != other.m_position;

380 }

381

382 private:

383 Node* node() { return m_position; }

384

385 const ListHashSetType* m_set;

386 Node* m_position;

387 };

388

389 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetReverseIterator {

390 private:

391 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;

392 typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> re verse_iterator;

393 typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashAr g> const_reverse_iterator;

394 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;

395 typedef ValueArg ValueType;

396 typedef ValueType& ReferenceType;

397 typedef ValueType* PointerType;

398

399 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

400

401 ListHashSetReverseIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }

402

403 public:

404 ListHashSetReverseIterator() { }

405

406 // default copy, assignment and destructor are OK

407

408 PointerType get() const { return const_cast<PointerType>(m_iterator.get( )); }

409 ReferenceType operator() const { return get(); }

410 PointerType operator->() const { return get(); }

411

412 reverse_iterator& operator++() { ++m_iterator; return *this; }

413

414 // postfix ++ intentionally omitted

415

416 reverse_iterator& operator--() { --m_iterator; return *this; }

417

418 // postfix -- intentionally omitted

419

420 // Comparison.

421 bool operator==(const reverse_iterator& other) const { return m_iterator == other.m_iterator; }

422 bool operator!=(const reverse_iterator& other) const { return m_iterator != other.m_iterator; }

423

424 operator const_reverse_iterator() const { return m_iterator; }

425

426 private:

427 Node* node() { return m_iterator.node(); }

428

429 const_reverse_iterator m_iterator;

430 };

431

432 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class L istHashSetConstReverseIterator {

433 private:

434 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;

435 typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> re verse_iterator;

436 typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashAr g> const_reverse_iterator;

437 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;

438 typedef ValueArg ValueType;

439 typedef const ValueType& ReferenceType;

440 typedef const ValueType* PointerType;

441

442 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

443 friend class ListHashSetReverseIterator<ValueArg, inlineCapacity, HashAr g>;

444

445 ListHashSetConstReverseIterator(const ListHashSetType* set, Node* positi on)

446 : m_set(set)

447 , m_position(position)

448 {

449 }

450

451 public:

452 ListHashSetConstReverseIterator()

453 {

454 }

455

456 PointerType get() const

457 {

458 return &m_position->m_value;

459 }

460 ReferenceType operator() const { return get(); }

461 PointerType operator->() const { return get(); }

462

463 const_reverse_iterator& operator++()

464 {

465 ASSERT(m_position != 0);

466 m_position = m_position->m_prev;

467 return *this;

468 }

469

470 // postfix ++ intentionally omitted

471

472 const_reverse_iterator& operator--()

473 {

474 ASSERT(m_position != m_set->m_tail);

475 if (!m_position)

476 m_position = m_set->m_head;

477 else

478 m_position = m_position->m_next;

479 return *this;

480 }

481

482 // postfix -- intentionally omitted

483

484 // Comparison.

485 bool operator==(const const_reverse_iterator& other) const

486 {

487 return m_position == other.m_position;

488 }

489 bool operator!=(const const_reverse_iterator& other) const

490 {

491 return m_position != other.m_position;

492 }

493

494 private:

495 Node* node() { return m_position; }

496

497 const ListHashSetType* m_set;

498 Node* m_position;

499 };

500

501 template<typename HashFunctions>

502 struct ListHashSetTranslator {

503 template<typename T> static unsigned hash(const T& key) { return HashFun ctions::hash(key); }

504 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); }

505 template<typename T, typename U, typename V> static void translate(T*& l ocation, const U& key, const V& allocator)

506 {

507 location = new (allocator) T(key);

508 }

509 };

510

511 template<typename T, size_t inlineCapacity, typename U>

512 inline ListHashSet<T, inlineCapacity, U>::ListHashSet()

513 : m_head(0)

514 , m_tail(0)

515 , m_allocator(adoptPtr(new NodeAllocator))

516 {

517 }

518

519 template<typename T, size_t inlineCapacity, typename U>

520 inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& oth er)

521 : m_head(0)

522 , m_tail(0)

523 , m_allocator(adoptPtr(new NodeAllocator))

524 {

525 const_iterator end = other.end();

526 for (const_iterator it = other.begin(); it != end; ++it)

527 add(*it);

528 }

529

530 template<typename T, size_t inlineCapacity, typename U>

531 inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>: :operator=(const ListHashSet& other)

532 {

533 ListHashSet tmp(other);

534 swap(tmp);

535 return *this;

536 }

537

538 template<typename T, size_t inlineCapacity, typename U>

539 inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)

540 {

541 m_impl.swap(other.m_impl);

542 std::swap(m_head, other.m_head);

543 std::swap(m_tail, other.m_tail);

544 m_allocator.swap(other.m_allocator);

545 }

546

547 template<typename T, size_t inlineCapacity, typename U>

548 inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()

549 {

550 deleteAllNodes();

551 }

552

553 template<typename T, size_t inlineCapacity, typename U>

554 inline int ListHashSet<T, inlineCapacity, U>::size() const

555 {

556 return m_impl.size();

557 }

558

559 template<typename T, size_t inlineCapacity, typename U>

560 inline int ListHashSet<T, inlineCapacity, U>::capacity() const

561 {

562 return m_impl.capacity();

563 }

564

565 template<typename T, size_t inlineCapacity, typename U>

566 inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const

567 {

568 return m_impl.isEmpty();

569 }

570

571 template<typename T, size_t inlineCapacity, typename U>

572 size_t ListHashSet<T, inlineCapacity, U>::sizeInBytes() const

573 {

574 size_t result = sizeof(this) + sizeof(m_allocator);

575 result += sizeof(typename ImplType::ValueType) * m_impl.capacity();

576 for (Node* node = m_head; node; node = node->m_next) {

577 if (!m_allocator->inPool(node))

578 result += sizeof(Node);

579 }

580 return result;

581 }

582

583 template<typename T, size_t inlineCapacity, typename U>

584 inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, i nlineCapacity, U>::begin()

585 {

586 return makeIterator(m_head);

587 }

588

589 template<typename T, size_t inlineCapacity, typename U>

590 inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, i nlineCapacity, U>::end()

591 {

592 return makeIterator(0);

593 }

594

595 template<typename T, size_t inlineCapacity, typename U>

596 inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSe t<T, inlineCapacity, U>::begin() const

597 {

598 return makeConstIterator(m_head);

599 }

600

601 template<typename T, size_t inlineCapacity, typename U>

602 inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSe t<T, inlineCapacity, U>::end() const

603 {

604 return makeConstIterator(0);

605 }

606

607 template<typename T, size_t inlineCapacity, typename U>

608 inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHash Set<T, inlineCapacity, U>::rbegin()

609 {

610 return makeReverseIterator(m_tail);

611 }

612

613 template<typename T, size_t inlineCapacity, typename U>

614 inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHash Set<T, inlineCapacity, U>::rend()

615 {

616 return makeReverseIterator(0);

617 }

618

619 template<typename T, size_t inlineCapacity, typename U>

620 inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator Li stHashSet<T, inlineCapacity, U>::rbegin() const

621 {

622 return makeConstReverseIterator(m_tail);

623 }

624

625 template<typename T, size_t inlineCapacity, typename U>

626 inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator Li stHashSet<T, inlineCapacity, U>::rend() const

627 {

628 return makeConstReverseIterator(0);

629 }

630

631 template<typename T, size_t inlineCapacity, typename U>

632 inline T& ListHashSet<T, inlineCapacity, U>::first()

633 {

634 ASSERT(!isEmpty());

635 return m_head->m_value;

636 }

637

638 template<typename T, size_t inlineCapacity, typename U>

639 inline void ListHashSet<T, inlineCapacity, U>::removeFirst()

640 {

641 ASSERT(!isEmpty());

642 m_impl.remove(m_head);

643 unlinkAndDelete(m_head);

644 }

645

646 template<typename T, size_t inlineCapacity, typename U>

647 inline const T& ListHashSet<T, inlineCapacity, U>::first() const

648 {

649 ASSERT(!isEmpty());

650 return m_head->m_value;

651 }

652

653 template<typename T, size_t inlineCapacity, typename U>

654 inline T& ListHashSet<T, inlineCapacity, U>::last()

655 {

656 ASSERT(!isEmpty());

657 return m_tail->m_value;

658 }

659

660 template<typename T, size_t inlineCapacity, typename U>

661 inline const T& ListHashSet<T, inlineCapacity, U>::last() const

662 {

663 ASSERT(!isEmpty());

664 return m_tail->m_value;

665 }

666

667 template<typename T, size_t inlineCapacity, typename U>

668 inline void ListHashSet<T, inlineCapacity, U>::removeLast()

669 {

670 ASSERT(!isEmpty());

671 m_impl.remove(m_tail);

672 unlinkAndDelete(m_tail);

673 }

674

675 template<typename T, size_t inlineCapacity, typename U>

676 inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, i nlineCapacity, U>::find(const ValueType& value)

677 {

678 ImplTypeIterator it = m_impl.template find<BaseTranslator>(value);

679 if (it == m_impl.end())

680 return end();

681 return makeIterator(*it);

682 }

683

684 template<typename T, size_t inlineCapacity, typename U>

685 inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSe t<T, inlineCapacity, U>::find(const ValueType& value) const

686 {

687 ImplTypeConstIterator it = m_impl.template find<BaseTranslator>(value);

688 if (it == m_impl.end())

689 return end();

690 return makeConstIterator(*it);

691 }

692

693 template<typename Translator>

694 struct ListHashSetTranslatorAdapter {

695 template<typename T> static unsigned hash(const T& key) { return Transla tor::hash(key); }

696 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }

697 };

698

699 template<typename ValueType, size_t inlineCapacity, typename U>

700 template<typename T, typename HashTranslator>

701 inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHash Set<ValueType, inlineCapacity, U>::find(const T& value)

702 {

703 ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAda pter<HashTranslator> >(value);

704 if (it == m_impl.end())

705 return end();

706 return makeIterator(*it);

707 }

708

709 template<typename ValueType, size_t inlineCapacity, typename U>

710 template<typename T, typename HashTranslator>

711 inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator Li stHashSet<ValueType, inlineCapacity, U>::find(const T& value) const

712 {

713 ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAda pter<HashTranslator> >(value);

714 if (it == m_impl.end())

715 return end();

716 return makeConstIterator(*it);

717 }

718

719 template<typename ValueType, size_t inlineCapacity, typename U>

720 template<typename T, typename HashTranslator>

721 inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& val ue) const

722 {

723 return m_impl.template contains<ListHashSetTranslatorAdapter<HashTransla tor> >(value);

724 }

725

726 template<typename T, size_t inlineCapacity, typename U>

727 inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& val ue) const

728 {

729 return m_impl.template contains<BaseTranslator>(value);

730 }

731

732 template<typename T, size_t inlineCapacity, typename U>

733 typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineC apacity, U>::add(const ValueType &value)

734 {

735 typename ImplType::AddResult result = m_impl.template add<BaseTranslator >(value, m_allocator.get());

736 if (result.isNewEntry)

737 appendNode(*result.iterator);

738 return AddResult(makeIterator(*result.iterator), result.isNewEntry);

739 }

740

741 template<typename T, size_t inlineCapacity, typename U>

742 typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineC apacity, U>::appendOrMoveToLast(const ValueType &value)

743 {

744 typename ImplType::AddResult result = m_impl.template add<BaseTranslator >(value, m_allocator.get());

745 Node* node = *result.iterator;

746 if (!result.isNewEntry)

747 unlink(node);

748 appendNode(node);

749 return AddResult(makeIterator(*result.iterator), result.isNewEntry);

750 }

751

752 template<typename T, size_t inlineCapacity, typename U>

753 typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineC apacity, U>::prependOrMoveToFirst(const ValueType &value)

754 {

755 typename ImplType::AddResult result = m_impl.template add<BaseTranslator >(value, m_allocator.get());

756 Node* node = *result.iterator;

757 if (!result.isNewEntry)

758 unlink(node);

759 prependNode(node);

760 return AddResult(makeIterator(*result.iterator), result.isNewEntry);

761 }

762

763 template<typename T, size_t inlineCapacity, typename U>

764 typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineC apacity, U>::insertBefore(iterator it, const ValueType& newValue)

765 {

766 typename ImplType::AddResult result = m_impl.template add<BaseTranslator >(newValue, m_allocator.get());

767 if (result.isNewEntry)

768 insertNodeBefore(it.node(), *result.iterator);

769 return AddResult(makeIterator(*result.iterator), result.isNewEntry);

770 }

771

772 template<typename T, size_t inlineCapacity, typename U>

773 typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineC apacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValu e)

774 {

775 return insertBefore(find(beforeValue), newValue);

776 }

777

778 template<typename T, size_t inlineCapacity, typename U>

779 inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it)

780 {

781 if (it == end())

782 return;

783 m_impl.remove(it.node());

784 unlinkAndDelete(it.node());

785 }

786

787 template<typename T, size_t inlineCapacity, typename U>

788 inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value )

789 {

790 remove(find(value));

791 }

792

793 template<typename T, size_t inlineCapacity, typename U>

794 inline void ListHashSet<T, inlineCapacity, U>::clear()

795 {

796 deleteAllNodes();

797 m_impl.clear();

798 m_head = 0;

799 m_tail = 0;

800 }

801

802 template<typename T, size_t inlineCapacity, typename U>

803 void ListHashSet<T, inlineCapacity, U>::unlink(Node* node)

804 {

805 if (!node->m_prev) {

806 ASSERT(node == m_head);

807 m_head = node->m_next;

808 } else {

809 ASSERT(node != m_head);

810 node->m_prev->m_next = node->m_next;

811 }

812

813 if (!node->m_next) {

814 ASSERT(node == m_tail);

815 m_tail = node->m_prev;

816 } else {

817 ASSERT(node != m_tail);

818 node->m_next->m_prev = node->m_prev;

819 }

820 }

821

822 template<typename T, size_t inlineCapacity, typename U>

823 void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)

824 {

825 unlink(node);

826 node->destroy(m_allocator.get());

827 }

828

829 template<typename T, size_t inlineCapacity, typename U>

830 void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)

831 {

832 node->m_prev = m_tail;

833 node->m_next = 0;

834

835 if (m_tail) {

836 ASSERT(m_head);

837 m_tail->m_next = node;

838 } else {

839 ASSERT(!m_head);

840 m_head = node;

841 }

842

843 m_tail = node;

844 }

845

846 template<typename T, size_t inlineCapacity, typename U>

847 void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node)

848 {

849 node->m_prev = 0;

850 node->m_next = m_head;

851

852 if (m_head)

853 m_head->m_prev = node;

854 else

855 m_tail = node;

856

857 m_head = node;

858 }

859

860 template<typename T, size_t inlineCapacity, typename U>

861 void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, N ode* newNode)

862 {

863 if (!beforeNode)

864 return appendNode(newNode);

865

866 newNode->m_next = beforeNode;

867 newNode->m_prev = beforeNode->m_prev;

868 if (beforeNode->m_prev)

869 beforeNode->m_prev->m_next = newNode;

870 beforeNode->m_prev = newNode;

871

872 if (!newNode->m_prev)

873 m_head = newNode;

874 }

875

876 template<typename T, size_t inlineCapacity, typename U>

877 void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()

878 {

879 if (!m_head)

880 return;

881

882 for (Node* node = m_head, *next = m_head->m_next; node; node = next, nex t = node ? node->m_next : 0)

883 node->destroy(m_allocator.get());

884 }

885

886 template<typename T, size_t inlineCapacity, typename U>

887 inline ListHashSetReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlin eCapacity, U>::makeReverseIterator(Node* position)

888 {

889 return ListHashSetReverseIterator<T, inlineCapacity, U>(this, position);

890 }

891

892 template<typename T, size_t inlineCapacity, typename U>

893 inline ListHashSetConstReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstReverseIterator(Node* position) const

894 {

895 return ListHashSetConstReverseIterator<T, inlineCapacity, U>(this, posit ion);

896 }

897

898 template<typename T, size_t inlineCapacity, typename U>

899 inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapaci ty, U>::makeIterator(Node* position)

900 {

901 return ListHashSetIterator<T, inlineCapacity, U>(this, position);

902 }

903

904 template<typename T, size_t inlineCapacity, typename U>

905 inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineC apacity, U>::makeConstIterator(Node* position) const

906 {

907 return ListHashSetConstIterator<T, inlineCapacity, U>(this, position);

908 }

909 template<bool, typename ValueType, typename HashTableType>

910 void deleteAllValues(HashTableType& collection)

911 {

912 typedef typename HashTableType::const_iterator iterator;

913 iterator end = collection.end();

914 for (iterator it = collection.begin(); it != end; ++it)

915 delete (*it)->m_value;

916 }

917

918 template<typename T, size_t inlineCapacity, typename U>

919 inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collect ion)

920 {

921 deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueT ype>(collection.m_impl);

922 }

923

924 } // namespace WTF

925

926 using WTF::ListHashSet;

927

928 #endif /* WTF_ListHashSet_h */

OLD	NEW

« no previous file with comments | « Source/WTF/wtf/IntegralTypedArrayBase.h ('k') | Source/WTF/wtf/ListRefPtr.h » ('j') | Source/config.h » ('J')