1 | /**************************************************************************** |
---|---|

2 | ** |

3 | ** Copyright (C) 2016 The Qt Company Ltd. |

4 | ** Contact: https://www.qt.io/licensing/ |

5 | ** |

6 | ** This file is part of the QtGui module of the Qt Toolkit. |

7 | ** |

8 | ** $QT_BEGIN_LICENSE:LGPL$ |

9 | ** Commercial License Usage |

10 | ** Licensees holding valid commercial Qt licenses may use this file in |

11 | ** accordance with the commercial license agreement provided with the |

12 | ** Software or, alternatively, in accordance with the terms contained in |

13 | ** a written agreement between you and The Qt Company. For licensing terms |

14 | ** and conditions see https://www.qt.io/terms-conditions. For further |

15 | ** information use the contact form at https://www.qt.io/contact-us. |

16 | ** |

17 | ** GNU Lesser General Public License Usage |

18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |

19 | ** General Public License version 3 as published by the Free Software |

20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |

21 | ** packaging of this file. Please review the following information to |

22 | ** ensure the GNU Lesser General Public License version 3 requirements |

23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |

24 | ** |

25 | ** GNU General Public License Usage |

26 | ** Alternatively, this file may be used under the terms of the GNU |

27 | ** General Public License version 2.0 or (at your option) the GNU General |

28 | ** Public license version 3 or any later version approved by the KDE Free |

29 | ** Qt Foundation. The licenses are as published by the Free Software |

30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |

31 | ** included in the packaging of this file. Please review the following |

32 | ** information to ensure the GNU General Public License requirements will |

33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |

34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |

35 | ** |

36 | ** $QT_END_LICENSE$ |

37 | ** |

38 | ****************************************************************************/ |

39 | |

40 | #ifndef QFRAGMENTMAP_P_H |

41 | #define QFRAGMENTMAP_P_H |

42 | |

43 | // |

44 | // W A R N I N G |

45 | // ------------- |

46 | // |

47 | // This file is not part of the Qt API. It exists purely as an |

48 | // implementation detail. This header file may change from version to |

49 | // version without notice, or even be removed. |

50 | // |

51 | // We mean it. |

52 | // |

53 | |

54 | #include <QtGui/private/qtguiglobal_p.h> |

55 | #include <stdlib.h> |

56 | #include <private/qtools_p.h> |

57 | |

58 | QT_BEGIN_NAMESPACE |

59 | |

60 | |

61 | template <int N = 1> |

62 | class QFragment |

63 | { |

64 | public: |

65 | quint32 parent; |

66 | quint32 left; |

67 | quint32 right; |

68 | quint32 color; |

69 | quint32 size_left_array[N]; |

70 | quint32 size_array[N]; |

71 | enum {size_array_max = N }; |

72 | }; |

73 | |

74 | template <class Fragment> |

75 | class QFragmentMapData |

76 | { |

77 | enum Color { Red, Black }; |

78 | public: |

79 | QFragmentMapData(); |

80 | ~QFragmentMapData(); |

81 | |

82 | void init(); |

83 | |

84 | class Header |

85 | { |

86 | public: |

87 | quint32 root; // this relies on being at the same position as parent in the fragment struct |

88 | quint32 tag; |

89 | quint32 freelist; |

90 | quint32 node_count; |

91 | quint32 allocated; |

92 | }; |

93 | |

94 | |

95 | enum {fragmentSize = sizeof(Fragment) }; |

96 | |

97 | |

98 | int length(uint field = 0) const; |

99 | |

100 | |

101 | inline Fragment *fragment(uint index) { |

102 | return (fragments + index); |

103 | } |

104 | inline const Fragment *fragment(uint index) const { |

105 | return (fragments + index); |

106 | } |

107 | |

108 | |

109 | inline Fragment &F(uint index) { return fragments[index] ; } |

110 | inline const Fragment &F(uint index) const { return fragments[index] ; } |

111 | |

112 | inline bool isRoot(uint index) const { |

113 | return !fragment(index)->parent; |

114 | } |

115 | |

116 | inline uint position(uint node, uint field = 0) const { |

117 | Q_ASSERT(field < Fragment::size_array_max); |

118 | const Fragment *f = fragment(node); |

119 | uint offset = f->size_left_array[field]; |

120 | while (f->parent) { |

121 | uint p = f->parent; |

122 | f = fragment(p); |

123 | if (f->right == node) |

124 | offset += f->size_left_array[field] + f->size_array[field]; |

125 | node = p; |

126 | } |

127 | return offset; |

128 | } |

129 | inline uint sizeRight(uint node, uint field = 0) const { |

130 | Q_ASSERT(field < Fragment::size_array_max); |

131 | uint sr = 0; |

132 | const Fragment *f = fragment(node); |

133 | node = f->right; |

134 | while (node) { |

135 | f = fragment(node); |

136 | sr += f->size_left_array[field] + f->size_array[field]; |

137 | node = f->right; |

138 | } |

139 | return sr; |

140 | } |

141 | inline uint sizeLeft(uint node, uint field = 0) const { |

142 | Q_ASSERT(field < Fragment::size_array_max); |

143 | return fragment(node)->size_left_array[field]; |

144 | } |

145 | |

146 | |

147 | inline uint size(uint node, uint field = 0) const { |

148 | Q_ASSERT(field < Fragment::size_array_max); |

149 | return fragment(node)->size_array[field]; |

150 | } |

151 | |

152 | inline void setSize(uint node, int new_size, uint field = 0) { |

153 | Q_ASSERT(field < Fragment::size_array_max); |

154 | Fragment *f = fragment(node); |

155 | int diff = new_size - f->size_array[field]; |

156 | f->size_array[field] = new_size; |

157 | while (f->parent) { |

158 | uint p = f->parent; |

159 | f = fragment(p); |

160 | if (f->left == node) |

161 | f->size_left_array[field] += diff; |

162 | node = p; |

163 | } |

164 | } |

165 | |

166 | |

167 | uint findNode(int k, uint field = 0) const; |

168 | |

169 | uint insert_single(int key, uint length); |

170 | uint erase_single(uint f); |

171 | |

172 | uint minimum(uint n) const { |

173 | while (n && fragment(n)->left) |

174 | n = fragment(n)->left; |

175 | return n; |

176 | } |

177 | |

178 | uint maximum(uint n) const { |

179 | while (n && fragment(n)->right) |

180 | n = fragment(n)->right; |

181 | return n; |

182 | } |

183 | |

184 | uint next(uint n) const; |

185 | uint previous(uint n) const; |

186 | |

187 | inline uint root() const { |

188 | Q_ASSERT(!head->root || !fragment(head->root)->parent); |

189 | return head->root; |

190 | } |

191 | inline void setRoot(uint new_root) { |

192 | Q_ASSERT(!head->root || !fragment(new_root)->parent); |

193 | head->root = new_root; |

194 | } |

195 | |

196 | inline bool isValid(uint n) const { |

197 | return n > 0 && n != head->freelist; |

198 | } |

199 | |

200 | union { |

201 | Header *head; |

202 | Fragment *fragments; |

203 | }; |

204 | |

205 | private: |

206 | |

207 | void rotateLeft(uint x); |

208 | void rotateRight(uint x); |

209 | void rebalance(uint x); |

210 | void removeAndRebalance(uint z); |

211 | |

212 | uint createFragment(); |

213 | void freeFragment(uint f); |

214 | |

215 | }; |

216 | |

217 | template <class Fragment> |

218 | QFragmentMapData<Fragment>::QFragmentMapData() |

219 | : fragments(nullptr) |

220 | { |

221 | init(); |

222 | } |

223 | |

224 | template <class Fragment> |

225 | void QFragmentMapData<Fragment>::init() |

226 | { |

227 | // the following code will realloc an existing fragment or create a new one. |

228 | // it will also ignore errors when shrinking an existing fragment. |

229 | Fragment *newFragments = (Fragment *)realloc(fragments, 64*fragmentSize); |

230 | if (newFragments) { |

231 | fragments = newFragments; |

232 | head->allocated = 64; |

233 | } |

234 | Q_CHECK_PTR(fragments); |

235 | |

236 | head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //TAG('p', 'm', 'a', 'p'); |

237 | head->root = 0; |

238 | head->freelist = 1; |

239 | head->node_count = 0; |

240 | // mark all items to the right as unused |

241 | F(head->freelist).right = 0; |

242 | } |

243 | |

244 | template <class Fragment> |

245 | QFragmentMapData<Fragment>::~QFragmentMapData() |

246 | { |

247 | free(fragments); |

248 | } |

249 | |

250 | template <class Fragment> |

251 | uint QFragmentMapData<Fragment>::createFragment() |

252 | { |

253 | Q_ASSERT(head->freelist <= head->allocated); |

254 | |

255 | uint freePos = head->freelist; |

256 | if (freePos == head->allocated) { |

257 | // need to create some free space |

258 | auto blockInfo = qCalculateGrowingBlockSize(freePos + 1, fragmentSize); |

259 | Fragment *newFragments = (Fragment *)realloc(fragments, blockInfo.size); |

260 | Q_CHECK_PTR(newFragments); |

261 | fragments = newFragments; |

262 | head->allocated = quint32(blockInfo.elementCount); |

263 | F(freePos).right = 0; |

264 | } |

265 | |

266 | uint nextPos = F(freePos).right; |

267 | if (!nextPos) { |

268 | nextPos = freePos+1; |

269 | if (nextPos < head->allocated) |

270 | F(nextPos).right = 0; |

271 | } |

272 | |

273 | head->freelist = nextPos; |

274 | |

275 | ++head->node_count; |

276 | |

277 | return freePos; |

278 | } |

279 | |

280 | template <class Fragment> |

281 | void QFragmentMapData<Fragment>::freeFragment(uint i) |

282 | { |

283 | F(i).right = head->freelist; |

284 | head->freelist = i; |

285 | |

286 | --head->node_count; |

287 | } |

288 | |

289 | |

290 | template <class Fragment> |

291 | uint QFragmentMapData<Fragment>::next(uint n) const { |

292 | Q_ASSERT(n); |

293 | if (F(n).right) { |

294 | n = F(n).right; |

295 | while (F(n).left) |

296 | n = F(n).left; |

297 | } else { |

298 | uint y = F(n).parent; |

299 | while (F(n).parent && n == F(y).right) { |

300 | n = y; |

301 | y = F(y).parent; |

302 | } |

303 | n = y; |

304 | } |

305 | return n; |

306 | } |

307 | |

308 | template <class Fragment> |

309 | uint QFragmentMapData<Fragment>::previous(uint n) const { |

310 | if (!n) |

311 | return maximum(root()); |

312 | |

313 | if (F(n).left) { |

314 | n = F(n).left; |

315 | while (F(n).right) |

316 | n = F(n).right; |

317 | } else { |

318 | uint y = F(n).parent; |

319 | while (F(n).parent && n == F(y).left) { |

320 | n = y; |

321 | y = F(y).parent; |

322 | } |

323 | n = y; |

324 | } |

325 | return n; |

326 | } |

327 | |

328 | |

329 | /* |

330 | x y |

331 | \ / \ |

332 | y --> x b |

333 | / \ \ |

334 | a b a |

335 | */ |

336 | template <class Fragment> |

337 | void QFragmentMapData<Fragment>::rotateLeft(uint x) |

338 | { |

339 | uint p = F(x).parent; |

340 | uint y = F(x).right; |

341 | |

342 | |

343 | if (y) { |

344 | F(x).right = F(y).left; |

345 | if (F(y).left) |

346 | F(F(y).left).parent = x; |

347 | F(y).left = x; |

348 | F(y).parent = p; |

349 | } else { |

350 | F(x).right = 0; |

351 | } |

352 | if (!p) { |

353 | Q_ASSERT(head->root == x); |

354 | head->root = y; |

355 | } |

356 | else if (x == F(p).left) |

357 | F(p).left = y; |

358 | else |

359 | F(p).right = y; |

360 | F(x).parent = y; |

361 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

362 | F(y).size_left_array[field] += F(x).size_left_array[field] + F(x).size_array[field]; |

363 | } |

364 | |

365 | |

366 | /* |

367 | x y |

368 | / / \ |

369 | y --> a x |

370 | / \ / |

371 | a b b |

372 | */ |

373 | template <class Fragment> |

374 | void QFragmentMapData<Fragment>::rotateRight(uint x) |

375 | { |

376 | uint y = F(x).left; |

377 | uint p = F(x).parent; |

378 | |

379 | if (y) { |

380 | F(x).left = F(y).right; |

381 | if (F(y).right) |

382 | F(F(y).right).parent = x; |

383 | F(y).right = x; |

384 | F(y).parent = p; |

385 | } else { |

386 | F(x).left = 0; |

387 | } |

388 | if (!p) { |

389 | Q_ASSERT(head->root == x); |

390 | head->root = y; |

391 | } |

392 | else if (x == F(p).right) |

393 | F(p).right = y; |

394 | else |

395 | F(p).left = y; |

396 | F(x).parent = y; |

397 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

398 | F(x).size_left_array[field] -= F(y).size_left_array[field] + F(y).size_array[field]; |

399 | } |

400 | |

401 | |

402 | template <class Fragment> |

403 | void QFragmentMapData<Fragment>::rebalance(uint x) |

404 | { |

405 | F(x).color = Red; |

406 | |

407 | while (F(x).parent && F(F(x).parent).color == Red) { |

408 | uint p = F(x).parent; |

409 | uint pp = F(p).parent; |

410 | Q_ASSERT(pp); |

411 | if (p == F(pp).left) { |

412 | uint y = F(pp).right; |

413 | if (y && F(y).color == Red) { |

414 | F(p).color = Black; |

415 | F(y).color = Black; |

416 | F(pp).color = Red; |

417 | x = pp; |

418 | } else { |

419 | if (x == F(p).right) { |

420 | x = p; |

421 | rotateLeft(x); |

422 | p = F(x).parent; |

423 | pp = F(p).parent; |

424 | } |

425 | F(p).color = Black; |

426 | if (pp) { |

427 | F(pp).color = Red; |

428 | rotateRight(pp); |

429 | } |

430 | } |

431 | } else { |

432 | uint y = F(pp).left; |

433 | if (y && F(y).color == Red) { |

434 | F(p).color = Black; |

435 | F(y).color = Black; |

436 | F(pp).color = Red; |

437 | x = pp; |

438 | } else { |

439 | if (x == F(p).left) { |

440 | x = p; |

441 | rotateRight(x); |

442 | p = F(x).parent; |

443 | pp = F(p).parent; |

444 | } |

445 | F(p).color = Black; |

446 | if (pp) { |

447 | F(pp).color = Red; |

448 | rotateLeft(pp); |

449 | } |

450 | } |

451 | } |

452 | } |

453 | F(root()).color = Black; |

454 | } |

455 | |

456 | |

457 | template <class Fragment> |

458 | uint QFragmentMapData<Fragment>::erase_single(uint z) |

459 | { |

460 | uint w = previous(z); |

461 | uint y = z; |

462 | uint x; |

463 | uint p; |

464 | |

465 | if (!F(y).left) { |

466 | x = F(y).right; |

467 | } else if (!F(y).right) { |

468 | x = F(y).left; |

469 | } else { |

470 | y = F(y).right; |

471 | while (F(y).left) |

472 | y = F(y).left; |

473 | x = F(y).right; |

474 | } |

475 | |

476 | if (y != z) { |

477 | F(F(z).left).parent = y; |

478 | F(y).left = F(z).left; |

479 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

480 | F(y).size_left_array[field] = F(z).size_left_array[field]; |

481 | if (y != F(z).right) { |

482 | /* |

483 | z y |

484 | / \ / \ |

485 | a b a b |

486 | / / |

487 | ... --> ... |

488 | / / |

489 | y x |

490 | / \ |

491 | 0 x |

492 | */ |

493 | p = F(y).parent; |

494 | if (x) |

495 | F(x).parent = p; |

496 | F(p).left = x; |

497 | F(y).right = F(z).right; |

498 | F(F(z).right).parent = y; |

499 | uint n = p; |

500 | while (n != y) { |

501 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

502 | F(n).size_left_array[field] -= F(y).size_array[field]; |

503 | n = F(n).parent; |

504 | } |

505 | } else { |

506 | /* |

507 | z y |

508 | / \ / \ |

509 | a y --> a x |

510 | / \ |

511 | 0 x |

512 | */ |

513 | p = y; |

514 | } |

515 | uint zp = F(z).parent; |

516 | if (!zp) { |

517 | Q_ASSERT(head->root == z); |

518 | head->root = y; |

519 | } else if (F(zp).left == z) { |

520 | F(zp).left = y; |

521 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

522 | F(zp).size_left_array[field] -= F(z).size_array[field]; |

523 | } else { |

524 | F(zp).right = y; |

525 | } |

526 | F(y).parent = zp; |

527 | // Swap the colors |

528 | uint c = F(y).color; |

529 | F(y).color = F(z).color; |

530 | F(z).color = c; |

531 | y = z; |

532 | } else { |

533 | /* |

534 | p p p p |

535 | / / \ \ |

536 | z --> x z --> x |

537 | | | |

538 | x x |

539 | */ |

540 | p = F(z).parent; |

541 | if (x) |

542 | F(x).parent = p; |

543 | if (!p) { |

544 | Q_ASSERT(head->root == z); |

545 | head->root = x; |

546 | } else if (F(p).left == z) { |

547 | F(p).left = x; |

548 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

549 | F(p).size_left_array[field] -= F(z).size_array[field]; |

550 | } else { |

551 | F(p).right = x; |

552 | } |

553 | } |

554 | uint n = z; |

555 | while (F(n).parent) { |

556 | uint p = F(n).parent; |

557 | if (F(p).left == n) { |

558 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

559 | F(p).size_left_array[field] -= F(z).size_array[field]; |

560 | } |

561 | n = p; |

562 | } |

563 | |

564 | freeFragment(z); |

565 | |

566 | |

567 | if (F(y).color != Red) { |

568 | while (F(x).parent && (x == 0 || F(x).color == Black)) { |

569 | if (x == F(p).left) { |

570 | uint w = F(p).right; |

571 | if (F(w).color == Red) { |

572 | F(w).color = Black; |

573 | F(p).color = Red; |

574 | rotateLeft(p); |

575 | w = F(p).right; |

576 | } |

577 | if ((F(w).left == 0 || F(F(w).left).color == Black) && |

578 | (F(w).right == 0 || F(F(w).right).color == Black)) { |

579 | F(w).color = Red; |

580 | x = p; |

581 | p = F(x).parent; |

582 | } else { |

583 | if (F(w).right == 0 || F(F(w).right).color == Black) { |

584 | if (F(w).left) |

585 | F(F(w).left).color = Black; |

586 | F(w).color = Red; |

587 | rotateRight(F(p).right); |

588 | w = F(p).right; |

589 | } |

590 | F(w).color = F(p).color; |

591 | F(p).color = Black; |

592 | if (F(w).right) |

593 | F(F(w).right).color = Black; |

594 | rotateLeft(p); |

595 | break; |

596 | } |

597 | } else { |

598 | uint w = F(p).left; |

599 | if (F(w).color == Red) { |

600 | F(w).color = Black; |

601 | F(p).color = Red; |

602 | rotateRight(p); |

603 | w = F(p).left; |

604 | } |

605 | if ((F(w).right == 0 || F(F(w).right).color == Black) && |

606 | (F(w).left == 0 || F(F(w).left).color == Black)) { |

607 | F(w).color = Red; |

608 | x = p; |

609 | p = F(x).parent; |

610 | } else { |

611 | if (F(w).left == 0 || F(F(w).left).color == Black) { |

612 | if (F(w).right) |

613 | F(F(w).right).color = Black; |

614 | F(w).color = Red; |

615 | rotateLeft(F(p).left); |

616 | w = F(p).left; |

617 | } |

618 | F(w).color = F(p).color; |

619 | F(p).color = Black; |

620 | if (F(w).left) |

621 | F(F(w).left).color = Black; |

622 | rotateRight(p); |

623 | break; |

624 | } |

625 | } |

626 | } |

627 | if (x) |

628 | F(x).color = Black; |

629 | } |

630 | |

631 | return w; |

632 | } |

633 | |

634 | template <class Fragment> |

635 | uint QFragmentMapData<Fragment>::findNode(int k, uint field) const |

636 | { |

637 | Q_ASSERT(field < Fragment::size_array_max); |

638 | uint x = root(); |

639 | |

640 | uint s = k; |

641 | while (x) { |

642 | if (sizeLeft(x, field) <= s) { |

643 | if (s < sizeLeft(x, field) + size(x, field)) |

644 | return x; |

645 | s -= sizeLeft(x, field) + size(x, field); |

646 | x = F(x).right; |

647 | } else { |

648 | x = F(x).left; |

649 | } |

650 | } |

651 | return 0; |

652 | } |

653 | |

654 | template <class Fragment> |

655 | uint QFragmentMapData<Fragment>::insert_single(int key, uint length) |

656 | { |

657 | Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key); |

658 | |

659 | uint z = createFragment(); |

660 | |

661 | F(z).left = 0; |

662 | F(z).right = 0; |

663 | F(z).size_array[0] = length; |

664 | for (uint field = 1; field < Fragment::size_array_max; ++field) |

665 | F(z).size_array[field] = 1; |

666 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

667 | F(z).size_left_array[field] = 0; |

668 | |

669 | uint y = 0; |

670 | uint x = root(); |

671 | |

672 | Q_ASSERT(!x || F(x).parent == 0); |

673 | |

674 | uint s = key; |

675 | bool right = false; |

676 | while (x) { |

677 | y = x; |

678 | if (s <= F(x).size_left_array[0]) { |

679 | x = F(x).left; |

680 | right = false; |

681 | } else { |

682 | s -= F(x).size_left_array[0] + F(x).size_array[0]; |

683 | x = F(x).right; |

684 | right = true; |

685 | } |

686 | } |

687 | |

688 | F(z).parent = y; |

689 | if (!y) { |

690 | head->root = z; |

691 | } else if (!right) { |

692 | F(y).left = z; |

693 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

694 | F(y).size_left_array[field] = F(z).size_array[field]; |

695 | } else { |

696 | F(y).right = z; |

697 | } |

698 | while (y && F(y).parent) { |

699 | uint p = F(y).parent; |

700 | if (F(p).left == y) { |

701 | for (uint field = 0; field < Fragment::size_array_max; ++field) |

702 | F(p).size_left_array[field] += F(z).size_array[field]; |

703 | } |

704 | y = p; |

705 | } |

706 | rebalance(z); |

707 | |

708 | return z; |

709 | } |

710 | |

711 | |

712 | template <class Fragment> |

713 | int QFragmentMapData<Fragment>::length(uint field) const { |

714 | uint root = this->root(); |

715 | return root ? sizeLeft(root, field) + size(root, field) + sizeRight(root, field) : 0; |

716 | } |

717 | |

718 | |

719 | template <class Fragment> // NOTE: must inherit QFragment |

720 | class QFragmentMap |

721 | { |

722 | public: |

723 | class Iterator |

724 | { |

725 | public: |

726 | QFragmentMap *pt; |

727 | quint32 n; |

728 | |

729 | Iterator() : pt(0), n(0) {} |

730 | Iterator(QFragmentMap *p, int node) : pt(p), n(node) {} |

731 | Iterator(const Iterator& it) : pt(it.pt), n(it.n) {} |

732 | |

733 | inline bool atEnd() const { return !n; } |

734 | |

735 | bool operator==(const Iterator& it) const { return pt == it.pt && n == it.n; } |

736 | bool operator!=(const Iterator& it) const { return pt != it.pt || n != it.n; } |

737 | bool operator<(const Iterator &it) const { return position() < it.position(); } |

738 | |

739 | Fragment *operator*() { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

740 | const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

741 | Fragment *operator->() { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

742 | const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

743 | |

744 | int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); } |

745 | const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

746 | Fragment *value() { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

747 | |

748 | Iterator& operator++() { |

749 | n = pt->data.next(n); |

750 | return *this; |

751 | } |

752 | Iterator& operator--() { |

753 | n = pt->data.previous(n); |

754 | return *this; |

755 | } |

756 | |

757 | }; |

758 | |

759 | |

760 | class ConstIterator |

761 | { |

762 | public: |

763 | const QFragmentMap *pt; |

764 | quint32 n; |

765 | |

766 | /** |

767 | * Functions |

768 | */ |

769 | ConstIterator() : pt(0), n(0) {} |

770 | ConstIterator(const QFragmentMap *p, int node) : pt(p), n(node) {} |

771 | ConstIterator(const ConstIterator& it) : pt(it.pt), n(it.n) {} |

772 | ConstIterator(const Iterator& it) : pt(it.pt), n(it.n) {} |

773 | |

774 | inline bool atEnd() const { return !n; } |

775 | |

776 | bool operator==(const ConstIterator& it) const { return pt == it.pt && n == it.n; } |

777 | bool operator!=(const ConstIterator& it) const { return pt != it.pt || n != it.n; } |

778 | bool operator<(const ConstIterator &it) const { return position() < it.position(); } |

779 | |

780 | const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

781 | const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

782 | |

783 | int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); } |

784 | int size() const { Q_ASSERT(!atEnd()); return pt->data.size(n); } |

785 | const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |

786 | |

787 | ConstIterator& operator++() { |

788 | n = pt->data.next(n); |

789 | return *this; |

790 | } |

791 | ConstIterator& operator--() { |

792 | n = pt->data.previous(n); |

793 | return *this; |

794 | } |

795 | }; |

796 | |

797 | |

798 | QFragmentMap() {} |

799 | ~QFragmentMap() |

800 | { |

801 | if (!data.fragments) |

802 | return; // in case of out-of-memory, we won't have fragments |

803 | for (Iterator it = begin(); !it.atEnd(); ++it) |

804 | it.value()->free(); |

805 | } |

806 | |

807 | inline void clear() { |

808 | for (Iterator it = begin(); !it.atEnd(); ++it) |

809 | it.value()->free(); |

810 | data.init(); |

811 | } |

812 | |

813 | inline Iterator begin() { return Iterator(this, data.minimum(data.root())); } |

814 | inline Iterator end() { return Iterator(this, 0); } |

815 | inline ConstIterator begin() const { return ConstIterator(this, data.minimum(data.root())); } |

816 | inline ConstIterator end() const { return ConstIterator(this, 0); } |

817 | |

818 | inline ConstIterator last() const { return ConstIterator(this, data.maximum(data.root())); } |

819 | |

820 | inline bool isEmpty() const { return data.head->node_count == 0; } |

821 | inline int numNodes() const { return data.head->node_count; } |

822 | int length(uint field = 0) const { return data.length(field); } |

823 | |

824 | Iterator find(int k, uint field = 0) { return Iterator(this, data.findNode(k, field)); } |

825 | ConstIterator find(int k, uint field = 0) const { return ConstIterator(this, data.findNode(k, field)); } |

826 | |

827 | uint findNode(int k, uint field = 0) const { return data.findNode(k, field); } |

828 | |

829 | uint insert_single(int key, uint length) |

830 | { |

831 | uint f = data.insert_single(key, length); |

832 | if (f != 0) { |

833 | Fragment *frag = fragment(f); |

834 | Q_ASSERT(frag); |

835 | frag->initialize(); |

836 | } |

837 | return f; |

838 | } |

839 | uint erase_single(uint f) |

840 | { |

841 | if (f != 0) { |

842 | Fragment *frag = fragment(f); |

843 | Q_ASSERT(frag); |

844 | frag->free(); |

845 | } |

846 | return data.erase_single(f); |

847 | } |

848 | |

849 | inline Fragment *fragment(uint index) { |

850 | Q_ASSERT(index != 0); |

851 | return data.fragment(index); |

852 | } |

853 | inline const Fragment *fragment(uint index) const { |

854 | Q_ASSERT(index != 0); |

855 | return data.fragment(index); |

856 | } |

857 | inline uint position(uint node, uint field = 0) const { return data.position(node, field); } |

858 | inline bool isValid(uint n) const { return data.isValid(n); } |

859 | inline uint next(uint n) const { return data.next(n); } |

860 | inline uint previous(uint n) const { return data.previous(n); } |

861 | inline uint size(uint node, uint field = 0) const { return data.size(node, field); } |

862 | inline void setSize(uint node, int new_size, uint field = 0) |

863 | { data.setSize(node, new_size, field); |

864 | if (node != 0 && field == 0) { |

865 | Fragment *frag = fragment(node); |

866 | Q_ASSERT(frag); |

867 | frag->invalidate(); |

868 | } |

869 | } |

870 | |

871 | inline int firstNode() const { return data.minimum(data.root()); } |

872 | |

873 | private: |

874 | friend class Iterator; |

875 | friend class ConstIterator; |

876 | |

877 | QFragmentMapData<Fragment> data; |

878 | |

879 | QFragmentMap(const QFragmentMap& m); |

880 | QFragmentMap& operator= (const QFragmentMap& m); |

881 | }; |

882 | |

883 | QT_END_NAMESPACE |

884 | |

885 | #endif // QFRAGMENTMAP_P_H |

886 |