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
fragment(uint index)101 inline Fragment *fragment(uint index) {
102 return (fragments + index);
103 }
fragment(uint index)104 inline const Fragment *fragment(uint index) const {
105 return (fragments + index);
106 }
107
108
F(uint index)109 inline Fragment &F(uint index) { return fragments[index] ; }
F(uint index)110 inline const Fragment &F(uint index) const { return fragments[index] ; }
111
isRoot(uint index)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
minimum(uint n)172 uint minimum(uint n) const {
173 while (n && fragment(n)->left)
174 n = fragment(n)->left;
175 return n;
176 }
177
maximum(uint n)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
root()187 inline uint root() const {
188 Q_ASSERT(!head->root || !fragment(head->root)->parent);
189 return head->root;
190 }
setRoot(uint new_root)191 inline void setRoot(uint new_root) {
192 Q_ASSERT(!head->root || !fragment(new_root)->parent);
193 head->root = new_root;
194 }
195
isValid(uint n)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>
QFragmentMapData()218 QFragmentMapData<Fragment>::QFragmentMapData()
219 : fragments(nullptr)
220 {
221 init();
222 }
223
224 template <class Fragment>
init()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>
~QFragmentMapData()245 QFragmentMapData<Fragment>::~QFragmentMapData()
246 {
247 free(fragments);
248 }
249
250 template <class Fragment>
createFragment()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>
freeFragment(uint i)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>
next(uint n)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>
previous(uint n)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>
rotateLeft(uint x)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>
rotateRight(uint x)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>
rebalance(uint x)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>
erase_single(uint z)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>
findNode(int k,uint field)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>
insert_single(int key,uint length)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>
length(uint field)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
Iterator()729 Iterator() : pt(0), n(0) {}
Iterator(QFragmentMap * p,int node)730 Iterator(QFragmentMap *p, int node) : pt(p), n(node) {}
Iterator(const Iterator & it)731 Iterator(const Iterator& it) : pt(it.pt), n(it.n) {}
732
atEnd()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
position()744 int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); }
value()745 const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
value()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 */
ConstIterator()769 ConstIterator() : pt(0), n(0) {}
ConstIterator(const QFragmentMap * p,int node)770 ConstIterator(const QFragmentMap *p, int node) : pt(p), n(node) {}
ConstIterator(const ConstIterator & it)771 ConstIterator(const ConstIterator& it) : pt(it.pt), n(it.n) {}
ConstIterator(const Iterator & it)772 ConstIterator(const Iterator& it) : pt(it.pt), n(it.n) {}
773
atEnd()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
position()783 int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); }
size()784 int size() const { Q_ASSERT(!atEnd()); return pt->data.size(n); }
value()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
QFragmentMap()798 QFragmentMap() {}
~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
clear()807 inline void clear() {
808 for (Iterator it = begin(); !it.atEnd(); ++it)
809 it.value()->free();
810 data.init();
811 }
812
begin()813 inline Iterator begin() { return Iterator(this, data.minimum(data.root())); }
end()814 inline Iterator end() { return Iterator(this, 0); }
begin()815 inline ConstIterator begin() const { return ConstIterator(this, data.minimum(data.root())); }
end()816 inline ConstIterator end() const { return ConstIterator(this, 0); }
817
last()818 inline ConstIterator last() const { return ConstIterator(this, data.maximum(data.root())); }
819
isEmpty()820 inline bool isEmpty() const { return data.head->node_count == 0; }
numNodes()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
insert_single(int key,uint length)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 }
erase_single(uint f)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
fragment(uint index)849 inline Fragment *fragment(uint index) {
850 Q_ASSERT(index != 0);
851 return data.fragment(index);
852 }
fragment(uint index)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); }
isValid(uint n)858 inline bool isValid(uint n) const { return data.isValid(n); }
next(uint n)859 inline uint next(uint n) const { return data.next(n); }
previous(uint 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
firstNode()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