LCOV - code coverage report
Current view: top level - contrib/intarray - _int_tool.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 175 182 96.2 %
Date: 2025-04-01 14:15:22 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      188654 : 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      188654 :     na = ARRNELEMS(a);
      26      188654 :     nb = ARRNELEMS(b);
      27      188654 :     da = ARRPTR(a);
      28      188654 :     db = ARRPTR(b);
      29             : 
      30      188654 :     i = j = n = 0;
      31      467532 :     while (i < na && j < nb)
      32             :     {
      33      453896 :         if (da[i] < db[j])
      34      265478 :             i++;
      35      188418 :         else if (da[i] == db[j])
      36             :         {
      37       13400 :             n++;
      38       13400 :             i++;
      39       13400 :             j++;
      40             :         }
      41             :         else
      42      175018 :             break;              /* db[j] is not in da */
      43             :     }
      44             : 
      45      188654 :     return (n == nb);
      46             : }
      47             : 
      48             : /* arguments are assumed sorted */
      49             : bool
      50       47392 : 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       47392 :     na = ARRNELEMS(a);
      60       47392 :     nb = ARRNELEMS(b);
      61       47392 :     da = ARRPTR(a);
      62       47392 :     db = ARRPTR(b);
      63             : 
      64       47392 :     i = j = 0;
      65      223964 :     while (i < na && j < nb)
      66             :     {
      67      182466 :         if (da[i] < db[j])
      68       93354 :             i++;
      69       89112 :         else if (da[i] == db[j])
      70        5894 :             return true;
      71             :         else
      72       83218 :             j++;
      73             :     }
      74             : 
      75       41498 :     return false;
      76             : }
      77             : 
      78             : ArrayType *
      79     4469926 : inner_int_union(ArrayType *a, ArrayType *b)
      80             : {
      81     4469926 :     ArrayType  *r = NULL;
      82             : 
      83     4469926 :     CHECKARRVALID(a);
      84     4469926 :     CHECKARRVALID(b);
      85             : 
      86     4469926 :     if (ARRISEMPTY(a) && ARRISEMPTY(b))
      87         348 :         return new_intArrayType(0);
      88     4469578 :     if (ARRISEMPTY(a))
      89       28438 :         r = copy_intArrayType(b);
      90     4469578 :     if (ARRISEMPTY(b))
      91        9108 :         r = copy_intArrayType(a);
      92             : 
      93     4469578 :     if (!r)
      94             :     {
      95     4432032 :         int         na = ARRNELEMS(a),
      96     4432032 :                     nb = ARRNELEMS(b);
      97     4432032 :         int        *da = ARRPTR(a),
      98     4432032 :                    *db = ARRPTR(b);
      99             :         int         i,
     100             :                     j,
     101             :                    *dr;
     102             : 
     103     4432032 :         r = new_intArrayType(na + nb);
     104     4432032 :         dr = ARRPTR(r);
     105             : 
     106             :         /* union */
     107     4432032 :         i = j = 0;
     108   166310432 :         while (i < na && j < nb)
     109             :         {
     110   161878400 :             if (da[i] == db[j])
     111             :             {
     112    10499740 :                 *dr++ = da[i++];
     113    10499740 :                 j++;
     114             :             }
     115   151378660 :             else if (da[i] < db[j])
     116   127779754 :                 *dr++ = da[i++];
     117             :             else
     118    23598906 :                 *dr++ = db[j++];
     119             :         }
     120             : 
     121    15519096 :         while (i < na)
     122    11087064 :             *dr++ = da[i++];
     123     8484074 :         while (j < nb)
     124     4052042 :             *dr++ = db[j++];
     125             : 
     126     4432032 :         r = resize_intArrayType(r, dr - ARRPTR(r));
     127             :     }
     128             : 
     129     4469578 :     if (ARRNELEMS(r) > 1)
     130     4469558 :         r = _int_unique(r);
     131             : 
     132     4469578 :     return r;
     133             : }
     134             : 
     135             : ArrayType *
     136     3591292 : 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     3591292 :     if (ARRISEMPTY(a) || ARRISEMPTY(b))
     149       36636 :         return new_intArrayType(0);
     150             : 
     151     3554656 :     na = ARRNELEMS(a);
     152     3554656 :     nb = ARRNELEMS(b);
     153     3554656 :     da = ARRPTR(a);
     154     3554656 :     db = ARRPTR(b);
     155     3554656 :     r = new_intArrayType(Min(na, nb));
     156     3554656 :     dr = ARRPTR(r);
     157             : 
     158     3554656 :     i = j = k = 0;
     159    44328642 :     while (i < na && j < nb)
     160             :     {
     161    40773986 :         if (da[i] < db[j])
     162    18820940 :             i++;
     163    21953046 :         else if (da[i] == db[j])
     164             :         {
     165     3643618 :             if (k == 0 || dr[k - 1] != db[j])
     166     3643618 :                 dr[k++] = db[j];
     167     3643618 :             i++;
     168     3643618 :             j++;
     169             :         }
     170             :         else
     171    18309428 :             j++;
     172             :     }
     173             : 
     174     3554656 :     if (k == 0)
     175             :     {
     176     2826660 :         pfree(r);
     177     2826660 :         return new_intArrayType(0);
     178             :     }
     179             :     else
     180      727996 :         return resize_intArrayType(r, k);
     181             : }
     182             : 
     183             : void
     184     8677144 : rt__int_size(ArrayType *a, float *size)
     185             : {
     186     8677144 :     *size = (float) ARRNELEMS(a);
     187     8677144 : }
     188             : 
     189             : /* comparison function for isort() and _int_unique() */
     190             : static inline int
     191   704947040 : isort_cmp(const void *a, const void *b, void *arg)
     192             : {
     193   704947040 :     int32       aval = *((const int32 *) a);
     194   704947040 :     int32       bval = *((const int32 *) b);
     195             : 
     196   704947040 :     if (*((bool *) arg))
     197             :     {
     198             :         /* compare for ascending order */
     199   704947028 :         if (aval < bval)
     200   307937200 :             return -1;
     201   397009828 :         if (aval > bval)
     202   394757394 :             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     2252434 :     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    11065010 : new_intArrayType(int num)
     225             : {
     226             :     ArrayType  *r;
     227             :     int         nbytes;
     228             : 
     229             :     /* if no elements, return a zero-dimensional array */
     230    11065010 :     if (num <= 0)
     231             :     {
     232             :         Assert(num == 0);
     233     2863644 :         r = construct_empty_array(INT4OID);
     234     2863644 :         return r;
     235             :     }
     236             : 
     237     8201366 :     nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
     238             : 
     239     8201366 :     r = (ArrayType *) palloc0(nbytes);
     240             : 
     241     8201366 :     SET_VARSIZE(r, nbytes);
     242     8201366 :     ARR_NDIM(r) = 1;
     243     8201366 :     r->dataoffset = 0;           /* marker for no null bitmap */
     244     8201366 :     ARR_ELEMTYPE(r) = INT4OID;
     245     8201366 :     ARR_DIMS(r)[0] = num;
     246     8201366 :     ARR_LBOUND(r)[0] = 1;
     247             : 
     248     8201366 :     return r;
     249             : }
     250             : 
     251             : ArrayType *
     252    10295270 : resize_intArrayType(ArrayType *a, int num)
     253             : {
     254             :     int         nbytes;
     255             :     int         i;
     256             : 
     257             :     /* if no elements, return a zero-dimensional array */
     258    10295270 :     if (num <= 0)
     259             :     {
     260             :         Assert(num == 0);
     261         432 :         a = construct_empty_array(INT4OID);
     262         432 :         return a;
     263             :     }
     264             : 
     265    10294838 :     if (num == ARRNELEMS(a))
     266     8000438 :         return a;
     267             : 
     268     2294400 :     nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
     269             : 
     270     2294400 :     a = (ArrayType *) repalloc(a, nbytes);
     271             : 
     272     2294400 :     SET_VARSIZE(a, nbytes);
     273             :     /* usually the array should be 1-D already, but just in case ... */
     274     4588800 :     for (i = 0; i < ARR_NDIM(a); i++)
     275             :     {
     276     2294400 :         ARR_DIMS(a)[i] = num;
     277     2294400 :         num = 1;
     278             :     }
     279     2294400 :     return a;
     280             : }
     281             : 
     282             : ArrayType *
     283       40090 : copy_intArrayType(ArrayType *a)
     284             : {
     285             :     ArrayType  *r;
     286       40090 :     int         n = ARRNELEMS(a);
     287             : 
     288       40090 :     r = new_intArrayType(n);
     289       40090 :     memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
     290       40090 :     return r;
     291             : }
     292             : 
     293             : /* num for compressed key */
     294             : int
     295       61126 : internal_size(int *a, int len)
     296             : {
     297             :     int         i;
     298       61126 :     int64       size = 0;
     299             : 
     300    14442830 :     for (i = 0; i < len; i += 2)
     301             :     {
     302    14381704 :         if (!i || a[i] != a[i - 1]) /* do not count repeated range */
     303    14381704 :             size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
     304             :     }
     305             : 
     306       61126 :     if (size > (int64) INT_MAX || size < (int64) INT_MIN)
     307           0 :         return -1;              /* overflow */
     308       61126 :     return (int) size;
     309             : }
     310             : 
     311             : /* unique-ify elements of r in-place ... r must be sorted already */
     312             : ArrayType *
     313     5129394 : _int_unique(ArrayType *r)
     314             : {
     315     5129394 :     int         num = ARRNELEMS(r);
     316     5129394 :     bool        ascending = true;
     317             : 
     318     5129394 :     num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
     319             :                       &ascending);
     320             : 
     321     5129394 :     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.14