← Back to branch summary

~canonical-dx-team/ubuntu/maverick/gtk+2.0/menuproxy

« back to all changes in this revision

Viewing changes to gdk/linux-fb/mispans.c

  • Committer: Bazaar Package Importer
  • Author(s): Sebastien Bacher
  • Date: 2007-05-04 12:24:25 UTC
  • mfrom: (1.1.21 upstream)
  • Revision ID: james.westby@ubuntu.com-20070504122425-0m8midgzrp40y8w2
Tags: 2.10.12-1ubuntu1
* Sync with Debian
* New upstream version:
  Fixed bugs:
  - 379414 file chooser warnings when changing path in the entry
  - 418585 GtkFileChooserDefault sizing code is not DPI independent
  - 419568 Crash in search if start with special letter
  - 435062 build dies with icon cache validation
  - 379399 Segfault to call gtk_print_operation_run twice.
  - 387889 cups backend has problems when there are too many printers
  - 418531 invalid read to gtkicontheme.c gtk_icon_theme_lookup_icon...
  - 423916 crash in color scheme code
  - 424042 Segmentation fault while quickly pressing Alt+arrows
  - 415260 Protect against negative indices when setting values in G...
  - 419171 XGetVisualInfo() may not set nxvisuals
  - 128852 Gdk cursors don't look good on win32
  - 344657 Ctrl-H doesn't toggle "Show Hidden Files" setting
  - 345345 PrintOperation::paginate is not emitted for class handler
  - 347567 GtkPrintOperation::end-print is not emitted if it's cance...
  - 369112 gtk_ui_manager_add_ui should accept unnamed separator
  - 392015 Selected menu item invisible on Windows Vista
  - 399253 MS-Windows Theme Bottom Tab placement rendering glitches
  - 399425 gtk_input_dialog_fill_axes() adds child to gtkscrolledwin...
  - 403251 [patch] little memory leak in GtkPrintJob
  - 403267 [patch] memory leak in GtkPageSetupUnixDialog
  - 403470 MS-Windows Theme tab placement other than on top leaks a ...
  - 404506 Windows system fonts that have multi-byte font names cann...
  - 405089 Incorrect window placement for GtkEventBox private window
  - 405515 Minor leak in gtkfilesystemmodel.c
  - 405539 gdk_pixbuf_save() for PNG saver can return FALSE without ...
  - 415681 gdk_window_clear_area includes an extra line and column o...
  - 418219 GtkRecentChooser should apply filter before sorting and c...
  - 418403 Scroll to printer after selecting it from settings
  - 421985 _gtk_print_operation_platform_backend_launch_preview
  - 421990 gtk_print_job_get_surface
  - 421993 gtk_print_operation_init
  - 423064 Conditional jump or move depends on uninitialised value(s...
  - 423722 Fix printing header in gtk-demo
  - 424168 gtk_print_operation_run on async preview
  - 425655 Don't install gtk+-unix-print-2.0.pc on non-UNIX platforms
  - 425786 GDK segfaults if XineramaQueryScreens fails
  - 428665 Lpr Backend gets stuck in infinite loop during gtk_enumer...
  - 429902 GtkPrintOperation leaks cairo contextes
  - 431997 First delay of GdkPixbufAnimationIter is wrong
  - 433242 Inconsistent scroll arrow position calculations
  - 433972 Placing gtk.Expander inside a gtk.TextView() changes gtk....
  - 434261 _gtk_toolbar_elide_underscores incorrectly handles some s...
  - 383354 ctrl-L should make 'Location' entry disappear
  - 418673 gtk_recent_manager_add_item
  - 429732 gtk_accel_group_finalize accesses invalid memory
  - 435028 WM_CLIENT_LEADER is wrong on the leader_window
  - 431067 Background of the header window is not updated
  - 338843 add recent files support inside the ui manager
  - 148535 add drop shadow to menus, tooltips, etc. under Windows XP
* debian/control.in:
  - Conflicts on ubuntulooks (<= 0.9.11-1)
* debian/patches/15_default-fallback-icon-theme.patch:
  - patch from Debian, fallback on gnome icon theme

Show diffs side-by-side

added added

removed removed

Lines of Context:
gdk/linux-fb/mispans.c
 
1
/* $XFree86: xc/programs/Xserver/mi/mispans.c,v 3.1 1998/10/04 09:39:33 dawes Exp $ */
 
2
/***********************************************************
 
3
 
 
4
Copyright 1989, 1998  The Open Group
 
5
 
 
6
All Rights Reserved.
 
7
 
 
8
The above copyright notice and this permission notice shall be included in
 
9
all copies or substantial portions of the Software.
 
10
 
 
11
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
12
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
13
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 
14
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 
15
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 
16
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 
17
 
 
18
Except as contained in this notice, the name of The Open Group shall not be
 
19
used in advertising or otherwise to promote the sale, use or other dealings
 
20
in this Software without prior written authorization from The Open Group.
 
21
 
 
22
 
 
23
Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
 
24
 
 
25
                        All Rights Reserved
 
26
 
 
27
Permission to use, copy, modify, and distribute this software and its 
 
28
documentation for any purpose and without fee is hereby granted, 
 
29
provided that the above copyright notice appear in all copies and that
 
30
both that copyright notice and this permission notice appear in 
 
31
supporting documentation, and that the name of Digital not be
 
32
used in advertising or publicity pertaining to distribution of the
 
33
software without specific, written prior permission.  
 
34
 
 
35
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 
36
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
 
37
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
 
38
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
 
39
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 
40
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 
41
SOFTWARE.
 
42
 
 
43
******************************************************************/
 
44
 
 
45
/* $TOG: mispans.c /main/7 1998/02/09 14:48:44 kaleb $ */
 
46
 
 
47
#include <config.h>
 
48
#include "mi.h"
 
49
#include "mispans.h"
 
50
#include <string.h>             /* for memmove */
 
51
 
 
52
/*
 
53
 
 
54
These routines maintain lists of Spans, in order to implement the
 
55
``touch-each-pixel-once'' rules of wide lines and arcs.
 
56
 
 
57
Written by Joel McCormack, Summer 1989.
 
58
 
 
59
*/
 
60
 
 
61
 
 
62
void miInitSpanGroup(SpanGroup *spanGroup)
 
63
{
 
64
    spanGroup->size = 0;
 
65
    spanGroup->count = 0;
 
66
    spanGroup->group = NULL;
 
67
    spanGroup->ymin = SHRT_MAX;
 
68
    spanGroup->ymax = SHRT_MIN;
 
69
} /* InitSpanGroup */
 
70
 
 
71
#define YMIN(spans) (spans->points[0].y)
 
72
#define YMAX(spans)  (spans->points[spans->count-1].y)
 
73
 
 
74
void miSubtractSpans (SpanGroup *spanGroup, Spans *sub)
 
75
{
 
76
    int         i, subCount, spansCount;
 
77
    int         ymin, ymax, xmin, xmax;
 
78
    Spans       *spans;
 
79
    GdkSpan*    subPt, *spansPt;
 
80
    int         extra;
 
81
 
 
82
    ymin = YMIN(sub);
 
83
    ymax = YMAX(sub);
 
84
    spans = spanGroup->group;
 
85
    for (i = spanGroup->count; i; i--, spans++) {
 
86
        if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
 
87
            subCount = sub->count;
 
88
            subPt = sub->points;
 
89
            spansCount = spans->count;
 
90
            spansPt = spans->points;
 
91
            extra = 0;
 
92
            for (;;)
 
93
            {
 
94
                while (spansCount && spansPt->y < subPt->y)
 
95
                {
 
96
                    spansPt++; spansCount--;
 
97
                }
 
98
                if (!spansCount)
 
99
                    break;
 
100
                while (subCount && subPt->y < spansPt->y)
 
101
                {
 
102
                    subPt++; subCount--;
 
103
                }
 
104
                if (!subCount)
 
105
                    break;
 
106
                if (subPt->y == spansPt->y)
 
107
                {
 
108
                    xmin = subPt->x;
 
109
                    xmax = xmin + subPt->width;
 
110
                    if (xmin >= (spansPt->x + spansPt->width) || spansPt->x >= xmax)
 
111
                    {
 
112
                        ;
 
113
                    }
 
114
                    else if (xmin <= spansPt->x)
 
115
                    {
 
116
                        if (xmax >= (spansPt->x + spansPt->width))
 
117
                        {
 
118
                            g_memmove (spansPt, spansPt + 1, sizeof *spansPt * (spansCount - 1));
 
119
                            spansPt--;
 
120
                            spans->count--;
 
121
                            extra++;
 
122
                        }
 
123
                        else 
 
124
                        {
 
125
                          spansPt->width -= xmax - spansPt->x;
 
126
                          spansPt->x = xmax;
 
127
                        }
 
128
                    }
 
129
                    else
 
130
                    {
 
131
                        if (xmax >= (spansPt->x + spansPt->width))
 
132
                        {
 
133
                          spansPt->width = xmin - spansPt->x;
 
134
                        }
 
135
                        else
 
136
                        {
 
137
                            if (!extra) {
 
138
                                GdkSpan* newPt;
 
139
 
 
140
#define EXTRA 8
 
141
                                newPt = (GdkSpan*) g_realloc (spans->points, (spans->count + EXTRA) * sizeof (GdkSpan));
 
142
                                if (!newPt)
 
143
                                    break;
 
144
                                spansPt = newPt + (spansPt - spans->points);
 
145
                                spans->points = newPt;
 
146
                                extra = EXTRA;
 
147
                            }
 
148
                            g_memmove (spansPt + 1, spansPt, sizeof *spansPt * (spansCount));
 
149
                            spans->count++;
 
150
                            extra--;
 
151
                            spansPt->width = xmin - spansPt->x;
 
152
                            spansPt++;
 
153
                            spansPt->width -= xmax - spansPt->x;
 
154
                            spansPt->x = xmax;
 
155
                        }
 
156
                    }
 
157
                }
 
158
                spansPt++; spansCount--;
 
159
            }
 
160
        }
 
161
    }
 
162
}
 
163
    
 
164
void miAppendSpans(SpanGroup *spanGroup, SpanGroup *otherGroup, Spans *spans)
 
165
{
 
166
    register    int ymin, ymax;
 
167
    register    int spansCount;
 
168
 
 
169
    spansCount = spans->count;
 
170
    if (spansCount > 0) {
 
171
        if (spanGroup->size == spanGroup->count) {
 
172
            spanGroup->size = (spanGroup->size + 8) * 2;
 
173
            spanGroup->group = (Spans *)
 
174
                g_realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
 
175
         }
 
176
 
 
177
        spanGroup->group[spanGroup->count] = *spans;
 
178
        (spanGroup->count)++;
 
179
        ymin = spans->points[0].y;
 
180
        if (ymin < spanGroup->ymin) spanGroup->ymin = ymin;
 
181
        ymax = spans->points[spansCount - 1].y;
 
182
        if (ymax > spanGroup->ymax) spanGroup->ymax = ymax;
 
183
        if (otherGroup &&
 
184
            otherGroup->ymin < ymax &&
 
185
            ymin < otherGroup->ymax)
 
186
        {
 
187
            miSubtractSpans (otherGroup, spans);
 
188
        }
 
189
    }
 
190
    else
 
191
    {
 
192
        g_free (spans->points);
 
193
    }
 
194
} /* AppendSpans */
 
195
 
 
196
void miFreeSpanGroup(SpanGroup *spanGroup)
 
197
{
 
198
    if (spanGroup->group != NULL) g_free(spanGroup->group);
 
199
}
 
200
 
 
201
static void QuickSortSpansX(register GdkSpan points[], register int numSpans)
 
202
{
 
203
    register int            x;
 
204
    register int            i, j, m;
 
205
    register GdkSpan*    r;
 
206
 
 
207
/* Always called with numSpans > 1 */
 
208
/* Sorts only by x, as all y should be the same */
 
209
 
 
210
#define ExchangeSpans(a, b)                                 \
 
211
{                                                           \
 
212
    GdkSpan     tpt;                                \
 
213
                                                            \
 
214
    tpt = points[a]; points[a] = points[b]; points[b] = tpt;    \
 
215
}
 
216
 
 
217
    do {
 
218
        if (numSpans < 9) {
 
219
            /* Do insertion sort */
 
220
            register int xprev;
 
221
 
 
222
            xprev = points[0].x;
 
223
            i = 1;
 
224
            do { /* while i != numSpans */
 
225
                x = points[i].x;
 
226
                if (xprev > x) {
 
227
                    /* points[i] is out of order.  Move into proper location. */
 
228
                    GdkSpan tpt;
 
229
                    int     k;
 
230
 
 
231
                    for (j = 0; x >= points[j].x; j++) {}
 
232
                    tpt = points[i];
 
233
                    for (k = i; k != j; k--) {
 
234
                        points[k] = points[k-1];
 
235
                    }
 
236
                    points[j] = tpt;
 
237
                    x = points[i].x;
 
238
                } /* if out of order */
 
239
                xprev = x;
 
240
                i++;
 
241
            } while (i != numSpans);
 
242
            return;
 
243
        }
 
244
 
 
245
        /* Choose partition element, stick in location 0 */
 
246
        m = numSpans / 2;
 
247
        if (points[m].x > points[0].x)          ExchangeSpans(m, 0);
 
248
        if (points[m].x > points[numSpans-1].x) ExchangeSpans(m, numSpans-1);
 
249
        if (points[m].x > points[0].x)          ExchangeSpans(m, 0);
 
250
        x = points[0].x;
 
251
 
 
252
        /* Partition array */
 
253
        i = 0;
 
254
        j = numSpans;
 
255
        do {
 
256
            r = &(points[i]);
 
257
            do {
 
258
                r++;
 
259
                i++;
 
260
            } while (i != numSpans && r->x < x);
 
261
            r = &(points[j]);
 
262
            do {
 
263
                r--;
 
264
                j--;
 
265
            } while (x < r->x);
 
266
            if (i < j) ExchangeSpans(i, j);
 
267
        } while (i < j);
 
268
 
 
269
        /* Move partition element back to middle */
 
270
        ExchangeSpans(0, j);
 
271
 
 
272
        /* Recurse */
 
273
        if (numSpans-j-1 > 1)
 
274
            QuickSortSpansX(&points[j+1], numSpans-j-1);
 
275
        numSpans = j;
 
276
    } while (numSpans > 1);
 
277
} /* QuickSortSpans */
 
278
 
 
279
 
 
280
static int UniquifySpansX(Spans *spans, register GdkSpan *newPoints)
 
281
{
 
282
    register int newx1, newx2, oldpt, i, y;
 
283
    GdkSpan    *oldPoints, *startNewPoints = newPoints;
 
284
 
 
285
/* Always called with numSpans > 1 */
 
286
/* Uniquify the spans, and stash them into newPoints and newWidths.  Return the
 
287
   number of unique spans. */
 
288
 
 
289
 
 
290
    oldPoints = spans->points;
 
291
 
 
292
    y = oldPoints->y;
 
293
    newx1 = oldPoints->x;
 
294
    newx2 = newx1 + oldPoints->width;
 
295
 
 
296
    for (i = spans->count-1; i != 0; i--) {
 
297
        oldPoints++;
 
298
        oldpt = oldPoints->x;
 
299
        if (oldpt > newx2) {
 
300
            /* Write current span, start a new one */
 
301
            newPoints->x = newx1;
 
302
            newPoints->y = y;
 
303
            newPoints->width = newx2 - newx1;
 
304
            newPoints++;
 
305
            newx1 = oldpt;
 
306
            newx2 = oldpt + oldPoints->width;
 
307
        } else {
 
308
            /* extend current span, if old extends beyond new */
 
309
            oldpt = oldpt + oldPoints->width;
 
310
            if (oldpt > newx2) newx2 = oldpt;
 
311
        }
 
312
    } /* for */
 
313
 
 
314
    /* Write final span */
 
315
    newPoints->x = newx1;
 
316
    newPoints->width = newx2 - newx1;
 
317
    newPoints->y = y;
 
318
 
 
319
    return (newPoints - startNewPoints) + 1;
 
320
} /* UniquifySpansX */
 
321
 
 
322
void
 
323
miDisposeSpanGroup (SpanGroup *spanGroup)
 
324
{
 
325
    int     i;
 
326
    Spans   *spans;
 
327
 
 
328
    for (i = 0; i < spanGroup->count; i++)
 
329
    {
 
330
        spans = spanGroup->group + i;
 
331
        g_free (spans->points);
 
332
    }
 
333
}
 
334
 
 
335
void miFillUniqueSpanGroup(GdkDrawable *pDraw, GdkGC *pGC, SpanGroup *spanGroup)
 
336
{
 
337
    register int    i;
 
338
    register Spans  *spans;
 
339
    register Spans  *yspans;
 
340
    register int    *ysizes;
 
341
    register int    ymin, ylength;
 
342
 
 
343
    /* Outgoing spans for one big call to FillSpans */
 
344
    register GdkSpan*    points;
 
345
    register int            count;
 
346
 
 
347
    if (spanGroup->count == 0) return;
 
348
 
 
349
    if (spanGroup->count == 1) {
 
350
        /* Already should be sorted, unique */
 
351
        spans = spanGroup->group;
 
352
        gdk_fb_fill_spans(pDraw, pGC, spans->points, spans->count, TRUE);
 
353
        g_free(spans->points);
 
354
    }
 
355
    else
 
356
    {
 
357
        /* Yuck.  Gross.  Radix sort into y buckets, then sort x and uniquify */
 
358
        /* This seems to be the fastest thing to do.  I've tried sorting on
 
359
           both x and y at the same time rather than creating into all those
 
360
           y buckets, but it was somewhat slower. */
 
361
 
 
362
        ymin    = spanGroup->ymin;
 
363
        ylength = spanGroup->ymax - ymin + 1;
 
364
 
 
365
        /* Allocate Spans for y buckets */
 
366
        yspans = (Spans *) g_malloc(ylength * sizeof(Spans));
 
367
        ysizes = (int *) g_malloc(ylength * sizeof (int));
 
368
 
 
369
        if (!yspans || !ysizes)
 
370
        {
 
371
            if (yspans)
 
372
                g_free (yspans);
 
373
            if (ysizes)
 
374
                g_free (ysizes);
 
375
            miDisposeSpanGroup (spanGroup);
 
376
            return;
 
377
        }
 
378
        
 
379
        for (i = 0; i != ylength; i++) {
 
380
            ysizes[i]        = 0;
 
381
            yspans[i].count  = 0;
 
382
            yspans[i].points = NULL;
 
383
        }
 
384
 
 
385
        /* Go through every single span and put it into the correct bucket */
 
386
        count = 0;
 
387
        for (i = 0, spans = spanGroup->group;
 
388
                i != spanGroup->count;
 
389
                i++, spans++) {
 
390
            int         index;
 
391
            int         j;
 
392
 
 
393
            for (j = 0, points = spans->points;
 
394
                 j != spans->count;
 
395
                 j++, points++) {
 
396
                index = points->y - ymin;
 
397
                if (index >= 0 && index < ylength) {
 
398
                    Spans *newspans = &(yspans[index]);
 
399
                    if (newspans->count == ysizes[index]) {
 
400
                        GdkSpan* newpoints;
 
401
                        ysizes[index] = (ysizes[index] + 8) * 2;
 
402
                        newpoints = (GdkSpan*) g_realloc(
 
403
                            newspans->points,
 
404
                            ysizes[index] * sizeof(GdkSpan));
 
405
                        if (!newpoints)
 
406
                        {
 
407
                            int i;
 
408
 
 
409
                            for (i = 0; i < ylength; i++)
 
410
                            {
 
411
                                g_free (yspans[i].points);
 
412
                            }
 
413
                            g_free (yspans);
 
414
                            g_free (ysizes);
 
415
                            miDisposeSpanGroup (spanGroup);
 
416
                            return;
 
417
                        }
 
418
                        newspans->points = newpoints;
 
419
                    }
 
420
                    newspans->points[newspans->count] = *points;
 
421
                    (newspans->count)++;
 
422
                } /* if y value of span in range */
 
423
            } /* for j through spans */
 
424
            count += spans->count;
 
425
            g_free(spans->points);
 
426
            spans->points = NULL;
 
427
        } /* for i thorough Spans */
 
428
 
 
429
        /* Now sort by x and uniquify each bucket into the final array */
 
430
        points = (GdkSpan*) g_malloc(count * sizeof(GdkSpan));
 
431
        if (!points)
 
432
        {
 
433
            int i;
 
434
 
 
435
            for (i = 0; i < ylength; i++)
 
436
            {
 
437
                g_free (yspans[i].points);
 
438
            }
 
439
            g_free (yspans);
 
440
            g_free (ysizes);
 
441
            if (points)
 
442
                g_free (points);
 
443
            return;
 
444
        }
 
445
        count = 0;
 
446
        for (i = 0; i != ylength; i++) {
 
447
            int ycount = yspans[i].count;
 
448
            if (ycount > 0) {
 
449
                if (ycount > 1) {
 
450
                    QuickSortSpansX(yspans[i].points, ycount);
 
451
                    count += UniquifySpansX
 
452
                        (&(yspans[i]), &(points[count]));
 
453
                } else {
 
454
                    points[count] = yspans[i].points[0];
 
455
                    count++;
 
456
                }
 
457
                g_free(yspans[i].points);
 
458
            }
 
459
        }
 
460
 
 
461
        gdk_fb_fill_spans(pDraw, pGC, points, count, TRUE);
 
462
        g_free(points);
 
463
        g_free(yspans);
 
464
        g_free(ysizes);         /* use (DE)ALLOCATE_LOCAL for these? */
 
465
    }
 
466
 
 
467
    spanGroup->count = 0;
 
468
    spanGroup->ymin = SHRT_MAX;
 
469
    spanGroup->ymax = SHRT_MIN;
 
470
}
 
471
 
 
472
 
 
473
void miFillSpanGroup(GdkDrawable *pDraw, GdkGC *pGC, SpanGroup *spanGroup)
 
474
{
 
475
    register int    i;
 
476
    register Spans  *spans;
 
477
 
 
478
    for (i = 0, spans = spanGroup->group; i != spanGroup->count; i++, spans++) {
 
479
      gdk_fb_fill_spans(pDraw, pGC, spans->points, spans->count, TRUE);
 
480
      g_free(spans->points);
 
481
    }
 
482
 
 
483
    spanGroup->count = 0;
 
484
    spanGroup->ymin = SHRT_MAX;
 
485
    spanGroup->ymax = SHRT_MIN;
 
486
} /* FillSpanGroup */