src/gui/text/qfragmentmap_p.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   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.
  16 **
  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.
  20 **
  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.
  28 **
  29 ** Other Usage
  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.
  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     inline bool isValid(uint n) const {
 199         return n > 0 && n != head->freelist;
 200     }
 201
 202     union {
 203         Header *head;
 204         Fragment *fragments;
 205     };
 206
 207 private:
 208
 209     void rotateLeft(uint x);
 210     void rotateRight(uint x);
 211     void rebalance(uint x);
 212     void removeAndRebalance(uint z);
 213
 214     uint createFragment();
 215     void freeFragment(uint f);
 216
 217 };
 218
 219 template <class Fragment>
 220 QFragmentMapData<Fragment>::QFragmentMapData()
 221     : fragments(0)
 222 {
 223     init();
 224 }
 225
 226 template <class Fragment>
 227 void QFragmentMapData<Fragment>::init()
 228 {
 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);
 232     if (newFragments) {
 233         fragments = newFragments;
 234         head->allocated = 64;
 235     }
 236     Q_CHECK_PTR(fragments);
 237
 238     head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //TAG('p', 'm', 'a', 'p');
 239     head->root = 0;
 240     head->freelist = 1;
 241     head->node_count = 0;
 242     // mark all items to the right as unused
 243     F(head->freelist).right = 0;
 244 }
 245
 246 template <class Fragment>
 247 QFragmentMapData<Fragment>::~QFragmentMapData()
 248 {
 249     free(fragments);
 250 }
 251
 252 template <class Fragment>
 253 uint QFragmentMapData<Fragment>::createFragment()
 254 {
 255     Q_ASSERT(head->freelist <= head->allocated);
 256
 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;
 267     }
 268
 269     uint nextPos = F(freePos).right;
 270     if (!nextPos) {
 271         nextPos = freePos+1;
 272         if (nextPos < head->allocated)
 273             F(nextPos).right = 0;
 274     }
 275
 276     head->freelist = nextPos;
 277
 278     ++head->node_count;
 279
 280     return freePos;
 281 }
 282
 283 template <class Fragment>
 284 void QFragmentMapData<Fragment>::freeFragment(uint i)
 285 {
 286     F(i).right = head->freelist;
 287     head->freelist = i;
 288
 289     --head->node_count;
 290 }
 291
 292
 293 template <class Fragment>
 294 uint QFragmentMapData<Fragment>::next(uint n) const {
 295     Q_ASSERT(n);
 296     if (F(n).right) {
 297         n = F(n).right;
 298         while (F(n).left)
 299             n = F(n).left;
 300     } else {
 301         uint y = F(n).parent;
 302         while (F(n).parent && n == F(y).right) {
 303             n = y;
 304             y = F(y).parent;
 305         }
 306         n = y;
 307     }
 308     return n;
 309 }
 310
 311 template <class Fragment>
 312 uint QFragmentMapData<Fragment>::previous(uint n) const {
 313     if (!n)
 314         return maximum(root());
 315
 316     if (F(n).left) {
 317         n = F(n).left;
 318         while (F(n).right)
 319             n = F(n).right;
 320     } else {
 321         uint y = F(n).parent;
 322         while (F(n).parent && n == F(y).left) {
 323             n = y;
 324             y = F(y).parent;
 325         }
 326         n = y;
 327     }
 328     return n;
 329 }
 330
 331
 332 /*
 333      x              y
 334       \            / \
 335        y    -->   x   b
 336       / \          \
 337      a   b          a
 338 */
 339 template <class Fragment>
 340 void QFragmentMapData<Fragment>::rotateLeft(uint x)
 341 {
 342     uint p = F(x).parent;
 343     uint y = F(x).right;
 344
 345
 346     if (y) {
 347         F(x).right = F(y).left;
 348         if (F(y).left)
 349             F(F(y).left).parent = x;
 350         F(y).left = x;
 351         F(y).parent = p;
 352     } else {
 353         F(x).right = 0;
 354     }
 355     if (!p) {
 356         Q_ASSERT(head->root == x);
 357         head->root = y;
 358     }
 359     else if (x == F(p).left)
 360         F(p).left = y;
 361     else
 362         F(p).right = y;
 363     F(x).parent = y;
 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];
 366 }
 367
 368
 369 /*
 370          x          y
 371         /          / \
 372        y    -->   a   x
 373       / \            /
 374      a   b          b
 375 */
 376 template <class Fragment>
 377 void QFragmentMapData<Fragment>::rotateRight(uint x)
 378 {
 379     uint y = F(x).left;
 380     uint p = F(x).parent;
 381
 382     if (y) {
 383         F(x).left = F(y).right;
 384         if (F(y).right)
 385             F(F(y).right).parent = x;
 386         F(y).right = x;
 387         F(y).parent = p;
 388     } else {
 389         F(x).left = 0;
 390     }
 391     if (!p) {
 392         Q_ASSERT(head->root == x);
 393         head->root = y;
 394     }
 395     else if (x == F(p).right)
 396         F(p).right = y;
 397     else
 398         F(p).left = y;
 399     F(x).parent = y;
 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];
 402 }
 403
 404
 405 template <class Fragment>
 406 void QFragmentMapData<Fragment>::rebalance(uint x)
 407 {
 408     F(x).color = Red;
 409
 410     while (F(x).parent && F(F(x).parent).color == Red) {
 411         uint p = F(x).parent;
 412         uint pp = F(p).parent;
 413         Q_ASSERT(pp);
 414         if (p == F(pp).left) {
 415             uint y = F(pp).right;
 416             if (y && F(y).color == Red) {
 417                 F(p).color = Black;
 418                 F(y).color = Black;
 419                 F(pp).color = Red;
 420                 x = pp;
 421             } else {
 422                 if (x == F(p).right) {
 423                     x = p;
 424                     rotateLeft(x);
 425                     p = F(x).parent;
 426                     pp = F(p).parent;
 427                 }
 428                 F(p).color = Black;
 429                 if (pp) {
 430                     F(pp).color = Red;
 431                     rotateRight(pp);
 432                 }
 433             }
 434         } else {
 435             uint y = F(pp).left;
 436             if (y && F(y).color == Red) {
 437                 F(p).color = Black;
 438                 F(y).color = Black;
 439                 F(pp).color = Red;
 440                 x = pp;
 441             } else {
 442                 if (x == F(p).left) {
 443                     x = p;
 444                     rotateRight(x);
 445                     p = F(x).parent;
 446                     pp = F(p).parent;
 447                 }
 448                 F(p).color = Black;
 449                 if (pp) {
 450                     F(pp).color = Red;
 451                     rotateLeft(pp);
 452                 }
 453             }
 454         }
 455     }
 456     F(root()).color = Black;
 457 }
 458
 459
 460 template <class Fragment>
 461 uint QFragmentMapData<Fragment>::erase_single(uint z)
 462 {
 463     uint w = previous(z);
 464     uint y = z;
 465     uint x;
 466     uint p;
 467
 468     if (!F(y).left) {
 469         x = F(y).right;
 470     } else if (!F(y).right) {
 471         x = F(y).left;
 472     } else {
 473         y = F(y).right;
 474         while (F(y).left)
 475             y = F(y).left;
 476         x = F(y).right;
 477     }
 478
 479     if (y != z) {
 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) {
 485             /*
 486                      z                y
 487                     / \              / \
 488                    a   b            a   b
 489                       /                /
 490                     ...     -->      ...
 491                     /                /
 492                    y                x
 493                   / \
 494                  0   x
 495              */
 496             p = F(y).parent;
 497             if (x)
 498                 F(x).parent = p;
 499             F(p).left = x;
 500             F(y).right = F(z).right;
 501             F(F(z).right).parent = y;
 502             uint n = p;
 503             while (n != y) {
 504                 for (uint field = 0; field < Fragment::size_array_max; ++field)
 505                     F(n).size_left_array[field] -= F(y).size_array[field];
 506                 n = F(n).parent;
 507             }
 508         } else {
 509             /*
 510                      z                y
 511                     / \              / \
 512                    a   y     -->    a   x
 513                       / \
 514                      0   x
 515              */
 516             p = y;
 517         }
 518         uint zp = F(z).parent;
 519         if (!zp) {
 520             Q_ASSERT(head->root == z);
 521             head->root = y;
 522         } else if (F(zp).left == z) {
 523             F(zp).left = y;
 524             for (uint field = 0; field < Fragment::size_array_max; ++field)
 525                 F(zp).size_left_array[field] -= F(z).size_array[field];
 526         } else {
 527             F(zp).right = y;
 528         }
 529         F(y).parent = zp;
 530         // Swap the colors
 531         uint c = F(y).color;
 532         F(y).color = F(z).color;
 533         F(z).color = c;
 534         y = z;
 535     } else {
 536         /*
 537                 p          p            p          p
 538                /          /              \          \
 539               z    -->   x                z  -->     x
 540               |                           |
 541               x                           x
 542          */
 543         p = F(z).parent;
 544         if (x)
 545             F(x).parent = p;
 546         if (!p) {
 547             Q_ASSERT(head->root == z);
 548             head->root = x;
 549         } else if (F(p).left == z) {
 550             F(p).left = x;
 551             for (uint field = 0; field < Fragment::size_array_max; ++field)
 552                 F(p).size_left_array[field] -= F(z).size_array[field];
 553         } else {
 554             F(p).right = x;
 555         }
 556     }
 557     uint n = z;
 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];
 563         }
 564         n = p;
 565     }
 566
 567     freeFragment(z);
 568
 569
 570     if (F(y).color != Red) {
 571         while (F(x).parent && (x == 0 || F(x).color == Black)) {
 572             if (x == F(p).left) {
 573                 uint w = F(p).right;
 574                 if (F(w).color == Red) {
 575                     F(w).color = Black;
 576                     F(p).color = Red;
 577                     rotateLeft(p);
 578                     w = F(p).right;
 579                 }
 580                 if ((F(w).left == 0 || F(F(w).left).color == Black) &&
 581                     (F(w).right == 0 || F(F(w).right).color == Black)) {
 582                     F(w).color = Red;
 583                     x = p;
 584                     p = F(x).parent;
 585                 } else {
 586                     if (F(w).right == 0 || F(F(w).right).color == Black) {
 587                         if (F(w).left)
 588                             F(F(w).left).color = Black;
 589                         F(w).color = Red;
 590                         rotateRight(F(p).right);
 591                         w = F(p).right;
 592                     }
 593                     F(w).color = F(p).color;
 594                     F(p).color = Black;
 595                     if (F(w).right)
 596                         F(F(w).right).color = Black;
 597                     rotateLeft(p);
 598                     break;
 599                 }
 600             } else {
 601                 uint w = F(p).left;
 602                 if (F(w).color == Red) {
 603                     F(w).color = Black;
 604                     F(p).color = Red;
 605                     rotateRight(p);
 606                     w = F(p).left;
 607                 }
 608                 if ((F(w).right == 0 || F(F(w).right).color == Black) &&
 609                     (F(w).left == 0 || F(F(w).left).color == Black)) {
 610                     F(w).color = Red;
 611                     x = p;
 612                     p = F(x).parent;
 613                 } else {
 614                     if (F(w).left == 0 || F(F(w).left).color == Black) {
 615                         if (F(w).right)
 616                             F(F(w).right).color = Black;
 617                         F(w).color = Red;
 618                         rotateLeft(F(p).left);
 619                         w = F(p).left;
 620                     }
 621                     F(w).color = F(p).color;
 622                     F(p).color = Black;
 623                     if (F(w).left)
 624                         F(F(w).left).color = Black;
 625                     rotateRight(p);
 626                     break;
 627                 }
 628             }
 629         }
 630         if (x)
 631             F(x).color = Black;
 632     }
 633
 634     return w;
 635 }
 636
 637 template <class Fragment>
 638 uint QFragmentMapData<Fragment>::findNode(int k, uint field) const
 639 {
 640     Q_ASSERT(field < Fragment::size_array_max);
 641     uint x = root();
 642
 643     uint s = k;
 644     while (x) {
 645         if (sizeLeft(x, field) <= s) {
 646             if (s < sizeLeft(x, field) + size(x, field))
 647                 return x;
 648             s -= sizeLeft(x, field) + size(x, field);
 649             x = F(x).right;
 650         } else {
 651             x = F(x).left;
 652         }
 653     }
 654     return 0;
 655 }
 656
 657 template <class Fragment>
 658 uint QFragmentMapData<Fragment>::insert_single(int key, uint length)
 659 {
 660     Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);
 661
 662     uint z = createFragment();
 663
 664     F(z).left = 0;
 665     F(z).right = 0;
 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;
 671
 672     uint y = 0;
 673     uint x = root();
 674
 675     Q_ASSERT(!x || F(x).parent == 0);
 676
 677     uint s = key;
 678     bool right = false;
 679     while (x) {
 680         y = x;
 681         if (s <= F(x).size_left_array[0]) {
 682             x = F(x).left;
 683             right = false;
 684         } else {
 685             s -= F(x).size_left_array[0] + F(x).size_array[0];
 686             x = F(x).right;
 687             right = true;
 688         }
 689     }
 690
 691     F(z).parent = y;
 692     if (!y) {
 693         head->root = z;
 694     } else if (!right) {
 695         F(y).left = z;
 696         for (uint field = 0; field < Fragment::size_array_max; ++field)
 697             F(y).size_left_array[field] = F(z).size_array[field];
 698     } else {
 699         F(y).right = z;
 700     }
 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];
 706         }
 707         y = p;
 708     }
 709     rebalance(z);
 710
 711     return z;
 712 }
 713
 714
 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;
 719 }
 720
 721
 722 template <class Fragment> // NOTE: must inherit QFragment
 723 class QFragmentMap
 724 {
 725 public:
 726     class Iterator
 727     {
 728     public:
 729         QFragmentMap *pt;
 730         quint32 n;
 731
 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) {}
 735
 736         inline bool atEnd() const { return !n; }
 737
 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(); }
 741
 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); }
 746
 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); }
 750
 751         Iterator& operator++() {
 752             n = pt->data.next(n);
 753             return *this;
 754         }
 755         Iterator& operator--() {
 756             n = pt->data.previous(n);
 757             return *this;
 758         }
 759
 760     };
 761
 762
 763     class ConstIterator
 764     {
 765     public:
 766         const QFragmentMap *pt;
 767         quint32 n;
 768
 769         /**
 770          * Functions
 771          */
 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) {}
 776
 777         inline bool atEnd() const { return !n; }
 778
 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(); }
 782
 783         const Fragment *operator*()  const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
 784         const Fragment *operator->()  const { Q_ASSERT(!atEnd()); return pt->fragment(n); }
 785
 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); }
 789
 790         ConstIterator& operator++() {
 791             n = pt->data.next(n);
 792             return *this;
 793         }
 794         ConstIterator& operator--() {
 795             n = pt->data.previous(n);
 796             return *this;
 797         }
 798     };
 799
 800
 801     QFragmentMap() {}
 802     ~QFragmentMap()
 803     {
 804         if (!data.fragments)
 805             return; // in case of out-of-memory, we won't have fragments
 806         for (Iterator it = begin(); !it.atEnd(); ++it)
 807             it.value()->free();
 808     }
 809
 810     inline void clear() {
 811         for (Iterator it = begin(); !it.atEnd(); ++it)
 812             it.value()->free();
 813         data.init();
 814     }
 815
 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); }
 820
 821     inline ConstIterator last() const { return ConstIterator(this, data.maximum(data.root())); }
 822
 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); }
 826
 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)); }
 829
 830     uint findNode(int k, uint field = 0) const { return data.findNode(k, field); }
 831
 832     uint insert_single(int key, uint length)
 833     {
 834         uint f = data.insert_single(key, length);
 835         if (f != 0) {
 836             Fragment *frag = fragment(f);
 837             Q_ASSERT(frag);
 838             frag->initialize();
 839         }
 840         return f;
 841     }
 842     uint erase_single(uint f)
 843     {
 844       if (f != 0) {
 845           Fragment *frag = fragment(f);
 846           Q_ASSERT(frag);
 847           frag->free();
 848       }
 849       return data.erase_single(f);
 850     }
 851
 852     inline Fragment *fragment(uint index) {
 853         Q_ASSERT(index != 0);
 854         return data.fragment(index);
 855     }
 856     inline const Fragment *fragment(uint index) const {
 857         Q_ASSERT(index != 0);
 858         return data.fragment(index);
 859     }
 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);
 869           Q_ASSERT(frag);
 870           frag->invalidate();
 871       }
 872     }
 873
 874     inline int firstNode() const { return data.minimum(data.root()); }
 875
 876 private:
 877     friend class Iterator;
 878     friend class ConstIterator;
 879
 880     QFragmentMapData<Fragment> data;
 881
 882     QFragmentMap(const QFragmentMap& m);
 883     QFragmentMap& operator= (const QFragmentMap& m);
 884 };
 885
 886 QT_END_NAMESPACE
 887
 888 #endif // QFRAGMENTMAP_P_H