LCOV - code coverage report
Current view: top level - contrib/intarray - _int_tool.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 179 189 94.7 %
Date: 2021-12-05 01:09:12 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      165308 : 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      165308 :     na = ARRNELEMS(a);
      25      165308 :     nb = ARRNELEMS(b);
      26      165308 :     da = ARRPTR(a);
      27      165308 :     db = ARRPTR(b);
      28             : 
      29      165308 :     i = j = n = 0;
      30      374864 :     while (i < na && j < nb)
      31             :     {
      32      363730 :         if (da[i] < db[j])
      33      200360 :             i++;
      34      163370 :         else if (da[i] == db[j])
      35             :         {
      36        9196 :             n++;
      37        9196 :             i++;
      38        9196 :             j++;
      39             :         }
      40             :         else
      41      154174 :             break;              /* db[j] is not in da */
      42             :     }
      43             : 
      44      165308 :     return (n == nb);
      45             : }
      46             : 
      47             : /* arguments are assumed sorted */
      48             : bool
      49       37952 : 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       37952 :     na = ARRNELEMS(a);
      59       37952 :     nb = ARRNELEMS(b);
      60       37952 :     da = ARRPTR(a);
      61       37952 :     db = ARRPTR(b);
      62             : 
      63       37952 :     i = j = 0;
      64      170348 :     while (i < na && j < nb)
      65             :     {
      66      136744 :         if (da[i] < db[j])
      67       65696 :             i++;
      68       71048 :         else if (da[i] == db[j])
      69        4348 :             return true;
      70             :         else
      71       66700 :             j++;
      72             :     }
      73             : 
      74       33604 :     return false;
      75             : }
      76             : 
      77             : ArrayType *
      78     3254916 : inner_int_union(ArrayType *a, ArrayType *b)
      79             : {
      80     3254916 :     ArrayType  *r = NULL;
      81             : 
      82     3254916 :     CHECKARRVALID(a);
      83     3254916 :     CHECKARRVALID(b);
      84             : 
      85     3254916 :     if (ARRISEMPTY(a) && ARRISEMPTY(b))
      86         246 :         return new_intArrayType(0);
      87     3254670 :     if (ARRISEMPTY(a))
      88       19174 :         r = copy_intArrayType(b);
      89     3254670 :     if (ARRISEMPTY(b))
      90        6588 :         r = copy_intArrayType(a);
      91             : 
      92     3254670 :     if (!r)
      93             :     {
      94     3228908 :         int         na = ARRNELEMS(a),
      95     3228908 :                     nb = ARRNELEMS(b);
      96     3228908 :         int        *da = ARRPTR(a),
      97     3228908 :                    *db = ARRPTR(b);
      98             :         int         i,
      99             :                     j,
     100             :                    *dr;
     101             : 
     102     3228908 :         r = new_intArrayType(na + nb);
     103     3228908 :         dr = ARRPTR(r);
     104             : 
     105             :         /* union */
     106     3228908 :         i = j = 0;
     107    50718138 :         while (i < na && j < nb)
     108             :         {
     109    47489230 :             if (da[i] == db[j])
     110             :             {
     111     2397562 :                 *dr++ = da[i++];
     112     2397562 :                 j++;
     113             :             }
     114    45091668 :             else if (da[i] < db[j])
     115    35909804 :                 *dr++ = da[i++];
     116             :             else
     117     9181864 :                 *dr++ = db[j++];
     118             :         }
     119             : 
     120     9988832 :         while (i < na)
     121     6759924 :             *dr++ = da[i++];
     122     6183926 :         while (j < nb)
     123     2955018 :             *dr++ = db[j++];
     124             : 
     125     3228908 :         r = resize_intArrayType(r, dr - ARRPTR(r));
     126             :     }
     127             : 
     128     3254670 :     if (ARRNELEMS(r) > 1)
     129     3254650 :         r = _int_unique(r);
     130             : 
     131     3254670 :     return r;
     132             : }
     133             : 
     134             : ArrayType *
     135     2764462 : 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     2764462 :     if (ARRISEMPTY(a) || ARRISEMPTY(b))
     148       25244 :         return new_intArrayType(0);
     149             : 
     150     2739218 :     na = ARRNELEMS(a);
     151     2739218 :     nb = ARRNELEMS(b);
     152     2739218 :     da = ARRPTR(a);
     153     2739218 :     db = ARRPTR(b);
     154     2739218 :     r = new_intArrayType(Min(na, nb));
     155     2739218 :     dr = ARRPTR(r);
     156             : 
     157     2739218 :     i = j = k = 0;
     158    20627838 :     while (i < na && j < nb)
     159             :     {
     160    17888620 :         if (da[i] < db[j])
     161     8694970 :             i++;
     162     9193650 :         else if (da[i] == db[j])
     163             :         {
     164     1085002 :             if (k == 0 || dr[k - 1] != db[j])
     165     1085002 :                 dr[k++] = db[j];
     166     1085002 :             i++;
     167     1085002 :             j++;
     168             :         }
     169             :         else
     170     8108648 :             j++;
     171             :     }
     172             : 
     173     2739218 :     if (k == 0)
     174             :     {
     175     2202908 :         pfree(r);
     176     2202908 :         return new_intArrayType(0);
     177             :     }
     178             :     else
     179      536310 :         return resize_intArrayType(r, k);
     180             : }
     181             : 
     182             : void
     183     6342484 : rt__int_size(ArrayType *a, float *size)
     184             : {
     185     6342484 :     *size = (float) ARRNELEMS(a);
     186     6342484 : }
     187             : 
     188             : /* qsort_arg comparison function for isort() */
     189             : static int
     190    61407062 : isort_cmp(const void *a, const void *b, void *arg)
     191             : {
     192    61407062 :     int32       aval = *((const int32 *) a);
     193    61407062 :     int32       bval = *((const int32 *) b);
     194             : 
     195    61407062 :     if (aval < bval)
     196      817510 :         return -1;
     197    60589552 :     if (aval > bval)
     198    60368002 :         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      221550 :     *((bool *) arg) = true;
     206      221550 :     return 0;
     207             : }
     208             : 
     209             : /* Sort the given data (len >= 2).  Return true if any duplicates found */
     210             : bool
     211      510774 : isort(int32 *a, int len)
     212             : {
     213      510774 :     bool        r = false;
     214             : 
     215      510774 :     qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
     216      510774 :     return r;
     217             : }
     218             : 
     219             : /* Create a new int array with room for "num" elements */
     220             : ArrayType *
     221     8275748 : new_intArrayType(int num)
     222             : {
     223             :     ArrayType  *r;
     224             :     int         nbytes;
     225             : 
     226             :     /* if no elements, return a zero-dimensional array */
     227     8275748 :     if (num <= 0)
     228             :     {
     229             :         Assert(num == 0);
     230     2228398 :         r = construct_empty_array(INT4OID);
     231     2228398 :         return r;
     232             :     }
     233             : 
     234     6047350 :     nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
     235             : 
     236     6047350 :     r = (ArrayType *) palloc0(nbytes);
     237             : 
     238     6047350 :     SET_VARSIZE(r, nbytes);
     239     6047350 :     ARR_NDIM(r) = 1;
     240     6047350 :     r->dataoffset = 0;           /* marker for no null bitmap */
     241     6047350 :     ARR_ELEMTYPE(r) = INT4OID;
     242     6047350 :     ARR_DIMS(r)[0] = num;
     243     6047350 :     ARR_LBOUND(r)[0] = 1;
     244             : 
     245     6047350 :     return r;
     246             : }
     247             : 
     248             : ArrayType *
     249     7082766 : resize_intArrayType(ArrayType *a, int num)
     250             : {
     251             :     int         nbytes;
     252             :     int         i;
     253             : 
     254             :     /* if no elements, return a zero-dimensional array */
     255     7082766 :     if (num <= 0)
     256             :     {
     257             :         Assert(num == 0);
     258           0 :         a = construct_empty_array(INT4OID);
     259           0 :         return a;
     260             :     }
     261             : 
     262     7082766 :     if (num == ARRNELEMS(a))
     263     5562110 :         return a;
     264             : 
     265     1520656 :     nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
     266             : 
     267     1520656 :     a = (ArrayType *) repalloc(a, nbytes);
     268             : 
     269     1520656 :     SET_VARSIZE(a, nbytes);
     270             :     /* usually the array should be 1-D already, but just in case ... */
     271     3041312 :     for (i = 0; i < ARR_NDIM(a); i++)
     272             :     {
     273     1520656 :         ARR_DIMS(a)[i] = num;
     274     1520656 :         num = 1;
     275             :     }
     276     1520656 :     return a;
     277             : }
     278             : 
     279             : ArrayType *
     280       26522 : copy_intArrayType(ArrayType *a)
     281             : {
     282             :     ArrayType  *r;
     283       26522 :     int         n = ARRNELEMS(a);
     284             : 
     285       26522 :     r = new_intArrayType(n);
     286       26522 :     memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
     287       26522 :     return r;
     288             : }
     289             : 
     290             : /* num for compressed key */
     291             : int
     292        6324 : internal_size(int *a, int len)
     293             : {
     294             :     int         i;
     295        6324 :     int64       size = 0;
     296             : 
     297      638724 :     for (i = 0; i < len; i += 2)
     298             :     {
     299      632400 :         if (!i || a[i] != a[i - 1]) /* do not count repeated range */
     300      632400 :             size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
     301             :     }
     302             : 
     303        6324 :     if (size > (int64) INT_MAX || size < (int64) INT_MIN)
     304           0 :         return -1;              /* overflow */
     305        6324 :     return (int) size;
     306             : }
     307             : 
     308             : /* unique-ify elements of r in-place ... r must be sorted already */
     309             : ArrayType *
     310     3317024 : _int_unique(ArrayType *r)
     311             : {
     312     3317024 :     int         num = ARRNELEMS(r);
     313             :     bool        duplicates_found;   /* not used */
     314             : 
     315     3317024 :     num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
     316             :                       &duplicates_found);
     317             : 
     318     3317024 :     return resize_intArrayType(r, num);
     319             : }
     320             : 
     321             : void
     322           0 : gensign(BITVECP sign, int *a, int len, int siglen)
     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, siglen);
     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    61665208 : compASC(const void *a, const void *b)
     398             : {
     399    61665208 :     if (*(const int32 *) a == *(const int32 *) b)
     400      219974 :         return 0;
     401    61445234 :     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.14