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