1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

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

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

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

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

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

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef QFRAGMENTMAP_P_H

    43 #define QFRAGMENTMAP_P_H

    44 

    45 //

    46 //  W A R N I N G

    47 //  -------------

    48 //

    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.

    52 //

    53 // We mean it.

    54 //

    55 

    56 #include "QtCore/qglobal.h"

    57 #include <stdlib.h>

    58 #include <private/qtools_p.h>

    59 

    60 QT_BEGIN_NAMESPACE

    61 

    62 

    63 template <int N = 1>

    64 class QFragment

    65 {

    66 public:

    67     quint32 parent;

    68     quint32 left;

    69     quint32 right;

    70     quint32 color;

    71     quint32 size_left_array[N];

    72     quint32 size_array[N];

    73     enum {size_array_max = N };

    74 };

    75 

    76 template <class Fragment>

    77 class QFragmentMapData

    78 {

    79     enum Color { Red, Black };

    80 public:

    81     QFragmentMapData();

    82     ~QFragmentMapData();

    83 

    84     void init();

    85 

    86     class Header

    87     {

    88     public:

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

    90         quint32 tag;

    91         quint32 freelist;

    92         quint32 node_count;

    93         quint32 allocated;

    94     };

    95 

    96 

    97     enum {fragmentSize = sizeof(Fragment) };

    98 

    99 

   100     int length(uint field = 0) const;

   101 

   102 

   103     inline Fragment *fragment(uint index) {

   104         return (fragments + index);

   105     }

   106     inline const Fragment *fragment(uint index) const {

   107         return (fragments + index);

   108     }

   109 

   110 

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

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

   113 

   114     inline bool isRoot(uint index) const {

   115         return !fragment(index)->parent;

   116     }

   117 

   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];

   122         while (f->parent) {

   123             uint p = f->parent;

   124             f = fragment(p);

   125             if (f->right == node)

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

   127             node = p;

   128         }

   129         return offset;

   130     }

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

   132         Q_ASSERT(field < Fragment::size_array_max);

   133         uint sr = 0;

   134         const Fragment *f = fragment(node);

   135         node = f->right;

   136         while (node) {

   137             f = fragment(node);

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

   139             node = f->right;

   140         }

   141         return sr;

   142     }

   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];

   146     }

   147 

   148 

   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];

   152     }

   153 

   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;

   159         while (f->parent) {

   160             uint p = f->parent;

   161             f = fragment(p);

   162             if (f->left == node)

   163                 f->size_left_array[field] += diff;

   164             node = p;

   165         }

   166     }

   167 

   168 

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

   170 

   171     uint insert_single(int key, uint length);

   172     uint erase_single(uint f);

   173 

   174     uint minimum(uint n) const {

   175         while (n && fragment(n)->left)

   176             n = fragment(n)->left;

   177         return n;

   178     }

   179 

   180     uint maximum(uint n) const {

   181         while (n && fragment(n)->right)

   182             n = fragment(n)->right;

   183         return n;

   184     }

   185 

   186     uint next(uint n) const;

   187     uint previous(uint n) const;

   188 

   189     inline uint root() const {

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

   191         return head->root;

   192     }

   193     inline void setRoot(uint new_root) {

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

   195         head->root = new_root;

   196     }

   197 

   198     union {

   199         Header *head;

   200         Fragment *fragments;

   201     };

   202 

   203 private:

   204 

   205     void rotateLeft(uint x);

   206     void rotateRight(uint x);

   207     void rebalance(uint x);

   208     void removeAndRebalance(uint z);

   209 

   210     uint createFragment();

   211     void freeFragment(uint f);

   212 

   213 };

   214 

   215 template <class Fragment>

   216 QFragmentMapData<Fragment>::QFragmentMapData()

   217     : fragments(0)

   218 {

   219     init();

   220 }

   221 

   222 template <class Fragment>

   223 void QFragmentMapData<Fragment>::init()

   224 {

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

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

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

   228     if (newFragments) {

   229         fragments = newFragments;

   230         head->allocated = 64;

   231     }

   232     Q_CHECK_PTR(fragments);

   233 

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

   235     head->root = 0;

   236     head->freelist = 1;

   237     head->node_count = 0;

   238     // mark all items to the right as unused

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

   240 }

   241 

   242 template <class Fragment>

   243 QFragmentMapData<Fragment>::~QFragmentMapData()

   244 {

   245     free(fragments);

   246 }

   247 

   248 template <class Fragment>

   249 uint QFragmentMapData<Fragment>::createFragment()

   250 {

   251     Q_ASSERT(head->freelist <= head->allocated);

   252 

   253     uint freePos = head->freelist;

   254     if (freePos == head->allocated) {

   255         // need to create some free space

   256         uint needed = qAllocMore((freePos+1)*fragmentSize, 0);

   257         Q_ASSERT(needed/fragmentSize > head->allocated);

   258         Fragment *newFragments = (Fragment *)realloc(fragments, needed);

   259         Q_CHECK_PTR(newFragments);

   260         fragments = newFragments;

   261         head->allocated = needed/fragmentSize;

   262         F(freePos).right = 0;

   263     }

   264 

   265     uint nextPos = F(freePos).right;

   266     if (!nextPos) {

   267         nextPos = freePos+1;

   268         if (nextPos < head->allocated)

   269             F(nextPos).right = 0;

   270     }

   271 

   272     head->freelist = nextPos;

   273 

   274     ++head->node_count;

   275 

   276     return freePos;

   277 }

   278 

   279 template <class Fragment>

   280 void QFragmentMapData<Fragment>::freeFragment(uint i)

   281 {

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

   283     head->freelist = i;

   284 

   285     --head->node_count;

   286 }

   287 

   288 

   289 template <class Fragment>

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

   291     Q_ASSERT(n);

   292     if (F(n).right) {

   293         n = F(n).right;

   294         while (F(n).left)

   295             n = F(n).left;

   296     } else {

   297         uint y = F(n).parent;

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

   299             n = y;

   300             y = F(y).parent;

   301         }

   302         n = y;

   303     }

   304     return n;

   305 }

   306 

   307 template <class Fragment>

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

   309     if (!n)

   310         return maximum(root());

   311 

   312     if (F(n).left) {

   313         n = F(n).left;

   314         while (F(n).right)

   315             n = F(n).right;

   316     } else {

   317         uint y = F(n).parent;

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

   319             n = y;

   320             y = F(y).parent;

   321         }

   322         n = y;

   323     }

   324     return n;

   325 }

   326 

   327 

   328 /*

   329      x              y

   330       \            / \

   331        y    -->   x   b

   332       / \          \

   333      a   b          a

   334 */

   335 template <class Fragment>

   336 void QFragmentMapData<Fragment>::rotateLeft(uint x)

   337 {

   338     uint p = F(x).parent;

   339     uint y = F(x).right;

   340 

   341 

   342     if (y) {

   343         F(x).right = F(y).left;

   344         if (F(y).left)

   345             F(F(y).left).parent = x;

   346         F(y).left = x;

   347         F(y).parent = p;

   348     } else {

   349         F(x).right = 0;

   350     }

   351     if (!p) {

   352         Q_ASSERT(head->root == x);

   353         head->root = y;

   354     }

   355     else if (x == F(p).left)

   356         F(p).left = y;

   357     else

   358         F(p).right = y;

   359     F(x).parent = y;

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

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

   362 }

   363 

   364 

   365 /*

   366          x          y

   367         /          / \

   368        y    -->   a   x

   369       / \            /

   370      a   b          b

   371 */

   372 template <class Fragment>

   373 void QFragmentMapData<Fragment>::rotateRight(uint x)

   374 {

   375     uint y = F(x).left;

   376     uint p = F(x).parent;

   377 

   378     if (y) {

   379         F(x).left = F(y).right;

   380         if (F(y).right)

   381             F(F(y).right).parent = x;

   382         F(y).right = x;

   383         F(y).parent = p;

   384     } else {

   385         F(x).left = 0;

   386     }

   387     if (!p) {

   388         Q_ASSERT(head->root == x);

   389         head->root = y;

   390     }

   391     else if (x == F(p).right)

   392         F(p).right = y;

   393     else

   394         F(p).left = y;

   395     F(x).parent = y;

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

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

   398 }

   399 

   400 

   401 template <class Fragment>

   402 void QFragmentMapData<Fragment>::rebalance(uint x)

   403 {

   404     F(x).color = Red;

   405 

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

   407         uint p = F(x).parent;

   408         uint pp = F(p).parent;

   409         Q_ASSERT(pp);

   410         if (p == F(pp).left) {

   411             uint y = F(pp).right;

   412             if (y && F(y).color == Red) {

   413                 F(p).color = Black;

   414                 F(y).color = Black;

   415                 F(pp).color = Red;

   416                 x = pp;

   417             } else {

   418                 if (x == F(p).right) {

   419                     x = p;

   420                     rotateLeft(x);

   421                     p = F(x).parent;

   422                     pp = F(p).parent;

   423                 }

   424                 F(p).color = Black;

   425                 if (pp) {

   426                     F(pp).color = Red;

   427                     rotateRight(pp);

   428                 }

   429             }

   430         } else {

   431             uint y = F(pp).left;

   432             if (y && F(y).color == Red) {

   433                 F(p).color = Black;

   434                 F(y).color = Black;

   435                 F(pp).color = Red;

   436                 x = pp;

   437             } else {

   438                 if (x == F(p).left) {

   439                     x = p;

   440                     rotateRight(x);

   441                     p = F(x).parent;

   442                     pp = F(p).parent;

   443                 }

   444                 F(p).color = Black;

   445                 if (pp) {

   446                     F(pp).color = Red;

   447                     rotateLeft(pp);

   448                 }

   449             }

   450         }

   451     }

   452     F(root()).color = Black;

   453 }

   454 

   455 

   456 template <class Fragment>

   457 uint QFragmentMapData<Fragment>::erase_single(uint z)

   458 {

   459     uint w = previous(z);

   460     uint y = z;

   461     uint x;

   462     uint p;

   463 

   464     if (!F(y).left) {

   465         x = F(y).right;

   466     } else if (!F(y).right) {

   467         x = F(y).left;

   468     } else {

   469         y = F(y).right;

   470         while (F(y).left)

   471             y = F(y).left;

   472         x = F(y).right;

   473     }

   474 

   475     if (y != z) {

   476         F(F(z).left).parent = y;

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

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

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

   480         if (y != F(z).right) {

   481             /*

   482                      z                y

   483                     / \              / \

   484                    a   b            a   b

   485                       /                /

   486                     ...     -->      ...

   487                     /                /

   488                    y                x

   489                   / \

   490                  0   x

   491              */

   492             p = F(y).parent;

   493             if (x)

   494                 F(x).parent = p;

   495             F(p).left = x;

   496             F(y).right = F(z).right;

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

   498             uint n = p;

   499             while (n != y) {

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

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

   502                 n = F(n).parent;

   503             }

   504         } else {

   505             /*

   506                      z                y

   507                     / \              / \

   508                    a   y     -->    a   x

   509                       / \

   510                      0   x

   511              */

   512             p = y;

   513         }

   514         uint zp = F(z).parent;

   515         if (!zp) {

   516             Q_ASSERT(head->root == z);

   517             head->root = y;

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

   519             F(zp).left = y;

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

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

   522         } else {

   523             F(zp).right = y;

   524         }

   525         F(y).parent = zp;

   526         // Swap the colors

   527         uint c = F(y).color;

   528         F(y).color = F(z).color;

   529         F(z).color = c;

   530         y = z;

   531     } else {

   532         /*

   533                 p          p            p          p

   534                /          /              \          \

   535               z    -->   x                z  -->     x

   536               |                           |

   537               x                           x

   538          */

   539         p = F(z).parent;

   540         if (x)

   541             F(x).parent = p;

   542         if (!p) {

   543             Q_ASSERT(head->root == z);

   544             head->root = x;

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

   546             F(p).left = x;

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

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

   549         } else {

   550             F(p).right = x;

   551         }

   552     }

   553     uint n = z;

   554     while (F(n).parent) {

   555         uint p = F(n).parent;

   556         if (F(p).left == n) {

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

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

   559         }

   560         n = p;

   561     }

   562 

   563     freeFragment(z);

   564 

   565 

   566     if (F(y).color != Red) {

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

   568             if (x == F(p).left) {

   569                 uint w = F(p).right;

   570                 if (F(w).color == Red) {

   571                     F(w).color = Black;

   572                     F(p).color = Red;

   573                     rotateLeft(p);

   574                     w = F(p).right;

   575                 }

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

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

   578                     F(w).color = Red;

   579                     x = p;

   580                     p = F(x).parent;

   581                 } else {

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

   583                         if (F(w).left)

   584                             F(F(w).left).color = Black;

   585                         F(w).color = Red;

   586                         rotateRight(F(p).right);

   587                         w = F(p).right;

   588                     }

   589                     F(w).color = F(p).color;

   590                     F(p).color = Black;

   591                     if (F(w).right)

   592                         F(F(w).right).color = Black;

   593                     rotateLeft(p);

   594                     break;

   595                 }

   596             } else {

   597                 uint w = F(p).left;

   598                 if (F(w).color == Red) {

   599                     F(w).color = Black;

   600                     F(p).color = Red;

   601                     rotateRight(p);

   602                     w = F(p).left;

   603                 }

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

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

   606                     F(w).color = Red;

   607                     x = p;

   608                     p = F(x).parent;

   609                 } else {

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

   611                         if (F(w).right)

   612                             F(F(w).right).color = Black;

   613                         F(w).color = Red;

   614                         rotateLeft(F(p).left);

   615                         w = F(p).left;

   616                     }

   617                     F(w).color = F(p).color;

   618                     F(p).color = Black;

   619                     if (F(w).left)

   620                         F(F(w).left).color = Black;

   621                     rotateRight(p);

   622                     break;

   623                 }

   624             }

   625         }

   626         if (x)

   627             F(x).color = Black;

   628     }

   629 

   630     return w;

   631 }

   632 

   633 template <class Fragment>

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

   635 {

   636     Q_ASSERT(field < Fragment::size_array_max);

   637     uint x = root();

   638 

   639     uint s = k;

   640     while (x) {

   641         if (sizeLeft(x, field) <= s) {

   642             if (s < sizeLeft(x, field) + size(x, field))

   643                 return x;

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

   645             x = F(x).right;

   646         } else {

   647             x = F(x).left;

   648         }

   649     }

   650     return 0;

   651 }

   652 

   653 template <class Fragment>

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

   655 {

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

   657 

   658     uint z = createFragment();

   659 

   660     F(z).left = 0;

   661     F(z).right = 0;

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

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

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

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

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

   667 

   668     uint y = 0;

   669     uint x = root();

   670 

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

   672 

   673     uint s = key;

   674     bool right = false;

   675     while (x) {

   676         y = x;

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

   678             x = F(x).left;

   679             right = false;

   680         } else {

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

   682             x = F(x).right;

   683             right = true;

   684         }

   685     }

   686 

   687     F(z).parent = y;

   688     if (!y) {

   689         head->root = z;

   690     } else if (!right) {

   691         F(y).left = z;

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

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

   694     } else {

   695         F(y).right = z;

   696     }

   697     while (y && F(y).parent) {

   698         uint p = F(y).parent;

   699         if (F(p).left == y) {

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

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

   702         }

   703         y = p;

   704     }

   705     rebalance(z);

   706 

   707     return z;

   708 }

   709 

   710 

   711 template <class Fragment>

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

   713     uint root = this->root();

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

   715 }

   716 

   717 

   718 template <class Fragment> // NOTE: must inherit QFragment

   719 class QFragmentMap

   720 {

   721 public:

   722     class Iterator

   723     {

   724     public:

   725         QFragmentMap *pt;

   726         quint32 n;

   727 

   728         Iterator() : pt(0), n(0) {}

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

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

   731 

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

   733 

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

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

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

   737 

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

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

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

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

   742 

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

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

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

   746 

   747         Iterator& operator++() {

   748             n = pt->data.next(n);

   749             return *this;

   750         }

   751         Iterator& operator--() {

   752             n = pt->data.previous(n);

   753             return *this;

   754         }

   755 

   756     };

   757 

   758 

   759     class ConstIterator

   760     {

   761     public:

   762         const QFragmentMap *pt;

   763         quint32 n;

   764 

   765         /**

   766          * Functions

   767          */

   768         ConstIterator() : pt(0), n(0) {}

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

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

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

   772 

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

   774 

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

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

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

   778 

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

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

   781 

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

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

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

   785 

   786         ConstIterator& operator++() {

   787             n = pt->data.next(n);

   788             return *this;

   789         }

   790         ConstIterator& operator--() {

   791             n = pt->data.previous(n);

   792             return *this;

   793         }

   794     };

   795 

   796 

   797     QFragmentMap() {}

   798     ~QFragmentMap()

   799     {

   800         if (!data.fragments)

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

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

   803             it.value()->free();

   804     }

   805 

   806     inline void clear() {

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

   808             it.value()->free();

   809         data.init();

   810     }

   811 

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

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

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

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

   816 

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

   818 

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

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

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

   822 

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

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

   825 

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

   827 

   828     uint insert_single(int key, uint length)

   829     {

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

   831         if (f != 0) {

   832             Fragment *frag = fragment(f);

   833             Q_ASSERT(frag);

   834             frag->initialize();

   835         }

   836         return f;

   837     }

   838     uint erase_single(uint f)

   839     {

   840       if (f != 0) {

   841           Fragment *frag = fragment(f);

   842           Q_ASSERT(frag);

   843           frag->free();

   844       }

   845       return data.erase_single(f);

   846     }

   847 

   848     inline Fragment *fragment(uint index) {

   849         Q_ASSERT(index != 0);

   850         return data.fragment(index);

   851     }

   852     inline const Fragment *fragment(uint index) const {

   853         Q_ASSERT(index != 0);

   854         return data.fragment(index);

   855     }

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

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

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

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

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

   861         { data.setSize(node, new_size, field);

   862       if (node != 0 && field == 0) {

   863           Fragment *frag = fragment(node);

   864           Q_ASSERT(frag);

   865           frag->invalidate();

   866       }

   867     }

   868 

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

   870 

   871 private:

   872     friend class Iterator;

   873     friend class ConstIterator;

   874 

   875     QFragmentMapData<Fragment> data;

   876 

   877     QFragmentMap(const QFragmentMap& m);

   878     QFragmentMap& operator= (const QFragmentMap& m);

   879 };

   880 

   881 QT_END_NAMESPACE

   882 

   883 #endif // QFRAGMENTMAP_P_H