contrib/intarray/_int_tool.c

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