LCOV - code coverage report
Current view: top level - contrib/intarray - _int_tool.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 176 185 95.1 %
Date: 2024-03-29 06:11:42 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 "common/int.h"
      11             : #include "lib/qunique.h"
      12             : 
      13             : /* arguments are assumed sorted & unique-ified */
      14             : bool
      15      188132 : inner_int_contains(ArrayType *a, ArrayType *b)
      16             : {
      17             :     int         na,
      18             :                 nb;
      19             :     int         i,
      20             :                 j,
      21             :                 n;
      22             :     int        *da,
      23             :                *db;
      24             : 
      25      188132 :     na = ARRNELEMS(a);
      26      188132 :     nb = ARRNELEMS(b);
      27      188132 :     da = ARRPTR(a);
      28      188132 :     db = ARRPTR(b);
      29             : 
      30      188132 :     i = j = n = 0;
      31      461092 :     while (i < na && j < nb)
      32             :     {
      33      447694 :         if (da[i] < db[j])
      34      259992 :             i++;
      35      187702 :         else if (da[i] == db[j])
      36             :         {
      37       12968 :             n++;
      38       12968 :             i++;
      39       12968 :             j++;
      40             :         }
      41             :         else
      42      174734 :             break;              /* db[j] is not in da */
      43             :     }
      44             : 
      45      188132 :     return (n == nb);
      46             : }
      47             : 
      48             : /* arguments are assumed sorted */
      49             : bool
      50       48384 : inner_int_overlap(ArrayType *a, ArrayType *b)
      51             : {
      52             :     int         na,
      53             :                 nb;
      54             :     int         i,
      55             :                 j;
      56             :     int        *da,
      57             :                *db;
      58             : 
      59       48384 :     na = ARRNELEMS(a);
      60       48384 :     nb = ARRNELEMS(b);
      61       48384 :     da = ARRPTR(a);
      62       48384 :     db = ARRPTR(b);
      63             : 
      64       48384 :     i = j = 0;
      65      226614 :     while (i < na && j < nb)
      66             :     {
      67      184042 :         if (da[i] < db[j])
      68       92898 :             i++;
      69       91144 :         else if (da[i] == db[j])
      70        5812 :             return true;
      71             :         else
      72       85332 :             j++;
      73             :     }
      74             : 
      75       42572 :     return false;
      76             : }
      77             : 
      78             : ArrayType *
      79     4544752 : inner_int_union(ArrayType *a, ArrayType *b)
      80             : {
      81     4544752 :     ArrayType  *r = NULL;
      82             : 
      83     4544752 :     CHECKARRVALID(a);
      84     4544752 :     CHECKARRVALID(b);
      85             : 
      86     4544752 :     if (ARRISEMPTY(a) && ARRISEMPTY(b))
      87         376 :         return new_intArrayType(0);
      88     4544376 :     if (ARRISEMPTY(a))
      89       25842 :         r = copy_intArrayType(b);
      90     4544376 :     if (ARRISEMPTY(b))
      91        8150 :         r = copy_intArrayType(a);
      92             : 
      93     4544376 :     if (!r)
      94             :     {
      95     4510384 :         int         na = ARRNELEMS(a),
      96     4510384 :                     nb = ARRNELEMS(b);
      97     4510384 :         int        *da = ARRPTR(a),
      98     4510384 :                    *db = ARRPTR(b);
      99             :         int         i,
     100             :                     j,
     101             :                    *dr;
     102             : 
     103     4510384 :         r = new_intArrayType(na + nb);
     104     4510384 :         dr = ARRPTR(r);
     105             : 
     106             :         /* union */
     107     4510384 :         i = j = 0;
     108   163745028 :         while (i < na && j < nb)
     109             :         {
     110   159234644 :             if (da[i] == db[j])
     111             :             {
     112    10085820 :                 *dr++ = da[i++];
     113    10085820 :                 j++;
     114             :             }
     115   149148824 :             else if (da[i] < db[j])
     116   125975720 :                 *dr++ = da[i++];
     117             :             else
     118    23173104 :                 *dr++ = db[j++];
     119             :         }
     120             : 
     121    15489512 :         while (i < na)
     122    10979128 :             *dr++ = da[i++];
     123     8691436 :         while (j < nb)
     124     4181052 :             *dr++ = db[j++];
     125             : 
     126     4510384 :         r = resize_intArrayType(r, dr - ARRPTR(r));
     127             :     }
     128             : 
     129     4544376 :     if (ARRNELEMS(r) > 1)
     130     4544354 :         r = _int_unique(r);
     131             : 
     132     4544376 :     return r;
     133             : }
     134             : 
     135             : ArrayType *
     136     3660586 : inner_int_inter(ArrayType *a, ArrayType *b)
     137             : {
     138             :     ArrayType  *r;
     139             :     int         na,
     140             :                 nb;
     141             :     int        *da,
     142             :                *db,
     143             :                *dr;
     144             :     int         i,
     145             :                 j,
     146             :                 k;
     147             : 
     148     3660586 :     if (ARRISEMPTY(a) || ARRISEMPTY(b))
     149       33240 :         return new_intArrayType(0);
     150             : 
     151     3627346 :     na = ARRNELEMS(a);
     152     3627346 :     nb = ARRNELEMS(b);
     153     3627346 :     da = ARRPTR(a);
     154     3627346 :     db = ARRPTR(b);
     155     3627346 :     r = new_intArrayType(Min(na, nb));
     156     3627346 :     dr = ARRPTR(r);
     157             : 
     158     3627346 :     i = j = k = 0;
     159    43896484 :     while (i < na && j < nb)
     160             :     {
     161    40269138 :         if (da[i] < db[j])
     162    18656416 :             i++;
     163    21612722 :         else if (da[i] == db[j])
     164             :         {
     165     3477518 :             if (k == 0 || dr[k - 1] != db[j])
     166     3477518 :                 dr[k++] = db[j];
     167     3477518 :             i++;
     168     3477518 :             j++;
     169             :         }
     170             :         else
     171    18135204 :             j++;
     172             :     }
     173             : 
     174     3627346 :     if (k == 0)
     175             :     {
     176     2877562 :         pfree(r);
     177     2877562 :         return new_intArrayType(0);
     178             :     }
     179             :     else
     180      749784 :         return resize_intArrayType(r, k);
     181             : }
     182             : 
     183             : void
     184     8825620 : rt__int_size(ArrayType *a, float *size)
     185             : {
     186     8825620 :     *size = (float) ARRNELEMS(a);
     187     8825620 : }
     188             : 
     189             : /* qsort_arg comparison function for isort() */
     190             : static int
     191   206825058 : isort_cmp(const void *a, const void *b, void *arg)
     192             : {
     193   206825058 :     int32       aval = *((const int32 *) a);
     194   206825058 :     int32       bval = *((const int32 *) b);
     195             : 
     196   206825058 :     if (aval < bval)
     197     1245028 :         return -1;
     198   205580030 :     if (aval > bval)
     199   204533852 :         return 1;
     200             : 
     201             :     /*
     202             :      * Report if we have any duplicates.  If there are equal keys, qsort must
     203             :      * compare them at some point, else it wouldn't know whether one should go
     204             :      * before or after the other.
     205             :      */
     206     1046178 :     *((bool *) arg) = true;
     207     1046178 :     return 0;
     208             : }
     209             : 
     210             : /* Sort the given data (len >= 2).  Return true if any duplicates found */
     211             : bool
     212      573014 : isort(int32 *a, int len)
     213             : {
     214      573014 :     bool        r = false;
     215             : 
     216      573014 :     qsort_arg(a, len, sizeof(int32), isort_cmp, &r);
     217      573014 :     return r;
     218             : }
     219             : 
     220             : /* Create a new int array with room for "num" elements */
     221             : ArrayType *
     222    11251876 : new_intArrayType(int num)
     223             : {
     224             :     ArrayType  *r;
     225             :     int         nbytes;
     226             : 
     227             :     /* if no elements, return a zero-dimensional array */
     228    11251876 :     if (num <= 0)
     229             :     {
     230             :         Assert(num == 0);
     231     2911178 :         r = construct_empty_array(INT4OID);
     232     2911178 :         return r;
     233             :     }
     234             : 
     235     8340698 :     nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
     236             : 
     237     8340698 :     r = (ArrayType *) palloc0(nbytes);
     238             : 
     239     8340698 :     SET_VARSIZE(r, nbytes);
     240     8340698 :     ARR_NDIM(r) = 1;
     241     8340698 :     r->dataoffset = 0;           /* marker for no null bitmap */
     242     8340698 :     ARR_ELEMTYPE(r) = INT4OID;
     243     8340698 :     ARR_DIMS(r)[0] = num;
     244     8340698 :     ARR_LBOUND(r)[0] = 1;
     245             : 
     246     8340698 :     return r;
     247             : }
     248             : 
     249             : ArrayType *
     250     9942288 : resize_intArrayType(ArrayType *a, int num)
     251             : {
     252             :     int         nbytes;
     253             :     int         i;
     254             : 
     255             :     /* if no elements, return a zero-dimensional array */
     256     9942288 :     if (num <= 0)
     257             :     {
     258             :         Assert(num == 0);
     259           0 :         a = construct_empty_array(INT4OID);
     260           0 :         return a;
     261             :     }
     262             : 
     263     9942288 :     if (num == ARRNELEMS(a))
     264     7602806 :         return a;
     265             : 
     266     2339482 :     nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
     267             : 
     268     2339482 :     a = (ArrayType *) repalloc(a, nbytes);
     269             : 
     270     2339482 :     SET_VARSIZE(a, nbytes);
     271             :     /* usually the array should be 1-D already, but just in case ... */
     272     4678964 :     for (i = 0; i < ARR_NDIM(a); i++)
     273             :     {
     274     2339482 :         ARR_DIMS(a)[i] = num;
     275     2339482 :         num = 1;
     276             :     }
     277     2339482 :     return a;
     278             : }
     279             : 
     280             : ArrayType *
     281       36392 : copy_intArrayType(ArrayType *a)
     282             : {
     283             :     ArrayType  *r;
     284       36392 :     int         n = ARRNELEMS(a);
     285             : 
     286       36392 :     r = new_intArrayType(n);
     287       36392 :     memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
     288       36392 :     return r;
     289             : }
     290             : 
     291             : /* num for compressed key */
     292             : int
     293       54350 : internal_size(int *a, int len)
     294             : {
     295             :     int         i;
     296       54350 :     int64       size = 0;
     297             : 
     298    13018822 :     for (i = 0; i < len; i += 2)
     299             :     {
     300    12964472 :         if (!i || a[i] != a[i - 1]) /* do not count repeated range */
     301    12964472 :             size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
     302             :     }
     303             : 
     304       54350 :     if (size > (int64) INT_MAX || size < (int64) INT_MIN)
     305           0 :         return -1;              /* overflow */
     306       54350 :     return (int) size;
     307             : }
     308             : 
     309             : /* unique-ify elements of r in-place ... r must be sorted already */
     310             : ArrayType *
     311     4676572 : _int_unique(ArrayType *r)
     312             : {
     313     4676572 :     int         num = ARRNELEMS(r);
     314             :     bool        duplicates_found;   /* not used */
     315             : 
     316     4676572 :     num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
     317             :                       &duplicates_found);
     318             : 
     319     4676572 :     return resize_intArrayType(r, num);
     320             : }
     321             : 
     322             : void
     323           0 : gensign(BITVECP sign, int *a, int len, int siglen)
     324             : {
     325             :     int         i;
     326             : 
     327             :     /* we assume that the sign vector is previously zeroed */
     328           0 :     for (i = 0; i < len; i++)
     329             :     {
     330           0 :         HASH(sign, *a, siglen);
     331           0 :         a++;
     332             :     }
     333           0 : }
     334             : 
     335             : int32
     336           2 : intarray_match_first(ArrayType *a, int32 elem)
     337             : {
     338             :     int32      *aa,
     339             :                 c,
     340             :                 i;
     341             : 
     342           2 :     CHECKARRVALID(a);
     343           2 :     c = ARRNELEMS(a);
     344           2 :     aa = ARRPTR(a);
     345           4 :     for (i = 0; i < c; i++)
     346           4 :         if (aa[i] == elem)
     347           2 :             return (i + 1);
     348           0 :     return 0;
     349             : }
     350             : 
     351             : ArrayType *
     352           8 : intarray_add_elem(ArrayType *a, int32 elem)
     353             : {
     354             :     ArrayType  *result;
     355             :     int32      *r;
     356             :     int32       c;
     357             : 
     358           8 :     CHECKARRVALID(a);
     359           8 :     c = ARRNELEMS(a);
     360           8 :     result = new_intArrayType(c + 1);
     361           8 :     r = ARRPTR(result);
     362           8 :     if (c > 0)
     363           8 :         memcpy(r, ARRPTR(a), c * sizeof(int32));
     364           8 :     r[c] = elem;
     365           8 :     return result;
     366             : }
     367             : 
     368             : ArrayType *
     369           2 : intarray_concat_arrays(ArrayType *a, ArrayType *b)
     370             : {
     371             :     ArrayType  *result;
     372           2 :     int32       ac = ARRNELEMS(a);
     373           2 :     int32       bc = ARRNELEMS(b);
     374             : 
     375           2 :     CHECKARRVALID(a);
     376           2 :     CHECKARRVALID(b);
     377           2 :     result = new_intArrayType(ac + bc);
     378           2 :     if (ac)
     379           2 :         memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
     380           2 :     if (bc)
     381           2 :         memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
     382           2 :     return result;
     383             : }
     384             : 
     385             : ArrayType *
     386           2 : int_to_intset(int32 elem)
     387             : {
     388             :     ArrayType  *result;
     389             :     int32      *aa;
     390             : 
     391           2 :     result = new_intArrayType(1);
     392           2 :     aa = ARRPTR(result);
     393           2 :     aa[0] = elem;
     394           2 :     return result;
     395             : }
     396             : 
     397             : int
     398   460514004 : compASC(const void *a, const void *b)
     399             : {
     400   460514004 :     return pg_cmp_s32(*(const int32 *) a, *(const int32 *) b);
     401             : }
     402             : 
     403             : int
     404          12 : compDESC(const void *a, const void *b)
     405             : {
     406          12 :     return pg_cmp_s32(*(const int32 *) b, *(const int32 *) a);
     407             : }

Generated by: LCOV version 1.14