Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * gistproc.c
4 : : * Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
5 : : * points).
6 : : *
7 : : * This gives R-tree behavior, with Guttman's poly-time split algorithm.
8 : : *
9 : : *
10 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
11 : : * Portions Copyright (c) 1994, Regents of the University of California
12 : : *
13 : : * IDENTIFICATION
14 : : * src/backend/access/gist/gistproc.c
15 : : *
16 : : *-------------------------------------------------------------------------
17 : : */
18 : : #include "postgres.h"
19 : :
20 : : #include <math.h>
21 : :
22 : : #include "access/gist.h"
23 : : #include "access/stratnum.h"
24 : : #include "utils/float.h"
25 : : #include "utils/fmgrprotos.h"
26 : : #include "utils/geo_decls.h"
27 : : #include "utils/sortsupport.h"
28 : :
29 : :
30 : : static bool gist_box_leaf_consistent(BOX *key, BOX *query,
31 : : StrategyNumber strategy);
32 : : static bool rtree_internal_consistent(BOX *key, BOX *query,
33 : : StrategyNumber strategy);
34 : :
35 : : static uint64 point_zorder_internal(float4 x, float4 y);
36 : : static uint64 part_bits32_by2(uint32 x);
37 : : static uint32 ieee_float32_to_uint32(float f);
38 : : static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup);
39 : : static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup);
40 : : static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup);
41 : :
42 : :
43 : : /* Minimum accepted ratio of split */
44 : : #define LIMIT_RATIO 0.3
45 : :
46 : :
47 : : /**************************************************
48 : : * Box ops
49 : : **************************************************/
50 : :
51 : : /*
52 : : * Calculates union of two boxes, a and b. The result is stored in *n.
53 : : */
54 : : static void
55 : 0 : rt_box_union(BOX *n, const BOX *a, const BOX *b)
56 : : {
57 : 0 : n->high.x = float8_max(a->high.x, b->high.x);
58 : 0 : n->high.y = float8_max(a->high.y, b->high.y);
59 : 0 : n->low.x = float8_min(a->low.x, b->low.x);
60 : 0 : n->low.y = float8_min(a->low.y, b->low.y);
61 : 0 : }
62 : :
63 : : /*
64 : : * Size of a BOX for penalty-calculation purposes.
65 : : * The result can be +Infinity, but not NaN.
66 : : */
67 : : static float8
68 : 0 : size_box(const BOX *box)
69 : : {
70 : : /*
71 : : * Check for zero-width cases. Note that we define the size of a zero-
72 : : * by-infinity box as zero. It's important to special-case this somehow,
73 : : * as naively multiplying infinity by zero will produce NaN.
74 : : *
75 : : * The less-than cases should not happen, but if they do, say "zero".
76 : : */
77 [ # # # # ]: 0 : if (float8_le(box->high.x, box->low.x) ||
78 : 0 : float8_le(box->high.y, box->low.y))
79 : 0 : return 0.0;
80 : :
81 : : /*
82 : : * We treat NaN as larger than +Infinity, so any distance involving a NaN
83 : : * and a non-NaN is infinite. Note the previous check eliminated the
84 : : * possibility that the low fields are NaNs.
85 : : */
86 [ # # # # : 0 : if (isnan(box->high.x) || isnan(box->high.y))
# # # # #
# # # ]
87 : 0 : return get_float8_infinity();
88 : 0 : return float8_mul(float8_mi(box->high.x, box->low.x),
89 : 0 : float8_mi(box->high.y, box->low.y));
90 : 0 : }
91 : :
92 : : /*
93 : : * Return amount by which the union of the two boxes is larger than
94 : : * the original BOX's area. The result can be +Infinity, but not NaN.
95 : : */
96 : : static float8
97 : 0 : box_penalty(const BOX *original, const BOX *new)
98 : : {
99 : 0 : BOX unionbox;
100 : :
101 : 0 : rt_box_union(&unionbox, original, new);
102 : 0 : return float8_mi(size_box(&unionbox), size_box(original));
103 : 0 : }
104 : :
105 : : /*
106 : : * The GiST Consistent method for boxes
107 : : *
108 : : * Should return false if for all data items x below entry,
109 : : * the predicate x op query must be false, where op is the oper
110 : : * corresponding to strategy in the pg_amop table.
111 : : */
112 : : Datum
113 : 1361 : gist_box_consistent(PG_FUNCTION_ARGS)
114 : : {
115 : 1361 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
116 : 1361 : BOX *query = PG_GETARG_BOX_P(1);
117 : 1361 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
118 : : #ifdef NOT_USED
119 : : Oid subtype = PG_GETARG_OID(3);
120 : : #endif
121 : 1361 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
122 : :
123 : : /* All cases served by this function are exact */
124 : 1361 : *recheck = false;
125 : :
126 [ + - - + ]: 1361 : if (DatumGetBoxP(entry->key) == NULL || query == NULL)
127 : 0 : PG_RETURN_BOOL(false);
128 : :
129 : : /*
130 : : * if entry is not leaf, use rtree_internal_consistent, else use
131 : : * gist_box_leaf_consistent
132 : : */
133 [ + + ]: 1361 : if (GIST_LEAF(entry))
134 : 782 : PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
135 : : query,
136 : : strategy));
137 : : else
138 : 579 : PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
139 : : query,
140 : : strategy));
141 : 1361 : }
142 : :
143 : : /*
144 : : * Increase BOX b to include addon.
145 : : */
146 : : static void
147 : 0 : adjustBox(BOX *b, const BOX *addon)
148 : : {
149 [ # # ]: 0 : if (float8_lt(b->high.x, addon->high.x))
150 : 0 : b->high.x = addon->high.x;
151 [ # # ]: 0 : if (float8_gt(b->low.x, addon->low.x))
152 : 0 : b->low.x = addon->low.x;
153 [ # # ]: 0 : if (float8_lt(b->high.y, addon->high.y))
154 : 0 : b->high.y = addon->high.y;
155 [ # # ]: 0 : if (float8_gt(b->low.y, addon->low.y))
156 : 0 : b->low.y = addon->low.y;
157 : 0 : }
158 : :
159 : : /*
160 : : * The GiST Union method for boxes
161 : : *
162 : : * returns the minimal bounding box that encloses all the entries in entryvec
163 : : */
164 : : Datum
165 : 0 : gist_box_union(PG_FUNCTION_ARGS)
166 : : {
167 : 0 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
168 : 0 : int *sizep = (int *) PG_GETARG_POINTER(1);
169 : 0 : int numranges,
170 : : i;
171 : 0 : BOX *cur,
172 : : *pageunion;
173 : :
174 : 0 : numranges = entryvec->n;
175 : 0 : pageunion = palloc_object(BOX);
176 : 0 : cur = DatumGetBoxP(entryvec->vector[0].key);
177 : 0 : memcpy(pageunion, cur, sizeof(BOX));
178 : :
179 [ # # ]: 0 : for (i = 1; i < numranges; i++)
180 : : {
181 : 0 : cur = DatumGetBoxP(entryvec->vector[i].key);
182 : 0 : adjustBox(pageunion, cur);
183 : 0 : }
184 : 0 : *sizep = sizeof(BOX);
185 : :
186 : 0 : PG_RETURN_POINTER(pageunion);
187 : 0 : }
188 : :
189 : : /*
190 : : * We store boxes as boxes in GiST indexes, so we do not need
191 : : * compress, decompress, or fetch functions.
192 : : */
193 : :
194 : : /*
195 : : * The GiST Penalty method for boxes (also used for points)
196 : : *
197 : : * As in the R-tree paper, we use change in area as our penalty metric
198 : : */
199 : : Datum
200 : 0 : gist_box_penalty(PG_FUNCTION_ARGS)
201 : : {
202 : 0 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
203 : 0 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
204 : 0 : float *result = (float *) PG_GETARG_POINTER(2);
205 : 0 : BOX *origbox = DatumGetBoxP(origentry->key);
206 : 0 : BOX *newbox = DatumGetBoxP(newentry->key);
207 : :
208 : 0 : *result = (float) box_penalty(origbox, newbox);
209 : 0 : PG_RETURN_POINTER(result);
210 : 0 : }
211 : :
212 : : /*
213 : : * Trivial split: half of entries will be placed on one page
214 : : * and another half - to another
215 : : */
216 : : static void
217 : 0 : fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
218 : : {
219 : 0 : OffsetNumber i,
220 : : maxoff;
221 : 0 : BOX *unionL = NULL,
222 : 0 : *unionR = NULL;
223 : 0 : int nbytes;
224 : :
225 : 0 : maxoff = entryvec->n - 1;
226 : :
227 : 0 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
228 : 0 : v->spl_left = (OffsetNumber *) palloc(nbytes);
229 : 0 : v->spl_right = (OffsetNumber *) palloc(nbytes);
230 : 0 : v->spl_nleft = v->spl_nright = 0;
231 : :
232 [ # # ]: 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
233 : : {
234 : 0 : BOX *cur = DatumGetBoxP(entryvec->vector[i].key);
235 : :
236 [ # # ]: 0 : if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
237 : : {
238 : 0 : v->spl_left[v->spl_nleft] = i;
239 [ # # ]: 0 : if (unionL == NULL)
240 : : {
241 : 0 : unionL = palloc_object(BOX);
242 : 0 : *unionL = *cur;
243 : 0 : }
244 : : else
245 : 0 : adjustBox(unionL, cur);
246 : :
247 : 0 : v->spl_nleft++;
248 : 0 : }
249 : : else
250 : : {
251 : 0 : v->spl_right[v->spl_nright] = i;
252 [ # # ]: 0 : if (unionR == NULL)
253 : : {
254 : 0 : unionR = palloc_object(BOX);
255 : 0 : *unionR = *cur;
256 : 0 : }
257 : : else
258 : 0 : adjustBox(unionR, cur);
259 : :
260 : 0 : v->spl_nright++;
261 : : }
262 : 0 : }
263 : :
264 : 0 : v->spl_ldatum = BoxPGetDatum(unionL);
265 : 0 : v->spl_rdatum = BoxPGetDatum(unionR);
266 : 0 : }
267 : :
268 : : /*
269 : : * Represents information about an entry that can be placed to either group
270 : : * without affecting overlap over selected axis ("common entry").
271 : : */
272 : : typedef struct
273 : : {
274 : : /* Index of entry in the initial array */
275 : : int index;
276 : : /* Delta between penalties of entry insertion into different groups */
277 : : float8 delta;
278 : : } CommonEntry;
279 : :
280 : : /*
281 : : * Context for g_box_consider_split. Contains information about currently
282 : : * selected split and some general information.
283 : : */
284 : : typedef struct
285 : : {
286 : : int entriesCount; /* total number of entries being split */
287 : : BOX boundingBox; /* minimum bounding box across all entries */
288 : :
289 : : /* Information about currently selected split follows */
290 : :
291 : : bool first; /* true if no split was selected yet */
292 : :
293 : : float8 leftUpper; /* upper bound of left interval */
294 : : float8 rightLower; /* lower bound of right interval */
295 : :
296 : : float4 ratio;
297 : : float4 overlap;
298 : : int dim; /* axis of this split */
299 : : float8 range; /* width of general MBR projection to the
300 : : * selected axis */
301 : : } ConsiderSplitContext;
302 : :
303 : : /*
304 : : * Interval represents projection of box to axis.
305 : : */
306 : : typedef struct
307 : : {
308 : : float8 lower,
309 : : upper;
310 : : } SplitInterval;
311 : :
312 : : /*
313 : : * Interval comparison function by lower bound of the interval;
314 : : */
315 : : static int
316 : 0 : interval_cmp_lower(const void *i1, const void *i2)
317 : : {
318 : 0 : float8 lower1 = ((const SplitInterval *) i1)->lower,
319 : 0 : lower2 = ((const SplitInterval *) i2)->lower;
320 : :
321 : 0 : return float8_cmp_internal(lower1, lower2);
322 : 0 : }
323 : :
324 : : /*
325 : : * Interval comparison function by upper bound of the interval;
326 : : */
327 : : static int
328 : 0 : interval_cmp_upper(const void *i1, const void *i2)
329 : : {
330 : 0 : float8 upper1 = ((const SplitInterval *) i1)->upper,
331 : 0 : upper2 = ((const SplitInterval *) i2)->upper;
332 : :
333 : 0 : return float8_cmp_internal(upper1, upper2);
334 : 0 : }
335 : :
336 : : /*
337 : : * Replace negative (or NaN) value with zero.
338 : : */
339 : : static inline float
340 : 0 : non_negative(float val)
341 : : {
342 [ # # ]: 0 : if (val >= 0.0f)
343 : 0 : return val;
344 : : else
345 : 0 : return 0.0f;
346 : 0 : }
347 : :
348 : : /*
349 : : * Consider replacement of currently selected split with the better one.
350 : : */
351 : : static inline void
352 : 0 : g_box_consider_split(ConsiderSplitContext *context, int dimNum,
353 : : float8 rightLower, int minLeftCount,
354 : : float8 leftUpper, int maxLeftCount)
355 : : {
356 : 0 : int leftCount,
357 : : rightCount;
358 : 0 : float4 ratio,
359 : : overlap;
360 : 0 : float8 range;
361 : :
362 : : /*
363 : : * Calculate entries distribution ratio assuming most uniform distribution
364 : : * of common entries.
365 : : */
366 [ # # ]: 0 : if (minLeftCount >= (context->entriesCount + 1) / 2)
367 : : {
368 : 0 : leftCount = minLeftCount;
369 : 0 : }
370 : : else
371 : : {
372 [ # # ]: 0 : if (maxLeftCount <= context->entriesCount / 2)
373 : 0 : leftCount = maxLeftCount;
374 : : else
375 : 0 : leftCount = context->entriesCount / 2;
376 : : }
377 : 0 : rightCount = context->entriesCount - leftCount;
378 : :
379 : : /*
380 : : * Ratio of split - quotient between size of lesser group and total
381 : : * entries count.
382 : : */
383 [ # # ]: 0 : ratio = float4_div(Min(leftCount, rightCount), context->entriesCount);
384 : :
385 [ # # ]: 0 : if (ratio > LIMIT_RATIO)
386 : : {
387 : 0 : bool selectthis = false;
388 : :
389 : : /*
390 : : * The ratio is acceptable, so compare current split with previously
391 : : * selected one. Between splits of one dimension we search for minimal
392 : : * overlap (allowing negative values) and minimal ration (between same
393 : : * overlaps. We switch dimension if find less overlap (non-negative)
394 : : * or less range with same overlap.
395 : : */
396 [ # # ]: 0 : if (dimNum == 0)
397 : 0 : range = float8_mi(context->boundingBox.high.x,
398 : 0 : context->boundingBox.low.x);
399 : : else
400 : 0 : range = float8_mi(context->boundingBox.high.y,
401 : 0 : context->boundingBox.low.y);
402 : :
403 : 0 : overlap = float8_div(float8_mi(leftUpper, rightLower), range);
404 : :
405 : : /* If there is no previous selection, select this */
406 [ # # ]: 0 : if (context->first)
407 : 0 : selectthis = true;
408 [ # # ]: 0 : else if (context->dim == dimNum)
409 : : {
410 : : /*
411 : : * Within the same dimension, choose the new split if it has a
412 : : * smaller overlap, or same overlap but better ratio.
413 : : */
414 [ # # # # ]: 0 : if (overlap < context->overlap ||
415 [ # # ]: 0 : (overlap == context->overlap && ratio > context->ratio))
416 : 0 : selectthis = true;
417 : 0 : }
418 : : else
419 : : {
420 : : /*
421 : : * Across dimensions, choose the new split if it has a smaller
422 : : * *non-negative* overlap, or same *non-negative* overlap but
423 : : * bigger range. This condition differs from the one described in
424 : : * the article. On the datasets where leaf MBRs don't overlap
425 : : * themselves, non-overlapping splits (i.e. splits which have zero
426 : : * *non-negative* overlap) are frequently possible. In this case
427 : : * splits tends to be along one dimension, because most distant
428 : : * non-overlapping splits (i.e. having lowest negative overlap)
429 : : * appears to be in the same dimension as in the previous split.
430 : : * Therefore MBRs appear to be very prolonged along another
431 : : * dimension, which leads to bad search performance. Using range
432 : : * as the second split criteria makes MBRs more quadratic. Using
433 : : * *non-negative* overlap instead of overlap as the first split
434 : : * criteria gives to range criteria a chance to matter, because
435 : : * non-overlapping splits are equivalent in this criteria.
436 : : */
437 [ # # # # ]: 0 : if (non_negative(overlap) < non_negative(context->overlap) ||
438 [ # # ]: 0 : (range > context->range &&
439 : 0 : non_negative(overlap) <= non_negative(context->overlap)))
440 : 0 : selectthis = true;
441 : : }
442 : :
443 [ # # ]: 0 : if (selectthis)
444 : : {
445 : : /* save information about selected split */
446 : 0 : context->first = false;
447 : 0 : context->ratio = ratio;
448 : 0 : context->range = range;
449 : 0 : context->overlap = overlap;
450 : 0 : context->rightLower = rightLower;
451 : 0 : context->leftUpper = leftUpper;
452 : 0 : context->dim = dimNum;
453 : 0 : }
454 : 0 : }
455 : 0 : }
456 : :
457 : : /*
458 : : * Compare common entries by their deltas.
459 : : */
460 : : static int
461 : 0 : common_entry_cmp(const void *i1, const void *i2)
462 : : {
463 : 0 : float8 delta1 = ((const CommonEntry *) i1)->delta,
464 : 0 : delta2 = ((const CommonEntry *) i2)->delta;
465 : :
466 : 0 : return float8_cmp_internal(delta1, delta2);
467 : 0 : }
468 : :
469 : : /*
470 : : * --------------------------------------------------------------------------
471 : : * Double sorting split algorithm. This is used for both boxes and points.
472 : : *
473 : : * The algorithm finds split of boxes by considering splits along each axis.
474 : : * Each entry is first projected as an interval on the X-axis, and different
475 : : * ways to split the intervals into two groups are considered, trying to
476 : : * minimize the overlap of the groups. Then the same is repeated for the
477 : : * Y-axis, and the overall best split is chosen. The quality of a split is
478 : : * determined by overlap along that axis and some other criteria (see
479 : : * g_box_consider_split).
480 : : *
481 : : * After that, all the entries are divided into three groups:
482 : : *
483 : : * 1) Entries which should be placed to the left group
484 : : * 2) Entries which should be placed to the right group
485 : : * 3) "Common entries" which can be placed to any of groups without affecting
486 : : * of overlap along selected axis.
487 : : *
488 : : * The common entries are distributed by minimizing penalty.
489 : : *
490 : : * For details see:
491 : : * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
492 : : * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
493 : : * --------------------------------------------------------------------------
494 : : */
495 : : Datum
496 : 0 : gist_box_picksplit(PG_FUNCTION_ARGS)
497 : : {
498 : 0 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
499 : 0 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
500 : 0 : OffsetNumber i,
501 : : maxoff;
502 : 0 : ConsiderSplitContext context;
503 : 0 : BOX *box,
504 : : *leftBox,
505 : : *rightBox;
506 : 0 : int dim,
507 : : commonEntriesCount;
508 : 0 : SplitInterval *intervalsLower,
509 : : *intervalsUpper;
510 : 0 : CommonEntry *commonEntries;
511 : 0 : int nentries;
512 : :
513 : 0 : memset(&context, 0, sizeof(ConsiderSplitContext));
514 : :
515 : 0 : maxoff = entryvec->n - 1;
516 : 0 : nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
517 : :
518 : : /* Allocate arrays for intervals along axes */
519 : 0 : intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
520 : 0 : intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
521 : :
522 : : /*
523 : : * Calculate the overall minimum bounding box over all the entries.
524 : : */
525 [ # # ]: 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
526 : : {
527 : 0 : box = DatumGetBoxP(entryvec->vector[i].key);
528 [ # # ]: 0 : if (i == FirstOffsetNumber)
529 : 0 : context.boundingBox = *box;
530 : : else
531 : 0 : adjustBox(&context.boundingBox, box);
532 : 0 : }
533 : :
534 : : /*
535 : : * Iterate over axes for optimal split searching.
536 : : */
537 : 0 : context.first = true; /* nothing selected yet */
538 [ # # ]: 0 : for (dim = 0; dim < 2; dim++)
539 : : {
540 : 0 : float8 leftUpper,
541 : : rightLower;
542 : 0 : int i1,
543 : : i2;
544 : :
545 : : /* Project each entry as an interval on the selected axis. */
546 [ # # ]: 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
547 : : {
548 : 0 : box = DatumGetBoxP(entryvec->vector[i].key);
549 [ # # ]: 0 : if (dim == 0)
550 : : {
551 : 0 : intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
552 : 0 : intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
553 : 0 : }
554 : : else
555 : : {
556 : 0 : intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
557 : 0 : intervalsLower[i - FirstOffsetNumber].upper = box->high.y;
558 : : }
559 : 0 : }
560 : :
561 : : /*
562 : : * Make two arrays of intervals: one sorted by lower bound and another
563 : : * sorted by upper bound.
564 : : */
565 : 0 : memcpy(intervalsUpper, intervalsLower,
566 : : sizeof(SplitInterval) * nentries);
567 : 0 : qsort(intervalsLower, nentries, sizeof(SplitInterval),
568 : : interval_cmp_lower);
569 : 0 : qsort(intervalsUpper, nentries, sizeof(SplitInterval),
570 : : interval_cmp_upper);
571 : :
572 : : /*----
573 : : * The goal is to form a left and right interval, so that every entry
574 : : * interval is contained by either left or right interval (or both).
575 : : *
576 : : * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
577 : : *
578 : : * 0 1 2 3 4
579 : : * +-+
580 : : * +---+
581 : : * +-+
582 : : * +---+
583 : : *
584 : : * The left and right intervals are of the form (0,a) and (b,4).
585 : : * We first consider splits where b is the lower bound of an entry.
586 : : * We iterate through all entries, and for each b, calculate the
587 : : * smallest possible a. Then we consider splits where a is the
588 : : * upper bound of an entry, and for each a, calculate the greatest
589 : : * possible b.
590 : : *
591 : : * In the above example, the first loop would consider splits:
592 : : * b=0: (0,1)-(0,4)
593 : : * b=1: (0,1)-(1,4)
594 : : * b=2: (0,3)-(2,4)
595 : : *
596 : : * And the second loop:
597 : : * a=1: (0,1)-(1,4)
598 : : * a=3: (0,3)-(2,4)
599 : : * a=4: (0,4)-(2,4)
600 : : */
601 : :
602 : : /*
603 : : * Iterate over lower bound of right group, finding smallest possible
604 : : * upper bound of left group.
605 : : */
606 : 0 : i1 = 0;
607 : 0 : i2 = 0;
608 : 0 : rightLower = intervalsLower[i1].lower;
609 : 0 : leftUpper = intervalsUpper[i2].lower;
610 : 0 : while (true)
611 : : {
612 : : /*
613 : : * Find next lower bound of right group.
614 : : */
615 [ # # # # ]: 0 : while (i1 < nentries &&
616 : 0 : float8_eq(rightLower, intervalsLower[i1].lower))
617 : : {
618 [ # # ]: 0 : if (float8_lt(leftUpper, intervalsLower[i1].upper))
619 : 0 : leftUpper = intervalsLower[i1].upper;
620 : 0 : i1++;
621 : : }
622 [ # # ]: 0 : if (i1 >= nentries)
623 : 0 : break;
624 : 0 : rightLower = intervalsLower[i1].lower;
625 : :
626 : : /*
627 : : * Find count of intervals which anyway should be placed to the
628 : : * left group.
629 : : */
630 [ # # # # ]: 0 : while (i2 < nentries &&
631 : 0 : float8_le(intervalsUpper[i2].upper, leftUpper))
632 : 0 : i2++;
633 : :
634 : : /*
635 : : * Consider found split.
636 : : */
637 : 0 : g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
638 : : }
639 : :
640 : : /*
641 : : * Iterate over upper bound of left group finding greatest possible
642 : : * lower bound of right group.
643 : : */
644 : 0 : i1 = nentries - 1;
645 : 0 : i2 = nentries - 1;
646 : 0 : rightLower = intervalsLower[i1].upper;
647 : 0 : leftUpper = intervalsUpper[i2].upper;
648 : 0 : while (true)
649 : : {
650 : : /*
651 : : * Find next upper bound of left group.
652 : : */
653 [ # # # # ]: 0 : while (i2 >= 0 && float8_eq(leftUpper, intervalsUpper[i2].upper))
654 : : {
655 [ # # ]: 0 : if (float8_gt(rightLower, intervalsUpper[i2].lower))
656 : 0 : rightLower = intervalsUpper[i2].lower;
657 : 0 : i2--;
658 : : }
659 [ # # ]: 0 : if (i2 < 0)
660 : 0 : break;
661 : 0 : leftUpper = intervalsUpper[i2].upper;
662 : :
663 : : /*
664 : : * Find count of intervals which anyway should be placed to the
665 : : * right group.
666 : : */
667 [ # # # # ]: 0 : while (i1 >= 0 && float8_ge(intervalsLower[i1].lower, rightLower))
668 : 0 : i1--;
669 : :
670 : : /*
671 : : * Consider found split.
672 : : */
673 : 0 : g_box_consider_split(&context, dim,
674 : 0 : rightLower, i1 + 1, leftUpper, i2 + 1);
675 : : }
676 : 0 : }
677 : :
678 : : /*
679 : : * If we failed to find any acceptable splits, use trivial split.
680 : : */
681 [ # # ]: 0 : if (context.first)
682 : : {
683 : 0 : fallbackSplit(entryvec, v);
684 : 0 : PG_RETURN_POINTER(v);
685 : : }
686 : :
687 : : /*
688 : : * Ok, we have now selected the split across one axis.
689 : : *
690 : : * While considering the splits, we already determined that there will be
691 : : * enough entries in both groups to reach the desired ratio, but we did
692 : : * not memorize which entries go to which group. So determine that now.
693 : : */
694 : :
695 : : /* Allocate vectors for results */
696 : 0 : v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
697 : 0 : v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
698 : 0 : v->spl_nleft = 0;
699 : 0 : v->spl_nright = 0;
700 : :
701 : : /* Allocate bounding boxes of left and right groups */
702 : 0 : leftBox = palloc0_object(BOX);
703 : 0 : rightBox = palloc0_object(BOX);
704 : :
705 : : /*
706 : : * Allocate an array for "common entries" - entries which can be placed to
707 : : * either group without affecting overlap along selected axis.
708 : : */
709 : 0 : commonEntriesCount = 0;
710 : 0 : commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
711 : :
712 : : /* Helper macros to place an entry in the left or right group */
713 : : #define PLACE_LEFT(box, off) \
714 : : do { \
715 : : if (v->spl_nleft > 0) \
716 : : adjustBox(leftBox, box); \
717 : : else \
718 : : *leftBox = *(box); \
719 : : v->spl_left[v->spl_nleft++] = off; \
720 : : } while(0)
721 : :
722 : : #define PLACE_RIGHT(box, off) \
723 : : do { \
724 : : if (v->spl_nright > 0) \
725 : : adjustBox(rightBox, box); \
726 : : else \
727 : : *rightBox = *(box); \
728 : : v->spl_right[v->spl_nright++] = off; \
729 : : } while(0)
730 : :
731 : : /*
732 : : * Distribute entries which can be distributed unambiguously, and collect
733 : : * common entries.
734 : : */
735 [ # # ]: 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
736 : : {
737 : 0 : float8 lower,
738 : : upper;
739 : :
740 : : /*
741 : : * Get upper and lower bounds along selected axis.
742 : : */
743 : 0 : box = DatumGetBoxP(entryvec->vector[i].key);
744 [ # # ]: 0 : if (context.dim == 0)
745 : : {
746 : 0 : lower = box->low.x;
747 : 0 : upper = box->high.x;
748 : 0 : }
749 : : else
750 : : {
751 : 0 : lower = box->low.y;
752 : 0 : upper = box->high.y;
753 : : }
754 : :
755 [ # # ]: 0 : if (float8_le(upper, context.leftUpper))
756 : : {
757 : : /* Fits to the left group */
758 [ # # ]: 0 : if (float8_ge(lower, context.rightLower))
759 : : {
760 : : /* Fits also to the right group, so "common entry" */
761 : 0 : commonEntries[commonEntriesCount++].index = i;
762 : 0 : }
763 : : else
764 : : {
765 : : /* Doesn't fit to the right group, so join to the left group */
766 [ # # ]: 0 : PLACE_LEFT(box, i);
767 : : }
768 : 0 : }
769 : : else
770 : : {
771 : : /*
772 : : * Each entry should fit on either left or right group. Since this
773 : : * entry didn't fit on the left group, it better fit in the right
774 : : * group.
775 : : */
776 [ # # ]: 0 : Assert(float8_ge(lower, context.rightLower));
777 : :
778 : : /* Doesn't fit to the left group, so join to the right group */
779 [ # # ]: 0 : PLACE_RIGHT(box, i);
780 : : }
781 : 0 : }
782 : :
783 : : /*
784 : : * Distribute "common entries", if any.
785 : : */
786 [ # # ]: 0 : if (commonEntriesCount > 0)
787 : : {
788 : : /*
789 : : * Calculate minimum number of entries that must be placed in both
790 : : * groups, to reach LIMIT_RATIO.
791 : : */
792 : 0 : int m = ceil(LIMIT_RATIO * nentries);
793 : :
794 : : /*
795 : : * Calculate delta between penalties of join "common entries" to
796 : : * different groups.
797 : : */
798 [ # # ]: 0 : for (i = 0; i < commonEntriesCount; i++)
799 : : {
800 : 0 : box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
801 : 0 : commonEntries[i].delta = fabs(float8_mi(box_penalty(leftBox, box),
802 : 0 : box_penalty(rightBox, box)));
803 : 0 : }
804 : :
805 : : /*
806 : : * Sort "common entries" by calculated deltas in order to distribute
807 : : * the most ambiguous entries first.
808 : : */
809 : 0 : qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
810 : :
811 : : /*
812 : : * Distribute "common entries" between groups.
813 : : */
814 [ # # ]: 0 : for (i = 0; i < commonEntriesCount; i++)
815 : : {
816 : 0 : box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
817 : :
818 : : /*
819 : : * Check if we have to place this entry in either group to achieve
820 : : * LIMIT_RATIO.
821 : : */
822 [ # # ]: 0 : if (v->spl_nleft + (commonEntriesCount - i) <= m)
823 [ # # ]: 0 : PLACE_LEFT(box, commonEntries[i].index);
824 [ # # ]: 0 : else if (v->spl_nright + (commonEntriesCount - i) <= m)
825 [ # # ]: 0 : PLACE_RIGHT(box, commonEntries[i].index);
826 : : else
827 : : {
828 : : /* Otherwise select the group by minimal penalty */
829 [ # # ]: 0 : if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
830 [ # # ]: 0 : PLACE_LEFT(box, commonEntries[i].index);
831 : : else
832 [ # # ]: 0 : PLACE_RIGHT(box, commonEntries[i].index);
833 : : }
834 : 0 : }
835 : 0 : }
836 : :
837 : 0 : v->spl_ldatum = PointerGetDatum(leftBox);
838 : 0 : v->spl_rdatum = PointerGetDatum(rightBox);
839 : 0 : PG_RETURN_POINTER(v);
840 : 0 : }
841 : :
842 : : /*
843 : : * Equality method
844 : : *
845 : : * This is used for boxes, points, circles, and polygons, all of which store
846 : : * boxes as GiST index entries.
847 : : *
848 : : * Returns true only when boxes are exactly the same. We can't use fuzzy
849 : : * comparisons here without breaking index consistency; therefore, this isn't
850 : : * equivalent to box_same().
851 : : */
852 : : Datum
853 : 0 : gist_box_same(PG_FUNCTION_ARGS)
854 : : {
855 : 0 : BOX *b1 = PG_GETARG_BOX_P(0);
856 : 0 : BOX *b2 = PG_GETARG_BOX_P(1);
857 : 0 : bool *result = (bool *) PG_GETARG_POINTER(2);
858 : :
859 [ # # # # ]: 0 : if (b1 && b2)
860 [ # # ]: 0 : *result = (float8_eq(b1->low.x, b2->low.x) &&
861 [ # # ]: 0 : float8_eq(b1->low.y, b2->low.y) &&
862 [ # # ]: 0 : float8_eq(b1->high.x, b2->high.x) &&
863 : 0 : float8_eq(b1->high.y, b2->high.y));
864 : : else
865 [ # # ]: 0 : *result = (b1 == NULL && b2 == NULL);
866 : 0 : PG_RETURN_POINTER(result);
867 : 0 : }
868 : :
869 : : /*
870 : : * Leaf-level consistency for boxes: just apply the query operator
871 : : */
872 : : static bool
873 : 0 : gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
874 : : {
875 : 0 : bool retval;
876 : :
877 [ # # # # : 0 : switch (strategy)
# # # # #
# # # # ]
878 : : {
879 : : case RTLeftStrategyNumber:
880 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_left,
881 : : PointerGetDatum(key),
882 : : PointerGetDatum(query)));
883 : 0 : break;
884 : : case RTOverLeftStrategyNumber:
885 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overleft,
886 : : PointerGetDatum(key),
887 : : PointerGetDatum(query)));
888 : 0 : break;
889 : : case RTOverlapStrategyNumber:
890 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overlap,
891 : : PointerGetDatum(key),
892 : : PointerGetDatum(query)));
893 : 0 : break;
894 : : case RTOverRightStrategyNumber:
895 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overright,
896 : : PointerGetDatum(key),
897 : : PointerGetDatum(query)));
898 : 0 : break;
899 : : case RTRightStrategyNumber:
900 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_right,
901 : : PointerGetDatum(key),
902 : : PointerGetDatum(query)));
903 : 0 : break;
904 : : case RTSameStrategyNumber:
905 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_same,
906 : : PointerGetDatum(key),
907 : : PointerGetDatum(query)));
908 : 0 : break;
909 : : case RTContainsStrategyNumber:
910 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_contain,
911 : : PointerGetDatum(key),
912 : : PointerGetDatum(query)));
913 : 0 : break;
914 : : case RTContainedByStrategyNumber:
915 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_contained,
916 : : PointerGetDatum(key),
917 : : PointerGetDatum(query)));
918 : 0 : break;
919 : : case RTOverBelowStrategyNumber:
920 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
921 : : PointerGetDatum(key),
922 : : PointerGetDatum(query)));
923 : 0 : break;
924 : : case RTBelowStrategyNumber:
925 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_below,
926 : : PointerGetDatum(key),
927 : : PointerGetDatum(query)));
928 : 0 : break;
929 : : case RTAboveStrategyNumber:
930 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_above,
931 : : PointerGetDatum(key),
932 : : PointerGetDatum(query)));
933 : 0 : break;
934 : : case RTOverAboveStrategyNumber:
935 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overabove,
936 : : PointerGetDatum(key),
937 : : PointerGetDatum(query)));
938 : 0 : break;
939 : : default:
940 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
941 : 0 : retval = false; /* keep compiler quiet */
942 : 0 : break;
943 : : }
944 : 0 : return retval;
945 : 0 : }
946 : :
947 : : /*****************************************
948 : : * Common rtree functions (for boxes, polygons, and circles)
949 : : *****************************************/
950 : :
951 : : /*
952 : : * Internal-page consistency for all these types
953 : : *
954 : : * We can use the same function since all types use bounding boxes as the
955 : : * internal-page representation.
956 : : */
957 : : static bool
958 : 0 : rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
959 : : {
960 : 0 : bool retval;
961 : :
962 [ # # # # : 0 : switch (strategy)
# # # # #
# # # ]
963 : : {
964 : : case RTLeftStrategyNumber:
965 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overright,
966 : : PointerGetDatum(key),
967 : : PointerGetDatum(query)));
968 : 0 : break;
969 : : case RTOverLeftStrategyNumber:
970 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_right,
971 : : PointerGetDatum(key),
972 : : PointerGetDatum(query)));
973 : 0 : break;
974 : : case RTOverlapStrategyNumber:
975 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overlap,
976 : : PointerGetDatum(key),
977 : : PointerGetDatum(query)));
978 : 0 : break;
979 : : case RTOverRightStrategyNumber:
980 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_left,
981 : : PointerGetDatum(key),
982 : : PointerGetDatum(query)));
983 : 0 : break;
984 : : case RTRightStrategyNumber:
985 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
986 : : PointerGetDatum(key),
987 : : PointerGetDatum(query)));
988 : 0 : break;
989 : : case RTSameStrategyNumber:
990 : : case RTContainsStrategyNumber:
991 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_contain,
992 : : PointerGetDatum(key),
993 : : PointerGetDatum(query)));
994 : 0 : break;
995 : : case RTContainedByStrategyNumber:
996 : 0 : retval = DatumGetBool(DirectFunctionCall2(box_overlap,
997 : : PointerGetDatum(key),
998 : : PointerGetDatum(query)));
999 : 0 : break;
1000 : : case RTOverBelowStrategyNumber:
1001 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_above,
1002 : : PointerGetDatum(key),
1003 : : PointerGetDatum(query)));
1004 : 0 : break;
1005 : : case RTBelowStrategyNumber:
1006 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
1007 : : PointerGetDatum(key),
1008 : : PointerGetDatum(query)));
1009 : 0 : break;
1010 : : case RTAboveStrategyNumber:
1011 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
1012 : : PointerGetDatum(key),
1013 : : PointerGetDatum(query)));
1014 : 0 : break;
1015 : : case RTOverAboveStrategyNumber:
1016 : 0 : retval = !DatumGetBool(DirectFunctionCall2(box_below,
1017 : : PointerGetDatum(key),
1018 : : PointerGetDatum(query)));
1019 : 0 : break;
1020 : : default:
1021 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1022 : 0 : retval = false; /* keep compiler quiet */
1023 : 0 : break;
1024 : : }
1025 : 0 : return retval;
1026 : 0 : }
1027 : :
1028 : : /**************************************************
1029 : : * Polygon ops
1030 : : **************************************************/
1031 : :
1032 : : /*
1033 : : * GiST compress for polygons: represent a polygon by its bounding box
1034 : : */
1035 : : Datum
1036 : 0 : gist_poly_compress(PG_FUNCTION_ARGS)
1037 : : {
1038 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1039 : 0 : GISTENTRY *retval;
1040 : :
1041 [ # # ]: 0 : if (entry->leafkey)
1042 : : {
1043 : 0 : POLYGON *in = DatumGetPolygonP(entry->key);
1044 : 0 : BOX *r;
1045 : :
1046 : 0 : r = palloc_object(BOX);
1047 : 0 : memcpy(r, &(in->boundbox), sizeof(BOX));
1048 : :
1049 : 0 : retval = palloc_object(GISTENTRY);
1050 : 0 : gistentryinit(*retval, PointerGetDatum(r),
1051 : : entry->rel, entry->page,
1052 : : entry->offset, false);
1053 : 0 : }
1054 : : else
1055 : 0 : retval = entry;
1056 : 0 : PG_RETURN_POINTER(retval);
1057 : 0 : }
1058 : :
1059 : : /*
1060 : : * The GiST Consistent method for polygons
1061 : : */
1062 : : Datum
1063 : 0 : gist_poly_consistent(PG_FUNCTION_ARGS)
1064 : : {
1065 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1066 : 0 : POLYGON *query = PG_GETARG_POLYGON_P(1);
1067 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1068 : : #ifdef NOT_USED
1069 : : Oid subtype = PG_GETARG_OID(3);
1070 : : #endif
1071 : 0 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1072 : 0 : bool result;
1073 : :
1074 : : /* All cases served by this function are inexact */
1075 : 0 : *recheck = true;
1076 : :
1077 [ # # # # ]: 0 : if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1078 : 0 : PG_RETURN_BOOL(false);
1079 : :
1080 : : /*
1081 : : * Since the operators require recheck anyway, we can just use
1082 : : * rtree_internal_consistent even at leaf nodes. (This works in part
1083 : : * because the index entries are bounding boxes not polygons.)
1084 : : */
1085 : 0 : result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1086 : 0 : &(query->boundbox), strategy);
1087 : :
1088 : : /* Avoid memory leak if supplied poly is toasted */
1089 [ # # ]: 0 : PG_FREE_IF_COPY(query, 1);
1090 : :
1091 : 0 : PG_RETURN_BOOL(result);
1092 : 0 : }
1093 : :
1094 : : /**************************************************
1095 : : * Circle ops
1096 : : **************************************************/
1097 : :
1098 : : /*
1099 : : * GiST compress for circles: represent a circle by its bounding box
1100 : : */
1101 : : Datum
1102 : 0 : gist_circle_compress(PG_FUNCTION_ARGS)
1103 : : {
1104 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1105 : 0 : GISTENTRY *retval;
1106 : :
1107 [ # # ]: 0 : if (entry->leafkey)
1108 : : {
1109 : 0 : CIRCLE *in = DatumGetCircleP(entry->key);
1110 : 0 : BOX *r;
1111 : :
1112 : 0 : r = palloc_object(BOX);
1113 : 0 : r->high.x = float8_pl(in->center.x, in->radius);
1114 : 0 : r->low.x = float8_mi(in->center.x, in->radius);
1115 : 0 : r->high.y = float8_pl(in->center.y, in->radius);
1116 : 0 : r->low.y = float8_mi(in->center.y, in->radius);
1117 : :
1118 : 0 : retval = palloc_object(GISTENTRY);
1119 : 0 : gistentryinit(*retval, PointerGetDatum(r),
1120 : : entry->rel, entry->page,
1121 : : entry->offset, false);
1122 : 0 : }
1123 : : else
1124 : 0 : retval = entry;
1125 : 0 : PG_RETURN_POINTER(retval);
1126 : 0 : }
1127 : :
1128 : : /*
1129 : : * The GiST Consistent method for circles
1130 : : */
1131 : : Datum
1132 : 0 : gist_circle_consistent(PG_FUNCTION_ARGS)
1133 : : {
1134 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1135 : 0 : CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1136 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1137 : : #ifdef NOT_USED
1138 : : Oid subtype = PG_GETARG_OID(3);
1139 : : #endif
1140 : 0 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1141 : 0 : BOX bbox;
1142 : 0 : bool result;
1143 : :
1144 : : /* All cases served by this function are inexact */
1145 : 0 : *recheck = true;
1146 : :
1147 [ # # # # ]: 0 : if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1148 : 0 : PG_RETURN_BOOL(false);
1149 : :
1150 : : /*
1151 : : * Since the operators require recheck anyway, we can just use
1152 : : * rtree_internal_consistent even at leaf nodes. (This works in part
1153 : : * because the index entries are bounding boxes not circles.)
1154 : : */
1155 : 0 : bbox.high.x = float8_pl(query->center.x, query->radius);
1156 : 0 : bbox.low.x = float8_mi(query->center.x, query->radius);
1157 : 0 : bbox.high.y = float8_pl(query->center.y, query->radius);
1158 : 0 : bbox.low.y = float8_mi(query->center.y, query->radius);
1159 : :
1160 : 0 : result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1161 : 0 : &bbox, strategy);
1162 : :
1163 : 0 : PG_RETURN_BOOL(result);
1164 : 0 : }
1165 : :
1166 : : /**************************************************
1167 : : * Point ops
1168 : : **************************************************/
1169 : :
1170 : : Datum
1171 : 0 : gist_point_compress(PG_FUNCTION_ARGS)
1172 : : {
1173 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1174 : :
1175 [ # # ]: 0 : if (entry->leafkey) /* Point, actually */
1176 : : {
1177 : 0 : BOX *box = palloc_object(BOX);
1178 : 0 : Point *point = DatumGetPointP(entry->key);
1179 : 0 : GISTENTRY *retval = palloc_object(GISTENTRY);
1180 : :
1181 : 0 : box->high = box->low = *point;
1182 : :
1183 : 0 : gistentryinit(*retval, BoxPGetDatum(box),
1184 : : entry->rel, entry->page, entry->offset, false);
1185 : :
1186 : 0 : PG_RETURN_POINTER(retval);
1187 : 0 : }
1188 : :
1189 : 0 : PG_RETURN_POINTER(entry);
1190 : 0 : }
1191 : :
1192 : : /*
1193 : : * GiST Fetch method for point
1194 : : *
1195 : : * Get point coordinates from its bounding box coordinates and form new
1196 : : * gistentry.
1197 : : */
1198 : : Datum
1199 : 0 : gist_point_fetch(PG_FUNCTION_ARGS)
1200 : : {
1201 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1202 : 0 : BOX *in = DatumGetBoxP(entry->key);
1203 : 0 : Point *r;
1204 : 0 : GISTENTRY *retval;
1205 : :
1206 : 0 : retval = palloc_object(GISTENTRY);
1207 : :
1208 : 0 : r = palloc_object(Point);
1209 : 0 : r->x = in->high.x;
1210 : 0 : r->y = in->high.y;
1211 : 0 : gistentryinit(*retval, PointerGetDatum(r),
1212 : : entry->rel, entry->page,
1213 : : entry->offset, false);
1214 : :
1215 : 0 : PG_RETURN_POINTER(retval);
1216 : 0 : }
1217 : :
1218 : :
1219 : : #define point_point_distance(p1,p2) \
1220 : : DatumGetFloat8(DirectFunctionCall2(point_distance, \
1221 : : PointPGetDatum(p1), PointPGetDatum(p2)))
1222 : :
1223 : : static float8
1224 : 0 : computeDistance(bool isLeaf, BOX *box, Point *point)
1225 : : {
1226 : 0 : float8 result = 0.0;
1227 : :
1228 [ # # ]: 0 : if (isLeaf)
1229 : : {
1230 : : /* simple point to point distance */
1231 : 0 : result = point_point_distance(point, &box->low);
1232 : 0 : }
1233 [ # # # # ]: 0 : else if (point->x <= box->high.x && point->x >= box->low.x &&
1234 [ # # # # ]: 0 : point->y <= box->high.y && point->y >= box->low.y)
1235 : : {
1236 : : /* point inside the box */
1237 : 0 : result = 0.0;
1238 : 0 : }
1239 [ # # # # ]: 0 : else if (point->x <= box->high.x && point->x >= box->low.x)
1240 : : {
1241 : : /* point is over or below box */
1242 [ # # ]: 0 : Assert(box->low.y <= box->high.y);
1243 [ # # ]: 0 : if (point->y > box->high.y)
1244 : 0 : result = float8_mi(point->y, box->high.y);
1245 [ # # ]: 0 : else if (point->y < box->low.y)
1246 : 0 : result = float8_mi(box->low.y, point->y);
1247 : : else
1248 [ # # # # ]: 0 : elog(ERROR, "inconsistent point values");
1249 : 0 : }
1250 [ # # # # ]: 0 : else if (point->y <= box->high.y && point->y >= box->low.y)
1251 : : {
1252 : : /* point is to left or right of box */
1253 [ # # ]: 0 : Assert(box->low.x <= box->high.x);
1254 [ # # ]: 0 : if (point->x > box->high.x)
1255 : 0 : result = float8_mi(point->x, box->high.x);
1256 [ # # ]: 0 : else if (point->x < box->low.x)
1257 : 0 : result = float8_mi(box->low.x, point->x);
1258 : : else
1259 [ # # # # ]: 0 : elog(ERROR, "inconsistent point values");
1260 : 0 : }
1261 : : else
1262 : : {
1263 : : /* closest point will be a vertex */
1264 : 0 : Point p;
1265 : 0 : float8 subresult;
1266 : :
1267 : 0 : result = point_point_distance(point, &box->low);
1268 : :
1269 : 0 : subresult = point_point_distance(point, &box->high);
1270 [ # # ]: 0 : if (result > subresult)
1271 : 0 : result = subresult;
1272 : :
1273 : 0 : p.x = box->low.x;
1274 : 0 : p.y = box->high.y;
1275 : 0 : subresult = point_point_distance(point, &p);
1276 [ # # ]: 0 : if (result > subresult)
1277 : 0 : result = subresult;
1278 : :
1279 : 0 : p.x = box->high.x;
1280 : 0 : p.y = box->low.y;
1281 : 0 : subresult = point_point_distance(point, &p);
1282 [ # # ]: 0 : if (result > subresult)
1283 : 0 : result = subresult;
1284 : 0 : }
1285 : :
1286 : 0 : return result;
1287 : 0 : }
1288 : :
1289 : : static bool
1290 : 0 : gist_point_consistent_internal(StrategyNumber strategy,
1291 : : bool isLeaf, BOX *key, Point *query)
1292 : : {
1293 : 0 : bool result = false;
1294 : :
1295 [ # # # # : 0 : switch (strategy)
# # ]
1296 : : {
1297 : : case RTLeftStrategyNumber:
1298 : 0 : result = FPlt(key->low.x, query->x);
1299 : 0 : break;
1300 : : case RTRightStrategyNumber:
1301 : 0 : result = FPgt(key->high.x, query->x);
1302 : 0 : break;
1303 : : case RTAboveStrategyNumber:
1304 : 0 : result = FPgt(key->high.y, query->y);
1305 : 0 : break;
1306 : : case RTBelowStrategyNumber:
1307 : 0 : result = FPlt(key->low.y, query->y);
1308 : 0 : break;
1309 : : case RTSameStrategyNumber:
1310 [ # # ]: 0 : if (isLeaf)
1311 : : {
1312 : : /* key.high must equal key.low, so we can disregard it */
1313 [ # # ]: 0 : result = (FPeq(key->low.x, query->x) &&
1314 : 0 : FPeq(key->low.y, query->y));
1315 : 0 : }
1316 : : else
1317 : : {
1318 [ # # ]: 0 : result = (FPle(query->x, key->high.x) &&
1319 [ # # ]: 0 : FPge(query->x, key->low.x) &&
1320 [ # # ]: 0 : FPle(query->y, key->high.y) &&
1321 : 0 : FPge(query->y, key->low.y));
1322 : : }
1323 : 0 : break;
1324 : : default:
1325 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1326 : 0 : result = false; /* keep compiler quiet */
1327 : 0 : break;
1328 : : }
1329 : :
1330 : 0 : return result;
1331 : 0 : }
1332 : :
1333 : : #define GeoStrategyNumberOffset 20
1334 : : #define PointStrategyNumberGroup 0
1335 : : #define BoxStrategyNumberGroup 1
1336 : : #define PolygonStrategyNumberGroup 2
1337 : : #define CircleStrategyNumberGroup 3
1338 : :
1339 : : Datum
1340 : 0 : gist_point_consistent(PG_FUNCTION_ARGS)
1341 : : {
1342 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1343 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1344 : 0 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1345 : 0 : bool result;
1346 : 0 : StrategyNumber strategyGroup;
1347 : :
1348 : : /*
1349 : : * We have to remap these strategy numbers to get this klugy
1350 : : * classification logic to work.
1351 : : */
1352 [ # # ]: 0 : if (strategy == RTOldBelowStrategyNumber)
1353 : 0 : strategy = RTBelowStrategyNumber;
1354 [ # # ]: 0 : else if (strategy == RTOldAboveStrategyNumber)
1355 : 0 : strategy = RTAboveStrategyNumber;
1356 : :
1357 : 0 : strategyGroup = strategy / GeoStrategyNumberOffset;
1358 [ # # # # : 0 : switch (strategyGroup)
# ]
1359 : : {
1360 : : case PointStrategyNumberGroup:
1361 : 0 : result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset,
1362 : 0 : GIST_LEAF(entry),
1363 : 0 : DatumGetBoxP(entry->key),
1364 : 0 : PG_GETARG_POINT_P(1));
1365 : 0 : *recheck = false;
1366 : 0 : break;
1367 : : case BoxStrategyNumberGroup:
1368 : : {
1369 : : /*
1370 : : * The only operator in this group is point <@ box (on_pb), so
1371 : : * we needn't examine strategy again.
1372 : : *
1373 : : * For historical reasons, on_pb uses exact rather than fuzzy
1374 : : * comparisons. We could use box_overlap when at an internal
1375 : : * page, but that would lead to possibly visiting child pages
1376 : : * uselessly, because box_overlap uses fuzzy comparisons.
1377 : : * Instead we write a non-fuzzy overlap test. The same code
1378 : : * will also serve for leaf-page tests, since leaf keys have
1379 : : * high == low.
1380 : : */
1381 : 0 : BOX *query,
1382 : : *key;
1383 : :
1384 : 0 : query = PG_GETARG_BOX_P(1);
1385 : 0 : key = DatumGetBoxP(entry->key);
1386 : :
1387 [ # # ]: 0 : result = (key->high.x >= query->low.x &&
1388 [ # # ]: 0 : key->low.x <= query->high.x &&
1389 [ # # ]: 0 : key->high.y >= query->low.y &&
1390 : 0 : key->low.y <= query->high.y);
1391 : 0 : *recheck = false;
1392 : 0 : }
1393 : 0 : break;
1394 : : case PolygonStrategyNumberGroup:
1395 : : {
1396 : 0 : POLYGON *query = PG_GETARG_POLYGON_P(1);
1397 : :
1398 : 0 : result = DatumGetBool(DirectFunctionCall5(gist_poly_consistent,
1399 : : PointerGetDatum(entry),
1400 : : PolygonPGetDatum(query),
1401 : : Int16GetDatum(RTOverlapStrategyNumber),
1402 : : 0, PointerGetDatum(recheck)));
1403 : :
1404 [ # # # # ]: 0 : if (GIST_LEAF(entry) && result)
1405 : : {
1406 : : /*
1407 : : * We are on leaf page and quick check shows overlapping
1408 : : * of polygon's bounding box and point
1409 : : */
1410 : 0 : BOX *box = DatumGetBoxP(entry->key);
1411 : :
1412 [ # # ]: 0 : Assert(box->high.x == box->low.x
1413 : : && box->high.y == box->low.y);
1414 : 0 : result = DatumGetBool(DirectFunctionCall2(poly_contain_pt,
1415 : : PolygonPGetDatum(query),
1416 : : PointPGetDatum(&box->high)));
1417 : 0 : *recheck = false;
1418 : 0 : }
1419 : 0 : }
1420 : 0 : break;
1421 : : case CircleStrategyNumberGroup:
1422 : : {
1423 : 0 : CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1424 : :
1425 : 0 : result = DatumGetBool(DirectFunctionCall5(gist_circle_consistent,
1426 : : PointerGetDatum(entry),
1427 : : CirclePGetDatum(query),
1428 : : Int16GetDatum(RTOverlapStrategyNumber),
1429 : : 0, PointerGetDatum(recheck)));
1430 : :
1431 [ # # # # ]: 0 : if (GIST_LEAF(entry) && result)
1432 : : {
1433 : : /*
1434 : : * We are on leaf page and quick check shows overlapping
1435 : : * of polygon's bounding box and point
1436 : : */
1437 : 0 : BOX *box = DatumGetBoxP(entry->key);
1438 : :
1439 [ # # ]: 0 : Assert(box->high.x == box->low.x
1440 : : && box->high.y == box->low.y);
1441 : 0 : result = DatumGetBool(DirectFunctionCall2(circle_contain_pt,
1442 : : CirclePGetDatum(query),
1443 : : PointPGetDatum(&box->high)));
1444 : 0 : *recheck = false;
1445 : 0 : }
1446 : 0 : }
1447 : 0 : break;
1448 : : default:
1449 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1450 : 0 : result = false; /* keep compiler quiet */
1451 : 0 : break;
1452 : : }
1453 : :
1454 : 0 : PG_RETURN_BOOL(result);
1455 : 0 : }
1456 : :
1457 : : Datum
1458 : 0 : gist_point_distance(PG_FUNCTION_ARGS)
1459 : : {
1460 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1461 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1462 : 0 : float8 distance;
1463 : 0 : StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1464 : :
1465 [ # # ]: 0 : switch (strategyGroup)
1466 : : {
1467 : : case PointStrategyNumberGroup:
1468 : 0 : distance = computeDistance(GIST_LEAF(entry),
1469 : 0 : DatumGetBoxP(entry->key),
1470 : 0 : PG_GETARG_POINT_P(1));
1471 : 0 : break;
1472 : : default:
1473 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1474 : 0 : distance = 0.0; /* keep compiler quiet */
1475 : 0 : break;
1476 : : }
1477 : :
1478 : 0 : PG_RETURN_FLOAT8(distance);
1479 : 0 : }
1480 : :
1481 : : static float8
1482 : 0 : gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
1483 : : {
1484 : 0 : float8 distance;
1485 : 0 : StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1486 : :
1487 [ # # ]: 0 : switch (strategyGroup)
1488 : : {
1489 : : case PointStrategyNumberGroup:
1490 : 0 : distance = computeDistance(false,
1491 : 0 : DatumGetBoxP(entry->key),
1492 : 0 : DatumGetPointP(query));
1493 : 0 : break;
1494 : : default:
1495 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1496 : 0 : distance = 0.0; /* keep compiler quiet */
1497 : 0 : }
1498 : :
1499 : 0 : return distance;
1500 : 0 : }
1501 : :
1502 : : Datum
1503 : 0 : gist_box_distance(PG_FUNCTION_ARGS)
1504 : : {
1505 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1506 : 0 : Datum query = PG_GETARG_DATUM(1);
1507 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1508 : : #ifdef NOT_USED
1509 : : Oid subtype = PG_GETARG_OID(3);
1510 : : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1511 : : #endif
1512 : 0 : float8 distance;
1513 : :
1514 : 0 : distance = gist_bbox_distance(entry, query, strategy);
1515 : :
1516 : 0 : PG_RETURN_FLOAT8(distance);
1517 : 0 : }
1518 : :
1519 : : /*
1520 : : * The inexact GiST distance methods for geometric types that store bounding
1521 : : * boxes.
1522 : : *
1523 : : * Compute lossy distance from point to index entries. The result is inexact
1524 : : * because index entries are bounding boxes, not the exact shapes of the
1525 : : * indexed geometric types. We use distance from point to MBR of index entry.
1526 : : * This is a lower bound estimate of distance from point to indexed geometric
1527 : : * type.
1528 : : */
1529 : : Datum
1530 : 0 : gist_circle_distance(PG_FUNCTION_ARGS)
1531 : : {
1532 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1533 : 0 : Datum query = PG_GETARG_DATUM(1);
1534 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1535 : : #ifdef NOT_USED
1536 : : Oid subtype = PG_GETARG_OID(3);
1537 : : #endif
1538 : 0 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1539 : 0 : float8 distance;
1540 : :
1541 : 0 : distance = gist_bbox_distance(entry, query, strategy);
1542 : 0 : *recheck = true;
1543 : :
1544 : 0 : PG_RETURN_FLOAT8(distance);
1545 : 0 : }
1546 : :
1547 : : Datum
1548 : 0 : gist_poly_distance(PG_FUNCTION_ARGS)
1549 : : {
1550 : 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1551 : 0 : Datum query = PG_GETARG_DATUM(1);
1552 : 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1553 : : #ifdef NOT_USED
1554 : : Oid subtype = PG_GETARG_OID(3);
1555 : : #endif
1556 : 0 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1557 : 0 : float8 distance;
1558 : :
1559 : 0 : distance = gist_bbox_distance(entry, query, strategy);
1560 : 0 : *recheck = true;
1561 : :
1562 : 0 : PG_RETURN_FLOAT8(distance);
1563 : 0 : }
1564 : :
1565 : : /*
1566 : : * Z-order routines for fast index build
1567 : : */
1568 : :
1569 : : /*
1570 : : * Compute Z-value of a point
1571 : : *
1572 : : * Z-order (also known as Morton Code) maps a two-dimensional point to a
1573 : : * single integer, in a way that preserves locality. Points that are close in
1574 : : * the two-dimensional space are mapped to integer that are not far from each
1575 : : * other. We do that by interleaving the bits in the X and Y components.
1576 : : *
1577 : : * Morton Code is normally defined only for integers, but the X and Y values
1578 : : * of a point are floating point. We expect floats to be in IEEE format.
1579 : : */
1580 : : static uint64
1581 : 0 : point_zorder_internal(float4 x, float4 y)
1582 : : {
1583 : 0 : uint32 ix = ieee_float32_to_uint32(x);
1584 : 0 : uint32 iy = ieee_float32_to_uint32(y);
1585 : :
1586 : : /* Interleave the bits */
1587 : 0 : return part_bits32_by2(ix) | (part_bits32_by2(iy) << 1);
1588 : 0 : }
1589 : :
1590 : : /* Interleave 32 bits with zeroes */
1591 : : static uint64
1592 : 0 : part_bits32_by2(uint32 x)
1593 : : {
1594 : 0 : uint64 n = x;
1595 : :
1596 : 0 : n = (n | (n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
1597 : 0 : n = (n | (n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
1598 : 0 : n = (n | (n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
1599 : 0 : n = (n | (n << 2)) & UINT64CONST(0x3333333333333333);
1600 : 0 : n = (n | (n << 1)) & UINT64CONST(0x5555555555555555);
1601 : :
1602 : 0 : return n;
1603 : 0 : }
1604 : :
1605 : : /*
1606 : : * Convert a 32-bit IEEE float to uint32 in a way that preserves the ordering
1607 : : */
1608 : : static uint32
1609 : 0 : ieee_float32_to_uint32(float f)
1610 : : {
1611 : : /*----
1612 : : *
1613 : : * IEEE 754 floating point format
1614 : : * ------------------------------
1615 : : *
1616 : : * IEEE 754 floating point numbers have this format:
1617 : : *
1618 : : * exponent (8 bits)
1619 : : * |
1620 : : * s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm
1621 : : * | |
1622 : : * sign mantissa (23 bits)
1623 : : *
1624 : : * Infinity has all bits in the exponent set and the mantissa is all
1625 : : * zeros. Negative infinity is the same but with the sign bit set.
1626 : : *
1627 : : * NaNs are represented with all bits in the exponent set, and the least
1628 : : * significant bit in the mantissa also set. The rest of the mantissa bits
1629 : : * can be used to distinguish different kinds of NaNs.
1630 : : *
1631 : : * The IEEE format has the nice property that when you take the bit
1632 : : * representation and interpret it as an integer, the order is preserved,
1633 : : * except for the sign. That holds for the +-Infinity values too.
1634 : : *
1635 : : * Mapping to uint32
1636 : : * -----------------
1637 : : *
1638 : : * In order to have a smooth transition from negative to positive numbers,
1639 : : * we map floats to unsigned integers like this:
1640 : : *
1641 : : * x < 0 to range 0-7FFFFFFF
1642 : : * x = 0 to value 8000000 (both positive and negative zero)
1643 : : * x > 0 to range 8000001-FFFFFFFF
1644 : : *
1645 : : * We don't care to distinguish different kind of NaNs, so they are all
1646 : : * mapped to the same arbitrary value, FFFFFFFF. Because of the IEEE bit
1647 : : * representation of NaNs, there aren't any non-NaN values that would be
1648 : : * mapped to FFFFFFFF. In fact, there is a range of unused values on both
1649 : : * ends of the uint32 space.
1650 : : */
1651 [ # # # # : 0 : if (isnan(f))
# # ]
1652 : 0 : return 0xFFFFFFFF;
1653 : : else
1654 : : {
1655 : 0 : union
1656 : : {
1657 : : float f;
1658 : : uint32 i;
1659 : : } u;
1660 : :
1661 : 0 : u.f = f;
1662 : :
1663 : : /* Check the sign bit */
1664 [ # # ]: 0 : if ((u.i & 0x80000000) != 0)
1665 : : {
1666 : : /*
1667 : : * Map the negative value to range 0-7FFFFFFF. This flips the sign
1668 : : * bit to 0 in the same instruction.
1669 : : */
1670 [ # # ]: 0 : Assert(f <= 0); /* can be -0 */
1671 : 0 : u.i ^= 0xFFFFFFFF;
1672 : 0 : }
1673 : : else
1674 : : {
1675 : : /* Map the positive value (or 0) to range 80000000-FFFFFFFF */
1676 : 0 : u.i |= 0x80000000;
1677 : : }
1678 : :
1679 : 0 : return u.i;
1680 : 0 : }
1681 : 0 : }
1682 : :
1683 : : /*
1684 : : * Compare the Z-order of points
1685 : : */
1686 : : static int
1687 : 0 : gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup)
1688 : : {
1689 : 0 : Point *p1 = &(DatumGetBoxP(a)->low);
1690 : 0 : Point *p2 = &(DatumGetBoxP(b)->low);
1691 : 0 : uint64 z1;
1692 : 0 : uint64 z2;
1693 : :
1694 : : /*
1695 : : * Do a quick check for equality first. It's not clear if this is worth it
1696 : : * in general, but certainly is when used as tie-breaker with abbreviated
1697 : : * keys,
1698 : : */
1699 [ # # # # ]: 0 : if (p1->x == p2->x && p1->y == p2->y)
1700 : 0 : return 0;
1701 : :
1702 : 0 : z1 = point_zorder_internal(p1->x, p1->y);
1703 : 0 : z2 = point_zorder_internal(p2->x, p2->y);
1704 [ # # ]: 0 : if (z1 > z2)
1705 : 0 : return 1;
1706 [ # # ]: 0 : else if (z1 < z2)
1707 : 0 : return -1;
1708 : : else
1709 : 0 : return 0;
1710 : 0 : }
1711 : :
1712 : : /*
1713 : : * Abbreviated version of Z-order comparison
1714 : : *
1715 : : * The abbreviated format is a Z-order value computed from the two 32-bit
1716 : : * floats. Now that sizeof(Datum) is always 8, the 64-bit Z-order value
1717 : : * always fits fully in the abbreviated Datum.
1718 : : */
1719 : : static Datum
1720 : 0 : gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
1721 : : {
1722 : 0 : Point *p = &(DatumGetBoxP(original)->low);
1723 : 0 : uint64 z;
1724 : :
1725 : 0 : z = point_zorder_internal(p->x, p->y);
1726 : :
1727 : 0 : return UInt64GetDatum(z);
1728 : 0 : }
1729 : :
1730 : : /*
1731 : : * We never consider aborting the abbreviation.
1732 : : *
1733 : : * On 64-bit systems, the abbreviation is not lossy so it is always
1734 : : * worthwhile. (Perhaps it's not on 32-bit systems, but we don't bother
1735 : : * with logic to decide.)
1736 : : */
1737 : : static bool
1738 : 0 : gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
1739 : : {
1740 : 0 : return false;
1741 : : }
1742 : :
1743 : : /*
1744 : : * Sort support routine for fast GiST index build by sorting.
1745 : : */
1746 : : Datum
1747 : 0 : gist_point_sortsupport(PG_FUNCTION_ARGS)
1748 : : {
1749 : 0 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
1750 : :
1751 [ # # ]: 0 : if (ssup->abbreviate)
1752 : : {
1753 : 0 : ssup->comparator = ssup_datum_unsigned_cmp;
1754 : 0 : ssup->abbrev_converter = gist_bbox_zorder_abbrev_convert;
1755 : 0 : ssup->abbrev_abort = gist_bbox_zorder_abbrev_abort;
1756 : 0 : ssup->abbrev_full_comparator = gist_bbox_zorder_cmp;
1757 : 0 : }
1758 : : else
1759 : : {
1760 : 0 : ssup->comparator = gist_bbox_zorder_cmp;
1761 : : }
1762 : 0 : PG_RETURN_VOID();
1763 : 0 : }
|
