| /**************************************************************************** |
| ** |
| ** Copyright (C) 2015 The Qt Company Ltd. |
| ** Contact: http://www.qt.io/licensing/ |
| ** |
| ** This file is part of the QtGui module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL21$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see http://www.qt.io/terms-conditions. For further |
| ** information use the contact form at http://www.qt.io/contact-us. |
| ** |
| ** GNU Lesser General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU Lesser |
| ** General Public License version 2.1 or version 3 as published by the Free |
| ** Software Foundation and appearing in the file LICENSE.LGPLv21 and |
| ** LICENSE.LGPLv3 included in the packaging of this file. Please review the |
| ** following information to ensure the GNU Lesser General Public License |
| ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and |
| ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
| ** |
| ** As a special exception, The Qt Company gives you certain additional |
| ** rights. These rights are described in The Qt Company LGPL Exception |
| ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #ifndef QFRAGMENTMAP_P_H |
| #define QFRAGMENTMAP_P_H |
| |
| // |
| // W A R N I N G |
| // ------------- |
| // |
| // This file is not part of the Qt API. It exists purely as an |
| // implementation detail. This header file may change from version to |
| // version without notice, or even be removed. |
| // |
| // We mean it. |
| // |
| |
| #include "QtCore/qglobal.h" |
| #include <stdlib.h> |
| #include <private/qtools_p.h> |
| |
| QT_BEGIN_NAMESPACE |
| |
| |
| template <int N = 1> |
| class QFragment |
| { |
| public: |
| quint32 parent; |
| quint32 left; |
| quint32 right; |
| quint32 color; |
| quint32 size_left_array[N]; |
| quint32 size_array[N]; |
| enum {size_array_max = N }; |
| }; |
| |
| template <class Fragment> |
| class QFragmentMapData |
| { |
| enum Color { Red, Black }; |
| public: |
| QFragmentMapData(); |
| ~QFragmentMapData(); |
| |
| void init(); |
| |
| class Header |
| { |
| public: |
| quint32 root; // this relies on being at the same position as parent in the fragment struct |
| quint32 tag; |
| quint32 freelist; |
| quint32 node_count; |
| quint32 allocated; |
| }; |
| |
| |
| enum {fragmentSize = sizeof(Fragment) }; |
| |
| |
| int length(uint field = 0) const; |
| |
| |
| inline Fragment *fragment(uint index) { |
| return (fragments + index); |
| } |
| inline const Fragment *fragment(uint index) const { |
| return (fragments + index); |
| } |
| |
| |
| inline Fragment &F(uint index) { return fragments[index] ; } |
| inline const Fragment &F(uint index) const { return fragments[index] ; } |
| |
| inline bool isRoot(uint index) const { |
| return !fragment(index)->parent; |
| } |
| |
| inline uint position(uint node, uint field = 0) const { |
| Q_ASSERT(field < Fragment::size_array_max); |
| const Fragment *f = fragment(node); |
| uint offset = f->size_left_array[field]; |
| while (f->parent) { |
| uint p = f->parent; |
| f = fragment(p); |
| if (f->right == node) |
| offset += f->size_left_array[field] + f->size_array[field]; |
| node = p; |
| } |
| return offset; |
| } |
| inline uint sizeRight(uint node, uint field = 0) const { |
| Q_ASSERT(field < Fragment::size_array_max); |
| uint sr = 0; |
| const Fragment *f = fragment(node); |
| node = f->right; |
| while (node) { |
| f = fragment(node); |
| sr += f->size_left_array[field] + f->size_array[field]; |
| node = f->right; |
| } |
| return sr; |
| } |
| inline uint sizeLeft(uint node, uint field = 0) const { |
| Q_ASSERT(field < Fragment::size_array_max); |
| return fragment(node)->size_left_array[field]; |
| } |
| |
| |
| inline uint size(uint node, uint field = 0) const { |
| Q_ASSERT(field < Fragment::size_array_max); |
| return fragment(node)->size_array[field]; |
| } |
| |
| inline void setSize(uint node, int new_size, uint field = 0) { |
| Q_ASSERT(field < Fragment::size_array_max); |
| Fragment *f = fragment(node); |
| int diff = new_size - f->size_array[field]; |
| f->size_array[field] = new_size; |
| while (f->parent) { |
| uint p = f->parent; |
| f = fragment(p); |
| if (f->left == node) |
| f->size_left_array[field] += diff; |
| node = p; |
| } |
| } |
| |
| |
| uint findNode(int k, uint field = 0) const; |
| |
| uint insert_single(int key, uint length); |
| uint erase_single(uint f); |
| |
| uint minimum(uint n) const { |
| while (n && fragment(n)->left) |
| n = fragment(n)->left; |
| return n; |
| } |
| |
| uint maximum(uint n) const { |
| while (n && fragment(n)->right) |
| n = fragment(n)->right; |
| return n; |
| } |
| |
| uint next(uint n) const; |
| uint previous(uint n) const; |
| |
| inline uint root() const { |
| Q_ASSERT(!head->root || !fragment(head->root)->parent); |
| return head->root; |
| } |
| inline void setRoot(uint new_root) { |
| Q_ASSERT(!head->root || !fragment(new_root)->parent); |
| head->root = new_root; |
| } |
| |
| inline bool isValid(uint n) const { |
| return n > 0 && n != head->freelist; |
| } |
| |
| union { |
| Header *head; |
| Fragment *fragments; |
| }; |
| |
| private: |
| |
| void rotateLeft(uint x); |
| void rotateRight(uint x); |
| void rebalance(uint x); |
| void removeAndRebalance(uint z); |
| |
| uint createFragment(); |
| void freeFragment(uint f); |
| |
| }; |
| |
| template <class Fragment> |
| QFragmentMapData<Fragment>::QFragmentMapData() |
| : fragments(0) |
| { |
| init(); |
| } |
| |
| template <class Fragment> |
| void QFragmentMapData<Fragment>::init() |
| { |
| // the following code will realloc an existing fragment or create a new one. |
| // it will also ignore errors when shrinking an existing fragment. |
| Fragment *newFragments = (Fragment *)realloc(fragments, 64*fragmentSize); |
| if (newFragments) { |
| fragments = newFragments; |
| head->allocated = 64; |
| } |
| Q_CHECK_PTR(fragments); |
| |
| head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //TAG('p', 'm', 'a', 'p'); |
| head->root = 0; |
| head->freelist = 1; |
| head->node_count = 0; |
| // mark all items to the right as unused |
| F(head->freelist).right = 0; |
| } |
| |
| template <class Fragment> |
| QFragmentMapData<Fragment>::~QFragmentMapData() |
| { |
| free(fragments); |
| } |
| |
| template <class Fragment> |
| uint QFragmentMapData<Fragment>::createFragment() |
| { |
| Q_ASSERT(head->freelist <= head->allocated); |
| |
| uint freePos = head->freelist; |
| if (freePos == head->allocated) { |
| // need to create some free space |
| if (freePos >= uint(MaxAllocSize) / fragmentSize) |
| qBadAlloc(); |
| uint needed = qAllocMore((freePos+1)*fragmentSize, 0); |
| Q_ASSERT(needed/fragmentSize > head->allocated); |
| Fragment *newFragments = (Fragment *)realloc(fragments, needed); |
| Q_CHECK_PTR(newFragments); |
| fragments = newFragments; |
| head->allocated = needed/fragmentSize; |
| F(freePos).right = 0; |
| } |
| |
| uint nextPos = F(freePos).right; |
| if (!nextPos) { |
| nextPos = freePos+1; |
| if (nextPos < head->allocated) |
| F(nextPos).right = 0; |
| } |
| |
| head->freelist = nextPos; |
| |
| ++head->node_count; |
| |
| return freePos; |
| } |
| |
| template <class Fragment> |
| void QFragmentMapData<Fragment>::freeFragment(uint i) |
| { |
| F(i).right = head->freelist; |
| head->freelist = i; |
| |
| --head->node_count; |
| } |
| |
| |
| template <class Fragment> |
| uint QFragmentMapData<Fragment>::next(uint n) const { |
| Q_ASSERT(n); |
| if (F(n).right) { |
| n = F(n).right; |
| while (F(n).left) |
| n = F(n).left; |
| } else { |
| uint y = F(n).parent; |
| while (F(n).parent && n == F(y).right) { |
| n = y; |
| y = F(y).parent; |
| } |
| n = y; |
| } |
| return n; |
| } |
| |
| template <class Fragment> |
| uint QFragmentMapData<Fragment>::previous(uint n) const { |
| if (!n) |
| return maximum(root()); |
| |
| if (F(n).left) { |
| n = F(n).left; |
| while (F(n).right) |
| n = F(n).right; |
| } else { |
| uint y = F(n).parent; |
| while (F(n).parent && n == F(y).left) { |
| n = y; |
| y = F(y).parent; |
| } |
| n = y; |
| } |
| return n; |
| } |
| |
| |
| /* |
| x y |
| \ / \ |
| y --> x b |
| / \ \ |
| a b a |
| */ |
| template <class Fragment> |
| void QFragmentMapData<Fragment>::rotateLeft(uint x) |
| { |
| uint p = F(x).parent; |
| uint y = F(x).right; |
| |
| |
| if (y) { |
| F(x).right = F(y).left; |
| if (F(y).left) |
| F(F(y).left).parent = x; |
| F(y).left = x; |
| F(y).parent = p; |
| } else { |
| F(x).right = 0; |
| } |
| if (!p) { |
| Q_ASSERT(head->root == x); |
| head->root = y; |
| } |
| else if (x == F(p).left) |
| F(p).left = y; |
| else |
| F(p).right = y; |
| F(x).parent = y; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(y).size_left_array[field] += F(x).size_left_array[field] + F(x).size_array[field]; |
| } |
| |
| |
| /* |
| x y |
| / / \ |
| y --> a x |
| / \ / |
| a b b |
| */ |
| template <class Fragment> |
| void QFragmentMapData<Fragment>::rotateRight(uint x) |
| { |
| uint y = F(x).left; |
| uint p = F(x).parent; |
| |
| if (y) { |
| F(x).left = F(y).right; |
| if (F(y).right) |
| F(F(y).right).parent = x; |
| F(y).right = x; |
| F(y).parent = p; |
| } else { |
| F(x).left = 0; |
| } |
| if (!p) { |
| Q_ASSERT(head->root == x); |
| head->root = y; |
| } |
| else if (x == F(p).right) |
| F(p).right = y; |
| else |
| F(p).left = y; |
| F(x).parent = y; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(x).size_left_array[field] -= F(y).size_left_array[field] + F(y).size_array[field]; |
| } |
| |
| |
| template <class Fragment> |
| void QFragmentMapData<Fragment>::rebalance(uint x) |
| { |
| F(x).color = Red; |
| |
| while (F(x).parent && F(F(x).parent).color == Red) { |
| uint p = F(x).parent; |
| uint pp = F(p).parent; |
| Q_ASSERT(pp); |
| if (p == F(pp).left) { |
| uint y = F(pp).right; |
| if (y && F(y).color == Red) { |
| F(p).color = Black; |
| F(y).color = Black; |
| F(pp).color = Red; |
| x = pp; |
| } else { |
| if (x == F(p).right) { |
| x = p; |
| rotateLeft(x); |
| p = F(x).parent; |
| pp = F(p).parent; |
| } |
| F(p).color = Black; |
| if (pp) { |
| F(pp).color = Red; |
| rotateRight(pp); |
| } |
| } |
| } else { |
| uint y = F(pp).left; |
| if (y && F(y).color == Red) { |
| F(p).color = Black; |
| F(y).color = Black; |
| F(pp).color = Red; |
| x = pp; |
| } else { |
| if (x == F(p).left) { |
| x = p; |
| rotateRight(x); |
| p = F(x).parent; |
| pp = F(p).parent; |
| } |
| F(p).color = Black; |
| if (pp) { |
| F(pp).color = Red; |
| rotateLeft(pp); |
| } |
| } |
| } |
| } |
| F(root()).color = Black; |
| } |
| |
| |
| template <class Fragment> |
| uint QFragmentMapData<Fragment>::erase_single(uint z) |
| { |
| uint w = previous(z); |
| uint y = z; |
| uint x; |
| uint p; |
| |
| if (!F(y).left) { |
| x = F(y).right; |
| } else if (!F(y).right) { |
| x = F(y).left; |
| } else { |
| y = F(y).right; |
| while (F(y).left) |
| y = F(y).left; |
| x = F(y).right; |
| } |
| |
| if (y != z) { |
| F(F(z).left).parent = y; |
| F(y).left = F(z).left; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(y).size_left_array[field] = F(z).size_left_array[field]; |
| if (y != F(z).right) { |
| /* |
| z y |
| / \ / \ |
| a b a b |
| / / |
| ... --> ... |
| / / |
| y x |
| / \ |
| 0 x |
| */ |
| p = F(y).parent; |
| if (x) |
| F(x).parent = p; |
| F(p).left = x; |
| F(y).right = F(z).right; |
| F(F(z).right).parent = y; |
| uint n = p; |
| while (n != y) { |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(n).size_left_array[field] -= F(y).size_array[field]; |
| n = F(n).parent; |
| } |
| } else { |
| /* |
| z y |
| / \ / \ |
| a y --> a x |
| / \ |
| 0 x |
| */ |
| p = y; |
| } |
| uint zp = F(z).parent; |
| if (!zp) { |
| Q_ASSERT(head->root == z); |
| head->root = y; |
| } else if (F(zp).left == z) { |
| F(zp).left = y; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(zp).size_left_array[field] -= F(z).size_array[field]; |
| } else { |
| F(zp).right = y; |
| } |
| F(y).parent = zp; |
| // Swap the colors |
| uint c = F(y).color; |
| F(y).color = F(z).color; |
| F(z).color = c; |
| y = z; |
| } else { |
| /* |
| p p p p |
| / / \ \ |
| z --> x z --> x |
| | | |
| x x |
| */ |
| p = F(z).parent; |
| if (x) |
| F(x).parent = p; |
| if (!p) { |
| Q_ASSERT(head->root == z); |
| head->root = x; |
| } else if (F(p).left == z) { |
| F(p).left = x; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(p).size_left_array[field] -= F(z).size_array[field]; |
| } else { |
| F(p).right = x; |
| } |
| } |
| uint n = z; |
| while (F(n).parent) { |
| uint p = F(n).parent; |
| if (F(p).left == n) { |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(p).size_left_array[field] -= F(z).size_array[field]; |
| } |
| n = p; |
| } |
| |
| freeFragment(z); |
| |
| |
| if (F(y).color != Red) { |
| while (F(x).parent && (x == 0 || F(x).color == Black)) { |
| if (x == F(p).left) { |
| uint w = F(p).right; |
| if (F(w).color == Red) { |
| F(w).color = Black; |
| F(p).color = Red; |
| rotateLeft(p); |
| w = F(p).right; |
| } |
| if ((F(w).left == 0 || F(F(w).left).color == Black) && |
| (F(w).right == 0 || F(F(w).right).color == Black)) { |
| F(w).color = Red; |
| x = p; |
| p = F(x).parent; |
| } else { |
| if (F(w).right == 0 || F(F(w).right).color == Black) { |
| if (F(w).left) |
| F(F(w).left).color = Black; |
| F(w).color = Red; |
| rotateRight(F(p).right); |
| w = F(p).right; |
| } |
| F(w).color = F(p).color; |
| F(p).color = Black; |
| if (F(w).right) |
| F(F(w).right).color = Black; |
| rotateLeft(p); |
| break; |
| } |
| } else { |
| uint w = F(p).left; |
| if (F(w).color == Red) { |
| F(w).color = Black; |
| F(p).color = Red; |
| rotateRight(p); |
| w = F(p).left; |
| } |
| if ((F(w).right == 0 || F(F(w).right).color == Black) && |
| (F(w).left == 0 || F(F(w).left).color == Black)) { |
| F(w).color = Red; |
| x = p; |
| p = F(x).parent; |
| } else { |
| if (F(w).left == 0 || F(F(w).left).color == Black) { |
| if (F(w).right) |
| F(F(w).right).color = Black; |
| F(w).color = Red; |
| rotateLeft(F(p).left); |
| w = F(p).left; |
| } |
| F(w).color = F(p).color; |
| F(p).color = Black; |
| if (F(w).left) |
| F(F(w).left).color = Black; |
| rotateRight(p); |
| break; |
| } |
| } |
| } |
| if (x) |
| F(x).color = Black; |
| } |
| |
| return w; |
| } |
| |
| template <class Fragment> |
| uint QFragmentMapData<Fragment>::findNode(int k, uint field) const |
| { |
| Q_ASSERT(field < Fragment::size_array_max); |
| uint x = root(); |
| |
| uint s = k; |
| while (x) { |
| if (sizeLeft(x, field) <= s) { |
| if (s < sizeLeft(x, field) + size(x, field)) |
| return x; |
| s -= sizeLeft(x, field) + size(x, field); |
| x = F(x).right; |
| } else { |
| x = F(x).left; |
| } |
| } |
| return 0; |
| } |
| |
| template <class Fragment> |
| uint QFragmentMapData<Fragment>::insert_single(int key, uint length) |
| { |
| Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key); |
| |
| uint z = createFragment(); |
| |
| F(z).left = 0; |
| F(z).right = 0; |
| F(z).size_array[0] = length; |
| for (uint field = 1; field < Fragment::size_array_max; ++field) |
| F(z).size_array[field] = 1; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(z).size_left_array[field] = 0; |
| |
| uint y = 0; |
| uint x = root(); |
| |
| Q_ASSERT(!x || F(x).parent == 0); |
| |
| uint s = key; |
| bool right = false; |
| while (x) { |
| y = x; |
| if (s <= F(x).size_left_array[0]) { |
| x = F(x).left; |
| right = false; |
| } else { |
| s -= F(x).size_left_array[0] + F(x).size_array[0]; |
| x = F(x).right; |
| right = true; |
| } |
| } |
| |
| F(z).parent = y; |
| if (!y) { |
| head->root = z; |
| } else if (!right) { |
| F(y).left = z; |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(y).size_left_array[field] = F(z).size_array[field]; |
| } else { |
| F(y).right = z; |
| } |
| while (y && F(y).parent) { |
| uint p = F(y).parent; |
| if (F(p).left == y) { |
| for (uint field = 0; field < Fragment::size_array_max; ++field) |
| F(p).size_left_array[field] += F(z).size_array[field]; |
| } |
| y = p; |
| } |
| rebalance(z); |
| |
| return z; |
| } |
| |
| |
| template <class Fragment> |
| int QFragmentMapData<Fragment>::length(uint field) const { |
| uint root = this->root(); |
| return root ? sizeLeft(root, field) + size(root, field) + sizeRight(root, field) : 0; |
| } |
| |
| |
| template <class Fragment> // NOTE: must inherit QFragment |
| class QFragmentMap |
| { |
| public: |
| class Iterator |
| { |
| public: |
| QFragmentMap *pt; |
| quint32 n; |
| |
| Iterator() : pt(0), n(0) {} |
| Iterator(QFragmentMap *p, int node) : pt(p), n(node) {} |
| Iterator(const Iterator& it) : pt(it.pt), n(it.n) {} |
| |
| inline bool atEnd() const { return !n; } |
| |
| bool operator==(const Iterator& it) const { return pt == it.pt && n == it.n; } |
| bool operator!=(const Iterator& it) const { return pt != it.pt || n != it.n; } |
| bool operator<(const Iterator &it) const { return position() < it.position(); } |
| |
| Fragment *operator*() { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| Fragment *operator->() { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| |
| int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); } |
| const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| Fragment *value() { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| |
| Iterator& operator++() { |
| n = pt->data.next(n); |
| return *this; |
| } |
| Iterator& operator--() { |
| n = pt->data.previous(n); |
| return *this; |
| } |
| |
| }; |
| |
| |
| class ConstIterator |
| { |
| public: |
| const QFragmentMap *pt; |
| quint32 n; |
| |
| /** |
| * Functions |
| */ |
| ConstIterator() : pt(0), n(0) {} |
| ConstIterator(const QFragmentMap *p, int node) : pt(p), n(node) {} |
| ConstIterator(const ConstIterator& it) : pt(it.pt), n(it.n) {} |
| ConstIterator(const Iterator& it) : pt(it.pt), n(it.n) {} |
| |
| inline bool atEnd() const { return !n; } |
| |
| bool operator==(const ConstIterator& it) const { return pt == it.pt && n == it.n; } |
| bool operator!=(const ConstIterator& it) const { return pt != it.pt || n != it.n; } |
| bool operator<(const ConstIterator &it) const { return position() < it.position(); } |
| |
| const Fragment *operator*() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| const Fragment *operator->() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| |
| int position() const { Q_ASSERT(!atEnd()); return pt->data.position(n); } |
| int size() const { Q_ASSERT(!atEnd()); return pt->data.size(n); } |
| const Fragment *value() const { Q_ASSERT(!atEnd()); return pt->fragment(n); } |
| |
| ConstIterator& operator++() { |
| n = pt->data.next(n); |
| return *this; |
| } |
| ConstIterator& operator--() { |
| n = pt->data.previous(n); |
| return *this; |
| } |
| }; |
| |
| |
| QFragmentMap() {} |
| ~QFragmentMap() |
| { |
| if (!data.fragments) |
| return; // in case of out-of-memory, we won't have fragments |
| for (Iterator it = begin(); !it.atEnd(); ++it) |
| it.value()->free(); |
| } |
| |
| inline void clear() { |
| for (Iterator it = begin(); !it.atEnd(); ++it) |
| it.value()->free(); |
| data.init(); |
| } |
| |
| inline Iterator begin() { return Iterator(this, data.minimum(data.root())); } |
| inline Iterator end() { return Iterator(this, 0); } |
| inline ConstIterator begin() const { return ConstIterator(this, data.minimum(data.root())); } |
| inline ConstIterator end() const { return ConstIterator(this, 0); } |
| |
| inline ConstIterator last() const { return ConstIterator(this, data.maximum(data.root())); } |
| |
| inline bool isEmpty() const { return data.head->node_count == 0; } |
| inline int numNodes() const { return data.head->node_count; } |
| int length(uint field = 0) const { return data.length(field); } |
| |
| Iterator find(int k, uint field = 0) { return Iterator(this, data.findNode(k, field)); } |
| ConstIterator find(int k, uint field = 0) const { return ConstIterator(this, data.findNode(k, field)); } |
| |
| uint findNode(int k, uint field = 0) const { return data.findNode(k, field); } |
| |
| uint insert_single(int key, uint length) |
| { |
| uint f = data.insert_single(key, length); |
| if (f != 0) { |
| Fragment *frag = fragment(f); |
| Q_ASSERT(frag); |
| frag->initialize(); |
| } |
| return f; |
| } |
| uint erase_single(uint f) |
| { |
| if (f != 0) { |
| Fragment *frag = fragment(f); |
| Q_ASSERT(frag); |
| frag->free(); |
| } |
| return data.erase_single(f); |
| } |
| |
| inline Fragment *fragment(uint index) { |
| Q_ASSERT(index != 0); |
| return data.fragment(index); |
| } |
| inline const Fragment *fragment(uint index) const { |
| Q_ASSERT(index != 0); |
| return data.fragment(index); |
| } |
| inline uint position(uint node, uint field = 0) const { return data.position(node, field); } |
| inline bool isValid(uint n) const { return data.isValid(n); } |
| inline uint next(uint n) const { return data.next(n); } |
| inline uint previous(uint n) const { return data.previous(n); } |
| inline uint size(uint node, uint field = 0) const { return data.size(node, field); } |
| inline void setSize(uint node, int new_size, uint field = 0) |
| { data.setSize(node, new_size, field); |
| if (node != 0 && field == 0) { |
| Fragment *frag = fragment(node); |
| Q_ASSERT(frag); |
| frag->invalidate(); |
| } |
| } |
| |
| inline int firstNode() const { return data.minimum(data.root()); } |
| |
| private: |
| friend class Iterator; |
| friend class ConstIterator; |
| |
| QFragmentMapData<Fragment> data; |
| |
| QFragmentMap(const QFragmentMap& m); |
| QFragmentMap& operator= (const QFragmentMap& m); |
| }; |
| |
| QT_END_NAMESPACE |
| |
| #endif // QFRAGMENTMAP_P_H |