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