PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
network_spgist.c
Go to the documentation of this file.
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-2017, 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 
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
51 {
52  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
54 
55  cfg->prefixType = CIDROID;
56  cfg->labelType = VOIDOID;
57  cfg->canReturnData = true;
58  cfg->longValuesOK = false;
59 
61 }
62 
63 /*
64  * The SP-GiST choose function
65  */
66 Datum
68 {
71  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  if (!in->hasPrefix)
80  {
81  /* allTheSame isn't possible for such a tuple */
82  Assert(!in->allTheSame);
83  Assert(in->nNodes == 2);
84 
85  out->resultType = spgMatchNode;
86  out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1;
87  out->result.matchNode.restDatum = InetPGetDatum(val);
88 
90  }
91 
92  /* Else it must split by prefix */
93  Assert(in->nNodes == 4 || in->allTheSame);
94 
95  prefix = DatumGetInetPP(in->prefixDatum);
96  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  if (ip_family(val) != ip_family(prefix))
103  {
104  /* Set up 2-node tuple */
105  out->resultType = spgSplitTuple;
106  out->result.splitTuple.prefixHasPrefix = false;
107  out->result.splitTuple.prefixNNodes = 2;
108  out->result.splitTuple.prefixNodeLabels = NULL;
109 
110  /* Identify which node the existing data goes into */
111  out->result.splitTuple.childNodeN =
112  (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1;
113 
114  out->result.splitTuple.postfixHasPrefix = true;
115  out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
116 
117  PG_RETURN_VOID();
118  }
119 
120  /*
121  * If the new value does not match the existing prefix, we have to split.
122  */
123  if (ip_bits(val) < commonbits ||
124  bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0)
125  {
126  /* Determine new prefix length for the split tuple */
127  commonbits = bitncommon(ip_addr(prefix), ip_addr(val),
128  Min(ip_bits(val), commonbits));
129 
130  /* Set up 4-node tuple */
131  out->resultType = spgSplitTuple;
132  out->result.splitTuple.prefixHasPrefix = true;
133  out->result.splitTuple.prefixPrefixDatum =
134  InetPGetDatum(cidr_set_masklen_internal(val, commonbits));
135  out->result.splitTuple.prefixNNodes = 4;
136  out->result.splitTuple.prefixNodeLabels = NULL;
137 
138  /* Identify which node the existing data goes into */
139  out->result.splitTuple.childNodeN =
140  inet_spg_node_number(prefix, commonbits);
141 
142  out->result.splitTuple.postfixHasPrefix = true;
143  out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
144 
145  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  out->resultType = spgMatchNode;
154  out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits);
155  out->result.matchNode.restDatum = InetPGetDatum(val);
156 
157  PG_RETURN_VOID();
158 }
159 
160 /*
161  * The GiST PickSplit method
162  */
163 Datum
165 {
168  inet *prefix,
169  *tmp;
170  int i,
171  commonbits;
172  bool differentFamilies = false;
173 
174  /* Initialize the prefix with the first item */
175  prefix = DatumGetInetPP(in->datums[0]);
176  commonbits = ip_bits(prefix);
177 
178  /* Examine remaining items to discover minimum common prefix length */
179  for (i = 1; i < in->nTuples; i++)
180  {
181  tmp = DatumGetInetPP(in->datums[i]);
182 
183  if (ip_family(tmp) != ip_family(prefix))
184  {
185  differentFamilies = true;
186  break;
187  }
188 
189  if (ip_bits(tmp) < commonbits)
190  commonbits = ip_bits(tmp);
191  commonbits = bitncommon(ip_addr(prefix), ip_addr(tmp), commonbits);
192  if (commonbits == 0)
193  break;
194  }
195 
196  /* Don't need labels; allocate output arrays */
197  out->nodeLabels = NULL;
198  out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
199  out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
200 
201  if (differentFamilies)
202  {
203  /* Set up 2-node tuple */
204  out->hasPrefix = false;
205  out->nNodes = 2;
206 
207  for (i = 0; i < in->nTuples; i++)
208  {
209  tmp = DatumGetInetPP(in->datums[i]);
210  out->mapTuplesToNodes[i] =
211  (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1;
212  out->leafTupleDatums[i] = InetPGetDatum(tmp);
213  }
214  }
215  else
216  {
217  /* Set up 4-node tuple */
218  out->hasPrefix = true;
219  out->prefixDatum =
220  InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits));
221  out->nNodes = 4;
222 
223  for (i = 0; i < in->nTuples; i++)
224  {
225  tmp = DatumGetInetPP(in->datums[i]);
226  out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits);
227  out->leafTupleDatums[i] = InetPGetDatum(tmp);
228  }
229  }
230 
231  PG_RETURN_VOID();
232 }
233 
234 /*
235  * The SP-GiST query consistency check for inner tuples
236  */
237 Datum
239 {
242  int i;
243  int which;
244 
245  if (!in->hasPrefix)
246  {
247  Assert(!in->allTheSame);
248  Assert(in->nNodes == 2);
249 
250  /* Identify which child nodes need to be visited */
251  which = 1 | (1 << 1);
252 
253  for (i = 0; i < in->nkeys; i++)
254  {
255  StrategyNumber strategy = in->scankeys[i].sk_strategy;
256  inet *argument = DatumGetInetPP(in->scankeys[i].sk_argument);
257 
258  switch (strategy)
259  {
262  if (ip_family(argument) == PGSQL_AF_INET)
263  which &= 1;
264  break;
265 
268  if (ip_family(argument) == PGSQL_AF_INET6)
269  which &= (1 << 1);
270  break;
271 
273  break;
274 
275  default:
276  /* all other ops can only match addrs of same family */
277  if (ip_family(argument) == PGSQL_AF_INET)
278  which &= 1;
279  else
280  which &= (1 << 1);
281  break;
282  }
283  }
284  }
285  else if (!in->allTheSame)
286  {
287  Assert(in->nNodes == 4);
288 
289  /* Identify which child nodes need to be visited */
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  which = ~0;
297  }
298 
299  out->nNodes = 0;
300 
301  if (which)
302  {
303  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
304 
305  for (i = 0; i < in->nNodes; i++)
306  {
307  if (which & (1 << i))
308  {
309  out->nodeNumbers[out->nNodes] = i;
310  out->nNodes++;
311  }
312  }
313  }
314 
315  PG_RETURN_VOID();
316 }
317 
318 /*
319  * The SP-GiST query consistency check for leaf tuples
320  */
321 Datum
323 {
326  inet *leaf = DatumGetInetPP(in->leafDatum);
327 
328  /* All tests are exact. */
329  out->recheck = false;
330 
331  /* Leaf is what it is... */
332  out->leafValue = InetPGetDatum(leaf);
333 
334  /* Use common code to apply the tests. */
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
349 inet_spg_node_number(const inet *val, int commonbits)
350 {
351  int nodeN = 0;
352 
353  if (commonbits < ip_maxbits(val) &&
354  ip_addr(val)[commonbits / 8] & (1 << (7 - commonbits % 8)))
355  nodeN |= 1;
356  if (commonbits < ip_bits(val))
357  nodeN |= 2;
358 
359  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
373 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  if (leaf)
382  bitmap = 1;
383  else
384  bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);
385 
386  commonbits = ip_bits(prefix);
387 
388  for (i = 0; i < nkeys; i++)
389  {
390  inet *argument = DatumGetInetPP(scankeys[i].sk_argument);
391  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  if (ip_family(argument) != ip_family(prefix))
400  {
401  switch (strategy)
402  {
405  if (ip_family(argument) < ip_family(prefix))
406  bitmap = 0;
407  break;
408 
411  if (ip_family(argument) > ip_family(prefix))
412  bitmap = 0;
413  break;
414 
416  break;
417 
418  default:
419  /* For all other cases, we can be sure there is no match */
420  bitmap = 0;
421  break;
422  }
423 
424  if (!bitmap)
425  break;
426 
427  /* Other checks make no sense with different families. */
428  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  switch (strategy)
445  {
446  case RTSubStrategyNumber:
447  if (commonbits <= ip_bits(argument))
448  bitmap &= (1 << 2) | (1 << 3);
449  break;
450 
452  if (commonbits < ip_bits(argument))
453  bitmap &= (1 << 2) | (1 << 3);
454  break;
455 
457  if (commonbits == ip_bits(argument) - 1)
458  bitmap &= 1 | (1 << 1);
459  else if (commonbits >= ip_bits(argument))
460  bitmap = 0;
461  break;
462 
464  if (commonbits == ip_bits(argument))
465  bitmap &= 1 | (1 << 1);
466  else if (commonbits > ip_bits(argument))
467  bitmap = 0;
468  break;
469 
471  if (commonbits < ip_bits(argument))
472  bitmap &= (1 << 2) | (1 << 3);
473  else if (commonbits == ip_bits(argument))
474  bitmap &= 1 | (1 << 1);
475  else
476  bitmap = 0;
477  break;
478  }
479 
480  if (!bitmap)
481  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  order = bitncmp(ip_addr(prefix), ip_addr(argument),
492  Min(commonbits, ip_bits(argument)));
493 
494  if (order != 0)
495  {
496  switch (strategy)
497  {
500  if (order > 0)
501  bitmap = 0;
502  break;
503 
506  if (order < 0)
507  bitmap = 0;
508  break;
509 
511  break;
512 
513  default:
514  /* For all other cases, we can be sure there is no match */
515  bitmap = 0;
516  break;
517  }
518 
519  if (!bitmap)
520  break;
521 
522  /*
523  * Remaining checks make no sense when common bits don't match.
524  */
525  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  if (bitmap & ((1 << 2) | (1 << 3)) &&
538  commonbits < ip_bits(argument))
539  {
540  int nextbit;
541 
542  nextbit = ip_addr(argument)[commonbits / 8] &
543  (1 << (7 - commonbits % 8));
544 
545  switch (strategy)
546  {
549  if (!nextbit)
550  bitmap &= 1 | (1 << 1) | (1 << 2);
551  break;
552 
555  if (nextbit)
556  bitmap &= 1 | (1 << 1) | (1 << 3);
557  break;
558 
560  break;
561 
562  default:
563  if (!nextbit)
564  bitmap &= 1 | (1 << 1) | (1 << 2);
565  else
566  bitmap &= 1 | (1 << 1) | (1 << 3);
567  break;
568  }
569 
570  if (!bitmap)
571  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  */
578  if (strategy < RTEqualStrategyNumber ||
579  strategy > RTGreaterEqualStrategyNumber)
580  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  switch (strategy)
590  {
593  if (commonbits == ip_bits(argument))
594  bitmap &= 1 | (1 << 1);
595  else if (commonbits > ip_bits(argument))
596  bitmap = 0;
597  break;
598 
601  if (commonbits < ip_bits(argument))
602  bitmap &= (1 << 2) | (1 << 3);
603  break;
604  }
605 
606  if (!bitmap)
607  break;
608 
609  /* Remaining checks don't make sense with different ip_bits. */
610  if (commonbits != ip_bits(argument))
611  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  if (!leaf && bitmap & (1 | (1 << 1)) &&
624  commonbits < ip_maxbits(argument))
625  {
626  int nextbit;
627 
628  nextbit = ip_addr(argument)[commonbits / 8] &
629  (1 << (7 - commonbits % 8));
630 
631  switch (strategy)
632  {
635  if (!nextbit)
636  bitmap &= 1 | (1 << 2) | (1 << 3);
637  break;
638 
641  if (nextbit)
642  bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
643  break;
644 
646  break;
647 
648  default:
649  if (!nextbit)
650  bitmap &= 1 | (1 << 2) | (1 << 3);
651  else
652  bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
653  break;
654  }
655 
656  if (!bitmap)
657  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  */
666  if (leaf)
667  {
668  /* Redo ordering comparison using all address bits */
669  order = bitncmp(ip_addr(prefix), ip_addr(argument),
670  ip_maxbits(prefix));
671 
672  switch (strategy)
673  {
675  if (order >= 0)
676  bitmap = 0;
677  break;
678 
680  if (order > 0)
681  bitmap = 0;
682  break;
683 
685  if (order != 0)
686  bitmap = 0;
687  break;
688 
690  if (order < 0)
691  bitmap = 0;
692  break;
693 
695  if (order <= 0)
696  bitmap = 0;
697  break;
698 
700  if (order == 0)
701  bitmap = 0;
702  break;
703  }
704 
705  if (!bitmap)
706  break;
707  }
708  }
709 
710  return bitmap;
711 }
#define CIDROID
Definition: pg_type.h:443
static int inet_spg_node_number(const inet *val, int commonbits)
Datum datum
Definition: spgist.h:56
bool hasPrefix
Definition: spgist.h:62
struct spgChooseOut::@41::@42 matchNode
#define ip_bits(inetptr)
Definition: inet.h:74
#define ip_family(inetptr)
Definition: inet.h:71
#define RTSuperStrategyNumber
Definition: stratnum.h:69
#define PGSQL_AF_INET
Definition: inet.h:39
bool canReturnData
Definition: spgist.h:47
Datum * leafTupleDatums
Definition: spgist.h:127
Datum inet_spg_config(PG_FUNCTION_ARGS)
Datum * datums
Definition: spgist.h:114
#define DatumGetInetPP(X)
Definition: inet.h:108
#define ip_addr(inetptr)
Definition: inet.h:77
#define Min(x, y)
Definition: c.h:802
int bitncommon(const unsigned char *l, const unsigned char *r, int n)
Definition: network.c:994
Datum prefixDatum
Definition: spgist.h:63
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:232
#define RTLessStrategyNumber
Definition: stratnum.h:63
#define PGSQL_AF_INET6
Definition: inet.h:40
#define ip_maxbits(inetptr)
Definition: inet.h:83
Datum inet_spg_leaf_consistent(PG_FUNCTION_ARGS)
#define VOIDOID
Definition: pg_type.h:678
Datum * nodeLabels
Definition: spgist.h:124
StrategyNumber sk_strategy
Definition: skey.h:68
Datum inet_spg_choose(PG_FUNCTION_ARGS)
ScanKey scankeys
Definition: spgist.h:167
#define RTGreaterStrategyNumber
Definition: stratnum.h:65
#define RTLessEqualStrategyNumber
Definition: stratnum.h:64
Definition: inet.h:52
struct spgChooseOut::@41::@44 splitTuple
int nNodes
Definition: spgist.h:64
#define InetPGetDatum(X)
Definition: inet.h:109
static int inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys, bool leaf)
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:303
bool longValuesOK
Definition: spgist.h:48
uintptr_t Datum
Definition: postgres.h:374
#define RTSubStrategyNumber
Definition: stratnum.h:67
Oid prefixType
Definition: spgist.h:45
spgChooseResultType resultType
Definition: spgist.h:77
#define PG_RETURN_VOID()
Definition: fmgr.h:293
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define RTEqualStrategyNumber
Definition: stratnum.h:61
bool hasPrefix
Definition: spgist.h:120
inet * cidr_set_masklen_internal(const inet *src, int bits)
Definition: network.c:327
ScanKey scankeys
Definition: spgist.h:135
#define RTSuperEqualStrategyNumber
Definition: stratnum.h:70
Datum inet_spg_inner_consistent(PG_FUNCTION_ARGS)
void * palloc(Size size)
Definition: mcxt.c:849
int bitncmp(const unsigned char *l, const unsigned char *r, int n)
Definition: network.c:960
Oid labelType
Definition: spgist.h:46
int i
int * mapTuplesToNodes
Definition: spgist.h:126
union spgChooseOut::@41 result
bool allTheSame
Definition: spgist.h:61
#define RTSubEqualStrategyNumber
Definition: stratnum.h:68
Datum prefixDatum
Definition: spgist.h:121
#define PG_FUNCTION_ARGS
Definition: fmgr.h:150
#define RTNotEqualStrategyNumber
Definition: stratnum.h:62
#define RTGreaterEqualStrategyNumber
Definition: stratnum.h:66
Datum inet_spg_picksplit(PG_FUNCTION_ARGS)
Datum sk_argument
Definition: skey.h:72
long val
Definition: informix.c:689