PostgreSQL Source Code  git master
cube.c
Go to the documentation of this file.
1 /******************************************************************************
2  contrib/cube/cube.c
3 
4  This file contains routines that can be bound to a Postgres backend and
5  called by the backend in the process of processing queries. The calling
6  format for these routines is dictated by Postgres architecture.
7 ******************************************************************************/
8 
9 #include "postgres.h"
10 
11 #include <math.h>
12 
13 #include "access/gist.h"
14 #include "access/stratnum.h"
15 #include "cubedata.h"
16 #include "libpq/pqformat.h"
17 #include "utils/array.h"
18 #include "utils/float.h"
19 
21 
22 /*
23  * Taken from the intarray contrib header
24  */
25 #define ARRPTR(x) ( (double *) ARR_DATA_PTR(x) )
26 #define ARRNELEMS(x) ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x))
27 
28 /*
29 ** Input/Output routines
30 */
47 
48 /*
49 ** GiST support methods
50 */
51 
60 
61 /*
62 ** B-tree support functions
63 */
71 
72 /*
73 ** R-tree support functions
74 */
75 
82 
83 /*
84 ** miscellaneous
85 */
91 
92 /*
93 ** For internal use only
94 */
96 bool cube_contains_v0(NDBOX *a, NDBOX *b);
97 bool cube_overlap_v0(NDBOX *a, NDBOX *b);
99 void rt_cube_size(NDBOX *a, double *sz);
100 NDBOX *g_cube_binary_union(NDBOX *r1, NDBOX *r2, int *sizep);
101 bool g_cube_leaf_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy);
102 bool g_cube_internal_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy);
103 
104 /*
105 ** Auxiliary functions
106 */
107 static double distance_1D(double a1, double a2, double b1, double b2);
108 static bool cube_is_point_internal(NDBOX *cube);
109 
110 
111 /*****************************************************************************
112  * Input/Output functions
113  *****************************************************************************/
114 
115 /* NdBox = [(lowerleft),(upperright)] */
116 /* [(xLL(1)...xLL(N)),(xUR(1)...xUR(n))] */
117 Datum
119 {
120  char *str = PG_GETARG_CSTRING(0);
121  NDBOX *result;
122 
123  cube_scanner_init(str);
124 
125  if (cube_yyparse(&result) != 0)
126  cube_yyerror(&result, "cube parser failed");
127 
129 
130  PG_RETURN_NDBOX_P(result);
131 }
132 
133 
134 /*
135 ** Allows the construction of a cube from 2 float[]'s
136 */
137 Datum
139 {
142  NDBOX *result;
143  int i;
144  int dim;
145  int size;
146  bool point;
147  double *dur,
148  *dll;
149 
151  ereport(ERROR,
152  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
153  errmsg("cannot work with arrays containing NULLs")));
154 
155  dim = ARRNELEMS(ur);
156  if (dim > CUBE_MAX_DIM)
157  ereport(ERROR,
158  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
159  errmsg("can't extend cube"),
160  errdetail("A cube cannot have more than %d dimensions.",
161  CUBE_MAX_DIM)));
162 
163  if (ARRNELEMS(ll) != dim)
164  ereport(ERROR,
165  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
166  errmsg("UR and LL arrays must be of same length")));
167 
168  dur = ARRPTR(ur);
169  dll = ARRPTR(ll);
170 
171  /* Check if it's a point */
172  point = true;
173  for (i = 0; i < dim; i++)
174  {
175  if (dur[i] != dll[i])
176  {
177  point = false;
178  break;
179  }
180  }
181 
182  size = point ? POINT_SIZE(dim) : CUBE_SIZE(dim);
183  result = (NDBOX *) palloc0(size);
184  SET_VARSIZE(result, size);
185  SET_DIM(result, dim);
186 
187  for (i = 0; i < dim; i++)
188  result->x[i] = dur[i];
189 
190  if (!point)
191  {
192  for (i = 0; i < dim; i++)
193  result->x[i + dim] = dll[i];
194  }
195  else
196  SET_POINT_BIT(result);
197 
198  PG_RETURN_NDBOX_P(result);
199 }
200 
201 /*
202 ** Allows the construction of a zero-volume cube from a float[]
203 */
204 Datum
206 {
208  NDBOX *result;
209  int i;
210  int dim;
211  int size;
212  double *dur;
213 
214  if (array_contains_nulls(ur))
215  ereport(ERROR,
216  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
217  errmsg("cannot work with arrays containing NULLs")));
218 
219  dim = ARRNELEMS(ur);
220  if (dim > CUBE_MAX_DIM)
221  ereport(ERROR,
222  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
223  errmsg("array is too long"),
224  errdetail("A cube cannot have more than %d dimensions.",
225  CUBE_MAX_DIM)));
226 
227  dur = ARRPTR(ur);
228 
229  size = POINT_SIZE(dim);
230  result = (NDBOX *) palloc0(size);
231  SET_VARSIZE(result, size);
232  SET_DIM(result, dim);
233  SET_POINT_BIT(result);
234 
235  for (i = 0; i < dim; i++)
236  result->x[i] = dur[i];
237 
238  PG_RETURN_NDBOX_P(result);
239 }
240 
241 Datum
243 {
244  NDBOX *c = PG_GETARG_NDBOX_P(0);
246  NDBOX *result;
247  int size,
248  dim,
249  i;
250  int *dx;
251 
252  if (array_contains_nulls(idx))
253  ereport(ERROR,
254  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
255  errmsg("cannot work with arrays containing NULLs")));
256 
257  dx = (int32 *) ARR_DATA_PTR(idx);
258 
259  dim = ARRNELEMS(idx);
260  if (dim > CUBE_MAX_DIM)
261  ereport(ERROR,
262  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
263  errmsg("array is too long"),
264  errdetail("A cube cannot have more than %d dimensions.",
265  CUBE_MAX_DIM)));
266 
267  size = IS_POINT(c) ? POINT_SIZE(dim) : CUBE_SIZE(dim);
268  result = (NDBOX *) palloc0(size);
269  SET_VARSIZE(result, size);
270  SET_DIM(result, dim);
271 
272  if (IS_POINT(c))
273  SET_POINT_BIT(result);
274 
275  for (i = 0; i < dim; i++)
276  {
277  if ((dx[i] <= 0) || (dx[i] > DIM(c)))
278  ereport(ERROR,
279  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
280  errmsg("Index out of bounds")));
281  result->x[i] = c->x[dx[i] - 1];
282  if (!IS_POINT(c))
283  result->x[i + dim] = c->x[dx[i] + DIM(c) - 1];
284  }
285 
286  PG_FREE_IF_COPY(c, 0);
287  PG_RETURN_NDBOX_P(result);
288 }
289 
290 Datum
292 {
293  NDBOX *cube = PG_GETARG_NDBOX_P(0);
295  int dim = DIM(cube);
296  int i;
297 
298  initStringInfo(&buf);
299 
300  appendStringInfoChar(&buf, '(');
301  for (i = 0; i < dim; i++)
302  {
303  if (i > 0)
304  appendStringInfoString(&buf, ", ");
306  }
307  appendStringInfoChar(&buf, ')');
308 
309  if (!cube_is_point_internal(cube))
310  {
311  appendStringInfoString(&buf, ",(");
312  for (i = 0; i < dim; i++)
313  {
314  if (i > 0)
315  appendStringInfoString(&buf, ", ");
317  }
318  appendStringInfoChar(&buf, ')');
319  }
320 
321  PG_FREE_IF_COPY(cube, 0);
322  PG_RETURN_CSTRING(buf.data);
323 }
324 
325 /*
326  * cube_send - a binary output handler for cube type
327  */
328 Datum
330 {
331  NDBOX *cube = PG_GETARG_NDBOX_P(0);
333  int32 i,
334  nitems = DIM(cube);
335 
336  pq_begintypsend(&buf);
337  pq_sendint32(&buf, cube->header);
338  if (!IS_POINT(cube))
339  nitems += nitems;
340  /* for symmetry with cube_recv, we don't use LL_COORD/UR_COORD here */
341  for (i = 0; i < nitems; i++)
342  pq_sendfloat8(&buf, cube->x[i]);
343 
345 }
346 
347 /*
348  * cube_recv - a binary input handler for cube type
349  */
350 Datum
352 {
354  int32 header;
355  int32 i,
356  nitems;
357  NDBOX *cube;
358 
359  header = pq_getmsgint(buf, sizeof(int32));
360  nitems = (header & DIM_MASK);
361  if (nitems > CUBE_MAX_DIM)
362  ereport(ERROR,
363  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
364  errmsg("cube dimension is too large"),
365  errdetail("A cube cannot have more than %d dimensions.",
366  CUBE_MAX_DIM)));
367  if ((header & POINT_BIT) == 0)
368  nitems += nitems;
369  cube = palloc(offsetof(NDBOX, x) + sizeof(double) * nitems);
370  SET_VARSIZE(cube, offsetof(NDBOX, x) + sizeof(double) * nitems);
371  cube->header = header;
372  for (i = 0; i < nitems; i++)
373  cube->x[i] = pq_getmsgfloat8(buf);
374 
375  PG_RETURN_NDBOX_P(cube);
376 }
377 
378 
379 /*****************************************************************************
380  * GiST functions
381  *****************************************************************************/
382 
383 /*
384 ** The GiST Consistent method for boxes
385 ** Should return false if for all data items x below entry,
386 ** the predicate x op query == false, where op is the oper
387 ** corresponding to strategy in the pg_amop table.
388 */
389 Datum
391 {
392  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
393  NDBOX *query = PG_GETARG_NDBOX_P(1);
395 
396  /* Oid subtype = PG_GETARG_OID(3); */
397  bool *recheck = (bool *) PG_GETARG_POINTER(4);
398  bool res;
399 
400  /* All cases served by this function are exact */
401  *recheck = false;
402 
403  /*
404  * if entry is not leaf, use g_cube_internal_consistent, else use
405  * g_cube_leaf_consistent
406  */
407  if (GIST_LEAF(entry))
409  query, strategy);
410  else
412  query, strategy);
413 
414  PG_FREE_IF_COPY(query, 1);
415  PG_RETURN_BOOL(res);
416 }
417 
418 
419 /*
420 ** The GiST Union method for boxes
421 ** returns the minimal bounding box that encloses all the entries in entryvec
422 */
423 Datum
425 {
427  int *sizep = (int *) PG_GETARG_POINTER(1);
428  NDBOX *out = (NDBOX *) NULL;
429  NDBOX *tmp;
430  int i;
431 
432  tmp = DatumGetNDBOXP(entryvec->vector[0].key);
433 
434  /*
435  * sizep = sizeof(NDBOX); -- NDBOX has variable size
436  */
437  *sizep = VARSIZE(tmp);
438 
439  for (i = 1; i < entryvec->n; i++)
440  {
441  out = g_cube_binary_union(tmp,
442  DatumGetNDBOXP(entryvec->vector[i].key),
443  sizep);
444  tmp = out;
445  }
446 
447  PG_RETURN_POINTER(out);
448 }
449 
450 /*
451 ** GiST Compress and Decompress methods for boxes
452 ** do not do anything.
453 */
454 
455 Datum
457 {
459 }
460 
461 Datum
463 {
464  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
465  NDBOX *key = DatumGetNDBOXP(entry->key);
466 
467  if (key != DatumGetNDBOXP(entry->key))
468  {
469  GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
470 
471  gistentryinit(*retval, PointerGetDatum(key),
472  entry->rel, entry->page,
473  entry->offset, false);
474  PG_RETURN_POINTER(retval);
475  }
476  PG_RETURN_POINTER(entry);
477 }
478 
479 
480 /*
481 ** The GiST Penalty method for boxes
482 ** As in the R-tree paper, we use change in area as our penalty metric
483 */
484 Datum
486 {
487  GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
488  GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
489  float *result = (float *) PG_GETARG_POINTER(2);
490  NDBOX *ud;
491  double tmp1,
492  tmp2;
493 
494  ud = cube_union_v0(DatumGetNDBOXP(origentry->key),
495  DatumGetNDBOXP(newentry->key));
496  rt_cube_size(ud, &tmp1);
497  rt_cube_size(DatumGetNDBOXP(origentry->key), &tmp2);
498  *result = (float) (tmp1 - tmp2);
499 
500  PG_RETURN_FLOAT8(*result);
501 }
502 
503 
504 
505 /*
506 ** The GiST PickSplit method for boxes
507 ** We use Guttman's poly time split algorithm
508 */
509 Datum
511 {
514  OffsetNumber i,
515  j;
516  NDBOX *datum_alpha,
517  *datum_beta;
518  NDBOX *datum_l,
519  *datum_r;
520  NDBOX *union_d,
521  *union_dl,
522  *union_dr;
523  NDBOX *inter_d;
524  bool firsttime;
525  double size_alpha,
526  size_beta,
527  size_union,
528  size_inter;
529  double size_waste,
530  waste;
531  double size_l,
532  size_r;
533  int nbytes;
534  OffsetNumber seed_1 = 1,
535  seed_2 = 2;
536  OffsetNumber *left,
537  *right;
538  OffsetNumber maxoff;
539 
540  maxoff = entryvec->n - 2;
541  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
542  v->spl_left = (OffsetNumber *) palloc(nbytes);
543  v->spl_right = (OffsetNumber *) palloc(nbytes);
544 
545  firsttime = true;
546  waste = 0.0;
547 
548  for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
549  {
550  datum_alpha = DatumGetNDBOXP(entryvec->vector[i].key);
551  for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
552  {
553  datum_beta = DatumGetNDBOXP(entryvec->vector[j].key);
554 
555  /* compute the wasted space by unioning these guys */
556  /* size_waste = size_union - size_inter; */
557  union_d = cube_union_v0(datum_alpha, datum_beta);
558  rt_cube_size(union_d, &size_union);
560  entryvec->vector[i].key,
561  entryvec->vector[j].key));
562  rt_cube_size(inter_d, &size_inter);
563  size_waste = size_union - size_inter;
564 
565  /*
566  * are these a more promising split than what we've already seen?
567  */
568 
569  if (size_waste > waste || firsttime)
570  {
571  waste = size_waste;
572  seed_1 = i;
573  seed_2 = j;
574  firsttime = false;
575  }
576  }
577  }
578 
579  left = v->spl_left;
580  v->spl_nleft = 0;
581  right = v->spl_right;
582  v->spl_nright = 0;
583 
584  datum_alpha = DatumGetNDBOXP(entryvec->vector[seed_1].key);
585  datum_l = cube_union_v0(datum_alpha, datum_alpha);
586  rt_cube_size(datum_l, &size_l);
587  datum_beta = DatumGetNDBOXP(entryvec->vector[seed_2].key);
588  datum_r = cube_union_v0(datum_beta, datum_beta);
589  rt_cube_size(datum_r, &size_r);
590 
591  /*
592  * Now split up the regions between the two seeds. An important property
593  * of this split algorithm is that the split vector v has the indices of
594  * items to be split in order in its left and right vectors. We exploit
595  * this property by doing a merge in the code that actually splits the
596  * page.
597  *
598  * For efficiency, we also place the new index tuple in this loop. This is
599  * handled at the very end, when we have placed all the existing tuples
600  * and i == maxoff + 1.
601  */
602 
603  maxoff = OffsetNumberNext(maxoff);
604  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
605  {
606  /*
607  * If we've already decided where to place this item, just put it on
608  * the right list. Otherwise, we need to figure out which page needs
609  * the least enlargement in order to store the item.
610  */
611 
612  if (i == seed_1)
613  {
614  *left++ = i;
615  v->spl_nleft++;
616  continue;
617  }
618  else if (i == seed_2)
619  {
620  *right++ = i;
621  v->spl_nright++;
622  continue;
623  }
624 
625  /* okay, which page needs least enlargement? */
626  datum_alpha = DatumGetNDBOXP(entryvec->vector[i].key);
627  union_dl = cube_union_v0(datum_l, datum_alpha);
628  union_dr = cube_union_v0(datum_r, datum_alpha);
629  rt_cube_size(union_dl, &size_alpha);
630  rt_cube_size(union_dr, &size_beta);
631 
632  /* pick which page to add it to */
633  if (size_alpha - size_l < size_beta - size_r)
634  {
635  datum_l = union_dl;
636  size_l = size_alpha;
637  *left++ = i;
638  v->spl_nleft++;
639  }
640  else
641  {
642  datum_r = union_dr;
643  size_r = size_beta;
644  *right++ = i;
645  v->spl_nright++;
646  }
647  }
648  *left = *right = FirstOffsetNumber; /* sentinel value */
649 
650  v->spl_ldatum = PointerGetDatum(datum_l);
651  v->spl_rdatum = PointerGetDatum(datum_r);
652 
654 }
655 
656 /*
657 ** Equality method
658 */
659 Datum
661 {
662  NDBOX *b1 = PG_GETARG_NDBOX_P(0);
663  NDBOX *b2 = PG_GETARG_NDBOX_P(1);
664  bool *result = (bool *) PG_GETARG_POINTER(2);
665 
666  if (cube_cmp_v0(b1, b2) == 0)
667  *result = true;
668  else
669  *result = false;
670 
671  PG_RETURN_NDBOX_P(result);
672 }
673 
674 /*
675 ** SUPPORT ROUTINES
676 */
677 bool
679  NDBOX *query,
680  StrategyNumber strategy)
681 {
682  bool retval;
683 
684  switch (strategy)
685  {
687  retval = cube_overlap_v0(key, query);
688  break;
690  retval = (cube_cmp_v0(key, query) == 0);
691  break;
694  retval = cube_contains_v0(key, query);
695  break;
698  retval = cube_contains_v0(query, key);
699  break;
700  default:
701  retval = false;
702  }
703  return retval;
704 }
705 
706 bool
708  NDBOX *query,
709  StrategyNumber strategy)
710 {
711  bool retval;
712 
713  switch (strategy)
714  {
716  retval = (bool) cube_overlap_v0(key, query);
717  break;
721  retval = (bool) cube_contains_v0(key, query);
722  break;
725  retval = (bool) cube_overlap_v0(key, query);
726  break;
727  default:
728  retval = false;
729  }
730  return retval;
731 }
732 
733 NDBOX *
734 g_cube_binary_union(NDBOX *r1, NDBOX *r2, int *sizep)
735 {
736  NDBOX *retval;
737 
738  retval = cube_union_v0(r1, r2);
739  *sizep = VARSIZE(retval);
740 
741  return retval;
742 }
743 
744 
745 /* cube_union_v0 */
746 NDBOX *
748 {
749  int i;
750  NDBOX *result;
751  int dim;
752  int size;
753 
754  /* trivial case */
755  if (a == b)
756  return a;
757 
758  /* swap the arguments if needed, so that 'a' is always larger than 'b' */
759  if (DIM(a) < DIM(b))
760  {
761  NDBOX *tmp = b;
762 
763  b = a;
764  a = tmp;
765  }
766  dim = DIM(a);
767 
768  size = CUBE_SIZE(dim);
769  result = palloc0(size);
770  SET_VARSIZE(result, size);
771  SET_DIM(result, dim);
772 
773  /* First compute the union of the dimensions present in both args */
774  for (i = 0; i < DIM(b); i++)
775  {
776  result->x[i] = Min(Min(LL_COORD(a, i), UR_COORD(a, i)),
777  Min(LL_COORD(b, i), UR_COORD(b, i)));
778  result->x[i + DIM(a)] = Max(Max(LL_COORD(a, i), UR_COORD(a, i)),
779  Max(LL_COORD(b, i), UR_COORD(b, i)));
780  }
781  /* continue on the higher dimensions only present in 'a' */
782  for (; i < DIM(a); i++)
783  {
784  result->x[i] = Min(0,
785  Min(LL_COORD(a, i), UR_COORD(a, i))
786  );
787  result->x[i + dim] = Max(0,
788  Max(LL_COORD(a, i), UR_COORD(a, i))
789  );
790  }
791 
792  /*
793  * Check if the result was in fact a point, and set the flag in the datum
794  * accordingly. (we don't bother to repalloc it smaller)
795  */
796  if (cube_is_point_internal(result))
797  {
798  size = POINT_SIZE(dim);
799  SET_VARSIZE(result, size);
800  SET_POINT_BIT(result);
801  }
802 
803  return result;
804 }
805 
806 Datum
808 {
809  NDBOX *a = PG_GETARG_NDBOX_P(0);
810  NDBOX *b = PG_GETARG_NDBOX_P(1);
811  NDBOX *res;
812 
813  res = cube_union_v0(a, b);
814 
815  PG_FREE_IF_COPY(a, 0);
816  PG_FREE_IF_COPY(b, 1);
817  PG_RETURN_NDBOX_P(res);
818 }
819 
820 /* cube_inter */
821 Datum
823 {
824  NDBOX *a = PG_GETARG_NDBOX_P(0);
825  NDBOX *b = PG_GETARG_NDBOX_P(1);
826  NDBOX *result;
827  bool swapped = false;
828  int i;
829  int dim;
830  int size;
831 
832  /* swap the arguments if needed, so that 'a' is always larger than 'b' */
833  if (DIM(a) < DIM(b))
834  {
835  NDBOX *tmp = b;
836 
837  b = a;
838  a = tmp;
839  swapped = true;
840  }
841  dim = DIM(a);
842 
843  size = CUBE_SIZE(dim);
844  result = (NDBOX *) palloc0(size);
845  SET_VARSIZE(result, size);
846  SET_DIM(result, dim);
847 
848  /* First compute intersection of the dimensions present in both args */
849  for (i = 0; i < DIM(b); i++)
850  {
851  result->x[i] = Max(Min(LL_COORD(a, i), UR_COORD(a, i)),
852  Min(LL_COORD(b, i), UR_COORD(b, i)));
853  result->x[i + DIM(a)] = Min(Max(LL_COORD(a, i), UR_COORD(a, i)),
854  Max(LL_COORD(b, i), UR_COORD(b, i)));
855  }
856  /* continue on the higher dimensions only present in 'a' */
857  for (; i < DIM(a); i++)
858  {
859  result->x[i] = Max(0,
860  Min(LL_COORD(a, i), UR_COORD(a, i))
861  );
862  result->x[i + DIM(a)] = Min(0,
863  Max(LL_COORD(a, i), UR_COORD(a, i))
864  );
865  }
866 
867  /*
868  * Check if the result was in fact a point, and set the flag in the datum
869  * accordingly. (we don't bother to repalloc it smaller)
870  */
871  if (cube_is_point_internal(result))
872  {
873  size = POINT_SIZE(dim);
874  result = repalloc(result, size);
875  SET_VARSIZE(result, size);
876  SET_POINT_BIT(result);
877  }
878 
879  if (swapped)
880  {
881  PG_FREE_IF_COPY(b, 0);
882  PG_FREE_IF_COPY(a, 1);
883  }
884  else
885  {
886  PG_FREE_IF_COPY(a, 0);
887  PG_FREE_IF_COPY(b, 1);
888  }
889 
890  /*
891  * Is it OK to return a non-null intersection for non-overlapping boxes?
892  */
893  PG_RETURN_NDBOX_P(result);
894 }
895 
896 /* cube_size */
897 Datum
899 {
900  NDBOX *a = PG_GETARG_NDBOX_P(0);
901  double result;
902 
903  rt_cube_size(a, &result);
904  PG_FREE_IF_COPY(a, 0);
905  PG_RETURN_FLOAT8(result);
906 }
907 
908 void
909 rt_cube_size(NDBOX *a, double *size)
910 {
911  double result;
912  int i;
913 
914  if (a == (NDBOX *) NULL)
915  {
916  /* special case for GiST */
917  result = 0.0;
918  }
919  else if (IS_POINT(a) || DIM(a) == 0)
920  {
921  /* necessarily has zero size */
922  result = 0.0;
923  }
924  else
925  {
926  result = 1.0;
927  for (i = 0; i < DIM(a); i++)
928  result *= Abs(UR_COORD(a, i) - LL_COORD(a, i));
929  }
930  *size = result;
931 }
932 
933 /* make up a metric in which one box will be 'lower' than the other
934  -- this can be useful for sorting and to determine uniqueness */
935 int32
937 {
938  int i;
939  int dim;
940 
941  dim = Min(DIM(a), DIM(b));
942 
943  /* compare the common dimensions */
944  for (i = 0; i < dim; i++)
945  {
946  if (Min(LL_COORD(a, i), UR_COORD(a, i)) >
947  Min(LL_COORD(b, i), UR_COORD(b, i)))
948  return 1;
949  if (Min(LL_COORD(a, i), UR_COORD(a, i)) <
950  Min(LL_COORD(b, i), UR_COORD(b, i)))
951  return -1;
952  }
953  for (i = 0; i < dim; i++)
954  {
955  if (Max(LL_COORD(a, i), UR_COORD(a, i)) >
956  Max(LL_COORD(b, i), UR_COORD(b, i)))
957  return 1;
958  if (Max(LL_COORD(a, i), UR_COORD(a, i)) <
959  Max(LL_COORD(b, i), UR_COORD(b, i)))
960  return -1;
961  }
962 
963  /* compare extra dimensions to zero */
964  if (DIM(a) > DIM(b))
965  {
966  for (i = dim; i < DIM(a); i++)
967  {
968  if (Min(LL_COORD(a, i), UR_COORD(a, i)) > 0)
969  return 1;
970  if (Min(LL_COORD(a, i), UR_COORD(a, i)) < 0)
971  return -1;
972  }
973  for (i = dim; i < DIM(a); i++)
974  {
975  if (Max(LL_COORD(a, i), UR_COORD(a, i)) > 0)
976  return 1;
977  if (Max(LL_COORD(a, i), UR_COORD(a, i)) < 0)
978  return -1;
979  }
980 
981  /*
982  * if all common dimensions are equal, the cube with more dimensions
983  * wins
984  */
985  return 1;
986  }
987  if (DIM(a) < DIM(b))
988  {
989  for (i = dim; i < DIM(b); i++)
990  {
991  if (Min(LL_COORD(b, i), UR_COORD(b, i)) > 0)
992  return -1;
993  if (Min(LL_COORD(b, i), UR_COORD(b, i)) < 0)
994  return 1;
995  }
996  for (i = dim; i < DIM(b); i++)
997  {
998  if (Max(LL_COORD(b, i), UR_COORD(b, i)) > 0)
999  return -1;
1000  if (Max(LL_COORD(b, i), UR_COORD(b, i)) < 0)
1001  return 1;
1002  }
1003 
1004  /*
1005  * if all common dimensions are equal, the cube with more dimensions
1006  * wins
1007  */
1008  return -1;
1009  }
1010 
1011  /* They're really equal */
1012  return 0;
1013 }
1014 
1015 Datum
1017 {
1018  NDBOX *a = PG_GETARG_NDBOX_P(0),
1019  *b = PG_GETARG_NDBOX_P(1);
1020  int32 res;
1021 
1022  res = cube_cmp_v0(a, b);
1023 
1024  PG_FREE_IF_COPY(a, 0);
1025  PG_FREE_IF_COPY(b, 1);
1026  PG_RETURN_INT32(res);
1027 }
1028 
1029 
1030 Datum
1032 {
1033  NDBOX *a = PG_GETARG_NDBOX_P(0),
1034  *b = PG_GETARG_NDBOX_P(1);
1035  int32 res;
1036 
1037  res = cube_cmp_v0(a, b);
1038 
1039  PG_FREE_IF_COPY(a, 0);
1040  PG_FREE_IF_COPY(b, 1);
1041  PG_RETURN_BOOL(res == 0);
1042 }
1043 
1044 
1045 Datum
1047 {
1048  NDBOX *a = PG_GETARG_NDBOX_P(0),
1049  *b = PG_GETARG_NDBOX_P(1);
1050  int32 res;
1051 
1052  res = cube_cmp_v0(a, b);
1053 
1054  PG_FREE_IF_COPY(a, 0);
1055  PG_FREE_IF_COPY(b, 1);
1056  PG_RETURN_BOOL(res != 0);
1057 }
1058 
1059 
1060 Datum
1062 {
1063  NDBOX *a = PG_GETARG_NDBOX_P(0),
1064  *b = PG_GETARG_NDBOX_P(1);
1065  int32 res;
1066 
1067  res = cube_cmp_v0(a, b);
1068 
1069  PG_FREE_IF_COPY(a, 0);
1070  PG_FREE_IF_COPY(b, 1);
1071  PG_RETURN_BOOL(res < 0);
1072 }
1073 
1074 
1075 Datum
1077 {
1078  NDBOX *a = PG_GETARG_NDBOX_P(0),
1079  *b = PG_GETARG_NDBOX_P(1);
1080  int32 res;
1081 
1082  res = cube_cmp_v0(a, b);
1083 
1084  PG_FREE_IF_COPY(a, 0);
1085  PG_FREE_IF_COPY(b, 1);
1086  PG_RETURN_BOOL(res > 0);
1087 }
1088 
1089 
1090 Datum
1092 {
1093  NDBOX *a = PG_GETARG_NDBOX_P(0),
1094  *b = PG_GETARG_NDBOX_P(1);
1095  int32 res;
1096 
1097  res = cube_cmp_v0(a, b);
1098 
1099  PG_FREE_IF_COPY(a, 0);
1100  PG_FREE_IF_COPY(b, 1);
1101  PG_RETURN_BOOL(res <= 0);
1102 }
1103 
1104 
1105 Datum
1107 {
1108  NDBOX *a = PG_GETARG_NDBOX_P(0),
1109  *b = PG_GETARG_NDBOX_P(1);
1110  int32 res;
1111 
1112  res = cube_cmp_v0(a, b);
1113 
1114  PG_FREE_IF_COPY(a, 0);
1115  PG_FREE_IF_COPY(b, 1);
1116  PG_RETURN_BOOL(res >= 0);
1117 }
1118 
1119 
1120 /* Contains */
1121 /* Box(A) CONTAINS Box(B) IFF pt(A) < pt(B) */
1122 bool
1124 {
1125  int i;
1126 
1127  if ((a == NULL) || (b == NULL))
1128  return false;
1129 
1130  if (DIM(a) < DIM(b))
1131  {
1132  /*
1133  * the further comparisons will make sense if the excess dimensions of
1134  * (b) were zeroes Since both UL and UR coordinates must be zero, we
1135  * can check them all without worrying about which is which.
1136  */
1137  for (i = DIM(a); i < DIM(b); i++)
1138  {
1139  if (LL_COORD(b, i) != 0)
1140  return false;
1141  if (UR_COORD(b, i) != 0)
1142  return false;
1143  }
1144  }
1145 
1146  /* Can't care less about the excess dimensions of (a), if any */
1147  for (i = 0; i < Min(DIM(a), DIM(b)); i++)
1148  {
1149  if (Min(LL_COORD(a, i), UR_COORD(a, i)) >
1150  Min(LL_COORD(b, i), UR_COORD(b, i)))
1151  return false;
1152  if (Max(LL_COORD(a, i), UR_COORD(a, i)) <
1153  Max(LL_COORD(b, i), UR_COORD(b, i)))
1154  return false;
1155  }
1156 
1157  return true;
1158 }
1159 
1160 Datum
1162 {
1163  NDBOX *a = PG_GETARG_NDBOX_P(0),
1164  *b = PG_GETARG_NDBOX_P(1);
1165  bool res;
1166 
1167  res = cube_contains_v0(a, b);
1168 
1169  PG_FREE_IF_COPY(a, 0);
1170  PG_FREE_IF_COPY(b, 1);
1171  PG_RETURN_BOOL(res);
1172 }
1173 
1174 /* Contained */
1175 /* Box(A) Contained by Box(B) IFF Box(B) Contains Box(A) */
1176 Datum
1178 {
1179  NDBOX *a = PG_GETARG_NDBOX_P(0),
1180  *b = PG_GETARG_NDBOX_P(1);
1181  bool res;
1182 
1183  res = cube_contains_v0(b, a);
1184 
1185  PG_FREE_IF_COPY(a, 0);
1186  PG_FREE_IF_COPY(b, 1);
1187  PG_RETURN_BOOL(res);
1188 }
1189 
1190 /* Overlap */
1191 /* Box(A) Overlap Box(B) IFF (pt(a)LL < pt(B)UR) && (pt(b)LL < pt(a)UR) */
1192 bool
1194 {
1195  int i;
1196 
1197  if ((a == NULL) || (b == NULL))
1198  return false;
1199 
1200  /* swap the box pointers if needed */
1201  if (DIM(a) < DIM(b))
1202  {
1203  NDBOX *tmp = b;
1204 
1205  b = a;
1206  a = tmp;
1207  }
1208 
1209  /* compare within the dimensions of (b) */
1210  for (i = 0; i < DIM(b); i++)
1211  {
1212  if (Min(LL_COORD(a, i), UR_COORD(a, i)) > Max(LL_COORD(b, i), UR_COORD(b, i)))
1213  return false;
1214  if (Max(LL_COORD(a, i), UR_COORD(a, i)) < Min(LL_COORD(b, i), UR_COORD(b, i)))
1215  return false;
1216  }
1217 
1218  /* compare to zero those dimensions in (a) absent in (b) */
1219  for (i = DIM(b); i < DIM(a); i++)
1220  {
1221  if (Min(LL_COORD(a, i), UR_COORD(a, i)) > 0)
1222  return false;
1223  if (Max(LL_COORD(a, i), UR_COORD(a, i)) < 0)
1224  return false;
1225  }
1226 
1227  return true;
1228 }
1229 
1230 
1231 Datum
1233 {
1234  NDBOX *a = PG_GETARG_NDBOX_P(0),
1235  *b = PG_GETARG_NDBOX_P(1);
1236  bool res;
1237 
1238  res = cube_overlap_v0(a, b);
1239 
1240  PG_FREE_IF_COPY(a, 0);
1241  PG_FREE_IF_COPY(b, 1);
1242  PG_RETURN_BOOL(res);
1243 }
1244 
1245 
1246 /* Distance */
1247 /* The distance is computed as a per axis sum of the squared distances
1248  between 1D projections of the boxes onto Cartesian axes. Assuming zero
1249  distance between overlapping projections, this metric coincides with the
1250  "common sense" geometric distance */
1251 Datum
1253 {
1254  NDBOX *a = PG_GETARG_NDBOX_P(0),
1255  *b = PG_GETARG_NDBOX_P(1);
1256  bool swapped = false;
1257  double d,
1258  distance;
1259  int i;
1260 
1261  /* swap the box pointers if needed */
1262  if (DIM(a) < DIM(b))
1263  {
1264  NDBOX *tmp = b;
1265 
1266  b = a;
1267  a = tmp;
1268  swapped = true;
1269  }
1270 
1271  distance = 0.0;
1272  /* compute within the dimensions of (b) */
1273  for (i = 0; i < DIM(b); i++)
1274  {
1275  d = distance_1D(LL_COORD(a, i), UR_COORD(a, i), LL_COORD(b, i), UR_COORD(b, i));
1276  distance += d * d;
1277  }
1278 
1279  /* compute distance to zero for those dimensions in (a) absent in (b) */
1280  for (i = DIM(b); i < DIM(a); i++)
1281  {
1282  d = distance_1D(LL_COORD(a, i), UR_COORD(a, i), 0.0, 0.0);
1283  distance += d * d;
1284  }
1285 
1286  if (swapped)
1287  {
1288  PG_FREE_IF_COPY(b, 0);
1289  PG_FREE_IF_COPY(a, 1);
1290  }
1291  else
1292  {
1293  PG_FREE_IF_COPY(a, 0);
1294  PG_FREE_IF_COPY(b, 1);
1295  }
1296 
1297  PG_RETURN_FLOAT8(sqrt(distance));
1298 }
1299 
1300 Datum
1302 {
1303  NDBOX *a = PG_GETARG_NDBOX_P(0),
1304  *b = PG_GETARG_NDBOX_P(1);
1305  bool swapped = false;
1306  double distance;
1307  int i;
1308 
1309  /* swap the box pointers if needed */
1310  if (DIM(a) < DIM(b))
1311  {
1312  NDBOX *tmp = b;
1313 
1314  b = a;
1315  a = tmp;
1316  swapped = true;
1317  }
1318 
1319  distance = 0.0;
1320  /* compute within the dimensions of (b) */
1321  for (i = 0; i < DIM(b); i++)
1322  distance += fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1323  LL_COORD(b, i), UR_COORD(b, i)));
1324 
1325  /* compute distance to zero for those dimensions in (a) absent in (b) */
1326  for (i = DIM(b); i < DIM(a); i++)
1327  distance += fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1328  0.0, 0.0));
1329 
1330  if (swapped)
1331  {
1332  PG_FREE_IF_COPY(b, 0);
1333  PG_FREE_IF_COPY(a, 1);
1334  }
1335  else
1336  {
1337  PG_FREE_IF_COPY(a, 0);
1338  PG_FREE_IF_COPY(b, 1);
1339  }
1340 
1341  PG_RETURN_FLOAT8(distance);
1342 }
1343 
1344 Datum
1346 {
1347  NDBOX *a = PG_GETARG_NDBOX_P(0),
1348  *b = PG_GETARG_NDBOX_P(1);
1349  bool swapped = false;
1350  double d,
1351  distance;
1352  int i;
1353 
1354  /* swap the box pointers if needed */
1355  if (DIM(a) < DIM(b))
1356  {
1357  NDBOX *tmp = b;
1358 
1359  b = a;
1360  a = tmp;
1361  swapped = true;
1362  }
1363 
1364  distance = 0.0;
1365  /* compute within the dimensions of (b) */
1366  for (i = 0; i < DIM(b); i++)
1367  {
1368  d = fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i),
1369  LL_COORD(b, i), UR_COORD(b, i)));
1370  if (d > distance)
1371  distance = d;
1372  }
1373 
1374  /* compute distance to zero for those dimensions in (a) absent in (b) */
1375  for (i = DIM(b); i < DIM(a); i++)
1376  {
1377  d = fabs(distance_1D(LL_COORD(a, i), UR_COORD(a, i), 0.0, 0.0));
1378  if (d > distance)
1379  distance = d;
1380  }
1381 
1382  if (swapped)
1383  {
1384  PG_FREE_IF_COPY(b, 0);
1385  PG_FREE_IF_COPY(a, 1);
1386  }
1387  else
1388  {
1389  PG_FREE_IF_COPY(a, 0);
1390  PG_FREE_IF_COPY(b, 1);
1391  }
1392 
1393  PG_RETURN_FLOAT8(distance);
1394 }
1395 
1396 Datum
1398 {
1399  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1401  NDBOX *cube = DatumGetNDBOXP(entry->key);
1402  double retval;
1403 
1404  if (strategy == CubeKNNDistanceCoord)
1405  {
1406  /*
1407  * Handle ordering by ~> operator. See comments of cube_coord_llur()
1408  * for details
1409  */
1410  int coord = PG_GETARG_INT32(1);
1411  bool isLeaf = GistPageIsLeaf(entry->page);
1412  bool inverse = false;
1413 
1414  /* 0 is the only unsupported coordinate value */
1415  if (coord == 0)
1416  ereport(ERROR,
1417  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1418  errmsg("zero cube index is not defined")));
1419 
1420  /* Return inversed value for negative coordinate */
1421  if (coord < 0)
1422  {
1423  coord = -coord;
1424  inverse = true;
1425  }
1426 
1427  if (coord <= 2 * DIM(cube))
1428  {
1429  /* dimension index */
1430  int index = (coord - 1) / 2;
1431 
1432  /* whether this is upper bound (lower bound otherwise) */
1433  bool upper = ((coord - 1) % 2 == 1);
1434 
1435  if (IS_POINT(cube))
1436  {
1437  retval = cube->x[index];
1438  }
1439  else
1440  {
1441  if (isLeaf)
1442  {
1443  /* For leaf just return required upper/lower bound */
1444  if (upper)
1445  retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1446  else
1447  retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1448  }
1449  else
1450  {
1451  /*
1452  * For non-leaf we should always return lower bound,
1453  * because even upper bound of a child in the subtree can
1454  * be as small as our lower bound. For inversed case we
1455  * return upper bound because it becomes lower bound for
1456  * inversed value.
1457  */
1458  if (!inverse)
1459  retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1460  else
1461  retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1462  }
1463  }
1464  }
1465  else
1466  {
1467  retval = 0.0;
1468  }
1469 
1470  /* Inverse return value if needed */
1471  if (inverse)
1472  retval = -retval;
1473  }
1474  else
1475  {
1476  NDBOX *query = PG_GETARG_NDBOX_P(1);
1477 
1478  switch (strategy)
1479  {
1482  PointerGetDatum(cube), PointerGetDatum(query)));
1483  break;
1484  case CubeKNNDistanceEuclid:
1486  PointerGetDatum(cube), PointerGetDatum(query)));
1487  break;
1490  PointerGetDatum(cube), PointerGetDatum(query)));
1491  break;
1492  default:
1493  elog(ERROR, "unrecognized cube strategy number: %d", strategy);
1494  retval = 0; /* keep compiler quiet */
1495  break;
1496  }
1497  }
1498  PG_RETURN_FLOAT8(retval);
1499 }
1500 
1501 static double
1502 distance_1D(double a1, double a2, double b1, double b2)
1503 {
1504  /* interval (a) is entirely on the left of (b) */
1505  if ((a1 <= b1) && (a2 <= b1) && (a1 <= b2) && (a2 <= b2))
1506  return (Min(b1, b2) - Max(a1, a2));
1507 
1508  /* interval (a) is entirely on the right of (b) */
1509  if ((a1 > b1) && (a2 > b1) && (a1 > b2) && (a2 > b2))
1510  return (Min(a1, a2) - Max(b1, b2));
1511 
1512  /* the rest are all sorts of intersections */
1513  return 0.0;
1514 }
1515 
1516 /* Test if a box is also a point */
1517 Datum
1519 {
1520  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1521  bool result;
1522 
1523  result = cube_is_point_internal(cube);
1524  PG_FREE_IF_COPY(cube, 0);
1525  PG_RETURN_BOOL(result);
1526 }
1527 
1528 static bool
1530 {
1531  int i;
1532 
1533  if (IS_POINT(cube))
1534  return true;
1535 
1536  /*
1537  * Even if the point-flag is not set, all the lower-left coordinates might
1538  * match the upper-right coordinates, so that the value is in fact a
1539  * point. Such values don't arise with current code - the point flag is
1540  * always set if appropriate - but they might be present on-disk in
1541  * clusters upgraded from pre-9.4 versions.
1542  */
1543  for (i = 0; i < DIM(cube); i++)
1544  {
1545  if (LL_COORD(cube, i) != UR_COORD(cube, i))
1546  return false;
1547  }
1548  return true;
1549 }
1550 
1551 /* Return dimensions in use in the data structure */
1552 Datum
1554 {
1555  NDBOX *c = PG_GETARG_NDBOX_P(0);
1556  int dim = DIM(c);
1557 
1558  PG_FREE_IF_COPY(c, 0);
1559  PG_RETURN_INT32(dim);
1560 }
1561 
1562 /* Return a specific normalized LL coordinate */
1563 Datum
1565 {
1566  NDBOX *c = PG_GETARG_NDBOX_P(0);
1567  int n = PG_GETARG_INT32(1);
1568  double result;
1569 
1570  if (DIM(c) >= n && n > 0)
1571  result = Min(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
1572  else
1573  result = 0;
1574 
1575  PG_FREE_IF_COPY(c, 0);
1576  PG_RETURN_FLOAT8(result);
1577 }
1578 
1579 /* Return a specific normalized UR coordinate */
1580 Datum
1582 {
1583  NDBOX *c = PG_GETARG_NDBOX_P(0);
1584  int n = PG_GETARG_INT32(1);
1585  double result;
1586 
1587  if (DIM(c) >= n && n > 0)
1588  result = Max(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
1589  else
1590  result = 0;
1591 
1592  PG_FREE_IF_COPY(c, 0);
1593  PG_RETURN_FLOAT8(result);
1594 }
1595 
1596 /*
1597  * Function returns cube coordinate.
1598  * Numbers from 1 to DIM denotes first corner coordinates.
1599  * Numbers from DIM+1 to 2*DIM denotes second corner coordinates.
1600  */
1601 Datum
1603 {
1604  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1605  int coord = PG_GETARG_INT32(1);
1606 
1607  if (coord <= 0 || coord > 2 * DIM(cube))
1608  ereport(ERROR,
1609  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1610  errmsg("cube index %d is out of bounds", coord)));
1611 
1612  if (IS_POINT(cube))
1613  PG_RETURN_FLOAT8(cube->x[(coord - 1) % DIM(cube)]);
1614  else
1615  PG_RETURN_FLOAT8(cube->x[coord - 1]);
1616 }
1617 
1618 
1619 /*----
1620  * This function works like cube_coord(), but rearranges coordinates in the
1621  * way suitable to support coordinate ordering using KNN-GiST. For historical
1622  * reasons this extension allows us to create cubes in form ((2,1),(1,2)) and
1623  * instead of normalizing such cube to ((1,1),(2,2)) it stores cube in original
1624  * way. But in order to get cubes ordered by one of dimensions from the index
1625  * without explicit sort step we need this representation-independent coordinate
1626  * getter. Moreover, indexed dataset may contain cubes of different dimensions
1627  * number. Accordingly, this coordinate getter should be able to return
1628  * lower/upper bound for particular dimension independently on number of cube
1629  * dimensions. Also, KNN-GiST supports only ascending sorting. In order to
1630  * support descending sorting, this function returns inverse of value when
1631  * negative coordinate is given.
1632  *
1633  * Long story short, this function uses following meaning of coordinates:
1634  * # (2 * N - 1) -- lower bound of Nth dimension,
1635  * # (2 * N) -- upper bound of Nth dimension,
1636  * # - (2 * N - 1) -- negative of lower bound of Nth dimension,
1637  * # - (2 * N) -- negative of upper bound of Nth dimension.
1638  *
1639  * When given coordinate exceeds number of cube dimensions, then 0 returned
1640  * (reproducing logic of GiST indexing of variable-length cubes).
1641  */
1642 Datum
1644 {
1645  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1646  int coord = PG_GETARG_INT32(1);
1647  bool inverse = false;
1648  float8 result;
1649 
1650  /* 0 is the only unsupported coordinate value */
1651  if (coord == 0)
1652  ereport(ERROR,
1653  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1654  errmsg("zero cube index is not defined")));
1655 
1656  /* Return inversed value for negative coordinate */
1657  if (coord < 0)
1658  {
1659  coord = -coord;
1660  inverse = true;
1661  }
1662 
1663  if (coord <= 2 * DIM(cube))
1664  {
1665  /* dimension index */
1666  int index = (coord - 1) / 2;
1667 
1668  /* whether this is upper bound (lower bound otherwise) */
1669  bool upper = ((coord - 1) % 2 == 1);
1670 
1671  if (IS_POINT(cube))
1672  {
1673  result = cube->x[index];
1674  }
1675  else
1676  {
1677  if (upper)
1678  result = Max(cube->x[index], cube->x[index + DIM(cube)]);
1679  else
1680  result = Min(cube->x[index], cube->x[index + DIM(cube)]);
1681  }
1682  }
1683  else
1684  {
1685  /*
1686  * Return zero if coordinate is out of bound. That reproduces logic
1687  * of how cubes with low dimension number are expanded during GiST
1688  * indexing.
1689  */
1690  result = 0.0;
1691  }
1692 
1693  /* Inverse value if needed */
1694  if (inverse)
1695  result = -result;
1696 
1697  PG_RETURN_FLOAT8(result);
1698 }
1699 
1700 /* Increase or decrease box size by a radius in at least n dimensions. */
1701 Datum
1703 {
1704  NDBOX *a = PG_GETARG_NDBOX_P(0);
1705  double r = PG_GETARG_FLOAT8(1);
1706  int32 n = PG_GETARG_INT32(2);
1707  NDBOX *result;
1708  int dim = 0;
1709  int size;
1710  int i,
1711  j;
1712 
1713  if (n > CUBE_MAX_DIM)
1714  n = CUBE_MAX_DIM;
1715  if (r > 0 && n > 0)
1716  dim = n;
1717  if (DIM(a) > dim)
1718  dim = DIM(a);
1719 
1720  size = CUBE_SIZE(dim);
1721  result = (NDBOX *) palloc0(size);
1722  SET_VARSIZE(result, size);
1723  SET_DIM(result, dim);
1724 
1725  for (i = 0, j = dim; i < DIM(a); i++, j++)
1726  {
1727  if (LL_COORD(a, i) >= UR_COORD(a, i))
1728  {
1729  result->x[i] = UR_COORD(a, i) - r;
1730  result->x[j] = LL_COORD(a, i) + r;
1731  }
1732  else
1733  {
1734  result->x[i] = LL_COORD(a, i) - r;
1735  result->x[j] = UR_COORD(a, i) + r;
1736  }
1737  if (result->x[i] > result->x[j])
1738  {
1739  result->x[i] = (result->x[i] + result->x[j]) / 2;
1740  result->x[j] = result->x[i];
1741  }
1742  }
1743  /* dim > a->dim only if r > 0 */
1744  for (; i < dim; i++, j++)
1745  {
1746  result->x[i] = -r;
1747  result->x[j] = r;
1748  }
1749 
1750  /*
1751  * Check if the result was in fact a point, and set the flag in the datum
1752  * accordingly. (we don't bother to repalloc it smaller)
1753  */
1754  if (cube_is_point_internal(result))
1755  {
1756  size = POINT_SIZE(dim);
1757  SET_VARSIZE(result, size);
1758  SET_POINT_BIT(result);
1759  }
1760 
1761  PG_FREE_IF_COPY(a, 0);
1762  PG_RETURN_NDBOX_P(result);
1763 }
1764 
1765 /* Create a one dimensional box with identical upper and lower coordinates */
1766 Datum
1768 {
1769  double x = PG_GETARG_FLOAT8(0);
1770  NDBOX *result;
1771  int size;
1772 
1773  size = POINT_SIZE(1);
1774  result = (NDBOX *) palloc0(size);
1775  SET_VARSIZE(result, size);
1776  SET_DIM(result, 1);
1777  SET_POINT_BIT(result);
1778  result->x[0] = x;
1779 
1780  PG_RETURN_NDBOX_P(result);
1781 }
1782 
1783 /* Create a one dimensional box */
1784 Datum
1786 {
1787  double x0 = PG_GETARG_FLOAT8(0);
1788  double x1 = PG_GETARG_FLOAT8(1);
1789  NDBOX *result;
1790  int size;
1791 
1792  if (x0 == x1)
1793  {
1794  size = POINT_SIZE(1);
1795  result = (NDBOX *) palloc0(size);
1796  SET_VARSIZE(result, size);
1797  SET_DIM(result, 1);
1798  SET_POINT_BIT(result);
1799  result->x[0] = x0;
1800  }
1801  else
1802  {
1803  size = CUBE_SIZE(1);
1804  result = (NDBOX *) palloc0(size);
1805  SET_VARSIZE(result, size);
1806  SET_DIM(result, 1);
1807  result->x[0] = x0;
1808  result->x[1] = x1;
1809  }
1810 
1811  PG_RETURN_NDBOX_P(result);
1812 }
1813 
1814 /* Add a dimension to an existing cube with the same values for the new
1815  coordinate */
1816 Datum
1818 {
1819  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1820  double x = PG_GETARG_FLOAT8(1);
1821  NDBOX *result;
1822  int size;
1823  int i;
1824 
1825  if (DIM(cube) + 1 > CUBE_MAX_DIM)
1826  ereport(ERROR,
1827  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1828  errmsg("can't extend cube"),
1829  errdetail("A cube cannot have more than %d dimensions.",
1830  CUBE_MAX_DIM)));
1831 
1832  if (IS_POINT(cube))
1833  {
1834  size = POINT_SIZE((DIM(cube) + 1));
1835  result = (NDBOX *) palloc0(size);
1836  SET_VARSIZE(result, size);
1837  SET_DIM(result, DIM(cube) + 1);
1838  SET_POINT_BIT(result);
1839  for (i = 0; i < DIM(cube); i++)
1840  result->x[i] = cube->x[i];
1841  result->x[DIM(result) - 1] = x;
1842  }
1843  else
1844  {
1845  size = CUBE_SIZE((DIM(cube) + 1));
1846  result = (NDBOX *) palloc0(size);
1847  SET_VARSIZE(result, size);
1848  SET_DIM(result, DIM(cube) + 1);
1849  for (i = 0; i < DIM(cube); i++)
1850  {
1851  result->x[i] = cube->x[i];
1852  result->x[DIM(result) + i] = cube->x[DIM(cube) + i];
1853  }
1854  result->x[DIM(result) - 1] = x;
1855  result->x[2 * DIM(result) - 1] = x;
1856  }
1857 
1858  PG_FREE_IF_COPY(cube, 0);
1859  PG_RETURN_NDBOX_P(result);
1860 }
1861 
1862 /* Add a dimension to an existing cube */
1863 Datum
1865 {
1866  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1867  double x1 = PG_GETARG_FLOAT8(1);
1868  double x2 = PG_GETARG_FLOAT8(2);
1869  NDBOX *result;
1870  int size;
1871  int i;
1872 
1873  if (DIM(cube) + 1 > CUBE_MAX_DIM)
1874  ereport(ERROR,
1875  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1876  errmsg("can't extend cube"),
1877  errdetail("A cube cannot have more than %d dimensions.",
1878  CUBE_MAX_DIM)));
1879 
1880  if (IS_POINT(cube) && (x1 == x2))
1881  {
1882  size = POINT_SIZE((DIM(cube) + 1));
1883  result = (NDBOX *) palloc0(size);
1884  SET_VARSIZE(result, size);
1885  SET_DIM(result, DIM(cube) + 1);
1886  SET_POINT_BIT(result);
1887  for (i = 0; i < DIM(cube); i++)
1888  result->x[i] = cube->x[i];
1889  result->x[DIM(result) - 1] = x1;
1890  }
1891  else
1892  {
1893  size = CUBE_SIZE((DIM(cube) + 1));
1894  result = (NDBOX *) palloc0(size);
1895  SET_VARSIZE(result, size);
1896  SET_DIM(result, DIM(cube) + 1);
1897  for (i = 0; i < DIM(cube); i++)
1898  {
1899  result->x[i] = LL_COORD(cube, i);
1900  result->x[DIM(result) + i] = UR_COORD(cube, i);
1901  }
1902  result->x[DIM(result) - 1] = x1;
1903  result->x[2 * DIM(result) - 1] = x2;
1904  }
1905 
1906  PG_FREE_IF_COPY(cube, 0);
1907  PG_RETURN_NDBOX_P(result);
1908 }
Datum cube_lt(PG_FUNCTION_ARGS)
Definition: cube.c:1061
#define GIST_LEAF(entry)
Definition: gist.h:170
Relation rel
Definition: gist.h:161
#define PG_GETARG_FLOAT8(n)
Definition: fmgr.h:282
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
int32 cube_cmp_v0(NDBOX *a, NDBOX *b)
Definition: cube.c:936
Datum cube_distance(PG_FUNCTION_ARGS)
Definition: cube.c:1252
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
Datum cube_ne(PG_FUNCTION_ARGS)
Definition: cube.c:1046
unsigned int header
Definition: cubedata.h:27
Datum cube_dim(PG_FUNCTION_ARGS)
Definition: cube.c:1553
#define RTOldContainsStrategyNumber
Definition: stratnum.h:63
Datum distance_chebyshev(PG_FUNCTION_ARGS)
Definition: cube.c:1345
Datum cube_c_f8(PG_FUNCTION_ARGS)
Definition: cube.c:1817
#define RTOldContainedByStrategyNumber
Definition: stratnum.h:64
char * float8out_internal(double num)
Definition: float.c:541
#define CubeKNNDistanceTaxicab
Definition: cubedata.h:58
#define DatumGetNDBOXP(x)
Definition: cubedata.h:52
#define VARSIZE(PTR)
Definition: postgres.h:316
Datum g_cube_distance(PG_FUNCTION_ARGS)
Definition: cube.c:1397
bool g_cube_leaf_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy)
Definition: cube.c:678
#define PointerGetDatum(X)
Definition: postgres.h:600
#define DIM(cube)
Definition: cubedata.h:42
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
void pq_begintypsend(StringInfo buf)
Definition: pqformat.c:328
#define CubeKNNDistanceEuclid
Definition: cubedata.h:59
Datum cube_cmp(PG_FUNCTION_ARGS)
Definition: cube.c:1016
Datum cube_a_f8_f8(PG_FUNCTION_ARGS)
Definition: cube.c:138
Datum cube_subset(PG_FUNCTION_ARGS)
Definition: cube.c:242
void pq_sendfloat8(StringInfo buf, float8 f)
Definition: pqformat.c:278
StringInfoData * StringInfo
Definition: stringinfo.h:44
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
#define Min(x, y)
Definition: c.h:986
#define POINT_BIT
Definition: cubedata.h:37
OffsetNumber * spl_left
Definition: gist.h:142
Datum spl_rdatum
Definition: gist.h:149
#define PG_RETURN_INT32(x)
Definition: fmgr.h:354
int32 n
Definition: gist.h:235
PG_FUNCTION_INFO_V1(cube_in)
uint16 StrategyNumber
Definition: stratnum.h:22
int errcode(int sqlerrcode)
Definition: elog.c:698
bool g_cube_internal_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy)
Definition: cube.c:707
void cube_scanner_init(const char *str)
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:259
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_RETURN_BYTEA_P(x)
Definition: fmgr.h:371
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:77
int spl_nleft
Definition: gist.h:143
bool cube_overlap_v0(NDBOX *a, NDBOX *b)
Definition: cube.c:1193
Datum cube_f8(PG_FUNCTION_ARGS)
Definition: cube.c:1767
bytea * pq_endtypsend(StringInfo buf)
Definition: pqformat.c:348
#define PG_GETARG_NDBOX_P(x)
Definition: cubedata.h:53
Datum g_cube_compress(PG_FUNCTION_ARGS)
Definition: cube.c:456
Datum cube_enlarge(PG_FUNCTION_ARGS)
Definition: cube.c:1702
Datum cube_ll_coord(PG_FUNCTION_ARGS)
Definition: cube.c:1564
signed int int32
Definition: c.h:429
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:162
#define Abs(x)
Definition: c.h:992
Definition: type.h:89
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:236
static void pq_sendint32(StringInfo buf, uint32 i)
Definition: pqformat.h:145
#define CUBE_MAX_DIM
Definition: cubedata.h:7
Datum distance_taxicab(PG_FUNCTION_ARGS)
Definition: cube.c:1301
static const FormData_pg_attribute a2
Definition: heap.c:167
#define PG_GETARG_ARRAYTYPE_P(n)
Definition: array.h:256
static double distance_1D(double a1, double a2, double b1, double b2)
Definition: cube.c:1502
Datum cube_size(PG_FUNCTION_ARGS)
Definition: cube.c:898
#define CubeKNNDistanceChebyshev
Definition: cubedata.h:60
#define ERROR
Definition: elog.h:46
double float8
Definition: c.h:565
int spl_nright
Definition: gist.h:148
void cube_scanner_finish(void)
#define LL_COORD(cube, i)
Definition: cubedata.h:45
Datum cube_contains(PG_FUNCTION_ARGS)
Definition: cube.c:1161
Datum g_cube_penalty(PG_FUNCTION_ARGS)
Definition: cube.c:485
void cube_yyerror(NDBOX **result, const char *message) pg_attribute_noreturn()
Datum cube_union(PG_FUNCTION_ARGS)
Definition: cube.c:807
Datum key
Definition: gist.h:160
void appendStringInfoString(StringInfo str, const char *s)
Definition: stringinfo.c:176
#define ARR_DATA_PTR(a)
Definition: array.h:315
Datum g_cube_picksplit(PG_FUNCTION_ARGS)
Definition: cube.c:510
Datum cube_inter(PG_FUNCTION_ARGS)
Definition: cube.c:822
char * c
static char * buf
Definition: pg_test_fsync.c:68
#define FirstOffsetNumber
Definition: off.h:27
int errdetail(const char *fmt,...)
Definition: elog.c:1042
#define RTSameStrategyNumber
Definition: stratnum.h:56
#define IS_POINT(cube)
Definition: cubedata.h:40
Datum cube_coord(PG_FUNCTION_ARGS)
Definition: cube.c:1602
Datum cube_recv(PG_FUNCTION_ARGS)
Definition: cube.c:351
Datum cube_a_f8(PG_FUNCTION_ARGS)
Definition: cube.c:205
Datum g_cube_same(PG_FUNCTION_ARGS)
Definition: cube.c:660
#define GistPageIsLeaf(page)
Definition: gist.h:169
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:188
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
NDBOX * g_cube_binary_union(NDBOX *r1, NDBOX *r2, int *sizep)
Definition: cube.c:734
void * palloc0(Size size)
Definition: mcxt.c:1093
Datum cube_f8_f8(PG_FUNCTION_ARGS)
Definition: cube.c:1785
void rt_cube_size(NDBOX *a, double *sz)
Definition: cube.c:909
#define DatumGetFloat8(X)
Definition: postgres.h:758
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
uintptr_t Datum
Definition: postgres.h:411
#define PG_RETURN_DATUM(x)
Definition: fmgr.h:353
Datum g_cube_decompress(PG_FUNCTION_ARGS)
Definition: cube.c:462
Datum cube_in(PG_FUNCTION_ARGS)
Definition: cube.c:118
#define ereport(elevel,...)
Definition: elog.h:157
Datum cube_is_point(PG_FUNCTION_ARGS)
Definition: cube.c:1518
Datum cube_send(PG_FUNCTION_ARGS)
Definition: cube.c:329
#define Max(x, y)
Definition: c.h:980
Datum cube_contained(PG_FUNCTION_ARGS)
Definition: cube.c:1177
Definition: cubedata.h:9
Datum spl_ldatum
Definition: gist.h:144
float8 pq_getmsgfloat8(StringInfo msg)
Definition: pqformat.c:490
Datum cube_out(PG_FUNCTION_ARGS)
Definition: cube.c:291
Datum cube_c_f8_f8(PG_FUNCTION_ARGS)
Definition: cube.c:1864
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:244
#define PG_RETURN_NDBOX_P(x)
Definition: cubedata.h:54
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
double x[FLEXIBLE_ARRAY_MEMBER]
Definition: cubedata.h:33
OffsetNumber * spl_right
Definition: gist.h:147
#define POINT_SIZE(_dim)
Definition: cubedata.h:48
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define RTContainsStrategyNumber
Definition: stratnum.h:57
#define DIM_MASK
Definition: cubedata.h:38
#define ARRNELEMS(x)
Definition: cube.c:26
static void header(const char *fmt,...) pg_attribute_printf(1
Definition: pg_regress.c:210
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1182
Datum cube_le(PG_FUNCTION_ARGS)
Definition: cube.c:1091
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272
NDBOX * cube_union_v0(NDBOX *a, NDBOX *b)
Definition: cube.c:747
int cube_yyparse(NDBOX **result)
void * palloc(Size size)
Definition: mcxt.c:1062
int errmsg(const char *fmt,...)
Definition: elog.c:909
#define elog(elevel,...)
Definition: elog.h:232
#define SET_POINT_BIT(cube)
Definition: cubedata.h:41
int i
#define SET_DIM(cube, _dim)
Definition: cubedata.h:43
Datum cube_overlap(PG_FUNCTION_ARGS)
Definition: cube.c:1232
PG_MODULE_MAGIC
Definition: cube.c:20
Datum cube_ge(PG_FUNCTION_ARGS)
Definition: cube.c:1106
#define PG_GETARG_CSTRING(n)
Definition: fmgr.h:277
#define CUBE_SIZE(_dim)
Definition: cubedata.h:49
#define RTOverlapStrategyNumber
Definition: stratnum.h:53
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
unsigned int pq_getmsgint(StringInfo msg, int b)
Definition: pqformat.c:417
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:342
#define ARRPTR(x)
Definition: cube.c:25
#define CubeKNNDistanceCoord
Definition: cubedata.h:57
static const FormData_pg_attribute a1
Definition: heap.c:153
static bool cube_is_point_internal(NDBOX *cube)
Definition: cube.c:1529
Datum cube_coord_llur(PG_FUNCTION_ARGS)
Definition: cube.c:1643
#define UR_COORD(cube, i)
Definition: cubedata.h:46
bool array_contains_nulls(ArrayType *array)
Definition: arrayfuncs.c:3557
OffsetNumber offset
Definition: gist.h:163
bool cube_contains_v0(NDBOX *a, NDBOX *b)
Definition: cube.c:1123
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:628
#define offsetof(type, field)
Definition: c.h:727
Datum cube_eq(PG_FUNCTION_ARGS)
Definition: cube.c:1031
unsigned char bool
Definition: c.h:391
Datum cube_gt(PG_FUNCTION_ARGS)
Definition: cube.c:1076
Datum g_cube_union(PG_FUNCTION_ARGS)
Definition: cube.c:424
Datum cube_ur_coord(PG_FUNCTION_ARGS)
Definition: cube.c:1581
Datum g_cube_consistent(PG_FUNCTION_ARGS)
Definition: cube.c:390