1 // ************************************************************************
2 //
3 // Copyright (c) 1995-2002 Juniper Networks, Inc. All rights reserved.
4 //
5 // Permission is hereby granted, without written agreement and without
6 // license or royalty fees, to use, copy, modify, and distribute this
7 // software and its documentation for any purpose, provided that the
8 // above copyright notice and the following three paragraphs appear in
9 // all copies of this software.
10 //
11 // IN NO EVENT SHALL JUNIPER NETWORKS, INC. BE LIABLE TO ANY PARTY FOR
12 // DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
13 // ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
14 // JUNIPER NETWORKS, INC. HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
15 // DAMAGE.
16 //
17 // JUNIPER NETWORKS, INC. SPECIFICALLY DISCLAIMS ANY WARRANTIES,
18 // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
20 // NON-INFRINGEMENT.
21 //
22 // THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND JUNIPER
23 // NETWORKS, INC. HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
24 // UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
25 //
26 // ************************************************************************
27
28
29
30 /* bpMain.c
31 *
32 * Top-level routines for BPlanes
33 * (interface to other modules)
34 *
35 * See bpEnum.c for enum routines.
36 * See bpTcl.c for tcl-level interface.
37 */
38
39 #include <stdio.h>
40 #include "utils/utils.h"
41 #include "utils/malloc.h"
42 #include "database/database.h"
43 #include "textio/textio.h"
44 #include "utils/geometry.h"
45 #include "bplane/bplaneInt.h"
46
47 /*
48 * ----------------------------------------------------------------------------
49 * BPNew --
50 *
51 * Return newly created BPlane.
52 *
53 * ----------------------------------------------------------------------------
54 */
BPNew(void)55 BPlane *BPNew(void)
56 {
57 BPlane *new;
58
59 new = (BPlane *)mallocMagic(sizeof(BPlane));
60
61 new->bp_bbox = GeoNullRect;
62 new->bp_bbox_exact = TRUE;
63
64 new->bp_count = 0;
65
66 /* ENUMS */
67 new->bp_enums = NULL;
68
69 /* HASH TABLE */
70 new->bp_hashTable = IHashInit(4, /* initial buckets */
71 OFFSET(Element, e_rect), /* key */
72 OFFSET(Element, e_hashLink),
73 IHash4WordKeyHash,
74 IHash4WordKeyEq);
75
76 /* IN BOX */
77 new->bp_inBox = NULL;
78
79 /* BINS */
80 new->bp_binLife = 0;
81 new->bp_inAdds = 0;
82 new->bp_binArea = GeoNullRect;
83 new->bp_rootNode = NULL;
84
85 return new;
86 }
87
88 /*
89 * ----------------------------------------------------------------------------
90 * BPFree --
91 *
92 * free (empty) BPlane
93 *
94 * ----------------------------------------------------------------------------
95 */
BPFree(BPlane * bp)96 void BPFree(BPlane *bp)
97 {
98 ASSERT(bp->bp_count == 0,"BPFree");
99 IHashFree(bp->bp_hashTable);
100 freeMagic((char *)bp);
101 }
102
103 /*
104 * ----------------------------------------------------------------------------
105 * BPAdd --
106 *
107 * Add element to the given bplane
108 *
109 * NOTE: e_rect better be canonical!
110 *
111 * ----------------------------------------------------------------------------
112 */
BPAdd(BPlane * bp,void * element)113 void BPAdd(BPlane *bp, void *element)
114 {
115 int size;
116 int binDim;
117 Element * e = element;
118 Rect *r = &e->e_rect;
119
120 /* Don't allow adds during active enumerations.
121 * This is confusing, since newly added elements may or may not
122 * be enumerated in on going enumerations, is not particularly
123 * useful, since elements to add can just be stored up on a local
124 * list and added after the enumeration completes.
125 */
126 ASSERT(!bp->bp_enums,
127 "BPAdd, attempted during active enumerations");
128
129 /* element rect must be canonical! */
130 #ifdef PARANOID
131 ASSERT(GeoIsCanonicalRect(r),"BPAdd, rect must be canonical.");
132 #endif
133
134 bp->bp_count++;
135
136 /* update hash table */
137 IHashAdd(bp->bp_hashTable, element);
138
139 /* update bbox */
140 if(bp->bp_count == 1)
141 {
142 bp->bp_bbox = *r;
143 }
144 else
145 {
146 GeoIncludeRectInBBox(r,&bp->bp_bbox);
147 }
148
149 /* no bins? */
150 if(!bp->bp_rootNode) goto inBox;
151
152 /* doesn't fit inside bins ? */
153 if(!GEO_SURROUND(&bp->bp_binArea,r)) goto inBox;
154
155 /* bin element */
156 bpBinAdd(bp->bp_rootNode, e);
157 return;
158
159 /* add to in box */
160 inBox:
161 bp->bp_inAdds++;
162 e->e_link = bp->bp_inBox;
163 bp->bp_inBox = e;
164
165 /* maintain back pointers */
166 e->e_linkp = &bp->bp_inBox;
167 if(e->e_link) e->e_link->e_linkp = &e->e_link;
168
169 }
170
171 /*
172 * ----------------------------------------------------------------------------
173 * BPDelete --
174 *
175 * remove element from bplane
176 *
177 * ----------------------------------------------------------------------------
178 */
BPDelete(BPlane * bp,void * element)179 void BPDelete(BPlane *bp, void *element)
180 {
181 Element *e = element;
182
183 ASSERT(e,"BPDelete");
184 if (bp->bp_count == 0)
185 {
186 TxError("Error: Attempt to delete instance from empty cell!\n");
187 return;
188 }
189 bp->bp_count--;
190
191 /* if element was on edge of bbox, bbox may no longer
192 * be exact.
193 */
194 if(bp->bp_bbox_exact &&
195 (bp->bp_bbox.r_xbot == e->e_rect.r_xbot ||
196 bp->bp_bbox.r_xtop == e->e_rect.r_xtop ||
197 bp->bp_bbox.r_ybot == e->e_rect.r_ybot ||
198 bp->bp_bbox.r_ytop == e->e_rect.r_ytop))
199 {
200 bp->bp_bbox_exact = FALSE;
201 }
202
203 /* advance any nextElement pointers at e */
204 {
205 BPEnum *bpe;
206
207 for(bpe=bp->bp_enums; bpe; bpe=bpe->bpe_next)
208 {
209 if(bpe->bpe_nextElement != e) continue;
210
211 if(bpe->bpe_match == BPE_EQUAL)
212 {
213 bpe->bpe_nextElement = IHashLookUpNext(bp->bp_hashTable, e);
214 }
215 else
216 {
217 bpe->bpe_nextElement = e->e_link;
218 }
219 }
220 }
221
222 IHashDelete(bp->bp_hashTable, e);
223
224 /* next pointer of prev element */
225 *e->e_linkp = e->e_link;
226
227 /* back pointer of next element */
228 if(e->e_link) e->e_link->e_linkp = e->e_linkp;
229 }
230
231 /*
232 * ----------------------------------------------------------------------------
233 * BPBBox --
234 *
235 * Get current bplane bbox.
236 *
237 * returns: current bplane bbox
238 * (returns an inverted rect, if bplane is empty)
239 *
240 * ----------------------------------------------------------------------------
241 */
BPBBox(BPlane * bp)242 Rect BPBBox(BPlane *bp)
243 {
244
245 if(bp->bp_count == 0) return GeoInvertedRect;
246
247 /* if bbox is not up-to-date, recompute */
248 if(!bp->bp_bbox_exact)
249 {
250 BPEnum bpe;
251 Element *e;
252
253 bp->bp_bbox_exact = TRUE;
254
255 BPEnumInit(&bpe,
256 bp,
257 NULL,
258 BPE_ALL,
259 "BPBBox");
260
261 e = BPEnumNext(&bpe);
262 bp->bp_bbox = e->e_rect;
263
264 while(e = BPEnumNext(&bpe))
265 {
266 GeoIncludeRectInBBox(&e->e_rect, &bp->bp_bbox);
267 }
268 }
269
270 return bp->bp_bbox;
271 }
272
273
274
275
276
277
278
279
280