LCOV - code coverage report
Current view: top level - contrib/seg - seg.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 322 432 74.5 %
Date: 2020-05-29 01:06:25 Functions: 58 66 87.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13