PostGIS  2.5.2dev-r@@SVN_REVISION@@

◆ gserialized_cmp()

int gserialized_cmp ( const GSERIALIZED g1,
const GSERIALIZED g2 
)

Return -1 if g1 is "less than" g2, 1 if g1 is "greater than" g2 and 0 if g1 and g2 are the "same".

Equality is evaluated with a memcmp and size check. So it is possible that two identical objects where one lacks a bounding box could be evaluated as non-equal initially. Greater and less than are evaluated by calculating a sortable key from the center point of the object bounds.

Definition at line 294 of file g_serialized.c.

References GSERIALIZED::data, floatuint::f, GSERIALIZED::flags, FLAGS_GET_BBOX, gbox_get_sortable_hash(), gserialized_cmp_srid(), gserialized_get_gbox_p(), gserialized_header_size(), LW_FAILURE, POINTTYPE, GSERIALIZED::size, SIZE_GET, floatuint::u, uint32_interleave_2(), GBOX::xmax, GBOX::xmin, GBOX::ymax, and GBOX::ymin.

Referenced by geography_cmp(), geography_eq(), geography_ge(), geography_gt(), geography_le(), geography_lt(), lwgeom_cmp(), lwgeom_eq(), lwgeom_ge(), lwgeom_gt(), lwgeom_le(), and lwgeom_lt().

295 {
296  int g1_is_empty, g2_is_empty, cmp;
297  GBOX box1, box2;
298  uint64_t hash1, hash2;
299  size_t sz1 = SIZE_GET(g1->size);
300  size_t sz2 = SIZE_GET(g2->size);
301  union floatuint x, y;
302 
303  /*
304  * For two non-same points, we can skip a lot of machinery.
305  */
306  if (
307  sz1 > 16 && // 16 is size of EMPTY, if it's larger - it has coordinates
308  sz2 > 16 &&
309  !FLAGS_GET_BBOX(g1->flags) &&
310  !FLAGS_GET_BBOX(g2->flags) &&
311  *(uint32_t*)(g1+8) == POINTTYPE &&
312  *(uint32_t*)(g2+8) == POINTTYPE
313  )
314  {
315  double *dptr = (double*)(g1->data + sizeof(double));
316  x.f = 2.0 * dptr[0];
317  y.f = 2.0 * dptr[1];
318  hash1 = uint32_interleave_2(x.u, y.u);
319 
320  dptr = (double*)(g2->data + sizeof(double));
321  x.f = 2.0 * dptr[0];
322  y.f = 2.0 * dptr[1];
323  hash2 = uint32_interleave_2(x.u, y.u);
324 
325  /* If the SRIDs are the same, we can use hash inequality */
326  /* to jump us out of this function early. Otherwise we still */
327  /* have to do the full calculation */
328  if ( gserialized_cmp_srid(g1, g2) == 0 )
329  {
330  if ( hash1 > hash2 )
331  return 1;
332  if ( hash1 < hash2 )
333  return -1;
334  }
335 
336  /* if hashes happen to be the same, go to full compare. */
337  }
338 
339  size_t hsz1 = gserialized_header_size(g1);
340  size_t hsz2 = gserialized_header_size(g2);
341 
342  uint8_t *b1 = (uint8_t*)g1 + hsz1;
343  uint8_t *b2 = (uint8_t*)g2 + hsz2;
344  size_t bsz1 = sz1 - hsz1;
345  size_t bsz2 = sz2 - hsz2;
346  size_t bsz = bsz1 < bsz2 ? bsz1 : bsz2;
347 
348  int cmp_srid = gserialized_cmp_srid(g1, g2);
349 
350  g1_is_empty = (gserialized_get_gbox_p(g1, &box1) == LW_FAILURE);
351  g2_is_empty = (gserialized_get_gbox_p(g2, &box2) == LW_FAILURE);
352 
353  /* Empty < Non-empty */
354  if (g1_is_empty && !g2_is_empty)
355  return -1;
356 
357  /* Non-empty > Empty */
358  if (!g1_is_empty && g2_is_empty)
359  return 1;
360 
361  /* Return equality for perfect equality only */
362  cmp = memcmp(b1, b2, bsz);
363  if ( bsz1 == bsz2 && cmp_srid == 0 && cmp == 0 )
364  return 0;
365 
366  if (!g1_is_empty && !g2_is_empty)
367  {
368  /* Using the centroids, calculate somewhat sortable */
369  /* hash key. The key doesn't provide good locality over */
370  /* the +/- boundary, but otherwise is pretty OK */
371  hash1 = gbox_get_sortable_hash(&box1);
372  hash2 = gbox_get_sortable_hash(&box2);
373 
374  if ( hash1 > hash2 )
375  return 1;
376  else if ( hash1 < hash2 )
377  return -1;
378 
379  /* What, the hashes are equal? OK... sort on the */
380  /* box minima */
381  if (box1.xmin < box2.xmin)
382  return -1;
383  else if (box1.xmin > box2.xmin)
384  return 1;
385 
386  if (box1.ymin < box2.ymin)
387  return -1;
388  else if (box1.ymin > box2.ymin)
389  return 1;
390 
391  /* Still equal? OK... sort on the box maxima */
392  if (box1.xmax < box2.xmax)
393  return -1;
394  else if (box1.xmax > box2.xmax)
395  return 1;
396 
397  if (box1.ymax < box2.ymax)
398  return -1;
399  else if (box1.ymax > box2.ymax)
400  return 1;
401  }
402 
403  /* Prefix comes before longer one. */
404  if (bsz1 != bsz2 && cmp == 0)
405  {
406  if (bsz1 < bsz2)
407  return -1;
408  else if (bsz1 > bsz2)
409  return 1;
410  }
411  return cmp > 0 ? 1 : -1;
412 }
int gserialized_get_gbox_p(const GSERIALIZED *g, GBOX *box)
Read the bounding box off a serialization and calculate one if it is not already there.
Definition: g_serialized.c:640
uint8_t data[1]
Definition: liblwgeom.h:387
static int gserialized_cmp_srid(const GSERIALIZED *s1, const GSERIALIZED *s2)
Definition: g_serialized.c:133
double xmax
Definition: liblwgeom.h:296
#define LW_FAILURE
Definition: liblwgeom.h:79
uint64_t gbox_get_sortable_hash(const GBOX *g)
Return a sortable key based on the center point of the GBOX.
Definition: g_serialized.c:259
unsigned int uint32_t
Definition: uthash.h:78
double ymin
Definition: liblwgeom.h:297
static uint64_t uint32_interleave_2(uint32_t u1, uint32_t u2)
Definition: g_serialized.c:228
double xmin
Definition: liblwgeom.h:295
#define FLAGS_GET_BBOX(flags)
Definition: liblwgeom.h:142
double ymax
Definition: liblwgeom.h:298
#define SIZE_GET(varsize)
Macro for reading the size from the GSERIALIZED size attribute.
uint32_t size
Definition: liblwgeom.h:384
#define POINTTYPE
LWTYPE numbers, used internally by PostGIS.
Definition: liblwgeom.h:85
uint32_t gserialized_header_size(const GSERIALIZED *gser)
Returns the size in bytes of the header, from the start of the object up to the type number...
Definition: g_serialized.c:76
unsigned char uint8_t
Definition: uthash.h:79
uint8_t flags
Definition: liblwgeom.h:386
Here is the call graph for this function:
Here is the caller graph for this function: