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