LCOV - code coverage report
Current view: top level - contrib/seg - seg.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 321 416 77.2 %
Date: 2019-11-13 22:07:24 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        9224 : gseg_consistent(PG_FUNCTION_ARGS)
     196             : {
     197        9224 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     198        9224 :     Datum       query = PG_GETARG_DATUM(1);
     199        9224 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     200             : 
     201             :     /* Oid      subtype = PG_GETARG_OID(3); */
     202        9224 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     203             : 
     204             :     /* All cases served by this function are exact */
     205        9224 :     *recheck = false;
     206             : 
     207             :     /*
     208             :      * if entry is not leaf, use gseg_internal_consistent, else use
     209             :      * gseg_leaf_consistent
     210             :      */
     211        9224 :     if (GIST_LEAF(entry))
     212        9096 :         return gseg_leaf_consistent(entry->key, query, strategy);
     213             :     else
     214         128 :         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       10892 : gseg_penalty(PG_FUNCTION_ARGS)
     270             : {
     271       10892 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
     272       10892 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     273       10892 :     float      *result = (float *) PG_GETARG_POINTER(2);
     274             :     SEG        *ud;
     275             :     float       tmp1,
     276             :                 tmp2;
     277             : 
     278       10892 :     ud = DatumGetSegP(DirectFunctionCall2(seg_union,
     279             :                                           origentry->key,
     280             :                                           newentry->key));
     281       10892 :     rt_seg_size(ud, &tmp1);
     282       10892 :     rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
     283       10892 :     *result = tmp1 - tmp2;
     284             : 
     285             : #ifdef GIST_DEBUG
     286             :     fprintf(stderr, "penalty\n");
     287             :     fprintf(stderr, "\t%g\n", *result);
     288             : #endif
     289             : 
     290       10892 :     PG_RETURN_POINTER(result);
     291             : }
     292             : 
     293             : /*
     294             :  * Compare function for gseg_picksplit_item: sort by center.
     295             :  */
     296             : static int
     297       52718 : gseg_picksplit_item_cmp(const void *a, const void *b)
     298             : {
     299       52718 :     const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
     300       52718 :     const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
     301             : 
     302       52718 :     if (i1->center < i2->center)
     303       22250 :         return -1;
     304       30468 :     else if (i1->center == i2->center)
     305        9142 :         return 0;
     306             :     else
     307       21326 :         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          30 : gseg_picksplit(PG_FUNCTION_ARGS)
     319             : {
     320          30 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     321          30 :     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          30 :     maxoff = entryvec->n - 1;
     338             : 
     339             :     /*
     340             :      * Prepare the auxiliary array and sort it.
     341             :      */
     342          30 :     sort_items = (gseg_picksplit_item *)
     343          30 :         palloc(maxoff * sizeof(gseg_picksplit_item));
     344        7890 :     for (i = 1; i <= maxoff; i++)
     345             :     {
     346        7860 :         seg = DatumGetSegP(entryvec->vector[i].key);
     347             :         /* center calculation is done this way to avoid possible overflow */
     348        7860 :         sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
     349        7860 :         sort_items[i - 1].index = i;
     350        7860 :         sort_items[i - 1].data = seg;
     351             :     }
     352          30 :     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          30 :     firstright = maxoff / 2;
     357             : 
     358          30 :     v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
     359          30 :     v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
     360          30 :     left = v->spl_left;
     361          30 :     v->spl_nleft = 0;
     362          30 :     right = v->spl_right;
     363          30 :     v->spl_nright = 0;
     364             : 
     365             :     /*
     366             :      * Emit segments to the left output page, and compute its bounding box.
     367             :      */
     368          30 :     seg_l = (SEG *) palloc(sizeof(SEG));
     369          30 :     memcpy(seg_l, sort_items[0].data, sizeof(SEG));
     370          30 :     *left++ = sort_items[0].index;
     371          30 :     v->spl_nleft++;
     372        3930 :     for (i = 1; i < firstright; i++)
     373             :     {
     374        3900 :         Datum       sortitem = PointerGetDatum(sort_items[i].data);
     375             : 
     376        3900 :         seg_l = DatumGetSegP(DirectFunctionCall2(seg_union,
     377             :                                                  PointerGetDatum(seg_l),
     378             :                                                  sortitem));
     379        3900 :         *left++ = sort_items[i].index;
     380        3900 :         v->spl_nleft++;
     381             :     }
     382             : 
     383             :     /*
     384             :      * Likewise for the right page.
     385             :      */
     386          30 :     seg_r = (SEG *) palloc(sizeof(SEG));
     387          30 :     memcpy(seg_r, sort_items[firstright].data, sizeof(SEG));
     388          30 :     *right++ = sort_items[firstright].index;
     389          30 :     v->spl_nright++;
     390        3930 :     for (i = firstright + 1; i < maxoff; i++)
     391             :     {
     392        3900 :         Datum       sortitem = PointerGetDatum(sort_items[i].data);
     393             : 
     394        3900 :         seg_r = DatumGetSegP(DirectFunctionCall2(seg_union,
     395             :                                                  PointerGetDatum(seg_r),
     396             :                                                  sortitem));
     397        3900 :         *right++ = sort_items[i].index;
     398        3900 :         v->spl_nright++;
     399             :     }
     400             : 
     401          30 :     v->spl_ldatum = PointerGetDatum(seg_l);
     402          30 :     v->spl_rdatum = PointerGetDatum(seg_r);
     403             : 
     404          30 :     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        4478 :         *result = true;
     417             :     else
     418         152 :         *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        9096 : 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        9096 :     switch (strategy)
     440             :     {
     441             :         case RTLeftStrategyNumber:
     442           0 :             retval = DirectFunctionCall2(seg_left, key, query);
     443           0 :             break;
     444             :         case RTOverLeftStrategyNumber:
     445           0 :             retval = DirectFunctionCall2(seg_over_left, key, query);
     446           0 :             break;
     447             :         case RTOverlapStrategyNumber:
     448           0 :             retval = DirectFunctionCall2(seg_overlap, key, query);
     449           0 :             break;
     450             :         case RTOverRightStrategyNumber:
     451           0 :             retval = DirectFunctionCall2(seg_over_right, key, query);
     452           0 :             break;
     453             :         case RTRightStrategyNumber:
     454           0 :             retval = DirectFunctionCall2(seg_right, key, query);
     455           0 :             break;
     456             :         case RTSameStrategyNumber:
     457           0 :             retval = DirectFunctionCall2(seg_same, key, query);
     458           0 :             break;
     459             :         case RTContainsStrategyNumber:
     460             :         case RTOldContainsStrategyNumber:
     461        9096 :             retval = DirectFunctionCall2(seg_contains, key, query);
     462        9096 :             break;
     463             :         case RTContainedByStrategyNumber:
     464             :         case RTOldContainedByStrategyNumber:
     465           0 :             retval = DirectFunctionCall2(seg_contained, key, query);
     466           0 :             break;
     467             :         default:
     468           0 :             retval = false;
     469             :     }
     470             : 
     471        9096 :     PG_RETURN_DATUM(retval);
     472             : }
     473             : 
     474             : static Datum
     475         128 : 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         128 :     switch (strategy)
     484             :     {
     485             :         case RTLeftStrategyNumber:
     486           0 :             retval =
     487           0 :                 !DatumGetBool(DirectFunctionCall2(seg_over_right, key, query));
     488           0 :             break;
     489             :         case RTOverLeftStrategyNumber:
     490           0 :             retval =
     491           0 :                 !DatumGetBool(DirectFunctionCall2(seg_right, key, query));
     492           0 :             break;
     493             :         case RTOverlapStrategyNumber:
     494           0 :             retval =
     495           0 :                 DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
     496           0 :             break;
     497             :         case RTOverRightStrategyNumber:
     498           0 :             retval =
     499           0 :                 !DatumGetBool(DirectFunctionCall2(seg_left, key, query));
     500           0 :             break;
     501             :         case RTRightStrategyNumber:
     502           0 :             retval =
     503           0 :                 !DatumGetBool(DirectFunctionCall2(seg_over_left, key, query));
     504           0 :             break;
     505             :         case RTSameStrategyNumber:
     506             :         case RTContainsStrategyNumber:
     507             :         case RTOldContainsStrategyNumber:
     508         128 :             retval =
     509         128 :                 DatumGetBool(DirectFunctionCall2(seg_contains, key, query));
     510         128 :             break;
     511             :         case RTContainedByStrategyNumber:
     512             :         case RTOldContainedByStrategyNumber:
     513           0 :             retval =
     514           0 :                 DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
     515           0 :             break;
     516             :         default:
     517           0 :             retval = false;
     518             :     }
     519             : 
     520         128 :     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        9254 : seg_contains(PG_FUNCTION_ARGS)
     537             : {
     538        9254 :     SEG        *a = PG_GETARG_SEG_P(0);
     539        9254 :     SEG        *b = PG_GETARG_SEG_P(1);
     540             : 
     541        9254 :     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(
     561             :                                     DirectFunctionCall2(seg_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));
     562             : 
     563        4918 :     PG_RETURN_BOOL(cmp == 0);
     564             : }
     565             : 
     566             : /*  seg_overlap -- does a overlap b?
     567             :  */
     568             : Datum
     569          30 : seg_overlap(PG_FUNCTION_ARGS)
     570             : {
     571          30 :     SEG        *a = PG_GETARG_SEG_P(0);
     572          30 :     SEG        *b = PG_GETARG_SEG_P(1);
     573             : 
     574          30 :     PG_RETURN_BOOL(((a->upper >= b->upper) && (a->lower <= b->upper)) ||
     575             :                    ((b->upper >= a->upper) && (b->lower <= a->upper)));
     576             : }
     577             : 
     578             : /*  seg_over_left -- is the right edge of (a) located at or left of the right edge of (b)?
     579             :  */
     580             : Datum
     581          22 : seg_over_left(PG_FUNCTION_ARGS)
     582             : {
     583          22 :     SEG        *a = PG_GETARG_SEG_P(0);
     584          22 :     SEG        *b = PG_GETARG_SEG_P(1);
     585             : 
     586          22 :     PG_RETURN_BOOL(a->upper <= b->upper);
     587             : }
     588             : 
     589             : /*  seg_left -- is (a) entirely on the left of (b)?
     590             :  */
     591             : Datum
     592          22 : seg_left(PG_FUNCTION_ARGS)
     593             : {
     594          22 :     SEG        *a = PG_GETARG_SEG_P(0);
     595          22 :     SEG        *b = PG_GETARG_SEG_P(1);
     596             : 
     597          22 :     PG_RETURN_BOOL(a->upper < b->lower);
     598             : }
     599             : 
     600             : /*  seg_right -- is (a) entirely on the right of (b)?
     601             :  */
     602             : Datum
     603          22 : seg_right(PG_FUNCTION_ARGS)
     604             : {
     605          22 :     SEG        *a = PG_GETARG_SEG_P(0);
     606          22 :     SEG        *b = PG_GETARG_SEG_P(1);
     607             : 
     608          22 :     PG_RETURN_BOOL(a->lower > b->upper);
     609             : }
     610             : 
     611             : /*  seg_over_right -- is the left edge of (a) located at or right of the left edge of (b)?
     612             :  */
     613             : Datum
     614          22 : seg_over_right(PG_FUNCTION_ARGS)
     615             : {
     616          22 :     SEG        *a = PG_GETARG_SEG_P(0);
     617          22 :     SEG        *b = PG_GETARG_SEG_P(1);
     618             : 
     619          22 :     PG_RETURN_BOOL(a->lower >= b->lower);
     620             : }
     621             : 
     622             : Datum
     623       23324 : seg_union(PG_FUNCTION_ARGS)
     624             : {
     625       23324 :     SEG        *a = PG_GETARG_SEG_P(0);
     626       23324 :     SEG        *b = PG_GETARG_SEG_P(1);
     627             :     SEG        *n;
     628             : 
     629       23324 :     n = (SEG *) palloc(sizeof(*n));
     630             : 
     631             :     /* take max of upper endpoints */
     632       23324 :     if (a->upper > b->upper)
     633             :     {
     634       19858 :         n->upper = a->upper;
     635       19858 :         n->u_sigd = a->u_sigd;
     636       19858 :         n->u_ext = a->u_ext;
     637             :     }
     638             :     else
     639             :     {
     640        3466 :         n->upper = b->upper;
     641        3466 :         n->u_sigd = b->u_sigd;
     642        3466 :         n->u_ext = b->u_ext;
     643             :     }
     644             : 
     645             :     /* take min of lower endpoints */
     646       23324 :     if (a->lower < b->lower)
     647             :     {
     648       22752 :         n->lower = a->lower;
     649       22752 :         n->l_sigd = a->l_sigd;
     650       22752 :         n->l_ext = a->l_ext;
     651             :     }
     652             :     else
     653             :     {
     654         572 :         n->lower = b->lower;
     655         572 :         n->l_sigd = b->l_sigd;
     656         572 :         n->l_ext = b->l_ext;
     657             :     }
     658             : 
     659       23324 :     PG_RETURN_POINTER(n);
     660             : }
     661             : 
     662             : Datum
     663           0 : seg_inter(PG_FUNCTION_ARGS)
     664             : {
     665           0 :     SEG        *a = PG_GETARG_SEG_P(0);
     666           0 :     SEG        *b = PG_GETARG_SEG_P(1);
     667             :     SEG        *n;
     668             : 
     669           0 :     n = (SEG *) palloc(sizeof(*n));
     670             : 
     671             :     /* take min of upper endpoints */
     672           0 :     if (a->upper < b->upper)
     673             :     {
     674           0 :         n->upper = a->upper;
     675           0 :         n->u_sigd = a->u_sigd;
     676           0 :         n->u_ext = a->u_ext;
     677             :     }
     678             :     else
     679             :     {
     680           0 :         n->upper = b->upper;
     681           0 :         n->u_sigd = b->u_sigd;
     682           0 :         n->u_ext = b->u_ext;
     683             :     }
     684             : 
     685             :     /* take max of lower endpoints */
     686           0 :     if (a->lower > b->lower)
     687             :     {
     688           0 :         n->lower = a->lower;
     689           0 :         n->l_sigd = a->l_sigd;
     690           0 :         n->l_ext = a->l_ext;
     691             :     }
     692             :     else
     693             :     {
     694           0 :         n->lower = b->lower;
     695           0 :         n->l_sigd = b->l_sigd;
     696           0 :         n->l_ext = b->l_ext;
     697             :     }
     698             : 
     699           0 :     PG_RETURN_POINTER(n);
     700             : }
     701             : 
     702             : static void
     703       21784 : rt_seg_size(SEG *a, float *size)
     704             : {
     705       21784 :     if (a == (SEG *) NULL || a->upper <= a->lower)
     706           0 :         *size = 0.0;
     707             :     else
     708       21784 :         *size = (float) Abs(a->upper - a->lower);
     709             : 
     710       21784 :     return;
     711             : }
     712             : 
     713             : Datum
     714           0 : seg_size(PG_FUNCTION_ARGS)
     715             : {
     716           0 :     SEG        *seg = PG_GETARG_SEG_P(0);
     717             : 
     718           0 :     PG_RETURN_FLOAT4((float) Abs(seg->upper - seg->lower));
     719             : }
     720             : 
     721             : 
     722             : /*****************************************************************************
     723             :  *                 Miscellaneous operators
     724             :  *****************************************************************************/
     725             : Datum
     726        8866 : seg_cmp(PG_FUNCTION_ARGS)
     727             : {
     728        8866 :     SEG        *a = PG_GETARG_SEG_P(0);
     729        8866 :     SEG        *b = PG_GETARG_SEG_P(1);
     730             : 
     731             :     /*
     732             :      * First compare on lower boundary position
     733             :      */
     734        8866 :     if (a->lower < b->lower)
     735        1808 :         PG_RETURN_INT32(-1);
     736        7058 :     if (a->lower > b->lower)
     737        1600 :         PG_RETURN_INT32(1);
     738             : 
     739             :     /*
     740             :      * a->lower == b->lower, so consider type of boundary.
     741             :      *
     742             :      * A '-' lower bound is < any other kind (this could only be relevant if
     743             :      * -HUGE_VAL is used as a regular data value). A '<' lower bound is < any
     744             :      * other kind except '-'. A '>' lower bound is > any other kind.
     745             :      */
     746        5458 :     if (a->l_ext != b->l_ext)
     747             :     {
     748         132 :         if (a->l_ext == '-')
     749           0 :             PG_RETURN_INT32(-1);
     750         132 :         if (b->l_ext == '-')
     751           0 :             PG_RETURN_INT32(1);
     752         132 :         if (a->l_ext == '<')
     753          52 :             PG_RETURN_INT32(-1);
     754          80 :         if (b->l_ext == '<')
     755          42 :             PG_RETURN_INT32(1);
     756          38 :         if (a->l_ext == '>')
     757          26 :             PG_RETURN_INT32(1);
     758          12 :         if (b->l_ext == '>')
     759          12 :             PG_RETURN_INT32(-1);
     760             :     }
     761             : 
     762             :     /*
     763             :      * For other boundary types, consider # of significant digits first.
     764             :      */
     765        5326 :     if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
     766          36 :         PG_RETURN_INT32(-1);
     767        5290 :     if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
     768             :                                  * included in (b) */
     769          36 :         PG_RETURN_INT32(1);
     770             : 
     771             :     /*
     772             :      * For same # of digits, an approximate boundary is more blurred than
     773             :      * exact.
     774             :      */
     775        5254 :     if (a->l_ext != b->l_ext)
     776             :     {
     777           0 :         if (a->l_ext == '~') /* (a) is approximate, while (b) is exact */
     778           0 :             PG_RETURN_INT32(-1);
     779           0 :         if (b->l_ext == '~')
     780           0 :             PG_RETURN_INT32(1);
     781             :         /* can't get here unless data is corrupt */
     782           0 :         elog(ERROR, "bogus lower boundary types %d %d",
     783             :              (int) a->l_ext, (int) b->l_ext);
     784             :     }
     785             : 
     786             :     /* at this point, the lower boundaries are identical */
     787             : 
     788             :     /*
     789             :      * First compare on upper boundary position
     790             :      */
     791        5254 :     if (a->upper < b->upper)
     792         326 :         PG_RETURN_INT32(-1);
     793        4928 :     if (a->upper > b->upper)
     794         252 :         PG_RETURN_INT32(1);
     795             : 
     796             :     /*
     797             :      * a->upper == b->upper, so consider type of boundary.
     798             :      *
     799             :      * A '-' upper bound is > any other kind (this could only be relevant if
     800             :      * HUGE_VAL is used as a regular data value). A '<' upper bound is < any
     801             :      * other kind. A '>' upper bound is > any other kind except '-'.
     802             :      */
     803        4676 :     if (a->u_ext != b->u_ext)
     804             :     {
     805         146 :         if (a->u_ext == '-')
     806           0 :             PG_RETURN_INT32(1);
     807         146 :         if (b->u_ext == '-')
     808           0 :             PG_RETURN_INT32(-1);
     809         146 :         if (a->u_ext == '<')
     810           6 :             PG_RETURN_INT32(-1);
     811         140 :         if (b->u_ext == '<')
     812           2 :             PG_RETURN_INT32(1);
     813         138 :         if (a->u_ext == '>')
     814          76 :             PG_RETURN_INT32(1);
     815          62 :         if (b->u_ext == '>')
     816          62 :             PG_RETURN_INT32(-1);
     817             :     }
     818             : 
     819             :     /*
     820             :      * For other boundary types, consider # of significant digits first. Note
     821             :      * result here is converse of the lower-boundary case.
     822             :      */
     823        4530 :     if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
     824          24 :         PG_RETURN_INT32(1);
     825        4506 :     if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
     826             :                                  * included in (b) */
     827          24 :         PG_RETURN_INT32(-1);
     828             : 
     829             :     /*
     830             :      * For same # of digits, an approximate boundary is more blurred than
     831             :      * exact.  Again, result is converse of lower-boundary case.
     832             :      */
     833        4482 :     if (a->u_ext != b->u_ext)
     834             :     {
     835           0 :         if (a->u_ext == '~') /* (a) is approximate, while (b) is exact */
     836           0 :             PG_RETURN_INT32(1);
     837           0 :         if (b->u_ext == '~')
     838           0 :             PG_RETURN_INT32(-1);
     839             :         /* can't get here unless data is corrupt */
     840           0 :         elog(ERROR, "bogus upper boundary types %d %d",
     841             :              (int) a->u_ext, (int) b->u_ext);
     842             :     }
     843             : 
     844        4482 :     PG_RETURN_INT32(0);
     845             : }
     846             : 
     847             : Datum
     848           0 : seg_lt(PG_FUNCTION_ARGS)
     849             : {
     850           0 :     int         cmp = DatumGetInt32(
     851             :                                     DirectFunctionCall2(seg_cmp, PG_GETARG_DATUM(0), 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(
     860             :                                     DirectFunctionCall2(seg_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));
     861             : 
     862           0 :     PG_RETURN_BOOL(cmp <= 0);
     863             : }
     864             : 
     865             : Datum
     866           0 : seg_gt(PG_FUNCTION_ARGS)
     867             : {
     868           0 :     int         cmp = DatumGetInt32(
     869             :                                     DirectFunctionCall2(seg_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));
     870             : 
     871           0 :     PG_RETURN_BOOL(cmp > 0);
     872             : }
     873             : 
     874             : Datum
     875           0 : seg_ge(PG_FUNCTION_ARGS)
     876             : {
     877           0 :     int         cmp = DatumGetInt32(
     878             :                                     DirectFunctionCall2(seg_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));
     879             : 
     880           0 :     PG_RETURN_BOOL(cmp >= 0);
     881             : }
     882             : 
     883             : 
     884             : Datum
     885           4 : seg_different(PG_FUNCTION_ARGS)
     886             : {
     887           4 :     int         cmp = DatumGetInt32(
     888             :                                     DirectFunctionCall2(seg_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));
     889             : 
     890           4 :     PG_RETURN_BOOL(cmp != 0);
     891             : }
     892             : 
     893             : 
     894             : 
     895             : /*****************************************************************************
     896             :  *                 Auxiliary functions
     897             :  *****************************************************************************/
     898             : 
     899             : /*
     900             :  * The purpose of this routine is to print the given floating point
     901             :  * value with exactly n significant digits.  Its behaviour
     902             :  * is similar to %.ng except it prints 8.00 where %.ng would
     903             :  * print 8.  Returns the length of the string written at "result".
     904             :  *
     905             :  * Caller must provide a sufficiently large result buffer; 16 bytes
     906             :  * should be enough for all known float implementations.
     907             :  */
     908             : static int
     909         648 : restore(char *result, float val, int n)
     910             : {
     911         648 :     char        buf[25] = {
     912             :         '0', '0', '0', '0', '0',
     913             :         '0', '0', '0', '0', '0',
     914             :         '0', '0', '0', '0', '0',
     915             :         '0', '0', '0', '0', '0',
     916             :         '0', '0', '0', '0', '\0'
     917             :     };
     918             :     char       *p;
     919             :     int         exp;
     920             :     int         i,
     921             :                 dp,
     922             :                 sign;
     923             : 
     924             :     /*
     925             :      * Put a cap on the number of significant digits to avoid garbage in the
     926             :      * output and ensure we don't overrun the result buffer.
     927             :      */
     928         648 :     n = Min(n, FLT_DIG);
     929             : 
     930             :     /* remember the sign */
     931         648 :     sign = (val < 0 ? 1 : 0);
     932             : 
     933             :     /* print, in %e style to start with */
     934         648 :     sprintf(result, "%.*e", n - 1, val);
     935             : 
     936             :     /* find the exponent */
     937         648 :     p = strchr(result, 'e');
     938             : 
     939             :     /* punt if we have 'inf' or similar */
     940         648 :     if (p == NULL)
     941           0 :         return strlen(result);
     942             : 
     943         648 :     exp = atoi(p + 1);
     944         648 :     if (exp == 0)
     945             :     {
     946             :         /* just truncate off the 'e+00' */
     947         338 :         *p = '\0';
     948             :     }
     949             :     else
     950             :     {
     951         310 :         if (Abs(exp) <= 4)
     952             :         {
     953             :             /*
     954             :              * remove the decimal point from the mantissa and write the digits
     955             :              * to the buf array
     956             :              */
     957        1258 :             for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
     958             :             {
     959         984 :                 buf[i] = *p;
     960         984 :                 if (*p == '.')
     961             :                 {
     962         258 :                     dp = i--;   /* skip the decimal point */
     963             :                 }
     964             :             }
     965         274 :             if (dp == 0)
     966          16 :                 dp = i--;       /* no decimal point was found in the above
     967             :                                  * for() loop */
     968             : 
     969         274 :             if (exp > 0)
     970             :             {
     971         264 :                 if (dp - 10 + exp >= n)
     972             :                 {
     973             :                     /*
     974             :                      * the decimal point is behind the last significant digit;
     975             :                      * the digits in between must be converted to the exponent
     976             :                      * and the decimal point placed after the first digit
     977             :                      */
     978          86 :                     exp = dp - 10 + exp - n;
     979          86 :                     buf[10 + n] = '\0';
     980             : 
     981             :                     /* insert the decimal point */
     982          86 :                     if (n > 1)
     983             :                     {
     984          78 :                         dp = 11;
     985        1014 :                         for (i = 23; i > dp; i--)
     986         936 :                             buf[i] = buf[i - 1];
     987          78 :                         buf[dp] = '.';
     988             :                     }
     989             : 
     990             :                     /*
     991             :                      * adjust the exponent by the number of digits after the
     992             :                      * decimal point
     993             :                      */
     994          86 :                     if (n > 1)
     995          78 :                         sprintf(&buf[11 + n], "e%d", exp + n - 1);
     996             :                     else
     997           8 :                         sprintf(&buf[11], "e%d", exp + n - 1);
     998             : 
     999          86 :                     if (sign)
    1000             :                     {
    1001           0 :                         buf[9] = '-';
    1002           0 :                         strcpy(result, &buf[9]);
    1003             :                     }
    1004             :                     else
    1005          86 :                         strcpy(result, &buf[10]);
    1006             :                 }
    1007             :                 else
    1008             :                 {               /* insert the decimal point */
    1009         178 :                     dp += exp;
    1010        2136 :                     for (i = 23; i > dp; i--)
    1011        1958 :                         buf[i] = buf[i - 1];
    1012         178 :                     buf[11 + n] = '\0';
    1013         178 :                     buf[dp] = '.';
    1014         178 :                     if (sign)
    1015             :                     {
    1016           0 :                         buf[9] = '-';
    1017           0 :                         strcpy(result, &buf[9]);
    1018             :                     }
    1019             :                     else
    1020         178 :                         strcpy(result, &buf[10]);
    1021             :                 }
    1022             :             }
    1023             :             else
    1024             :             {                   /* exp <= 0 */
    1025          10 :                 dp += exp - 1;
    1026          10 :                 buf[10 + n] = '\0';
    1027          10 :                 buf[dp] = '.';
    1028          10 :                 if (sign)
    1029             :                 {
    1030           0 :                     buf[dp - 2] = '-';
    1031           0 :                     strcpy(result, &buf[dp - 2]);
    1032             :                 }
    1033             :                 else
    1034          10 :                     strcpy(result, &buf[dp - 1]);
    1035             :             }
    1036             :         }
    1037             : 
    1038             :         /* do nothing for Abs(exp) > 4; %e must be OK */
    1039             :         /* just get rid of zeroes after [eE]- and +zeroes after [Ee]. */
    1040             : 
    1041             :         /* ... this is not done yet. */
    1042             :     }
    1043         648 :     return strlen(result);
    1044             : }
    1045             : 
    1046             : 
    1047             : /*
    1048             : ** Miscellany
    1049             : */
    1050             : 
    1051             : /* find out the number of significant digits in a string representing
    1052             :  * a floating point number
    1053             :  */
    1054             : int
    1055       10368 : significant_digits(const char *s)
    1056             : {
    1057       10368 :     const char *p = s;
    1058             :     int         n,
    1059             :                 c,
    1060             :                 zeroes;
    1061             : 
    1062       10368 :     zeroes = 1;
    1063             :     /* skip leading zeroes and sign */
    1064       10368 :     for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
    1065             : 
    1066             :     /* skip decimal point and following zeroes */
    1067       10414 :     for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
    1068             :     {
    1069          46 :         if (c != '.')
    1070          22 :             zeroes++;
    1071             :     }
    1072             : 
    1073             :     /* count significant digits (n) */
    1074       40410 :     for (c = *p, n = 0; c != 0; c = *(++p))
    1075             :     {
    1076       30096 :         if (!((c >= '0' && c <= '9') || (c == '.')))
    1077          54 :             break;
    1078       30042 :         if (c != '.')
    1079       20950 :             n++;
    1080             :     }
    1081             : 
    1082       10368 :     if (!n)
    1083         194 :         return zeroes;
    1084             : 
    1085       10174 :     return n;
    1086             : }

Generated by: LCOV version 1.13