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

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