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-2018, 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
inet_gist_consistent(PG_FUNCTION_ARGS)114 inet_gist_consistent(PG_FUNCTION_ARGS)
115 {
116 GISTENTRY *ent = (GISTENTRY *) PG_GETARG_POINTER(0);
117 inet *query = PG_GETARG_INET_PP(1);
118 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
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
calc_inet_union_params(GISTENTRY * ent,int m,int n,int * minfamily_p,int * maxfamily_p,int * minbits_p,int * commonbits_p)344 calc_inet_union_params(GISTENTRY *ent,
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
calc_inet_union_params_indexed(GISTENTRY * ent,OffsetNumber * offsets,int noffsets,int * minfamily_p,int * maxfamily_p,int * minbits_p,int * commonbits_p)406 calc_inet_union_params_indexed(GISTENTRY *ent,
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 *
build_inet_union_key(int family,int minbits,int commonbits,unsigned char * addr)471 build_inet_union_key(int family, int minbits, int commonbits,
472 unsigned char *addr)
473 {
474 GistInetKey *result;
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
inet_gist_union(PG_FUNCTION_ARGS)504 inet_gist_union(PG_FUNCTION_ARGS)
505 {
506 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
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
inet_gist_compress(PG_FUNCTION_ARGS)541 inet_gist_compress(PG_FUNCTION_ARGS)
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);
558 gk_ip_commonbits(r) = gk_ip_maxbits(r);
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 * We do not need a decompress function, because the other GiST inet
580 * support functions work with the GistInetKey representation.
581 */
582
583 /*
584 * The GiST fetch function
585 *
586 * Reconstruct the original inet datum from a GistInetKey.
587 */
588 Datum
inet_gist_fetch(PG_FUNCTION_ARGS)589 inet_gist_fetch(PG_FUNCTION_ARGS)
590 {
591 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
592 GistInetKey *key = DatumGetInetKeyP(entry->key);
593 GISTENTRY *retval;
594 inet *dst;
595
596 dst = (inet *) palloc0(sizeof(inet));
597
598 ip_family(dst) = gk_ip_family(key);
599 ip_bits(dst) = gk_ip_minbits(key);
600 memcpy(ip_addr(dst), gk_ip_addr(key), ip_addrsize(dst));
601 SET_INET_VARSIZE(dst);
602
603 retval = palloc(sizeof(GISTENTRY));
604 gistentryinit(*retval, InetPGetDatum(dst), entry->rel, entry->page,
605 entry->offset, false);
606
607 PG_RETURN_POINTER(retval);
608 }
609
610 /*
611 * The GiST page split penalty function
612 *
613 * Charge a large penalty if address family doesn't match, or a somewhat
614 * smaller one if the new value would degrade the union's minbits
615 * (minimum netmask width). Otherwise, penalty is inverse of the
616 * new number of common address bits.
617 */
618 Datum
inet_gist_penalty(PG_FUNCTION_ARGS)619 inet_gist_penalty(PG_FUNCTION_ARGS)
620 {
621 GISTENTRY *origent = (GISTENTRY *) PG_GETARG_POINTER(0);
622 GISTENTRY *newent = (GISTENTRY *) PG_GETARG_POINTER(1);
623 float *penalty = (float *) PG_GETARG_POINTER(2);
624 GistInetKey *orig = DatumGetInetKeyP(origent->key),
625 *new = DatumGetInetKeyP(newent->key);
626 int commonbits;
627
628 if (gk_ip_family(orig) == gk_ip_family(new))
629 {
630 if (gk_ip_minbits(orig) <= gk_ip_minbits(new))
631 {
632 commonbits = bitncommon(gk_ip_addr(orig), gk_ip_addr(new),
633 Min(gk_ip_commonbits(orig),
634 gk_ip_commonbits(new)));
635 if (commonbits > 0)
636 *penalty = 1.0f / commonbits;
637 else
638 *penalty = 2;
639 }
640 else
641 *penalty = 3;
642 }
643 else
644 *penalty = 4;
645
646 PG_RETURN_POINTER(penalty);
647 }
648
649 /*
650 * The GiST PickSplit method
651 *
652 * There are two ways to split. First one is to split by address families,
653 * if there are multiple families appearing in the input.
654 *
655 * The second and more common way is to split by addresses. To achieve this,
656 * determine the number of leading bits shared by all the keys, then split on
657 * the next bit. (We don't currently consider the netmask widths while doing
658 * this; should we?) If we fail to get a nontrivial split that way, split
659 * 50-50.
660 */
661 Datum
inet_gist_picksplit(PG_FUNCTION_ARGS)662 inet_gist_picksplit(PG_FUNCTION_ARGS)
663 {
664 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
665 GIST_SPLITVEC *splitvec = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
666 GISTENTRY *ent = entryvec->vector;
667 int minfamily,
668 maxfamily,
669 minbits,
670 commonbits;
671 unsigned char *addr;
672 GistInetKey *tmp,
673 *left_union,
674 *right_union;
675 int maxoff,
676 nbytes;
677 OffsetNumber i,
678 *left,
679 *right;
680
681 maxoff = entryvec->n - 1;
682 nbytes = (maxoff + 1) * sizeof(OffsetNumber);
683
684 left = (OffsetNumber *) palloc(nbytes);
685 right = (OffsetNumber *) palloc(nbytes);
686
687 splitvec->spl_left = left;
688 splitvec->spl_right = right;
689
690 splitvec->spl_nleft = 0;
691 splitvec->spl_nright = 0;
692
693 /* Determine parameters of the union of all the inputs. */
694 calc_inet_union_params(ent, FirstOffsetNumber, maxoff,
695 &minfamily, &maxfamily,
696 &minbits, &commonbits);
697
698 if (minfamily != maxfamily)
699 {
700 /* Multiple families, so split by family. */
701 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
702 {
703 /*
704 * If there's more than 2 families, all but maxfamily go into the
705 * left union. This could only happen if the inputs include some
706 * IPv4, some IPv6, and some already-multiple-family unions.
707 */
708 tmp = DatumGetInetKeyP(ent[i].key);
709 if (gk_ip_family(tmp) != maxfamily)
710 left[splitvec->spl_nleft++] = i;
711 else
712 right[splitvec->spl_nright++] = i;
713 }
714 }
715 else
716 {
717 /*
718 * Split on the next bit after the common bits. If that yields a
719 * trivial split, try the next bit position to the right. Repeat till
720 * success; or if we run out of bits, do an arbitrary 50-50 split.
721 */
722 int maxbits = ip_family_maxbits(minfamily);
723
724 while (commonbits < maxbits)
725 {
726 /* Split using the commonbits'th bit position. */
727 int bitbyte = commonbits / 8;
728 int bitmask = 0x80 >> (commonbits % 8);
729
730 splitvec->spl_nleft = splitvec->spl_nright = 0;
731
732 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
733 {
734 tmp = DatumGetInetKeyP(ent[i].key);
735 addr = gk_ip_addr(tmp);
736 if ((addr[bitbyte] & bitmask) == 0)
737 left[splitvec->spl_nleft++] = i;
738 else
739 right[splitvec->spl_nright++] = i;
740 }
741
742 if (splitvec->spl_nleft > 0 && splitvec->spl_nright > 0)
743 break; /* success */
744 commonbits++;
745 }
746
747 if (commonbits >= maxbits)
748 {
749 /* Failed ... do a 50-50 split. */
750 splitvec->spl_nleft = splitvec->spl_nright = 0;
751
752 for (i = FirstOffsetNumber; i <= maxoff / 2; i = OffsetNumberNext(i))
753 {
754 left[splitvec->spl_nleft++] = i;
755 }
756 for (; i <= maxoff; i = OffsetNumberNext(i))
757 {
758 right[splitvec->spl_nright++] = i;
759 }
760 }
761 }
762
763 /*
764 * Compute the union value for each side from scratch. In most cases we
765 * could approximate the union values with what we already know, but this
766 * ensures that each side has minbits and commonbits set as high as
767 * possible.
768 */
769 calc_inet_union_params_indexed(ent, left, splitvec->spl_nleft,
770 &minfamily, &maxfamily,
771 &minbits, &commonbits);
772 if (minfamily != maxfamily)
773 minfamily = 0;
774 tmp = DatumGetInetKeyP(ent[left[0]].key);
775 addr = gk_ip_addr(tmp);
776 left_union = build_inet_union_key(minfamily, minbits, commonbits, addr);
777 splitvec->spl_ldatum = PointerGetDatum(left_union);
778
779 calc_inet_union_params_indexed(ent, right, splitvec->spl_nright,
780 &minfamily, &maxfamily,
781 &minbits, &commonbits);
782 if (minfamily != maxfamily)
783 minfamily = 0;
784 tmp = DatumGetInetKeyP(ent[right[0]].key);
785 addr = gk_ip_addr(tmp);
786 right_union = build_inet_union_key(minfamily, minbits, commonbits, addr);
787 splitvec->spl_rdatum = PointerGetDatum(right_union);
788
789 PG_RETURN_POINTER(splitvec);
790 }
791
792 /*
793 * The GiST equality function
794 */
795 Datum
inet_gist_same(PG_FUNCTION_ARGS)796 inet_gist_same(PG_FUNCTION_ARGS)
797 {
798 GistInetKey *left = DatumGetInetKeyP(PG_GETARG_DATUM(0));
799 GistInetKey *right = DatumGetInetKeyP(PG_GETARG_DATUM(1));
800 bool *result = (bool *) PG_GETARG_POINTER(2);
801
802 *result = (gk_ip_family(left) == gk_ip_family(right) &&
803 gk_ip_minbits(left) == gk_ip_minbits(right) &&
804 gk_ip_commonbits(left) == gk_ip_commonbits(right) &&
805 memcmp(gk_ip_addr(left), gk_ip_addr(right),
806 gk_ip_addrsize(left)) == 0);
807
808 PG_RETURN_POINTER(result);
809 }
810