1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtGui module of the Qt Toolkit.
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
42 #ifndef QFRAGMENTMAP_P_H
43 #define QFRAGMENTMAP_P_H
49 // This file is not part of the Qt API. It exists purely as an
50 // implementation detail. This header file may change from version to
51 // version without notice, or even be removed.
56 #include "QtCore/qglobal.h"
58 #include <private/qtools_p.h>
71 quint32 size_left_array[N];
72 quint32 size_array[N];
73 enum {size_array_max = N };
76 template <class Fragment>
77 class QFragmentMapData
79 enum Color { Red, Black };
89 quint32 root; // this relies on being at the same position as parent in the fragment struct
97 enum {fragmentSize = sizeof(Fragment) };
100 int length(uint field = 0) const;
103 inline Fragment *fragment(uint index) {
104 return (fragments + index);
106 inline const Fragment *fragment(uint index) const {
107 return (fragments + index);
111 inline Fragment &F(uint index) { return fragments[index] ; }
112 inline const Fragment &F(uint index) const { return fragments[index] ; }
114 inline bool isRoot(uint index) const {
115 return !fragment(index)->parent;
118 inline uint position(uint node, uint field = 0) const {
119 Q_ASSERT(field < Fragment::size_array_max);
120 const Fragment *f = fragment(node);
121 uint offset = f->size_left_array[field];
125 if (f->right == node)
126 offset += f->size_left_array[field] + f->size_array[field];
131 inline uint sizeRight(uint node, uint field = 0) const {
132 Q_ASSERT(field < Fragment::size_array_max);
134 const Fragment *f = fragment(node);
138 sr += f->size_left_array[field] + f->size_array[field];
143 inline uint sizeLeft(uint node, uint field = 0) const {
144 Q_ASSERT(field < Fragment::size_array_max);
145 return fragment(node)->size_left_array[field];
149 inline uint size(uint node, uint field = 0) const {
150 Q_ASSERT(field < Fragment::size_array_max);
151 return fragment(node)->size_array[field];
154 inline void setSize(uint node, int new_size, uint field = 0) {
155 Q_ASSERT(field < Fragment::size_array_max);
156 Fragment *f = fragment(node);
157 int diff = new_size - f->size_array[field];
158 f->size_array[field] = new_size;
163 f->size_left_array[field] += diff;
169 uint findNode(int k, uint field = 0) const;
171 uint insert_single(int key, uint length);
172 uint erase_single(uint f);
174 uint minimum(uint n) const {
175 while (n && fragment(n)->left)
176 n = fragment(n)->left;
180 uint maximum(uint n) const {
181 while (n && fragment(n)->right)
182 n = fragment(n)->right;
186 uint next(uint n) const;
187 uint previous(uint n) const;
189 inline uint root() const {
190 Q_ASSERT(!head->root || !fragment(head->root)->parent);
193 inline void setRoot(uint new_root) {
194 Q_ASSERT(!head->root || !fragment(new_root)->parent);
195 head->root = new_root;
198 inline bool isValid(uint n) const {
199 return n > 0 && n != head->freelist;
209 void rotateLeft(uint x);
210 void rotateRight(uint x);
211 void rebalance(uint x);
212 void removeAndRebalance(uint z);
214 uint createFragment();
215 void freeFragment(uint f);
219 template <class Fragment>
220 QFragmentMapData<Fragment>::QFragmentMapData()
226 template <class Fragment>
227 void QFragmentMapData<Fragment>::init()
229 // the following code will realloc an existing fragment or create a new one.
230 // it will also ignore errors when shrinking an existing fragment.
231 Fragment *newFragments = (Fragment *)realloc(fragments, 64*fragmentSize);
233 fragments = newFragments;
234 head->allocated = 64;
236 Q_CHECK_PTR(fragments);
238 head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //TAG('p', 'm', 'a', 'p');
241 head->node_count = 0;
242 // mark all items to the right as unused
243 F(head->freelist).right = 0;
246 template <class Fragment>
247 QFragmentMapData<Fragment>::~QFragmentMapData()
252 template <class Fragment>
253 uint QFragmentMapData<Fragment>::createFragment()
255 Q_ASSERT(head->freelist <= head->allocated);
257 uint freePos = head->freelist;
258 if (freePos == head->allocated) {
259 // need to create some free space
260 uint needed = qAllocMore((freePos+1)*fragmentSize, 0);
261 Q_ASSERT(needed/fragmentSize > head->allocated);
262 Fragment *newFragments = (Fragment *)realloc(fragments, needed);
263 Q_CHECK_PTR(newFragments);
264 fragments = newFragments;
265 head->allocated = needed/fragmentSize;
266 F(freePos).right = 0;
269 uint nextPos = F(freePos).right;
272 if (nextPos < head->allocated)
273 F(nextPos).right = 0;
276 head->freelist = nextPos;
283 template <class Fragment>
284 void QFragmentMapData<Fragment>::freeFragment(uint i)
286 F(i).right = head->freelist;
293 template <class Fragment>
294 uint QFragmentMapData<Fragment>::next(uint n) const {
301 uint y = F(n).parent;
302 while (F(n).parent && n == F(y).right) {
311 template <class Fragment>
312 uint QFragmentMapData<Fragment>::previous(uint n) const {
314 return maximum(root());
321 uint y = F(n).parent;
322 while (F(n).parent && n == F(y).left) {
339 template <class Fragment>
340 void QFragmentMapData<Fragment>::rotateLeft(uint x)
342 uint p = F(x).parent;
347 F(x).right = F(y).left;
349 F(F(y).left).parent = x;
356 Q_ASSERT(head->root == x);
359 else if (x == F(p).left)
364 for (uint field = 0; field < Fragment::size_array_max; ++field)
365 F(y).size_left_array[field] += F(x).size_left_array[field] + F(x).size_array[field];
376 template <class Fragment>
377 void QFragmentMapData<Fragment>::rotateRight(uint x)
380 uint p = F(x).parent;
383 F(x).left = F(y).right;
385 F(F(y).right).parent = x;
392 Q_ASSERT(head->root == x);
395 else if (x == F(p).right)
400 for (uint field = 0; field < Fragment::size_array_max; ++field)
401 F(x).size_left_array[field] -= F(y).size_left_array[field] + F(y).size_array[field];
405 template <class Fragment>
406 void QFragmentMapData<Fragment>::rebalance(uint x)
410 while (F(x).parent && F(F(x).parent).color == Red) {
411 uint p = F(x).parent;
412 uint pp = F(p).parent;
414 if (p == F(pp).left) {
415 uint y = F(pp).right;
416 if (y && F(y).color == Red) {
422 if (x == F(p).right) {
436 if (y && F(y).color == Red) {
442 if (x == F(p).left) {
456 F(root()).color = Black;
460 template <class Fragment>
461 uint QFragmentMapData<Fragment>::erase_single(uint z)
463 uint w = previous(z);
470 } else if (!F(y).right) {
480 F(F(z).left).parent = y;
481 F(y).left = F(z).left;
482 for (uint field = 0; field < Fragment::size_array_max; ++field)
483 F(y).size_left_array[field] = F(z).size_left_array[field];
484 if (y != F(z).right) {
500 F(y).right = F(z).right;
501 F(F(z).right).parent = y;
504 for (uint field = 0; field < Fragment::size_array_max; ++field)
505 F(n).size_left_array[field] -= F(y).size_array[field];
518 uint zp = F(z).parent;
520 Q_ASSERT(head->root == z);
522 } else if (F(zp).left == z) {
524 for (uint field = 0; field < Fragment::size_array_max; ++field)
525 F(zp).size_left_array[field] -= F(z).size_array[field];
532 F(y).color = F(z).color;
547 Q_ASSERT(head->root == z);
549 } else if (F(p).left == z) {
551 for (uint field = 0; field < Fragment::size_array_max; ++field)
552 F(p).size_left_array[field] -= F(z).size_array[field];
558 while (F(n).parent) {
559 uint p = F(n).parent;
560 if (F(p).left == n) {
561 for (uint field = 0; field < Fragment::size_array_max; ++field)
562 F(p).size_left_array[field] -= F(z).size_array[field];
570 if (F(y).color != Red) {
571 while (F(x).parent && (x == 0 || F(x).color == Black)) {
572 if (x == F(p).left) {
574 if (F(w).color == Red) {
580 if ((F(w).left == 0 || F(F(w).left).color == Black) &&
581 (F(w).right == 0 || F(F(w).right).color == Black)) {
586 if (F(w).right == 0 || F(F(w).right).color == Black) {
588 F(F(w).left).color = Black;
590 rotateRight(F(p).right);
593 F(w).color = F(p).color;
596 F(F(w).right).color = Black;
602 if (F(w).color == Red) {
608 if ((F(w).right == 0 || F(F(w).right).color == Black) &&
609 (F(w).left == 0 || F(F(w).left).color == Black)) {
614 if (F(w).left == 0 || F(F(w).left).color == Black) {
616 F(F(w).right).color = Black;
618 rotateLeft(F(p).left);
621 F(w).color = F(p).color;
624 F(F(w).left).color = Black;
637 template <class Fragment>
638 uint QFragmentMapData<Fragment>::findNode(int k, uint field) const
640 Q_ASSERT(field < Fragment::size_array_max);
645 if (sizeLeft(x, field) <= s) {
646 if (s < sizeLeft(x, field) + size(x, field))
648 s -= sizeLeft(x, field) + size(x, field);
657 template <class Fragment>
658 uint QFragmentMapData<Fragment>::insert_single(int key, uint length)
660 Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);
662 uint z = createFragment();
666 F(z).size_array[0] = length;
667 for (uint field = 1; field < Fragment::size_array_max; ++field)
668 F(z).size_array[field] = 1;
669 for (uint field = 0; field < Fragment::size_array_max; ++field)
670 F(z).size_left_array[field] = 0;
675 Q_ASSERT(!x || F(x).parent == 0);
681 if (s <= F(x).size_left_array[0]) {
685 s -= F(x).size_left_array[0] + F(x).size_array[0];
696 for (uint field = 0; field < Fragment::size_array_max; ++field)
697 F(y).size_left_array[field] = F(z).size_array[field];
701 while (y && F(y).parent) {
702 uint p = F(y).parent;
703 if (F(p).left == y) {
704 for (uint field = 0; field < Fragment::size_array_max; ++field)
705 F(p).size_left_array[field] += F(z).size_array[field];
715 template <class Fragment>
716 int QFragmentMapData<Fragment>::length(uint field) const {
717 uint root = this->root();
718 return root ? sizeLeft(root, field) + size(root, field) + sizeRight(root, field) : 0;
722 template <class Fragment> // NOTE: must inherit QFragment
732 Iterator() : pt(0), n(0) {}
733 Iterator(QFragmentMap *p, int node) : pt(p), n(node) {}
734 Iterator(const Iterator& it) : pt(it.pt), n(it.n) {}
736 inline bool atEnd() const { return !n; }
738 bool operator==(const Iterator& it) const { return pt == it.pt && n == it.n; }
739 bool operator!=(const Iterator& it) const { return pt != it.pt || n != it.n; }
740 bool operator<(const Iterator &it) const { return position() < it.position(); }
742 Fragment *operator*() { Q_ASSERT(!atEnd()); return pt->fragment(n); }
743 const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
744 Fragment *operator->() { Q_ASSERT(!atEnd()); return pt->fragment(n); }
745 const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
747 int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); }
748 const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
749 Fragment *value() { Q_ASSERT(!atEnd()); return pt->fragment(n); }
751 Iterator& operator++() {
752 n = pt->data.next(n);
755 Iterator& operator--() {
756 n = pt->data.previous(n);
766 const QFragmentMap *pt;
772 ConstIterator() : pt(0), n(0) {}
773 ConstIterator(const QFragmentMap *p, int node) : pt(p), n(node) {}
774 ConstIterator(const ConstIterator& it) : pt(it.pt), n(it.n) {}
775 ConstIterator(const Iterator& it) : pt(it.pt), n(it.n) {}
777 inline bool atEnd() const { return !n; }
779 bool operator==(const ConstIterator& it) const { return pt == it.pt && n == it.n; }
780 bool operator!=(const ConstIterator& it) const { return pt != it.pt || n != it.n; }
781 bool operator<(const ConstIterator &it) const { return position() < it.position(); }
783 const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
784 const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
786 int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); }
787 int size() const { Q_ASSERT(!atEnd()); return pt->data.size(n); }
788 const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
790 ConstIterator& operator++() {
791 n = pt->data.next(n);
794 ConstIterator& operator--() {
795 n = pt->data.previous(n);
805 return; // in case of out-of-memory, we won't have fragments
806 for (Iterator it = begin(); !it.atEnd(); ++it)
810 inline void clear() {
811 for (Iterator it = begin(); !it.atEnd(); ++it)
816 inline Iterator begin() { return Iterator(this, data.minimum(data.root())); }
817 inline Iterator end() { return Iterator(this, 0); }
818 inline ConstIterator begin() const { return ConstIterator(this, data.minimum(data.root())); }
819 inline ConstIterator end() const { return ConstIterator(this, 0); }
821 inline ConstIterator last() const { return ConstIterator(this, data.maximum(data.root())); }
823 inline bool isEmpty() const { return data.head->node_count == 0; }
824 inline int numNodes() const { return data.head->node_count; }
825 int length(uint field = 0) const { return data.length(field); }
827 Iterator find(int k, uint field = 0) { return Iterator(this, data.findNode(k, field)); }
828 ConstIterator find(int k, uint field = 0) const { return ConstIterator(this, data.findNode(k, field)); }
830 uint findNode(int k, uint field = 0) const { return data.findNode(k, field); }
832 uint insert_single(int key, uint length)
834 uint f = data.insert_single(key, length);
836 Fragment *frag = fragment(f);
842 uint erase_single(uint f)
845 Fragment *frag = fragment(f);
849 return data.erase_single(f);
852 inline Fragment *fragment(uint index) {
853 Q_ASSERT(index != 0);
854 return data.fragment(index);
856 inline const Fragment *fragment(uint index) const {
857 Q_ASSERT(index != 0);
858 return data.fragment(index);
860 inline uint position(uint node, uint field = 0) const { return data.position(node, field); }
861 inline bool isValid(uint n) const { return data.isValid(n); }
862 inline uint next(uint n) const { return data.next(n); }
863 inline uint previous(uint n) const { return data.previous(n); }
864 inline uint size(uint node, uint field = 0) const { return data.size(node, field); }
865 inline void setSize(uint node, int new_size, uint field = 0)
866 { data.setSize(node, new_size, field);
867 if (node != 0 && field == 0) {
868 Fragment *frag = fragment(node);
874 inline int firstNode() const { return data.minimum(data.root()); }
877 friend class Iterator;
878 friend class ConstIterator;
880 QFragmentMapData<Fragment> data;
882 QFragmentMap(const QFragmentMap& m);
883 QFragmentMap& operator= (const QFragmentMap& m);
888 #endif // QFRAGMENTMAP_P_H