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 <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  /*
1341  * Handle ordering by ~> operator. See comments of cube_coord_llur()
1342  * for details
1343  */
1344  int coord = PG_GETARG_INT32(1);
1345  bool isLeaf = GistPageIsLeaf(entry->page);
1346  bool inverse = false;
1347 
1348  /* 0 is the only unsupported coordinate value */
1349  if (coord == 0)
1350  ereport(ERROR,
1351  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1352  errmsg("zero cube index is not defined")));
1353 
1354  /* Return inversed value for negative coordinate */
1355  if (coord < 0)
1356  {
1357  coord = -coord;
1358  inverse = true;
1359  }
1360 
1361  if (coord <= 2 * DIM(cube))
1362  {
1363  /* dimension index */
1364  int index = (coord - 1) / 2;
1365 
1366  /* whether this is upper bound (lower bound otherwise) */
1367  bool upper = ((coord - 1) % 2 == 1);
1368 
1369  if (IS_POINT(cube))
1370  {
1371  retval = cube->x[index];
1372  }
1373  else
1374  {
1375  if (isLeaf)
1376  {
1377  /* For leaf just return required upper/lower bound */
1378  if (upper)
1379  retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1380  else
1381  retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1382  }
1383  else
1384  {
1385  /*
1386  * For non-leaf we should always return lower bound,
1387  * because even upper bound of a child in the subtree can
1388  * be as small as our lower bound. For inversed case we
1389  * return upper bound because it becomes lower bound for
1390  * inversed value.
1391  */
1392  if (!inverse)
1393  retval = Min(cube->x[index], cube->x[index + DIM(cube)]);
1394  else
1395  retval = Max(cube->x[index], cube->x[index + DIM(cube)]);
1396  }
1397  }
1398  }
1399  else
1400  {
1401  retval = 0.0;
1402  }
1403 
1404  /* Inverse return value if needed */
1405  if (inverse)
1406  retval = -retval;
1407  }
1408  else
1409  {
1410  NDBOX *query = PG_GETARG_NDBOX_P(1);
1411 
1412  switch (strategy)
1413  {
1416  PointerGetDatum(cube), PointerGetDatum(query)));
1417  break;
1418  case CubeKNNDistanceEuclid:
1420  PointerGetDatum(cube), PointerGetDatum(query)));
1421  break;
1424  PointerGetDatum(cube), PointerGetDatum(query)));
1425  break;
1426  default:
1427  elog(ERROR, "unrecognized cube strategy number: %d", strategy);
1428  retval = 0; /* keep compiler quiet */
1429  break;
1430  }
1431  }
1432  PG_RETURN_FLOAT8(retval);
1433 }
1434 
1435 static double
1436 distance_1D(double a1, double a2, double b1, double b2)
1437 {
1438  /* interval (a) is entirely on the left of (b) */
1439  if ((a1 <= b1) && (a2 <= b1) && (a1 <= b2) && (a2 <= b2))
1440  return (Min(b1, b2) - Max(a1, a2));
1441 
1442  /* interval (a) is entirely on the right of (b) */
1443  if ((a1 > b1) && (a2 > b1) && (a1 > b2) && (a2 > b2))
1444  return (Min(a1, a2) - Max(b1, b2));
1445 
1446  /* the rest are all sorts of intersections */
1447  return 0.0;
1448 }
1449 
1450 /* Test if a box is also a point */
1451 Datum
1453 {
1454  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1455  bool result;
1456 
1457  result = cube_is_point_internal(cube);
1458  PG_FREE_IF_COPY(cube, 0);
1459  PG_RETURN_BOOL(result);
1460 }
1461 
1462 static bool
1464 {
1465  int i;
1466 
1467  if (IS_POINT(cube))
1468  return true;
1469 
1470  /*
1471  * Even if the point-flag is not set, all the lower-left coordinates might
1472  * match the upper-right coordinates, so that the value is in fact a
1473  * point. Such values don't arise with current code - the point flag is
1474  * always set if appropriate - but they might be present on-disk in
1475  * clusters upgraded from pre-9.4 versions.
1476  */
1477  for (i = 0; i < DIM(cube); i++)
1478  {
1479  if (LL_COORD(cube, i) != UR_COORD(cube, i))
1480  return false;
1481  }
1482  return true;
1483 }
1484 
1485 /* Return dimensions in use in the data structure */
1486 Datum
1488 {
1489  NDBOX *c = PG_GETARG_NDBOX_P(0);
1490  int dim = DIM(c);
1491 
1492  PG_FREE_IF_COPY(c, 0);
1493  PG_RETURN_INT32(dim);
1494 }
1495 
1496 /* Return a specific normalized LL coordinate */
1497 Datum
1499 {
1500  NDBOX *c = PG_GETARG_NDBOX_P(0);
1501  int n = PG_GETARG_INT32(1);
1502  double result;
1503 
1504  if (DIM(c) >= n && n > 0)
1505  result = Min(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
1506  else
1507  result = 0;
1508 
1509  PG_FREE_IF_COPY(c, 0);
1510  PG_RETURN_FLOAT8(result);
1511 }
1512 
1513 /* Return a specific normalized UR coordinate */
1514 Datum
1516 {
1517  NDBOX *c = PG_GETARG_NDBOX_P(0);
1518  int n = PG_GETARG_INT32(1);
1519  double result;
1520 
1521  if (DIM(c) >= n && n > 0)
1522  result = Max(LL_COORD(c, n - 1), UR_COORD(c, n - 1));
1523  else
1524  result = 0;
1525 
1526  PG_FREE_IF_COPY(c, 0);
1527  PG_RETURN_FLOAT8(result);
1528 }
1529 
1530 /*
1531  * Function returns cube coordinate.
1532  * Numbers from 1 to DIM denotes first corner coordinates.
1533  * Numbers from DIM+1 to 2*DIM denotes second corner coordinates.
1534  */
1535 Datum
1537 {
1538  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1539  int coord = PG_GETARG_INT32(1);
1540 
1541  if (coord <= 0 || coord > 2 * DIM(cube))
1542  ereport(ERROR,
1543  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1544  errmsg("cube index %d is out of bounds", coord)));
1545 
1546  if (IS_POINT(cube))
1547  PG_RETURN_FLOAT8(cube->x[(coord - 1) % DIM(cube)]);
1548  else
1549  PG_RETURN_FLOAT8(cube->x[coord - 1]);
1550 }
1551 
1552 
1553 /*----
1554  * This function works like cube_coord(), but rearranges coordinates in the
1555  * way suitable to support coordinate ordering using KNN-GiST. For historical
1556  * reasons this extension allows us to create cubes in form ((2,1),(1,2)) and
1557  * instead of normalizing such cube to ((1,1),(2,2)) it stores cube in original
1558  * way. But in order to get cubes ordered by one of dimensions from the index
1559  * without explicit sort step we need this representation-independent coordinate
1560  * getter. Moreover, indexed dataset may contain cubes of different dimensions
1561  * number. Accordingly, this coordinate getter should be able to return
1562  * lower/upper bound for particular dimension independently on number of cube
1563  * dimensions. Also, KNN-GiST supports only ascending sorting. In order to
1564  * support descending sorting, this function returns inverse of value when
1565  * negative coordinate is given.
1566  *
1567  * Long story short, this function uses following meaning of coordinates:
1568  * # (2 * N - 1) -- lower bound of Nth dimension,
1569  * # (2 * N) -- upper bound of Nth dimension,
1570  * # - (2 * N - 1) -- negative of lower bound of Nth dimension,
1571  * # - (2 * N) -- negative of upper bound of Nth dimension.
1572  *
1573  * When given coordinate exceeds number of cube dimensions, then 0 returned
1574  * (reproducing logic of GiST indexing of variable-length cubes).
1575  */
1576 Datum
1578 {
1579  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1580  int coord = PG_GETARG_INT32(1);
1581  bool inverse = false;
1582  float8 result;
1583 
1584  /* 0 is the only unsupported coordinate value */
1585  if (coord == 0)
1586  ereport(ERROR,
1587  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
1588  errmsg("zero cube index is not defined")));
1589 
1590  /* Return inversed value for negative coordinate */
1591  if (coord < 0)
1592  {
1593  coord = -coord;
1594  inverse = true;
1595  }
1596 
1597  if (coord <= 2 * DIM(cube))
1598  {
1599  /* dimension index */
1600  int index = (coord - 1) / 2;
1601 
1602  /* whether this is upper bound (lower bound otherwise) */
1603  bool upper = ((coord - 1) % 2 == 1);
1604 
1605  if (IS_POINT(cube))
1606  {
1607  result = cube->x[index];
1608  }
1609  else
1610  {
1611  if (upper)
1612  result = Max(cube->x[index], cube->x[index + DIM(cube)]);
1613  else
1614  result = Min(cube->x[index], cube->x[index + DIM(cube)]);
1615  }
1616  }
1617  else
1618  {
1619  /*
1620  * Return zero if coordinate is out of bound. That reproduces logic
1621  * of how cubes with low dimension number are expanded during GiST
1622  * indexing.
1623  */
1624  result = 0.0;
1625  }
1626 
1627  /* Inverse value if needed */
1628  if (inverse)
1629  result = -result;
1630 
1631  PG_RETURN_FLOAT8(result);
1632 }
1633 
1634 /* Increase or decrease box size by a radius in at least n dimensions. */
1635 Datum
1637 {
1638  NDBOX *a = PG_GETARG_NDBOX_P(0);
1639  double r = PG_GETARG_FLOAT8(1);
1640  int32 n = PG_GETARG_INT32(2);
1641  NDBOX *result;
1642  int dim = 0;
1643  int size;
1644  int i,
1645  j;
1646 
1647  if (n > CUBE_MAX_DIM)
1648  n = CUBE_MAX_DIM;
1649  if (r > 0 && n > 0)
1650  dim = n;
1651  if (DIM(a) > dim)
1652  dim = DIM(a);
1653 
1654  size = CUBE_SIZE(dim);
1655  result = (NDBOX *) palloc0(size);
1656  SET_VARSIZE(result, size);
1657  SET_DIM(result, dim);
1658 
1659  for (i = 0, j = dim; i < DIM(a); i++, j++)
1660  {
1661  if (LL_COORD(a, i) >= UR_COORD(a, i))
1662  {
1663  result->x[i] = UR_COORD(a, i) - r;
1664  result->x[j] = LL_COORD(a, i) + r;
1665  }
1666  else
1667  {
1668  result->x[i] = LL_COORD(a, i) - r;
1669  result->x[j] = UR_COORD(a, i) + r;
1670  }
1671  if (result->x[i] > result->x[j])
1672  {
1673  result->x[i] = (result->x[i] + result->x[j]) / 2;
1674  result->x[j] = result->x[i];
1675  }
1676  }
1677  /* dim > a->dim only if r > 0 */
1678  for (; i < dim; i++, j++)
1679  {
1680  result->x[i] = -r;
1681  result->x[j] = r;
1682  }
1683 
1684  /*
1685  * Check if the result was in fact a point, and set the flag in the datum
1686  * accordingly. (we don't bother to repalloc it smaller)
1687  */
1688  if (cube_is_point_internal(result))
1689  {
1690  size = POINT_SIZE(dim);
1691  SET_VARSIZE(result, size);
1692  SET_POINT_BIT(result);
1693  }
1694 
1695  PG_FREE_IF_COPY(a, 0);
1696  PG_RETURN_NDBOX_P(result);
1697 }
1698 
1699 /* Create a one dimensional box with identical upper and lower coordinates */
1700 Datum
1702 {
1703  double x = PG_GETARG_FLOAT8(0);
1704  NDBOX *result;
1705  int size;
1706 
1707  size = POINT_SIZE(1);
1708  result = (NDBOX *) palloc0(size);
1709  SET_VARSIZE(result, size);
1710  SET_DIM(result, 1);
1711  SET_POINT_BIT(result);
1712  result->x[0] = x;
1713 
1714  PG_RETURN_NDBOX_P(result);
1715 }
1716 
1717 /* Create a one dimensional box */
1718 Datum
1720 {
1721  double x0 = PG_GETARG_FLOAT8(0);
1722  double x1 = PG_GETARG_FLOAT8(1);
1723  NDBOX *result;
1724  int size;
1725 
1726  if (x0 == x1)
1727  {
1728  size = POINT_SIZE(1);
1729  result = (NDBOX *) palloc0(size);
1730  SET_VARSIZE(result, size);
1731  SET_DIM(result, 1);
1732  SET_POINT_BIT(result);
1733  result->x[0] = x0;
1734  }
1735  else
1736  {
1737  size = CUBE_SIZE(1);
1738  result = (NDBOX *) palloc0(size);
1739  SET_VARSIZE(result, size);
1740  SET_DIM(result, 1);
1741  result->x[0] = x0;
1742  result->x[1] = x1;
1743  }
1744 
1745  PG_RETURN_NDBOX_P(result);
1746 }
1747 
1748 /* Add a dimension to an existing cube with the same values for the new
1749  coordinate */
1750 Datum
1752 {
1753  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1754  double x = PG_GETARG_FLOAT8(1);
1755  NDBOX *result;
1756  int size;
1757  int i;
1758 
1759  if (IS_POINT(cube))
1760  {
1761  size = POINT_SIZE((DIM(cube) + 1));
1762  result = (NDBOX *) palloc0(size);
1763  SET_VARSIZE(result, size);
1764  SET_DIM(result, DIM(cube) + 1);
1765  SET_POINT_BIT(result);
1766  for (i = 0; i < DIM(cube); i++)
1767  result->x[i] = cube->x[i];
1768  result->x[DIM(result) - 1] = x;
1769  }
1770  else
1771  {
1772  size = CUBE_SIZE((DIM(cube) + 1));
1773  result = (NDBOX *) palloc0(size);
1774  SET_VARSIZE(result, size);
1775  SET_DIM(result, DIM(cube) + 1);
1776  for (i = 0; i < DIM(cube); i++)
1777  {
1778  result->x[i] = cube->x[i];
1779  result->x[DIM(result) + i] = cube->x[DIM(cube) + i];
1780  }
1781  result->x[DIM(result) - 1] = x;
1782  result->x[2 * DIM(result) - 1] = x;
1783  }
1784 
1785  PG_FREE_IF_COPY(cube, 0);
1786  PG_RETURN_NDBOX_P(result);
1787 }
1788 
1789 /* Add a dimension to an existing cube */
1790 Datum
1792 {
1793  NDBOX *cube = PG_GETARG_NDBOX_P(0);
1794  double x1 = PG_GETARG_FLOAT8(1);
1795  double x2 = PG_GETARG_FLOAT8(2);
1796  NDBOX *result;
1797  int size;
1798  int i;
1799 
1800  if (IS_POINT(cube) && (x1 == x2))
1801  {
1802  size = POINT_SIZE((DIM(cube) + 1));
1803  result = (NDBOX *) palloc0(size);
1804  SET_VARSIZE(result, size);
1805  SET_DIM(result, DIM(cube) + 1);
1806  SET_POINT_BIT(result);
1807  for (i = 0; i < DIM(cube); i++)
1808  result->x[i] = cube->x[i];
1809  result->x[DIM(result) - 1] = x1;
1810  }
1811  else
1812  {
1813  size = CUBE_SIZE((DIM(cube) + 1));
1814  result = (NDBOX *) palloc0(size);
1815  SET_VARSIZE(result, size);
1816  SET_DIM(result, DIM(cube) + 1);
1817  for (i = 0; i < DIM(cube); i++)
1818  {
1819  result->x[i] = LL_COORD(cube, i);
1820  result->x[DIM(result) + i] = UR_COORD(cube, i);
1821  }
1822  result->x[DIM(result) - 1] = x1;
1823  result->x[2 * DIM(result) - 1] = x2;
1824  }
1825 
1826  PG_FREE_IF_COPY(cube, 0);
1827  PG_RETURN_NDBOX_P(result);
1828 }
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:251
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:326
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:239
Datum cube_ne(PG_FUNCTION_ARGS)
Definition: cube.c:980
Datum cube_dim(PG_FUNCTION_ARGS)
Definition: cube.c:1487
#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:1751
#define RTOldContainedByStrategyNumber
Definition: stratnum.h:57
char * float8out_internal(double num)
Definition: float.c:593
#define CubeKNNDistanceTaxicab
Definition: cubedata.h:58
#define DatumGetNDBOXP(x)
Definition: cubedata.h:52
#define VARSIZE(PTR)
Definition: postgres.h:303
Datum g_cube_distance(PG_FUNCTION_ARGS)
Definition: cube.c:1331
bool g_cube_leaf_consistent(NDBOX *key, NDBOX *query, StrategyNumber strategy)
Definition: cube.c:604
#define PointerGetDatum(X)
Definition: postgres.h:541
#define DIM(cube)
Definition: cubedata.h:42
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:238
#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:331
#define Min(x, y)
Definition: c.h:857
OffsetNumber * spl_left
Definition: gist.h:105
Datum spl_rdatum
Definition: gist.h:112
#define PG_RETURN_INT32(x)
Definition: fmgr.h:319
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:246
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:75
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:1701
#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:1636
Datum cube_ll_coord(PG_FUNCTION_ARGS)
Definition: cube.c:1498
char bool
Definition: c.h:275
signed int int32
Definition: c.h:313
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:125
#define Abs(x)
Definition: c.h:863
Definition: type.h:89
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:1436
Datum cube_size(PG_FUNCTION_ARGS)
Definition: cube.c:832
#define CubeKNNDistanceChebyshev
Definition: cubedata.h:60
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:458
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:1536
#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
#define GistPageIsLeaf(page)
Definition: gist.h:132
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:955
Datum cube_f8_f8(PG_FUNCTION_ARGS)
Definition: cube.c:1719
void rt_cube_size(NDBOX *a, double *sz)
Definition: cube.c:843
#define DatumGetFloat8(X)
Definition: postgres.h:713
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:324
uintptr_t Datum
Definition: postgres.h:367
#define PG_RETURN_DATUM(x)
Definition: fmgr.h:318
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:1452
static FormData_pg_attribute a1
Definition: heap.c:147
#define Max(x, y)
Definition: c.h:851
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:1791
#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:327
#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:230
#define RTContainsStrategyNumber
Definition: stratnum.h:50
#define ARRNELEMS(x)
Definition: cube.c:27
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1044
Datum cube_le(PG_FUNCTION_ARGS)
Definition: cube.c:1025
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:242
NDBOX * cube_union_v0(NDBOX *a, NDBOX *b)
Definition: cube.c:673
int cube_yyparse(NDBOX **result)
void * palloc(Size size)
Definition: mcxt.c:924
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:247
#define CUBE_SIZE(_dim)
Definition: cubedata.h:49
#define RTOverlapStrategyNumber
Definition: stratnum.h:46
#define PG_FUNCTION_ARGS
Definition: fmgr.h:163
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:329
#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:1463
Datum cube_coord_llur(PG_FUNCTION_ARGS)
Definition: cube.c:1577
#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:592
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:153
Datum cube_ur_coord(PG_FUNCTION_ARGS)
Definition: cube.c:1515
Datum g_cube_consistent(PG_FUNCTION_ARGS)
Definition: cube.c:316