LCOV - code coverage report
Current view: top level - contrib/intarray - _int_tool.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 179 189 94.7 %
Date: 2019-11-21 13:06:38 Functions: 18 19 94.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * contrib/intarray/_int_tool.c
       3             :  */
       4             : #include "postgres.h"
       5             : 
       6             : #include <limits.h>
       7             : 
       8             : #include "_int.h"
       9             : #include "catalog/pg_type.h"
      10             : #include "lib/qunique.h"
      11             : 
      12             : /* arguments are assumed sorted & unique-ified */
      13             : bool
      14      100784 : inner_int_contains(ArrayType *a, ArrayType *b)
      15             : {
      16             :     int         na,
      17             :                 nb;
      18             :     int         i,
      19             :                 j,
      20             :                 n;
      21             :     int        *da,
      22             :                *db;
      23             : 
      24      100784 :     na = ARRNELEMS(a);
      25      100784 :     nb = ARRNELEMS(b);
      26      100784 :     da = ARRPTR(a);
      27      100784 :     db = ARRPTR(b);
      28             : 
      29      100784 :     i = j = n = 0;
      30      320302 :     while (i < na && j < nb)
      31             :     {
      32      214108 :         if (da[i] < db[j])
      33      113516 :             i++;
      34      100592 :         else if (da[i] == db[j])
      35             :         {
      36        5218 :             n++;
      37        5218 :             i++;
      38        5218 :             j++;
      39             :         }
      40             :         else
      41       95374 :             break;              /* db[j] is not in da */
      42             :     }
      43             : 
      44      100784 :     return (n == nb) ? true : false;
      45             : }
      46             : 
      47             : /* arguments are assumed sorted */
      48             : bool
      49       25404 : inner_int_overlap(ArrayType *a, ArrayType *b)
      50             : {
      51             :     int         na,
      52             :                 nb;
      53             :     int         i,
      54             :                 j;
      55             :     int        *da,
      56             :                *db;
      57             : 
      58       25404 :     na = ARRNELEMS(a);
      59       25404 :     nb = ARRNELEMS(b);
      60       25404 :     da = ARRPTR(a);
      61       25404 :     db = ARRPTR(b);
      62             : 
      63       25404 :     i = j = 0;
      64      138348 :     while (i < na && j < nb)
      65             :     {
      66       90098 :         if (da[i] < db[j])
      67       42388 :             i++;
      68       47710 :         else if (da[i] == db[j])
      69        2558 :             return true;
      70             :         else
      71       45152 :             j++;
      72             :     }
      73             : 
      74       22846 :     return false;
      75             : }
      76             : 
      77             : ArrayType *
      78     1643528 : inner_int_union(ArrayType *a, ArrayType *b)
      79             : {
      80     1643528 :     ArrayType  *r = NULL;
      81             : 
      82     1643528 :     CHECKARRVALID(a);
      83     1643528 :     CHECKARRVALID(b);
      84             : 
      85     1643528 :     if (ARRISEMPTY(a) && ARRISEMPTY(b))
      86         120 :         return new_intArrayType(0);
      87     1643408 :     if (ARRISEMPTY(a))
      88        9384 :         r = copy_intArrayType(b);
      89     1643408 :     if (ARRISEMPTY(b))
      90        3394 :         r = copy_intArrayType(a);
      91             : 
      92     1643408 :     if (!r)
      93             :     {
      94     1630630 :         int         na = ARRNELEMS(a),
      95     1630630 :                     nb = ARRNELEMS(b);
      96     1630630 :         int        *da = ARRPTR(a),
      97     1630630 :                    *db = ARRPTR(b);
      98             :         int         i,
      99             :                     j,
     100             :                    *dr;
     101             : 
     102     1630630 :         r = new_intArrayType(na + nb);
     103     1630630 :         dr = ARRPTR(r);
     104             : 
     105             :         /* union */
     106     1630630 :         i = j = 0;
     107    25359792 :         while (i < na && j < nb)
     108             :         {
     109    22098532 :             if (da[i] == db[j])
     110             :             {
     111      980156 :                 *dr++ = da[i++];
     112      980156 :                 j++;
     113             :             }
     114    21118376 :             else if (da[i] < db[j])
     115    16695776 :                 *dr++ = da[i++];
     116             :             else
     117     4422600 :                 *dr++ = db[j++];
     118             :         }
     119             : 
     120     6547764 :         while (i < na)
     121     3286504 :             *dr++ = da[i++];
     122     4753502 :         while (j < nb)
     123     1492242 :             *dr++ = db[j++];
     124             : 
     125     1630630 :         r = resize_intArrayType(r, dr - ARRPTR(r));
     126             :     }
     127             : 
     128     1643408 :     if (ARRNELEMS(r) > 1)
     129     1643388 :         r = _int_unique(r);
     130             : 
     131     1643408 :     return r;
     132             : }
     133             : 
     134             : ArrayType *
     135     1411270 : inner_int_inter(ArrayType *a, ArrayType *b)
     136             : {
     137             :     ArrayType  *r;
     138             :     int         na,
     139             :                 nb;
     140             :     int        *da,
     141             :                *db,
     142             :                *dr;
     143             :     int         i,
     144             :                 j,
     145             :                 k;
     146             : 
     147     1411270 :     if (ARRISEMPTY(a) || ARRISEMPTY(b))
     148       12522 :         return new_intArrayType(0);
     149             : 
     150     1398748 :     na = ARRNELEMS(a);
     151     1398748 :     nb = ARRNELEMS(b);
     152     1398748 :     da = ARRPTR(a);
     153     1398748 :     db = ARRPTR(b);
     154     1398748 :     r = new_intArrayType(Min(na, nb));
     155     1398748 :     dr = ARRPTR(r);
     156             : 
     157     1398748 :     i = j = k = 0;
     158    11512300 :     while (i < na && j < nb)
     159             :     {
     160     8714804 :         if (da[i] < db[j])
     161     4307930 :             i++;
     162     4406874 :         else if (da[i] == db[j])
     163             :         {
     164      432486 :             if (k == 0 || dr[k - 1] != db[j])
     165      432486 :                 dr[k++] = db[j];
     166      432486 :             i++;
     167      432486 :             j++;
     168             :         }
     169             :         else
     170     3974388 :             j++;
     171             :     }
     172             : 
     173     1398748 :     if (k == 0)
     174             :     {
     175     1124656 :         pfree(r);
     176     1124656 :         return new_intArrayType(0);
     177             :     }
     178             :     else
     179      274092 :         return resize_intArrayType(r, k);
     180             : }
     181             : 
     182             : void
     183     3202968 : rt__int_size(ArrayType *a, float *size)
     184             : {
     185     3202968 :     *size = (float) ARRNELEMS(a);
     186     3202968 : }
     187             : 
     188             : /* qsort_arg comparison function for isort() */
     189             : static int
     190    28952186 : isort_cmp(const void *a, const void *b, void *arg)
     191             : {
     192    28952186 :     int32       aval = *((const int32 *) a);
     193    28952186 :     int32       bval = *((const int32 *) b);
     194             : 
     195    28952186 :     if (aval < bval)
     196      562986 :         return -1;
     197    28389200 :     if (aval > bval)
     198    28280450 :         return 1;
     199             : 
     200             :     /*
     201             :      * Report if we have any duplicates.  If there are equal keys, qsort must
     202             :      * compare them at some point, else it wouldn't know whether one should go
     203             :      * before or after the other.
     204             :      */
     205      108750 :     *((bool *) arg) = true;
     206      108750 :     return 0;
     207             : }
     208             : 
     209             : /* Sort the given data (len >= 2).  Return true if any duplicates found */
     210             : bool
     211      334620 : isort(int32 *a, int len)
     212             : {
     213      334620 :     bool        r = false;
     214             : 
     215      334620 :     qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
     216      334620 :     return r;
     217             : }
     218             : 
     219             : /* Create a new int array with room for "num" elements */
     220             : ArrayType *
     221     4206966 : new_intArrayType(int num)
     222             : {
     223             :     ArrayType  *r;
     224             :     int         nbytes;
     225             : 
     226             :     /* if no elements, return a zero-dimensional array */
     227     4206966 :     if (num <= 0)
     228             :     {
     229             :         Assert(num == 0);
     230     1137298 :         r = construct_empty_array(INT4OID);
     231     1137298 :         return r;
     232             :     }
     233             : 
     234     3069668 :     nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
     235             : 
     236     3069668 :     r = (ArrayType *) palloc0(nbytes);
     237             : 
     238     3069668 :     SET_VARSIZE(r, nbytes);
     239     3069668 :     ARR_NDIM(r) = 1;
     240     3069668 :     r->dataoffset = 0;           /* marker for no null bitmap */
     241     3069668 :     ARR_ELEMTYPE(r) = INT4OID;
     242     3069668 :     ARR_DIMS(r)[0] = num;
     243     3069668 :     ARR_LBOUND(r)[0] = 1;
     244             : 
     245     3069668 :     return r;
     246             : }
     247             : 
     248             : ArrayType *
     249     3581518 : resize_intArrayType(ArrayType *a, int num)
     250             : {
     251             :     int         nbytes;
     252             :     int         i;
     253             : 
     254             :     /* if no elements, return a zero-dimensional array */
     255     3581518 :     if (num <= 0)
     256             :     {
     257             :         Assert(num == 0);
     258           0 :         a = construct_empty_array(INT4OID);
     259           0 :         return a;
     260             :     }
     261             : 
     262     3581518 :     if (num == ARRNELEMS(a))
     263     2818550 :         return a;
     264             : 
     265      762968 :     nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
     266             : 
     267      762968 :     a = (ArrayType *) repalloc(a, nbytes);
     268             : 
     269      762968 :     SET_VARSIZE(a, nbytes);
     270             :     /* usually the array should be 1-D already, but just in case ... */
     271     1525936 :     for (i = 0; i < ARR_NDIM(a); i++)
     272             :     {
     273      762968 :         ARR_DIMS(a)[i] = num;
     274      762968 :         num = 1;
     275             :     }
     276      762968 :     return a;
     277             : }
     278             : 
     279             : ArrayType *
     280       13118 : copy_intArrayType(ArrayType *a)
     281             : {
     282             :     ArrayType  *r;
     283       13118 :     int         n = ARRNELEMS(a);
     284             : 
     285       13118 :     r = new_intArrayType(n);
     286       13118 :     memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
     287       13118 :     return r;
     288             : }
     289             : 
     290             : /* num for compressed key */
     291             : int
     292        5102 : internal_size(int *a, int len)
     293             : {
     294             :     int         i;
     295        5102 :     int64       size = 0;
     296             : 
     297      515302 :     for (i = 0; i < len; i += 2)
     298             :     {
     299      510200 :         if (!i || a[i] != a[i - 1]) /* do not count repeated range */
     300      510200 :             size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
     301             :     }
     302             : 
     303        5102 :     if (size > (int64) INT_MAX || size < (int64) INT_MIN)
     304           0 :         return -1;              /* overflow */
     305        5102 :     return (int) size;
     306             : }
     307             : 
     308             : /* unique-ify elements of r in-place ... r must be sorted already */
     309             : ArrayType *
     310     1676228 : _int_unique(ArrayType *r)
     311             : {
     312     1676228 :     int         num = ARRNELEMS(r);
     313             :     bool        duplicates_found;   /* not used */
     314             : 
     315     1676228 :     num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
     316             :                       &duplicates_found);
     317             : 
     318     1676228 :     return resize_intArrayType(r, num);
     319             : }
     320             : 
     321             : void
     322           0 : gensign(BITVEC sign, int *a, int len)
     323             : {
     324             :     int         i;
     325             : 
     326             :     /* we assume that the sign vector is previously zeroed */
     327           0 :     for (i = 0; i < len; i++)
     328             :     {
     329           0 :         HASH(sign, *a);
     330           0 :         a++;
     331             :     }
     332           0 : }
     333             : 
     334             : int32
     335           2 : intarray_match_first(ArrayType *a, int32 elem)
     336             : {
     337             :     int32      *aa,
     338             :                 c,
     339             :                 i;
     340             : 
     341           2 :     CHECKARRVALID(a);
     342           2 :     c = ARRNELEMS(a);
     343           2 :     aa = ARRPTR(a);
     344           4 :     for (i = 0; i < c; i++)
     345           4 :         if (aa[i] == elem)
     346           2 :             return (i + 1);
     347           0 :     return 0;
     348             : }
     349             : 
     350             : ArrayType *
     351           8 : intarray_add_elem(ArrayType *a, int32 elem)
     352             : {
     353             :     ArrayType  *result;
     354             :     int32      *r;
     355             :     int32       c;
     356             : 
     357           8 :     CHECKARRVALID(a);
     358           8 :     c = ARRNELEMS(a);
     359           8 :     result = new_intArrayType(c + 1);
     360           8 :     r = ARRPTR(result);
     361           8 :     if (c > 0)
     362           8 :         memcpy(r, ARRPTR(a), c * sizeof(int32));
     363           8 :     r[c] = elem;
     364           8 :     return result;
     365             : }
     366             : 
     367             : ArrayType *
     368           2 : intarray_concat_arrays(ArrayType *a, ArrayType *b)
     369             : {
     370             :     ArrayType  *result;
     371           2 :     int32       ac = ARRNELEMS(a);
     372           2 :     int32       bc = ARRNELEMS(b);
     373             : 
     374           2 :     CHECKARRVALID(a);
     375           2 :     CHECKARRVALID(b);
     376           2 :     result = new_intArrayType(ac + bc);
     377           2 :     if (ac)
     378           2 :         memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
     379           2 :     if (bc)
     380           2 :         memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
     381           2 :     return result;
     382             : }
     383             : 
     384             : ArrayType *
     385           2 : int_to_intset(int32 n)
     386             : {
     387             :     ArrayType  *result;
     388             :     int32      *aa;
     389             : 
     390           2 :     result = new_intArrayType(1);
     391           2 :     aa = ARRPTR(result);
     392           2 :     aa[0] = n;
     393           2 :     return result;
     394             : }
     395             : 
     396             : int
     397    26411438 : compASC(const void *a, const void *b)
     398             : {
     399    26411438 :     if (*(const int32 *) a == *(const int32 *) b)
     400      101146 :         return 0;
     401    26310292 :     return (*(const int32 *) a > *(const int32 *) b) ? 1 : -1;
     402             : }
     403             : 
     404             : int
     405          12 : compDESC(const void *a, const void *b)
     406             : {
     407          12 :     if (*(const int32 *) a == *(const int32 *) b)
     408           0 :         return 0;
     409          12 :     return (*(const int32 *) a < *(const int32 *) b) ? 1 : -1;
     410             : }

Generated by: LCOV version 1.13