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