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
31 /* bpEnum.c -
32 *
33 * Search routines for bplanes
34 *
35 */
36
37 #include <stdio.h>
38 #include "utils/utils.h"
39 #include "database/database.h"
40 #include "utils/geometry.h"
41 #include "bplane/bplaneInt.h"
42
43 /*
44 * ----------------------------------------------------------------------------
45 * BPEnumInit --
46 *
47 * set up search.
48 *
49 * ----------------------------------------------------------------------------
50 */
BPEnumInit(BPEnum * bpe,BPlane * bp,Rect * area,int match,char * id)51 void BPEnumInit(BPEnum *bpe, /* enum to initialize */
52 BPlane *bp,
53 Rect *area, /* search area */
54 int match,
55 char *id) /* for debugging */
56 {
57 bool inside = FALSE;
58 bpe->bpe_plane = bp;
59 bpe->bpe_id = id;
60 bpe->bpe_match = match;
61 bpe->bpe_top = bpe->bpe_stack;
62
63 /*
64 fprintf(stderr,"DEBUG bpEnumInit, match=%d id=%s\n",
65 match, id);
66 */
67
68 /* link enum to bplane */
69 bpe->bpe_next = bp->bp_enums;
70 bp->bp_enums = bpe;
71
72 switch (match)
73 {
74
75 case BPE_EQUAL:
76 GeoCanonicalRect(area, &bpe->bpe_srchArea);
77 bpe->bpe_nextElement = IHashLookUp(bp->bp_hashTable, &bpe->bpe_srchArea);
78 bpe->bpe_top->bps_state = BPS_HASH;
79 /* don't need to setup stack, just return */
80 return;
81
82 case BPE_ALL:
83 /* If we start 'INSIDE', no match checks will be done */
84 bpe->bpe_top->bps_state = BPS_BINS_INSIDE;
85 inside = TRUE;
86 break;
87
88 case BPE_TOUCH:
89 GeoCanonicalRect(area, &bpe->bpe_srchArea);
90 inside = GEO_SURROUND(&bpe->bpe_srchArea, &bp->bp_bbox);
91 if(inside)
92 {
93 bpe->bpe_top->bps_state = BPS_BINS_INSIDE;
94 }
95 else
96 {
97 bpe->bpe_top->bps_state = BPS_BINS;
98 bpe->bpe_subBinMinX = GEO_WIDTH(&bpe->bpe_srchArea)/2;
99 bpe->bpe_subBinMinY = GEO_HEIGHT(&bpe->bpe_srchArea)/2;
100 bpBinsUpdate(bp);
101 }
102 break;
103
104 case BPE_OVERLAP:
105 GeoCanonicalRect(area, &bpe->bpe_srchArea);
106 GEO_EXPAND(&bpe->bpe_srchArea, -1, &bpe->bpe_srchArea);
107 inside = GEO_SURROUND(&bpe->bpe_srchArea, &bp->bp_bbox);
108 if(inside)
109 {
110 bpe->bpe_top->bps_state = BPS_BINS_INSIDE;
111 }
112 else
113 {
114 bpe->bpe_top->bps_state = BPS_BINS;
115 bpe->bpe_subBinMinX = GEO_WIDTH(&bpe->bpe_srchArea)/2;
116 bpe->bpe_subBinMinY = GEO_HEIGHT(&bpe->bpe_srchArea)/2;
117 bpBinsUpdate(bp);
118 }
119 break;
120
121 default:
122 ASSERT(FALSE,"BPEnumInit, bad match value");
123 }
124
125 /* push rootnode */
126 if(bp->bp_rootNode)
127 {
128 bpEnumPush(bpe, bp->bp_rootNode, inside);
129 bpe->bpe_nextElement = NULL;
130 }
131 else
132 {
133 /* no bins, go straight to inbox */
134 bpe->bpe_top->bps_state = BPS_INBOX | inside;
135 bpe->bpe_nextElement = bp->bp_inBox;
136 }
137 }
138
139 /*
140 * ----------------------------------------------------------------------------
141 * BPEnumTerm --
142 *
143 * terminate enumeration
144 *
145 * ----------------------------------------------------------------------------
146 */
BPEnumTerm(BPEnum * bpe)147 void BPEnumTerm(BPEnum *bpe)
148 {
149 BPEnum **linkp;
150
151 /*
152 fprintf(stderr,"DEBUG bpEnumTerm, id=%s\n",
153 bpe->bpe_id);
154 */
155
156 /* unlink */
157
158 linkp = &bpe->bpe_plane->bp_enums;
159 while(*linkp && *linkp != bpe) linkp = &(*linkp)->bpe_next;
160 ASSERT(*linkp==bpe,"BPEnumTerm");
161 *linkp = bpe->bpe_next;
162 }
163
164
165
166
167