contrib/intarray/_int_tool.c

   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 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         na = ARRNELEMS(a);
  25         nb = ARRNELEMS(b);
  26         da = ARRPTR(a);
  27         db = ARRPTR(b);
  28
  29         i = j = n = 0;
  30         while (i < na && j < nb)
  31         {
  32                 if (da[i] < db[j])
  33                         i++;
  34                 else if (da[i] == db[j])
  35                 {
  36                         n++;
  37                         i++;
  38                         j++;
  39                 }
  40                 else
  41                         break;                          /* db[j] is not in da */
  42         }
  43
  44         return (n == nb);
  45 }
  46
  47 /* arguments are assumed sorted */
  48 bool
  49 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         na = ARRNELEMS(a);
  59         nb = ARRNELEMS(b);
  60         da = ARRPTR(a);
  61         db = ARRPTR(b);
  62
  63         i = j = 0;
  64         while (i < na && j < nb)
  65         {
  66                 if (da[i] < db[j])
  67                         i++;
  68                 else if (da[i] == db[j])
  69                         return true;
  70                 else
  71                         j++;
  72         }
  73
  74         return false;
  75 }
  76
  77 ArrayType *
  78 inner_int_union(ArrayType *a, ArrayType *b)
  79 {
  80         ArrayType  *r = NULL;
  81
  82         CHECKARRVALID(a);
  83         CHECKARRVALID(b);
  84
  85         if (ARRISEMPTY(a) && ARRISEMPTY(b))
  86                 return new_intArrayType(0);
  87         if (ARRISEMPTY(a))
  88                 r = copy_intArrayType(b);
  89         if (ARRISEMPTY(b))
  90                 r = copy_intArrayType(a);
  91
  92         if (!r)
  93         {
  94                 int                     na = ARRNELEMS(a),
  95                                         nb = ARRNELEMS(b);
  96                 int                *da = ARRPTR(a),
  97                                    *db = ARRPTR(b);
  98                 int                     i,
  99                                         j,
 100                                    *dr;
 101
 102                 r = new_intArrayType(na + nb);
 103                 dr = ARRPTR(r);
 104
 105                 /* union */
 106                 i = j = 0;
 107                 while (i < na && j < nb)
 108                 {
 109                         if (da[i] == db[j])
 110                         {
 111                                 *dr++ = da[i++];
 112                                 j++;
 113                         }
 114                         else if (da[i] < db[j])
 115                                 *dr++ = da[i++];
 116                         else
 117                                 *dr++ = db[j++];
 118                 }
 119
 120                 while (i < na)
 121                         *dr++ = da[i++];
 122                 while (j < nb)
 123                         *dr++ = db[j++];
 124
 125                 r = resize_intArrayType(r, dr - ARRPTR(r));
 126         }
 127
 128         if (ARRNELEMS(r) > 1)
 129                 r = _int_unique(r);
 130
 131         return r;
 132 }
 133
 134 ArrayType *
 135 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         if (ARRISEMPTY(a) || ARRISEMPTY(b))
 148                 return new_intArrayType(0);
 149
 150         na = ARRNELEMS(a);
 151         nb = ARRNELEMS(b);
 152         da = ARRPTR(a);
 153         db = ARRPTR(b);
 154         r = new_intArrayType(Min(na, nb));
 155         dr = ARRPTR(r);
 156
 157         i = j = k = 0;
 158         while (i < na && j < nb)
 159         {
 160                 if (da[i] < db[j])
 161                         i++;
 162                 else if (da[i] == db[j])
 163                 {
 164                         if (k == 0 || dr[k - 1] != db[j])
 165                                 dr[k++] = db[j];
 166                         i++;
 167                         j++;
 168                 }
 169                 else
 170                         j++;
 171         }
 172
 173         if (k == 0)
 174         {
 175                 pfree(r);
 176                 return new_intArrayType(0);
 177         }
 178         else
 179                 return resize_intArrayType(r, k);
 180 }
 181
 182 void
 183 rt__int_size(ArrayType *a, float *size)
 184 {
 185         *size = (float) ARRNELEMS(a);
 186 }
 187
 188 /* qsort_arg comparison function for isort() */
 189 static int
 190 isort_cmp(const void *a, const void *b, void *arg)
 191 {
 192         int32           aval = *((const int32 *) a);
 193         int32           bval = *((const int32 *) b);
 194
 195         if (aval < bval)
 196                 return -1;
 197         if (aval > bval)
 198                 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         *((bool *) arg) = true;
 206         return 0;
 207 }
 208
 209 /* Sort the given data (len >= 2).  Return true if any duplicates found */
 210 bool
 211 isort(int32 *a, int len)
 212 {
 213         bool            r = false;
 214
 215         qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
 216         return r;
 217 }
 218
 219 /* Create a new int array with room for "num" elements */
 220 ArrayType *
 221 new_intArrayType(int num)
 222 {
 223         ArrayType  *r;
 224         int                     nbytes;
 225
 226         /* if no elements, return a zero-dimensional array */
 227         if (num <= 0)
 228         {
 229                 Assert(num == 0);
 230                 r = construct_empty_array(INT4OID);
 231                 return r;
 232         }
 233
 234         nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
 235
 236         r = (ArrayType *) palloc0(nbytes);
 237
 238         SET_VARSIZE(r, nbytes);
 239         ARR_NDIM(r) = 1;
 240         r->dataoffset = 0;                      /* marker for no null bitmap */
 241         ARR_ELEMTYPE(r) = INT4OID;
 242         ARR_DIMS(r)[0] = num;
 243         ARR_LBOUND(r)[0] = 1;
 244
 245         return r;
 246 }
 247
 248 ArrayType *
 249 resize_intArrayType(ArrayType *a, int num)
 250 {
 251         int                     nbytes;
 252         int                     i;
 253
 254         /* if no elements, return a zero-dimensional array */
 255         if (num <= 0)
 256         {
 257                 Assert(num == 0);
 258                 a = construct_empty_array(INT4OID);
 259                 return a;
 260         }
 261
 262         if (num == ARRNELEMS(a))
 263                 return a;
 264
 265         nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
 266
 267         a = (ArrayType *) repalloc(a, nbytes);
 268
 269         SET_VARSIZE(a, nbytes);
 270         /* usually the array should be 1-D already, but just in case ... */
 271         for (i = 0; i < ARR_NDIM(a); i++)
 272         {
 273                 ARR_DIMS(a)[i] = num;
 274                 num = 1;
 275         }
 276         return a;
 277 }
 278
 279 ArrayType *
 280 copy_intArrayType(ArrayType *a)
 281 {
 282         ArrayType  *r;
 283         int                     n = ARRNELEMS(a);
 284
 285         r = new_intArrayType(n);
 286         memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
 287         return r;
 288 }
 289
 290 /* num for compressed key */
 291 int
 292 internal_size(int *a, int len)
 293 {
 294         int                     i;
 295         int64           size = 0;
 296
 297         for (i = 0; i < len; i += 2)
 298         {
 299                 if (!i || a[i] != a[i - 1]) /* do not count repeated range */
 300                         size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
 301         }
 302
 303         if (size > (int64) INT_MAX || size < (int64) INT_MIN)
 304                 return -1;                              /* overflow */
 305         return (int) size;
 306 }
 307
 308 /* unique-ify elements of r in-place ... r must be sorted already */
 309 ArrayType *
 310 _int_unique(ArrayType *r)
 311 {
 312         int                     num = ARRNELEMS(r);
 313         bool            duplicates_found;       /* not used */
 314
 315         num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
 316                                           &duplicates_found);
 317
 318         return resize_intArrayType(r, num);
 319 }
 320
 321 void
 322 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         for (i = 0; i < len; i++)
 328         {
 329                 HASH(sign, *a, siglen);
 330                 a++;
 331         }
 332 }
 333
 334 int32
 335 intarray_match_first(ArrayType *a, int32 elem)
 336 {
 337         int32      *aa,
 338                                 c,
 339                                 i;
 340
 341         CHECKARRVALID(a);
 342         c = ARRNELEMS(a);
 343         aa = ARRPTR(a);
 344         for (i = 0; i < c; i++)
 345                 if (aa[i] == elem)
 346                         return (i + 1);
 347         return 0;
 348 }
 349
 350 ArrayType *
 351 intarray_add_elem(ArrayType *a, int32 elem)
 352 {
 353         ArrayType  *result;
 354         int32      *r;
 355         int32           c;
 356
 357         CHECKARRVALID(a);
 358         c = ARRNELEMS(a);
 359         result = new_intArrayType(c + 1);
 360         r = ARRPTR(result);
 361         if (c > 0)
 362                 memcpy(r, ARRPTR(a), c * sizeof(int32));
 363         r[c] = elem;
 364         return result;
 365 }
 366
 367 ArrayType *
 368 intarray_concat_arrays(ArrayType *a, ArrayType *b)
 369 {
 370         ArrayType  *result;
 371         int32           ac = ARRNELEMS(a);
 372         int32           bc = ARRNELEMS(b);
 373
 374         CHECKARRVALID(a);
 375         CHECKARRVALID(b);
 376         result = new_intArrayType(ac + bc);
 377         if (ac)
 378                 memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
 379         if (bc)
 380                 memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
 381         return result;
 382 }
 383
 384 ArrayType *
 385 int_to_intset(int32 n)
 386 {
 387         ArrayType  *result;
 388         int32      *aa;
 389
 390         result = new_intArrayType(1);
 391         aa = ARRPTR(result);
 392         aa[0] = n;
 393         return result;
 394 }
 395
 396 int
 397 compASC(const void *a, const void *b)
 398 {
 399         if (*(const int32 *) a == *(const int32 *) b)
 400                 return 0;
 401         return (*(const int32 *) a > *(const int32 *) b) ? 1 : -1;
 402 }
 403
 404 int
 405 compDESC(const void *a, const void *b)
 406 {
 407         if (*(const int32 *) a == *(const int32 *) b)
 408                 return 0;
 409         return (*(const int32 *) a < *(const int32 *) b) ? 1 : -1;
 410 }