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
15
 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
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-error-private.h"
40
#include "cairo-rtree-private.h"
41

            
42
cairo_rtree_node_t *
43
_cairo_rtree_node_create (cairo_rtree_t		 *rtree,
44
		          cairo_rtree_node_t	 *parent,
45
			  int			  x,
46
			  int			  y,
47
			  int			  width,
48
			  int			  height)
49
{
50
    cairo_rtree_node_t *node;
51

            
52
    node = _cairo_freepool_alloc (&rtree->node_freepool);
53
    if (node == NULL) {
54
	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
55
	return NULL;
56
    }
57

            
58
    node->children[0] = NULL;
59
    node->parent = parent;
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
	rtree->destroy (node);
81
    } else {
82
	for (i = 0; i < 4 && node->children[i] != NULL; i++)
83
	    _cairo_rtree_node_destroy (rtree, node->children[i]);
84
    }
85

            
86
    _cairo_freepool_free (&rtree->node_freepool, node);
87
}
88

            
89
void
90
_cairo_rtree_node_collapse (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
91
{
92
    int i;
93

            
94
    do {
95
	assert (node->state == CAIRO_RTREE_NODE_DIVIDED);
96

            
97
	for (i = 0;  i < 4 && node->children[i] != NULL; i++)
98
	    if (node->children[i]->state != CAIRO_RTREE_NODE_AVAILABLE)
99
		return;
100

            
101
	for (i = 0; i < 4 && node->children[i] != NULL; i++)
102
	    _cairo_rtree_node_destroy (rtree, node->children[i]);
103

            
104
	node->children[0] = NULL;
105
	node->state = CAIRO_RTREE_NODE_AVAILABLE;
106
	cairo_list_move (&node->link, &rtree->available);
107
    } while ((node = node->parent) != NULL);
108
}
109

            
110
cairo_status_t
111
_cairo_rtree_node_insert (cairo_rtree_t *rtree,
112
	                  cairo_rtree_node_t *node,
113
			  int width,
114
			  int height,
115
			  cairo_rtree_node_t **out)
116
{
117
    int w, h, i;
118

            
119
    assert (node->state == CAIRO_RTREE_NODE_AVAILABLE);
120
    assert (node->pinned == FALSE);
121

            
122
    if (node->width  - width  > rtree->min_size ||
123
	node->height - height > rtree->min_size)
124
    {
125
	w = node->width  - width;
126
	h = node->height - height;
127

            
128
	i = 0;
129
	node->children[i] = _cairo_rtree_node_create (rtree, node,
130
						      node->x, node->y,
131
						      width, height);
132
	if (unlikely (node->children[i] == NULL))
133
	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
134
	i++;
135

            
136
	if (w > rtree->min_size) {
137
	    node->children[i] = _cairo_rtree_node_create (rtree, node,
138
							  node->x + width,
139
							  node->y,
140
							  w, height);
141
	    if (unlikely (node->children[i] == NULL))
142
		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
143
	    i++;
144
	}
145

            
146
	if (h > rtree->min_size) {
147
	    node->children[i] = _cairo_rtree_node_create (rtree, node,
148
							  node->x,
149
							  node->y + height,
150
							  width, h);
151
	    if (unlikely (node->children[i] == NULL))
152
		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
153
	    i++;
154

            
155
	    if (w > rtree->min_size) {
156
		node->children[i] = _cairo_rtree_node_create (rtree, node,
157
							      node->x + width,
158
							      node->y + height,
159
							      w, h);
160
		if (unlikely (node->children[i] == NULL))
161
		    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
162
		i++;
163
	    }
164
	}
165

            
166
	if (i < 4)
167
	    node->children[i] = NULL;
168

            
169
	node->state = CAIRO_RTREE_NODE_DIVIDED;
170
	cairo_list_move (&node->link, &rtree->evictable);
171
	node = node->children[0];
172
    }
173

            
174
    node->state = CAIRO_RTREE_NODE_OCCUPIED;
175
    cairo_list_move (&node->link, &rtree->evictable);
176
    *out = node;
177

            
178
    return CAIRO_STATUS_SUCCESS;
179
}
180

            
181
void
182
_cairo_rtree_node_remove (cairo_rtree_t *rtree, cairo_rtree_node_t *node)
183
{
184
    assert (node->state == CAIRO_RTREE_NODE_OCCUPIED);
185
    assert (node->pinned == FALSE);
186

            
187
    rtree->destroy (node);
188

            
189
    node->state = CAIRO_RTREE_NODE_AVAILABLE;
190
    cairo_list_move (&node->link, &rtree->available);
191

            
192
    _cairo_rtree_node_collapse (rtree, node->parent);
193
}
194

            
195
cairo_int_status_t
196
_cairo_rtree_insert (cairo_rtree_t	     *rtree,
197
		     int		      width,
198
	             int		      height,
199
	             cairo_rtree_node_t	    **out)
200
{
201
    cairo_rtree_node_t *node;
202

            
203
    cairo_list_foreach_entry (node, cairo_rtree_node_t,
204
			      &rtree->available, link)
205
    {
206
	if (node->width >= width && node->height >= height)
207
	    return _cairo_rtree_node_insert (rtree, node, width, height, out);
208
    }
209

            
210
    return CAIRO_INT_STATUS_UNSUPPORTED;
211
}
212

            
213
static uint32_t
214
hars_petruska_f54_1_random (void)
215
{
216
#define rol(x,k) ((x << k) | (x >> (32-k)))
217
    static uint32_t x;
218
    return x = (x ^ rol (x, 5) ^ rol (x, 24)) + 0x37798849;
219
#undef rol
220
}
221

            
222
cairo_int_status_t
223
_cairo_rtree_evict_random (cairo_rtree_t	 *rtree,
224
		           int			  width,
225
		           int			  height,
226
		           cairo_rtree_node_t		**out)
227
{
228
    cairo_int_status_t ret = CAIRO_INT_STATUS_UNSUPPORTED;
229
    cairo_rtree_node_t *node, *next;
230
    cairo_list_t tmp_pinned;
231
    int i, cnt;
232

            
233
    cairo_list_init (&tmp_pinned);
234

            
235
    /* propagate pinned from children to root */
236
    cairo_list_foreach_entry_safe (node, next,
237
				   cairo_rtree_node_t, &rtree->pinned, link) {
238
	node = node->parent;
239
	while (node && ! node->pinned) {
240
	    node->pinned = 1;
241
	    cairo_list_move (&node->link, &tmp_pinned);
242
	    node = node->parent;
243
	}
244
    }
245

            
246
    cnt = 0;
247
    cairo_list_foreach_entry (node, cairo_rtree_node_t,
248
			      &rtree->evictable, link)
249
    {
250
	if (node->width >= width && node->height >= height)
251
	    cnt++;
252
    }
253

            
254
    if (cnt == 0)
255
	goto out;
256

            
257
    cnt = hars_petruska_f54_1_random () % cnt;
258
    cairo_list_foreach_entry (node, cairo_rtree_node_t,
259
			      &rtree->evictable, link)
260
    {
261
	if (node->width >= width && node->height >= height && cnt-- == 0) {
262
	    if (node->state == CAIRO_RTREE_NODE_OCCUPIED) {
263
		rtree->destroy (node);
264
	    } else {
265
		for (i = 0; i < 4 && node->children[i] != NULL; i++)
266
		    _cairo_rtree_node_destroy (rtree, node->children[i]);
267
		node->children[0] = NULL;
268
	    }
269

            
270
	    node->state = CAIRO_RTREE_NODE_AVAILABLE;
271
	    cairo_list_move (&node->link, &rtree->available);
272

            
273
	    *out = node;
274
	    ret = CAIRO_STATUS_SUCCESS;
275
	    break;
276
	}
277
    }
278

            
279
out:
280
    while (! cairo_list_is_empty (&tmp_pinned)) {
281
	node = cairo_list_first_entry (&tmp_pinned, cairo_rtree_node_t, link);
282
	node->pinned = 0;
283
	cairo_list_move (&node->link, &rtree->evictable);
284
    }
285
    return ret;
286
}
287

            
288
void
289
_cairo_rtree_unpin (cairo_rtree_t *rtree)
290
{
291
    while (! cairo_list_is_empty (&rtree->pinned)) {
292
	cairo_rtree_node_t *node = cairo_list_first_entry (&rtree->pinned,
293
							   cairo_rtree_node_t,
294
							   link);
295
	node->pinned = 0;
296
	cairo_list_move (&node->link, &rtree->evictable);
297
    }
298
}
299

            
300
void
301
_cairo_rtree_init (cairo_rtree_t	*rtree,
302
	           int			 width,
303
		   int			 height,
304
		   int			 min_size,
305
		   int			 node_size,
306
		   void (*destroy) (cairo_rtree_node_t *))
307
{
308
    assert (node_size >= (int) sizeof (cairo_rtree_node_t));
309
    _cairo_freepool_init (&rtree->node_freepool, node_size);
310

            
311
    cairo_list_init (&rtree->available);
312
    cairo_list_init (&rtree->pinned);
313
    cairo_list_init (&rtree->evictable);
314

            
315
    rtree->min_size = min_size;
316
    rtree->destroy = destroy;
317

            
318
    memset (&rtree->root, 0, sizeof (rtree->root));
319
    rtree->root.width = width;
320
    rtree->root.height = height;
321
    rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
322
    cairo_list_add (&rtree->root.link, &rtree->available);
323
}
324

            
325
void
326
_cairo_rtree_reset (cairo_rtree_t *rtree)
327
{
328
    int i;
329

            
330
    if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
331
	rtree->destroy (&rtree->root);
332
    } else {
333
	for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
334
	    _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
335
	rtree->root.children[0] = NULL;
336
    }
337

            
338
    cairo_list_init (&rtree->available);
339
    cairo_list_init (&rtree->evictable);
340
    cairo_list_init (&rtree->pinned);
341

            
342
    rtree->root.state = CAIRO_RTREE_NODE_AVAILABLE;
343
    rtree->root.pinned = FALSE;
344
    cairo_list_add (&rtree->root.link, &rtree->available);
345
}
346

            
347
static void
348
_cairo_rtree_node_foreach (cairo_rtree_node_t *node,
349
			   void (*func)(cairo_rtree_node_t *, void *data),
350
			   void *data)
351
{
352
    int i;
353

            
354
    for (i = 0; i < 4 && node->children[i] != NULL; i++)
355
	_cairo_rtree_node_foreach(node->children[i], func, data);
356

            
357
    func(node, data);
358
}
359

            
360
void
361
_cairo_rtree_foreach (cairo_rtree_t *rtree,
362
		      void (*func)(cairo_rtree_node_t *, void *data),
363
		      void *data)
364
{
365
    int i;
366

            
367
    if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
368
	func(&rtree->root, data);
369
    } else {
370
	for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
371
	    _cairo_rtree_node_foreach (rtree->root.children[i], func, data);
372
    }
373
}
374

            
375
void
376
_cairo_rtree_fini (cairo_rtree_t *rtree)
377
{
378
    int i;
379

            
380
    if (rtree->root.state == CAIRO_RTREE_NODE_OCCUPIED) {
381
	rtree->destroy (&rtree->root);
382
    } else {
383
	for (i = 0; i < 4 && rtree->root.children[i] != NULL; i++)
384
	    _cairo_rtree_node_destroy (rtree, rtree->root.children[i]);
385
    }
386

            
387
    _cairo_freepool_fini (&rtree->node_freepool);
388
}