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-2023, 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/builtins.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 GIC 9 : inet_spg_config(PG_FUNCTION_ARGS)
52 ECB : {
53 : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
54 GIC 9 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
55 ECB :
56 GIC 9 : cfg->prefixType = CIDROID;
57 CBC 9 : cfg->labelType = VOIDOID;
58 9 : cfg->canReturnData = true;
59 9 : cfg->longValuesOK = false;
60 ECB :
61 GIC 9 : PG_RETURN_VOID();
62 ECB : }
63 :
64 : /*
65 : * The SP-GiST choose function
66 : */
67 : Datum
68 UIC 0 : inet_spg_choose(PG_FUNCTION_ARGS)
69 EUB : {
70 UIC 0 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
71 UBC 0 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
72 0 : inet *val = DatumGetInetPP(in->datum),
73 EUB : *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 UIC 0 : if (!in->hasPrefix)
81 EUB : {
82 : /* allTheSame isn't possible for such a tuple */
83 UIC 0 : Assert(!in->allTheSame);
84 UBC 0 : Assert(in->nNodes == 2);
85 EUB :
86 UIC 0 : out->resultType = spgMatchNode;
87 UBC 0 : out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1;
88 0 : out->result.matchNode.restDatum = InetPGetDatum(val);
89 EUB :
90 UIC 0 : PG_RETURN_VOID();
91 EUB : }
92 :
93 : /* Else it must split by prefix */
94 UIC 0 : Assert(in->nNodes == 4 || in->allTheSame);
95 EUB :
96 UIC 0 : prefix = DatumGetInetPP(in->prefixDatum);
97 UBC 0 : commonbits = ip_bits(prefix);
98 EUB :
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 UIC 0 : if (ip_family(val) != ip_family(prefix))
104 EUB : {
105 : /* Set up 2-node tuple */
106 UIC 0 : out->resultType = spgSplitTuple;
107 UBC 0 : out->result.splitTuple.prefixHasPrefix = false;
108 0 : out->result.splitTuple.prefixNNodes = 2;
109 0 : out->result.splitTuple.prefixNodeLabels = NULL;
110 EUB :
111 : /* Identify which node the existing data goes into */
112 UIC 0 : out->result.splitTuple.childNodeN =
113 UBC 0 : (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1;
114 EUB :
115 UIC 0 : out->result.splitTuple.postfixHasPrefix = true;
116 UBC 0 : out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
117 EUB :
118 UIC 0 : PG_RETURN_VOID();
119 EUB : }
120 :
121 : /*
122 : * If the new value does not match the existing prefix, we have to split.
123 : */
124 UIC 0 : if (ip_bits(val) < commonbits ||
125 UBC 0 : bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0)
126 EUB : {
127 : /* Determine new prefix length for the split tuple */
128 UIC 0 : commonbits = bitncommon(ip_addr(prefix), ip_addr(val),
129 UBC 0 : Min(ip_bits(val), commonbits));
130 EUB :
131 : /* Set up 4-node tuple */
132 UIC 0 : out->resultType = spgSplitTuple;
133 UBC 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 EUB :
139 : /* Identify which node the existing data goes into */
140 UIC 0 : out->result.splitTuple.childNodeN =
141 UBC 0 : inet_spg_node_number(prefix, commonbits);
142 EUB :
143 UIC 0 : out->result.splitTuple.postfixHasPrefix = true;
144 UBC 0 : out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
145 EUB :
146 UIC 0 : PG_RETURN_VOID();
147 EUB : }
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 UIC 0 : out->resultType = spgMatchNode;
155 UBC 0 : out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits);
156 0 : out->result.matchNode.restDatum = InetPGetDatum(val);
157 EUB :
158 UIC 0 : PG_RETURN_VOID();
159 EUB : }
160 :
161 : /*
162 : * The GiST PickSplit method
163 : */
164 : Datum
165 UIC 0 : inet_spg_picksplit(PG_FUNCTION_ARGS)
166 EUB : {
167 UIC 0 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
168 UBC 0 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
169 EUB : inet *prefix,
170 : *tmp;
171 : int i,
172 : commonbits;
173 UIC 0 : bool differentFamilies = false;
174 EUB :
175 : /* Initialize the prefix with the first item */
176 UIC 0 : prefix = DatumGetInetPP(in->datums[0]);
177 UBC 0 : commonbits = ip_bits(prefix);
178 EUB :
179 : /* Examine remaining items to discover minimum common prefix length */
180 UIC 0 : for (i = 1; i < in->nTuples; i++)
181 EUB : {
182 UIC 0 : tmp = DatumGetInetPP(in->datums[i]);
183 EUB :
184 UIC 0 : if (ip_family(tmp) != ip_family(prefix))
185 EUB : {
186 UIC 0 : differentFamilies = true;
187 UBC 0 : break;
188 EUB : }
189 :
190 UIC 0 : if (ip_bits(tmp) < commonbits)
191 UBC 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 EUB : }
196 :
197 : /* Don't need labels; allocate output arrays */
198 UIC 0 : out->nodeLabels = NULL;
199 UBC 0 : out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
200 0 : out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
201 EUB :
202 UIC 0 : if (differentFamilies)
203 EUB : {
204 : /* Set up 2-node tuple */
205 UIC 0 : out->hasPrefix = false;
206 UBC 0 : out->nNodes = 2;
207 EUB :
208 UIC 0 : for (i = 0; i < in->nTuples; i++)
209 EUB : {
210 UIC 0 : tmp = DatumGetInetPP(in->datums[i]);
211 UBC 0 : out->mapTuplesToNodes[i] =
212 0 : (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1;
213 0 : out->leafTupleDatums[i] = InetPGetDatum(tmp);
214 EUB : }
215 : }
216 : else
217 : {
218 : /* Set up 4-node tuple */
219 UIC 0 : out->hasPrefix = true;
220 UBC 0 : out->prefixDatum =
221 0 : InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits));
222 0 : out->nNodes = 4;
223 EUB :
224 UIC 0 : for (i = 0; i < in->nTuples; i++)
225 EUB : {
226 UIC 0 : tmp = DatumGetInetPP(in->datums[i]);
227 UBC 0 : out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits);
228 0 : out->leafTupleDatums[i] = InetPGetDatum(tmp);
229 EUB : }
230 : }
231 :
232 UIC 0 : PG_RETURN_VOID();
233 EUB : }
234 :
235 : /*
236 : * The SP-GiST query consistency check for inner tuples
237 : */
238 : Datum
239 UIC 0 : inet_spg_inner_consistent(PG_FUNCTION_ARGS)
240 EUB : {
241 UIC 0 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
242 UBC 0 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
243 EUB : int i;
244 : int which;
245 :
246 UIC 0 : if (!in->hasPrefix)
247 EUB : {
248 UIC 0 : Assert(!in->allTheSame);
249 UBC 0 : Assert(in->nNodes == 2);
250 EUB :
251 : /* Identify which child nodes need to be visited */
252 UIC 0 : which = 1 | (1 << 1);
253 EUB :
254 UIC 0 : for (i = 0; i < in->nkeys; i++)
255 EUB : {
256 UIC 0 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
257 UBC 0 : inet *argument = DatumGetInetPP(in->scankeys[i].sk_argument);
258 EUB :
259 UIC 0 : switch (strategy)
260 EUB : {
261 UIC 0 : case RTLessStrategyNumber:
262 EUB : case RTLessEqualStrategyNumber:
263 UIC 0 : if (ip_family(argument) == PGSQL_AF_INET)
264 UBC 0 : which &= 1;
265 0 : break;
266 EUB :
267 UIC 0 : case RTGreaterEqualStrategyNumber:
268 EUB : case RTGreaterStrategyNumber:
269 UIC 0 : if (ip_family(argument) == PGSQL_AF_INET6)
270 UBC 0 : which &= (1 << 1);
271 0 : break;
272 EUB :
273 UIC 0 : case RTNotEqualStrategyNumber:
274 UBC 0 : break;
275 EUB :
276 UIC 0 : default:
277 EUB : /* all other ops can only match addrs of same family */
278 UIC 0 : if (ip_family(argument) == PGSQL_AF_INET)
279 UBC 0 : which &= 1;
280 EUB : else
281 UIC 0 : which &= (1 << 1);
282 UBC 0 : break;
283 EUB : }
284 : }
285 : }
286 UIC 0 : else if (!in->allTheSame)
287 EUB : {
288 UIC 0 : Assert(in->nNodes == 4);
289 EUB :
290 : /* Identify which child nodes need to be visited */
291 UIC 0 : which = inet_spg_consistent_bitmap(DatumGetInetPP(in->prefixDatum),
292 EUB : in->nkeys, in->scankeys, false);
293 : }
294 : else
295 : {
296 : /* Must visit all nodes; we assume there are less than 32 of 'em */
297 UIC 0 : which = ~0;
298 EUB : }
299 :
300 UIC 0 : out->nNodes = 0;
301 EUB :
302 UIC 0 : if (which)
303 EUB : {
304 UIC 0 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
305 EUB :
306 UIC 0 : for (i = 0; i < in->nNodes; i++)
307 EUB : {
308 UIC 0 : if (which & (1 << i))
309 EUB : {
310 UIC 0 : out->nodeNumbers[out->nNodes] = i;
311 UBC 0 : out->nNodes++;
312 EUB : }
313 : }
314 : }
315 :
316 UIC 0 : PG_RETURN_VOID();
317 EUB : }
318 :
319 : /*
320 : * The SP-GiST query consistency check for leaf tuples
321 : */
322 : Datum
323 GIC 612 : inet_spg_leaf_consistent(PG_FUNCTION_ARGS)
324 ECB : {
325 GIC 612 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
326 CBC 612 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
327 612 : inet *leaf = DatumGetInetPP(in->leafDatum);
328 ECB :
329 : /* All tests are exact. */
330 GIC 612 : out->recheck = false;
331 ECB :
332 : /* Leaf is what it is... */
333 GIC 612 : out->leafValue = InetPGetDatum(leaf);
334 ECB :
335 : /* Use common code to apply the tests. */
336 GIC 612 : PG_RETURN_BOOL(inet_spg_consistent_bitmap(leaf, in->nkeys, in->scankeys,
337 ECB : 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
350 UIC 0 : inet_spg_node_number(const inet *val, int commonbits)
351 EUB : {
352 UIC 0 : int nodeN = 0;
353 EUB :
354 UIC 0 : if (commonbits < ip_maxbits(val) &&
355 UBC 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 EUB :
360 UIC 0 : return nodeN;
361 EUB : }
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
374 GIC 612 : inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys,
375 ECB : bool leaf)
376 : {
377 : int bitmap;
378 : int commonbits,
379 : i;
380 :
381 : /* Initialize result to allow visiting all children */
382 GIC 612 : if (leaf)
383 CBC 612 : bitmap = 1;
384 ECB : else
385 UIC 0 : bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);
386 EUB :
387 GIC 612 : commonbits = ip_bits(prefix);
388 ECB :
389 GIC 828 : for (i = 0; i < nkeys; i++)
390 ECB : {
391 GIC 612 : inet *argument = DatumGetInetPP(scankeys[i].sk_argument);
392 CBC 612 : StrategyNumber strategy = scankeys[i].sk_strategy;
393 ECB : int order;
394 :
395 : /*
396 : * Check 0: different families
397 : *
398 : * Matching families do not help any of the strategies.
399 : */
400 GIC 612 : if (ip_family(argument) != ip_family(prefix))
401 ECB : {
402 GIC 108 : switch (strategy)
403 ECB : {
404 GIC 18 : case RTLessStrategyNumber:
405 ECB : case RTLessEqualStrategyNumber:
406 GIC 18 : if (ip_family(argument) < ip_family(prefix))
407 CBC 18 : bitmap = 0;
408 18 : break;
409 ECB :
410 GIC 18 : case RTGreaterEqualStrategyNumber:
411 ECB : case RTGreaterStrategyNumber:
412 GIC 18 : if (ip_family(argument) > ip_family(prefix))
413 LBC 0 : bitmap = 0;
414 GBC 18 : break;
415 ECB :
416 GIC 9 : case RTNotEqualStrategyNumber:
417 CBC 9 : break;
418 ECB :
419 GIC 63 : default:
420 ECB : /* For all other cases, we can be sure there is no match */
421 GIC 63 : bitmap = 0;
422 CBC 63 : break;
423 ECB : }
424 :
425 GIC 108 : if (!bitmap)
426 CBC 81 : break;
427 ECB :
428 : /* Other checks make no sense with different families. */
429 GIC 27 : continue;
430 ECB : }
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 GIC 504 : switch (strategy)
446 ECB : {
447 GIC 84 : case RTSubStrategyNumber:
448 CBC 84 : if (commonbits <= ip_bits(argument))
449 60 : bitmap &= (1 << 2) | (1 << 3);
450 84 : break;
451 ECB :
452 GIC 42 : case RTSubEqualStrategyNumber:
453 CBC 42 : if (commonbits < ip_bits(argument))
454 18 : bitmap &= (1 << 2) | (1 << 3);
455 42 : break;
456 ECB :
457 GIC 42 : case RTSuperStrategyNumber:
458 CBC 42 : if (commonbits == ip_bits(argument) - 1)
459 LBC 0 : bitmap &= 1 | (1 << 1);
460 GBC 42 : else if (commonbits >= ip_bits(argument))
461 CBC 24 : bitmap = 0;
462 42 : break;
463 ECB :
464 GIC 42 : case RTSuperEqualStrategyNumber:
465 CBC 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 ECB :
471 GIC 42 : case RTEqualStrategyNumber:
472 CBC 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 ECB : else
477 GIC 12 : bitmap = 0;
478 CBC 42 : break;
479 ECB : }
480 :
481 GIC 504 : if (!bitmap)
482 CBC 144 : break;
483 ECB :
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 GIC 360 : order = bitncmp(ip_addr(prefix), ip_addr(argument),
493 CBC 360 : Min(commonbits, ip_bits(argument)));
494 ECB :
495 GIC 360 : if (order != 0)
496 ECB : {
497 GIC 198 : switch (strategy)
498 ECB : {
499 GIC 48 : case RTLessStrategyNumber:
500 ECB : case RTLessEqualStrategyNumber:
501 GIC 48 : if (order > 0)
502 LBC 0 : bitmap = 0;
503 GBC 48 : break;
504 ECB :
505 GIC 48 : case RTGreaterEqualStrategyNumber:
506 ECB : case RTGreaterStrategyNumber:
507 GIC 48 : if (order < 0)
508 CBC 48 : bitmap = 0;
509 48 : break;
510 ECB :
511 GIC 24 : case RTNotEqualStrategyNumber:
512 CBC 24 : break;
513 ECB :
514 GIC 78 : default:
515 ECB : /* For all other cases, we can be sure there is no match */
516 GIC 78 : bitmap = 0;
517 CBC 78 : break;
518 ECB : }
519 :
520 GIC 198 : if (!bitmap)
521 CBC 126 : break;
522 ECB :
523 : /*
524 : * Remaining checks make no sense when common bits don't match.
525 : */
526 GIC 72 : continue;
527 ECB : }
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 GIC 162 : if (bitmap & ((1 << 2) | (1 << 3)) &&
539 LBC 0 : commonbits < ip_bits(argument))
540 EUB : {
541 : int nextbit;
542 :
543 UIC 0 : nextbit = ip_addr(argument)[commonbits / 8] &
544 UBC 0 : (1 << (7 - commonbits % 8));
545 EUB :
546 UIC 0 : switch (strategy)
547 EUB : {
548 UIC 0 : case RTLessStrategyNumber:
549 EUB : case RTLessEqualStrategyNumber:
550 UIC 0 : if (!nextbit)
551 UBC 0 : bitmap &= 1 | (1 << 1) | (1 << 2);
552 0 : break;
553 EUB :
554 UIC 0 : case RTGreaterEqualStrategyNumber:
555 EUB : case RTGreaterStrategyNumber:
556 UIC 0 : if (nextbit)
557 UBC 0 : bitmap &= 1 | (1 << 1) | (1 << 3);
558 0 : break;
559 EUB :
560 UIC 0 : case RTNotEqualStrategyNumber:
561 UBC 0 : break;
562 EUB :
563 UIC 0 : default:
564 UBC 0 : if (!nextbit)
565 0 : bitmap &= 1 | (1 << 1) | (1 << 2);
566 EUB : else
567 UIC 0 : bitmap &= 1 | (1 << 1) | (1 << 3);
568 UBC 0 : break;
569 EUB : }
570 :
571 UIC 0 : if (!bitmap)
572 UBC 0 : break;
573 EUB : }
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 : */
579 GIC 162 : if (strategy < RTEqualStrategyNumber ||
580 ECB : strategy > RTGreaterEqualStrategyNumber)
581 GIC 63 : continue;
582 ECB :
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 GIC 99 : switch (strategy)
591 ECB : {
592 GIC 36 : case RTLessStrategyNumber:
593 ECB : case RTLessEqualStrategyNumber:
594 GIC 36 : if (commonbits == ip_bits(argument))
595 CBC 18 : bitmap &= 1 | (1 << 1);
596 18 : else if (commonbits > ip_bits(argument))
597 18 : bitmap = 0;
598 36 : break;
599 ECB :
600 GIC 36 : case RTGreaterEqualStrategyNumber:
601 ECB : case RTGreaterStrategyNumber:
602 GIC 36 : if (commonbits < ip_bits(argument))
603 LBC 0 : bitmap &= (1 << 2) | (1 << 3);
604 GBC 36 : break;
605 ECB : }
606 :
607 GIC 99 : if (!bitmap)
608 CBC 18 : break;
609 ECB :
610 : /* Remaining checks don't make sense with different ip_bits. */
611 GIC 81 : if (commonbits != ip_bits(argument))
612 CBC 27 : continue;
613 ECB :
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 GIC 54 : if (!leaf && bitmap & (1 | (1 << 1)) &&
625 LBC 0 : commonbits < ip_maxbits(argument))
626 EUB : {
627 : int nextbit;
628 :
629 UIC 0 : nextbit = ip_addr(argument)[commonbits / 8] &
630 UBC 0 : (1 << (7 - commonbits % 8));
631 EUB :
632 UIC 0 : switch (strategy)
633 EUB : {
634 UIC 0 : case RTLessStrategyNumber:
635 EUB : case RTLessEqualStrategyNumber:
636 UIC 0 : if (!nextbit)
637 UBC 0 : bitmap &= 1 | (1 << 2) | (1 << 3);
638 0 : break;
639 EUB :
640 UIC 0 : case RTGreaterEqualStrategyNumber:
641 EUB : case RTGreaterStrategyNumber:
642 UIC 0 : if (nextbit)
643 UBC 0 : bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
644 0 : break;
645 EUB :
646 UIC 0 : case RTNotEqualStrategyNumber:
647 UBC 0 : break;
648 EUB :
649 UIC 0 : default:
650 UBC 0 : if (!nextbit)
651 0 : bitmap &= 1 | (1 << 2) | (1 << 3);
652 EUB : else
653 UIC 0 : bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
654 UBC 0 : break;
655 EUB : }
656 :
657 UIC 0 : if (!bitmap)
658 UBC 0 : break;
659 EUB : }
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 : */
667 GIC 54 : if (leaf)
668 ECB : {
669 : /* Redo ordering comparison using all address bits */
670 GIC 54 : order = bitncmp(ip_addr(prefix), ip_addr(argument),
671 CBC 54 : ip_maxbits(prefix));
672 ECB :
673 GIC 54 : switch (strategy)
674 ECB : {
675 GIC 9 : case RTLessStrategyNumber:
676 CBC 9 : if (order >= 0)
677 9 : bitmap = 0;
678 9 : break;
679 ECB :
680 GIC 9 : case RTLessEqualStrategyNumber:
681 CBC 9 : if (order > 0)
682 6 : bitmap = 0;
683 9 : break;
684 ECB :
685 GIC 9 : case RTEqualStrategyNumber:
686 CBC 9 : if (order != 0)
687 6 : bitmap = 0;
688 9 : break;
689 ECB :
690 GIC 9 : case RTGreaterEqualStrategyNumber:
691 CBC 9 : if (order < 0)
692 LBC 0 : bitmap = 0;
693 GBC 9 : break;
694 ECB :
695 GIC 9 : case RTGreaterStrategyNumber:
696 CBC 9 : if (order <= 0)
697 3 : bitmap = 0;
698 9 : break;
699 ECB :
700 GIC 9 : case RTNotEqualStrategyNumber:
701 CBC 9 : if (order == 0)
702 3 : bitmap = 0;
703 9 : break;
704 ECB : }
705 :
706 GIC 54 : if (!bitmap)
707 CBC 27 : break;
708 ECB : }
709 : }
710 :
711 GIC 612 : return bitmap;
712 ECB : }
|
