granicus.if.org Git - postgresql/blob - contrib/seg/seg.c

   1 /*
   2  * contrib/seg/seg.c
   3  *
   4  ******************************************************************************
   5   This file contains routines that can be bound to a Postgres backend and
   6   called by the backend in the process of processing queries.  The calling
   7   format for these routines is dictated by Postgres architecture.
   8 ******************************************************************************/
   9
  10 #include "postgres.h"
  11
  12 #include <float.h>
  13
  14 #include "access/gist.h"
  15 #include "access/stratnum.h"
  16 #include "fmgr.h"
  17
  18 #include "segdata.h"
  19
  20 /*
  21 #define GIST_DEBUG
  22 #define GIST_QUERY_DEBUG
  23 */
  24
  25 PG_MODULE_MAGIC;
  26
  27 /*
  28  * Auxiliary data structure for picksplit method.
  29  */
  30 typedef struct
  31 {
  32         float           center;
  33         OffsetNumber index;
  34         SEG                *data;
  35 } gseg_picksplit_item;
  36
  37 /*
  38 ** Input/Output routines
  39 */
  40 PG_FUNCTION_INFO_V1(seg_in);
  41 PG_FUNCTION_INFO_V1(seg_out);
  42 PG_FUNCTION_INFO_V1(seg_size);
  43 PG_FUNCTION_INFO_V1(seg_lower);
  44 PG_FUNCTION_INFO_V1(seg_upper);
  45 PG_FUNCTION_INFO_V1(seg_center);
  46
  47 /*
  48 ** GiST support methods
  49 */
  50 bool gseg_consistent(GISTENTRY *entry,
  51                                 SEG *query,
  52                                 StrategyNumber strategy,
  53                                 Oid subtype,
  54                                 bool *recheck);
  55 GISTENTRY  *gseg_compress(GISTENTRY *entry);
  56 GISTENTRY  *gseg_decompress(GISTENTRY *entry);
  57 float      *gseg_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result);
  58 GIST_SPLITVEC *gseg_picksplit(GistEntryVector *entryvec, GIST_SPLITVEC *v);
  59 bool            gseg_leaf_consistent(SEG *key, SEG *query, StrategyNumber strategy);
  60 bool            gseg_internal_consistent(SEG *key, SEG *query, StrategyNumber strategy);
  61 SEG                *gseg_union(GistEntryVector *entryvec, int *sizep);
  62 SEG                *gseg_binary_union(SEG *r1, SEG *r2, int *sizep);
  63 bool       *gseg_same(SEG *b1, SEG *b2, bool *result);
  64
  65
  66 /*
  67 ** R-tree support functions
  68 */
  69 bool            seg_same(SEG *a, SEG *b);
  70 bool            seg_contains_int(SEG *a, int *b);
  71 bool            seg_contains_float4(SEG *a, float4 *b);
  72 bool            seg_contains_float8(SEG *a, float8 *b);
  73 bool            seg_contains(SEG *a, SEG *b);
  74 bool            seg_contained(SEG *a, SEG *b);
  75 bool            seg_overlap(SEG *a, SEG *b);
  76 bool            seg_left(SEG *a, SEG *b);
  77 bool            seg_over_left(SEG *a, SEG *b);
  78 bool            seg_right(SEG *a, SEG *b);
  79 bool            seg_over_right(SEG *a, SEG *b);
  80 SEG                *seg_union(SEG *a, SEG *b);
  81 SEG                *seg_inter(SEG *a, SEG *b);
  82 void            rt_seg_size(SEG *a, float *sz);
  83
  84 /*
  85 ** Various operators
  86 */
  87 int32           seg_cmp(SEG *a, SEG *b);
  88 bool            seg_lt(SEG *a, SEG *b);
  89 bool            seg_le(SEG *a, SEG *b);
  90 bool            seg_gt(SEG *a, SEG *b);
  91 bool            seg_ge(SEG *a, SEG *b);
  92 bool            seg_different(SEG *a, SEG *b);
  93
  94 /*
  95 ** Auxiliary funxtions
  96 */
  97 static int      restore(char *s, float val, int n);
  98
  99
 100 /*****************************************************************************
 101  * Input/Output functions
 102  *****************************************************************************/
 103
 104 Datum
 105 seg_in(PG_FUNCTION_ARGS)
 106 {
 107         char       *str = PG_GETARG_CSTRING(0);
 108         SEG                *result = palloc(sizeof(SEG));
 109
 110         seg_scanner_init(str);
 111
 112         if (seg_yyparse(result) != 0)
 113                 seg_yyerror(result, "bogus input");
 114
 115         seg_scanner_finish();
 116
 117         PG_RETURN_POINTER(result);
 118 }
 119
 120 Datum
 121 seg_out(PG_FUNCTION_ARGS)
 122 {
 123         SEG                *seg = (SEG *) PG_GETARG_POINTER(0);
 124         char       *result;
 125         char       *p;
 126
 127         p = result = (char *) palloc(40);
 128
 129         if (seg->l_ext == '>' || seg->l_ext == '<' || seg->l_ext == '~')
 130                 p += sprintf(p, "%c", seg->l_ext);
 131
 132         if (seg->lower == seg->upper && seg->l_ext == seg->u_ext)
 133         {
 134                 /*
 135                  * indicates that this interval was built by seg_in off a single point
 136                  */
 137                 p += restore(p, seg->lower, seg->l_sigd);
 138         }
 139         else
 140         {
 141                 if (seg->l_ext != '-')
 142                 {
 143                         /* print the lower boundary if exists */
 144                         p += restore(p, seg->lower, seg->l_sigd);
 145                         p += sprintf(p, " ");
 146                 }
 147                 p += sprintf(p, "..");
 148                 if (seg->u_ext != '-')
 149                 {
 150                         /* print the upper boundary if exists */
 151                         p += sprintf(p, " ");
 152                         if (seg->u_ext == '>' || seg->u_ext == '<' || seg->l_ext == '~')
 153                                 p += sprintf(p, "%c", seg->u_ext);
 154                         p += restore(p, seg->upper, seg->u_sigd);
 155                 }
 156         }
 157
 158         PG_RETURN_CSTRING(result);
 159 }
 160
 161 Datum
 162 seg_center(PG_FUNCTION_ARGS)
 163 {
 164         SEG                *seg = (SEG *) PG_GETARG_POINTER(0);
 165
 166         PG_RETURN_FLOAT4(((float) seg->lower + (float) seg->upper) / 2.0);
 167 }
 168
 169 Datum
 170 seg_lower(PG_FUNCTION_ARGS)
 171 {
 172         SEG                *seg = (SEG *) PG_GETARG_POINTER(0);
 173
 174         PG_RETURN_FLOAT4(seg->lower);
 175 }
 176
 177 Datum
 178 seg_upper(PG_FUNCTION_ARGS)
 179 {
 180         SEG                *seg = (SEG *) PG_GETARG_POINTER(0);
 181
 182         PG_RETURN_FLOAT4(seg->upper);
 183 }
 184
 185
 186 /*****************************************************************************
 187  *                                                 GiST functions
 188  *****************************************************************************/
 189
 190 /*
 191 ** The GiST Consistent method for segments
 192 ** Should return false if for all data items x below entry,
 193 ** the predicate x op query == FALSE, where op is the oper
 194 ** corresponding to strategy in the pg_amop table.
 195 */
 196 bool
 197 gseg_consistent(GISTENTRY *entry,
 198                                 SEG *query,
 199                                 StrategyNumber strategy,
 200                                 Oid subtype,
 201                                 bool *recheck)
 202 {
 203         /* All cases served by this function are exact */
 204         *recheck = false;
 205
 206         /*
 207          * if entry is not leaf, use gseg_internal_consistent, else use
 208          * gseg_leaf_consistent
 209          */
 210         if (GIST_LEAF(entry))
 211                 return (gseg_leaf_consistent((SEG *) DatumGetPointer(entry->key), query, strategy));
 212         else
 213                 return (gseg_internal_consistent((SEG *) DatumGetPointer(entry->key), query, strategy));
 214 }
 215
 216 /*
 217 ** The GiST Union method for segments
 218 ** returns the minimal bounding seg that encloses all the entries in entryvec
 219 */
 220 SEG *
 221 gseg_union(GistEntryVector *entryvec, int *sizep)
 222 {
 223         int                     numranges,
 224                                 i;
 225         SEG                *out = (SEG *) NULL;
 226         SEG                *tmp;
 227
 228 #ifdef GIST_DEBUG
 229         fprintf(stderr, "union\n");
 230 #endif
 231
 232         numranges = entryvec->n;
 233         tmp = (SEG *) DatumGetPointer(entryvec->vector[0].key);
 234         *sizep = sizeof(SEG);
 235
 236         for (i = 1; i < numranges; i++)
 237         {
 238                 out = gseg_binary_union(tmp, (SEG *)
 239                                                                 DatumGetPointer(entryvec->vector[i].key),
 240                                                                 sizep);
 241                 tmp = out;
 242         }
 243
 244         return (out);
 245 }
 246
 247 /*
 248 ** GiST Compress and Decompress methods for segments
 249 ** do not do anything.
 250 */
 251 GISTENTRY *
 252 gseg_compress(GISTENTRY *entry)
 253 {
 254         return (entry);
 255 }
 256
 257 GISTENTRY *
 258 gseg_decompress(GISTENTRY *entry)
 259 {
 260         return (entry);
 261 }
 262
 263 /*
 264 ** The GiST Penalty method for segments
 265 ** As in the R-tree paper, we use change in area as our penalty metric
 266 */
 267 float *
 268 gseg_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result)
 269 {
 270         SEG                *ud;
 271         float           tmp1,
 272                                 tmp2;
 273
 274         ud = seg_union((SEG *) DatumGetPointer(origentry->key),
 275                                    (SEG *) DatumGetPointer(newentry->key));
 276         rt_seg_size(ud, &tmp1);
 277         rt_seg_size((SEG *) DatumGetPointer(origentry->key), &tmp2);
 278         *result = tmp1 - tmp2;
 279
 280 #ifdef GIST_DEBUG
 281         fprintf(stderr, "penalty\n");
 282         fprintf(stderr, "\t%g\n", *result);
 283 #endif
 284
 285         return (result);
 286 }
 287
 288 /*
 289  * Compare function for gseg_picksplit_item: sort by center.
 290  */
 291 static int
 292 gseg_picksplit_item_cmp(const void *a, const void *b)
 293 {
 294         const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
 295         const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
 296
 297         if (i1->center < i2->center)
 298                 return -1;
 299         else if (i1->center == i2->center)
 300                 return 0;
 301         else
 302                 return 1;
 303 }
 304
 305 /*
 306  * The GiST PickSplit method for segments
 307  *
 308  * We used to use Guttman's split algorithm here, but since the data is 1-D
 309  * it's easier and more robust to just sort the segments by center-point and
 310  * split at the middle.
 311  */
 312 GIST_SPLITVEC *
 313 gseg_picksplit(GistEntryVector *entryvec,
 314                            GIST_SPLITVEC *v)
 315 {
 316         int                     i;
 317         SEG                *datum_l,
 318                            *datum_r,
 319                            *seg;
 320         gseg_picksplit_item *sort_items;
 321         OffsetNumber *left,
 322                            *right;
 323         OffsetNumber maxoff;
 324         OffsetNumber firstright;
 325
 326 #ifdef GIST_DEBUG
 327         fprintf(stderr, "picksplit\n");
 328 #endif
 329
 330         /* Valid items in entryvec->vector[] are indexed 1..maxoff */
 331         maxoff = entryvec->n - 1;
 332
 333         /*
 334          * Prepare the auxiliary array and sort it.
 335          */
 336         sort_items = (gseg_picksplit_item *)
 337                 palloc(maxoff * sizeof(gseg_picksplit_item));
 338         for (i = 1; i <= maxoff; i++)
 339         {
 340                 seg = (SEG *) DatumGetPointer(entryvec->vector[i].key);
 341                 /* center calculation is done this way to avoid possible overflow */
 342                 sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
 343                 sort_items[i - 1].index = i;
 344                 sort_items[i - 1].data = seg;
 345         }
 346         qsort(sort_items, maxoff, sizeof(gseg_picksplit_item),
 347                   gseg_picksplit_item_cmp);
 348
 349         /* sort items below "firstright" will go into the left side */
 350         firstright = maxoff / 2;
 351
 352         v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
 353         v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
 354         left = v->spl_left;
 355         v->spl_nleft = 0;
 356         right = v->spl_right;
 357         v->spl_nright = 0;
 358
 359         /*
 360          * Emit segments to the left output page, and compute its bounding box.
 361          */
 362         datum_l = (SEG *) palloc(sizeof(SEG));
 363         memcpy(datum_l, sort_items[0].data, sizeof(SEG));
 364         *left++ = sort_items[0].index;
 365         v->spl_nleft++;
 366         for (i = 1; i < firstright; i++)
 367         {
 368                 datum_l = seg_union(datum_l, sort_items[i].data);
 369                 *left++ = sort_items[i].index;
 370                 v->spl_nleft++;
 371         }
 372
 373         /*
 374          * Likewise for the right page.
 375          */
 376         datum_r = (SEG *) palloc(sizeof(SEG));
 377         memcpy(datum_r, sort_items[firstright].data, sizeof(SEG));
 378         *right++ = sort_items[firstright].index;
 379         v->spl_nright++;
 380         for (i = firstright + 1; i < maxoff; i++)
 381         {
 382                 datum_r = seg_union(datum_r, sort_items[i].data);
 383                 *right++ = sort_items[i].index;
 384                 v->spl_nright++;
 385         }
 386
 387         v->spl_ldatum = PointerGetDatum(datum_l);
 388         v->spl_rdatum = PointerGetDatum(datum_r);
 389
 390         return v;
 391 }
 392
 393 /*
 394 ** Equality methods
 395 */
 396 bool *
 397 gseg_same(SEG *b1, SEG *b2, bool *result)
 398 {
 399         if (seg_same(b1, b2))
 400                 *result = TRUE;
 401         else
 402                 *result = FALSE;
 403
 404 #ifdef GIST_DEBUG
 405         fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
 406 #endif
 407
 408         return (result);
 409 }
 410
 411 /*
 412 ** SUPPORT ROUTINES
 413 */
 414 bool
 415 gseg_leaf_consistent(SEG *key,
 416                                          SEG *query,
 417                                          StrategyNumber strategy)
 418 {
 419         bool            retval;
 420
 421 #ifdef GIST_QUERY_DEBUG
 422         fprintf(stderr, "leaf_consistent, %d\n", strategy);
 423 #endif
 424
 425         switch (strategy)
 426         {
 427                 case RTLeftStrategyNumber:
 428                         retval = (bool) seg_left(key, query);
 429                         break;
 430                 case RTOverLeftStrategyNumber:
 431                         retval = (bool) seg_over_left(key, query);
 432                         break;
 433                 case RTOverlapStrategyNumber:
 434                         retval = (bool) seg_overlap(key, query);
 435                         break;
 436                 case RTOverRightStrategyNumber:
 437                         retval = (bool) seg_over_right(key, query);
 438                         break;
 439                 case RTRightStrategyNumber:
 440                         retval = (bool) seg_right(key, query);
 441                         break;
 442                 case RTSameStrategyNumber:
 443                         retval = (bool) seg_same(key, query);
 444                         break;
 445                 case RTContainsStrategyNumber:
 446                 case RTOldContainsStrategyNumber:
 447                         retval = (bool) seg_contains(key, query);
 448                         break;
 449                 case RTContainedByStrategyNumber:
 450                 case RTOldContainedByStrategyNumber:
 451                         retval = (bool) seg_contained(key, query);
 452                         break;
 453                 default:
 454                         retval = FALSE;
 455         }
 456         return (retval);
 457 }
 458
 459 bool
 460 gseg_internal_consistent(SEG *key,
 461                                                  SEG *query,
 462                                                  StrategyNumber strategy)
 463 {
 464         bool            retval;
 465
 466 #ifdef GIST_QUERY_DEBUG
 467         fprintf(stderr, "internal_consistent, %d\n", strategy);
 468 #endif
 469
 470         switch (strategy)
 471         {
 472                 case RTLeftStrategyNumber:
 473                         retval = (bool) !seg_over_right(key, query);
 474                         break;
 475                 case RTOverLeftStrategyNumber:
 476                         retval = (bool) !seg_right(key, query);
 477                         break;
 478                 case RTOverlapStrategyNumber:
 479                         retval = (bool) seg_overlap(key, query);
 480                         break;
 481                 case RTOverRightStrategyNumber:
 482                         retval = (bool) !seg_left(key, query);
 483                         break;
 484                 case RTRightStrategyNumber:
 485                         retval = (bool) !seg_over_left(key, query);
 486                         break;
 487                 case RTSameStrategyNumber:
 488                 case RTContainsStrategyNumber:
 489                 case RTOldContainsStrategyNumber:
 490                         retval = (bool) seg_contains(key, query);
 491                         break;
 492                 case RTContainedByStrategyNumber:
 493                 case RTOldContainedByStrategyNumber:
 494                         retval = (bool) seg_overlap(key, query);
 495                         break;
 496                 default:
 497                         retval = FALSE;
 498         }
 499         return (retval);
 500 }
 501
 502 SEG *
 503 gseg_binary_union(SEG *r1, SEG *r2, int *sizep)
 504 {
 505         SEG                *retval;
 506
 507         retval = seg_union(r1, r2);
 508         *sizep = sizeof(SEG);
 509
 510         return (retval);
 511 }
 512
 513
 514 bool
 515 seg_contains(SEG *a, SEG *b)
 516 {
 517         return ((a->lower <= b->lower) && (a->upper >= b->upper));
 518 }
 519
 520 bool
 521 seg_contained(SEG *a, SEG *b)
 522 {
 523         return (seg_contains(b, a));
 524 }
 525
 526 /*****************************************************************************
 527  * Operator class for R-tree indexing
 528  *****************************************************************************/
 529
 530 bool
 531 seg_same(SEG *a, SEG *b)
 532 {
 533         return seg_cmp(a, b) == 0;
 534 }
 535
 536 /*      seg_overlap -- does a overlap b?
 537  */
 538 bool
 539 seg_overlap(SEG *a, SEG *b)
 540 {
 541         return (
 542                         ((a->upper >= b->upper) && (a->lower <= b->upper))
 543                         ||
 544                         ((b->upper >= a->upper) && (b->lower <= a->upper))
 545                 );
 546 }
 547
 548 /*      seg_overleft -- is the right edge of (a) located at or left of the right edge of (b)?
 549  */
 550 bool
 551 seg_over_left(SEG *a, SEG *b)
 552 {
 553         return (a->upper <= b->upper);
 554 }
 555
 556 /*      seg_left -- is (a) entirely on the left of (b)?
 557  */
 558 bool
 559 seg_left(SEG *a, SEG *b)
 560 {
 561         return (a->upper < b->lower);
 562 }
 563
 564 /*      seg_right -- is (a) entirely on the right of (b)?
 565  */
 566 bool
 567 seg_right(SEG *a, SEG *b)
 568 {
 569         return (a->lower > b->upper);
 570 }
 571
 572 /*      seg_overright -- is the left edge of (a) located at or right of the left edge of (b)?
 573  */
 574 bool
 575 seg_over_right(SEG *a, SEG *b)
 576 {
 577         return (a->lower >= b->lower);
 578 }
 579
 580
 581 SEG *
 582 seg_union(SEG *a, SEG *b)
 583 {
 584         SEG                *n;
 585
 586         n = (SEG *) palloc(sizeof(*n));
 587
 588         /* take max of upper endpoints */
 589         if (a->upper > b->upper)
 590         {
 591                 n->upper = a->upper;
 592                 n->u_sigd = a->u_sigd;
 593                 n->u_ext = a->u_ext;
 594         }
 595         else
 596         {
 597                 n->upper = b->upper;
 598                 n->u_sigd = b->u_sigd;
 599                 n->u_ext = b->u_ext;
 600         }
 601
 602         /* take min of lower endpoints */
 603         if (a->lower < b->lower)
 604         {
 605                 n->lower = a->lower;
 606                 n->l_sigd = a->l_sigd;
 607                 n->l_ext = a->l_ext;
 608         }
 609         else
 610         {
 611                 n->lower = b->lower;
 612                 n->l_sigd = b->l_sigd;
 613                 n->l_ext = b->l_ext;
 614         }
 615
 616         return (n);
 617 }
 618
 619
 620 SEG *
 621 seg_inter(SEG *a, SEG *b)
 622 {
 623         SEG                *n;
 624
 625         n = (SEG *) palloc(sizeof(*n));
 626
 627         /* take min of upper endpoints */
 628         if (a->upper < b->upper)
 629         {
 630                 n->upper = a->upper;
 631                 n->u_sigd = a->u_sigd;
 632                 n->u_ext = a->u_ext;
 633         }
 634         else
 635         {
 636                 n->upper = b->upper;
 637                 n->u_sigd = b->u_sigd;
 638                 n->u_ext = b->u_ext;
 639         }
 640
 641         /* take max of lower endpoints */
 642         if (a->lower > b->lower)
 643         {
 644                 n->lower = a->lower;
 645                 n->l_sigd = a->l_sigd;
 646                 n->l_ext = a->l_ext;
 647         }
 648         else
 649         {
 650                 n->lower = b->lower;
 651                 n->l_sigd = b->l_sigd;
 652                 n->l_ext = b->l_ext;
 653         }
 654
 655         return (n);
 656 }
 657
 658 void
 659 rt_seg_size(SEG *a, float *size)
 660 {
 661         if (a == (SEG *) NULL || a->upper <= a->lower)
 662                 *size = 0.0;
 663         else
 664                 *size = (float) Abs(a->upper - a->lower);
 665
 666         return;
 667 }
 668
 669 Datum
 670 seg_size(PG_FUNCTION_ARGS)
 671 {
 672         SEG                *seg = (SEG *) PG_GETARG_POINTER(0);
 673
 674         PG_RETURN_FLOAT4((float) Abs(seg->upper - seg->lower));
 675 }
 676
 677
 678 /*****************************************************************************
 679  *                                 Miscellaneous operators
 680  *****************************************************************************/
 681 int32
 682 seg_cmp(SEG *a, SEG *b)
 683 {
 684         /*
 685          * First compare on lower boundary position
 686          */
 687         if (a->lower < b->lower)
 688                 return -1;
 689         if (a->lower > b->lower)
 690                 return 1;
 691
 692         /*
 693          * a->lower == b->lower, so consider type of boundary.
 694          *
 695          * A '-' lower bound is < any other kind (this could only be relevant if
 696          * -HUGE_VAL is used as a regular data value). A '<' lower bound is < any
 697          * other kind except '-'. A '>' lower bound is > any other kind.
 698          */
 699         if (a->l_ext != b->l_ext)
 700         {
 701                 if (a->l_ext == '-')
 702                         return -1;
 703                 if (b->l_ext == '-')
 704                         return 1;
 705                 if (a->l_ext == '<')
 706                         return -1;
 707                 if (b->l_ext == '<')
 708                         return 1;
 709                 if (a->l_ext == '>')
 710                         return 1;
 711                 if (b->l_ext == '>')
 712                         return -1;
 713         }
 714
 715         /*
 716          * For other boundary types, consider # of significant digits first.
 717          */
 718         if (a->l_sigd < b->l_sigd)      /* (a) is blurred and is likely to include (b) */
 719                 return -1;
 720         if (a->l_sigd > b->l_sigd)      /* (a) is less blurred and is likely to be
 721                                                                  * included in (b) */
 722                 return 1;
 723
 724         /*
 725          * For same # of digits, an approximate boundary is more blurred than
 726          * exact.
 727          */
 728         if (a->l_ext != b->l_ext)
 729         {
 730                 if (a->l_ext == '~')    /* (a) is approximate, while (b) is exact */
 731                         return -1;
 732                 if (b->l_ext == '~')
 733                         return 1;
 734                 /* can't get here unless data is corrupt */
 735                 elog(ERROR, "bogus lower boundary types %d %d",
 736                          (int) a->l_ext, (int) b->l_ext);
 737         }
 738
 739         /* at this point, the lower boundaries are identical */
 740
 741         /*
 742          * First compare on upper boundary position
 743          */
 744         if (a->upper < b->upper)
 745                 return -1;
 746         if (a->upper > b->upper)
 747                 return 1;
 748
 749         /*
 750          * a->upper == b->upper, so consider type of boundary.
 751          *
 752          * A '-' upper bound is > any other kind (this could only be relevant if
 753          * HUGE_VAL is used as a regular data value). A '<' upper bound is < any
 754          * other kind. A '>' upper bound is > any other kind except '-'.
 755          */
 756         if (a->u_ext != b->u_ext)
 757         {
 758                 if (a->u_ext == '-')
 759                         return 1;
 760                 if (b->u_ext == '-')
 761                         return -1;
 762                 if (a->u_ext == '<')
 763                         return -1;
 764                 if (b->u_ext == '<')
 765                         return 1;
 766                 if (a->u_ext == '>')
 767                         return 1;
 768                 if (b->u_ext == '>')
 769                         return -1;
 770         }
 771
 772         /*
 773          * For other boundary types, consider # of significant digits first. Note
 774          * result here is converse of the lower-boundary case.
 775          */
 776         if (a->u_sigd < b->u_sigd)      /* (a) is blurred and is likely to include (b) */
 777                 return 1;
 778         if (a->u_sigd > b->u_sigd)      /* (a) is less blurred and is likely to be
 779                                                                  * included in (b) */
 780                 return -1;
 781
 782         /*
 783          * For same # of digits, an approximate boundary is more blurred than
 784          * exact.  Again, result is converse of lower-boundary case.
 785          */
 786         if (a->u_ext != b->u_ext)
 787         {
 788                 if (a->u_ext == '~')    /* (a) is approximate, while (b) is exact */
 789                         return 1;
 790                 if (b->u_ext == '~')
 791                         return -1;
 792                 /* can't get here unless data is corrupt */
 793                 elog(ERROR, "bogus upper boundary types %d %d",
 794                          (int) a->u_ext, (int) b->u_ext);
 795         }
 796
 797         return 0;
 798 }
 799
 800 bool
 801 seg_lt(SEG *a, SEG *b)
 802 {
 803         return seg_cmp(a, b) < 0;
 804 }
 805
 806 bool
 807 seg_le(SEG *a, SEG *b)
 808 {
 809         return seg_cmp(a, b) <= 0;
 810 }
 811
 812 bool
 813 seg_gt(SEG *a, SEG *b)
 814 {
 815         return seg_cmp(a, b) > 0;
 816 }
 817
 818 bool
 819 seg_ge(SEG *a, SEG *b)
 820 {
 821         return seg_cmp(a, b) >= 0;
 822 }
 823
 824 bool
 825 seg_different(SEG *a, SEG *b)
 826 {
 827         return seg_cmp(a, b) != 0;
 828 }
 829
 830
 831
 832 /*****************************************************************************
 833  *                                 Auxiliary functions
 834  *****************************************************************************/
 835
 836 /* The purpose of this routine is to print the floating point
 837  * value with exact number of significant digits. Its behaviour
 838  * is similar to %.ng except it prints 8.00 where %.ng would
 839  * print 8
 840  */
 841 static int
 842 restore(char *result, float val, int n)
 843 {
 844         static char efmt[8] = {'%', '-', '1', '5', '.', '#', 'e', 0};
 845         char            buf[25] = {
 846                 '0', '0', '0', '0', '0',
 847                 '0', '0', '0', '0', '0',
 848                 '0', '0', '0', '0', '0',
 849                 '0', '0', '0', '0', '0',
 850                 '0', '0', '0', '0', '\0'
 851         };
 852         char       *p;
 853         int                     exp;
 854         int                     i,
 855                                 dp,
 856                                 sign;
 857
 858         /*
 859          * put a cap on the number of siugnificant digits to avoid nonsense in the
 860          * output
 861          */
 862         n = Min(n, FLT_DIG);
 863
 864         /* remember the sign */
 865         sign = (val < 0 ? 1 : 0);
 866
 867         efmt[5] = '0' + (n - 1) % 10;           /* makes %-15.(n-1)e -- this format
 868                                                                                  * guarantees that the exponent is
 869                                                                                  * always present */
 870
 871         sprintf(result, efmt, val);
 872
 873         /* trim the spaces left by the %e */
 874         for (p = result; *p != ' '; p++);
 875         *p = '\0';
 876
 877         /* get the exponent */
 878         strtok(pstrdup(result), "e");
 879         exp = atoi(strtok(NULL, "e"));
 880
 881         if (exp == 0)
 882         {
 883                 /* use the supplied mantyssa with sign */
 884                 strcpy((char *) strchr(result, 'e'), "");
 885         }
 886         else
 887         {
 888                 if (Abs(exp) <= 4)
 889                 {
 890                         /*
 891                          * remove the decimal point from the mantyssa and write the digits
 892                          * to the buf array
 893                          */
 894                         for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
 895                         {
 896                                 buf[i] = *p;
 897                                 if (*p == '.')
 898                                 {
 899                                         dp = i--;       /* skip the decimal point */
 900                                 }
 901                         }
 902                         if (dp == 0)
 903                                 dp = i--;               /* no decimal point was found in the above
 904                                                                  * for() loop */
 905
 906                         if (exp > 0)
 907                         {
 908                                 if (dp - 10 + exp >= n)
 909                                 {
 910                                         /*
 911                                          * the decimal point is behind the last significant digit;
 912                                          * the digits in between must be converted to the exponent
 913                                          * and the decimal point placed after the first digit
 914                                          */
 915                                         exp = dp - 10 + exp - n;
 916                                         buf[10 + n] = '\0';
 917
 918                                         /* insert the decimal point */
 919                                         if (n > 1)
 920                                         {
 921                                                 dp = 11;
 922                                                 for (i = 23; i > dp; i--)
 923                                                         buf[i] = buf[i - 1];
 924                                                 buf[dp] = '.';
 925                                         }
 926
 927                                         /*
 928                                          * adjust the exponent by the number of digits after the
 929                                          * decimal point
 930                                          */
 931                                         if (n > 1)
 932                                                 sprintf(&buf[11 + n], "e%d", exp + n - 1);
 933                                         else
 934                                                 sprintf(&buf[11], "e%d", exp + n - 1);
 935
 936                                         if (sign)
 937                                         {
 938                                                 buf[9] = '-';
 939                                                 strcpy(result, &buf[9]);
 940                                         }
 941                                         else
 942                                                 strcpy(result, &buf[10]);
 943                                 }
 944                                 else
 945                                 {                               /* insert the decimal point */
 946                                         dp += exp;
 947                                         for (i = 23; i > dp; i--)
 948                                                 buf[i] = buf[i - 1];
 949                                         buf[11 + n] = '\0';
 950                                         buf[dp] = '.';
 951                                         if (sign)
 952                                         {
 953                                                 buf[9] = '-';
 954                                                 strcpy(result, &buf[9]);
 955                                         }
 956                                         else
 957                                                 strcpy(result, &buf[10]);
 958                                 }
 959                         }
 960                         else
 961                         {                                       /* exp <= 0 */
 962                                 dp += exp - 1;
 963                                 buf[10 + n] = '\0';
 964                                 buf[dp] = '.';
 965                                 if (sign)
 966                                 {
 967                                         buf[dp - 2] = '-';
 968                                         strcpy(result, &buf[dp - 2]);
 969                                 }
 970                                 else
 971                                         strcpy(result, &buf[dp - 1]);
 972                         }
 973                 }
 974
 975                 /* do nothing for Abs(exp) > 4; %e must be OK */
 976                 /* just get rid of zeroes after [eE]- and +zeroes after [Ee]. */
 977
 978                 /* ... this is not done yet. */
 979         }
 980         return (strlen(result));
 981 }
 982
 983
 984 /*
 985 ** Miscellany
 986 */
 987
 988 bool
 989 seg_contains_int(SEG *a, int *b)
 990 {
 991         return ((a->lower <= *b) && (a->upper >= *b));
 992 }
 993
 994 bool
 995 seg_contains_float4(SEG *a, float4 *b)
 996 {
 997         return ((a->lower <= *b) && (a->upper >= *b));
 998 }
 999
1000 bool
1001 seg_contains_float8(SEG *a, float8 *b)
1002 {
1003         return ((a->lower <= *b) && (a->upper >= *b));
1004 }
1005
1006 /* find out the number of significant digits in a string representing
1007  * a floating point number
1008  */
1009 int
1010 significant_digits(char *s)
1011 {
1012         char       *p = s;
1013         int                     n,
1014                                 c,
1015                                 zeroes;
1016
1017         zeroes = 1;
1018         /* skip leading zeroes and sign */
1019         for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
1020
1021         /* skip decimal point and following zeroes */
1022         for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
1023         {
1024                 if (c != '.')
1025                         zeroes++;
1026         }
1027
1028         /* count significant digits (n) */
1029         for (c = *p, n = 0; c != 0; c = *(++p))
1030         {
1031                 if (!((c >= '0' && c <= '9') || (c == '.')))
1032                         break;
1033                 if (c != '.')
1034                         n++;
1035         }
1036
1037         if (!n)
1038                 return (zeroes);
1039
1040         return (n);
1041 }