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