PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geo_spgist.c File Reference
#include "postgres.h"
#include "access/spgist.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/geo_decls.h"
Include dependency graph for geo_spgist.c:

Go to the source code of this file.

Data Structures

struct  Range
 
struct  RangeBox
 
struct  RectBox
 

Functions

static int compareDoubles (const void *a, const void *b)
 
static uint8 getQuadrant (BOX *centroid, BOX *inBox)
 
static RangeBoxgetRangeBox (BOX *box)
 
static RectBoxinitRectBox (void)
 
static RectBoxnextRectBox (RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
 
static bool overlap2D (RangeBox *range_box, Range *query)
 
static bool overlap4D (RectBox *rect_box, RangeBox *query)
 
static bool contain2D (RangeBox *range_box, Range *query)
 
static bool contain4D (RectBox *rect_box, RangeBox *query)
 
static bool contained2D (RangeBox *range_box, Range *query)
 
static bool contained4D (RectBox *rect_box, RangeBox *query)
 
static bool lower2D (RangeBox *range_box, Range *query)
 
static bool overLower2D (RangeBox *range_box, Range *query)
 
static bool higher2D (RangeBox *range_box, Range *query)
 
static bool overHigher2D (RangeBox *range_box, Range *query)
 
static bool left4D (RectBox *rect_box, RangeBox *query)
 
static bool overLeft4D (RectBox *rect_box, RangeBox *query)
 
static bool right4D (RectBox *rect_box, RangeBox *query)
 
static bool overRight4D (RectBox *rect_box, RangeBox *query)
 
static bool below4D (RectBox *rect_box, RangeBox *query)
 
static bool overBelow4D (RectBox *rect_box, RangeBox *query)
 
static bool above4D (RectBox *rect_box, RangeBox *query)
 
static bool overAbove4D (RectBox *rect_box, RangeBox *query)
 
Datum spg_box_quad_config (PG_FUNCTION_ARGS)
 
Datum spg_box_quad_choose (PG_FUNCTION_ARGS)
 
Datum spg_box_quad_picksplit (PG_FUNCTION_ARGS)
 
Datum spg_box_quad_inner_consistent (PG_FUNCTION_ARGS)
 
Datum spg_box_quad_leaf_consistent (PG_FUNCTION_ARGS)
 

Function Documentation

static bool above4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 357 of file geo_spgist.c.

References higher2D(), RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

358 {
359  return higher2D(&rect_box->range_box_y, &query->right);
360 }
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
static bool higher2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:299
static bool below4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 343 of file geo_spgist.c.

References lower2D(), RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

344 {
345  return lower2D(&rect_box->range_box_y, &query->right);
346 }
static bool lower2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:283
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
static int compareDoubles ( const void *  a,
const void *  b 
)
static

Definition at line 90 of file geo_spgist.c.

Referenced by spg_box_quad_picksplit().

91 {
92  double x = *(double *) a;
93  double y = *(double *) b;
94 
95  if (x == y)
96  return 0;
97  return (x > y) ? 1 : -1;
98 }
static bool contain2D ( RangeBox range_box,
Range query 
)
static

Definition at line 249 of file geo_spgist.c.

References FPge, FPle, Range::high, RangeBox::left, Range::low, and RangeBox::right.

Referenced by contain4D().

250 {
251  return FPge(range_box->right.high, query->high) &&
252  FPle(range_box->left.low, query->low);
253 }
Range right
Definition: geo_spgist.c:109
double low
Definition: geo_spgist.c:102
double high
Definition: geo_spgist.c:103
#define FPge(A, B)
Definition: geo_decls.h:42
#define FPle(A, B)
Definition: geo_decls.h:40
Range left
Definition: geo_spgist.c:108
static bool contain4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 257 of file geo_spgist.c.

References contain2D(), RangeBox::left, RectBox::range_box_x, RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

258 {
259  return contain2D(&rect_box->range_box_x, &query->left) &&
260  contain2D(&rect_box->range_box_y, &query->right);
261 }
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
RangeBox range_box_x
Definition: geo_spgist.c:114
static bool contain2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:249
Range left
Definition: geo_spgist.c:108
static bool contained2D ( RangeBox range_box,
Range query 
)
static

Definition at line 265 of file geo_spgist.c.

References FPge, FPle, Range::high, RangeBox::left, Range::low, and RangeBox::right.

Referenced by contained4D().

266 {
267  return FPle(range_box->left.low, query->high) &&
268  FPge(range_box->left.high, query->low) &&
269  FPle(range_box->right.low, query->high) &&
270  FPge(range_box->right.high, query->low);
271 }
Range right
Definition: geo_spgist.c:109
double low
Definition: geo_spgist.c:102
double high
Definition: geo_spgist.c:103
#define FPge(A, B)
Definition: geo_decls.h:42
#define FPle(A, B)
Definition: geo_decls.h:40
Range left
Definition: geo_spgist.c:108
static bool contained4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 275 of file geo_spgist.c.

References contained2D(), RangeBox::left, RectBox::range_box_x, RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

276 {
277  return contained2D(&rect_box->range_box_x, &query->left) &&
278  contained2D(&rect_box->range_box_y, &query->right);
279 }
static bool contained2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:265
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
RangeBox range_box_x
Definition: geo_spgist.c:114
Range left
Definition: geo_spgist.c:108
static uint8 getQuadrant ( BOX centroid,
BOX inBox 
)
static

Definition at line 127 of file geo_spgist.c.

References BOX::high, BOX::low, Point::x, and Point::y.

Referenced by spg_box_quad_choose(), and spg_box_quad_picksplit().

128 {
129  uint8 quadrant = 0;
130 
131  if (inBox->low.x > centroid->low.x)
132  quadrant |= 0x8;
133 
134  if (inBox->high.x > centroid->high.x)
135  quadrant |= 0x4;
136 
137  if (inBox->low.y > centroid->low.y)
138  quadrant |= 0x2;
139 
140  if (inBox->high.y > centroid->high.y)
141  quadrant |= 0x1;
142 
143  return quadrant;
144 }
double y
Definition: geo_decls.h:60
unsigned char uint8
Definition: c.h:266
double x
Definition: geo_decls.h:60
Point low
Definition: geo_decls.h:104
Point high
Definition: geo_decls.h:104
static RangeBox* getRangeBox ( BOX box)
static

Definition at line 154 of file geo_spgist.c.

References Range::high, BOX::high, RangeBox::left, Range::low, BOX::low, palloc(), RangeBox::right, Point::x, and Point::y.

Referenced by spg_box_quad_inner_consistent().

155 {
156  RangeBox *range_box = (RangeBox *) palloc(sizeof(RangeBox));
157 
158  range_box->left.low = box->low.x;
159  range_box->left.high = box->high.x;
160 
161  range_box->right.low = box->low.y;
162  range_box->right.high = box->high.y;
163 
164  return range_box;
165 }
double y
Definition: geo_decls.h:60
Range right
Definition: geo_spgist.c:109
double x
Definition: geo_decls.h:60
double low
Definition: geo_spgist.c:102
Point low
Definition: geo_decls.h:104
double high
Definition: geo_spgist.c:103
Point high
Definition: geo_decls.h:104
void * palloc(Size size)
Definition: mcxt.c:849
Range left
Definition: geo_spgist.c:108
static bool higher2D ( RangeBox range_box,
Range query 
)
static

Definition at line 299 of file geo_spgist.c.

References FPgt, Range::high, RangeBox::left, and RangeBox::right.

Referenced by above4D(), and right4D().

300 {
301  return FPgt(range_box->left.high, query->high) &&
302  FPgt(range_box->right.high, query->high);
303 }
Range right
Definition: geo_spgist.c:109
#define FPgt(A, B)
Definition: geo_decls.h:41
double high
Definition: geo_spgist.c:103
Range left
Definition: geo_spgist.c:108
static RectBox* initRectBox ( void  )
static

Definition at line 174 of file geo_spgist.c.

References get_float8_infinity(), Range::high, RangeBox::left, Range::low, palloc(), RectBox::range_box_x, RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

175 {
176  RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
177  double infinity = get_float8_infinity();
178 
179  rect_box->range_box_x.left.low = -infinity;
180  rect_box->range_box_x.left.high = infinity;
181 
182  rect_box->range_box_x.right.low = -infinity;
183  rect_box->range_box_x.right.high = infinity;
184 
185  rect_box->range_box_y.left.low = -infinity;
186  rect_box->range_box_y.left.high = infinity;
187 
188  rect_box->range_box_y.right.low = -infinity;
189  rect_box->range_box_y.right.high = infinity;
190 
191  return rect_box;
192 }
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
RangeBox range_box_x
Definition: geo_spgist.c:114
double low
Definition: geo_spgist.c:102
double get_float8_infinity(void)
Definition: float.c:121
double high
Definition: geo_spgist.c:103
void * palloc(Size size)
Definition: mcxt.c:849
Range left
Definition: geo_spgist.c:108
static bool left4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 315 of file geo_spgist.c.

References RangeBox::left, lower2D(), and RectBox::range_box_x.

Referenced by spg_box_quad_inner_consistent().

316 {
317  return lower2D(&rect_box->range_box_x, &query->left);
318 }
static bool lower2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:283
RangeBox range_box_x
Definition: geo_spgist.c:114
Range left
Definition: geo_spgist.c:108
static bool lower2D ( RangeBox range_box,
Range query 
)
static

Definition at line 283 of file geo_spgist.c.

References FPlt, RangeBox::left, Range::low, and RangeBox::right.

Referenced by below4D(), and left4D().

284 {
285  return FPlt(range_box->left.low, query->low) &&
286  FPlt(range_box->right.low, query->low);
287 }
Range right
Definition: geo_spgist.c:109
double low
Definition: geo_spgist.c:102
#define FPlt(A, B)
Definition: geo_decls.h:39
Range left
Definition: geo_spgist.c:108
static RectBox* nextRectBox ( RectBox rect_box,
RangeBox centroid,
uint8  quadrant 
)
static

Definition at line 202 of file geo_spgist.c.

References Range::high, RangeBox::left, Range::low, palloc(), RectBox::range_box_x, RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

203 {
204  RectBox *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
205 
206  memcpy(next_rect_box, rect_box, sizeof(RectBox));
207 
208  if (quadrant & 0x8)
209  next_rect_box->range_box_x.left.low = centroid->left.low;
210  else
211  next_rect_box->range_box_x.left.high = centroid->left.low;
212 
213  if (quadrant & 0x4)
214  next_rect_box->range_box_x.right.low = centroid->left.high;
215  else
216  next_rect_box->range_box_x.right.high = centroid->left.high;
217 
218  if (quadrant & 0x2)
219  next_rect_box->range_box_y.left.low = centroid->right.low;
220  else
221  next_rect_box->range_box_y.left.high = centroid->right.low;
222 
223  if (quadrant & 0x1)
224  next_rect_box->range_box_y.right.low = centroid->right.high;
225  else
226  next_rect_box->range_box_y.right.high = centroid->right.high;
227 
228  return next_rect_box;
229 }
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
RangeBox range_box_x
Definition: geo_spgist.c:114
double low
Definition: geo_spgist.c:102
double high
Definition: geo_spgist.c:103
void * palloc(Size size)
Definition: mcxt.c:849
Range left
Definition: geo_spgist.c:108
static bool overAbove4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 364 of file geo_spgist.c.

References overHigher2D(), RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

365 {
366  return overHigher2D(&rect_box->range_box_y, &query->right);
367 }
static bool overHigher2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:307
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
static bool overBelow4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 350 of file geo_spgist.c.

References overLower2D(), RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

351 {
352  return overLower2D(&rect_box->range_box_y, &query->right);
353 }
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
static bool overLower2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:291
static bool overHigher2D ( RangeBox range_box,
Range query 
)
static

Definition at line 307 of file geo_spgist.c.

References FPge, Range::high, RangeBox::left, Range::low, and RangeBox::right.

Referenced by overAbove4D(), and overRight4D().

308 {
309  return FPge(range_box->left.high, query->low) &&
310  FPge(range_box->right.high, query->low);
311 }
Range right
Definition: geo_spgist.c:109
double low
Definition: geo_spgist.c:102
double high
Definition: geo_spgist.c:103
#define FPge(A, B)
Definition: geo_decls.h:42
Range left
Definition: geo_spgist.c:108
static bool overlap2D ( RangeBox range_box,
Range query 
)
static

Definition at line 233 of file geo_spgist.c.

References FPge, FPle, Range::high, RangeBox::left, Range::low, and RangeBox::right.

Referenced by overlap4D().

234 {
235  return FPge(range_box->right.high, query->low) &&
236  FPle(range_box->left.low, query->high);
237 }
Range right
Definition: geo_spgist.c:109
double low
Definition: geo_spgist.c:102
double high
Definition: geo_spgist.c:103
#define FPge(A, B)
Definition: geo_decls.h:42
#define FPle(A, B)
Definition: geo_decls.h:40
Range left
Definition: geo_spgist.c:108
static bool overlap4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 241 of file geo_spgist.c.

References RangeBox::left, overlap2D(), RectBox::range_box_x, RectBox::range_box_y, and RangeBox::right.

Referenced by spg_box_quad_inner_consistent().

242 {
243  return overlap2D(&rect_box->range_box_x, &query->left) &&
244  overlap2D(&rect_box->range_box_y, &query->right);
245 }
RangeBox range_box_y
Definition: geo_spgist.c:115
Range right
Definition: geo_spgist.c:109
RangeBox range_box_x
Definition: geo_spgist.c:114
static bool overlap2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:233
Range left
Definition: geo_spgist.c:108
static bool overLeft4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 322 of file geo_spgist.c.

References RangeBox::left, overLower2D(), and RectBox::range_box_x.

Referenced by spg_box_quad_inner_consistent().

323 {
324  return overLower2D(&rect_box->range_box_x, &query->left);
325 }
static bool overLower2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:291
RangeBox range_box_x
Definition: geo_spgist.c:114
Range left
Definition: geo_spgist.c:108
static bool overLower2D ( RangeBox range_box,
Range query 
)
static

Definition at line 291 of file geo_spgist.c.

References FPle, Range::high, RangeBox::left, Range::low, and RangeBox::right.

Referenced by overBelow4D(), and overLeft4D().

292 {
293  return FPle(range_box->left.low, query->high) &&
294  FPle(range_box->right.low, query->high);
295 }
Range right
Definition: geo_spgist.c:109
double low
Definition: geo_spgist.c:102
double high
Definition: geo_spgist.c:103
#define FPle(A, B)
Definition: geo_decls.h:40
Range left
Definition: geo_spgist.c:108
static bool overRight4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 336 of file geo_spgist.c.

References RangeBox::left, overHigher2D(), and RectBox::range_box_x.

Referenced by spg_box_quad_inner_consistent().

337 {
338  return overHigher2D(&rect_box->range_box_x, &query->left);
339 }
static bool overHigher2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:307
RangeBox range_box_x
Definition: geo_spgist.c:114
Range left
Definition: geo_spgist.c:108
static bool right4D ( RectBox rect_box,
RangeBox query 
)
static

Definition at line 329 of file geo_spgist.c.

References higher2D(), RangeBox::left, and RectBox::range_box_x.

Referenced by spg_box_quad_inner_consistent().

330 {
331  return higher2D(&rect_box->range_box_x, &query->left);
332 }
RangeBox range_box_x
Definition: geo_spgist.c:114
Range left
Definition: geo_spgist.c:108
static bool higher2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:299
Datum spg_box_quad_choose ( PG_FUNCTION_ARGS  )

Definition at line 389 of file geo_spgist.c.

References spgChooseIn::allTheSame, BoxPGetDatum, spgChooseIn::datum, DatumGetBoxP, getQuadrant(), spgChooseOut::matchNode, PG_GETARG_POINTER, PG_RETURN_VOID, spgChooseIn::prefixDatum, spgChooseOut::result, spgChooseOut::resultType, and spgMatchNode.

390 {
393  BOX *centroid = DatumGetBoxP(in->prefixDatum),
394  *box = DatumGetBoxP(in->datum);
395 
396  out->resultType = spgMatchNode;
397  out->result.matchNode.restDatum = BoxPGetDatum(box);
398 
399  /* nodeN will be set by core, when allTheSame. */
400  if (!in->allTheSame)
401  out->result.matchNode.nodeN = getQuadrant(centroid, box);
402 
403  PG_RETURN_VOID();
404 }
Definition: geo_decls.h:102
Datum datum
Definition: spgist.h:56
struct spgChooseOut::@48::@49 matchNode
Datum prefixDatum
Definition: spgist.h:63
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
spgChooseResultType resultType
Definition: spgist.h:77
#define BoxPGetDatum(X)
Definition: geo_decls.h:160
#define PG_RETURN_VOID()
Definition: fmgr.h:309
union spgChooseOut::@48 result
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
static uint8 getQuadrant(BOX *centroid, BOX *inBox)
Definition: geo_spgist.c:127
bool allTheSame
Definition: spgist.h:61
Datum spg_box_quad_config ( PG_FUNCTION_ARGS  )

Definition at line 373 of file geo_spgist.c.

References BOXOID, spgConfigOut::canReturnData, spgConfigOut::labelType, spgConfigOut::longValuesOK, PG_GETARG_POINTER, PG_RETURN_VOID, spgConfigOut::prefixType, and VOIDOID.

374 {
376 
377  cfg->prefixType = BOXOID;
378  cfg->labelType = VOIDOID; /* We don't need node labels. */
379  cfg->canReturnData = true;
380  cfg->longValuesOK = false;
381 
382  PG_RETURN_VOID();
383 }
bool canReturnData
Definition: spgist.h:47
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define VOIDOID
Definition: pg_type.h:690
#define BOXOID
Definition: pg_type.h:402
bool longValuesOK
Definition: spgist.h:48
Oid prefixType
Definition: spgist.h:45
#define PG_RETURN_VOID()
Definition: fmgr.h:309
Oid labelType
Definition: spgist.h:46
Datum spg_box_quad_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 480 of file geo_spgist.c.

References above4D(), spgInnerConsistentIn::allTheSame, below4D(), contain4D(), contained4D(), DatumGetBoxP, elog, ERROR, flag(), getRangeBox(), i, initRectBox(), left4D(), MemoryContextSwitchTo(), nextRectBox(), spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, overAbove4D(), overBelow4D(), overlap4D(), overLeft4D(), overRight4D(), palloc(), pfree(), PG_GETARG_POINTER, PG_RETURN_VOID, spgInnerConsistentIn::prefixDatum, right4D(), RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTContainsStrategyNumber, RTLeftStrategyNumber, RTOverAboveStrategyNumber, RTOverBelowStrategyNumber, RTOverlapStrategyNumber, RTOverLeftStrategyNumber, RTOverRightStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, spgInnerConsistentIn::traversalMemoryContext, spgInnerConsistentIn::traversalValue, and spgInnerConsistentOut::traversalValues.

481 {
484  int i;
485  MemoryContext old_ctx;
486  RectBox *rect_box;
487  uint8 quadrant;
488  RangeBox *centroid,
489  **queries;
490 
491  if (in->allTheSame)
492  {
493  /* Report that all nodes should be visited */
494  out->nNodes = in->nNodes;
495  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
496  for (i = 0; i < in->nNodes; i++)
497  out->nodeNumbers[i] = i;
498 
499  PG_RETURN_VOID();
500  }
501 
502  /*
503  * We are saving the traversal value or initialize it an unbounded one, if
504  * we have just begun to walk the tree.
505  */
506  if (in->traversalValue)
507  rect_box = in->traversalValue;
508  else
509  rect_box = initRectBox();
510 
511  /*
512  * We are casting the prefix and queries to RangeBoxes for ease of the
513  * following operations.
514  */
515  centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
516  queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
517  for (i = 0; i < in->nkeys; i++)
518  queries[i] = getRangeBox(DatumGetBoxP(in->scankeys[i].sk_argument));
519 
520  /* Allocate enough memory for nodes */
521  out->nNodes = 0;
522  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
523  out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
524 
525  /*
526  * We switch memory context, because we want to allocate memory for new
527  * traversal values (next_rect_box) and pass these pieces of memory to
528  * further call of this function.
529  */
531 
532  for (quadrant = 0; quadrant < in->nNodes; quadrant++)
533  {
534  RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
535  bool flag = true;
536 
537  for (i = 0; i < in->nkeys; i++)
538  {
539  StrategyNumber strategy = in->scankeys[i].sk_strategy;
540 
541  switch (strategy)
542  {
544  flag = overlap4D(next_rect_box, queries[i]);
545  break;
546 
548  flag = contain4D(next_rect_box, queries[i]);
549  break;
550 
553  flag = contained4D(next_rect_box, queries[i]);
554  break;
555 
557  flag = left4D(next_rect_box, queries[i]);
558  break;
559 
561  flag = overLeft4D(next_rect_box, queries[i]);
562  break;
563 
565  flag = right4D(next_rect_box, queries[i]);
566  break;
567 
569  flag = overRight4D(next_rect_box, queries[i]);
570  break;
571 
573  flag = above4D(next_rect_box, queries[i]);
574  break;
575 
577  flag = overAbove4D(next_rect_box, queries[i]);
578  break;
579 
581  flag = below4D(next_rect_box, queries[i]);
582  break;
583 
585  flag = overBelow4D(next_rect_box, queries[i]);
586  break;
587 
588  default:
589  elog(ERROR, "unrecognized strategy: %d", strategy);
590  }
591 
592  /* If any check is failed, we have found our answer. */
593  if (!flag)
594  break;
595  }
596 
597  if (flag)
598  {
599  out->traversalValues[out->nNodes] = next_rect_box;
600  out->nodeNumbers[out->nNodes] = quadrant;
601  out->nNodes++;
602  }
603  else
604  {
605  /*
606  * If this node is not selected, we don't need to keep the next
607  * traversal value in the memory context.
608  */
609  pfree(next_rect_box);
610  }
611  }
612 
613  /* Switch back */
614  MemoryContextSwitchTo(old_ctx);
615 
616  PG_RETURN_VOID();
617 }
static bool overAbove4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:364
static bool overBelow4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:350
static bool contain4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:257
#define RTLeftStrategyNumber
Definition: stratnum.h:44
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
unsigned char uint8
Definition: c.h:266
void * traversalValue
Definition: spgist.h:139
#define RTOverBelowStrategyNumber
Definition: stratnum.h:52
static bool overRight4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:336
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
static bool left4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:315
#define RTBelowStrategyNumber
Definition: stratnum.h:53
#define RTOverAboveStrategyNumber
Definition: stratnum.h:55
static bool below4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:343
void pfree(void *pointer)
Definition: mcxt.c:950
static bool overlap4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:241
MemoryContext traversalMemoryContext
Definition: spgist.h:140
#define ERROR
Definition: elog.h:43
StrategyNumber sk_strategy
Definition: skey.h:68
char * flag(int b)
Definition: test-ctype.c:33
#define RTSameStrategyNumber
Definition: stratnum.h:49
#define RTOverRightStrategyNumber
Definition: stratnum.h:47
void ** traversalValues
Definition: spgist.h:159
static bool above4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:357
#define RTOverLeftStrategyNumber
Definition: stratnum.h:45
static RectBox * initRectBox(void)
Definition: geo_spgist.c:174
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define RTAboveStrategyNumber
Definition: stratnum.h:54
#define RTRightStrategyNumber
Definition: stratnum.h:48
static bool contained4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:275
#define RTContainsStrategyNumber
Definition: stratnum.h:50
ScanKey scankeys
Definition: spgist.h:135
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
void * palloc(Size size)
Definition: mcxt.c:849
static bool overLeft4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:322
int i
#define RTOverlapStrategyNumber
Definition: stratnum.h:46
#define elog
Definition: elog.h:219
static bool right4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:329
static RangeBox * getRangeBox(BOX *box)
Definition: geo_spgist.c:154
Datum sk_argument
Definition: skey.h:72
static RectBox * nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
Definition: geo_spgist.c:202
Datum spg_box_quad_leaf_consistent ( PG_FUNCTION_ARGS  )

Definition at line 623 of file geo_spgist.c.

References box_above(), box_below(), box_contain(), box_contained(), box_left(), box_overabove(), box_overbelow(), box_overlap(), box_overleft(), box_overright(), box_right(), box_same(), DatumGetBool, DirectFunctionCall2, elog, ERROR, flag(), i, spgLeafConsistentIn::leafDatum, spgLeafConsistentOut::leafValue, spgLeafConsistentIn::nkeys, PG_GETARG_POINTER, PG_RETURN_BOOL, spgLeafConsistentOut::recheck, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTContainsStrategyNumber, RTLeftStrategyNumber, RTOverAboveStrategyNumber, RTOverBelowStrategyNumber, RTOverlapStrategyNumber, RTOverLeftStrategyNumber, RTOverRightStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgLeafConsistentIn::scankeys, ScanKeyData::sk_argument, and ScanKeyData::sk_strategy.

624 {
627  Datum leaf = in->leafDatum;
628  bool flag = true;
629  int i;
630 
631  /* All tests are exact. */
632  out->recheck = false;
633 
634  /* leafDatum is what it is... */
635  out->leafValue = in->leafDatum;
636 
637  /* Perform the required comparison(s) */
638  for (i = 0; i < in->nkeys; i++)
639  {
640  StrategyNumber strategy = in->scankeys[i].sk_strategy;
641  Datum query = in->scankeys[i].sk_argument;
642 
643  switch (strategy)
644  {
647  query));
648  break;
649 
652  query));
653  break;
654 
657  query));
658  break;
659 
662  query));
663  break;
664 
667  query));
668  break;
669 
672  query));
673  break;
674 
677  query));
678  break;
679 
682  query));
683  break;
684 
687  query));
688  break;
689 
692  query));
693  break;
694 
697  query));
698  break;
699 
702  query));
703  break;
704 
705  default:
706  elog(ERROR, "unrecognized strategy: %d", strategy);
707  }
708 
709  /* If any check is failed, we have found our answer. */
710  if (!flag)
711  break;
712  }
713 
714  PG_RETURN_BOOL(flag);
715 }
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:564
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:636
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:504
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:538
#define RTLeftStrategyNumber
Definition: stratnum.h:44
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:579
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:518
#define RTOverBelowStrategyNumber
Definition: stratnum.h:52
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
#define RTBelowStrategyNumber
Definition: stratnum.h:53
#define RTOverAboveStrategyNumber
Definition: stratnum.h:55
#define ERROR
Definition: elog.h:43
StrategyNumber sk_strategy
Definition: skey.h:68
ScanKey scankeys
Definition: spgist.h:167
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:650
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:613
char * flag(int b)
Definition: test-ctype.c:33
#define DatumGetBool(X)
Definition: postgres.h:399
#define RTSameStrategyNumber
Definition: stratnum.h:49
#define RTOverRightStrategyNumber
Definition: stratnum.h:47
#define RTOverLeftStrategyNumber
Definition: stratnum.h:45
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:319
uintptr_t Datum
Definition: postgres.h:372
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:602
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:590
#define RTAboveStrategyNumber
Definition: stratnum.h:54
#define RTRightStrategyNumber
Definition: stratnum.h:48
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:553
#define RTContainsStrategyNumber
Definition: stratnum.h:50
int i
#define RTOverlapStrategyNumber
Definition: stratnum.h:46
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:625
#define elog
Definition: elog.h:219
Datum sk_argument
Definition: skey.h:72
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:586
Datum spg_box_quad_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 413 of file geo_spgist.c.

References BoxPGetDatum, compareDoubles(), DatumGetBoxP, spgPickSplitIn::datums, getQuadrant(), spgPickSplitOut::hasPrefix, BOX::high, i, spgPickSplitOut::leafTupleDatums, BOX::low, spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, NULL, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, spgPickSplitOut::prefixDatum, qsort, Point::x, and Point::y.

414 {
417  BOX *centroid;
418  int median,
419  i;
420  double *lowXs = palloc(sizeof(double) * in->nTuples);
421  double *highXs = palloc(sizeof(double) * in->nTuples);
422  double *lowYs = palloc(sizeof(double) * in->nTuples);
423  double *highYs = palloc(sizeof(double) * in->nTuples);
424 
425  /* Calculate median of all 4D coordinates */
426  for (i = 0; i < in->nTuples; i++)
427  {
428  BOX *box = DatumGetBoxP(in->datums[i]);
429 
430  lowXs[i] = box->low.x;
431  highXs[i] = box->high.x;
432  lowYs[i] = box->low.y;
433  highYs[i] = box->high.y;
434  }
435 
436  qsort(lowXs, in->nTuples, sizeof(double), compareDoubles);
437  qsort(highXs, in->nTuples, sizeof(double), compareDoubles);
438  qsort(lowYs, in->nTuples, sizeof(double), compareDoubles);
439  qsort(highYs, in->nTuples, sizeof(double), compareDoubles);
440 
441  median = in->nTuples / 2;
442 
443  centroid = palloc(sizeof(BOX));
444 
445  centroid->low.x = lowXs[median];
446  centroid->high.x = highXs[median];
447  centroid->low.y = lowYs[median];
448  centroid->high.y = highYs[median];
449 
450  /* Fill the output */
451  out->hasPrefix = true;
452  out->prefixDatum = BoxPGetDatum(centroid);
453 
454  out->nNodes = 16;
455  out->nodeLabels = NULL; /* We don't need node labels. */
456 
457  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
458  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
459 
460  /*
461  * Assign ranges to corresponding nodes according to quadrants relative to
462  * the "centroid" range
463  */
464  for (i = 0; i < in->nTuples; i++)
465  {
466  BOX *box = DatumGetBoxP(in->datums[i]);
467  uint8 quadrant = getQuadrant(centroid, box);
468 
469  out->leafTupleDatums[i] = BoxPGetDatum(box);
470  out->mapTuplesToNodes[i] = quadrant;
471  }
472 
473  PG_RETURN_VOID();
474 }
Definition: geo_decls.h:102
Datum * leafTupleDatums
Definition: spgist.h:127
Datum * datums
Definition: spgist.h:114
double y
Definition: geo_decls.h:60
unsigned char uint8
Definition: c.h:266
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
double x
Definition: geo_decls.h:60
Datum * nodeLabels
Definition: spgist.h:124
Point low
Definition: geo_decls.h:104
uintptr_t Datum
Definition: postgres.h:372
#define BoxPGetDatum(X)
Definition: geo_decls.h:160
#define PG_RETURN_VOID()
Definition: fmgr.h:309
#define NULL
Definition: c.h:229
bool hasPrefix
Definition: spgist.h:120
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
Point high
Definition: geo_decls.h:104
static uint8 getQuadrant(BOX *centroid, BOX *inBox)
Definition: geo_spgist.c:127
void * palloc(Size size)
Definition: mcxt.c:849
int i
int * mapTuplesToNodes
Definition: spgist.h:126
static int compareDoubles(const void *a, const void *b)
Definition: geo_spgist.c:90
Datum prefixDatum
Definition: spgist.h:121
#define qsort(a, b, c, d)
Definition: port.h:440