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: 2020-02-27 19:06:28 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      100894 : 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      100894 :     na = ARRNELEMS(a);
      25      100894 :     nb = ARRNELEMS(b);
      26      100894 :     da = ARRPTR(a);
      27      100894 :     db = ARRPTR(b);
      28             : 
      29      100894 :     i = j = n = 0;
      30      221406 :     while (i < na && j < nb)
      31             :     {
      32      215752 :         if (da[i] < db[j])
      33      115092 :             i++;
      34      100660 :         else if (da[i] == db[j])
      35             :         {
      36        5420 :             n++;
      37        5420 :             i++;
      38        5420 :             j++;
      39             :         }
      40             :         else
      41       95240 :             break;              /* db[j] is not in da */
      42             :     }
      43             : 
      44      100894 :     return (n == nb) ? true : false;
      45             : }
      46             : 
      47             : /* arguments are assumed sorted */
      48             : bool
      49       25902 : 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       25902 :     na = ARRNELEMS(a);
      59       25902 :     nb = ARRNELEMS(b);
      60       25902 :     da = ARRPTR(a);
      61       25902 :     db = ARRPTR(b);
      62             : 
      63       25902 :     i = j = 0;
      64      115840 :     while (i < na && j < nb)
      65             :     {
      66       92512 :         if (da[i] < db[j])
      67       43770 :             i++;
      68       48742 :         else if (da[i] == db[j])
      69        2574 :             return true;
      70             :         else
      71       46168 :             j++;
      72             :     }
      73             : 
      74       23328 :     return false;
      75             : }
      76             : 
      77             : ArrayType *
      78     1618884 : inner_int_union(ArrayType *a, ArrayType *b)
      79             : {
      80     1618884 :     ArrayType  *r = NULL;
      81             : 
      82     1618884 :     CHECKARRVALID(a);
      83     1618884 :     CHECKARRVALID(b);
      84             : 
      85     1618884 :     if (ARRISEMPTY(a) && ARRISEMPTY(b))
      86         120 :         return new_intArrayType(0);
      87     1618764 :     if (ARRISEMPTY(a))
      88        9402 :         r = copy_intArrayType(b);
      89     1618764 :     if (ARRISEMPTY(b))
      90        3124 :         r = copy_intArrayType(a);
      91             : 
      92     1618764 :     if (!r)
      93             :     {
      94     1606238 :         int         na = ARRNELEMS(a),
      95     1606238 :                     nb = ARRNELEMS(b);
      96     1606238 :         int        *da = ARRPTR(a),
      97     1606238 :                    *db = ARRPTR(b);
      98             :         int         i,
      99             :                     j,
     100             :                    *dr;
     101             : 
     102     1606238 :         r = new_intArrayType(na + nb);
     103     1606238 :         dr = ARRPTR(r);
     104             : 
     105             :         /* union */
     106     1606238 :         i = j = 0;
     107    24490330 :         while (i < na && j < nb)
     108             :         {
     109    22884092 :             if (da[i] == db[j])
     110             :             {
     111     1097822 :                 *dr++ = da[i++];
     112     1097822 :                 j++;
     113             :             }
     114    21786270 :             else if (da[i] < db[j])
     115    17295906 :                 *dr++ = da[i++];
     116             :             else
     117     4490364 :                 *dr++ = db[j++];
     118             :         }
     119             : 
     120     5003668 :         while (i < na)
     121     3397430 :             *dr++ = da[i++];
     122     3047186 :         while (j < nb)
     123     1440948 :             *dr++ = db[j++];
     124             : 
     125     1606238 :         r = resize_intArrayType(r, dr - ARRPTR(r));
     126             :     }
     127             : 
     128     1618764 :     if (ARRNELEMS(r) > 1)
     129     1618764 :         r = _int_unique(r);
     130             : 
     131     1618764 :     return r;
     132             : }
     133             : 
     134             : ArrayType *
     135     1384924 : 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     1384924 :     if (ARRISEMPTY(a) || ARRISEMPTY(b))
     148       12276 :         return new_intArrayType(0);
     149             : 
     150     1372648 :     na = ARRNELEMS(a);
     151     1372648 :     nb = ARRNELEMS(b);
     152     1372648 :     da = ARRPTR(a);
     153     1372648 :     db = ARRPTR(b);
     154     1372648 :     r = new_intArrayType(Min(na, nb));
     155     1372648 :     dr = ARRPTR(r);
     156             : 
     157     1372648 :     i = j = k = 0;
     158    10197348 :     while (i < na && j < nb)
     159             :     {
     160     8824700 :         if (da[i] < db[j])
     161     4339668 :             i++;
     162     4485032 :         else if (da[i] == db[j])
     163             :         {
     164      487446 :             if (k == 0 || dr[k - 1] != db[j])
     165      487446 :                 dr[k++] = db[j];
     166      487446 :             i++;
     167      487446 :             j++;
     168             :         }
     169             :         else
     170     3997586 :             j++;
     171             :     }
     172             : 
     173     1372648 :     if (k == 0)
     174             :     {
     175     1101520 :         pfree(r);
     176     1101520 :         return new_intArrayType(0);
     177             :     }
     178             :     else
     179      271128 :         return resize_intArrayType(r, k);
     180             : }
     181             : 
     182             : void
     183     3154428 : rt__int_size(ArrayType *a, float *size)
     184             : {
     185     3154428 :     *size = (float) ARRNELEMS(a);
     186     3154428 : }
     187             : 
     188             : /* qsort_arg comparison function for isort() */
     189             : static int
     190    29998058 : isort_cmp(const void *a, const void *b, void *arg)
     191             : {
     192    29998058 :     int32       aval = *((const int32 *) a);
     193    29998058 :     int32       bval = *((const int32 *) b);
     194             : 
     195    29998058 :     if (aval < bval)
     196      563604 :         return -1;
     197    29434454 :     if (aval > bval)
     198    29318908 :         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      115546 :     *((bool *) arg) = true;
     206      115546 :     return 0;
     207             : }
     208             : 
     209             : /* Sort the given data (len >= 2).  Return true if any duplicates found */
     210             : bool
     211      336126 : isort(int32 *a, int len)
     212             : {
     213      336126 :     bool        r = false;
     214             : 
     215      336126 :     qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
     216      336126 :     return r;
     217             : }
     218             : 
     219             : /* Create a new int array with room for "num" elements */
     220             : ArrayType *
     221     4134430 : new_intArrayType(int num)
     222             : {
     223             :     ArrayType  *r;
     224             :     int         nbytes;
     225             : 
     226             :     /* if no elements, return a zero-dimensional array */
     227     4134430 :     if (num <= 0)
     228             :     {
     229             :         Assert(num == 0);
     230     1113916 :         r = construct_empty_array(INT4OID);
     231     1113916 :         return r;
     232             :     }
     233             : 
     234     3020514 :     nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
     235             : 
     236     3020514 :     r = (ArrayType *) palloc0(nbytes);
     237             : 
     238     3020514 :     SET_VARSIZE(r, nbytes);
     239     3020514 :     ARR_NDIM(r) = 1;
     240     3020514 :     r->dataoffset = 0;           /* marker for no null bitmap */
     241     3020514 :     ARR_ELEMTYPE(r) = INT4OID;
     242     3020514 :     ARR_DIMS(r)[0] = num;
     243     3020514 :     ARR_LBOUND(r)[0] = 1;
     244             : 
     245     3020514 :     return r;
     246             : }
     247             : 
     248             : ArrayType *
     249     3530166 : resize_intArrayType(ArrayType *a, int num)
     250             : {
     251             :     int         nbytes;
     252             :     int         i;
     253             : 
     254             :     /* if no elements, return a zero-dimensional array */
     255     3530166 :     if (num <= 0)
     256             :     {
     257             :         Assert(num == 0);
     258           0 :         a = construct_empty_array(INT4OID);
     259           0 :         return a;
     260             :     }
     261             : 
     262     3530166 :     if (num == ARRNELEMS(a))
     263     2767858 :         return a;
     264             : 
     265      762308 :     nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
     266             : 
     267      762308 :     a = (ArrayType *) repalloc(a, nbytes);
     268             : 
     269      762308 :     SET_VARSIZE(a, nbytes);
     270             :     /* usually the array should be 1-D already, but just in case ... */
     271     1524616 :     for (i = 0; i < ARR_NDIM(a); i++)
     272             :     {
     273      762308 :         ARR_DIMS(a)[i] = num;
     274      762308 :         num = 1;
     275             :     }
     276      762308 :     return a;
     277             : }
     278             : 
     279             : ArrayType *
     280       12886 : copy_intArrayType(ArrayType *a)
     281             : {
     282             :     ArrayType  *r;
     283       12886 :     int         n = ARRNELEMS(a);
     284             : 
     285       12886 :     r = new_intArrayType(n);
     286       12886 :     memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
     287       12886 :     return r;
     288             : }
     289             : 
     290             : /* num for compressed key */
     291             : int
     292        5924 : internal_size(int *a, int len)
     293             : {
     294             :     int         i;
     295        5924 :     int64       size = 0;
     296             : 
     297      598324 :     for (i = 0; i < len; i += 2)
     298             :     {
     299      592400 :         if (!i || a[i] != a[i - 1]) /* do not count repeated range */
     300      592400 :             size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
     301             :     }
     302             : 
     303        5924 :     if (size > (int64) INT_MAX || size < (int64) INT_MIN)
     304           0 :         return -1;              /* overflow */
     305        5924 :     return (int) size;
     306             : }
     307             : 
     308             : /* unique-ify elements of r in-place ... r must be sorted already */
     309             : ArrayType *
     310     1652312 : _int_unique(ArrayType *r)
     311             : {
     312     1652312 :     int         num = ARRNELEMS(r);
     313             :     bool        duplicates_found;   /* not used */
     314             : 
     315     1652312 :     num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
     316             :                       &duplicates_found);
     317             : 
     318     1652312 :     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    28904668 : compASC(const void *a, const void *b)
     398             : {
     399    28904668 :     if (*(const int32 *) a == *(const int32 *) b)
     400      108440 :         return 0;
     401    28796228 :     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