granicus.if.org Git - postgresql/blob - contrib/intarray/_intbig_gist.c

   1 /*
   2  * contrib/intarray/_intbig_gist.c
   3  */
   4 #include "postgres.h"
   5
   6 #include "_int.h"
   7 #include "access/gist.h"
   8 #include "access/stratnum.h"
   9 #include "port/pg_bitutils.h"
  10
  11 #define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))
  12 /*
  13 ** _intbig methods
  14 */
  15 PG_FUNCTION_INFO_V1(g_intbig_consistent);
  16 PG_FUNCTION_INFO_V1(g_intbig_compress);
  17 PG_FUNCTION_INFO_V1(g_intbig_decompress);
  18 PG_FUNCTION_INFO_V1(g_intbig_penalty);
  19 PG_FUNCTION_INFO_V1(g_intbig_picksplit);
  20 PG_FUNCTION_INFO_V1(g_intbig_union);
  21 PG_FUNCTION_INFO_V1(g_intbig_same);
  22 PG_FUNCTION_INFO_V1(_intbig_in);
  23 PG_FUNCTION_INFO_V1(_intbig_out);
  24
  25 Datum
  26 _intbig_in(PG_FUNCTION_ARGS)
  27 {
  28         ereport(ERROR,
  29                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
  30                          errmsg("_intbig_in() not implemented")));
  31         PG_RETURN_DATUM(0);
  32 }
  33
  34 Datum
  35 _intbig_out(PG_FUNCTION_ARGS)
  36 {
  37         ereport(ERROR,
  38                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
  39                          errmsg("_intbig_out() not implemented")));
  40         PG_RETURN_DATUM(0);
  41 }
  42
  43
  44 /*********************************************************************
  45 ** intbig functions
  46 *********************************************************************/
  47 static bool
  48 _intbig_overlap(GISTTYPE *a, ArrayType *b)
  49 {
  50         int                     num = ARRNELEMS(b);
  51         int32      *ptr = ARRPTR(b);
  52
  53         CHECKARRVALID(b);
  54
  55         while (num--)
  56         {
  57                 if (GETBIT(GETSIGN(a), HASHVAL(*ptr)))
  58                         return true;
  59                 ptr++;
  60         }
  61
  62         return false;
  63 }
  64
  65 static bool
  66 _intbig_contains(GISTTYPE *a, ArrayType *b)
  67 {
  68         int                     num = ARRNELEMS(b);
  69         int32      *ptr = ARRPTR(b);
  70
  71         CHECKARRVALID(b);
  72
  73         while (num--)
  74         {
  75                 if (!GETBIT(GETSIGN(a), HASHVAL(*ptr)))
  76                         return false;
  77                 ptr++;
  78         }
  79
  80         return true;
  81 }
  82
  83 Datum
  84 g_intbig_same(PG_FUNCTION_ARGS)
  85 {
  86         GISTTYPE   *a = (GISTTYPE *) PG_GETARG_POINTER(0);
  87         GISTTYPE   *b = (GISTTYPE *) PG_GETARG_POINTER(1);
  88         bool       *result = (bool *) PG_GETARG_POINTER(2);
  89
  90         if (ISALLTRUE(a) && ISALLTRUE(b))
  91                 *result = true;
  92         else if (ISALLTRUE(a))
  93                 *result = false;
  94         else if (ISALLTRUE(b))
  95                 *result = false;
  96         else
  97         {
  98                 int32           i;
  99                 BITVECP         sa = GETSIGN(a),
 100                                         sb = GETSIGN(b);
 101
 102                 *result = true;
 103                 LOOPBYTE
 104                 {
 105                         if (sa[i] != sb[i])
 106                         {
 107                                 *result = false;
 108                                 break;
 109                         }
 110                 }
 111         }
 112         PG_RETURN_POINTER(result);
 113 }
 114
 115 Datum
 116 g_intbig_compress(PG_FUNCTION_ARGS)
 117 {
 118         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 119
 120         if (entry->leafkey)
 121         {
 122                 GISTENTRY  *retval;
 123                 ArrayType  *in = DatumGetArrayTypeP(entry->key);
 124                 int32      *ptr;
 125                 int                     num;
 126                 GISTTYPE   *res = (GISTTYPE *) palloc0(CALCGTSIZE(0));
 127
 128                 CHECKARRVALID(in);
 129                 if (ARRISEMPTY(in))
 130                 {
 131                         ptr = NULL;
 132                         num = 0;
 133                 }
 134                 else
 135                 {
 136                         ptr = ARRPTR(in);
 137                         num = ARRNELEMS(in);
 138                 }
 139                 SET_VARSIZE(res, CALCGTSIZE(0));
 140
 141                 while (num--)
 142                 {
 143                         HASH(GETSIGN(res), *ptr);
 144                         ptr++;
 145                 }
 146
 147                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 148                 gistentryinit(*retval, PointerGetDatum(res),
 149                                           entry->rel, entry->page,
 150                                           entry->offset, false);
 151
 152                 if (in != DatumGetArrayTypeP(entry->key))
 153                         pfree(in);
 154
 155                 PG_RETURN_POINTER(retval);
 156         }
 157         else if (!ISALLTRUE(DatumGetPointer(entry->key)))
 158         {
 159                 GISTENTRY  *retval;
 160                 int                     i;
 161                 BITVECP         sign = GETSIGN(DatumGetPointer(entry->key));
 162                 GISTTYPE   *res;
 163
 164                 LOOPBYTE
 165                 {
 166                         if ((sign[i] & 0xff) != 0xff)
 167                                 PG_RETURN_POINTER(entry);
 168                 }
 169
 170                 res = (GISTTYPE *) palloc(CALCGTSIZE(ALLISTRUE));
 171                 SET_VARSIZE(res, CALCGTSIZE(ALLISTRUE));
 172                 res->flag = ALLISTRUE;
 173
 174                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 175                 gistentryinit(*retval, PointerGetDatum(res),
 176                                           entry->rel, entry->page,
 177                                           entry->offset, false);
 178
 179                 PG_RETURN_POINTER(retval);
 180         }
 181
 182         PG_RETURN_POINTER(entry);
 183 }
 184
 185
 186 static int32
 187 sizebitvec(BITVECP sign)
 188 {
 189         return pg_popcount(sign, SIGLEN);
 190 }
 191
 192 static int
 193 hemdistsign(BITVECP a, BITVECP b)
 194 {
 195         int                     i,
 196                                 diff,
 197                                 dist = 0;
 198
 199         LOOPBYTE
 200         {
 201                 diff = (unsigned char) (a[i] ^ b[i]);
 202                 /* Using the popcount functions here isn't likely to win */
 203                 dist += pg_number_of_ones[diff];
 204         }
 205         return dist;
 206 }
 207
 208 static int
 209 hemdist(GISTTYPE *a, GISTTYPE *b)
 210 {
 211         if (ISALLTRUE(a))
 212         {
 213                 if (ISALLTRUE(b))
 214                         return 0;
 215                 else
 216                         return SIGLENBIT - sizebitvec(GETSIGN(b));
 217         }
 218         else if (ISALLTRUE(b))
 219                 return SIGLENBIT - sizebitvec(GETSIGN(a));
 220
 221         return hemdistsign(GETSIGN(a), GETSIGN(b));
 222 }
 223
 224 Datum
 225 g_intbig_decompress(PG_FUNCTION_ARGS)
 226 {
 227         PG_RETURN_DATUM(PG_GETARG_DATUM(0));
 228 }
 229
 230 static int32
 231 unionkey(BITVECP sbase, GISTTYPE *add)
 232 {
 233         int32           i;
 234         BITVECP         sadd = GETSIGN(add);
 235
 236         if (ISALLTRUE(add))
 237                 return 1;
 238         LOOPBYTE
 239                 sbase[i] |= sadd[i];
 240         return 0;
 241 }
 242
 243 Datum
 244 g_intbig_union(PG_FUNCTION_ARGS)
 245 {
 246         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 247         int                *size = (int *) PG_GETARG_POINTER(1);
 248         BITVEC          base;
 249         int32           i,
 250                                 len;
 251         int32           flag = 0;
 252         GISTTYPE   *result;
 253
 254         MemSet((void *) base, 0, sizeof(BITVEC));
 255         for (i = 0; i < entryvec->n; i++)
 256         {
 257                 if (unionkey(base, GETENTRY(entryvec, i)))
 258                 {
 259                         flag = ALLISTRUE;
 260                         break;
 261                 }
 262         }
 263
 264         len = CALCGTSIZE(flag);
 265         result = (GISTTYPE *) palloc(len);
 266         SET_VARSIZE(result, len);
 267         result->flag = flag;
 268         if (!ISALLTRUE(result))
 269                 memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
 270         *size = len;
 271
 272         PG_RETURN_POINTER(result);
 273 }
 274
 275 Datum
 276 g_intbig_penalty(PG_FUNCTION_ARGS)
 277 {
 278         GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
 279         GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 280         float      *penalty = (float *) PG_GETARG_POINTER(2);
 281         GISTTYPE   *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
 282         GISTTYPE   *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
 283
 284         *penalty = hemdist(origval, newval);
 285         PG_RETURN_POINTER(penalty);
 286 }
 287
 288
 289 typedef struct
 290 {
 291         OffsetNumber pos;
 292         int32           cost;
 293 } SPLITCOST;
 294
 295 static int
 296 comparecost(const void *a, const void *b)
 297 {
 298         return ((const SPLITCOST *) a)->cost - ((const SPLITCOST *) b)->cost;
 299 }
 300
 301
 302 Datum
 303 g_intbig_picksplit(PG_FUNCTION_ARGS)
 304 {
 305         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 306         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 307         OffsetNumber k,
 308                                 j;
 309         GISTTYPE   *datum_l,
 310                            *datum_r;
 311         BITVECP         union_l,
 312                                 union_r;
 313         int32           size_alpha,
 314                                 size_beta;
 315         int32           size_waste,
 316                                 waste = -1;
 317         int32           nbytes;
 318         OffsetNumber seed_1 = 0,
 319                                 seed_2 = 0;
 320         OffsetNumber *left,
 321                            *right;
 322         OffsetNumber maxoff;
 323         BITVECP         ptr;
 324         int                     i;
 325         SPLITCOST  *costvector;
 326         GISTTYPE   *_k,
 327                            *_j;
 328
 329         maxoff = entryvec->n - 2;
 330         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 331         v->spl_left = (OffsetNumber *) palloc(nbytes);
 332         v->spl_right = (OffsetNumber *) palloc(nbytes);
 333
 334         for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 335         {
 336                 _k = GETENTRY(entryvec, k);
 337                 for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 338                 {
 339                         size_waste = hemdist(_k, GETENTRY(entryvec, j));
 340                         if (size_waste > waste)
 341                         {
 342                                 waste = size_waste;
 343                                 seed_1 = k;
 344                                 seed_2 = j;
 345                         }
 346                 }
 347         }
 348
 349         left = v->spl_left;
 350         v->spl_nleft = 0;
 351         right = v->spl_right;
 352         v->spl_nright = 0;
 353
 354         if (seed_1 == 0 || seed_2 == 0)
 355         {
 356                 seed_1 = 1;
 357                 seed_2 = 2;
 358         }
 359
 360         /* form initial .. */
 361         if (ISALLTRUE(GETENTRY(entryvec, seed_1)))
 362         {
 363                 datum_l = (GISTTYPE *) palloc(GTHDRSIZE);
 364                 SET_VARSIZE(datum_l, GTHDRSIZE);
 365                 datum_l->flag = ALLISTRUE;
 366         }
 367         else
 368         {
 369                 datum_l = (GISTTYPE *) palloc(GTHDRSIZE + SIGLEN);
 370                 SET_VARSIZE(datum_l, GTHDRSIZE + SIGLEN);
 371                 datum_l->flag = 0;
 372                 memcpy((void *) GETSIGN(datum_l), (void *) GETSIGN(GETENTRY(entryvec, seed_1)), sizeof(BITVEC));
 373         }
 374         if (ISALLTRUE(GETENTRY(entryvec, seed_2)))
 375         {
 376                 datum_r = (GISTTYPE *) palloc(GTHDRSIZE);
 377                 SET_VARSIZE(datum_r, GTHDRSIZE);
 378                 datum_r->flag = ALLISTRUE;
 379         }
 380         else
 381         {
 382                 datum_r = (GISTTYPE *) palloc(GTHDRSIZE + SIGLEN);
 383                 SET_VARSIZE(datum_r, GTHDRSIZE + SIGLEN);
 384                 datum_r->flag = 0;
 385                 memcpy((void *) GETSIGN(datum_r), (void *) GETSIGN(GETENTRY(entryvec, seed_2)), sizeof(BITVEC));
 386         }
 387
 388         maxoff = OffsetNumberNext(maxoff);
 389         /* sort before ... */
 390         costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 391         for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 392         {
 393                 costvector[j - 1].pos = j;
 394                 _j = GETENTRY(entryvec, j);
 395                 size_alpha = hemdist(datum_l, _j);
 396                 size_beta = hemdist(datum_r, _j);
 397                 costvector[j - 1].cost = Abs(size_alpha - size_beta);
 398         }
 399         qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 400
 401         union_l = GETSIGN(datum_l);
 402         union_r = GETSIGN(datum_r);
 403
 404         for (k = 0; k < maxoff; k++)
 405         {
 406                 j = costvector[k].pos;
 407                 if (j == seed_1)
 408                 {
 409                         *left++ = j;
 410                         v->spl_nleft++;
 411                         continue;
 412                 }
 413                 else if (j == seed_2)
 414                 {
 415                         *right++ = j;
 416                         v->spl_nright++;
 417                         continue;
 418                 }
 419                 _j = GETENTRY(entryvec, j);
 420                 size_alpha = hemdist(datum_l, _j);
 421                 size_beta = hemdist(datum_r, _j);
 422
 423                 if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
 424                 {
 425                         if (ISALLTRUE(datum_l) || ISALLTRUE(_j))
 426                         {
 427                                 if (!ISALLTRUE(datum_l))
 428                                         MemSet((void *) union_l, 0xff, sizeof(BITVEC));
 429                         }
 430                         else
 431                         {
 432                                 ptr = GETSIGN(_j);
 433                                 LOOPBYTE
 434                                         union_l[i] |= ptr[i];
 435                         }
 436                         *left++ = j;
 437                         v->spl_nleft++;
 438                 }
 439                 else
 440                 {
 441                         if (ISALLTRUE(datum_r) || ISALLTRUE(_j))
 442                         {
 443                                 if (!ISALLTRUE(datum_r))
 444                                         MemSet((void *) union_r, 0xff, sizeof(BITVEC));
 445                         }
 446                         else
 447                         {
 448                                 ptr = GETSIGN(_j);
 449                                 LOOPBYTE
 450                                         union_r[i] |= ptr[i];
 451                         }
 452                         *right++ = j;
 453                         v->spl_nright++;
 454                 }
 455         }
 456
 457         *right = *left = FirstOffsetNumber;
 458         pfree(costvector);
 459
 460         v->spl_ldatum = PointerGetDatum(datum_l);
 461         v->spl_rdatum = PointerGetDatum(datum_r);
 462
 463         PG_RETURN_POINTER(v);
 464 }
 465
 466 Datum
 467 g_intbig_consistent(PG_FUNCTION_ARGS)
 468 {
 469         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 470         ArrayType  *query = PG_GETARG_ARRAYTYPE_P(1);
 471         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 472
 473         /* Oid          subtype = PG_GETARG_OID(3); */
 474         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 475         bool            retval;
 476
 477         /* All cases served by this function are inexact */
 478         *recheck = true;
 479
 480         if (ISALLTRUE(DatumGetPointer(entry->key)))
 481                 PG_RETURN_BOOL(true);
 482
 483         if (strategy == BooleanSearchStrategy)
 484         {
 485                 retval = signconsistent((QUERYTYPE *) query,
 486                                                                 GETSIGN(DatumGetPointer(entry->key)),
 487                                                                 false);
 488                 PG_FREE_IF_COPY(query, 1);
 489                 PG_RETURN_BOOL(retval);
 490         }
 491
 492         CHECKARRVALID(query);
 493
 494         switch (strategy)
 495         {
 496                 case RTOverlapStrategyNumber:
 497                         retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key), query);
 498                         break;
 499                 case RTSameStrategyNumber:
 500                         if (GIST_LEAF(entry))
 501                         {
 502                                 int                     i,
 503                                                         num = ARRNELEMS(query);
 504                                 int32      *ptr = ARRPTR(query);
 505                                 BITVEC          qp;
 506                                 BITVECP         dq,
 507                                                         de;
 508
 509                                 memset(qp, 0, sizeof(BITVEC));
 510
 511                                 while (num--)
 512                                 {
 513                                         HASH(qp, *ptr);
 514                                         ptr++;
 515                                 }
 516
 517                                 de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
 518                                 dq = qp;
 519                                 retval = true;
 520                                 LOOPBYTE
 521                                 {
 522                                         if (de[i] != dq[i])
 523                                         {
 524                                                 retval = false;
 525                                                 break;
 526                                         }
 527                                 }
 528
 529                         }
 530                         else
 531                                 retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
 532                         break;
 533                 case RTContainsStrategyNumber:
 534                 case RTOldContainsStrategyNumber:
 535                         retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
 536                         break;
 537                 case RTContainedByStrategyNumber:
 538                 case RTOldContainedByStrategyNumber:
 539                         if (GIST_LEAF(entry))
 540                         {
 541                                 int                     i,
 542                                                         num = ARRNELEMS(query);
 543                                 int32      *ptr = ARRPTR(query);
 544                                 BITVEC          qp;
 545                                 BITVECP         dq,
 546                                                         de;
 547
 548                                 memset(qp, 0, sizeof(BITVEC));
 549
 550                                 while (num--)
 551                                 {
 552                                         HASH(qp, *ptr);
 553                                         ptr++;
 554                                 }
 555
 556                                 de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
 557                                 dq = qp;
 558                                 retval = true;
 559                                 LOOPBYTE
 560                                 {
 561                                         if (de[i] & ~dq[i])
 562                                         {
 563                                                 retval = false;
 564                                                 break;
 565                                         }
 566                                 }
 567                         }
 568                         else
 569                         {
 570                                 /*
 571                                  * Unfortunately, because empty arrays could be anywhere in
 572                                  * the index, we must search the whole tree.
 573                                  */
 574                                 retval = true;
 575                         }
 576                         break;
 577                 default:
 578                         retval = false;
 579         }
 580         PG_FREE_IF_COPY(query, 1);
 581         PG_RETURN_BOOL(retval);
 582 }