Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
14952 fschmid 1
/* cairo - a vector graphics library with display and print output
2
 *
3
 * Copyright © 2009 Chris Wilson
4
 *
5
 * This library is free software; you can redistribute it and/or
6
 * modify it either under the terms of the GNU Lesser General Public
7
 * License version 2.1 as published by the Free Software Foundation
8
 * (the "LGPL") or, at your option, under the terms of the Mozilla
9
 * Public License Version 1.1 (the "MPL"). If you do not alter this
10
 * notice, a recipient may use your version of this file under either
11
 * the MPL or the LGPL.
12
 *
13
 * You should have received a copy of the LGPL along with this library
14
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
18122 mrdocs 15
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
14952 fschmid 16
 * You should have received a copy of the MPL along with this library
17
 * in the file COPYING-MPL-1.1
18
 *
19
 * The contents of this file are subject to the Mozilla Public License
20
 * Version 1.1 (the "License"); you may not use this file except in
21
 * compliance with the License. You may obtain a copy of the License at
22
 * http://www.mozilla.org/MPL/
23
 *
24
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26
 * the specific language governing rights and limitations.
27
 *
28
 * The Original Code is the cairo graphics library.
29
 *
30
 * The Initial Developer of the Original Code is Chris Wilson.
31
 *
32
 * Contributor(s):
33
 *      Chris Wilson <chris@chris-wilson.co.uk>
34
 *
35
 */
36
 
37
#include "cairoint.h"
38
 
39
#include "cairo-rtree-private.h"
40
 
41
cairo_rtree_node_t *
42
_cairo_rtree_node_create (cairo_rtree_t          *rtree,
43
                          cairo_rtree_node_t     *parent,
44
                          int                     x,
45
                          int                     y,
46
                          int                     width,
47
                          int                     height)
48
{
49
    cairo_rtree_node_t *node;
50
 
51
    node = _cairo_freepool_alloc (&rtree->node_freepool);
52
    if (node == NULL) {
53
        _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
54
        return NULL;
55
    }
56
 
57
    node->children[0] = NULL;
58
    node->parent = parent;
59
    node->owner  = NULL;
60
    node->state  = CAIRO_RTREE_NODE_AVAILABLE;
61
    node->pinned = FALSE;
62
    node->x      = x;
63
    node->y      = y;
64
    node->width  = width;
65
    node->height = height;
66
 
67
    cairo_list_add (&node->link, &rtree->available);
68
 
69
    return node;
70
}
71
 
72
void
73
_cairo_rtree_node_destroy (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
74
{
75
    int i;
76
 
77
    cairo_list_del (&node->link);
78
 
79
    if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
80
        if (node->owner != NULL)
81
            *node->owner = NULL;
82
        if (rtree->evict != NULL)
83
            rtree->evict (node);
84
    } else {
85
        for (i = 0; i < 4 && node->children[i] != NULL; i++)
86
            _cairo_rtree_node_destroy (rtree, node->children[i]);
87
    }
88
 
89
    _cairo_freepool_free (&rtree->node_freepool, node);
90
}
91
 
92
void
93
_cairo_rtree_node_collapse (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
94
{
95
    int i;
96
 
97
    assert (node->pinned == FALSE);
98
 
99
    do {
100
        assert (node->state == CAIRO_RTREE_NODE_DIVIDED);
101
 
102
        for (i = 0;  i < 4 && node->children[i] != NULL; i++)
103
            if (node->children[i]->state != CAIRO_RTREE_NODE_AVAILABLE)
104
                return;
105
 
106
        for (i = 0; i < 4 && node->children[i] != NULL; i++)
107
            _cairo_rtree_node_destroy (rtree, node->children[i]);
108
 
109
        node->children[0] = NULL;
110
        node->state = CAIRO_RTREE_NODE_AVAILABLE;
111
        cairo_list_move (&node->link, &rtree->available);
112
 
113
        node = node->parent;
114
    } while (node != NULL && ! node->pinned);
115
}
116
 
117
cairo_status_t
118
_cairo_rtree_node_insert (cairo_rtree_t *rtree,
119
                          cairo_rtree_node_t *node,
120
                          int width,
121
                          int height,
122
                          cairo_rtree_node_t **out)
123
{
124
    int w, h, i;
125
 
126
    assert (node->state == CAIRO_RTREE_NODE_AVAILABLE);
127
    assert (node->pinned == FALSE);
128
 
129
    if (node->width  - width  > rtree->min_size ||
130
        node->height - height > rtree->min_size)
131
    {
132
        w = node->width  - width;
133
        h = node->height - height;
134
 
135
        i = 0;
136
        node->children[i] = _cairo_rtree_node_create (rtree, node,
137
                                                      node->x, node->y,
138
                                                      width, height);
139
        if (unlikely (node->children[i] == NULL))
140
            return _cairo_error (CAIRO_STATUS_NO_MEMORY);
141
        i++;
142
 
143
        if (w > rtree->min_size) {
144
            node->children[i] = _cairo_rtree_node_create (rtree, node,
145
                                                          node->x + width,
146
                                                          node->y,
147
                                                          w, height);
148
            if (unlikely (node->children[i] == NULL))
149
                return _cairo_error (CAIRO_STATUS_NO_MEMORY);
150
            i++;
151
        }
152
 
153
        if (h > rtree->min_size) {
154
            node->children[i] = _cairo_rtree_node_create (rtree, node,
155
                                                          node->x,
156
                                                          node->y + height,
157
                                                          width, h);
158
            if (unlikely (node->children[i] == NULL))
159
                return _cairo_error (CAIRO_STATUS_NO_MEMORY);
160
            i++;
161
 
162
            if (w > rtree->min_size) {
163
                node->children[i] = _cairo_rtree_node_create (rtree, node,
164
                                                              node->x + width,
165
                                                              node->y + height,
166
                                                              w, h);
167
                if (unlikely (node->children[i] == NULL))
168
                    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
169
                i++;
170
            }
171
        }
172
 
173
        if (i < 4)
174
            node->children[i] = NULL;
175
 
176
        node->state = CAIRO_RTREE_NODE_DIVIDED;
177
        cairo_list_move (&node->link, &rtree->evictable);
178
        node = node->children[0];
179
    }
180
 
181
    node->state = CAIRO_RTREE_NODE_OCCUPIED;
182
    cairo_list_move (&node->link, &rtree->evictable);
183
    *out = node;
184
 
185
    return CAIRO_STATUS_SUCCESS;
186
}
187
 
188
void
189
_cairo_rtree_node_remove (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
190
{
191
    assert (node->state == CAIRO_RTREE_NODE_OCCUPIED);
192
    assert (node->pinned == FALSE);
193
 
194
    node->state = CAIRO_RTREE_NODE_AVAILABLE;
195
    cairo_list_move (&node->link, &rtree->available);
196
 
197
    if (! node->parent->pinned)
198
        _cairo_rtree_node_collapse (rtree, node->parent);
199
}
200
 
201
cairo_int_status_t
202
_cairo_rtree_insert (cairo_rtree_t           *rtree,
203
                     int                      width,
204
                     int                      height,
205
                     cairo_rtree_node_t     **out)
206
{
207
    cairo_rtree_node_t *node;
208
 
209
    cairo_list_foreach_entry (node, cairo_rtree_node_t,
210
                              &rtree->available, link)
211
    {
212
        if (node->width >= width && node->height >= height)
213
            return _cairo_rtree_node_insert (rtree, node, width, height, out);
214
    }
215
 
216
    return CAIRO_INT_STATUS_UNSUPPORTED;
217
}
218
 
219
static uint32_t
220
hars_petruska_f54_1_random (void)
221
{
222
#define rol(x,k) ((x << k) | (x >> (32-k)))
223
    static uint32_t x;
224
    return x = (x ^ rol (x, 5) ^ rol (x, 24)) + 0x37798849;
225
#undef rol
226
}
227
 
228
cairo_int_status_t
229
_cairo_rtree_evict_random (cairo_rtree_t         *rtree,
230
                           int                    width,
231
                           int                    height,
232
                           cairo_rtree_node_t           **out)
233
{
234
    cairo_rtree_node_t *node;
235
    int i, cnt;
236
 
237
    cnt = 0;
238
    cairo_list_foreach_entry (node, cairo_rtree_node_t,
239
                              &rtree->evictable, link)
240
    {
241
        if (node->width >= width && node->height >= height)
242
            cnt++;
243
    }
244
 
245
    if (cnt == 0)
246
        return CAIRO_INT_STATUS_UNSUPPORTED;
247
 
248
    cnt = hars_petruska_f54_1_random () % cnt;
249
    cairo_list_foreach_entry (node, cairo_rtree_node_t,
250
                              &rtree->evictable, link)
251
    {
252
        if (node->width >= width && node->height >= height && cnt-- == 0) {
253
            if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
254
                if (node->owner != NULL)
255
                    *node->owner = NULL;
256
                if (rtree->evict != NULL)
257
                    rtree->evict (node);
258
            } else {
259
                for (i = 0; i < 4 && node->children[i] != NULL; i++)
260
                    _cairo_rtree_node_destroy (rtree, node->children[i]);
261
                node->children[0] = NULL;
262
            }
263
 
264
            node->state = CAIRO_RTREE_NODE_AVAILABLE;
265
            cairo_list_move (&node->link, &rtree->available);
266
 
267
            *out = node;
268
            return CAIRO_STATUS_SUCCESS;
269
        }
270
    }
271
 
272
    return CAIRO_INT_STATUS_UNSUPPORTED;
273
}
274
 
275
void *
276
_cairo_rtree_pin (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
277
{
278
    void *ptr = node;
279
 
280
    while (node->pinned == FALSE) {
281
        cairo_list_move (&node->link, &rtree->pinned);
282
        node->pinned = TRUE;
283
        node = node->parent;
284
        if (node == NULL)
285
            break;
286
    }
287
 
288
    return ptr;
289
}
290
 
291
void
292
_cairo_rtree_unpin (cairo_rtree_t *rtree)
293
{
294
    cairo_rtree_node_t *node, *next;
295
    cairo_list_t can_collapse;
296
 
297
    if (cairo_list_is_empty (&rtree->pinned))
298
        return;
299
 
300
    cairo_list_init (&can_collapse);
301
 
302
    cairo_list_foreach_entry_safe (node, next,
303
                                   cairo_rtree_node_t,
304
                                   &rtree->pinned,
305
                                   link)
306
    {
307
        node->pinned = FALSE;
308
        if (node->state == CAIRO_RTREE_NODE_OCCUPIED && node->owner == NULL) {
309
            cairo_bool_t all_available;
310
            int i;
311
 
312
            node->state = CAIRO_RTREE_NODE_AVAILABLE;
313
            cairo_list_move (&node->link, &rtree->available);
314
 
315
            all_available = TRUE;
316
            node = node->parent;
317
            for (i = 0; i < 4 && node->children[i] != NULL && all_available; i++)
318
                all_available &= node->children[i]->state == CAIRO_RTREE_NODE_AVAILABLE;
319
 
320
            if (all_available) {
321
                cairo_list_move (&node->link, &can_collapse);
322
                for (i = 0;  i < 4 && node->children[i] != NULL; i++)
323
                    cairo_list_del (&node->children[i]->link);
324
            }
325
        }
326
        else
327
        {
328
            cairo_list_move (&node->link, &rtree->evictable);
329
        }
330
    }
331
 
332
    cairo_list_foreach_entry_safe (node, next,
333
                                   cairo_rtree_node_t,
334
                                   &can_collapse,
335
                                   link)
336
    {
337
        _cairo_rtree_node_collapse (rtree, node);
338
    }
339
}
340
 
341
void
342
_cairo_rtree_init (cairo_rtree_t        *rtree,
343
                   int                   width,
344
                   int                   height,
345
                   int                   min_size,
346
                   int                   node_size,
347
                   void                  (*evict) (void *node))
348
{
349
    rtree->evict = evict;
350
 
351
    assert (node_size >= (int) sizeof (cairo_rtree_node_t));
352
    _cairo_freepool_init (&rtree->node_freepool, node_size);
353
 
354
    cairo_list_init (&rtree->available);
355
    cairo_list_init (&rtree->pinned);
356
    cairo_list_init (&rtree->evictable);
357
 
358
    rtree->min_size = min_size;
359
 
360
    memset (&rtree->root, 0, sizeof (rtree->root));
361
    rtree->root.width = width;
362
    rtree->root.height = height;
363
    rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
364
    cairo_list_add (&rtree->root.link, &rtree->available);
365
}
366
 
367
void
368
_cairo_rtree_reset (cairo_rtree_t *rtree)
369
{
370
    int i;
371
 
372
    if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
373
        if (rtree->root.owner != NULL)
374
            *rtree->root.owner = NULL;
375
        if (rtree->evict != NULL)
376
            rtree->evict (&rtree->root);
377
    } else {
378
        for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
379
            _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
380
        rtree->root.children[0] = NULL;
381
    }
382
 
383
    cairo_list_init (&rtree->available);
384
    cairo_list_init (&rtree->evictable);
385
    cairo_list_init (&rtree->pinned);
386
 
387
    rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
388
    rtree->root.pinned = FALSE;
389
    cairo_list_add (&rtree->root.link, &rtree->available);
390
}
391
 
392
void
393
_cairo_rtree_fini (cairo_rtree_t *rtree)
394
{
395
    int i;
396
 
397
    if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
398
        if (rtree->root.owner != NULL)
399
            *rtree->root.owner = NULL;
400
        if (rtree->evict != NULL)
401
            rtree->evict (&rtree->root);
402
    } else {
403
        for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
404
            _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
405
    }
406
 
407
    _cairo_freepool_fini (&rtree->node_freepool);
408
}