Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * network_spgist.c
4 : : * SP-GiST support for network types.
5 : : *
6 : : * We split inet index entries first by address family (IPv4 or IPv6).
7 : : * If the entries below a given inner tuple are all of the same family,
8 : : * we identify their common prefix and split by the next bit of the address,
9 : : * and by whether their masklens exceed the length of the common prefix.
10 : : *
11 : : * An inner tuple that has both IPv4 and IPv6 children has a null prefix
12 : : * and exactly two nodes, the first being for IPv4 and the second for IPv6.
13 : : *
14 : : * Otherwise, the prefix is a CIDR value representing the common prefix,
15 : : * and there are exactly four nodes. Node numbers 0 and 1 are for addresses
16 : : * with the same masklen as the prefix, while node numbers 2 and 3 are for
17 : : * addresses with larger masklen. (We do not allow a tuple to contain
18 : : * entries with masklen smaller than its prefix's.) Node numbers 0 and 1
19 : : * are distinguished by the next bit of the address after the common prefix,
20 : : * and likewise for node numbers 2 and 3. If there are no more bits in
21 : : * the address family, everything goes into node 0 (which will probably
22 : : * lead to creating an allTheSame tuple).
23 : : *
24 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
25 : : * Portions Copyright (c) 1994, Regents of the University of California
26 : : *
27 : : * IDENTIFICATION
28 : : * src/backend/utils/adt/network_spgist.c
29 : : *
30 : : *-------------------------------------------------------------------------
31 : : */
32 : : #include "postgres.h"
33 : :
34 : : #include <sys/socket.h>
35 : :
36 : : #include "access/spgist.h"
37 : : #include "catalog/pg_type.h"
38 : : #include "utils/fmgrprotos.h"
39 : : #include "utils/inet.h"
40 : : #include "varatt.h"
41 : :
42 : :
43 : : static int inet_spg_node_number(const inet *val, int commonbits);
44 : : static int inet_spg_consistent_bitmap(const inet *prefix, int nkeys,
45 : : ScanKey scankeys, bool leaf);
46 : :
47 : : /*
48 : : * The SP-GiST configuration function
49 : : */
50 : : Datum
2791 tgl@sss.pgh.pa.us 51 :CBC 9 : inet_spg_config(PG_FUNCTION_ARGS)
52 : : {
53 : : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
54 : 9 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
55 : :
56 : 9 : cfg->prefixType = CIDROID;
57 : 9 : cfg->labelType = VOIDOID;
58 : 9 : cfg->canReturnData = true;
59 : 9 : cfg->longValuesOK = false;
60 : :
61 : 9 : PG_RETURN_VOID();
62 : : }
63 : :
64 : : /*
65 : : * The SP-GiST choose function
66 : : */
67 : : Datum
2791 tgl@sss.pgh.pa.us 68 :UBC 0 : inet_spg_choose(PG_FUNCTION_ARGS)
69 : : {
70 : 0 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
71 : 0 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
72 : 0 : inet *val = DatumGetInetPP(in->datum),
73 : : *prefix;
74 : : int commonbits;
75 : :
76 : : /*
77 : : * If we're looking at a tuple that splits by address family, choose the
78 : : * appropriate subnode.
79 : : */
80 [ # # ]: 0 : if (!in->hasPrefix)
81 : : {
82 : : /* allTheSame isn't possible for such a tuple */
83 [ # # ]: 0 : Assert(!in->allTheSame);
84 [ # # ]: 0 : Assert(in->nNodes == 2);
85 : :
86 : 0 : out->resultType = spgMatchNode;
87 [ # # ]: 0 : out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1;
88 : 0 : out->result.matchNode.restDatum = InetPGetDatum(val);
89 : :
90 : 0 : PG_RETURN_VOID();
91 : : }
92 : :
93 : : /* Else it must split by prefix */
94 [ # # # # ]: 0 : Assert(in->nNodes == 4 || in->allTheSame);
95 : :
96 : 0 : prefix = DatumGetInetPP(in->prefixDatum);
97 [ # # ]: 0 : commonbits = ip_bits(prefix);
98 : :
99 : : /*
100 : : * We cannot put addresses from different families under the same inner
101 : : * node, so we have to split if the new value's family is different.
102 : : */
103 [ # # # # : 0 : if (ip_family(val) != ip_family(prefix))
# # ]
104 : : {
105 : : /* Set up 2-node tuple */
106 : 0 : out->resultType = spgSplitTuple;
107 : 0 : out->result.splitTuple.prefixHasPrefix = false;
108 : 0 : out->result.splitTuple.prefixNNodes = 2;
109 : 0 : out->result.splitTuple.prefixNodeLabels = NULL;
110 : :
111 : : /* Identify which node the existing data goes into */
112 : 0 : out->result.splitTuple.childNodeN =
113 [ # # ]: 0 : (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1;
114 : :
115 : 0 : out->result.splitTuple.postfixHasPrefix = true;
116 : 0 : out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
117 : :
118 : 0 : PG_RETURN_VOID();
119 : : }
120 : :
121 : : /*
122 : : * If the new value does not match the existing prefix, we have to split.
123 : : */
124 [ # # # # : 0 : if (ip_bits(val) < commonbits ||
# # ]
125 [ # # # # ]: 0 : bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0)
126 : : {
127 : : /* Determine new prefix length for the split tuple */
128 [ # # ]: 0 : commonbits = bitncommon(ip_addr(prefix), ip_addr(val),
129 [ # # # # ]: 0 : Min(ip_bits(val), commonbits));
130 : :
131 : : /* Set up 4-node tuple */
132 : 0 : out->resultType = spgSplitTuple;
133 : 0 : out->result.splitTuple.prefixHasPrefix = true;
134 : 0 : out->result.splitTuple.prefixPrefixDatum =
135 : 0 : InetPGetDatum(cidr_set_masklen_internal(val, commonbits));
136 : 0 : out->result.splitTuple.prefixNNodes = 4;
137 : 0 : out->result.splitTuple.prefixNodeLabels = NULL;
138 : :
139 : : /* Identify which node the existing data goes into */
140 : 0 : out->result.splitTuple.childNodeN =
141 : 0 : inet_spg_node_number(prefix, commonbits);
142 : :
143 : 0 : out->result.splitTuple.postfixHasPrefix = true;
144 : 0 : out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
145 : :
146 : 0 : PG_RETURN_VOID();
147 : : }
148 : :
149 : : /*
150 : : * All OK, choose the node to descend into. (If this tuple is marked
151 : : * allTheSame, the core code will ignore our choice of nodeN; but we need
152 : : * not account for that case explicitly here.)
153 : : */
154 : 0 : out->resultType = spgMatchNode;
155 : 0 : out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits);
156 : 0 : out->result.matchNode.restDatum = InetPGetDatum(val);
157 : :
158 : 0 : PG_RETURN_VOID();
159 : : }
160 : :
161 : : /*
162 : : * The GiST PickSplit method
163 : : */
164 : : Datum
165 : 0 : inet_spg_picksplit(PG_FUNCTION_ARGS)
166 : : {
167 : 0 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
168 : 0 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
169 : : inet *prefix,
170 : : *tmp;
171 : : int i,
172 : : commonbits;
173 : 0 : bool differentFamilies = false;
174 : :
175 : : /* Initialize the prefix with the first item */
176 : 0 : prefix = DatumGetInetPP(in->datums[0]);
177 [ # # ]: 0 : commonbits = ip_bits(prefix);
178 : :
179 : : /* Examine remaining items to discover minimum common prefix length */
180 [ # # ]: 0 : for (i = 1; i < in->nTuples; i++)
181 : : {
182 : 0 : tmp = DatumGetInetPP(in->datums[i]);
183 : :
184 [ # # # # : 0 : if (ip_family(tmp) != ip_family(prefix))
# # ]
185 : : {
186 : 0 : differentFamilies = true;
187 : 0 : break;
188 : : }
189 : :
190 [ # # # # ]: 0 : if (ip_bits(tmp) < commonbits)
191 [ # # ]: 0 : commonbits = ip_bits(tmp);
192 [ # # # # ]: 0 : commonbits = bitncommon(ip_addr(prefix), ip_addr(tmp), commonbits);
193 [ # # ]: 0 : if (commonbits == 0)
194 : 0 : break;
195 : : }
196 : :
197 : : /* Don't need labels; allocate output arrays */
198 : 0 : out->nodeLabels = NULL;
199 : 0 : out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
200 : 0 : out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
201 : :
202 [ # # ]: 0 : if (differentFamilies)
203 : : {
204 : : /* Set up 2-node tuple */
205 : 0 : out->hasPrefix = false;
206 : 0 : out->nNodes = 2;
207 : :
208 [ # # ]: 0 : for (i = 0; i < in->nTuples; i++)
209 : : {
210 : 0 : tmp = DatumGetInetPP(in->datums[i]);
211 : 0 : out->mapTuplesToNodes[i] =
212 [ # # ]: 0 : (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1;
213 : 0 : out->leafTupleDatums[i] = InetPGetDatum(tmp);
214 : : }
215 : : }
216 : : else
217 : : {
218 : : /* Set up 4-node tuple */
219 : 0 : out->hasPrefix = true;
220 : 0 : out->prefixDatum =
221 : 0 : InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits));
222 : 0 : out->nNodes = 4;
223 : :
224 [ # # ]: 0 : for (i = 0; i < in->nTuples; i++)
225 : : {
226 : 0 : tmp = DatumGetInetPP(in->datums[i]);
227 : 0 : out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits);
228 : 0 : out->leafTupleDatums[i] = InetPGetDatum(tmp);
229 : : }
230 : : }
231 : :
232 : 0 : PG_RETURN_VOID();
233 : : }
234 : :
235 : : /*
236 : : * The SP-GiST query consistency check for inner tuples
237 : : */
238 : : Datum
239 : 0 : inet_spg_inner_consistent(PG_FUNCTION_ARGS)
240 : : {
241 : 0 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
242 : 0 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
243 : : int i;
244 : : int which;
245 : :
246 [ # # ]: 0 : if (!in->hasPrefix)
247 : : {
248 [ # # ]: 0 : Assert(!in->allTheSame);
249 [ # # ]: 0 : Assert(in->nNodes == 2);
250 : :
251 : : /* Identify which child nodes need to be visited */
252 : 0 : which = 1 | (1 << 1);
253 : :
254 [ # # ]: 0 : for (i = 0; i < in->nkeys; i++)
255 : : {
256 : 0 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
257 : 0 : inet *argument = DatumGetInetPP(in->scankeys[i].sk_argument);
258 : :
259 [ # # # # ]: 0 : switch (strategy)
260 : : {
261 : 0 : case RTLessStrategyNumber:
262 : : case RTLessEqualStrategyNumber:
263 [ # # # # ]: 0 : if (ip_family(argument) == PGSQL_AF_INET)
264 : 0 : which &= 1;
265 : 0 : break;
266 : :
267 : 0 : case RTGreaterEqualStrategyNumber:
268 : : case RTGreaterStrategyNumber:
269 [ # # # # ]: 0 : if (ip_family(argument) == PGSQL_AF_INET6)
270 : 0 : which &= (1 << 1);
271 : 0 : break;
272 : :
273 : 0 : case RTNotEqualStrategyNumber:
274 : 0 : break;
275 : :
276 : 0 : default:
277 : : /* all other ops can only match addrs of same family */
278 [ # # # # ]: 0 : if (ip_family(argument) == PGSQL_AF_INET)
279 : 0 : which &= 1;
280 : : else
281 : 0 : which &= (1 << 1);
282 : 0 : break;
283 : : }
284 : : }
285 : : }
286 [ # # ]: 0 : else if (!in->allTheSame)
287 : : {
288 [ # # ]: 0 : Assert(in->nNodes == 4);
289 : :
290 : : /* Identify which child nodes need to be visited */
291 : 0 : which = inet_spg_consistent_bitmap(DatumGetInetPP(in->prefixDatum),
292 : : in->nkeys, in->scankeys, false);
293 : : }
294 : : else
295 : : {
296 : : /* Must visit all nodes; we assume there are less than 32 of 'em */
297 : 0 : which = ~0;
298 : : }
299 : :
300 : 0 : out->nNodes = 0;
301 : :
302 [ # # ]: 0 : if (which)
303 : : {
304 : 0 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
305 : :
306 [ # # ]: 0 : for (i = 0; i < in->nNodes; i++)
307 : : {
308 [ # # ]: 0 : if (which & (1 << i))
309 : : {
310 : 0 : out->nodeNumbers[out->nNodes] = i;
311 : 0 : out->nNodes++;
312 : : }
313 : : }
314 : : }
315 : :
316 : 0 : PG_RETURN_VOID();
317 : : }
318 : :
319 : : /*
320 : : * The SP-GiST query consistency check for leaf tuples
321 : : */
322 : : Datum
2791 tgl@sss.pgh.pa.us 323 :CBC 612 : inet_spg_leaf_consistent(PG_FUNCTION_ARGS)
324 : : {
325 : 612 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
326 : 612 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
327 : 612 : inet *leaf = DatumGetInetPP(in->leafDatum);
328 : :
329 : : /* All tests are exact. */
330 : 612 : out->recheck = false;
331 : :
332 : : /* Leaf is what it is... */
333 : 612 : out->leafValue = InetPGetDatum(leaf);
334 : :
335 : : /* Use common code to apply the tests. */
336 : 612 : PG_RETURN_BOOL(inet_spg_consistent_bitmap(leaf, in->nkeys, in->scankeys,
337 : : true));
338 : : }
339 : :
340 : : /*
341 : : * Calculate node number (within a 4-node, single-family inner index tuple)
342 : : *
343 : : * The value must have the same family as the node's prefix, and
344 : : * commonbits is the mask length of the prefix. We use even or odd
345 : : * nodes according to the next address bit after the commonbits,
346 : : * and low or high nodes according to whether the value's mask length
347 : : * is larger than commonbits.
348 : : */
349 : : static int
2791 tgl@sss.pgh.pa.us 350 :UBC 0 : inet_spg_node_number(const inet *val, int commonbits)
351 : : {
352 : 0 : int nodeN = 0;
353 : :
354 [ # # # # : 0 : if (commonbits < ip_maxbits(val) &&
# # ]
355 [ # # # # ]: 0 : ip_addr(val)[commonbits / 8] & (1 << (7 - commonbits % 8)))
356 : 0 : nodeN |= 1;
357 [ # # # # ]: 0 : if (commonbits < ip_bits(val))
358 : 0 : nodeN |= 2;
359 : :
360 : 0 : return nodeN;
361 : : }
362 : :
363 : : /*
364 : : * Calculate bitmap of node numbers that are consistent with the query
365 : : *
366 : : * This can be used either at a 4-way inner tuple, or at a leaf tuple.
367 : : * In the latter case, we should return a boolean result (0 or 1)
368 : : * not a bitmap.
369 : : *
370 : : * This definition is pretty odd, but the inner and leaf consistency checks
371 : : * are mostly common and it seems best to keep them in one function.
372 : : */
373 : : static int
2791 tgl@sss.pgh.pa.us 374 :CBC 612 : inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys,
375 : : bool leaf)
376 : : {
377 : : int bitmap;
378 : : int commonbits,
379 : : i;
380 : :
381 : : /* Initialize result to allow visiting all children */
382 [ + - ]: 612 : if (leaf)
383 : 612 : bitmap = 1;
384 : : else
2791 tgl@sss.pgh.pa.us 385 :UBC 0 : bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);
386 : :
2791 tgl@sss.pgh.pa.us 387 [ + - ]:CBC 612 : commonbits = ip_bits(prefix);
388 : :
389 [ + + ]: 828 : for (i = 0; i < nkeys; i++)
390 : : {
391 : 612 : inet *argument = DatumGetInetPP(scankeys[i].sk_argument);
392 : 612 : StrategyNumber strategy = scankeys[i].sk_strategy;
393 : : int order;
394 : :
395 : : /*
396 : : * Check 0: different families
397 : : *
398 : : * Matching families do not help any of the strategies.
399 : : */
400 [ - + + - : 612 : if (ip_family(argument) != ip_family(prefix))
+ + ]
401 : : {
402 [ + + + + ]: 108 : switch (strategy)
403 : : {
404 : 18 : case RTLessStrategyNumber:
405 : : case RTLessEqualStrategyNumber:
406 [ - + + - : 18 : if (ip_family(argument) < ip_family(prefix))
+ - ]
407 : 18 : bitmap = 0;
408 : 18 : break;
409 : :
410 : 18 : case RTGreaterEqualStrategyNumber:
411 : : case RTGreaterStrategyNumber:
412 [ - + + - : 18 : if (ip_family(argument) > ip_family(prefix))
- + ]
2791 tgl@sss.pgh.pa.us 413 :UBC 0 : bitmap = 0;
2791 tgl@sss.pgh.pa.us 414 :CBC 18 : break;
415 : :
416 : 9 : case RTNotEqualStrategyNumber:
417 : 9 : break;
418 : :
419 : 63 : default:
420 : : /* For all other cases, we can be sure there is no match */
421 : 63 : bitmap = 0;
422 : 63 : break;
423 : : }
424 : :
425 [ + + ]: 108 : if (!bitmap)
426 : 81 : break;
427 : :
428 : : /* Other checks make no sense with different families. */
429 : 27 : continue;
430 : : }
431 : :
432 : : /*
433 : : * Check 1: network bit count
434 : : *
435 : : * Network bit count (ip_bits) helps to check leaves for sub network
436 : : * and sup network operators. At non-leaf nodes, we know every child
437 : : * value has greater ip_bits, so we can avoid descending in some cases
438 : : * too.
439 : : *
440 : : * This check is less expensive than checking the address bits, so we
441 : : * are doing this before, but it has to be done after for the basic
442 : : * comparison strategies, because ip_bits only affect their results
443 : : * when the common network bits are the same.
444 : : */
445 [ + + + + : 504 : switch (strategy)
+ + ]
446 : : {
447 : 84 : case RTSubStrategyNumber:
448 [ - + + + ]: 84 : if (commonbits <= ip_bits(argument))
449 : 60 : bitmap &= (1 << 2) | (1 << 3);
450 : 84 : break;
451 : :
452 : 42 : case RTSubEqualStrategyNumber:
453 [ - + + + ]: 42 : if (commonbits < ip_bits(argument))
454 : 18 : bitmap &= (1 << 2) | (1 << 3);
455 : 42 : break;
456 : :
457 : 42 : case RTSuperStrategyNumber:
458 [ - + - + ]: 42 : if (commonbits == ip_bits(argument) - 1)
2791 tgl@sss.pgh.pa.us 459 :UBC 0 : bitmap &= 1 | (1 << 1);
2791 tgl@sss.pgh.pa.us 460 [ - + + + ]:CBC 42 : else if (commonbits >= ip_bits(argument))
461 : 24 : bitmap = 0;
462 : 42 : break;
463 : :
464 : 42 : case RTSuperEqualStrategyNumber:
465 [ - + + + ]: 42 : if (commonbits == ip_bits(argument))
466 : 12 : bitmap &= 1 | (1 << 1);
467 [ - + + + ]: 30 : else if (commonbits > ip_bits(argument))
468 : 12 : bitmap = 0;
469 : 42 : break;
470 : :
471 : 42 : case RTEqualStrategyNumber:
472 [ - + + + ]: 42 : if (commonbits < ip_bits(argument))
473 : 18 : bitmap &= (1 << 2) | (1 << 3);
474 [ - + + + ]: 24 : else if (commonbits == ip_bits(argument))
475 : 12 : bitmap &= 1 | (1 << 1);
476 : : else
477 : 12 : bitmap = 0;
478 : 42 : break;
479 : : }
480 : :
481 [ + + ]: 504 : if (!bitmap)
482 : 144 : break;
483 : :
484 : : /*
485 : : * Check 2: common network bits
486 : : *
487 : : * Compare available common prefix bits to the query, but not beyond
488 : : * either the query's netmask or the minimum netmask among the
489 : : * represented values. If these bits don't match the query, we can
490 : : * eliminate some cases.
491 : : */
492 [ + - ]: 360 : order = bitncmp(ip_addr(prefix), ip_addr(argument),
493 [ - + - + ]: 360 : Min(commonbits, ip_bits(argument)));
494 : :
495 [ + + ]: 360 : if (order != 0)
496 : : {
497 [ + + + + ]: 198 : switch (strategy)
498 : : {
499 : 48 : case RTLessStrategyNumber:
500 : : case RTLessEqualStrategyNumber:
501 [ - + ]: 48 : if (order > 0)
2791 tgl@sss.pgh.pa.us 502 :UBC 0 : bitmap = 0;
2791 tgl@sss.pgh.pa.us 503 :CBC 48 : break;
504 : :
505 : 48 : case RTGreaterEqualStrategyNumber:
506 : : case RTGreaterStrategyNumber:
507 [ + - ]: 48 : if (order < 0)
508 : 48 : bitmap = 0;
509 : 48 : break;
510 : :
511 : 24 : case RTNotEqualStrategyNumber:
512 : 24 : break;
513 : :
514 : 78 : default:
515 : : /* For all other cases, we can be sure there is no match */
516 : 78 : bitmap = 0;
517 : 78 : break;
518 : : }
519 : :
520 [ + + ]: 198 : if (!bitmap)
521 : 126 : break;
522 : :
523 : : /*
524 : : * Remaining checks make no sense when common bits don't match.
525 : : */
526 : 72 : continue;
527 : : }
528 : :
529 : : /*
530 : : * Check 3: next network bit
531 : : *
532 : : * We can filter out branch 2 or 3 using the next network bit of the
533 : : * argument, if it is available.
534 : : *
535 : : * This check matters for the performance of the search. The results
536 : : * would be correct without it.
537 : : */
538 [ - + ]: 162 : if (bitmap & ((1 << 2) | (1 << 3)) &&
2791 tgl@sss.pgh.pa.us 539 [ # # # # ]:UBC 0 : commonbits < ip_bits(argument))
540 : : {
541 : : int nextbit;
542 : :
543 [ # # ]: 0 : nextbit = ip_addr(argument)[commonbits / 8] &
544 : 0 : (1 << (7 - commonbits % 8));
545 : :
546 [ # # # # ]: 0 : switch (strategy)
547 : : {
548 : 0 : case RTLessStrategyNumber:
549 : : case RTLessEqualStrategyNumber:
550 [ # # ]: 0 : if (!nextbit)
551 : 0 : bitmap &= 1 | (1 << 1) | (1 << 2);
552 : 0 : break;
553 : :
554 : 0 : case RTGreaterEqualStrategyNumber:
555 : : case RTGreaterStrategyNumber:
556 [ # # ]: 0 : if (nextbit)
557 : 0 : bitmap &= 1 | (1 << 1) | (1 << 3);
558 : 0 : break;
559 : :
560 : 0 : case RTNotEqualStrategyNumber:
561 : 0 : break;
562 : :
563 : 0 : default:
564 [ # # ]: 0 : if (!nextbit)
565 : 0 : bitmap &= 1 | (1 << 1) | (1 << 2);
566 : : else
567 : 0 : bitmap &= 1 | (1 << 1) | (1 << 3);
568 : 0 : break;
569 : : }
570 : :
571 [ # # ]: 0 : if (!bitmap)
572 : 0 : break;
573 : : }
574 : :
575 : : /*
576 : : * Remaining checks are only for the basic comparison strategies. This
577 : : * test relies on the strategy number ordering defined in stratnum.h.
578 : : */
2791 tgl@sss.pgh.pa.us 579 [ + + + + ]:CBC 162 : if (strategy < RTEqualStrategyNumber ||
580 : : strategy > RTGreaterEqualStrategyNumber)
581 : 63 : continue;
582 : :
583 : : /*
584 : : * Check 4: network bit count
585 : : *
586 : : * At this point, we know that the common network bits of the prefix
587 : : * and the argument are the same, so we can go forward and check the
588 : : * ip_bits.
589 : : */
590 [ + + + ]: 99 : switch (strategy)
591 : : {
592 : 36 : case RTLessStrategyNumber:
593 : : case RTLessEqualStrategyNumber:
594 [ - + + + ]: 36 : if (commonbits == ip_bits(argument))
595 : 18 : bitmap &= 1 | (1 << 1);
596 [ - + + - ]: 18 : else if (commonbits > ip_bits(argument))
597 : 18 : bitmap = 0;
598 : 36 : break;
599 : :
600 : 36 : case RTGreaterEqualStrategyNumber:
601 : : case RTGreaterStrategyNumber:
602 [ - + - + ]: 36 : if (commonbits < ip_bits(argument))
2791 tgl@sss.pgh.pa.us 603 :UBC 0 : bitmap &= (1 << 2) | (1 << 3);
2791 tgl@sss.pgh.pa.us 604 :CBC 36 : break;
605 : : }
606 : :
607 [ + + ]: 99 : if (!bitmap)
608 : 18 : break;
609 : :
610 : : /* Remaining checks don't make sense with different ip_bits. */
611 [ - + + + ]: 81 : if (commonbits != ip_bits(argument))
612 : 27 : continue;
613 : :
614 : : /*
615 : : * Check 5: next host bit
616 : : *
617 : : * We can filter out branch 0 or 1 using the next host bit of the
618 : : * argument, if it is available.
619 : : *
620 : : * This check matters for the performance of the search. The results
621 : : * would be correct without it. There is no point in running it for
622 : : * leafs as we have to check the whole address on the next step.
623 : : */
624 [ - + - - : 54 : if (!leaf && bitmap & (1 | (1 << 1)) &&
- - ]
2791 tgl@sss.pgh.pa.us 625 [ # # # # ]:UBC 0 : commonbits < ip_maxbits(argument))
626 : : {
627 : : int nextbit;
628 : :
629 [ # # ]: 0 : nextbit = ip_addr(argument)[commonbits / 8] &
630 : 0 : (1 << (7 - commonbits % 8));
631 : :
632 [ # # # # ]: 0 : switch (strategy)
633 : : {
634 : 0 : case RTLessStrategyNumber:
635 : : case RTLessEqualStrategyNumber:
636 [ # # ]: 0 : if (!nextbit)
637 : 0 : bitmap &= 1 | (1 << 2) | (1 << 3);
638 : 0 : break;
639 : :
640 : 0 : case RTGreaterEqualStrategyNumber:
641 : : case RTGreaterStrategyNumber:
642 [ # # ]: 0 : if (nextbit)
643 : 0 : bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
644 : 0 : break;
645 : :
646 : 0 : case RTNotEqualStrategyNumber:
647 : 0 : break;
648 : :
649 : 0 : default:
650 [ # # ]: 0 : if (!nextbit)
651 : 0 : bitmap &= 1 | (1 << 2) | (1 << 3);
652 : : else
653 : 0 : bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
654 : 0 : break;
655 : : }
656 : :
657 [ # # ]: 0 : if (!bitmap)
658 : 0 : break;
659 : : }
660 : :
661 : : /*
662 : : * Check 6: whole address
663 : : *
664 : : * This is the last check for correctness of the basic comparison
665 : : * strategies. It's only appropriate at leaf entries.
666 : : */
2791 tgl@sss.pgh.pa.us 667 [ + - ]:CBC 54 : if (leaf)
668 : : {
669 : : /* Redo ordering comparison using all address bits */
670 [ - + + - ]: 54 : order = bitncmp(ip_addr(prefix), ip_addr(argument),
671 [ + - + - ]: 54 : ip_maxbits(prefix));
672 : :
673 [ + + + + : 54 : switch (strategy)
+ + - ]
674 : : {
675 : 9 : case RTLessStrategyNumber:
676 [ + - ]: 9 : if (order >= 0)
677 : 9 : bitmap = 0;
678 : 9 : break;
679 : :
680 : 9 : case RTLessEqualStrategyNumber:
681 [ + + ]: 9 : if (order > 0)
682 : 6 : bitmap = 0;
683 : 9 : break;
684 : :
685 : 9 : case RTEqualStrategyNumber:
686 [ + + ]: 9 : if (order != 0)
687 : 6 : bitmap = 0;
688 : 9 : break;
689 : :
690 : 9 : case RTGreaterEqualStrategyNumber:
691 [ - + ]: 9 : if (order < 0)
2791 tgl@sss.pgh.pa.us 692 :UBC 0 : bitmap = 0;
2791 tgl@sss.pgh.pa.us 693 :CBC 9 : break;
694 : :
695 : 9 : case RTGreaterStrategyNumber:
696 [ + + ]: 9 : if (order <= 0)
697 : 3 : bitmap = 0;
698 : 9 : break;
699 : :
700 : 9 : case RTNotEqualStrategyNumber:
701 [ + + ]: 9 : if (order == 0)
702 : 3 : bitmap = 0;
703 : 9 : break;
704 : : }
705 : :
706 [ + + ]: 54 : if (!bitmap)
707 : 27 : break;
708 : : }
709 : : }
710 : :
711 : 612 : return bitmap;
712 : : }
|
