PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
network_gist.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * network_gist.c
4  * GiST support for network types.
5  *
6  * The key thing to understand about this code is the definition of the
7  * "union" of a set of INET/CIDR values. It works like this:
8  * 1. If the values are not all of the same IP address family, the "union"
9  * is a dummy value with family number zero, minbits zero, commonbits zero,
10  * address all zeroes. Otherwise:
11  * 2. The union has the common IP address family number.
12  * 3. The union's minbits value is the smallest netmask length ("ip_bits")
13  * of all the input values.
14  * 4. Let C be the number of leading address bits that are in common among
15  * all the input values (C ranges from 0 to ip_maxbits for the family).
16  * 5. The union's commonbits value is C.
17  * 6. The union's address value is the same as the common prefix for its
18  * first C bits, and is zeroes to the right of that. The physical width
19  * of the address value is ip_maxbits for the address family.
20  *
21  * In a leaf index entry (representing a single key), commonbits is equal to
22  * ip_maxbits for the address family, minbits is the same as the represented
23  * value's ip_bits, and the address is equal to the represented address.
24  * Although it may appear that we're wasting a byte by storing the union
25  * format and not just the represented INET/CIDR value in leaf keys, the
26  * extra byte is actually "free" because of alignment considerations.
27  *
28  * Note that this design tracks minbits and commonbits independently; in any
29  * given union value, either might be smaller than the other. This does not
30  * help us much when descending the tree, because of the way inet comparison
31  * is defined: at non-leaf nodes we can't compare more than minbits bits
32  * even if we know them. However, it greatly improves the quality of split
33  * decisions. Preliminary testing suggests that searches are as much as
34  * twice as fast as for a simpler design in which a single field doubles as
35  * the common prefix length and the minimum ip_bits value.
36  *
37  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
38  * Portions Copyright (c) 1994, Regents of the University of California
39  *
40  *
41  * IDENTIFICATION
42  * src/backend/utils/adt/network_gist.c
43  *
44  *-------------------------------------------------------------------------
45  */
46 #include "postgres.h"
47 
48 #include <sys/socket.h>
49 
50 #include "access/gist.h"
51 #include "access/stratnum.h"
52 #include "utils/builtins.h"
53 #include "utils/inet.h"
54 
55 /*
56  * Operator strategy numbers used in the GiST inet_ops opclass
57  */
58 #define INETSTRAT_OVERLAPS RTOverlapStrategyNumber
59 #define INETSTRAT_EQ RTEqualStrategyNumber
60 #define INETSTRAT_NE RTNotEqualStrategyNumber
61 #define INETSTRAT_LT RTLessStrategyNumber
62 #define INETSTRAT_LE RTLessEqualStrategyNumber
63 #define INETSTRAT_GT RTGreaterStrategyNumber
64 #define INETSTRAT_GE RTGreaterEqualStrategyNumber
65 #define INETSTRAT_SUB RTSubStrategyNumber
66 #define INETSTRAT_SUBEQ RTSubEqualStrategyNumber
67 #define INETSTRAT_SUP RTSuperStrategyNumber
68 #define INETSTRAT_SUPEQ RTSuperEqualStrategyNumber
69 
70 
71 /*
72  * Representation of a GiST INET/CIDR index key. This is not identical to
73  * INET/CIDR because we need to keep track of the length of the common address
74  * prefix as well as the minimum netmask length. However, as long as it
75  * follows varlena header rules, the core GiST code won't know the difference.
76  * For simplicity we always use 1-byte-header varlena format.
77  */
78 typedef struct GistInetKey
79 {
80  uint8 va_header; /* varlena header --- don't touch directly */
81  unsigned char family; /* PGSQL_AF_INET, PGSQL_AF_INET6, or zero */
82  unsigned char minbits; /* minimum number of bits in netmask */
83  unsigned char commonbits; /* number of common prefix bits in addresses */
84  unsigned char ipaddr[16]; /* up to 128 bits of common address */
85 } GistInetKey;
86 
87 #define DatumGetInetKeyP(X) ((GistInetKey *) DatumGetPointer(X))
88 #define InetKeyPGetDatum(X) PointerGetDatum(X)
89 
90 /*
91  * Access macros; not really exciting, but we use these for notational
92  * consistency with access to INET/CIDR values. Note that family-zero values
93  * are stored with 4 bytes of address, not 16.
94  */
95 #define gk_ip_family(gkptr) ((gkptr)->family)
96 #define gk_ip_minbits(gkptr) ((gkptr)->minbits)
97 #define gk_ip_commonbits(gkptr) ((gkptr)->commonbits)
98 #define gk_ip_addr(gkptr) ((gkptr)->ipaddr)
99 #define ip_family_maxbits(fam) ((fam) == PGSQL_AF_INET6 ? 128 : 32)
100 
101 /* These require that the family field has been set: */
102 #define gk_ip_addrsize(gkptr) \
103  (gk_ip_family(gkptr) == PGSQL_AF_INET6 ? 16 : 4)
104 #define gk_ip_maxbits(gkptr) \
105  ip_family_maxbits(gk_ip_family(gkptr))
106 #define SET_GK_VARSIZE(dst) \
107  SET_VARSIZE_SHORT(dst, offsetof(GistInetKey, ipaddr) + gk_ip_addrsize(dst))
108 
109 
110 /*
111  * The GiST query consistency check
112  */
113 Datum
115 {
116  GISTENTRY *ent = (GISTENTRY *) PG_GETARG_POINTER(0);
117  inet *query = PG_GETARG_INET_PP(1);
119 
120  /* Oid subtype = PG_GETARG_OID(3); */
121  bool *recheck = (bool *) PG_GETARG_POINTER(4);
122  GistInetKey *key = DatumGetInetKeyP(ent->key);
123  int minbits,
124  order;
125 
126  /* All operators served by this function are exact. */
127  *recheck = false;
128 
129  /*
130  * Check 0: different families
131  *
132  * If key represents multiple address families, its children could match
133  * anything. This can only happen on an inner index page.
134  */
135  if (gk_ip_family(key) == 0)
136  {
137  Assert(!GIST_LEAF(ent));
138  PG_RETURN_BOOL(true);
139  }
140 
141  /*
142  * Check 1: different families
143  *
144  * Matching families do not help any of the strategies.
145  */
146  if (gk_ip_family(key) != ip_family(query))
147  {
148  switch (strategy)
149  {
150  case INETSTRAT_LT:
151  case INETSTRAT_LE:
152  if (gk_ip_family(key) < ip_family(query))
153  PG_RETURN_BOOL(true);
154  break;
155 
156  case INETSTRAT_GE:
157  case INETSTRAT_GT:
158  if (gk_ip_family(key) > ip_family(query))
159  PG_RETURN_BOOL(true);
160  break;
161 
162  case INETSTRAT_NE:
163  PG_RETURN_BOOL(true);
164  }
165  /* For all other cases, we can be sure there is no match */
166  PG_RETURN_BOOL(false);
167  }
168 
169  /*
170  * Check 2: network bit count
171  *
172  * Network bit count (ip_bits) helps to check leaves for sub network and
173  * sup network operators. At non-leaf nodes, we know every child value
174  * has ip_bits >= gk_ip_minbits(key), so we can avoid descending in some
175  * cases too.
176  */
177  switch (strategy)
178  {
179  case INETSTRAT_SUB:
180  if (GIST_LEAF(ent) && gk_ip_minbits(key) <= ip_bits(query))
181  PG_RETURN_BOOL(false);
182  break;
183 
184  case INETSTRAT_SUBEQ:
185  if (GIST_LEAF(ent) && gk_ip_minbits(key) < ip_bits(query))
186  PG_RETURN_BOOL(false);
187  break;
188 
189  case INETSTRAT_SUPEQ:
190  case INETSTRAT_EQ:
191  if (gk_ip_minbits(key) > ip_bits(query))
192  PG_RETURN_BOOL(false);
193  break;
194 
195  case INETSTRAT_SUP:
196  if (gk_ip_minbits(key) >= ip_bits(query))
197  PG_RETURN_BOOL(false);
198  break;
199  }
200 
201  /*
202  * Check 3: common network bits
203  *
204  * Compare available common prefix bits to the query, but not beyond
205  * either the query's netmask or the minimum netmask among the represented
206  * values. If these bits don't match the query, we have our answer (and
207  * may or may not need to descend, depending on the operator). If they do
208  * match, and we are not at a leaf, we descend in all cases.
209  *
210  * Note this is the final check for operators that only consider the
211  * network part of the address.
212  */
213  minbits = Min(gk_ip_commonbits(key), gk_ip_minbits(key));
214  minbits = Min(minbits, ip_bits(query));
215 
216  order = bitncmp(gk_ip_addr(key), ip_addr(query), minbits);
217 
218  switch (strategy)
219  {
220  case INETSTRAT_SUB:
221  case INETSTRAT_SUBEQ:
222  case INETSTRAT_OVERLAPS:
223  case INETSTRAT_SUPEQ:
224  case INETSTRAT_SUP:
225  PG_RETURN_BOOL(order == 0);
226 
227  case INETSTRAT_LT:
228  case INETSTRAT_LE:
229  if (order > 0)
230  PG_RETURN_BOOL(false);
231  if (order < 0 || !GIST_LEAF(ent))
232  PG_RETURN_BOOL(true);
233  break;
234 
235  case INETSTRAT_EQ:
236  if (order != 0)
237  PG_RETURN_BOOL(false);
238  if (!GIST_LEAF(ent))
239  PG_RETURN_BOOL(true);
240  break;
241 
242  case INETSTRAT_GE:
243  case INETSTRAT_GT:
244  if (order < 0)
245  PG_RETURN_BOOL(false);
246  if (order > 0 || !GIST_LEAF(ent))
247  PG_RETURN_BOOL(true);
248  break;
249 
250  case INETSTRAT_NE:
251  if (order != 0 || !GIST_LEAF(ent))
252  PG_RETURN_BOOL(true);
253  break;
254  }
255 
256  /*
257  * Remaining checks are only for leaves and basic comparison strategies.
258  * See network_cmp_internal() in network.c for the implementation we need
259  * to match. Note that in a leaf key, commonbits should equal the address
260  * length, so we compared the whole network parts above.
261  */
262  Assert(GIST_LEAF(ent));
263 
264  /*
265  * Check 4: network bit count
266  *
267  * Next step is to compare netmask widths.
268  */
269  switch (strategy)
270  {
271  case INETSTRAT_LT:
272  case INETSTRAT_LE:
273  if (gk_ip_minbits(key) < ip_bits(query))
274  PG_RETURN_BOOL(true);
275  if (gk_ip_minbits(key) > ip_bits(query))
276  PG_RETURN_BOOL(false);
277  break;
278 
279  case INETSTRAT_EQ:
280  if (gk_ip_minbits(key) != ip_bits(query))
281  PG_RETURN_BOOL(false);
282  break;
283 
284  case INETSTRAT_GE:
285  case INETSTRAT_GT:
286  if (gk_ip_minbits(key) > ip_bits(query))
287  PG_RETURN_BOOL(true);
288  if (gk_ip_minbits(key) < ip_bits(query))
289  PG_RETURN_BOOL(false);
290  break;
291 
292  case INETSTRAT_NE:
293  if (gk_ip_minbits(key) != ip_bits(query))
294  PG_RETURN_BOOL(true);
295  break;
296  }
297 
298  /*
299  * Check 5: whole address
300  *
301  * Netmask bit counts are the same, so check all the address bits.
302  */
303  order = bitncmp(gk_ip_addr(key), ip_addr(query), gk_ip_maxbits(key));
304 
305  switch (strategy)
306  {
307  case INETSTRAT_LT:
308  PG_RETURN_BOOL(order < 0);
309 
310  case INETSTRAT_LE:
311  PG_RETURN_BOOL(order <= 0);
312 
313  case INETSTRAT_EQ:
314  PG_RETURN_BOOL(order == 0);
315 
316  case INETSTRAT_GE:
317  PG_RETURN_BOOL(order >= 0);
318 
319  case INETSTRAT_GT:
320  PG_RETURN_BOOL(order > 0);
321 
322  case INETSTRAT_NE:
323  PG_RETURN_BOOL(order != 0);
324  }
325 
326  elog(ERROR, "unknown strategy for inet GiST");
327  PG_RETURN_BOOL(false); /* keep compiler quiet */
328 }
329 
330 /*
331  * Calculate parameters of the union of some GistInetKeys.
332  *
333  * Examine the keys in elements m..n inclusive of the GISTENTRY array,
334  * and compute these output parameters:
335  * *minfamily_p = minimum IP address family number
336  * *maxfamily_p = maximum IP address family number
337  * *minbits_p = minimum netmask width
338  * *commonbits_p = number of leading bits in common among the addresses
339  *
340  * minbits and commonbits are forced to zero if there's more than one
341  * address family.
342  */
343 static void
345  int m, int n,
346  int *minfamily_p,
347  int *maxfamily_p,
348  int *minbits_p,
349  int *commonbits_p)
350 {
351  int minfamily,
352  maxfamily,
353  minbits,
354  commonbits;
355  unsigned char *addr;
356  GistInetKey *tmp;
357  int i;
358 
359  /* Must be at least one key. */
360  Assert(m <= n);
361 
362  /* Initialize variables using the first key. */
363  tmp = DatumGetInetKeyP(ent[m].key);
364  minfamily = maxfamily = gk_ip_family(tmp);
365  minbits = gk_ip_minbits(tmp);
366  commonbits = gk_ip_commonbits(tmp);
367  addr = gk_ip_addr(tmp);
368 
369  /* Scan remaining keys. */
370  for (i = m + 1; i <= n; i++)
371  {
372  tmp = DatumGetInetKeyP(ent[i].key);
373 
374  /* Determine range of family numbers */
375  if (minfamily > gk_ip_family(tmp))
376  minfamily = gk_ip_family(tmp);
377  if (maxfamily < gk_ip_family(tmp))
378  maxfamily = gk_ip_family(tmp);
379 
380  /* Find minimum minbits */
381  if (minbits > gk_ip_minbits(tmp))
382  minbits = gk_ip_minbits(tmp);
383 
384  /* Find minimum number of bits in common */
385  if (commonbits > gk_ip_commonbits(tmp))
386  commonbits = gk_ip_commonbits(tmp);
387  if (commonbits > 0)
388  commonbits = bitncommon(addr, gk_ip_addr(tmp), commonbits);
389  }
390 
391  /* Force minbits/commonbits to zero if more than one family. */
392  if (minfamily != maxfamily)
393  minbits = commonbits = 0;
394 
395  *minfamily_p = minfamily;
396  *maxfamily_p = maxfamily;
397  *minbits_p = minbits;
398  *commonbits_p = commonbits;
399 }
400 
401 /*
402  * Same as above, but the GISTENTRY elements to examine are those with
403  * indices listed in the offsets[] array.
404  */
405 static void
407  OffsetNumber *offsets, int noffsets,
408  int *minfamily_p,
409  int *maxfamily_p,
410  int *minbits_p,
411  int *commonbits_p)
412 {
413  int minfamily,
414  maxfamily,
415  minbits,
416  commonbits;
417  unsigned char *addr;
418  GistInetKey *tmp;
419  int i;
420 
421  /* Must be at least one key. */
422  Assert(noffsets > 0);
423 
424  /* Initialize variables using the first key. */
425  tmp = DatumGetInetKeyP(ent[offsets[0]].key);
426  minfamily = maxfamily = gk_ip_family(tmp);
427  minbits = gk_ip_minbits(tmp);
428  commonbits = gk_ip_commonbits(tmp);
429  addr = gk_ip_addr(tmp);
430 
431  /* Scan remaining keys. */
432  for (i = 1; i < noffsets; i++)
433  {
434  tmp = DatumGetInetKeyP(ent[offsets[i]].key);
435 
436  /* Determine range of family numbers */
437  if (minfamily > gk_ip_family(tmp))
438  minfamily = gk_ip_family(tmp);
439  if (maxfamily < gk_ip_family(tmp))
440  maxfamily = gk_ip_family(tmp);
441 
442  /* Find minimum minbits */
443  if (minbits > gk_ip_minbits(tmp))
444  minbits = gk_ip_minbits(tmp);
445 
446  /* Find minimum number of bits in common */
447  if (commonbits > gk_ip_commonbits(tmp))
448  commonbits = gk_ip_commonbits(tmp);
449  if (commonbits > 0)
450  commonbits = bitncommon(addr, gk_ip_addr(tmp), commonbits);
451  }
452 
453  /* Force minbits/commonbits to zero if more than one family. */
454  if (minfamily != maxfamily)
455  minbits = commonbits = 0;
456 
457  *minfamily_p = minfamily;
458  *maxfamily_p = maxfamily;
459  *minbits_p = minbits;
460  *commonbits_p = commonbits;
461 }
462 
463 /*
464  * Construct a GistInetKey representing a union value.
465  *
466  * Inputs are the family/minbits/commonbits values to use, plus a pointer to
467  * the address field of one of the union inputs. (Since we're going to copy
468  * just the bits-in-common, it doesn't matter which one.)
469  */
470 static GistInetKey *
471 build_inet_union_key(int family, int minbits, int commonbits,
472  unsigned char *addr)
473 {
475 
476  /* Make sure any unused bits are zeroed. */
477  result = (GistInetKey *) palloc0(sizeof(GistInetKey));
478 
479  gk_ip_family(result) = family;
480  gk_ip_minbits(result) = minbits;
481  gk_ip_commonbits(result) = commonbits;
482 
483  /* Clone appropriate bytes of the address. */
484  if (commonbits > 0)
485  memcpy(gk_ip_addr(result), addr, (commonbits + 7) / 8);
486 
487  /* Clean any unwanted bits in the last partial byte. */
488  if (commonbits % 8 != 0)
489  gk_ip_addr(result)[commonbits / 8] &= ~(0xFF >> (commonbits % 8));
490 
491  /* Set varlena header correctly. */
492  SET_GK_VARSIZE(result);
493 
494  return result;
495 }
496 
497 
498 /*
499  * The GiST union function
500  *
501  * See comments at head of file for the definition of the union.
502  */
503 Datum
505 {
507  GISTENTRY *ent = entryvec->vector;
508  int minfamily,
509  maxfamily,
510  minbits,
511  commonbits;
512  unsigned char *addr;
513  GistInetKey *tmp,
514  *result;
515 
516  /* Determine parameters of the union. */
517  calc_inet_union_params(ent, 0, entryvec->n - 1,
518  &minfamily, &maxfamily,
519  &minbits, &commonbits);
520 
521  /* If more than one family, emit family number zero. */
522  if (minfamily != maxfamily)
523  minfamily = 0;
524 
525  /* Initialize address using the first key. */
526  tmp = DatumGetInetKeyP(ent[0].key);
527  addr = gk_ip_addr(tmp);
528 
529  /* Construct the union value. */
530  result = build_inet_union_key(minfamily, minbits, commonbits, addr);
531 
532  PG_RETURN_POINTER(result);
533 }
534 
535 /*
536  * The GiST compress function
537  *
538  * Convert an inet value to GistInetKey.
539  */
540 Datum
542 {
543  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
544  GISTENTRY *retval;
545 
546  if (entry->leafkey)
547  {
548  retval = palloc(sizeof(GISTENTRY));
549  if (DatumGetPointer(entry->key) != NULL)
550  {
551  inet *in = DatumGetInetPP(entry->key);
552  GistInetKey *r;
553 
554  r = (GistInetKey *) palloc0(sizeof(GistInetKey));
555 
556  gk_ip_family(r) = ip_family(in);
557  gk_ip_minbits(r) = ip_bits(in);
559  memcpy(gk_ip_addr(r), ip_addr(in), gk_ip_addrsize(r));
560  SET_GK_VARSIZE(r);
561 
562  gistentryinit(*retval, PointerGetDatum(r),
563  entry->rel, entry->page,
564  entry->offset, FALSE);
565  }
566  else
567  {
568  gistentryinit(*retval, (Datum) 0,
569  entry->rel, entry->page,
570  entry->offset, FALSE);
571  }
572  }
573  else
574  retval = entry;
575  PG_RETURN_POINTER(retval);
576 }
577 
578 /*
579  * The GiST decompress function
580  *
581  * do not do anything --- we just use the stored GistInetKey as-is.
582  */
583 Datum
585 {
586  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
587 
588  PG_RETURN_POINTER(entry);
589 }
590 
591 /*
592  * The GiST fetch function
593  *
594  * Reconstruct the original inet datum from a GistInetKey.
595  */
596 Datum
598 {
599  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
600  GistInetKey *key = DatumGetInetKeyP(entry->key);
601  GISTENTRY *retval;
602  inet *dst;
603 
604  dst = (inet *) palloc0(sizeof(inet));
605 
606  ip_family(dst) = gk_ip_family(key);
607  ip_bits(dst) = gk_ip_minbits(key);
608  memcpy(ip_addr(dst), gk_ip_addr(key), ip_addrsize(dst));
609  SET_INET_VARSIZE(dst);
610 
611  retval = palloc(sizeof(GISTENTRY));
612  gistentryinit(*retval, InetPGetDatum(dst), entry->rel, entry->page,
613  entry->offset, FALSE);
614 
615  PG_RETURN_POINTER(retval);
616 }
617 
618 /*
619  * The GiST page split penalty function
620  *
621  * Charge a large penalty if address family doesn't match, or a somewhat
622  * smaller one if the new value would degrade the union's minbits
623  * (minimum netmask width). Otherwise, penalty is inverse of the
624  * new number of common address bits.
625  */
626 Datum
628 {
629  GISTENTRY *origent = (GISTENTRY *) PG_GETARG_POINTER(0);
630  GISTENTRY *newent = (GISTENTRY *) PG_GETARG_POINTER(1);
631  float *penalty = (float *) PG_GETARG_POINTER(2);
632  GistInetKey *orig = DatumGetInetKeyP(origent->key),
633  *new = DatumGetInetKeyP(newent->key);
634  int commonbits;
635 
636  if (gk_ip_family(orig) == gk_ip_family(new))
637  {
638  if (gk_ip_minbits(orig) <= gk_ip_minbits(new))
639  {
640  commonbits = bitncommon(gk_ip_addr(orig), gk_ip_addr(new),
641  Min(gk_ip_commonbits(orig),
642  gk_ip_commonbits(new)));
643  if (commonbits > 0)
644  *penalty = 1.0f / commonbits;
645  else
646  *penalty = 2;
647  }
648  else
649  *penalty = 3;
650  }
651  else
652  *penalty = 4;
653 
654  PG_RETURN_POINTER(penalty);
655 }
656 
657 /*
658  * The GiST PickSplit method
659  *
660  * There are two ways to split. First one is to split by address families,
661  * if there are multiple families appearing in the input.
662  *
663  * The second and more common way is to split by addresses. To achieve this,
664  * determine the number of leading bits shared by all the keys, then split on
665  * the next bit. (We don't currently consider the netmask widths while doing
666  * this; should we?) If we fail to get a nontrivial split that way, split
667  * 50-50.
668  */
669 Datum
671 {
673  GIST_SPLITVEC *splitvec = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
674  GISTENTRY *ent = entryvec->vector;
675  int minfamily,
676  maxfamily,
677  minbits,
678  commonbits;
679  unsigned char *addr;
680  GistInetKey *tmp,
681  *left_union,
682  *right_union;
683  int maxoff,
684  nbytes;
685  OffsetNumber i,
686  *left,
687  *right;
688 
689  maxoff = entryvec->n - 1;
690  nbytes = (maxoff + 1) * sizeof(OffsetNumber);
691 
692  left = (OffsetNumber *) palloc(nbytes);
693  right = (OffsetNumber *) palloc(nbytes);
694 
695  splitvec->spl_left = left;
696  splitvec->spl_right = right;
697 
698  splitvec->spl_nleft = 0;
699  splitvec->spl_nright = 0;
700 
701  /* Determine parameters of the union of all the inputs. */
703  &minfamily, &maxfamily,
704  &minbits, &commonbits);
705 
706  if (minfamily != maxfamily)
707  {
708  /* Multiple families, so split by family. */
709  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
710  {
711  /*
712  * If there's more than 2 families, all but maxfamily go into the
713  * left union. This could only happen if the inputs include some
714  * IPv4, some IPv6, and some already-multiple-family unions.
715  */
716  tmp = DatumGetInetKeyP(ent[i].key);
717  if (gk_ip_family(tmp) != maxfamily)
718  left[splitvec->spl_nleft++] = i;
719  else
720  right[splitvec->spl_nright++] = i;
721  }
722  }
723  else
724  {
725  /*
726  * Split on the next bit after the common bits. If that yields a
727  * trivial split, try the next bit position to the right. Repeat till
728  * success; or if we run out of bits, do an arbitrary 50-50 split.
729  */
730  int maxbits = ip_family_maxbits(minfamily);
731 
732  while (commonbits < maxbits)
733  {
734  /* Split using the commonbits'th bit position. */
735  int bitbyte = commonbits / 8;
736  int bitmask = 0x80 >> (commonbits % 8);
737 
738  splitvec->spl_nleft = splitvec->spl_nright = 0;
739 
740  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
741  {
742  tmp = DatumGetInetKeyP(ent[i].key);
743  addr = gk_ip_addr(tmp);
744  if ((addr[bitbyte] & bitmask) == 0)
745  left[splitvec->spl_nleft++] = i;
746  else
747  right[splitvec->spl_nright++] = i;
748  }
749 
750  if (splitvec->spl_nleft > 0 && splitvec->spl_nright > 0)
751  break; /* success */
752  commonbits++;
753  }
754 
755  if (commonbits >= maxbits)
756  {
757  /* Failed ... do a 50-50 split. */
758  splitvec->spl_nleft = splitvec->spl_nright = 0;
759 
760  for (i = FirstOffsetNumber; i <= maxoff / 2; i = OffsetNumberNext(i))
761  {
762  left[splitvec->spl_nleft++] = i;
763  }
764  for (; i <= maxoff; i = OffsetNumberNext(i))
765  {
766  right[splitvec->spl_nright++] = i;
767  }
768  }
769  }
770 
771  /*
772  * Compute the union value for each side from scratch. In most cases we
773  * could approximate the union values with what we already know, but this
774  * ensures that each side has minbits and commonbits set as high as
775  * possible.
776  */
777  calc_inet_union_params_indexed(ent, left, splitvec->spl_nleft,
778  &minfamily, &maxfamily,
779  &minbits, &commonbits);
780  if (minfamily != maxfamily)
781  minfamily = 0;
782  tmp = DatumGetInetKeyP(ent[left[0]].key);
783  addr = gk_ip_addr(tmp);
784  left_union = build_inet_union_key(minfamily, minbits, commonbits, addr);
785  splitvec->spl_ldatum = PointerGetDatum(left_union);
786 
787  calc_inet_union_params_indexed(ent, right, splitvec->spl_nright,
788  &minfamily, &maxfamily,
789  &minbits, &commonbits);
790  if (minfamily != maxfamily)
791  minfamily = 0;
792  tmp = DatumGetInetKeyP(ent[right[0]].key);
793  addr = gk_ip_addr(tmp);
794  right_union = build_inet_union_key(minfamily, minbits, commonbits, addr);
795  splitvec->spl_rdatum = PointerGetDatum(right_union);
796 
797  PG_RETURN_POINTER(splitvec);
798 }
799 
800 /*
801  * The GiST equality function
802  */
803 Datum
805 {
808  bool *result = (bool *) PG_GETARG_POINTER(2);
809 
810  *result = (gk_ip_family(left) == gk_ip_family(right) &&
811  gk_ip_minbits(left) == gk_ip_minbits(right) &&
812  gk_ip_commonbits(left) == gk_ip_commonbits(right) &&
813  memcmp(gk_ip_addr(left), gk_ip_addr(right),
814  gk_ip_addrsize(left)) == 0);
815 
816  PG_RETURN_POINTER(result);
817 }
#define GIST_LEAF(entry)
Definition: gist.h:133
Relation rel
Definition: gist.h:124
Datum inet_gist_same(PG_FUNCTION_ARGS)
Definition: network_gist.c:804
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
Datum inet_gist_fetch(PG_FUNCTION_ARGS)
Definition: network_gist.c:597
struct GistInetKey GistInetKey
#define INETSTRAT_SUPEQ
Definition: network_gist.c:68
Datum inet_gist_compress(PG_FUNCTION_ARGS)
Definition: network_gist.c:541
#define ip_bits(inetptr)
Definition: inet.h:74
#define SET_GK_VARSIZE(dst)
Definition: network_gist.c:106
unsigned char commonbits
Definition: network_gist.c:83
#define ip_family(inetptr)
Definition: inet.h:71
#define INETSTRAT_SUBEQ
Definition: network_gist.c:66
#define gk_ip_maxbits(gkptr)
Definition: network_gist.c:104
#define PointerGetDatum(X)
Definition: postgres.h:562
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:233
#define DatumGetInetPP(X)
Definition: inet.h:122
#define INETSTRAT_OVERLAPS
Definition: network_gist.c:58
static void calc_inet_union_params(GISTENTRY *ent, int m, int n, int *minfamily_p, int *maxfamily_p, int *minbits_p, int *commonbits_p)
Definition: network_gist.c:344
#define ip_addr(inetptr)
Definition: inet.h:77
#define ip_family_maxbits(fam)
Definition: network_gist.c:99
#define Min(x, y)
Definition: c.h:806
#define SET_INET_VARSIZE(dst)
Definition: inet.h:86
OffsetNumber * spl_left
Definition: gist.h:105
Datum spl_rdatum
Definition: gist.h:112
unsigned char uint8
Definition: c.h:266
int bitncommon(const unsigned char *l, const unsigned char *r, int n)
Definition: network.c:1004
int32 n
Definition: gist.h:160
uint16 StrategyNumber
Definition: stratnum.h:22
return result
Definition: formatting.c:1633
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define INETSTRAT_LT
Definition: network_gist.c:61
#define ip_addrsize(inetptr)
Definition: inet.h:80
int spl_nleft
Definition: gist.h:106
#define INETSTRAT_SUB
Definition: network_gist.c:65
unsigned char minbits
Definition: network_gist.c:82
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:125
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
Datum inet_gist_union(PG_FUNCTION_ARGS)
Definition: network_gist.c:504
Datum inet_gist_penalty(PG_FUNCTION_ARGS)
Definition: network_gist.c:627
#define ERROR
Definition: elog.h:43
uint8 va_header
Definition: network_gist.c:80
#define gk_ip_addr(gkptr)
Definition: network_gist.c:98
#define FALSE
Definition: c.h:221
int spl_nright
Definition: gist.h:111
Datum key
Definition: gist.h:123
#define PG_GETARG_INET_PP(n)
Definition: inet.h:124
#define FirstOffsetNumber
Definition: off.h:27
Definition: inet.h:52
Datum inet_gist_picksplit(PG_FUNCTION_ARGS)
Definition: network_gist.c:670
static GistInetKey * build_inet_union_key(int family, int minbits, int commonbits, unsigned char *addr)
Definition: network_gist.c:471
#define DatumGetInetKeyP(X)
Definition: network_gist.c:87
#define INETSTRAT_GE
Definition: network_gist.c:64
bool leafkey
Definition: gist.h:127
static void calc_inet_union_params_indexed(GISTENTRY *ent, OffsetNumber *offsets, int noffsets, int *minfamily_p, int *maxfamily_p, int *minbits_p, int *commonbits_p)
Definition: network_gist.c:406
#define InetPGetDatum(X)
Definition: inet.h:123
void * palloc0(Size size)
Definition: mcxt.c:878
#define INETSTRAT_NE
Definition: network_gist.c:60
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:319
#define gk_ip_family(gkptr)
Definition: network_gist.c:95
uintptr_t Datum
Definition: postgres.h:372
Datum inet_gist_decompress(PG_FUNCTION_ARGS)
Definition: network_gist.c:584
#define gk_ip_commonbits(gkptr)
Definition: network_gist.c:97
Datum spl_ldatum
Definition: gist.h:107
#define NULL
Definition: c.h:229
#define INETSTRAT_LE
Definition: network_gist.c:62
#define Assert(condition)
Definition: c.h:675
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:169
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
OffsetNumber * spl_right
Definition: gist.h:110
#define INETSTRAT_GT
Definition: network_gist.c:63
unsigned char family
Definition: network_gist.c:81
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:237
#define DatumGetPointer(X)
Definition: postgres.h:555
#define INETSTRAT_EQ
Definition: network_gist.c:59
void * palloc(Size size)
Definition: mcxt.c:849
int bitncmp(const unsigned char *l, const unsigned char *r, int n)
Definition: network.c:970
int i
#define gk_ip_addrsize(gkptr)
Definition: network_gist.c:102
Datum inet_gist_consistent(PG_FUNCTION_ARGS)
Definition: network_gist.c:114
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
unsigned char ipaddr[16]
Definition: network_gist.c:84
#define elog
Definition: elog.h:219
OffsetNumber offset
Definition: gist.h:126
#define gk_ip_minbits(gkptr)
Definition: network_gist.c:96
#define INETSTRAT_SUP
Definition: network_gist.c:67