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 #ifndef _BPENUM_H
29 #define _BPENUM_H
30
31 /* bpEnum.h --
32 *
33 * inlined Search routines for bplanes (see also bpEnum.c)
34 *
35 */
36
37 #include <stdio.h>
38 #include "utils/utils.h"
39 #include "utils/geometry.h"
40 #include "utils/geofast.h"
41 #include "bplane/bplane.h"
42 #include "bplane/bplaneInt.h"
43
44 extern void DumpRect(char *msg, Rect *r);
45
46 /* state machine states */
47 #define BPS_BINS 0
48 #define BPS_BINS_INSIDE 1
49 #define BPS_INBOX 2
50 #define BPS_INBOX_INSIDE 3
51 #define BPS_HASH 4
52 #define BPS_DONE 5
53
54 /* range code */
55 #define R_LEFT 1
56 #define R_RIGHT 2
57 #define R_BOT 4
58 #define R_TOP 8
59
60 /*
61 * ----------------------------------------------------------------------------
62 *
63 * bpBinArea -- compute area covered by given bin.
64 *
65 * Returns: bin area.
66 *
67 * ----------------------------------------------------------------------------
68 */
bpBinArea(BinArray * ba,int i)69 static __inline__ Rect bpBinArea(BinArray *ba, int i)
70 {
71 int dimX = ba->ba_dimX;
72 int dx = ba->ba_dx;
73 int dy = ba->ba_dy;
74 int xi = i % dimX;
75 int yi = i / dimX;
76 Rect area;
77
78 area.r_xbot = ba->ba_bbox.r_xbot + dx*xi;
79 area.r_ybot = ba->ba_bbox.r_ybot + dy*yi;
80 area.r_xtop = area.r_xbot + dx;
81 area.r_ytop = area.r_ybot + dy;
82
83 return area;
84 }
85
86 /*
87 * ----------------------------------------------------------------------------
88 * bpEnumRange --
89 *
90 * Determine which edges of search area bin overlaps.
91 *
92 * (Used to make match checks as efficient as possible, for example if bin
93 * does not extend past srch area in any direction, no match checking is
94 * required)
95 *
96 * Returns: int encoding 'range'.
97 *
98 * ----------------------------------------------------------------------------
99 */
100 static __inline__ int
bpEnumRange(Rect * bin,Rect * srch)101 bpEnumRange(Rect *bin, Rect *srch)
102 {
103 int range = 0;
104
105 if (bin->r_xbot < srch->r_xbot) range |= R_LEFT;
106 if (bin->r_xtop > srch->r_xtop) range |= R_RIGHT;
107 if (bin->r_ybot < srch->r_ybot) range |= R_BOT;
108 if (bin->r_ytop > srch->r_ytop) range |= R_TOP;
109
110 return range;
111 }
112
113 /*
114 * ----------------------------------------------------------------------------
115 * bpEnumMatchQ -
116 *
117 * Check if element intersects search area
118 *
119 * range specifies which search area boundaries the element
120 * can potentially extend beyond.
121 *
122 * We rely on the optimizing compiler to remove unnecessary checks
123 * based on compile time knowledge of range value.
124 *
125 * Returns: TRUE on match, FALSE otherwise.
126 *
127 * ----------------------------------------------------------------------------
128 */
129 static __inline__ bool
bpEnumMatchQ(BPEnum * bpe,Element * e)130 bpEnumMatchQ(BPEnum *bpe, Element *e)
131 {
132 Rect *area = &bpe->bpe_srchArea;
133 Rect *r = &e->e_rect;
134
135 if(r->r_xtop < area->r_xbot) return FALSE;
136 if(r->r_xbot > area->r_xtop) return FALSE;
137 if(r->r_ytop < area->r_ybot) return FALSE;
138 if(r->r_ybot > area->r_ytop) return FALSE;
139
140 return TRUE;
141 }
142
143 /*
144 * ----------------------------------------------------------------------------
145 * bpEnumPushInside --
146 *
147 * called by bpEnumPush when the binarray is entirely inside the search area
148 *
149 * push a bin array onto an enum stack.
150 *
151 * ----------------------------------------------------------------------------
152 */
bpEnumPushInside(BPEnum * bpe,BinArray * ba)153 static __inline__ bool bpEnumPushInside(BPEnum *bpe,
154 BinArray *ba)
155 {
156 BPStack *bps;
157
158 /* push stack */
159 ++bpe->bpe_top;
160 bps = bpe->bpe_top;
161 bps->bps_node = ba;
162 bps->bps_state = BPS_BINS_INSIDE;
163
164 /* set up indices to scan entire bin array */
165 bps->bps_i = -1;
166 bps->bps_max = ba->ba_numBins;
167
168 return TRUE;
169 }
170
171 /*
172 * ----------------------------------------------------------------------------
173 * bpEnumPush --
174 *
175 * push a bin array onto an enum stack.
176 *
177 * normally returns TRUE, returns FALSE on (possible) state change.
178 *
179 * ----------------------------------------------------------------------------
180 */
bpEnumPush(BPEnum * bpe,BinArray * ba,bool inside)181 static __inline__ bool bpEnumPush(BPEnum *bpe,
182 BinArray *ba,
183 bool inside)
184 {
185 Rect area;
186 Rect *bbox;
187 int dx;
188 int dy;
189 BPStack *bps;
190
191 /*
192 fprintf(stderr,"DEBUG bpEnumPush, inside=%d\n", inside);
193 */
194
195 /* special case inside */
196 if(inside) return bpEnumPushInside(bpe,ba);
197
198 bbox = &ba->ba_bbox;
199 if(GEO_SURROUND(&bpe->bpe_srchArea,bbox))
200 {
201 bpEnumPushInside(bpe,ba);
202 return FALSE; /* state change */
203 }
204
205 /* push stack */
206 ++bpe->bpe_top;
207 bps = bpe->bpe_top;
208 bps->bps_node = ba;
209 bps->bps_state = BPS_BINS;
210 bps->bps_subbin = FALSE;
211 bps->bps_rejects = 0;
212
213 /* compute search area for this bin array */
214 dx = ba->ba_dx;
215 dy = ba->ba_dy;
216 area.r_xbot = bpe->bpe_srchArea.r_xbot - dx;
217 area.r_xtop = bpe->bpe_srchArea.r_xtop + 1;
218 area.r_ybot = bpe->bpe_srchArea.r_ybot - dy;
219 area.r_ytop = bpe->bpe_srchArea.r_ytop + 1;
220 GEOCLIP(&area,bbox);
221
222 if(GEO_RECTNULL(&area))
223 {
224 /* only need to check oversized */
225 bps->bps_i = 0;
226 bps->bps_rowMax = 0;
227 bps->bps_max = 0;
228 }
229 else
230 {
231 /* setup indices for this array and search area */
232 int dimX = ba->ba_dimX;
233 int i;
234
235 /* make area relative to bin bbox */
236 area.r_xbot -= bbox->r_xbot;
237 area.r_xtop -= bbox->r_xbot;
238 area.r_ybot -= bbox->r_ybot;
239 area.r_ytop -= bbox->r_ybot;
240
241 /* DumpRect("area relative to bin bbox = ",&area); */
242
243 area.r_xbot /= ba->ba_dx;
244 area.r_xtop /= ba->ba_dx;
245 area.r_ybot /= ba->ba_dy;
246 area.r_ytop /= ba->ba_dy;
247
248 i = area.r_ybot*dimX + area.r_xbot; /* next index */
249 bps->bps_i = i-1;
250 bps->bps_rowMax = i + area.r_xtop - area.r_xbot;
251 bps->bps_max = area.r_ytop*dimX + area.r_xtop;
252 bps->bps_rowDelta = dimX + area.r_xbot - area.r_xtop;
253 bps->bps_dimX = dimX;
254
255 /* consider subbinning? */
256 if(dx >= bpe->bpe_subBinMinX || dy >= bpe->bpe_subBinMinY)
257 {
258 bps->bps_subbin = TRUE;
259 }
260 }
261
262 return TRUE;
263 }
264
265 /*
266 * ----------------------------------------------------------------------------
267 * bpEnumNextBin1 --
268 *
269 * called by bpEnumNextBin() after indexes for new bin are setup
270 *
271 * returns: normally returns TRUE, returns FALSE on state change.
272 *
273 * ----------------------------------------------------------------------------
274 */
275 static __inline__ bool
bpEnumNextBin1(BPEnum * bpe,BPStack * bps,bool inside)276 bpEnumNextBin1(BPEnum *bpe, BPStack *bps, bool inside)
277 {
278 if(bpBinType(bps->bps_node,bps->bps_i) != BT_ARRAY)
279 {
280 bpe->bpe_nextElement = bpBinList(bps->bps_node,bps->bps_i);
281 return TRUE;
282 }
283
284 /* array, push into it */
285 return bpEnumPush(bpe, bpSubArray(bps->bps_node,bps->bps_i), inside);
286 }
287
288 /*
289 * ----------------------------------------------------------------------------
290 * bpEnumNextBin --
291 *
292 * called by bpEnumNextBINS to advance to next bin (bucket).
293 *
294 * cycles through normal bins first, then oversized,
295 * finally, for toplevel, sets INBOX state.
296 *
297 * sets bpe->bpe_nextElement to first element in next bin.
298 *
299 * returns: normally returns TRUE, returns FALSE on state change.
300 *
301 * ----------------------------------------------------------------------------
302 */
303 static __inline__ bool
bpEnumNextBin(BPEnum * bpe,bool inside)304 bpEnumNextBin(BPEnum *bpe, bool inside)
305 {
306 BPStack *bps = bpe->bpe_top;
307
308 #ifdef PARANOID
309 ASSERT(bps,"bpEnumNextBin");
310 ASSERT(!bpe->bpe_nextElement,"bpEnumNextBin");
311 #endif
312
313 /*
314 fprintf(stderr,"DEBUG bpEnumNextBin TOP inside=%d nextElement=%x\n",
315 inside, bpe->bpe_nextElement);
316 */
317
318 /* consider subbining this bin before advancing to next */
319 if(!inside)
320 {
321 if(bps->bps_rejects >= bpMinBAPop
322 && (bps->bps_subbin || bps->bps_i == bps->bps_node->ba_numBins))
323 {
324 int i = bps->bps_i;
325 BinArray *ba = bps->bps_node;
326 BinArray *sub;
327
328 /* fprintf(stderr,"DEBUG, subbining!\n"); */
329 sub = bpBinArrayBuild(bpBinArea(ba,i),
330 bpBinList(ba,i),
331 FALSE); /* don't recursively subbin! */
332
333 if(sub)
334 {
335 ba->ba_bins[i] =
336 (void *) ((pointertype) sub | BT_ARRAY);
337 }
338 }
339 bps->bps_rejects = 0;
340 }
341
342 /* handle inside case first */
343 if(inside)
344 {
345 /* Inside case, cycle through all bins */
346
347 /* next bin */
348 if(bps->bps_i<bps->bps_max)
349 {
350 bps->bps_i += 1;
351 return bpEnumNextBin1(bpe,bps,inside);
352 }
353 }
354 else
355 {
356 /* cycle only through relevant bins */
357
358 /* next in row */
359 if(bps->bps_i<bps->bps_rowMax)
360 {
361 bps->bps_i += 1;
362 goto bin;
363 }
364
365 /* next row */
366 if(bps->bps_i<bps->bps_max)
367 {
368 bps->bps_i += bps->bps_rowDelta;
369 bps->bps_rowMax += bps->bps_dimX;
370 goto bin;
371 }
372
373 /* oversized */
374 if(bps->bps_i == bps->bps_max)
375 {
376 bps->bps_i = bps->bps_node->ba_numBins;
377 goto bin;
378 }
379 }
380
381 /* pop stack */
382 /* fprintf(stderr,"DEBUG BPEnumNextBin Pop.\n"); */
383 bpe->bpe_top--;
384 if(bpe->bpe_top>bpe->bpe_stack) return FALSE; /* state may have changed */
385
386 /* inbox */
387 /* fprintf(stderr,"DEBUG BPEnumNextBin INBOX.\n"); */
388 bpe->bpe_nextElement = bpe->bpe_plane->bp_inBox;
389 bpe->bpe_top->bps_state = BPS_INBOX | inside;
390 return FALSE; /* state change */
391
392 /* dive into indexed bin */
393 bin:
394 return bpEnumNextBin1(bpe,bps,inside);
395 }
396
397 /*
398 * ----------------------------------------------------------------------------
399 * bpEnumNextBINS --
400 *
401 * Handle BINS state for BPEnumNext()
402 *
403 * (bin enumeration.)
404 *
405 * ----------------------------------------------------------------------------
406 */
bpEnumNextBINS(BPEnum * bpe,bool inside)407 static __inline__ Element* bpEnumNextBINS(BPEnum *bpe, bool inside)
408 {
409 /* bin by bin */
410 do
411 {
412 /* search this bin */
413 Element *e = bpe->bpe_nextElement;
414
415 while(e && !inside && !bpEnumMatchQ(bpe,e))
416 {
417 bpe->bpe_top->bps_rejects++;
418 e = e->e_link;
419 }
420
421 if(e)
422 {
423 bpe->bpe_nextElement = e->e_link;
424 /* DumpRect("DEBUG e_rect= ",&e->e_rect); */
425 return e;
426 }
427
428 bpe->bpe_nextElement = NULL;
429 }
430 while(bpEnumNextBin(bpe,inside));
431
432 /* next state */
433 return NULL;
434 }
435
436 /*
437 * ----------------------------------------------------------------------------
438 * bpEnumNextINBOX --
439 *
440 * Handle INBOX states for BPEnumNext()
441 *
442 * unbinned enumeration.
443 *
444 * ----------------------------------------------------------------------------
445 */
bpEnumNextINBOX(BPEnum * bpe,bool inside)446 static __inline__ Element *bpEnumNextINBOX(BPEnum *bpe,
447 bool inside)
448 {
449 Element *e = bpe->bpe_nextElement;
450
451 while(e && !inside && !bpEnumMatchQ(bpe,e)) e = e->e_link;
452 if(e)
453 {
454 bpe->bpe_nextElement = e->e_link;
455 return e;
456 }
457
458 /* done */
459 bpe->bpe_top->bps_state = BPS_DONE;
460 return NULL;
461 }
462
463 /*
464 * ----------------------------------------------------------------------------
465 * bpEnumNextHASH --
466 *
467 * Handle HASH state for BPEnumNext()
468 *
469 * (hash based (EQUALS) enumerations.)
470 *
471 * ----------------------------------------------------------------------------
472 */
bpEnumNextHASH(BPEnum * bpe)473 static __inline__ Element *bpEnumNextHASH(BPEnum *bpe)
474 {
475 Element *e = bpe->bpe_nextElement;
476
477 if(e)
478 {
479 bpe->bpe_nextElement =
480 IHashLookUpNext(bpe->bpe_plane->bp_hashTable, e);
481 }
482 else
483 {
484 bpe->bpe_top->bps_state = BPS_DONE;
485 }
486 return e;
487 }
488
489 /*
490 * ----------------------------------------------------------------------------
491 * BPEnumNext --
492 *
493 * get next element in enumeration.
494 *
495 * ----------------------------------------------------------------------------
496 */
BPEnumNext(BPEnum * bpe)497 static __inline__ void *BPEnumNext(BPEnum *bpe)
498 {
499 Element *e;
500
501 while(TRUE)
502 {
503 /*
504 fprintf(stderr,"DEBUG state=%d\n",bpe->bpe_top->bps_state);
505 */
506 switch (bpe->bpe_top->bps_state)
507 {
508 case BPS_BINS:
509 if(e=bpEnumNextBINS(bpe, 0)) return e;
510 break;
511
512 case BPS_BINS_INSIDE:
513 if(e=bpEnumNextBINS(bpe, 1)) return e;
514 break;
515
516 case BPS_INBOX:
517 if(e=bpEnumNextINBOX(bpe, 0)) return e;
518 break;
519
520 case BPS_INBOX_INSIDE:
521 if(e=bpEnumNextINBOX(bpe, 1)) return e;
522 break;
523
524 case BPS_HASH:
525 if(e=bpEnumNextHASH(bpe)) return e;
526 break;
527
528 case BPS_DONE:
529 return NULL;
530
531 default:
532 ASSERT(FALSE,"BPEnumNext, bad state");
533 }
534 }
535 }
536
537 #endif /* _BPENUM_H */
538