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