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