| 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-2025, 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/fmgrprotos.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 |
inet_gist_consistent(PG_FUNCTION_ARGS) |
| 116 |
{ |
| 117 |
GISTENTRY *ent = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 118 |
inet *query = PG_GETARG_INET_PP(1); |
| 119 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 120 |
|
| 121 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 122 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 123 |
GistInetKey *key = DatumGetInetKeyP(ent->key); |
| 124 |
int minbits, |
| 125 |
order; |
| 126 |
|
| 127 |
/* All operators served by this function are exact. */ |
| 128 |
*recheck = false; |
| 129 |
|
| 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 |
if (gk_ip_family(key) == 0) |
| 137 |
{ |
| 138 |
Assert(!GIST_LEAF(ent)); |
| 139 |
PG_RETURN_BOOL(true); |
| 140 |
} |
| 141 |
|
| 142 |
/* |
| 143 |
* Check 1: different families |
| 144 |
* |
| 145 |
* Matching families do not help any of the strategies. |
| 146 |
*/ |
| 147 |
if (gk_ip_family(key) != ip_family(query)) |
| 148 |
{ |
| 149 |
switch (strategy) |
| 150 |
{ |
| 151 |
case INETSTRAT_LT: |
| 152 |
case INETSTRAT_LE: |
| 153 |
if (gk_ip_family(key) < ip_family(query)) |
| 154 |
PG_RETURN_BOOL(true); |
| 155 |
break; |
| 156 |
|
| 157 |
case INETSTRAT_GE: |
| 158 |
case INETSTRAT_GT: |
| 159 |
if (gk_ip_family(key) > ip_family(query)) |
| 160 |
PG_RETURN_BOOL(true); |
| 161 |
break; |
| 162 |
|
| 163 |
case INETSTRAT_NE: |
| 164 |
PG_RETURN_BOOL(true); |
| 165 |
} |
| 166 |
/* For all other cases, we can be sure there is no match */ |
| 167 |
PG_RETURN_BOOL(false); |
| 168 |
} |
| 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 |
switch (strategy) |
| 179 |
{ |
| 180 |
case INETSTRAT_SUB: |
| 181 |
if (GIST_LEAF(ent) && gk_ip_minbits(key) <= ip_bits(query)) |
| 182 |
PG_RETURN_BOOL(false); |
| 183 |
break; |
| 184 |
|
| 185 |
case INETSTRAT_SUBEQ: |
| 186 |
if (GIST_LEAF(ent) && gk_ip_minbits(key) < ip_bits(query)) |
| 187 |
PG_RETURN_BOOL(false); |
| 188 |
break; |
| 189 |
|
| 190 |
case INETSTRAT_SUPEQ: |
| 191 |
case INETSTRAT_EQ: |
| 192 |
if (gk_ip_minbits(key) > ip_bits(query)) |
| 193 |
PG_RETURN_BOOL(false); |
| 194 |
break; |
| 195 |
|
| 196 |
case INETSTRAT_SUP: |
| 197 |
if (gk_ip_minbits(key) >= ip_bits(query)) |
| 198 |
PG_RETURN_BOOL(false); |
| 199 |
break; |
| 200 |
} |
| 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 |
minbits = Min(gk_ip_commonbits(key), gk_ip_minbits(key)); |
| 215 |
minbits = Min(minbits, ip_bits(query)); |
| 216 |
|
| 217 |
order = bitncmp(gk_ip_addr(key), ip_addr(query), minbits); |
| 218 |
|
| 219 |
switch (strategy) |
| 220 |
{ |
| 221 |
case INETSTRAT_SUB: |
| 222 |
case INETSTRAT_SUBEQ: |
| 223 |
case INETSTRAT_OVERLAPS: |
| 224 |
case INETSTRAT_SUPEQ: |
| 225 |
case INETSTRAT_SUP: |
| 226 |
PG_RETURN_BOOL(order == 0); |
| 227 |
|
| 228 |
case INETSTRAT_LT: |
| 229 |
case INETSTRAT_LE: |
| 230 |
if (order > 0) |
| 231 |
PG_RETURN_BOOL(false); |
| 232 |
if (order < 0 || !GIST_LEAF(ent)) |
| 233 |
PG_RETURN_BOOL(true); |
| 234 |
break; |
| 235 |
|
| 236 |
case INETSTRAT_EQ: |
| 237 |
if (order != 0) |
| 238 |
PG_RETURN_BOOL(false); |
| 239 |
if (!GIST_LEAF(ent)) |
| 240 |
PG_RETURN_BOOL(true); |
| 241 |
break; |
| 242 |
|
| 243 |
case INETSTRAT_GE: |
| 244 |
case INETSTRAT_GT: |
| 245 |
if (order < 0) |
| 246 |
PG_RETURN_BOOL(false); |
| 247 |
if (order > 0 || !GIST_LEAF(ent)) |
| 248 |
PG_RETURN_BOOL(true); |
| 249 |
break; |
| 250 |
|
| 251 |
case INETSTRAT_NE: |
| 252 |
if (order != 0 || !GIST_LEAF(ent)) |
| 253 |
PG_RETURN_BOOL(true); |
| 254 |
break; |
| 255 |
} |
| 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 |
Assert(GIST_LEAF(ent)); |
| 264 |
|
| 265 |
/* |
| 266 |
* Check 4: network bit count |
| 267 |
* |
| 268 |
* Next step is to compare netmask widths. |
| 269 |
*/ |
| 270 |
switch (strategy) |
| 271 |
{ |
| 272 |
case INETSTRAT_LT: |
| 273 |
case INETSTRAT_LE: |
| 274 |
if (gk_ip_minbits(key) < ip_bits(query)) |
| 275 |
PG_RETURN_BOOL(true); |
| 276 |
if (gk_ip_minbits(key) > ip_bits(query)) |
| 277 |
PG_RETURN_BOOL(false); |
| 278 |
break; |
| 279 |
|
| 280 |
case INETSTRAT_EQ: |
| 281 |
if (gk_ip_minbits(key) != ip_bits(query)) |
| 282 |
PG_RETURN_BOOL(false); |
| 283 |
break; |
| 284 |
|
| 285 |
case INETSTRAT_GE: |
| 286 |
case INETSTRAT_GT: |
| 287 |
if (gk_ip_minbits(key) > ip_bits(query)) |
| 288 |
PG_RETURN_BOOL(true); |
| 289 |
if (gk_ip_minbits(key) < ip_bits(query)) |
| 290 |
PG_RETURN_BOOL(false); |
| 291 |
break; |
| 292 |
|
| 293 |
case INETSTRAT_NE: |
| 294 |
if (gk_ip_minbits(key) != ip_bits(query)) |
| 295 |
PG_RETURN_BOOL(true); |
| 296 |
break; |
| 297 |
} |
| 298 |
|
| 299 |
/* |
| 300 |
* Check 5: whole address |
| 301 |
* |
| 302 |
* Netmask bit counts are the same, so check all the address bits. |
| 303 |
*/ |
| 304 |
order = bitncmp(gk_ip_addr(key), ip_addr(query), gk_ip_maxbits(key)); |
| 305 |
|
| 306 |
switch (strategy) |
| 307 |
{ |
| 308 |
case INETSTRAT_LT: |
| 309 |
PG_RETURN_BOOL(order < 0); |
| 310 |
|
| 311 |
case INETSTRAT_LE: |
| 312 |
PG_RETURN_BOOL(order <= 0); |
| 313 |
|
| 314 |
case INETSTRAT_EQ: |
| 315 |
PG_RETURN_BOOL(order == 0); |
| 316 |
|
| 317 |
case INETSTRAT_GE: |
| 318 |
PG_RETURN_BOOL(order >= 0); |
| 319 |
|
| 320 |
case INETSTRAT_GT: |
| 321 |
PG_RETURN_BOOL(order > 0); |
| 322 |
|
| 323 |
case INETSTRAT_NE: |
| 324 |
PG_RETURN_BOOL(order != 0); |
| 325 |
} |
| 326 |
|
| 327 |
elog(ERROR, "unknown strategy for inet GiST"); |
| 328 |
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 |
calc_inet_union_params(GISTENTRY *ent, |
| 346 |
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 |
Assert(m <= n); |
| 362 |
|
| 363 |
/* Initialize variables using the first key. */ |
| 364 |
tmp = DatumGetInetKeyP(ent[m].key); |
| 365 |
minfamily = maxfamily = gk_ip_family(tmp); |
| 366 |
minbits = gk_ip_minbits(tmp); |
| 367 |
commonbits = gk_ip_commonbits(tmp); |
| 368 |
addr = gk_ip_addr(tmp); |
| 369 |
|
| 370 |
/* Scan remaining keys. */ |
| 371 |
for (i = m + 1; i <= n; i++) |
| 372 |
{ |
| 373 |
tmp = DatumGetInetKeyP(ent[i].key); |
| 374 |
|
| 375 |
/* Determine range of family numbers */ |
| 376 |
if (minfamily > gk_ip_family(tmp)) |
| 377 |
minfamily = gk_ip_family(tmp); |
| 378 |
if (maxfamily < gk_ip_family(tmp)) |
| 379 |
maxfamily = gk_ip_family(tmp); |
| 380 |
|
| 381 |
/* Find minimum minbits */ |
| 382 |
if (minbits > gk_ip_minbits(tmp)) |
| 383 |
minbits = gk_ip_minbits(tmp); |
| 384 |
|
| 385 |
/* Find minimum number of bits in common */ |
| 386 |
if (commonbits > gk_ip_commonbits(tmp)) |
| 387 |
commonbits = gk_ip_commonbits(tmp); |
| 388 |
if (commonbits > 0) |
| 389 |
commonbits = bitncommon(addr, gk_ip_addr(tmp), commonbits); |
| 390 |
} |
| 391 |
|
| 392 |
/* Force minbits/commonbits to zero if more than one family. */ |
| 393 |
if (minfamily != maxfamily) |
| 394 |
minbits = commonbits = 0; |
| 395 |
|
| 396 |
*minfamily_p = minfamily; |
| 397 |
*maxfamily_p = maxfamily; |
| 398 |
*minbits_p = minbits; |
| 399 |
*commonbits_p = commonbits; |
| 400 |
} |
| 401 |
|
| 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 |
calc_inet_union_params_indexed(GISTENTRY *ent, |
| 408 |
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 |
Assert(noffsets > 0); |
| 424 |
|
| 425 |
/* Initialize variables using the first key. */ |
| 426 |
tmp = DatumGetInetKeyP(ent[offsets[0]].key); |
| 427 |
minfamily = maxfamily = gk_ip_family(tmp); |
| 428 |
minbits = gk_ip_minbits(tmp); |
| 429 |
commonbits = gk_ip_commonbits(tmp); |
| 430 |
addr = gk_ip_addr(tmp); |
| 431 |
|
| 432 |
/* Scan remaining keys. */ |
| 433 |
for (i = 1; i < noffsets; i++) |
| 434 |
{ |
| 435 |
tmp = DatumGetInetKeyP(ent[offsets[i]].key); |
| 436 |
|
| 437 |
/* Determine range of family numbers */ |
| 438 |
if (minfamily > gk_ip_family(tmp)) |
| 439 |
minfamily = gk_ip_family(tmp); |
| 440 |
if (maxfamily < gk_ip_family(tmp)) |
| 441 |
maxfamily = gk_ip_family(tmp); |
| 442 |
|
| 443 |
/* Find minimum minbits */ |
| 444 |
if (minbits > gk_ip_minbits(tmp)) |
| 445 |
minbits = gk_ip_minbits(tmp); |
| 446 |
|
| 447 |
/* Find minimum number of bits in common */ |
| 448 |
if (commonbits > gk_ip_commonbits(tmp)) |
| 449 |
commonbits = gk_ip_commonbits(tmp); |
| 450 |
if (commonbits > 0) |
| 451 |
commonbits = bitncommon(addr, gk_ip_addr(tmp), commonbits); |
| 452 |
} |
| 453 |
|
| 454 |
/* Force minbits/commonbits to zero if more than one family. */ |
| 455 |
if (minfamily != maxfamily) |
| 456 |
minbits = commonbits = 0; |
| 457 |
|
| 458 |
*minfamily_p = minfamily; |
| 459 |
*maxfamily_p = maxfamily; |
| 460 |
*minbits_p = minbits; |
| 461 |
*commonbits_p = commonbits; |
| 462 |
} |
| 463 |
|
| 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 |
build_inet_union_key(int family, int minbits, int commonbits, |
| 473 |
unsigned char *addr) |
| 474 |
{ |
| 475 |
GistInetKey *result; |
| 476 |
|
| 477 |
/* Make sure any unused bits are zeroed. */ |
| 478 |
result = (GistInetKey *) palloc0(sizeof(GistInetKey)); |
| 479 |
|
| 480 |
gk_ip_family(result) = family; |
| 481 |
gk_ip_minbits(result) = minbits; |
| 482 |
gk_ip_commonbits(result) = commonbits; |
| 483 |
|
| 484 |
/* Clone appropriate bytes of the address. */ |
| 485 |
if (commonbits > 0) |
| 486 |
memcpy(gk_ip_addr(result), addr, (commonbits + 7) / 8); |
| 487 |
|
| 488 |
/* Clean any unwanted bits in the last partial byte. */ |
| 489 |
if (commonbits % 8 != 0) |
| 490 |
gk_ip_addr(result)[commonbits / 8] &= ~(0xFF >> (commonbits % 8)); |
| 491 |
|
| 492 |
/* Set varlena header correctly. */ |
| 493 |
SET_GK_VARSIZE(result); |
| 494 |
|
| 495 |
return result; |
| 496 |
} |
| 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 |
inet_gist_union(PG_FUNCTION_ARGS) |
| 506 |
{ |
| 507 |
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); |
| 508 |
GISTENTRY *ent = entryvec->vector; |
| 509 |
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 |
calc_inet_union_params(ent, 0, entryvec->n - 1, |
| 519 |
&minfamily, &maxfamily, |
| 520 |
&minbits, &commonbits); |
| 521 |
|
| 522 |
/* If more than one family, emit family number zero. */ |
| 523 |
if (minfamily != maxfamily) |
| 524 |
minfamily = 0; |
| 525 |
|
| 526 |
/* Initialize address using the first key. */ |
| 527 |
tmp = DatumGetInetKeyP(ent[0].key); |
| 528 |
addr = gk_ip_addr(tmp); |
| 529 |
|
| 530 |
/* Construct the union value. */ |
| 531 |
result = build_inet_union_key(minfamily, minbits, commonbits, addr); |
| 532 |
|
| 533 |
PG_RETURN_POINTER(result); |
| 534 |
} |
| 535 |
|
| 536 |
/* |
| 537 |
* The GiST compress function |
| 538 |
* |
| 539 |
* Convert an inet value to GistInetKey. |
| 540 |
*/ |
| 541 |
Datum |
| 542 |
inet_gist_compress(PG_FUNCTION_ARGS) |
| 543 |
{ |
| 544 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 545 |
GISTENTRY *retval; |
| 546 |
|
| 547 |
if (entry->leafkey) |
| 548 |
{ |
| 549 |
retval = palloc(sizeof(GISTENTRY)); |
| 550 |
if (DatumGetPointer(entry->key) != NULL) |
| 551 |
{ |
| 552 |
inet *in = DatumGetInetPP(entry->key); |
| 553 |
GistInetKey *r; |
| 554 |
|
| 555 |
r = (GistInetKey *) palloc0(sizeof(GistInetKey)); |
| 556 |
|
| 557 |
gk_ip_family(r) = ip_family(in); |
| 558 |
gk_ip_minbits(r) = ip_bits(in); |
| 559 |
gk_ip_commonbits(r) = gk_ip_maxbits(r); |
| 560 |
memcpy(gk_ip_addr(r), ip_addr(in), gk_ip_addrsize(r)); |
| 561 |
SET_GK_VARSIZE(r); |
| 562 |
|
| 563 |
gistentryinit(*retval, PointerGetDatum(r), |
| 564 |
entry->rel, entry->page, |
| 565 |
entry->offset, false); |
| 566 |
} |
| 567 |
else |
| 568 |
{ |
| 569 |
gistentryinit(*retval, (Datum) 0, |
| 570 |
entry->rel, entry->page, |
| 571 |
entry->offset, false); |
| 572 |
} |
| 573 |
} |
| 574 |
else |
| 575 |
retval = entry; |
| 576 |
PG_RETURN_POINTER(retval); |
| 577 |
} |
| 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 |
inet_gist_fetch(PG_FUNCTION_ARGS) |
| 591 |
{ |
| 592 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 593 |
GistInetKey *key = DatumGetInetKeyP(entry->key); |
| 594 |
GISTENTRY *retval; |
| 595 |
inet *dst; |
| 596 |
|
| 597 |
dst = (inet *) palloc0(sizeof(inet)); |
| 598 |
|
| 599 |
ip_family(dst) = gk_ip_family(key); |
| 600 |
ip_bits(dst) = gk_ip_minbits(key); |
| 601 |
memcpy(ip_addr(dst), gk_ip_addr(key), ip_addrsize(dst)); |
| 602 |
SET_INET_VARSIZE(dst); |
| 603 |
|
| 604 |
retval = palloc(sizeof(GISTENTRY)); |
| 605 |
gistentryinit(*retval, InetPGetDatum(dst), entry->rel, entry->page, |
| 606 |
entry->offset, false); |
| 607 |
|
| 608 |
PG_RETURN_POINTER(retval); |
| 609 |
} |
| 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 |
inet_gist_penalty(PG_FUNCTION_ARGS) |
| 621 |
{ |
| 622 |
GISTENTRY *origent = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 623 |
GISTENTRY *newent = (GISTENTRY *) PG_GETARG_POINTER(1); |
| 624 |
float *penalty = (float *) PG_GETARG_POINTER(2); |
| 625 |
GistInetKey *orig = DatumGetInetKeyP(origent->key), |
| 626 |
*new = DatumGetInetKeyP(newent->key); |
| 627 |
int commonbits; |
| 628 |
|
| 629 |
if (gk_ip_family(orig) == gk_ip_family(new)) |
| 630 |
{ |
| 631 |
if (gk_ip_minbits(orig) <= gk_ip_minbits(new)) |
| 632 |
{ |
| 633 |
commonbits = bitncommon(gk_ip_addr(orig), gk_ip_addr(new), |
| 634 |
Min(gk_ip_commonbits(orig), |
| 635 |
gk_ip_commonbits(new))); |
| 636 |
if (commonbits > 0) |
| 637 |
*penalty = 1.0f / commonbits; |
| 638 |
else |
| 639 |
*penalty = 2; |
| 640 |
} |
| 641 |
else |
| 642 |
*penalty = 3; |
| 643 |
} |
| 644 |
else |
| 645 |
*penalty = 4; |
| 646 |
|
| 647 |
PG_RETURN_POINTER(penalty); |
| 648 |
} |
| 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 |
inet_gist_picksplit(PG_FUNCTION_ARGS) |
| 664 |
{ |
| 665 |
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); |
| 666 |
GIST_SPLITVEC *splitvec = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); |
| 667 |
GISTENTRY *ent = entryvec->vector; |
| 668 |
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 |
maxoff = entryvec->n - 1; |
| 683 |
nbytes = (maxoff + 1) * sizeof(OffsetNumber); |
| 684 |
|
| 685 |
left = (OffsetNumber *) palloc(nbytes); |
| 686 |
right = (OffsetNumber *) palloc(nbytes); |
| 687 |
|
| 688 |
splitvec->spl_left = left; |
| 689 |
splitvec->spl_right = right; |
| 690 |
|
| 691 |
splitvec->spl_nleft = 0; |
| 692 |
splitvec->spl_nright = 0; |
| 693 |
|
| 694 |
/* Determine parameters of the union of all the inputs. */ |
| 695 |
calc_inet_union_params(ent, FirstOffsetNumber, maxoff, |
| 696 |
&minfamily, &maxfamily, |
| 697 |
&minbits, &commonbits); |
| 698 |
|
| 699 |
if (minfamily != maxfamily) |
| 700 |
{ |
| 701 |
/* Multiple families, so split by family. */ |
| 702 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 703 |
{ |
| 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 |
tmp = DatumGetInetKeyP(ent[i].key); |
| 710 |
if (gk_ip_family(tmp) != maxfamily) |
| 711 |
left[splitvec->spl_nleft++] = i; |
| 712 |
else |
| 713 |
right[splitvec->spl_nright++] = i; |
| 714 |
} |
| 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 |
int maxbits = ip_family_maxbits(minfamily); |
| 724 |
|
| 725 |
while (commonbits < maxbits) |
| 726 |
{ |
| 727 |
/* Split using the commonbits'th bit position. */ |
| 728 |
int bitbyte = commonbits / 8; |
| 729 |
int bitmask = 0x80 >> (commonbits % 8); |
| 730 |
|
| 731 |
splitvec->spl_nleft = splitvec->spl_nright = 0; |
| 732 |
|
| 733 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 734 |
{ |
| 735 |
tmp = DatumGetInetKeyP(ent[i].key); |
| 736 |
addr = gk_ip_addr(tmp); |
| 737 |
if ((addr[bitbyte] & bitmask) == 0) |
| 738 |
left[splitvec->spl_nleft++] = i; |
| 739 |
else |
| 740 |
right[splitvec->spl_nright++] = i; |
| 741 |
} |
| 742 |
|
| 743 |
if (splitvec->spl_nleft > 0 && splitvec->spl_nright > 0) |
| 744 |
break; /* success */ |
| 745 |
commonbits++; |
| 746 |
} |
| 747 |
|
| 748 |
if (commonbits >= maxbits) |
| 749 |
{ |
| 750 |
/* Failed ... do a 50-50 split. */ |
| 751 |
splitvec->spl_nleft = splitvec->spl_nright = 0; |
| 752 |
|
| 753 |
for (i = FirstOffsetNumber; i <= maxoff / 2; i = OffsetNumberNext(i)) |
| 754 |
{ |
| 755 |
left[splitvec->spl_nleft++] = i; |
| 756 |
} |
| 757 |
for (; i <= maxoff; i = OffsetNumberNext(i)) |
| 758 |
{ |
| 759 |
right[splitvec->spl_nright++] = i; |
| 760 |
} |
| 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 |
calc_inet_union_params_indexed(ent, left, splitvec->spl_nleft, |
| 771 |
&minfamily, &maxfamily, |
| 772 |
&minbits, &commonbits); |
| 773 |
if (minfamily != maxfamily) |
| 774 |
minfamily = 0; |
| 775 |
tmp = DatumGetInetKeyP(ent[left[0]].key); |
| 776 |
addr = gk_ip_addr(tmp); |
| 777 |
left_union = build_inet_union_key(minfamily, minbits, commonbits, addr); |
| 778 |
splitvec->spl_ldatum = PointerGetDatum(left_union); |
| 779 |
|
| 780 |
calc_inet_union_params_indexed(ent, right, splitvec->spl_nright, |
| 781 |
&minfamily, &maxfamily, |
| 782 |
&minbits, &commonbits); |
| 783 |
if (minfamily != maxfamily) |
| 784 |
minfamily = 0; |
| 785 |
tmp = DatumGetInetKeyP(ent[right[0]].key); |
| 786 |
addr = gk_ip_addr(tmp); |
| 787 |
right_union = build_inet_union_key(minfamily, minbits, commonbits, addr); |
| 788 |
splitvec->spl_rdatum = PointerGetDatum(right_union); |
| 789 |
|
| 790 |
PG_RETURN_POINTER(splitvec); |
| 791 |
} |
| 792 |
|
| 793 |
/* |
| 794 |
* The GiST equality function |
| 795 |
*/ |
| 796 |
Datum |
| 797 |
inet_gist_same(PG_FUNCTION_ARGS) |
| 798 |
{ |
| 799 |
GistInetKey *left = DatumGetInetKeyP(PG_GETARG_DATUM(0)); |
| 800 |
GistInetKey *right = DatumGetInetKeyP(PG_GETARG_DATUM(1)); |
| 801 |
bool *result = (bool *) PG_GETARG_POINTER(2); |
| 802 |
|
| 803 |
*result = (gk_ip_family(left) == gk_ip_family(right) && |
| 804 |
gk_ip_minbits(left) == gk_ip_minbits(right) && |
| 805 |
gk_ip_commonbits(left) == gk_ip_commonbits(right) && |
| 806 |
memcmp(gk_ip_addr(left), gk_ip_addr(right), |
| 807 |
gk_ip_addrsize(left)) == 0); |
| 808 |
|
| 809 |
PG_RETURN_POINTER(result); |
| 810 |
} |