← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/gui/text/qfragmentmap.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gui/text/qfragmentmap.cpp
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
 
4
**
 
5
** This file is part of the text module of the Qt Toolkit.
 
6
**
 
7
** This file may be distributed under the terms of the Q Public License
 
8
** as defined by Trolltech AS of Norway and appearing in the file
 
9
** LICENSE.QPL included in the packaging of this file.
 
10
**
 
11
** This file may be distributed and/or modified under the terms of the
 
12
** GNU General Public License version 2 as published by the Free Software
 
13
** Foundation and appearing in the file LICENSE.GPL included in the
 
14
** packaging of this file.
 
15
**
 
16
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
 
17
**   information about Qt Commercial License Agreements.
 
18
** See http://www.trolltech.com/qpl/ for QPL licensing information.
 
19
** See http://www.trolltech.com/gpl/ for GPL licensing information.
 
20
**
 
21
** Contact info@trolltech.com if any conditions of this licensing are
 
22
** not clear to you.
 
23
**
 
24
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 
25
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 
26
**
 
27
****************************************************************************/
 
28
 
 
29
#include <private/qtools_p.h>
 
30
 
 
31
#include "qfragmentmap_p.h"
 
32
 
 
33
#include <stdlib.h>
 
34
#include <new>
 
35
 
 
36
#define F(x) (*fragment(x))
 
37
#define X (*fragment(x))
 
38
#define Y (*fragment(y))
 
39
#define Z (*fragment(z))
 
40
#define W (*fragment(w))
 
41
#define N (*fragment(n))
 
42
#define P (*fragment(p))
 
43
#define PP (*fragment(pp))
 
44
 
 
45
#ifdef QT_QMAP_DEBUG
 
46
#define PMDEBUG qDebug
 
47
void QFragmentMap::inorder(uint x, int level) {
 
48
    if (X.left)
 
49
        inorder(X.left, level + 1);
 
50
    for (int i = 0; i < level; ++i)
 
51
        std::cout << "    ";
 
52
    std::cout << "this=" << x << " Key=" << key(x) << " size_left=" << X.size_left
 
53
              << " size=" << X.size
 
54
              << " textPos=" << X.position << (X.color == Red ? " Red" : " Black")
 
55
              << std::endl;
 
56
    if (X.right)
 
57
        inorder(X.right, level + 1);
 
58
}
 
59
void QFragmentMap::check()
 
60
{
 
61
    Q_ASSERT((head->node_count == 0 && head->root == 0)
 
62
             || (head->node_count != 0 && head->root != 0 && F(head->root).parent == 0));
 
63
 
 
64
    ConstIterator it = begin();
 
65
    int key = 0;
 
66
    for (; it != end(); ++it) {
 
67
        Q_ASSERT(key == it.key());
 
68
        key += (*it)->size;
 
69
    }
 
70
}
 
71
#else
 
72
#define PMDEBUG if(0)qDebug
 
73
inline void inorder() {}
 
74
inline void check() {}
 
75
#endif
 
76
 
 
77
#define TAG(a,b,c,d) (((quint32)a) << 24) | (((quint32)b) << 16) | (((quint32)c) << 8) | d;
 
78
 
 
79
QFragmentMapData::QFragmentMapData(uint fs)
 
80
{
 
81
    fragmentSize = qMax<uint>(fs, sizeof(Header));
 
82
    init();
 
83
}
 
84
 
 
85
void QFragmentMapData::init()
 
86
{
 
87
    fragments = (char *)malloc(64*fragmentSize);
 
88
    head->tag = TAG('p', 'm', 'a', 'p');
 
89
    head->root = 0;
 
90
    head->freelist = 1;
 
91
    head->node_count = 0;
 
92
    head->allocated = 64;
 
93
    // mark all items to the right as unused
 
94
    F(head->freelist).right = 0;
 
95
#ifndef QT_NO_DEBUG
 
96
    for (uint i = 1; i < head->allocated; ++i)
 
97
        F(i).parent = 0xdeadbeef;
 
98
#endif
 
99
}
 
100
 
 
101
QFragmentMapData::~QFragmentMapData()
 
102
{
 
103
    free(head);
 
104
}
 
105
 
 
106
uint QFragmentMapData::createFragment()
 
107
{
 
108
    Q_ASSERT(head->freelist <= head->allocated);
 
109
 
 
110
    uint freePos = head->freelist;
 
111
    if (freePos == head->allocated) {
 
112
        // need to create some free space
 
113
        uint needed = qAllocMore((freePos+1)*fragmentSize, 0);
 
114
        Q_ASSERT(needed/fragmentSize > head->allocated);
 
115
        fragments = (char *)realloc(fragments, needed);
 
116
        head->allocated = needed/fragmentSize;
 
117
        F(freePos).right = 0;
 
118
#ifndef QT_NO_DEBUG
 
119
        for (uint i = freePos; i < head->allocated; ++i)
 
120
            F(i).parent = 0xdeadbeef;
 
121
#endif
 
122
    }
 
123
 
 
124
    uint nextPos = F(freePos).right;
 
125
    if (!nextPos) {
 
126
        nextPos = freePos+1;
 
127
        if (nextPos < head->allocated)
 
128
            F(nextPos).right = 0;
 
129
    }
 
130
 
 
131
    head->freelist = nextPos;
 
132
 
 
133
#ifndef QT_NO_DEBUG
 
134
    Q_ASSERT(F(freePos).parent == 0xdeadbeef);
 
135
    F(freePos).parent = 0;
 
136
    if (nextPos < head->allocated) {
 
137
        Q_ASSERT(F(nextPos).parent == 0xdeadbeef);
 
138
    }
 
139
#endif
 
140
 
 
141
    ++head->node_count;
 
142
 
 
143
    PMDEBUG("===> createFragment at %d", freePos);
 
144
    return freePos;
 
145
}
 
146
 
 
147
void QFragmentMapData::freeFragment(uint i)
 
148
{
 
149
    PMDEBUG("===> freeFragment at %d", i);
 
150
#ifndef QT_NO_DEBUG
 
151
    Q_ASSERT(F(i).parent != 0xdeadbeef);
 
152
    if (head->freelist < head->allocated) {
 
153
        Q_ASSERT(F(head->freelist).parent == 0xdeadbeef);
 
154
    }
 
155
    F(i).parent = 0xdeadbeef;
 
156
#endif
 
157
    F(i).right = head->freelist;
 
158
    head->freelist = i;
 
159
 
 
160
    --head->node_count;
 
161
}
 
162
 
 
163
 
 
164
uint QFragmentMapData::next(uint n) const {
 
165
    Q_ASSERT(n);
 
166
    if (N.right) {
 
167
        n = N.right;
 
168
        while (N.left)
 
169
            n = N.left;
 
170
    } else {
 
171
        uint y = N.parent;
 
172
        while (N.parent && n == Y.right) {
 
173
            n = y;
 
174
            y = Y.parent;
 
175
        }
 
176
        n = y;
 
177
    }
 
178
    return n;
 
179
}
 
180
 
 
181
uint QFragmentMapData::previous(uint n) const {
 
182
    if (!n)
 
183
        return maximum(root());
 
184
 
 
185
    if (N.left) {
 
186
        n = N.left;
 
187
        while (N.right)
 
188
            n = N.right;
 
189
    } else {
 
190
        uint y = N.parent;
 
191
        while (N.parent && n == Y.left) {
 
192
            n = y;
 
193
            y = Y.parent;
 
194
        }
 
195
        n = y;
 
196
    }
 
197
    return n;
 
198
}
 
199
 
 
200
 
 
201
/*
 
202
     x              y
 
203
      \            / \
 
204
       y    -->   x   b
 
205
      / \          \
 
206
     a   b          a
 
207
*/
 
208
void QFragmentMapData::rotateLeft(uint x)
 
209
{
 
210
    uint p = X.parent;
 
211
    uint y = X.right;
 
212
    PMDEBUG("    rotateLeft on x=%d (y=%d, p=%d)", x, y, p);
 
213
 
 
214
 
 
215
    if (y) {
 
216
        X.right = Y.left;
 
217
        if (Y.left)
 
218
            F(Y.left).parent = x;
 
219
        Y.left = x;
 
220
        Y.parent = p;
 
221
    } else {
 
222
        X.right = 0;
 
223
    }
 
224
    if (!p) {
 
225
        Q_ASSERT(head->root == x);
 
226
        head->root = y;
 
227
    }
 
228
    else if (x == P.left)
 
229
        P.left = y;
 
230
    else
 
231
        P.right = y;
 
232
    X.parent = y;
 
233
    Y.size_left += X.size_left + X.size;
 
234
 
 
235
    inorder();
 
236
    check();
 
237
}
 
238
 
 
239
 
 
240
/*
 
241
         x          y
 
242
        /          / \
 
243
       y    -->   a   x
 
244
      / \            /
 
245
     a   b          b
 
246
*/
 
247
void QFragmentMapData::rotateRight(uint x)
 
248
{
 
249
    uint y = X.left;
 
250
    uint p = X.parent;
 
251
    PMDEBUG("    rotateRight on x=%d (y=%d, p=%d)", x, y, p);
 
252
 
 
253
    if (y) {
 
254
        X.left = Y.right;
 
255
        if (Y.right)
 
256
            F(Y.right).parent = x;
 
257
        Y.right = x;
 
258
        Y.parent = p;
 
259
    } else {
 
260
        X.left = 0;
 
261
    }
 
262
    if (!p) {
 
263
        Q_ASSERT(head->root == x);
 
264
        head->root = y;
 
265
    }
 
266
    else if (x == P.right)
 
267
        P.right = y;
 
268
    else
 
269
        P.left = y;
 
270
    X.parent = y;
 
271
    X.size_left -= Y.size_left + Y.size;
 
272
 
 
273
    inorder();
 
274
    check();
 
275
}
 
276
 
 
277
 
 
278
void QFragmentMapData::rebalance(uint x)
 
279
{
 
280
    X.color = Red;
 
281
 
 
282
    PMDEBUG("  -> rebalance x=%d", x);
 
283
    inorder();
 
284
 
 
285
    while (X.parent && F(X.parent).color == Red) {
 
286
        uint p = X.parent;
 
287
        uint pp = P.parent;
 
288
        Q_ASSERT(pp);
 
289
        if (p == PP.left) {
 
290
            uint y = PP.right;
 
291
            if (y && Y.color == Red) {
 
292
                P.color = Black;
 
293
                Y.color = Black;
 
294
                PP.color = Red;
 
295
                x = pp;
 
296
            } else {
 
297
                if (x == P.right) {
 
298
                    x = p;
 
299
                    rotateLeft(x);
 
300
                    p = X.parent;
 
301
                    pp = P.parent;
 
302
                }
 
303
                P.color = Black;
 
304
                if (pp) {
 
305
                    PP.color = Red;
 
306
                    rotateRight(pp);
 
307
                }
 
308
            }
 
309
        } else {
 
310
            uint y = PP.left;
 
311
            if (y && Y.color == Red) {
 
312
                P.color = Black;
 
313
                Y.color = Black;
 
314
                PP.color = Red;
 
315
                x = pp;
 
316
            } else {
 
317
                if (x == P.left) {
 
318
                    x = p;
 
319
                    rotateRight(x);
 
320
                    p = X.parent;
 
321
                    pp = P.parent;
 
322
                }
 
323
                P.color = Black;
 
324
                if (pp) {
 
325
                    PP.color = Red;
 
326
                    rotateLeft(pp);
 
327
                }
 
328
            }
 
329
        }
 
330
    }
 
331
    F(root()).color = Black;
 
332
    check();
 
333
}
 
334
 
 
335
 
 
336
uint QFragmentMapData::erase_single(uint z)
 
337
{
 
338
    uint w = previous(z);
 
339
    uint y = z;
 
340
    uint x;
 
341
    uint p;
 
342
 
 
343
    if (!Y.left) {
 
344
        x = Y.right;
 
345
    } else if (!Y.right) {
 
346
        x = Y.left;
 
347
    } else {
 
348
        y = Y.right;
 
349
        while (Y.left)
 
350
            y = Y.left;
 
351
        x = Y.right;
 
352
    }
 
353
 
 
354
    PMDEBUG("removeAndRebalance on %d (x=%d, y=%d)", z, x, y);
 
355
    inorder();
 
356
 
 
357
    if (y != z) {
 
358
        F(Z.left).parent = y;
 
359
        Y.left = Z.left;
 
360
        Y.size_left = Z.size_left;
 
361
        if (y != Z.right) {
 
362
            /*
 
363
                     z                y
 
364
                    / \              / \
 
365
                   a   b            a   b
 
366
                      /                /
 
367
                    ...     -->      ...
 
368
                    /                /
 
369
                   y                x
 
370
                  / \
 
371
                 0   x
 
372
             */
 
373
            p = Y.parent;
 
374
            if (x)
 
375
                X.parent = p;
 
376
            P.left = x;
 
377
            Y.right = Z.right;
 
378
            F(Z.right).parent = y;
 
379
            uint n = p;
 
380
            while (n != y) {
 
381
                N.size_left -= Y.size;
 
382
                n = N.parent;
 
383
            }
 
384
        } else {
 
385
            /*
 
386
                     z                y
 
387
                    / \              / \
 
388
                   a   y     -->    a   x
 
389
                      / \
 
390
                     0   x
 
391
             */
 
392
            p = y;
 
393
        }
 
394
        uint zp = Z.parent;
 
395
        if (!zp) {
 
396
            Q_ASSERT(head->root == z);
 
397
            head->root = y;
 
398
        } else if (F(zp).left == z) {
 
399
            F(zp).left = y;
 
400
            F(zp).size_left -= Z.size;
 
401
        } else {
 
402
            F(zp).right = y;
 
403
        }
 
404
        Y.parent = zp;
 
405
        // Swap the colors
 
406
        uint c = Y.color;
 
407
        Y.color = Z.color;
 
408
        Z.color = c;
 
409
        y = z;
 
410
    } else {
 
411
        /*
 
412
                p          p            p          p
 
413
               /          /              \          \
 
414
              z    -->   x                z  -->     x
 
415
              |                           |
 
416
              x                           x
 
417
         */
 
418
        p = Z.parent;
 
419
        if (x)
 
420
            X.parent = p;
 
421
        if (!p) {
 
422
            Q_ASSERT(head->root == z);
 
423
            head->root = x;
 
424
        } else if (P.left == z) {
 
425
            P.left = x;
 
426
            P.size_left -= Z.size;
 
427
        } else {
 
428
            P.right = x;
 
429
        }
 
430
    }
 
431
    uint n = z;
 
432
    while (N.parent) {
 
433
        uint p = N.parent;
 
434
        if (P.left == n) {
 
435
            PMDEBUG("reducing size_left of %d by %d", N.parent, Z.size);
 
436
            P.size_left -= Z.size;
 
437
        }
 
438
        n = p;
 
439
    }
 
440
 
 
441
    freeFragment(z);
 
442
    PMDEBUG("after removal");
 
443
    inorder();
 
444
    check();
 
445
 
 
446
 
 
447
    if (Y.color != Red) {
 
448
        while (X.parent && (x == 0 || X.color == Black)) {
 
449
            if (x == P.left) {
 
450
                uint w = P.right;
 
451
                if (W.color == Red) {
 
452
                    W.color = Black;
 
453
                    P.color = Red;
 
454
                    rotateLeft(p);
 
455
                    w = P.right;
 
456
                }
 
457
                if ((W.left == 0 || F(W.left).color == Black) &&
 
458
                    (W.right == 0 || F(W.right).color == Black)) {
 
459
                    W.color = Red;
 
460
                    x = p;
 
461
                    p = X.parent;
 
462
                } else {
 
463
                    if (W.right == 0 || F(W.right).color == Black) {
 
464
                        if (W.left)
 
465
                            F(W.left).color = Black;
 
466
                        W.color = Red;
 
467
                        rotateRight(P.right);
 
468
                        w = P.right;
 
469
                    }
 
470
                    W.color = P.color;
 
471
                    P.color = Black;
 
472
                    if (W.right)
 
473
                        F(W.right).color = Black;
 
474
                    rotateLeft(p);
 
475
                    break;
 
476
                }
 
477
            } else {
 
478
                uint w = P.left;
 
479
                if (W.color == Red) {
 
480
                    W.color = Black;
 
481
                    P.color = Red;
 
482
                    rotateRight(p);
 
483
                    w = P.left;
 
484
                }
 
485
                if ((W.right == 0 || F(W.right).color == Black) &&
 
486
                    (W.left == 0 || F(W.left).color == Black)) {
 
487
                    W.color = Red;
 
488
                    x = p;
 
489
                    p = X.parent;
 
490
                } else {
 
491
                    if (W.left == 0 || F(W.left).color == Black) {
 
492
                        if (W.right)
 
493
                            F(W.right).color = Black;
 
494
                        W.color = Red;
 
495
                        rotateLeft(P.left);
 
496
                        w = P.left;
 
497
                    }
 
498
                    W.color = P.color;
 
499
                    P.color = Black;
 
500
                    if (W.left)
 
501
                        F(W.left).color = Black;
 
502
                    rotateRight(p);
 
503
                    break;
 
504
                }
 
505
            }
 
506
        }
 
507
        if (x)
 
508
            X.color = Black;
 
509
    }
 
510
 
 
511
    PMDEBUG("after rebalance");
 
512
    inorder();
 
513
    check();
 
514
 
 
515
    return w;
 
516
}
 
517
 
 
518
uint QFragmentMapData::findNode(int k) const
 
519
{
 
520
    uint x = root();
 
521
 
 
522
    uint s = k;
 
523
    while (x) {
 
524
        if (sizeLeft(x) <= s) {
 
525
            if (s < sizeLeft(x) + size(x))
 
526
                return x;
 
527
            s -= sizeLeft(x) + size(x);
 
528
            x = X.right;
 
529
        } else {
 
530
            x = X.left;
 
531
        }
 
532
    }
 
533
    return 0;
 
534
}
 
535
 
 
536
uint QFragmentMapData::insert_single(int key, uint length)
 
537
{
 
538
    Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);
 
539
 
 
540
    uint z = createFragment();
 
541
 
 
542
    Z.size = length;
 
543
    Z.left = 0;
 
544
    Z.right = 0;
 
545
    Z.size_left = 0;
 
546
 
 
547
    PMDEBUG("inserting with key %d", key);
 
548
    uint y = 0;
 
549
    uint x = root();
 
550
 
 
551
    Q_ASSERT(!x || X.parent == 0);
 
552
 
 
553
    uint s = key;
 
554
//     inorder();
 
555
    bool right = false;
 
556
    while (x) {
 
557
        y = x;
 
558
//          PMDEBUG("x=%p: x->size_left=%d, key=%d, s=%d", x, x->size_left, x->key(), s);
 
559
        if (s <= X.size_left) {
 
560
            x = X.left;
 
561
            right = false;
 
562
        } else {
 
563
            s -= X.size_left + X.size;
 
564
            x = X.right;
 
565
            right = true;
 
566
        }
 
567
    }
 
568
//     if (y)
 
569
//         PMDEBUG("  y=%p: y->size_left=%d, y->key=%d s=%d", y, y->size_left, y ? y->key() : -1, s);
 
570
 
 
571
    Z.parent = y;
 
572
    if (!y) {
 
573
        head->root = z;
 
574
    } else if (!right) {
 
575
//          PMDEBUG("inserting left");
 
576
        Y.left = z;
 
577
        Y.size_left = Z.size;
 
578
    } else {
 
579
//          PMDEBUG("inserting right");
 
580
        Y.right = z;
 
581
    }
 
582
    while (y && Y.parent) {
 
583
        uint p = Y.parent;
 
584
        if (P.left == y)
 
585
            P.size_left += Z.size;
 
586
        y = p;
 
587
    }
 
588
//     PMDEBUG("before rebalance");
 
589
//     inorder();
 
590
    rebalance(z);
 
591
 
 
592
    inorder();
 
593
    PMDEBUG("end insert\n");
 
594
 
 
595
    return z;
 
596
}
 
597
 
 
598
 
 
599
int QFragmentMapData::length() const {
 
600
    uint root = this->root();
 
601
    return root ? sizeLeft(root) + size(root) + sizeRight(root) : 0;
 
602
}
 
603