1 /* -*- tab-width: 4 -*-
2 *
3 * Electric(tm) VLSI Design System
4 *
5 * File: dbgeom.c
6 * Database geometry and search modules
7 * Written by: Steven M. Rubin, Static Free Software
8 *
9 * Copyright (c) 2000 Static Free Software.
10 *
11 * Electric(tm) is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version.
15 *
16 * Electric(tm) is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with Electric(tm); see the file COPYING. If not, write to
23 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
24 * Boston, Mass 02111-1307, USA.
25 *
26 * Static Free Software
27 * 4119 Alpine Road
28 * Portola Valley, California 94028
29 * info@staticfreesoft.com
30 */
31
32 #include "global.h"
33 #include "database.h"
34 #include "egraphics.h"
35 #include "tech.h"
36 #include "tecgen.h"
37 #include "tecschem.h"
38 #include "tecart.h"
39 #include <math.h>
40
41 #define mmini(a, b) ((a) < (b) ? (a) : (b))
42 #define mmaxi(a, b) ((a) > (b) ? (a) : (b))
43
44 #define MAXDEPTH 100 /* maximum depth of tree (for search) */
45 /* #define USEFLOATS */ /* uncomment to use floating point */
46
47 #define NORSEARCH ((RSEARCH *)-1)
48 typedef struct
49 {
50 RTNODE *rtn[MAXDEPTH];
51 INTBIG position[MAXDEPTH];
52 INTBIG depth;
53 INTBIG lx, hx, ly, hy;
54 } RSEARCH;
55
56 static RSEARCH *db_rsearchfree = NORSEARCH;
57 static void *db_geomsearchmutex = 0; /* mutex for geometric search modules */
58
59 /* prototypes for local routines */
60 static RSEARCH *db_allocrsearch(void);
61 static void db_freersearch(RSEARCH*);
62 static void db_removertnode(RTNODE*, INTBIG, NODEPROTO*);
63 static void db_reinsert(RTNODE*, NODEPROTO*);
64 static BOOLEAN db_findgeom(RTNODE*, GEOM*, RTNODE**, INTBIG*);
65 static BOOLEAN db_findgeomanywhere(RTNODE*, GEOM*, RTNODE**, INTBIG*);
66 static void db_figbounds(RTNODE*);
67
68 /*
69 * Routine to free all memory associated with this module.
70 */
db_freegeomemory(void)71 void db_freegeomemory(void)
72 {
73 REGISTER RSEARCH *rs;
74
75 /* free all window partitions */
76 while (db_rsearchfree != NORSEARCH)
77 {
78 rs = db_rsearchfree;
79 db_rsearchfree = (RSEARCH *)db_rsearchfree->lx;
80 efree((CHAR *)rs);
81 }
82 }
83
84 /*
85 * Routine to initialize the geometry module.
86 */
db_initgeometry(void)87 void db_initgeometry(void)
88 {
89 if (ensurevalidmutex(&db_geomsearchmutex, TRUE)) return;
90 }
91
92 /*********************** MODULE ALLOCATION ***********************/
93
94 /*
95 * routine to allocate a Rtree node from cluster "cluster".
96 */
allocrtnode(CLUSTER * cluster)97 RTNODE *allocrtnode(CLUSTER *cluster)
98 {
99 REGISTER RTNODE *rtn;
100 REGISTER INTBIG i;
101
102 rtn = (RTNODE *)emalloc((sizeof (RTNODE)), cluster);
103 if (rtn == 0) return(NORTNODE);
104 rtn->total = 0;
105 rtn->parent = NORTNODE;
106 rtn->numvar = 0;
107 rtn->firstvar = NOVARIABLE;
108 rtn->lowx = rtn->highx = rtn->lowy = rtn->highy = 0;
109 rtn->flag = 0;
110 for (i=0; i<MAXRTNODESIZE; i++) rtn->pointers[i] = 0;
111 return(rtn);
112 }
113
114 /*
115 * routine to free rtnode "rtn".
116 */
freertnode(RTNODE * rtn)117 void freertnode(RTNODE *rtn)
118 {
119 if (rtn == NORTNODE) return;
120 if (rtn->numvar != 0) db_freevars(&rtn->firstvar, &rtn->numvar);
121 efree((CHAR *)rtn);
122 }
123
124 /*
125 * Routine to allocate a geometry modules from memory cluster "cluster".
126 * The routine returns NOGEOM if allocation fails.
127 */
allocgeom(CLUSTER * cluster)128 GEOM *allocgeom(CLUSTER *cluster)
129 {
130 REGISTER GEOM *geom;
131
132 geom = (GEOM *)emalloc((sizeof (GEOM)), cluster);
133 if (geom == 0) return(NOGEOM);
134 geom->numvar = 0;
135 geom->firstvar = NOVARIABLE;
136 geom->entryisnode = FALSE;
137 geom->entryaddr.ni = NONODEINST;
138 geom->entryaddr.ai = NOARCINST;
139 geom->entryaddr.blind = 0;
140 geom->lowx = geom->highx = geom->lowy = geom->highy = 0;
141 return(geom);
142 }
143
144 /*
145 * routine to free a geometry module
146 */
freegeom(GEOM * geom)147 void freegeom(GEOM *geom)
148 {
149 if (geom == NOGEOM) return;
150 if (geom->numvar != 0) db_freevars(&geom->firstvar, &geom->numvar);
151 efree((CHAR *)geom);
152 }
153
154 /*
155 * routine to allocate a search module from the pool (if any) or memory
156 * the routine returns NOSEARCH if allocation fails.
157 */
db_allocrsearch(void)158 RSEARCH *db_allocrsearch(void)
159 {
160 REGISTER RSEARCH *rs;
161
162 /* grab a free module from the global list */
163 if (db_multiprocessing) emutexlock(db_geomsearchmutex);
164 rs = NORSEARCH;
165 if (db_rsearchfree != NORSEARCH)
166 {
167 /* take search module from free list */
168 rs = db_rsearchfree;
169 db_rsearchfree = (RSEARCH *)db_rsearchfree->lx;
170 }
171 if (db_multiprocessing) emutexunlock(db_geomsearchmutex);
172
173 /* if none on the list, allocate one */
174 if (rs == NORSEARCH)
175 {
176 /* no free search modules...allocate one */
177 rs = (RSEARCH *)emalloc((sizeof (RSEARCH)), db_cluster);
178 if (rs == 0) return(NORSEARCH);
179 }
180 return(rs);
181 }
182
183 /*
184 * routine to free a search module
185 */
db_freersearch(RSEARCH * rs)186 void db_freersearch(RSEARCH *rs)
187 {
188 if (rs == NORSEARCH) return;
189 if (db_multiprocessing) emutexlock(db_geomsearchmutex);
190 rs->lx = (INTBIG)db_rsearchfree;
191 db_rsearchfree = rs;
192 if (db_multiprocessing) emutexunlock(db_geomsearchmutex);
193 }
194
195 /*********************** CREATING A NEW R-TREE ***********************/
196
197 /*
198 * routine to build geometry module structure in cell "np".
199 * returns true upon error.
200 */
geomstructure(NODEPROTO * np)201 BOOLEAN geomstructure(NODEPROTO *np)
202 {
203 REGISTER RTNODE *top;
204
205 top = allocrtnode(np->lib->cluster);
206 if (top == NORTNODE) return(TRUE);
207 top->lowx = top->highx = top->lowy = top->highy = 0;
208 top->total = 0;
209 top->flag = 1;
210 top->parent = NORTNODE;
211 np->rtree = top;
212 return(FALSE);
213 }
214
215 /*
216 * Routine to free the r-tree structure headed by "rtn".
217 */
db_freertree(RTNODE * rtn)218 void db_freertree(RTNODE *rtn)
219 {
220 REGISTER INTBIG i;
221
222 if (rtn->flag == 0)
223 {
224 for(i=0; i<rtn->total; i++)
225 db_freertree((RTNODE *)rtn->pointers[i]);
226 }
227 freertnode(rtn);
228 }
229
230 /*********************** ADDING TO AN R-TREE ***********************/
231
232 /*
233 * routine to link geometry module "geom" into the R-tree. The parent
234 * nodeproto is in "parnt".
235 */
linkgeom(GEOM * geom,NODEPROTO * parnt)236 void linkgeom(GEOM *geom, NODEPROTO *parnt)
237 {
238 REGISTER RTNODE *rtn, *subrtn;
239 REGISTER INTBIG i, bestsubnode;
240 #ifdef USEFLOATS
241 REGISTER float area, newarea, bestexpand, expand;
242 #else
243 REGISTER INTBIG bestexpand, area, newarea, expand, scaledown;
244 #endif
245 REGISTER INTBIG lxv, hxv, lyv, hyv, xd, yd;
246
247 /* setup the bounding box of "geom" */
248 boundobj(geom, &geom->lowx, &geom->highx, &geom->lowy, &geom->highy);
249
250 /* find the leaf that would expand least by adding this node */
251 rtn = parnt->rtree;
252 for(;;)
253 {
254 /* if R-tree node contains primitives, exit loop */
255 if (rtn->flag != 0) break;
256
257 #ifndef USEFLOATS
258 /* compute scaling factor */
259 scaledown = MAXINTBIG;
260 for(i=0; i<rtn->total; i++)
261 {
262 subrtn = (RTNODE *)rtn->pointers[i];
263 xd = subrtn->highx - subrtn->lowx;
264 yd = subrtn->highy - subrtn->lowy;
265 if (xd < scaledown) scaledown = xd;
266 if (yd < scaledown) scaledown = yd;
267 }
268 if (scaledown <= 0) scaledown = 1;
269 #endif
270
271 /* find sub-node that would expand the least */
272 for(i=0; i<rtn->total; i++)
273 {
274 /* get bounds and area of sub-node */
275 subrtn = (RTNODE *)rtn->pointers[i];
276 lxv = subrtn->lowx;
277 hxv = subrtn->highx;
278 lyv = subrtn->lowy;
279 hyv = subrtn->highy;
280 #ifdef USEFLOATS
281 area = hxv - lxv; area *= hyv - lyv;
282 #else
283 area = ((hxv - lxv) / scaledown) * ((hyv - lyv) / scaledown);
284 #endif
285
286 /* get area of sub-node with new element */
287 if (geom->highx > hxv) hxv = geom->highx;
288 if (geom->lowx < lxv) lxv = geom->lowx;
289 if (geom->highy > hyv) hyv = geom->highy;
290 if (geom->lowy < lyv) lyv = geom->lowy;
291 #ifdef USEFLOATS
292 newarea = hxv - lxv; newarea *= hyv - lyv;
293 #else
294 newarea = ((hxv - lxv) / scaledown) * ((hyv - lyv) / scaledown);
295 #endif
296
297 /* accumulate the least expansion */
298 expand = newarea - area;
299
300 /* LINTED "bestexpand" used in proper order */
301 if (i != 0 && expand > bestexpand) continue;
302 bestexpand = expand;
303 bestsubnode = i;
304 }
305
306 /* recurse down to sub-node that expanded least */
307 rtn = (RTNODE *)rtn->pointers[bestsubnode];
308 }
309
310 /* add this geometry element to the correct leaf R-tree node */
311 (void)db_addtortnode((UINTBIG)geom, rtn, parnt);
312 }
313
314 /*
315 * routine to add "object" to R-tree node "rtn". Routine may have to
316 * split the node and recurse up the tree
317 */
db_addtortnode(UINTBIG object,RTNODE * rtn,NODEPROTO * cell)318 BOOLEAN db_addtortnode(UINTBIG object, RTNODE *rtn, NODEPROTO *cell)
319 {
320 RTNODE temp;
321 REGISTER INTBIG i, oldcount, oldn, newn, bestoldnode, bestnewnode;
322 #ifdef USEFLOATS
323 REGISTER float bestoldexpand, bestnewexpand, newareaplus, oldareaplus, newarea, oldarea;
324 #else
325 REGISTER INTBIG bestoldexpand, bestnewexpand, newareaplus, oldareaplus, newarea, oldarea, scaledown;
326 #endif
327 REGISTER INTBIG olddist, newdist, dist;
328 INTBIG lowestxv, highestxv, lowestyv, highestyv, lxv, hxv, lyv, hyv;
329 REGISTER RTNODE *newroot, *newrtn, *r;
330
331 /* see if there is room in the R-tree node */
332 if (rtn->total >= MAXRTNODESIZE)
333 {
334 /*
335 * no room: find the element farthest from new object
336 * also, compute scale and copy node to temporary
337 */
338 #ifndef USEFLOATS
339 scaledown = MAXINTBIG;
340 #endif
341 newdist = 0;
342 temp.flag = rtn->flag;
343 temp.pointers[0] = object;
344 db_rtnbbox(&temp, 0, &lowestxv, &highestxv, &lowestyv, &highestyv);
345 for(i=0; i<rtn->total; i++)
346 {
347 temp.pointers[i] = rtn->pointers[i];
348 db_rtnbbox(rtn, i, &lxv, &hxv, &lyv, &hyv);
349 dist = computedistance((lxv+hxv)/2, (lyv+hyv)/2,
350 (lowestxv+highestxv)/2, (lowestyv+highestyv)/2);
351 if (dist >= newdist)
352 {
353 newdist = dist;
354 newn = i;
355 }
356 #ifndef USEFLOATS
357 if (hxv-lxv < scaledown) scaledown = hxv - lxv;
358 if (hyv-lyv < scaledown) scaledown = hyv - lyv;
359 #endif
360 }
361 #ifndef USEFLOATS
362 if (scaledown <= 0) scaledown = 1;
363 #endif
364
365 /* now find element farthest from "newn" */
366 olddist = 0;
367 db_rtnbbox(rtn, newn, &lowestxv, &highestxv, &lowestyv, &highestyv);
368 for(i=0; i<rtn->total; i++)
369 {
370 if (i == newn) continue;
371 db_rtnbbox(rtn, i, &lxv, &hxv, &lyv, &hyv);
372 dist = computedistance((lxv+hxv)/2, (lyv+hyv)/2,
373 (lowestxv+highestxv)/2, (lowestyv+highestyv)/2);
374 if (dist >= olddist)
375 {
376 olddist = dist;
377 oldn = i;
378 }
379 }
380
381 /* allocate a new R-tree node and put in first seed element */
382 newrtn = allocrtnode(cell->lib->cluster);
383 if (newrtn == NORTNODE) return(TRUE);
384 newrtn->flag = rtn->flag;
385 newrtn->parent = rtn->parent;
386 newrtn->pointers[0] = temp.pointers[newn];
387 temp.pointers[newn] = (UINTBIG)NORTNODE;
388 if (newrtn->flag == 0) ((RTNODE *)newrtn->pointers[0])->parent = newrtn;
389 newrtn->total = 1;
390 db_rtnbbox(newrtn, 0, &newrtn->lowx, &newrtn->highx, &newrtn->lowy, &newrtn->highy);
391 #ifdef USEFLOATS
392 newarea = newrtn->highx - newrtn->lowx; newarea *= newrtn->highy - newrtn->lowy;
393 #else
394 newarea = ((newrtn->highx-newrtn->lowx) / scaledown) *
395 ((newrtn->highy-newrtn->lowy) / scaledown);
396 #endif
397
398 /* initialize old R-tree node and put in other seed element */
399 oldcount = rtn->total;
400 rtn->pointers[0] = temp.pointers[oldn];
401 temp.pointers[oldn] = (UINTBIG)NORTNODE;
402 if (rtn->flag == 0) ((RTNODE *)rtn->pointers[0])->parent = rtn;
403 rtn->total = 1;
404 db_rtnbbox(rtn, 0, &rtn->lowx, &rtn->highx, &rtn->lowy, &rtn->highy);
405 #ifdef USEFLOATS
406 oldarea = rtn->highx - rtn->lowx; oldarea *= rtn->highy - rtn->lowy;
407 #else
408 oldarea = ((rtn->highx - rtn->lowx) / scaledown) * ((rtn->highy - rtn->lowy) / scaledown);
409 #endif
410
411 /* cluster the rest of the nodes */
412 for(;;)
413 {
414 /* search for a cluster about each new node */
415 bestnewnode = bestoldnode = -1;
416 for(i=0; i<oldcount; i++)
417 {
418 if (temp.pointers[i] == (UINTBIG)NORTNODE) continue;
419 db_rtnbbox(&temp, i, &lxv, &hxv, &lyv, &hyv);
420
421 #ifdef USEFLOATS
422 newareaplus = mmaxi(hxv, newrtn->highx) - mmini(lxv, newrtn->lowx);
423 newareaplus *= mmaxi(hyv, newrtn->highy) - mmini(lyv, newrtn->lowy);
424 oldareaplus = mmaxi(hxv, rtn->highx) - mmini(lxv, rtn->lowx);
425 oldareaplus *= mmaxi(hyv, rtn->highy) - mmini(lyv, rtn->lowy);
426 #else
427 newareaplus = ((mmaxi(hxv, newrtn->highx) - mmini(lxv, newrtn->lowx)) / scaledown) *
428 ((mmaxi(hyv, newrtn->highy) - mmini(lyv, newrtn->lowy)) / scaledown);
429 oldareaplus = ((mmaxi(hxv, rtn->highx) - mmini(lxv, rtn->lowx)) / scaledown) *
430 ((mmaxi(hyv, rtn->highy) - mmini(lyv, rtn->lowy)) / scaledown);
431 #endif
432
433 /* LINTED "bestnewexpand" used in proper order */
434 if (bestnewnode < 0 || newareaplus-newarea < bestnewexpand)
435 {
436 bestnewexpand = newareaplus-newarea;
437 bestnewnode = i;
438 }
439
440 /* LINTED "bestoldexpand" used in proper order */
441 if (bestoldnode < 0 || oldareaplus-oldarea < bestoldexpand)
442 {
443 bestoldexpand = oldareaplus-oldarea;
444 bestoldnode = i;
445 }
446 }
447
448 /* if there were no nodes added, all have been clustered */
449 if (bestnewnode == -1 && bestoldnode == -1) break;
450
451 /* if both selected the same object, select another "oldn" */
452 if (bestnewnode == bestoldnode)
453 {
454 bestoldnode = -1;
455 for(i=0; i<oldcount; i++)
456 {
457 if (temp.pointers[i] == (UINTBIG)NORTNODE) continue;
458 if (i == bestnewnode) continue;
459 db_rtnbbox(&temp, i, &lxv, &hxv, &lyv, &hyv);
460
461 #ifdef USEFLOATS
462 oldareaplus = mmaxi(hxv, rtn->highx) - mmini(lxv, rtn->lowx);
463 oldareaplus *= mmaxi(hyv, rtn->highy) - mmini(lyv, rtn->lowy);
464 #else
465 oldareaplus = ((mmaxi(hxv, rtn->highx) - mmini(lxv, rtn->lowx)) / scaledown) *
466 ((mmaxi(hyv, rtn->highy) - mmini(lyv, rtn->lowy)) / scaledown);
467 #endif
468 if (bestoldnode < 0 || oldareaplus-oldarea < bestoldexpand)
469 {
470 bestoldexpand = oldareaplus-oldarea;
471 bestoldnode = i;
472 }
473 }
474 }
475
476 /* add to "oldn" cluster */
477 if (bestoldnode != -1)
478 {
479 /* add this node to "rtn" */
480 rtn->pointers[rtn->total] = temp.pointers[bestoldnode];
481 temp.pointers[bestoldnode] = (UINTBIG)NORTNODE;
482 if (rtn->flag == 0) ((RTNODE *)rtn->pointers[rtn->total])->parent = rtn;
483 db_rtnbbox(rtn, rtn->total, &lxv, &hxv, &lyv, &hyv);
484 rtn->total++;
485 if (lxv < rtn->lowx) rtn->lowx = lxv;
486 if (hxv > rtn->highx) rtn->highx = hxv;
487 if (lyv < rtn->lowy) rtn->lowy = lyv;
488 if (hyv > rtn->highy) rtn->highy = hyv;
489 #ifdef USEFLOATS
490 oldarea = rtn->highx - rtn->lowx;
491 oldarea *= rtn->highy - rtn->lowy;
492 #else
493 oldarea = ((rtn->highx - rtn->lowx) / scaledown) *
494 ((rtn->highy - rtn->lowy) / scaledown);
495 #endif
496 }
497
498 /* add to "newn" cluster */
499 if (bestnewnode != -1)
500 {
501 /* add this node to "newrtn" */
502 newrtn->pointers[newrtn->total] = temp.pointers[bestnewnode];
503 temp.pointers[bestnewnode] = (UINTBIG)NORTNODE;
504 if (newrtn->flag == 0) ((RTNODE *)newrtn->pointers[newrtn->total])->parent = newrtn;
505 db_rtnbbox(newrtn, newrtn->total, &lxv, &hxv, &lyv, &hyv);
506 newrtn->total++;
507 if (lxv < newrtn->lowx) newrtn->lowx = lxv;
508 if (hxv > newrtn->highx) newrtn->highx = hxv;
509 if (lyv < newrtn->lowy) newrtn->lowy = lyv;
510 if (hyv > newrtn->highy) newrtn->highy = hyv;
511 #ifdef USEFLOATS
512 newarea = newrtn->highx - newrtn->lowx;
513 newarea *= newrtn->highy - newrtn->lowy;
514 #else
515 newarea = ((newrtn->highx-newrtn->lowx) / scaledown) *
516 ((newrtn->highy-newrtn->lowy) / scaledown);
517 #endif
518 }
519 }
520
521 /* sensibility check */
522 if (oldcount != rtn->total + newrtn->total)
523 ttyputerr(_("R-trees: %ld nodes split to %d and %d!"),
524 oldcount, rtn->total, newrtn->total);
525
526 /* now recursively insert this new element up the tree */
527 if (rtn->parent == NORTNODE)
528 {
529 /* at top of tree: create a new level */
530 newroot = allocrtnode(cell->lib->cluster);
531 if (newroot == 0) return(TRUE);
532 newroot->total = 2;
533 newroot->pointers[0] = (UINTBIG)rtn;
534 newroot->pointers[1] = (UINTBIG)newrtn;
535 newroot->flag = 0;
536 newroot->parent = NORTNODE;
537 rtn->parent = newrtn->parent = newroot;
538 newroot->lowx = mmini(rtn->lowx, newrtn->lowx);
539 newroot->highx = mmaxi(rtn->highx, newrtn->highx);
540 newroot->lowy = mmini(rtn->lowy, newrtn->lowy);
541 newroot->highy = mmaxi(rtn->highy, newrtn->highy);
542 cell->rtree = newroot;
543 } else
544 {
545 /* first recompute bounding box of R-tree nodes up the tree */
546 for(r = rtn->parent; r != NORTNODE; r = r->parent) db_figbounds(r);
547
548 /* now add the new node up the tree */
549 if (db_addtortnode((UINTBIG)newrtn, rtn->parent, cell)) return(TRUE);
550 }
551 }
552
553 /* now add this element to the R-tree node */
554 rtn->pointers[rtn->total] = object;
555 db_rtnbbox(rtn, rtn->total, &lxv, &hxv, &lyv, &hyv);
556 rtn->total++;
557
558 /* special case when adding the first node in a cell */
559 if (rtn->total == 1 && rtn->parent == NORTNODE)
560 {
561 rtn->lowx = lxv;
562 rtn->highx = hxv;
563 rtn->lowy = lyv;
564 rtn->highy = hyv;
565 return(FALSE);
566 }
567
568 /* recursively update node sizes */
569 for(;;)
570 {
571 rtn->lowx = mmini(rtn->lowx, lxv);
572 rtn->highx = mmaxi(rtn->highx, hxv);
573 rtn->lowy = mmini(rtn->lowy, lyv);
574 rtn->highy = mmaxi(rtn->highy, hyv);
575 if (rtn->parent == NORTNODE) break;
576 rtn = rtn->parent;
577 }
578 return(FALSE);
579 }
580
581 /*********************** DELETING FROM AN R-TREE ***********************/
582
583 /*
584 * routine to remove geometry module "geom" from the R-tree in cell "parnt"
585 */
undogeom(GEOM * geom,NODEPROTO * parnt)586 void undogeom(GEOM *geom, NODEPROTO *parnt)
587 {
588 RTNODE *whichrtn;
589 INTBIG whichind;
590
591 /* find this node in the tree */
592 if (!db_findgeom(parnt->rtree, geom, &whichrtn, &whichind))
593 {
594 if (!db_findgeomanywhere(parnt->rtree, geom, &whichrtn, &whichind))
595 {
596 ttyputerr(_("Internal warning: cannot find %s in R-Tree of %s"),
597 geomname(geom), describenodeproto(parnt));
598 return;
599 }
600 ttyputmsg(_("Internal warning: %s not in proper R-Tree location"),
601 geomname(geom));
602 }
603
604 /* delete geom from this R-tree node */
605 db_removertnode(whichrtn, whichind, parnt);
606 }
607
608 /*
609 * routine to remove entry "ind" from R-tree node "rtn" in cell "cell"
610 */
db_removertnode(RTNODE * rtn,INTBIG ind,NODEPROTO * cell)611 void db_removertnode(RTNODE *rtn, INTBIG ind, NODEPROTO *cell)
612 {
613 REGISTER RTNODE *prtn;
614 RTNODE temp;
615 REGISTER INTBIG i, j, t;
616
617 /* delete entry from this R-tree node */
618 j = 0;
619 for(i=0; i<rtn->total; i++)
620 if (i != ind) rtn->pointers[j++] = rtn->pointers[i];
621 rtn->total = (INTSML)j;
622
623 /* see if node is now too small */
624 if (rtn->total < MINRTNODESIZE)
625 {
626 /* if recursed to top, shorten R-tree */
627 prtn = rtn->parent;
628 if (prtn == NORTNODE)
629 {
630 /* if tree has no hierarchy, allow short node */
631 if (rtn->flag != 0)
632 {
633 /* compute correct bounds of the top node */
634 db_figbounds(rtn);
635 return;
636 }
637
638 /* save all top-level entries */
639 for(i=0; i<rtn->total; i++) temp.pointers[i] = rtn->pointers[i];
640 t = rtn->total;
641
642 /* erase top level */
643 rtn->total = 0;
644 rtn->flag = 1;
645
646 /* reinsert all data */
647 for(i=0; i<t; i++) db_reinsert((RTNODE *)temp.pointers[i], cell);
648 return;
649 }
650
651 /* node has too few entries, must delete it and reinsert members */
652 for(i=0; i<prtn->total; i++)
653 if (prtn->pointers[i] == (UINTBIG)rtn) break;
654 if (i >= prtn->total) ttyputerr(_("R-trees: cannot find entry in parent"));
655
656 /* remove this entry from its parent */
657 db_removertnode(prtn, i, cell);
658
659 /* reinsert the entries */
660 db_reinsert(rtn, cell);
661 return;
662 }
663
664 /* recompute bounding box of this R-tree node and all up the tree */
665 for(;;)
666 {
667 db_figbounds(rtn);
668 if (rtn->parent == NORTNODE) break;
669 rtn = rtn->parent;
670 }
671 }
672
673 /*
674 * routine to reinsert the tree of nodes below "rtn" into cell "cell".
675 */
db_reinsert(RTNODE * rtn,NODEPROTO * cell)676 void db_reinsert(RTNODE *rtn, NODEPROTO *cell)
677 {
678 REGISTER INTBIG i;
679
680 if (rtn->flag != 0)
681 {
682 for(i=0; i<rtn->total; i++) linkgeom((GEOM *)rtn->pointers[i], cell);
683 } else
684 {
685 for(i=0; i<rtn->total; i++)
686 db_reinsert((RTNODE *)rtn->pointers[i], cell);
687 }
688 freertnode(rtn);
689 }
690
691 /*
692 * routine to find the location of geometry module "geom" in the R-tree
693 * at "rtn". The subnode that contains this module is placed in "subrtn"
694 * and the index in that subnode is placed in "subind". The routine returns
695 * false if it is unable to find the geometry module.
696 */
db_findgeom(RTNODE * rtn,GEOM * geom,RTNODE ** subrtn,INTBIG * subind)697 BOOLEAN db_findgeom(RTNODE *rtn, GEOM *geom, RTNODE **subrtn, INTBIG *subind)
698 {
699 REGISTER INTBIG i;
700 INTBIG lxv, hxv, lyv, hyv;
701
702 /* if R-tree node contains primitives, search for direct hit */
703 if (rtn->flag != 0)
704 {
705 for(i=0; i<rtn->total; i++)
706 {
707 if (rtn->pointers[i] == (UINTBIG)geom)
708 {
709 *subrtn = rtn;
710 *subind = i;
711 return(TRUE);
712 }
713 }
714 return(FALSE);
715 }
716
717 /* recurse on all sub-nodes that would contain this geometry module */
718 for(i=0; i<rtn->total; i++)
719 {
720 /* get bounds and area of sub-node */
721 db_rtnbbox(rtn, i, &lxv, &hxv, &lyv, &hyv);
722 if (geom->lowx < lxv || geom->highx > hxv || geom->lowy < lyv || geom->highy > hyv)
723 continue;
724 if (db_findgeom((RTNODE *)rtn->pointers[i], geom, subrtn, subind)) return(TRUE);
725 }
726 return(FALSE);
727 }
728
729 /*
730 * routine to find the location of geometry module "geom" anywhere in the R-tree
731 * at "rtn". The subnode that contains this module is placed in "subrtn"
732 * and the index in that subnode is placed in "subind". The routine returns
733 * false if it is unable to find the geometry module.
734 */
db_findgeomanywhere(RTNODE * rtn,GEOM * geom,RTNODE ** subrtn,INTBIG * subind)735 BOOLEAN db_findgeomanywhere(RTNODE *rtn, GEOM *geom, RTNODE **subrtn, INTBIG *subind)
736 {
737 REGISTER INTBIG i;
738
739 /* if R-tree node contains primitives, search for direct hit */
740 if (rtn->flag != 0)
741 {
742 for(i=0; i<rtn->total; i++)
743 {
744 if (rtn->pointers[i] == (UINTBIG)geom)
745 {
746 *subrtn = rtn;
747 *subind = i;
748 return(1);
749 }
750 }
751 return(FALSE);
752 }
753
754 /* recurse on all sub-nodes */
755 for(i=0; i<rtn->total; i++)
756 if (db_findgeomanywhere((RTNODE *)rtn->pointers[i], geom, subrtn, subind))
757 return(TRUE);
758 return(FALSE);
759 }
760
761 /************************ CHANGING AN R-TREE ************************/
762
763 /*
764 * routine to adjust the 8-way linked list when the size or position
765 * of the object in "geom" has changed.
766 */
updategeom(GEOM * geom,NODEPROTO * parnt)767 void updategeom(GEOM *geom, NODEPROTO *parnt)
768 {
769 /* first remove the module from the R-tree */
770 undogeom(geom, parnt);
771
772 /* now re-insert the module in the R-tree */
773 linkgeom(geom, parnt);
774 }
775
776 /*********************** INFORMATION ***********************/
777
db_printrtree(RTNODE * expectedparent,RTNODE * rtn,INTBIG indent)778 void db_printrtree(RTNODE *expectedparent, RTNODE *rtn, INTBIG indent)
779 {
780 REGISTER INTBIG i, j;
781 INTBIG lx, hx, ly, hy, lowestxv, highestxv, lowestyv, highestyv;
782 CHAR line[100];
783 REGISTER void *infstr;
784
785 infstr = initinfstr();
786 for(i=0; i<indent; i++) addtoinfstr(infstr, ' ');
787 (void)esnprintf(line, 100, M_("Node X(%s-%s) Y(%s-%s) has %d children:"),
788 latoa(rtn->lowx, 0), latoa(rtn->highx, 0), latoa(rtn->lowy, 0), latoa(rtn->highy, 0), rtn->total);
789 addstringtoinfstr(infstr, line);
790
791 /* sensibility check of this R-tree node */
792 if (rtn->parent != expectedparent) addstringtoinfstr(infstr, M_(" WRONG-PARENT"));
793 if (rtn->total > MAXRTNODESIZE) addstringtoinfstr(infstr, M_(" TOO-MANY"));
794 if (rtn->total < MINRTNODESIZE && rtn->parent != NORTNODE)
795 addstringtoinfstr(infstr, M_(" TOO-FEW"));
796 if (rtn->total != 0)
797 {
798 db_rtnbbox(rtn, 0, &lowestxv, &highestxv, &lowestyv, &highestyv);
799 for(j=1; j<rtn->total; j++)
800 {
801 db_rtnbbox(rtn, j, &lx, &hx, &ly, &hy);
802 if (lx < lowestxv) lowestxv = lx;
803 if (hx > highestxv) highestxv = hx;
804 if (ly < lowestyv) lowestyv = ly;
805 if (hy > highestyv) highestyv = hy;
806 }
807 if (rtn->lowx != lowestxv || rtn->highx != highestxv ||
808 rtn->lowy != lowestyv || rtn->highy != highestyv)
809 addstringtoinfstr(infstr, M_(" WRONG-BOUNDS"));
810 rtn->lowx = lowestxv;
811 rtn->highx = highestxv;
812 rtn->lowy = lowestyv;
813 rtn->highy = highestyv;
814 }
815 ttyputmsg(x_("%s"), returninfstr(infstr));
816
817 for(j=0; j<rtn->total; j++)
818 {
819 if (rtn->flag != 0)
820 {
821 infstr = initinfstr();
822 for(i=0; i<indent+3; i++) addtoinfstr(infstr, ' ');
823 addstringtoinfstr(infstr, geomname((GEOM *)rtn->pointers[j]));
824 db_rtnbbox(rtn, j, &lx, &hx, &ly, &hy);
825 (void)esnprintf(line, 100, x_(" X(%s-%s) Y(%s-%s)"),
826 latoa(lx, 0), latoa(hx, 0), latoa(ly, 0), latoa(hy, 0));
827 addstringtoinfstr(infstr, line);
828 ttyputmsg(x_("%s"), returninfstr(infstr));
829 } else db_printrtree(rtn, (RTNODE *)rtn->pointers[j], indent+3);
830 }
831 }
832
833 /*
834 * routine to recompute the bounds of R-tree node "rtn"
835 */
db_figbounds(RTNODE * rtn)836 void db_figbounds(RTNODE *rtn)
837 {
838 REGISTER INTBIG i;
839 INTBIG lx, hx, ly, hy;
840
841 if (rtn->total == 0)
842 {
843 rtn->lowx = rtn->highx = rtn->lowy = rtn->highy = 0;
844 return;
845 }
846 db_rtnbbox(rtn, 0, &rtn->lowx, &rtn->highx, &rtn->lowy, &rtn->highy);
847 for(i=1; i<rtn->total; i++)
848 {
849 db_rtnbbox(rtn, i, &lx, &hx, &ly, &hy);
850 if (lx < rtn->lowx) rtn->lowx = lx;
851 if (hx > rtn->highx) rtn->highx = hx;
852 if (ly < rtn->lowy) rtn->lowy = ly;
853 if (hy > rtn->highy) rtn->highy = hy;
854 }
855 }
856
857 /*
858 * routine to get the bounding box of child "child" of R-tree node "rtn" and
859 * place it in the reference parameters "lx", "hx", "ly", and "hy".
860 */
db_rtnbbox(RTNODE * rtn,INTBIG child,INTBIG * lx,INTBIG * hx,INTBIG * ly,INTBIG * hy)861 void db_rtnbbox(RTNODE *rtn, INTBIG child, INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy)
862 {
863 REGISTER RTNODE *subrtn;
864 REGISTER GEOM *geom;
865
866 if (rtn->flag == 0)
867 {
868 subrtn = (RTNODE *)rtn->pointers[child];
869 *lx = subrtn->lowx;
870 *hx = subrtn->highx;
871 *ly = subrtn->lowy;
872 *hy = subrtn->highy;
873 } else
874 {
875 geom = (GEOM *)rtn->pointers[child];
876 *lx = geom->lowx;
877 *hx = geom->highx;
878 *ly = geom->lowy;
879 *hy = geom->highy;
880 }
881 }
882
883 /*
884 * routine to establish the bounding box of geometry module "geom" by filling
885 * the reference parameters "lx", "hx", "ly", and "hy" with the minimum
886 * bounding rectangle.
887 */
boundobj(GEOM * geom,INTBIG * lx,INTBIG * hx,INTBIG * ly,INTBIG * hy)888 void boundobj(GEOM *geom, INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy)
889 {
890 REGISTER INTBIG end0extend, end1extend, radius, angle, j, pts,
891 xs, ys, xe, ye, xc, yc, xv, yv;
892 INTBIG x1, y1, x2, y2, num, xp, yp, plx, phx, ply, phy;
893 double startoffset, endangle, ctx, cty, a, b, p;
894 XARRAY trans;
895 REGISTER ARCINST *ai;
896 REGISTER NODEINST *ni;
897 REGISTER VARIABLE *var;
898 REGISTER POLYGON *poly;
899
900 if (geom->entryisnode)
901 {
902 ni = geom->entryaddr.ni;
903
904 /* handle special cases primitives */
905 if (ni->proto->primindex != 0)
906 {
907 /* special case for arcs of circles: compute precise bounding box */
908 if (ni->proto == art_circleprim || ni->proto == art_thickcircleprim)
909 {
910 /* see if there this circle is only a partial one */
911 getarcdegrees(ni, &startoffset, &endangle);
912 if (startoffset != 0.0 || endangle != 0.0)
913 {
914 /* get center of ellipse */
915 ctx = (ni->lowx + ni->highx) / 2;
916 cty = (ni->lowy + ni->highy) / 2;
917
918 /* compute the length of the semi-major and semi-minor axes */
919 a = (ni->highx - ni->lowx) / 2;
920 b = (ni->highy - ni->lowy) / 2;
921
922 pts = (INTBIG)(endangle * ELLIPSEPOINTS / (EPI * 2.0));
923 makerot(ni, trans);
924 for(j=0; j<pts; j++)
925 {
926 p = startoffset + j * endangle / (pts-1);
927 xv = rounddouble(ctx + a * cos(p));
928 yv = rounddouble(cty + b * sin(p));
929 xform(xv, yv, &xp, &yp, trans);
930 if (j == 0)
931 {
932 *lx = *hx = xp;
933 *ly = *hy = yp;
934 } else
935 {
936 if (xp < *lx) *lx = xp;
937 if (xp > *hx) *hx = xp;
938 if (yp < *ly) *ly = yp;
939 if (yp > *hy) *hy = yp;
940 }
941 }
942 return;
943 }
944 }
945
946 /* special case for pins that become steiner points */
947 if ((ni->proto->userbits&WIPEON1OR2) != 0 &&
948 ni->firstportexpinst == NOPORTEXPINST)
949 {
950 if (tech_pinusecount(ni, NOWINDOWPART))
951 {
952 *lx = *hx = (ni->lowx + ni->highx) / 2;
953 *ly = *hy = (ni->lowy + ni->highy) / 2;
954 return;
955 }
956 }
957
958 /* special case for polygonally-defined nodes: compute precise geometry */
959 if ((ni->proto->userbits&HOLDSTRACE) != 0)
960 {
961 var = gettrace(ni);
962 if (var != NOVARIABLE)
963 {
964 poly = allocpolygon(4, db_cluster);
965 makerot(ni, trans);
966 num = nodepolys(ni, 0, NOWINDOWPART);
967 for(j=0; j<num; j++)
968 {
969 shapenodepoly(ni, j, poly);
970 xformpoly(poly, trans);
971 getbbox(poly, &plx, &phx, &ply, &phy);
972 if (j == 0)
973 {
974 *lx = plx; *hx = phx;
975 *ly = ply; *hy = phy;
976 } else
977 {
978 if (plx < *lx) *lx = plx;
979 if (phx > *hx) *hx = phx;
980 if (ply < *ly) *ly = ply;
981 if (phy > *hy) *hy = phy;
982 }
983 }
984 freepolygon(poly);
985 return;
986 }
987 }
988 }
989
990 /* standard bounds computation */
991 if (ni->rotation == 0 && ni->transpose == 0)
992 {
993 *lx = ni->lowx; *hx = ni->highx;
994 *ly = ni->lowy; *hy = ni->highy;
995 } else
996 {
997 makerot(ni, trans);
998 *lx = ni->lowx; *hx = ni->highx;
999 *ly = ni->lowy; *hy = ni->highy;
1000 xformbox(lx, hx, ly, hy, trans);
1001 }
1002 } else
1003 {
1004 ai = geom->entryaddr.ai;
1005
1006 /* special case if the arc is curved */
1007 if ((ai->proto->userbits&CANCURVE) != 0)
1008 {
1009 /* prototype can curve...does this one have curvature? */
1010 var = getvalkey((INTBIG)ai, VARCINST, VINTEGER, el_arc_radius_key);
1011 if (var != NOVARIABLE)
1012 {
1013 /* this one has curvature...verify its sensibility */
1014 radius = var->addr;
1015 if (abs(radius)*2 >= ai->length)
1016 {
1017 /* arc is sensible...determine possible circle centers */
1018 if (!findcenters(abs(radius), ai->end[0].xpos,
1019 ai->end[0].ypos, ai->end[1].xpos, ai->end[1].ypos,
1020 ai->length, &x1, &y1, &x2, &y2))
1021 {
1022 /* determine center */
1023 if (radius < 0)
1024 {
1025 xc = x1; yc = y1;
1026 } else
1027 {
1028 xc = x2; yc = y2;
1029 }
1030
1031 /* determine start and endpoint */
1032 if ((ai->userbits&REVERSEEND) != 0)
1033 {
1034 xs = ai->end[1].xpos;
1035 ys = ai->end[1].ypos;
1036 xe = ai->end[0].xpos;
1037 ye = ai->end[0].ypos;
1038 } else
1039 {
1040 xs = ai->end[0].xpos;
1041 ys = ai->end[0].ypos;
1042 xe = ai->end[1].xpos;
1043 ye = ai->end[1].ypos;
1044 }
1045
1046 /*
1047 * compute bounding box for this arc.
1048 * Note that the start and end are reversed because
1049 * "arcbbox" takes clockwise arcs, but this one is
1050 * computed with counterclockwise points.
1051 */
1052 arcbbox(xe, ye, xs, ys, xc, yc, lx, hx, ly, hy);
1053 return;
1054 }
1055 }
1056 }
1057 }
1058
1059 /* straight arc...get endpoint extension factor */
1060 end0extend = end1extend = ai->width / 2;
1061 if ((ai->userbits&NOEXTEND) != 0)
1062 {
1063 if ((ai->userbits&NOTEND0) == 0) end0extend = 0;
1064 if ((ai->userbits&NOTEND1) == 0) end1extend = 0;
1065 } else if ((ai->userbits&ASHORT) != 0)
1066 {
1067 end0extend = tech_getextendfactor(ai->width, ai->endshrink & 0xFFFF);
1068 end1extend = tech_getextendfactor(ai->width, (ai->endshrink >> 16) & 0xFFFF);
1069 }
1070
1071 /* construct a polygon describing the arc */
1072 angle = (ai->userbits&AANGLE) >> AANGLESH;
1073 poly = allocpolygon(4, db_cluster);
1074 tech_makeendpointpoly(ai->length, ai->width, angle*10, ai->end[0].xpos,
1075 ai->end[0].ypos, end0extend, ai->end[1].xpos,
1076 ai->end[1].ypos, end1extend, poly);
1077 poly->style = FILLED;
1078
1079 /* get the bounding box of the polygon as the arc extent */
1080 getbbox(poly, lx, hx, ly, hy);
1081 freepolygon(poly);
1082 }
1083 }
1084
1085 /*
1086 * routine to compute the boundary of nodeproto "cell" and fill the
1087 * reference parameters "lx", "hx", "ly", and "hy" with the minimum
1088 * bounding rectangle
1089 */
db_boundcell(NODEPROTO * cell,INTBIG * lx,INTBIG * hx,INTBIG * ly,INTBIG * hy)1090 void db_boundcell(NODEPROTO *cell, INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy)
1091 {
1092 REGISTER NODEINST *ni;
1093 REGISTER ARCINST *ai;
1094 REGISTER VARIABLE *var;
1095 REGISTER BOOLEAN first;
1096 REGISTER INTBIG i;
1097
1098 /* cannot compute bounds if cell has nothing in it */
1099 *lx = *hx = *ly = *hy = 0;
1100 if (cell->firstnodeinst == NONODEINST) return;
1101
1102 /* include all nodes in the cell */
1103 first = TRUE;
1104 for(ni = cell->firstnodeinst; ni != NONODEINST; ni = ni->nextnodeinst)
1105 {
1106 /* special case: do not include "cell center" primitives from Generic */
1107 if (ni->proto == gen_cellcenterprim /* || ni->proto == gen_essentialprim */ ) continue;
1108
1109 /* special case for invisible pins: do not include if inheritable or interior-only */
1110 if (ni->proto == gen_invispinprim)
1111 {
1112 for(i=0; i<ni->numvar; i++)
1113 {
1114 var = &ni->firstvar[i];
1115 if ((var->type&VDISPLAY) != 0 &&
1116 (TDGETINTERIOR(var->textdescript) != 0 ||
1117 TDGETINHERIT(var->textdescript) != 0)) break;
1118 }
1119 if (i < ni->numvar) continue;
1120 }
1121
1122 if (first)
1123 {
1124 *lx = ni->geom->lowx;
1125 *hx = ni->geom->highx;
1126 *ly = ni->geom->lowy;
1127 *hy = ni->geom->highy;
1128 first = FALSE;
1129 continue;
1130 }
1131 *lx = mmini(*lx, ni->geom->lowx);
1132 *hx = mmaxi(*hx, ni->geom->highx);
1133 *ly = mmini(*ly, ni->geom->lowy);
1134 *hy = mmaxi(*hy, ni->geom->highy);
1135 }
1136
1137 /* include all arcs in the cell */
1138 for(ai = cell->firstarcinst; ai != NOARCINST; ai = ai->nextarcinst)
1139 {
1140 if (first)
1141 {
1142 *lx = ai->geom->lowx;
1143 *hx = ai->geom->highx;
1144 *ly = ai->geom->lowy;
1145 *hy = ai->geom->highy;
1146 first = FALSE;
1147 continue;
1148 }
1149 *lx = mmini(*lx, ai->geom->lowx);
1150 *hx = mmaxi(*hx, ai->geom->highx);
1151 *ly = mmini(*ly, ai->geom->lowy);
1152 *hy = mmaxi(*hy, ai->geom->highy);
1153 }
1154 }
1155
1156 /************************ SEARCHING ************************/
1157
1158 /*
1159 * search routine initialization. Begin search for objects that are in
1160 * cell "cell" and fall in the bounding box X from "lx" to "hx" and
1161 * Y from "ly" to "hy". Routine returns value that is passed to
1162 * "nextobject" calls to run the search.
1163 */
initsearch(INTBIG lx,INTBIG hx,INTBIG ly,INTBIG hy,NODEPROTO * cell)1164 INTBIG initsearch(INTBIG lx, INTBIG hx, INTBIG ly, INTBIG hy, NODEPROTO *cell)
1165 {
1166 REGISTER RSEARCH *rs;
1167
1168 rs = db_allocrsearch();
1169 if (rs == NORSEARCH) return(-1);
1170 rs->depth = 0;
1171 rs->rtn[0] = cell->rtree;
1172 rs->position[0] = 0;
1173 rs->lx = lx;
1174 rs->hx = hx;
1175 rs->ly = ly;
1176 rs->hy = hy;
1177 return((INTBIG)rs);
1178 }
1179
1180 /*
1181 * second routine for searches: takes the search module returned by
1182 * "initsearch" and returns the next geometry module in the
1183 * search area. If there are no more, this returns NOGEOM.
1184 */
nextobject(INTBIG rsin)1185 GEOM *nextobject(INTBIG rsin)
1186 {
1187 RSEARCH *rs;
1188 REGISTER RTNODE *rtn;
1189 REGISTER INTBIG i, depth;
1190 INTBIG lxv, hxv, lyv, hyv;
1191
1192 rs = (RSEARCH *)rsin;
1193 if (rs == NORSEARCH) return(NOGEOM);
1194 for(;;)
1195 {
1196 depth = rs->depth;
1197 rtn = rs->rtn[depth];
1198 i = rs->position[depth]++;
1199 if (i < rtn->total)
1200 {
1201 db_rtnbbox(rtn, i, &lxv, &hxv, &lyv, &hyv);
1202 if (rs->lx > hxv || rs->hx < lxv || rs->ly > hyv || rs->hy < lyv) continue;
1203 if (rtn->flag != 0) return((GEOM *)rtn->pointers[i]);
1204
1205 /* look down the hierarchy */
1206 if (rs->depth >= MAXDEPTH-1)
1207 {
1208 ttyputerr(_("R-trees: search too deep"));
1209 continue;
1210 }
1211 rs->depth++;
1212 rs->rtn[rs->depth] = (RTNODE *)rtn->pointers[i];
1213 rs->position[rs->depth] = 0;
1214 } else
1215 {
1216 /* pop up the hierarchy */
1217 if (depth == 0) break;
1218 rs->depth--;
1219 }
1220 }
1221 db_freersearch(rs);
1222 return(NOGEOM);
1223 }
1224
1225 /*
1226 * routine to clean up after a search. Takes the search module returned by
1227 * "initsearch" and frees it. This routine only needs to be called if the loop
1228 * through all neighbors is aborted BEFORE "nextobject" returns NOGEOM.
1229 */
termsearch(INTBIG rsin)1230 void termsearch(INTBIG rsin)
1231 {
1232 RSEARCH *rs;
1233
1234 rs = (RSEARCH *)rsin;
1235 if (rs != NORSEARCH) db_freersearch(rs);
1236 }
1237