LCOV - code coverage report
Current view: top level - contrib/intarray - _int_tool.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18beta1 Lines: 175 182 96.2 %
Date: 2025-06-07 16:18:04 Functions: 15 16 93.8 %
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      186658 : 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      186658 :     na = ARRNELEMS(a);
      26      186658 :     nb = ARRNELEMS(b);
      27      186658 :     da = ARRPTR(a);
      28      186658 :     db = ARRPTR(b);
      29             : 
      30      186658 :     i = j = n = 0;
      31      457198 :     while (i < na && j < nb)
      32             :     {
      33      443830 :         if (da[i] < db[j])
      34      257812 :             i++;
      35      186018 :         else if (da[i] == db[j])
      36             :         {
      37       12728 :             n++;
      38       12728 :             i++;
      39       12728 :             j++;
      40             :         }
      41             :         else
      42      173290 :             break;              /* db[j] is not in da */
      43             :     }
      44             : 
      45      186658 :     return (n == nb);
      46             : }
      47             : 
      48             : /* arguments are assumed sorted */
      49             : bool
      50       47640 : 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       47640 :     na = ARRNELEMS(a);
      60       47640 :     nb = ARRNELEMS(b);
      61       47640 :     da = ARRPTR(a);
      62       47640 :     db = ARRPTR(b);
      63             : 
      64       47640 :     i = j = 0;
      65      222944 :     while (i < na && j < nb)
      66             :     {
      67      181142 :         if (da[i] < db[j])
      68       91614 :             i++;
      69       89528 :         else if (da[i] == db[j])
      70        5838 :             return true;
      71             :         else
      72       83690 :             j++;
      73             :     }
      74             : 
      75       41802 :     return false;
      76             : }
      77             : 
      78             : ArrayType *
      79     4508938 : inner_int_union(ArrayType *a, ArrayType *b)
      80             : {
      81     4508938 :     ArrayType  *r = NULL;
      82             : 
      83     4508938 :     CHECKARRVALID(a);
      84     4508938 :     CHECKARRVALID(b);
      85             : 
      86     4508938 :     if (ARRISEMPTY(a) && ARRISEMPTY(b))
      87         278 :         return new_intArrayType(0);
      88     4508660 :     if (ARRISEMPTY(a))
      89       26280 :         r = copy_intArrayType(b);
      90     4508660 :     if (ARRISEMPTY(b))
      91        8690 :         r = copy_intArrayType(a);
      92             : 
      93     4508660 :     if (!r)
      94             :     {
      95     4473690 :         int         na = ARRNELEMS(a),
      96     4473690 :                     nb = ARRNELEMS(b);
      97     4473690 :         int        *da = ARRPTR(a),
      98     4473690 :                    *db = ARRPTR(b);
      99             :         int         i,
     100             :                     j,
     101             :                    *dr;
     102             : 
     103     4473690 :         r = new_intArrayType(na + nb);
     104     4473690 :         dr = ARRPTR(r);
     105             : 
     106             :         /* union */
     107     4473690 :         i = j = 0;
     108   164160550 :         while (i < na && j < nb)
     109             :         {
     110   159686860 :             if (da[i] == db[j])
     111             :             {
     112    10099748 :                 *dr++ = da[i++];
     113    10099748 :                 j++;
     114             :             }
     115   149587112 :             else if (da[i] < db[j])
     116   125725186 :                 *dr++ = da[i++];
     117             :             else
     118    23861926 :                 *dr++ = db[j++];
     119             :         }
     120             : 
     121    15577612 :         while (i < na)
     122    11103922 :             *dr++ = da[i++];
     123     8513760 :         while (j < nb)
     124     4040070 :             *dr++ = db[j++];
     125             : 
     126     4473690 :         r = resize_intArrayType(r, dr - ARRPTR(r));
     127             :     }
     128             : 
     129     4508660 :     if (ARRNELEMS(r) > 1)
     130     4508628 :         r = _int_unique(r);
     131             : 
     132     4508660 :     return r;
     133             : }
     134             : 
     135             : ArrayType *
     136     3633922 : 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     3633922 :     if (ARRISEMPTY(a) || ARRISEMPTY(b))
     149       34054 :         return new_intArrayType(0);
     150             : 
     151     3599868 :     na = ARRNELEMS(a);
     152     3599868 :     nb = ARRNELEMS(b);
     153     3599868 :     da = ARRPTR(a);
     154     3599868 :     db = ARRPTR(b);
     155     3599868 :     r = new_intArrayType(Min(na, nb));
     156     3599868 :     dr = ARRPTR(r);
     157             : 
     158     3599868 :     i = j = k = 0;
     159    44600346 :     while (i < na && j < nb)
     160             :     {
     161    41000478 :         if (da[i] < db[j])
     162    18928550 :             i++;
     163    22071928 :         else if (da[i] == db[j])
     164             :         {
     165     3453784 :             if (k == 0 || dr[k - 1] != db[j])
     166     3453784 :                 dr[k++] = db[j];
     167     3453784 :             i++;
     168     3453784 :             j++;
     169             :         }
     170             :         else
     171    18618144 :             j++;
     172             :     }
     173             : 
     174     3599868 :     if (k == 0)
     175             :     {
     176     2858342 :         pfree(r);
     177     2858342 :         return new_intArrayType(0);
     178             :     }
     179             :     else
     180      741526 :         return resize_intArrayType(r, k);
     181             : }
     182             : 
     183             : void
     184     8753524 : rt__int_size(ArrayType *a, float *size)
     185             : {
     186     8753524 :     *size = (float) ARRNELEMS(a);
     187     8753524 : }
     188             : 
     189             : /* comparison function for isort() and _int_unique() */
     190             : static inline int
     191   670632972 : isort_cmp(const void *a, const void *b, void *arg)
     192             : {
     193   670632972 :     int32       aval = *((const int32 *) a);
     194   670632972 :     int32       bval = *((const int32 *) b);
     195             : 
     196   670632972 :     if (*((bool *) arg))
     197             :     {
     198             :         /* compare for ascending order */
     199   670632960 :         if (aval < bval)
     200   288957840 :             return -1;
     201   381675120 :         if (aval > bval)
     202   379501038 :             return 1;
     203             :     }
     204             :     else
     205             :     {
     206          12 :         if (aval > bval)
     207           8 :             return -1;
     208           4 :         if (aval < bval)
     209           4 :             return 1;
     210             :     }
     211     2174082 :     return 0;
     212             : }
     213             : 
     214             : #define ST_SORT isort
     215             : #define ST_ELEMENT_TYPE int32
     216             : #define ST_COMPARE(a, b, ascending) isort_cmp(a, b, ascending)
     217             : #define ST_COMPARE_ARG_TYPE void
     218             : #define ST_SCOPE
     219             : #define ST_DEFINE
     220             : #include "lib/sort_template.h"
     221             : 
     222             : /* Create a new int array with room for "num" elements */
     223             : ArrayType *
     224    11168292 : new_intArrayType(int num)
     225             : {
     226             :     ArrayType  *r;
     227             :     int         nbytes;
     228             : 
     229             :     /* if no elements, return a zero-dimensional array */
     230    11168292 :     if (num <= 0)
     231             :     {
     232             :         Assert(num == 0);
     233     2892674 :         r = construct_empty_array(INT4OID);
     234     2892674 :         return r;
     235             :     }
     236             : 
     237     8275618 :     nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
     238             : 
     239     8275618 :     r = (ArrayType *) palloc0(nbytes);
     240             : 
     241     8275618 :     SET_VARSIZE(r, nbytes);
     242     8275618 :     ARR_NDIM(r) = 1;
     243     8275618 :     r->dataoffset = 0;           /* marker for no null bitmap */
     244     8275618 :     ARR_ELEMTYPE(r) = INT4OID;
     245     8275618 :     ARR_DIMS(r)[0] = num;
     246     8275618 :     ARR_LBOUND(r)[0] = 1;
     247             : 
     248     8275618 :     return r;
     249             : }
     250             : 
     251             : ArrayType *
     252    10408076 : resize_intArrayType(ArrayType *a, int num)
     253             : {
     254             :     int         nbytes;
     255             :     int         i;
     256             : 
     257             :     /* if no elements, return a zero-dimensional array */
     258    10408076 :     if (num <= 0)
     259             :     {
     260             :         Assert(num == 0);
     261         468 :         a = construct_empty_array(INT4OID);
     262         468 :         return a;
     263             :     }
     264             : 
     265    10407608 :     if (num == ARRNELEMS(a))
     266     8091168 :         return a;
     267             : 
     268     2316440 :     nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
     269             : 
     270     2316440 :     a = (ArrayType *) repalloc(a, nbytes);
     271             : 
     272     2316440 :     SET_VARSIZE(a, nbytes);
     273             :     /* usually the array should be 1-D already, but just in case ... */
     274     4632880 :     for (i = 0; i < ARR_NDIM(a); i++)
     275             :     {
     276     2316440 :         ARR_DIMS(a)[i] = num;
     277     2316440 :         num = 1;
     278             :     }
     279     2316440 :     return a;
     280             : }
     281             : 
     282             : ArrayType *
     283       37454 : copy_intArrayType(ArrayType *a)
     284             : {
     285             :     ArrayType  *r;
     286       37454 :     int         n = ARRNELEMS(a);
     287             : 
     288       37454 :     r = new_intArrayType(n);
     289       37454 :     memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
     290       37454 :     return r;
     291             : }
     292             : 
     293             : /* num for compressed key */
     294             : int
     295       53974 : internal_size(int *a, int len)
     296             : {
     297             :     int         i;
     298       53974 :     int64       size = 0;
     299             : 
     300    12899374 :     for (i = 0; i < len; i += 2)
     301             :     {
     302    12845400 :         if (!i || a[i] != a[i - 1]) /* do not count repeated range */
     303    12845400 :             size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
     304             :     }
     305             : 
     306       53974 :     if (size > (int64) INT_MAX || size < (int64) INT_MIN)
     307           0 :         return -1;              /* overflow */
     308       53974 :     return (int) size;
     309             : }
     310             : 
     311             : /* unique-ify elements of r in-place ... r must be sorted already */
     312             : ArrayType *
     313     5187680 : _int_unique(ArrayType *r)
     314             : {
     315     5187680 :     int         num = ARRNELEMS(r);
     316     5187680 :     bool        ascending = true;
     317             : 
     318     5187680 :     num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
     319             :                       &ascending);
     320             : 
     321     5187680 :     return resize_intArrayType(r, num);
     322             : }
     323             : 
     324             : void
     325           0 : gensign(BITVECP sign, int *a, int len, int siglen)
     326             : {
     327             :     int         i;
     328             : 
     329             :     /* we assume that the sign vector is previously zeroed */
     330           0 :     for (i = 0; i < len; i++)
     331             :     {
     332           0 :         HASH(sign, *a, siglen);
     333           0 :         a++;
     334             :     }
     335           0 : }
     336             : 
     337             : int32
     338           2 : intarray_match_first(ArrayType *a, int32 elem)
     339             : {
     340             :     int32      *aa,
     341             :                 c,
     342             :                 i;
     343             : 
     344           2 :     CHECKARRVALID(a);
     345           2 :     c = ARRNELEMS(a);
     346           2 :     aa = ARRPTR(a);
     347           4 :     for (i = 0; i < c; i++)
     348           4 :         if (aa[i] == elem)
     349           2 :             return (i + 1);
     350           0 :     return 0;
     351             : }
     352             : 
     353             : ArrayType *
     354           8 : intarray_add_elem(ArrayType *a, int32 elem)
     355             : {
     356             :     ArrayType  *result;
     357             :     int32      *r;
     358             :     int32       c;
     359             : 
     360           8 :     CHECKARRVALID(a);
     361           8 :     c = ARRNELEMS(a);
     362           8 :     result = new_intArrayType(c + 1);
     363           8 :     r = ARRPTR(result);
     364           8 :     if (c > 0)
     365           8 :         memcpy(r, ARRPTR(a), c * sizeof(int32));
     366           8 :     r[c] = elem;
     367           8 :     return result;
     368             : }
     369             : 
     370             : ArrayType *
     371           2 : intarray_concat_arrays(ArrayType *a, ArrayType *b)
     372             : {
     373             :     ArrayType  *result;
     374           2 :     int32       ac = ARRNELEMS(a);
     375           2 :     int32       bc = ARRNELEMS(b);
     376             : 
     377           2 :     CHECKARRVALID(a);
     378           2 :     CHECKARRVALID(b);
     379           2 :     result = new_intArrayType(ac + bc);
     380           2 :     if (ac)
     381           2 :         memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
     382           2 :     if (bc)
     383           2 :         memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
     384           2 :     return result;
     385             : }
     386             : 
     387             : ArrayType *
     388           2 : int_to_intset(int32 elem)
     389             : {
     390             :     ArrayType  *result;
     391             :     int32      *aa;
     392             : 
     393           2 :     result = new_intArrayType(1);
     394           2 :     aa = ARRPTR(result);
     395           2 :     aa[0] = elem;
     396           2 :     return result;
     397             : }

Generated by: LCOV version 1.16