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