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