4 * PCB, interactive printed circuit board design
5 * Copyright (C) 1994,1995,1996 Thomas Nau
6 * Copyright (C) 1998,1999,2000,2001,2002,2003,2004 harry eaton
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 * Contact addresses for paper mail and Email:
23 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
24 * haceaton@aplcomm.jhuapl.edu
28 /* this file, rtree.c, was written and is
29 * Copyright (c) 2004, harry eaton
32 /* implements r-tree structures.
33 * these should be much faster for the auto-router
34 * because the recursive search is much more efficient
35 * and that's where the auto-router spends all its time.
50 #ifdef HAVE_LIBDMALLOC
55 /* All rectangles are closed on the bottom left and open on the
56 * top right. i.e. they contain one corner point, but not the other.
57 * This requires that the corner points not be equal!
60 /* the number of entries in each rtree node
61 * 4 - 7 seem to be pretty good settings
65 /* it seems that sorting the leaf order slows us down
66 * but sometimes gives better routes
71 #define DELETE_BY_POINTER
75 const BoxType
*bptr
; /* pointer to the box */
76 BoxType bounds
; /* copy of the box for locality of reference */
81 BoxType box
; /* bounds rectangle of this node */
82 struct rtree_node
*parent
; /* parent of this node, NULL = root */
85 unsigned is_leaf
:1; /* this is a leaf node */
86 unsigned manage
:31; /* true==should free 'rect.bptr' if node is destroyed */
91 struct rtree_node
*kids
[M_SIZE
+ 1]; /* when not leaf */
92 Rentry rects
[M_SIZE
+ 1]; /* when leaf */
99 __r_node_is_good (struct rtree_node
*node
)
107 for (i
= 0; i
< M_SIZE
; i
++)
109 if (node
->flags
.is_leaf
)
111 if (!node
->u
.rects
[i
].bptr
)
116 /* check that once one entry is empty, all the rest are too */
117 if (node
->u
.rects
[i
].bptr
&& last
)
119 /* check that the box makes sense */
120 if (node
->box
.X1
> node
->box
.X2
)
122 if (node
->box
.Y1
> node
->box
.Y2
)
124 /* check that bounds is the same as the pointer */
125 if (node
->u
.rects
[i
].bounds
.X1
!= node
->u
.rects
[i
].bptr
->X1
)
127 if (node
->u
.rects
[i
].bounds
.Y1
!= node
->u
.rects
[i
].bptr
->Y1
)
129 if (node
->u
.rects
[i
].bounds
.X2
!= node
->u
.rects
[i
].bptr
->X2
)
131 if (node
->u
.rects
[i
].bounds
.Y2
!= node
->u
.rects
[i
].bptr
->Y2
)
133 /* check that entries are within node bounds */
134 if (node
->u
.rects
[i
].bounds
.X1
< node
->box
.X1
)
136 if (node
->u
.rects
[i
].bounds
.X2
> node
->box
.X2
)
138 if (node
->u
.rects
[i
].bounds
.Y1
< node
->box
.Y1
)
140 if (node
->u
.rects
[i
].bounds
.Y2
> node
->box
.Y2
)
145 if (!node
->u
.kids
[i
])
150 /* make sure all children are the same type */
152 kind
= node
->u
.kids
[i
]->flags
.is_leaf
;
153 else if (kind
!= node
->u
.kids
[i
]->flags
.is_leaf
)
155 /* check that once one entry is empty, all the rest are too */
156 if (node
->u
.kids
[i
] && last
)
158 /* check that entries are within node bounds */
159 if (node
->u
.kids
[i
]->box
.X1
< node
->box
.X1
)
161 if (node
->u
.kids
[i
]->box
.X2
> node
->box
.X2
)
163 if (node
->u
.kids
[i
]->box
.Y1
< node
->box
.Y1
)
165 if (node
->u
.kids
[i
]->box
.Y2
> node
->box
.Y2
)
170 /* check that we're completely in the parent's bounds */
173 if (node
->parent
->box
.X1
> node
->box
.X1
)
175 if (node
->parent
->box
.X2
< node
->box
.X2
)
177 if (node
->parent
->box
.Y1
> node
->box
.Y1
)
179 if (node
->parent
->box
.Y2
< node
->box
.Y2
)
182 /* make sure overflow is empty */
183 if (!node
->flags
.is_leaf
&& node
->u
.kids
[i
])
185 if (node
->flags
.is_leaf
&& node
->u
.rects
[i
].bptr
)
190 /* check the whole tree from this node down for consistency */
192 __r_tree_is_good (struct rtree_node
*node
)
198 if (!__r_node_is_good (node
))
200 if (node
->flags
.is_leaf
)
202 for (i
= 0; i
< M_SIZE
; i
++)
204 if (!__r_tree_is_good (node
->u
.kids
[i
]))
213 /* print out the tree */
215 __r_dump_tree (struct rtree_node
*node
, int depth
)
227 (node
->box
.X2
- node
->box
.X1
) * (double) (node
->box
.Y2
- node
->box
.Y1
);
229 for (i
= 0; i
< depth
; i
++)
231 if (!node
->flags
.is_leaf
)
233 printf ("p=0x%p node X(%d, %d) Y(%d, %d)\n", (void *) node
,
234 node
->box
.X1
, node
->box
.X2
, node
->box
.Y1
, node
->box
.Y2
);
238 printf ("p=0x%p leaf manage(%02x) X(%d, %d) Y(%d, %d)\n", (void *) node
,
239 node
->flags
.manage
, node
->box
.X1
, node
->box
.X2
, node
->box
.Y1
,
241 for (j
= 0; j
< M_SIZE
; j
++)
243 if (!node
->u
.rects
[j
].bptr
)
246 (node
->u
.rects
[j
].bounds
.X2
-
247 node
->u
.rects
[j
].bounds
.X1
) *
248 (double) (node
->u
.rects
[j
].bounds
.Y2
-
249 node
->u
.rects
[j
].bounds
.Y1
);
251 for (i
= 0; i
< depth
+ 1; i
++)
253 printf ("entry 0x%p X(%d, %d) Y(%d, %d)\n",
254 (void *) (node
->u
.rects
[j
].bptr
),
255 node
->u
.rects
[j
].bounds
.X1
, node
->u
.rects
[j
].bounds
.X2
,
256 node
->u
.rects
[j
].bounds
.Y1
, node
->u
.rects
[j
].bounds
.Y2
);
260 for (i
= 0; i
< M_SIZE
; i
++)
262 __r_dump_tree (node
->u
.kids
[i
], depth
+ 1);
264 printf ("average box area is %g\n", area
/ count
);
268 /* Sort the children or entries of a node
269 * according to the largest side.
273 cmp_box (const BoxType
* a
, const BoxType
* b
)
275 /* compare two box coordinates so that the __r_search
276 * will fail at the earliest comparison possible.
277 * It needs to see the biggest X1 first, then the
278 * smallest X2, the biggest Y1 and smallest Y2
298 sort_node (struct rtree_node
*node
)
300 if (node
->flags
.is_leaf
)
302 register Rentry
*r
, *i
, temp
;
304 for (r
= &node
->u
.rects
[1]; r
->bptr
; r
++)
308 while (i
>= &node
->u
.rects
[0])
310 if (cmp_box (&i
->bounds
, &r
->bounds
))
321 register struct rtree_node
**r
, **i
, *temp
;
323 for (r
= &node
->u
.kids
[1]; *r
; r
++)
327 while (i
>= &node
->u
.kids
[0])
329 if (cmp_box (&(*i
)->box
, &(*r
)->box
))
343 /* set the node bounds large enough to encompass all
344 * of the children's rectangles
347 adjust_bounds (struct rtree_node
*node
)
352 assert (node
->u
.kids
[0]);
353 if (node
->flags
.is_leaf
)
355 node
->box
= node
->u
.rects
[0].bounds
;
356 for (i
= 1; i
< M_SIZE
+ 1; i
++)
358 if (!node
->u
.rects
[i
].bptr
)
360 MAKEMIN (node
->box
.X1
, node
->u
.rects
[i
].bounds
.X1
);
361 MAKEMAX (node
->box
.X2
, node
->u
.rects
[i
].bounds
.X2
);
362 MAKEMIN (node
->box
.Y1
, node
->u
.rects
[i
].bounds
.Y1
);
363 MAKEMAX (node
->box
.Y2
, node
->u
.rects
[i
].bounds
.Y2
);
368 node
->box
= node
->u
.kids
[0]->box
;
369 for (i
= 1; i
< M_SIZE
+ 1; i
++)
371 if (!node
->u
.kids
[i
])
373 MAKEMIN (node
->box
.X1
, node
->u
.kids
[i
]->box
.X1
);
374 MAKEMAX (node
->box
.X2
, node
->u
.kids
[i
]->box
.X2
);
375 MAKEMIN (node
->box
.Y1
, node
->u
.kids
[i
]->box
.Y1
);
376 MAKEMAX (node
->box
.Y2
, node
->u
.kids
[i
]->box
.Y2
);
381 /* create an r-tree from an unsorted list of boxes.
382 * the r-tree will keep pointers into
383 * it, so don't free the box list until you've called r_destroy_tree.
384 * if you set 'manage' to true, r_destroy_tree will free your boxlist.
387 r_create_tree (const BoxType
* boxlist
[], int N
, int manage
)
390 struct rtree_node
*node
;
394 rtree
= (rtree_t
*)calloc (1, sizeof (*rtree
));
395 /* start with a single empty leaf node */
396 node
= (struct rtree_node
*)calloc (1, sizeof (*node
));
397 node
->flags
.is_leaf
= 1;
400 /* simple, just insert all of the boxes! */
401 for (i
= 0; i
< N
; i
++)
404 r_insert_entry (rtree
, boxlist
[i
], manage
);
407 assert (__r_tree_is_good (rtree
->root
));
413 __r_destroy_tree (struct rtree_node
*node
)
417 if (node
->flags
.is_leaf
)
418 for (i
= 0; i
< M_SIZE
; i
++)
420 if (!node
->u
.rects
[i
].bptr
)
422 if (node
->flags
.manage
& flag
)
423 free ((void *) node
->u
.rects
[i
].bptr
);
427 for (i
= 0; i
< M_SIZE
; i
++)
429 if (!node
->u
.kids
[i
])
431 __r_destroy_tree (node
->u
.kids
[i
]);
436 /* free the memory associated with an rtree. */
438 r_destroy_tree (rtree_t
** rtree
)
441 __r_destroy_tree ((*rtree
)->root
);
448 int (*check_it
) (const BoxType
* region
, void *cl
);
449 int (*found_it
) (const BoxType
* box
, void *cl
);
453 /* most of the auto-routing time is spent in this routine
454 * so some careful thought has been given to maximizing the speed
458 __r_search (struct rtree_node
*node
, const BoxType
* query
, r_arg
* arg
)
461 /** assert that starting_region is well formed */
462 assert (query
->X1
< query
->X2
&& query
->Y1
< query
->Y2
);
463 assert (node
->box
.X1
< query
->X2
&& node
->box
.X2
> query
->X1
&&
464 node
->box
.Y1
< query
->Y2
&& node
->box
.Y2
> query
->Y1
);
466 /** assert that node is well formed */
467 assert (__r_node_is_good (node
));
469 /* the check for bounds is done before entry. This saves the overhead
470 * of building/destroying the stack frame for each bounds that fails
471 * to intersect, which is the most common condition.
473 if (node
->flags
.is_leaf
)
476 if (arg
->found_it
) /* test this once outside of loop */
478 register int seen
= 0;
479 for (i
= 0; node
->u
.rects
[i
].bptr
; i
++)
481 if ((node
->u
.rects
[i
].bounds
.X1
< query
->X2
) &&
482 (node
->u
.rects
[i
].bounds
.X2
> query
->X1
) &&
483 (node
->u
.rects
[i
].bounds
.Y1
< query
->Y2
) &&
484 (node
->u
.rects
[i
].bounds
.Y2
> query
->Y1
) &&
485 arg
->found_it (node
->u
.rects
[i
].bptr
, arg
->closure
))
492 register int seen
= 0;
493 for (i
= 0; node
->u
.rects
[i
].bptr
; i
++)
495 if ((node
->u
.rects
[i
].bounds
.X1
< query
->X2
) &&
496 (node
->u
.rects
[i
].bounds
.X2
> query
->X1
) &&
497 (node
->u
.rects
[i
].bounds
.Y1
< query
->Y2
) &&
498 (node
->u
.rects
[i
].bounds
.Y2
> query
->Y1
))
505 /* not a leaf, recurse on lower nodes */
509 struct rtree_node
**n
;
510 for (n
= &node
->u
.kids
[0]; *n
; n
++)
512 if ((*n
)->box
.X1
>= query
->X2
||
513 (*n
)->box
.X2
<= query
->X1
||
514 (*n
)->box
.Y1
>= query
->Y2
|| (*n
)->box
.Y2
<= query
->Y1
||
515 !arg
->check_it (&(*n
)->box
, arg
->closure
))
517 seen
+= __r_search (*n
, query
, arg
);
524 struct rtree_node
**n
;
525 for (n
= &node
->u
.kids
[0]; *n
; n
++)
527 if ((*n
)->box
.X1
>= query
->X2
||
528 (*n
)->box
.X2
<= query
->X1
||
529 (*n
)->box
.Y1
>= query
->Y2
|| (*n
)->box
.Y2
<= query
->Y1
)
531 seen
+= __r_search (*n
, query
, arg
);
537 /* Parameterized search in the rtree.
538 * Returns the number of rectangles found.
539 * calls found_rectangle for each intersection seen
540 * and calls check_region with the current sub-region
541 * to see whether deeper searching is desired
544 r_search (rtree_t
* rtree
, const BoxType
* query
,
545 int (*check_region
) (const BoxType
* region
, void *cl
),
546 int (*found_rectangle
) (const BoxType
* box
, void *cl
), void *cl
)
550 if (!rtree
|| rtree
->size
< 1)
555 assert (__r_tree_is_good (rtree
->root
));
558 if (query
->X2
<= query
->X1
|| query
->Y2
<= query
->Y1
)
561 /* check this box. If it's not touched we're done here */
562 if (rtree
->root
->box
.X1
>= query
->X2
||
563 rtree
->root
->box
.X2
<= query
->X1
||
564 rtree
->root
->box
.Y1
>= query
->Y2
565 || rtree
->root
->box
.Y2
<= query
->Y1
)
567 arg
.check_it
= check_region
;
568 arg
.found_it
= found_rectangle
;
570 return __r_search (rtree
->root
, query
, &arg
);
574 arg
.check_it
= check_region
;
575 arg
.found_it
= found_rectangle
;
577 return __r_search (rtree
->root
, &rtree
->root
->box
, &arg
);
581 /*------ r_region_is_empty ------*/
583 __r_region_is_empty_rect_in_reg (const BoxType
* box
, void *cl
)
585 jmp_buf *envp
= (jmp_buf *) cl
;
586 longjmp (*envp
, 1); /* found one! */
589 /* return 0 if there are any rectangles in the given region. */
591 r_region_is_empty (rtree_t
* rtree
, const BoxType
* region
)
603 r_search (rtree
, region
, NULL
, __r_region_is_empty_rect_in_reg
, &env
);
605 assert (r
== 0); /* otherwise longjmp would have been called */
607 return 1; /* no rectangles found */
615 /* split the node into two nodes putting clusters in each
616 * use the k-means clustering algorithm
619 find_clusters (struct rtree_node
*node
)
621 float total_a
, total_b
;
622 float a_X
, a_Y
, b_X
, b_Y
;
623 bool belong
[M_SIZE
+ 1];
624 struct centroid center
[M_SIZE
+ 1];
625 int clust_a
, clust_b
, tries
;
626 int a_manage
= 0, b_manage
= 0;
627 int i
, old_ax
, old_ay
, old_bx
, old_by
;
628 struct rtree_node
*new_node
;
631 for (i
= 0; i
< M_SIZE
+ 1; i
++)
633 if (node
->flags
.is_leaf
)
634 b
= &(node
->u
.rects
[i
].bounds
);
636 b
= &(node
->u
.kids
[i
]->box
);
637 center
[i
].x
= 0.5 * (b
->X1
+ b
->X2
);
638 center
[i
].y
= 0.5 * (b
->Y1
+ b
->Y2
);
639 /* adding 1 prevents zero area */
640 center
[i
].area
= 1. + (float) (b
->X2
- b
->X1
) * (float) (b
->Y2
- b
->Y1
);
642 /* starting 'A' cluster center */
645 /* starting 'B' cluster center */
646 b_X
= center
[M_SIZE
].x
;
647 b_Y
= center
[M_SIZE
].y
;
648 /* don't allow the same cluster centers */
649 if (b_X
== a_X
&& b_Y
== a_Y
)
654 for (tries
= 0; tries
< M_SIZE
; tries
++)
660 clust_a
= clust_b
= 0;
661 for (i
= 0; i
< M_SIZE
+ 1; i
++)
665 dist1
= SQUARE (a_X
- center
[i
].x
) + SQUARE (a_Y
- center
[i
].y
);
666 dist2
= SQUARE (b_X
- center
[i
].x
) + SQUARE (b_Y
- center
[i
].y
);
667 if (dist1
* (clust_a
+ M_SIZE
/ 2) < dist2
* (clust_b
+ M_SIZE
/ 2))
678 /* kludge to fix degenerate cases */
679 if (clust_a
== M_SIZE
+ 1)
680 belong
[M_SIZE
/ 2] = false;
681 else if (clust_b
== M_SIZE
+ 1)
682 belong
[M_SIZE
/ 2] = true;
683 /* compute new center of gravity of clusters */
684 total_a
= total_b
= 0;
685 a_X
= a_Y
= b_X
= b_Y
= 0;
686 for (i
= 0; i
< M_SIZE
+ 1; i
++)
690 a_X
+= center
[i
].x
* center
[i
].area
;
691 a_Y
+= center
[i
].y
* center
[i
].area
;
692 total_a
+= center
[i
].area
;
696 b_X
+= center
[i
].x
* center
[i
].area
;
697 b_Y
+= center
[i
].y
* center
[i
].area
;
698 total_b
+= center
[i
].area
;
705 if (old_ax
== (int) a_X
&& old_ay
== (int) a_Y
&&
706 old_bx
== (int) b_X
&& old_by
== (int) b_Y
)
709 /* Now 'belong' has the partition map */
710 new_node
= (struct rtree_node
*)calloc (1, sizeof (*new_node
));
711 new_node
->parent
= node
->parent
;
712 new_node
->flags
.is_leaf
= node
->flags
.is_leaf
;
713 clust_a
= clust_b
= 0;
714 if (node
->flags
.is_leaf
)
716 int flag
, a_flag
, b_flag
;
717 flag
= a_flag
= b_flag
= 1;
718 for (i
= 0; i
< M_SIZE
+ 1; i
++)
722 node
->u
.rects
[clust_a
++] = node
->u
.rects
[i
];
723 if (node
->flags
.manage
& flag
)
729 new_node
->u
.rects
[clust_b
++] = node
->u
.rects
[i
];
730 if (node
->flags
.manage
& flag
)
739 for (i
= 0; i
< M_SIZE
+ 1; i
++)
742 node
->u
.kids
[clust_a
++] = node
->u
.kids
[i
];
745 node
->u
.kids
[i
]->parent
= new_node
;
746 new_node
->u
.kids
[clust_b
++] = node
->u
.kids
[i
];
750 node
->flags
.manage
= a_manage
;
751 new_node
->flags
.manage
= b_manage
;
752 assert (clust_a
!= 0);
753 assert (clust_b
!= 0);
754 if (node
->flags
.is_leaf
)
755 for (; clust_a
< M_SIZE
+ 1; clust_a
++)
756 node
->u
.rects
[clust_a
].bptr
= NULL
;
758 for (; clust_a
< M_SIZE
+ 1; clust_a
++)
759 node
->u
.kids
[clust_a
] = NULL
;
760 adjust_bounds (node
);
762 adjust_bounds (new_node
);
763 sort_node (new_node
);
767 /* split a node according to clusters
770 split_node (struct rtree_node
*node
)
773 struct rtree_node
*new_node
;
776 assert (node
->flags
.is_leaf
? (void *) node
->u
.rects
[M_SIZE
].
777 bptr
: (void *) node
->u
.kids
[M_SIZE
]);
778 new_node
= find_clusters (node
);
779 if (node
->parent
== NULL
) /* split root node */
781 struct rtree_node
*second
;
783 second
= (struct rtree_node
*)calloc (1, sizeof (*second
));
785 if (!second
->flags
.is_leaf
)
786 for (i
= 0; i
< M_SIZE
; i
++)
787 if (second
->u
.kids
[i
])
788 second
->u
.kids
[i
]->parent
= second
;
789 node
->flags
.is_leaf
= 0;
790 node
->flags
.manage
= 0;
791 second
->parent
= new_node
->parent
= node
;
792 node
->u
.kids
[0] = new_node
;
793 node
->u
.kids
[1] = second
;
794 for (i
= 2; i
< M_SIZE
+ 1; i
++)
795 node
->u
.kids
[i
] = NULL
;
796 adjust_bounds (node
);
799 assert (__r_tree_is_good (node
));
803 for (i
= 0; i
< M_SIZE
; i
++)
804 if (!node
->parent
->u
.kids
[i
])
806 node
->parent
->u
.kids
[i
] = new_node
;
808 assert (__r_node_is_good (node
));
809 assert (__r_node_is_good (new_node
));
814 assert (__r_node_is_good (node
->parent
));
816 sort_node (node
->parent
);
819 split_node (node
->parent
);
823 contained (struct rtree_node
*node
, const BoxType
* query
)
825 if (node
->box
.X1
> query
->X1
|| node
->box
.X2
< query
->X2
||
826 node
->box
.Y1
> query
->Y1
|| node
->box
.Y2
< query
->Y2
)
833 penalty (struct rtree_node
*node
, const BoxType
* query
)
837 /* Compute the area penalty for inserting here and return.
838 * The penalty is the increase in area necessary
839 * to include the query->
841 score
= (MAX (node
->box
.X2
, query
->X2
) - MIN (node
->box
.X1
, query
->X1
));
842 score
*= (MAX (node
->box
.Y2
, query
->Y2
) - MIN (node
->box
.Y1
, query
->Y1
));
844 (double)(node
->box
.X2
- node
->box
.X1
) *
845 (double)(node
->box
.Y2
- node
->box
.Y1
);
850 __r_insert_node (struct rtree_node
*node
, const BoxType
* query
,
851 int manage
, bool force
)
855 assert (__r_node_is_good (node
));
857 /* Ok, at this point we must already enclose the query or we're forcing
858 * this node to expand to enclose it, so if we're a leaf, simply store
862 if (node
->flags
.is_leaf
)
866 if (UNLIKELY (manage
))
868 register int flag
= 1;
870 for (i
= 0; i
< M_SIZE
; i
++)
872 if (!node
->u
.rects
[i
].bptr
)
876 node
->flags
.manage
|= flag
;
880 for (i
= 0; i
< M_SIZE
; i
++)
881 if (!node
->u
.rects
[i
].bptr
)
884 /* the node always has an extra space available */
885 node
->u
.rects
[i
].bptr
= query
;
886 node
->u
.rects
[i
].bounds
= *query
;
887 /* first entry in node determines initial bounding box */
892 MAKEMIN (node
->box
.X1
, query
->X1
);
893 MAKEMAX (node
->box
.X2
, query
->X2
);
894 MAKEMIN (node
->box
.Y1
, query
->Y1
);
895 MAKEMAX (node
->box
.Y2
, query
->Y2
);
902 /* we must split the node */
909 struct rtree_node
*best_node
;
910 double score
, best_score
;
914 MAKEMIN (node
->box
.X1
, query
->X1
);
915 MAKEMAX (node
->box
.X2
, query
->X2
);
916 MAKEMIN (node
->box
.Y1
, query
->Y1
);
917 MAKEMAX (node
->box
.Y2
, query
->Y2
);
920 /* this node encloses it, but it's not a leaf, so descend the tree */
922 /* First check if any children actually encloses it */
923 assert (node
->u
.kids
[0]);
924 for (i
= 0; i
< M_SIZE
; i
++)
926 if (!node
->u
.kids
[i
])
928 if (contained (node
->u
.kids
[i
], query
))
930 __r_insert_node (node
->u
.kids
[i
], query
, manage
, false);
936 /* see if there is room for a new leaf node */
937 if (node
->u
.kids
[0]->flags
.is_leaf
&& i
< M_SIZE
)
939 struct rtree_node
*new_node
;
940 new_node
= (struct rtree_node
*)calloc (1, sizeof (*new_node
));
941 new_node
->parent
= node
;
942 new_node
->flags
.is_leaf
= true;
943 node
->u
.kids
[i
] = new_node
;
944 new_node
->u
.rects
[0].bptr
= query
;
945 new_node
->u
.rects
[0].bounds
= *query
;
946 new_node
->box
= *query
;
947 if (UNLIKELY (manage
))
948 new_node
->flags
.manage
= 1;
953 /* Ok, so we're still here - look for the best child to push it into */
954 best_score
= penalty (node
->u
.kids
[0], query
);
955 best_node
= node
->u
.kids
[0];
956 for (i
= 1; i
< M_SIZE
; i
++)
958 if (!node
->u
.kids
[i
])
960 score
= penalty (node
->u
.kids
[i
], query
);
961 if (score
< best_score
)
964 best_node
= node
->u
.kids
[i
];
967 __r_insert_node (best_node
, query
, manage
, true);
974 r_insert_entry (rtree_t
* rtree
, const BoxType
* which
, int man
)
977 assert (which
->X1
<= which
->X2
);
978 assert (which
->Y1
<= which
->Y2
);
979 /* recursively search the tree for the best leaf node */
980 assert (rtree
->root
);
981 __r_insert_node (rtree
->root
, which
, man
,
982 rtree
->root
->box
.X1
> which
->X1
983 || rtree
->root
->box
.X2
< which
->X2
984 || rtree
->root
->box
.Y1
> which
->Y1
985 || rtree
->root
->box
.Y2
< which
->Y2
);
990 __r_delete (struct rtree_node
*node
, const BoxType
* query
)
992 int i
, flag
, mask
, a
;
994 /* the tree might be inconsistent during delete */
995 if (query
->X1
< node
->box
.X1
|| query
->Y1
< node
->box
.Y1
996 || query
->X2
> node
->box
.X2
|| query
->Y2
> node
->box
.Y2
)
998 if (!node
->flags
.is_leaf
)
1000 for (i
= 0; i
< M_SIZE
; i
++)
1002 /* if this is us being removed, free and copy over */
1003 if (node
->u
.kids
[i
] == (struct rtree_node
*) query
)
1005 free ((void *) query
);
1006 for (; i
< M_SIZE
; i
++)
1008 node
->u
.kids
[i
] = node
->u
.kids
[i
+ 1];
1009 if (!node
->u
.kids
[i
])
1012 /* nobody home here now ? */
1013 if (!node
->u
.kids
[0])
1017 /* wow, the root is empty! */
1018 node
->flags
.is_leaf
= 1;
1019 /* changing type of node, be sure it's all zero */
1020 for (i
= 1; i
< M_SIZE
+ 1; i
++)
1021 node
->u
.rects
[i
].bptr
= NULL
;
1024 return (__r_delete (node
->parent
, &node
->box
));
1027 /* propegate boundary adjust upward */
1030 adjust_bounds (node
);
1031 node
= node
->parent
;
1035 if (node
->u
.kids
[i
])
1037 if (__r_delete (node
->u
.kids
[i
], query
))
1045 /* leaf node here */
1048 for (i
= 0; i
< M_SIZE
; i
++)
1050 #ifdef DELETE_BY_POINTER
1051 if (!node
->u
.rects
[i
].bptr
|| node
->u
.rects
[i
].bptr
== query
)
1053 if (node
->u
.rects
[i
].bounds
.X1
== query
->X1
&&
1054 node
->u
.rects
[i
].bounds
.X2
== query
->X2
&&
1055 node
->u
.rects
[i
].bounds
.Y1
== query
->Y1
&&
1056 node
->u
.rects
[i
].bounds
.Y2
== query
->Y2
)
1062 if (!node
->u
.rects
[i
].bptr
)
1063 return false; /* not at this leaf */
1064 if (node
->flags
.manage
& a
)
1066 free ((void *) node
->u
.rects
[i
].bptr
);
1067 node
->u
.rects
[i
].bptr
= NULL
;
1069 /* squeeze the manage flags together */
1070 flag
= node
->flags
.manage
& mask
;
1071 mask
= (~mask
) << 1;
1072 node
->flags
.manage
= flag
| ((node
->flags
.manage
& mask
) >> 1);
1073 /* remove the entry */
1074 for (; i
< M_SIZE
; i
++)
1076 node
->u
.rects
[i
] = node
->u
.rects
[i
+ 1];
1077 if (!node
->u
.rects
[i
].bptr
)
1080 if (!node
->u
.rects
[0].bptr
)
1083 __r_delete (node
->parent
, &node
->box
);
1087 /* propagate boundary adjustment upward */
1090 adjust_bounds (node
);
1091 node
= node
->parent
;
1097 r_delete_entry (rtree_t
* rtree
, const BoxType
* box
)
1103 r
= __r_delete (rtree
->root
, box
);
1107 assert (__r_tree_is_good (rtree
->root
));