PostGIS  2.5.0dev-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 293 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().

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