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 #ifndef _BPOPAQUE_H
31 #define _BPOPAQUE_H
32
33 #ifndef _IHASH_H
34 #include "utils/ihash.h"
35 #endif /* _IHASH_H */
36
37 /*
38 * bpOpaque.h --
39 *
40 * This file contains strucs directly or indirectly referenced by
41 * clients of bplane module, whose internals should be treated
42 * as opaque by clients.
43 *
44 * It is included by bplane.h
45 *
46 */
47
48 /* data element, stored in BPlane
49 *
50 * Storage managed by caller.
51 * Inital part must correspond to below.
52 */
53 typedef struct element
54 {
55 struct element *e_hashLink;
56 struct element *e_link;
57 struct element **e_linkp; /* back pointer for quick deletes */
58 Rect e_rect;
59 /* client data goes here */
60 } Element;
61
62 /* number of link fields in element
63 *
64 * user code should not depend on more than 1 link.
65 * (and should only use/ref that link when element is not in a bplane)
66 */
67 #define BP_NUM_LINKS 3
68
69 /* bin array */
70 typedef struct binarray
71 {
72 Rect ba_bbox; /* area covered by array */
73 int ba_dx; /* dimensions of a single bin */
74 int ba_dy;
75 int ba_dimX; /* number of bins in a row */
76 int ba_numBins; /* number of regular bins (size of array - 1) */
77
78 void *ba_bins[1]; /* low order bit(s) used to encode type info.
79 * DON'T ACCESS DIRECTLY, USE MACROS BELOW
80 *
81 * (last bin is for oversized)
82 */
83 } BinArray;
84
85 /* bin types
86 *
87 * NOTE: its important that simple lists have type 0, i.e. are
88 * just standard pointers. This is so that the list head
89 * 'link' can be treated just as any other link, during
90 * deletion etc.
91 */
92
93 #define BT_TYPE_MASK 1
94 #define BT_LIST 0
95 #define BT_ARRAY 1
96
bpBinEmpty(BinArray * ba,int i)97 static __inline__ bool bpBinEmpty(BinArray *ba, int i)
98 {
99 return ba->ba_bins[i] == NULL;
100 }
101
bpBinType(BinArray * ba,int i)102 static __inline__ bool bpBinType(BinArray *ba, int i)
103 {
104 return (bool) (((pointertype) ba->ba_bins[i]) & BT_TYPE_MASK);
105 }
106
bpBinList(BinArray * ba,int i)107 static __inline__ Element *bpBinList(BinArray *ba, int i)
108 {
109 #ifdef PARANOID
110 ASSERT(bpBinType(ba,i)==BT_LIST,"bpBinList");
111 #endif
112 return (Element *) ba->ba_bins[i];
113 }
114
bpBinListHead(BinArray * ba,int i)115 static __inline__ Element **bpBinListHead(BinArray *ba, int i)
116 {
117 #ifdef PARANOID
118 ASSERT(bpBinType(ba,i)==BT_LIST,"bpBinList");
119 #endif
120 return (Element **) &ba->ba_bins[i];
121 }
122
bpSubArray(BinArray * ba,int i)123 static __inline__ BinArray *bpSubArray(BinArray *ba, int i)
124 {
125 #ifdef PARANOID
126 ASSERT(bpBinType(ba,i)==BT_ARRAY,"bpSubArray");
127 #endif
128 return (BinArray *) ((pointertype) ba->ba_bins[i] & ~BT_TYPE_MASK);
129 }
130
131 /* BPlane - toplevel struc */
132 typedef struct bplane
133 {
134 Rect bp_bbox; /* bbox (bin + in) */
135 bool bp_bbox_exact; /* if set bp_bbox, is exact,
136 * if reset bp_bbox may be over-sized.
137 */
138 int bp_count; /* total number of elements in bplane */
139 struct bpenum *bp_enums; /* list of active enums */
140
141 /* HASH TABLE */
142 IHashTable *bp_hashTable; /* hash table
143 * (for expediting BP_EQUAL searches) */
144 /* IN BOX */
145 Element *bp_inBox; /* elements not yet added to bin system */
146
147 /* BINS */
148 int bp_binLife; /* set to binCount when bin system
149 * built, decremented on add/delete ops.
150 * bin system rebuilt when zero reached.
151 */
152 int bp_inAdds; /* additions to inBox since last rebuild */
153
154 Rect bp_binArea; /* area covered by bin arrays */
155 BinArray *bp_rootNode; /* top bin node */
156 } BPlane;
157
158 /* context for BPlane enumeration */
159 typedef struct bpStack
160 {
161 int bps_state; /* where we are at rolled in one convenient
162 * number (see BPS_* defs in bpEnum.h)
163 */
164 BinArray *bps_node; /* current bin array */
165 int bps_i; /* current index */
166 int bps_rowMax; /* max index for this row */
167 int bps_rowDelta; /* increment from end of one row to beginning
168 * of next.
169 */
170 int bps_max; /* max index */
171 int bps_dimX; /* row length */
172 bool bps_subbin; /* if set consider subbinning */
173 int bps_rejects; /* number of unmatching elements in current
174 * bin, used to decide when to subbin.
175 */
176 } BPStack;
177
178 /* enumeration 'handle' */
179 typedef struct bpenum
180 {
181 struct bpenum *bpe_next; /* all enums for bplane linked together */
182 BPlane *bpe_plane; /* plane being searched */
183 Rect bpe_srchArea; /* area being searched */
184 int bpe_match; /* match criteria */
185 char *bpe_id; /* for debug */
186 int bpe_subBinMinX;
187 int bpe_subBinMinY; /* consider subbinning
188 * for bins bigger than this.
189 */
190 Element *bpe_nextElement; /* next element in current list */
191 BPStack *bpe_top; /* top of stack */
192 BPStack bpe_stack[10000]; /* stack for tree traversal during enum */
193 } BPEnum;
194
195 #endif /* _BPOPAQUE_H */
196