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