1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QFRAGMENTMAP_P_H
5#define QFRAGMENTMAP_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtGui/private/qtguiglobal_p.h>
19#include <stdlib.h>
20#include <private/qtools_p.h>
21
22QT_BEGIN_NAMESPACE
23
24
25template <int N = 1>
26class QFragment
27{
28public:
29 quint32 parent;
30 quint32 left;
31 quint32 right;
32 quint32 color;
33 quint32 size_left_array[N];
34 quint32 size_array[N];
35 enum {size_array_max = N };
36};
37
38template <class Fragment>
39class QFragmentMapData
40{
41 enum Color { Red, Black };
42public:
43 QFragmentMapData();
44 ~QFragmentMapData();
45
46 void init();
47
48 class Header
49 {
50 public:
51 quint32 root; // this relies on being at the same position as parent in the fragment struct
52 quint32 tag;
53 quint32 freelist;
54 quint32 node_count;
55 quint32 allocated;
56 };
57
58
59 enum {fragmentSize = sizeof(Fragment) };
60
61
62 int length(uint field = 0) const;
63
64
65 inline Fragment *fragment(uint index) {
66 return (fragments + index);
67 }
68 inline const Fragment *fragment(uint index) const {
69 return (fragments + index);
70 }
71
72
73 inline Fragment &F(uint index) { return fragments[index] ; }
74 inline const Fragment &F(uint index) const { return fragments[index] ; }
75
76 inline bool isRoot(uint index) const {
77 return !fragment(index)->parent;
78 }
79
80 inline uint position(uint node, uint field = 0) const {
81 Q_ASSERT(field < Fragment::size_array_max);
82 const Fragment *f = fragment(node);
83 uint offset = f->size_left_array[field];
84 while (f->parent) {
85 uint p = f->parent;
86 f = fragment(p);
87 if (f->right == node)
88 offset += f->size_left_array[field] + f->size_array[field];
89 node = p;
90 }
91 return offset;
92 }
93 inline uint sizeRight(uint node, uint field = 0) const {
94 Q_ASSERT(field < Fragment::size_array_max);
95 uint sr = 0;
96 const Fragment *f = fragment(node);
97 node = f->right;
98 while (node) {
99 f = fragment(node);
100 sr += f->size_left_array[field] + f->size_array[field];
101 node = f->right;
102 }
103 return sr;
104 }
105 inline uint sizeLeft(uint node, uint field = 0) const {
106 Q_ASSERT(field < Fragment::size_array_max);
107 return fragment(node)->size_left_array[field];
108 }
109
110
111 inline uint size(uint node, uint field = 0) const {
112 Q_ASSERT(field < Fragment::size_array_max);
113 return fragment(node)->size_array[field];
114 }
115
116 inline void setSize(uint node, int new_size, uint field = 0) {
117 Q_ASSERT(field < Fragment::size_array_max);
118 Fragment *f = fragment(node);
119 int diff = new_size - f->size_array[field];
120 f->size_array[field] = new_size;
121 while (f->parent) {
122 uint p = f->parent;
123 f = fragment(p);
124 if (f->left == node)
125 f->size_left_array[field] += diff;
126 node = p;
127 }
128 }
129
130
131 uint findNode(int k, uint field = 0) const;
132
133 uint insert_single(int key, uint length);
134 uint erase_single(uint f);
135
136 uint minimum(uint n) const {
137 while (n && fragment(n)->left)
138 n = fragment(n)->left;
139 return n;
140 }
141
142 uint maximum(uint n) const {
143 while (n && fragment(n)->right)
144 n = fragment(n)->right;
145 return n;
146 }
147
148 uint next(uint n) const;
149 uint previous(uint n) const;
150
151 inline uint root() const {
152 Q_ASSERT(!head->root || !fragment(head->root)->parent);
153 return head->root;
154 }
155 inline void setRoot(uint new_root) {
156 Q_ASSERT(!head->root || !fragment(new_root)->parent);
157 head->root = new_root;
158 }
159
160 inline bool isValid(uint n) const {
161 return n > 0 && n != head->freelist;
162 }
163
164 union {
165 Header *head;
166 Fragment *fragments;
167 };
168
169private:
170
171 void rotateLeft(uint x);
172 void rotateRight(uint x);
173 void rebalance(uint x);
174 void removeAndRebalance(uint z);
175
176 uint createFragment();
177 void freeFragment(uint f);
178
179};
180
181template <class Fragment>
182QFragmentMapData<Fragment>::QFragmentMapData()
183 : fragments(nullptr)
184{
185 init();
186}
187
188template <class Fragment>
189void QFragmentMapData<Fragment>::init()
190{
191 // the following code will realloc an existing fragment or create a new one.
192 // it will also ignore errors when shrinking an existing fragment.
193 Fragment *newFragments = (Fragment *)realloc(fragments, 64*fragmentSize);
194 if (newFragments) {
195 fragments = newFragments;
196 head->allocated = 64;
197 }
198 Q_CHECK_PTR(fragments);
199
200 head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //TAG('p', 'm', 'a', 'p');
201 head->root = 0;
202 head->freelist = 1;
203 head->node_count = 0;
204 // mark all items to the right as unused
205 F(head->freelist).right = 0;
206}
207
208template <class Fragment>
209QFragmentMapData<Fragment>::~QFragmentMapData()
210{
211 free(fragments);
212}
213
214template <class Fragment>
215uint QFragmentMapData<Fragment>::createFragment()
216{
217 Q_ASSERT(head->freelist <= head->allocated);
218
219 uint freePos = head->freelist;
220 if (freePos == head->allocated) {
221 // need to create some free space
222 auto blockInfo = qCalculateGrowingBlockSize(freePos + 1, fragmentSize);
223 Fragment *newFragments = (Fragment *)realloc(fragments, blockInfo.size);
224 Q_CHECK_PTR(newFragments);
225 fragments = newFragments;
226 head->allocated = quint32(blockInfo.elementCount);
227 F(freePos).right = 0;
228 }
229
230 uint nextPos = F(freePos).right;
231 if (!nextPos) {
232 nextPos = freePos+1;
233 if (nextPos < head->allocated)
234 F(nextPos).right = 0;
235 }
236
237 head->freelist = nextPos;
238
239 ++head->node_count;
240
241 return freePos;
242}
243
244template <class Fragment>
245void QFragmentMapData<Fragment>::freeFragment(uint i)
246{
247 F(i).right = head->freelist;
248 head->freelist = i;
249
250 --head->node_count;
251}
252
253
254template <class Fragment>
255uint QFragmentMapData<Fragment>::next(uint n) const {
256 Q_ASSERT(n);
257 if (F(n).right) {
258 n = F(n).right;
259 while (F(n).left)
260 n = F(n).left;
261 } else {
262 uint y = F(n).parent;
263 while (F(n).parent && n == F(y).right) {
264 n = y;
265 y = F(y).parent;
266 }
267 n = y;
268 }
269 return n;
270}
271
272template <class Fragment>
273uint QFragmentMapData<Fragment>::previous(uint n) const {
274 if (!n)
275 return maximum(n: root());
276
277 if (F(n).left) {
278 n = F(n).left;
279 while (F(n).right)
280 n = F(n).right;
281 } else {
282 uint y = F(n).parent;
283 while (F(n).parent && n == F(y).left) {
284 n = y;
285 y = F(y).parent;
286 }
287 n = y;
288 }
289 return n;
290}
291
292
293/*
294 x y
295 \ / \
296 y --> x b
297 / \ \
298 a b a
299*/
300template <class Fragment>
301void QFragmentMapData<Fragment>::rotateLeft(uint x)
302{
303 uint p = F(x).parent;
304 uint y = F(x).right;
305
306
307 if (y) {
308 F(x).right = F(y).left;
309 if (F(y).left)
310 F(F(y).left).parent = x;
311 F(y).left = x;
312 F(y).parent = p;
313 } else {
314 F(x).right = 0;
315 }
316 if (!p) {
317 Q_ASSERT(head->root == x);
318 head->root = y;
319 }
320 else if (x == F(p).left)
321 F(p).left = y;
322 else
323 F(p).right = y;
324 F(x).parent = y;
325 for (uint field = 0; field < Fragment::size_array_max; ++field)
326 F(y).size_left_array[field] += F(x).size_left_array[field] + F(x).size_array[field];
327}
328
329
330/*
331 x y
332 / / \
333 y --> a x
334 / \ /
335 a b b
336*/
337template <class Fragment>
338void QFragmentMapData<Fragment>::rotateRight(uint x)
339{
340 uint y = F(x).left;
341 uint p = F(x).parent;
342
343 if (y) {
344 F(x).left = F(y).right;
345 if (F(y).right)
346 F(F(y).right).parent = x;
347 F(y).right = x;
348 F(y).parent = p;
349 } else {
350 F(x).left = 0;
351 }
352 if (!p) {
353 Q_ASSERT(head->root == x);
354 head->root = y;
355 }
356 else if (x == F(p).right)
357 F(p).right = y;
358 else
359 F(p).left = y;
360 F(x).parent = y;
361 for (uint field = 0; field < Fragment::size_array_max; ++field)
362 F(x).size_left_array[field] -= F(y).size_left_array[field] + F(y).size_array[field];
363}
364
365
366template <class Fragment>
367void QFragmentMapData<Fragment>::rebalance(uint x)
368{
369 F(x).color = Red;
370
371 while (F(x).parent && F(F(x).parent).color == Red) {
372 uint p = F(x).parent;
373 uint pp = F(p).parent;
374 Q_ASSERT(pp);
375 if (p == F(pp).left) {
376 uint y = F(pp).right;
377 if (y && F(y).color == Red) {
378 F(p).color = Black;
379 F(y).color = Black;
380 F(pp).color = Red;
381 x = pp;
382 } else {
383 if (x == F(p).right) {
384 x = p;
385 rotateLeft(x);
386 p = F(x).parent;
387 pp = F(p).parent;
388 }
389 F(p).color = Black;
390 if (pp) {
391 F(pp).color = Red;
392 rotateRight(x: pp);
393 }
394 }
395 } else {
396 uint y = F(pp).left;
397 if (y && F(y).color == Red) {
398 F(p).color = Black;
399 F(y).color = Black;
400 F(pp).color = Red;
401 x = pp;
402 } else {
403 if (x == F(p).left) {
404 x = p;
405 rotateRight(x);
406 p = F(x).parent;
407 pp = F(p).parent;
408 }
409 F(p).color = Black;
410 if (pp) {
411 F(pp).color = Red;
412 rotateLeft(x: pp);
413 }
414 }
415 }
416 }
417 F(root()).color = Black;
418}
419
420
421template <class Fragment>
422uint QFragmentMapData<Fragment>::erase_single(uint z)
423{
424 uint w = previous(n: z);
425 uint y = z;
426 uint x;
427 uint p;
428
429 if (!F(y).left) {
430 x = F(y).right;
431 } else if (!F(y).right) {
432 x = F(y).left;
433 } else {
434 y = F(y).right;
435 while (F(y).left)
436 y = F(y).left;
437 x = F(y).right;
438 }
439
440 if (y != z) {
441 F(F(z).left).parent = y;
442 F(y).left = F(z).left;
443 for (uint field = 0; field < Fragment::size_array_max; ++field)
444 F(y).size_left_array[field] = F(z).size_left_array[field];
445 if (y != F(z).right) {
446 /*
447 z y
448 / \ / \
449 a b a b
450 / /
451 ... --> ...
452 / /
453 y x
454 / \
455 0 x
456 */
457 p = F(y).parent;
458 if (x)
459 F(x).parent = p;
460 F(p).left = x;
461 F(y).right = F(z).right;
462 F(F(z).right).parent = y;
463 uint n = p;
464 while (n != y) {
465 for (uint field = 0; field < Fragment::size_array_max; ++field)
466 F(n).size_left_array[field] -= F(y).size_array[field];
467 n = F(n).parent;
468 }
469 } else {
470 /*
471 z y
472 / \ / \
473 a y --> a x
474 / \
475 0 x
476 */
477 p = y;
478 }
479 uint zp = F(z).parent;
480 if (!zp) {
481 Q_ASSERT(head->root == z);
482 head->root = y;
483 } else if (F(zp).left == z) {
484 F(zp).left = y;
485 for (uint field = 0; field < Fragment::size_array_max; ++field)
486 F(zp).size_left_array[field] -= F(z).size_array[field];
487 } else {
488 F(zp).right = y;
489 }
490 F(y).parent = zp;
491 // Swap the colors
492 uint c = F(y).color;
493 F(y).color = F(z).color;
494 F(z).color = c;
495 y = z;
496 } else {
497 /*
498 p p p p
499 / / \ \
500 z --> x z --> x
501 | |
502 x x
503 */
504 p = F(z).parent;
505 if (x)
506 F(x).parent = p;
507 if (!p) {
508 Q_ASSERT(head->root == z);
509 head->root = x;
510 } else if (F(p).left == z) {
511 F(p).left = x;
512 for (uint field = 0; field < Fragment::size_array_max; ++field)
513 F(p).size_left_array[field] -= F(z).size_array[field];
514 } else {
515 F(p).right = x;
516 }
517 }
518 uint n = z;
519 while (F(n).parent) {
520 uint p = F(n).parent;
521 if (F(p).left == n) {
522 for (uint field = 0; field < Fragment::size_array_max; ++field)
523 F(p).size_left_array[field] -= F(z).size_array[field];
524 }
525 n = p;
526 }
527
528 freeFragment(i: z);
529
530
531 if (F(y).color != Red) {
532 while (F(x).parent && (x == 0 || F(x).color == Black)) {
533 if (x == F(p).left) {
534 uint w = F(p).right;
535 if (F(w).color == Red) {
536 F(w).color = Black;
537 F(p).color = Red;
538 rotateLeft(x: p);
539 w = F(p).right;
540 }
541 if ((F(w).left == 0 || F(F(w).left).color == Black) &&
542 (F(w).right == 0 || F(F(w).right).color == Black)) {
543 F(w).color = Red;
544 x = p;
545 p = F(x).parent;
546 } else {
547 if (F(w).right == 0 || F(F(w).right).color == Black) {
548 if (F(w).left)
549 F(F(w).left).color = Black;
550 F(w).color = Red;
551 rotateRight(x: F(p).right);
552 w = F(p).right;
553 }
554 F(w).color = F(p).color;
555 F(p).color = Black;
556 if (F(w).right)
557 F(F(w).right).color = Black;
558 rotateLeft(x: p);
559 break;
560 }
561 } else {
562 uint w = F(p).left;
563 if (F(w).color == Red) {
564 F(w).color = Black;
565 F(p).color = Red;
566 rotateRight(x: p);
567 w = F(p).left;
568 }
569 if ((F(w).right == 0 || F(F(w).right).color == Black) &&
570 (F(w).left == 0 || F(F(w).left).color == Black)) {
571 F(w).color = Red;
572 x = p;
573 p = F(x).parent;
574 } else {
575 if (F(w).left == 0 || F(F(w).left).color == Black) {
576 if (F(w).right)
577 F(F(w).right).color = Black;
578 F(w).color = Red;
579 rotateLeft(x: F(p).left);
580 w = F(p).left;
581 }
582 F(w).color = F(p).color;
583 F(p).color = Black;
584 if (F(w).left)
585 F(F(w).left).color = Black;
586 rotateRight(x: p);
587 break;
588 }
589 }
590 }
591 if (x)
592 F(x).color = Black;
593 }
594
595 return w;
596}
597
598template <class Fragment>
599uint QFragmentMapData<Fragment>::findNode(int k, uint field) const
600{
601 Q_ASSERT(field < Fragment::size_array_max);
602 uint x = root();
603
604 uint s = k;
605 while (x) {
606 if (sizeLeft(node: x, field) <= s) {
607 if (s < sizeLeft(node: x, field) + size(node: x, field))
608 return x;
609 s -= sizeLeft(node: x, field) + size(node: x, field);
610 x = F(x).right;
611 } else {
612 x = F(x).left;
613 }
614 }
615 return 0;
616}
617
618template <class Fragment>
619uint QFragmentMapData<Fragment>::insert_single(int key, uint length)
620{
621 Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);
622
623 uint z = createFragment();
624
625 F(z).left = 0;
626 F(z).right = 0;
627 F(z).size_array[0] = length;
628 for (uint field = 1; field < Fragment::size_array_max; ++field)
629 F(z).size_array[field] = 1;
630 for (uint field = 0; field < Fragment::size_array_max; ++field)
631 F(z).size_left_array[field] = 0;
632
633 uint y = 0;
634 uint x = root();
635
636 Q_ASSERT(!x || F(x).parent == 0);
637
638 uint s = key;
639 bool right = false;
640 while (x) {
641 y = x;
642 if (s <= F(x).size_left_array[0]) {
643 x = F(x).left;
644 right = false;
645 } else {
646 s -= F(x).size_left_array[0] + F(x).size_array[0];
647 x = F(x).right;
648 right = true;
649 }
650 }
651
652 F(z).parent = y;
653 if (!y) {
654 head->root = z;
655 } else if (!right) {
656 F(y).left = z;
657 for (uint field = 0; field < Fragment::size_array_max; ++field)
658 F(y).size_left_array[field] = F(z).size_array[field];
659 } else {
660 F(y).right = z;
661 }
662 while (y && F(y).parent) {
663 uint p = F(y).parent;
664 if (F(p).left == y) {
665 for (uint field = 0; field < Fragment::size_array_max; ++field)
666 F(p).size_left_array[field] += F(z).size_array[field];
667 }
668 y = p;
669 }
670 rebalance(x: z);
671
672 return z;
673}
674
675
676template <class Fragment>
677int QFragmentMapData<Fragment>::length(uint field) const {
678 uint root = this->root();
679 return root ? sizeLeft(node: root, field) + size(node: root, field) + sizeRight(node: root, field) : 0;
680}
681
682
683template <class Fragment> // NOTE: must inherit QFragment
684class QFragmentMap
685{
686public:
687 class Iterator
688 {
689 public:
690 QFragmentMap *pt;
691 quint32 n;
692
693 Iterator() : pt(0), n(0) {}
694 Iterator(QFragmentMap *p, int node) : pt(p), n(node) {}
695 Iterator(const Iterator& it) : pt(it.pt), n(it.n) {}
696
697 inline bool atEnd() const { return !n; }
698
699 bool operator==(const Iterator& it) const { return pt == it.pt && n == it.n; }
700 bool operator!=(const Iterator& it) const { return pt != it.pt || n != it.n; }
701 bool operator<(const Iterator &it) const { return position() < it.position(); }
702
703 Fragment *operator*() { Q_ASSERT(!atEnd()); return pt->fragment(n); }
704 const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
705 Fragment *operator->() { Q_ASSERT(!atEnd()); return pt->fragment(n); }
706 const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
707
708 int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); }
709 const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
710 Fragment *value() { Q_ASSERT(!atEnd()); return pt->fragment(n); }
711
712 Iterator& operator++() {
713 n = pt->data.next(n);
714 return *this;
715 }
716 Iterator& operator--() {
717 n = pt->data.previous(n);
718 return *this;
719 }
720
721 };
722
723
724 class ConstIterator
725 {
726 public:
727 const QFragmentMap *pt;
728 quint32 n;
729
730 /**
731 * Functions
732 */
733 ConstIterator() : pt(0), n(0) {}
734 ConstIterator(const QFragmentMap *p, int node) : pt(p), n(node) {}
735 ConstIterator(const ConstIterator& it) : pt(it.pt), n(it.n) {}
736 ConstIterator(const Iterator& it) : pt(it.pt), n(it.n) {}
737
738 inline bool atEnd() const { return !n; }
739
740 bool operator==(const ConstIterator& it) const { return pt == it.pt && n == it.n; }
741 bool operator!=(const ConstIterator& it) const { return pt != it.pt || n != it.n; }
742 bool operator<(const ConstIterator &it) const { return position() < it.position(); }
743
744 const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
745 const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
746
747 int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); }
748 int size() const { Q_ASSERT(!atEnd()); return pt->data.size(n); }
749 const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
750
751 ConstIterator& operator++() {
752 n = pt->data.next(n);
753 return *this;
754 }
755 ConstIterator& operator--() {
756 n = pt->data.previous(n);
757 return *this;
758 }
759 };
760
761
762 QFragmentMap() {}
763 ~QFragmentMap()
764 {
765 if (!data.fragments)
766 return; // in case of out-of-memory, we won't have fragments
767 for (Iterator it = begin(); !it.atEnd(); ++it)
768 it.value()->free();
769 }
770
771 inline void clear() {
772 for (Iterator it = begin(); !it.atEnd(); ++it)
773 it.value()->free();
774 data.init();
775 }
776
777 inline Iterator begin() { return Iterator(this, data.minimum(data.root())); }
778 inline Iterator end() { return Iterator(this, 0); }
779 inline ConstIterator begin() const { return ConstIterator(this, data.minimum(data.root())); }
780 inline ConstIterator end() const { return ConstIterator(this, 0); }
781
782 inline ConstIterator last() const { return ConstIterator(this, data.maximum(data.root())); }
783
784 inline bool isEmpty() const { return data.head->node_count == 0; }
785 inline int numNodes() const { return data.head->node_count; }
786 int length(uint field = 0) const { return data.length(field); }
787
788 Iterator find(int k, uint field = 0) { return Iterator(this, data.findNode(k, field)); }
789 ConstIterator find(int k, uint field = 0) const { return ConstIterator(this, data.findNode(k, field)); }
790
791 uint findNode(int k, uint field = 0) const { return data.findNode(k, field); }
792
793 uint insert_single(int key, uint length)
794 {
795 uint f = data.insert_single(key, length);
796 if (f != 0) {
797 Fragment *frag = fragment(f);
798 Q_ASSERT(frag);
799 frag->initialize();
800 }
801 return f;
802 }
803 uint erase_single(uint f)
804 {
805 if (f != 0) {
806 Fragment *frag = fragment(f);
807 Q_ASSERT(frag);
808 frag->free();
809 }
810 return data.erase_single(f);
811 }
812
813 inline Fragment *fragment(uint index) {
814 Q_ASSERT(index != 0);
815 return data.fragment(index);
816 }
817 inline const Fragment *fragment(uint index) const {
818 Q_ASSERT(index != 0);
819 return data.fragment(index);
820 }
821 inline uint position(uint node, uint field = 0) const { return data.position(node, field); }
822 inline bool isValid(uint n) const { return data.isValid(n); }
823 inline uint next(uint n) const { return data.next(n); }
824 inline uint previous(uint n) const { return data.previous(n); }
825 inline uint size(uint node, uint field = 0) const { return data.size(node, field); }
826 inline void setSize(uint node, int new_size, uint field = 0)
827 { data.setSize(node, new_size, field);
828 if (node != 0 && field == 0) {
829 Fragment *frag = fragment(node);
830 Q_ASSERT(frag);
831 frag->invalidate();
832 }
833 }
834
835 inline int firstNode() const { return data.minimum(data.root()); }
836
837private:
838 friend class Iterator;
839 friend class ConstIterator;
840
841 QFragmentMapData<Fragment> data;
842
843 QFragmentMap(const QFragmentMap& m);
844 QFragmentMap& operator= (const QFragmentMap& m);
845};
846
847QT_END_NAMESPACE
848
849#endif // QFRAGMENTMAP_P_H
850

source code of qtbase/src/gui/text/qfragmentmap_p.h