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 "_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 */
24 
25 Datum
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
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
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
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
85 {
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
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;
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));
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
188 {
189  return pg_popcount(sign, SIGLEN);
190 }
191 
192 static int
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
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
226 {
228 }
229 
230 static int32
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
245 {
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
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
304 {
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;
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 
464 }
465 
466 Datum
468 {
469  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
470  ArrayType *query = PG_GETARG_ARRAYTYPE_P(1);
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  {
497  retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key), query);
498  break;
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;
535  retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
536  break;
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 }
#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:319
Datum g_intbig_same(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:84
static int32 unionkey(BITVECP sbase, GISTTYPE *add)
Definition: _intbig_gist.c:231
#define RTOldContainsStrategyNumber
Definition: stratnum.h:63
Datum g_intbig_penalty(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:276
Datum g_intbig_compress(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:116
#define RTOldContainedByStrategyNumber
Definition: stratnum.h:64
struct NODE * left
#define GETSIGN(x)
Definition: hstore_gist.c:50
#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:16
Datum g_intbig_decompress(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:225
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:43
int errcode(int sqlerrcode)
Definition: elog.c:608
struct NODE * right
#define MemSet(start, val, len)
Definition: c.h:956
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
bool signconsistent(QUERYTYPE *query, BITVEC sign, bool calcnot)
Definition: _int_bool.c:300
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define HASH(sign, val)
Definition: hstore_gist.c:34
int32 flag
Definition: hstore_gist.c:39
int spl_nleft
Definition: gist.h:114
signed int int32
Definition: c.h:347
uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.c:282
int32 cost
Definition: hstore_gist.c:320
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:133
#define Abs(x)
Definition: c.h:911
#define PG_GETARG_ARRAYTYPE_P(n)
Definition: array.h:251
void pfree(void *pointer)
Definition: mcxt.c:1056
#define GETBIT(x, i)
Definition: blutils.c:32
#define WISH_F(a, b, c)
Definition: hstore_gist.c:65
#define ERROR
Definition: elog.h:43
Datum _intbig_out(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:35
#define GTHDRSIZE
Definition: hstore_gist.c:47
int spl_nright
Definition: gist.h:119
Datum g_intbig_consistent(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:467
char BITVEC[SIGLEN]
Definition: hstore_gist.c:18
char sign
Definition: informix.c:688
Datum key
Definition: gist.h:131
static bool _intbig_overlap(GISTTYPE *a, ArrayType *b)
Definition: _intbig_gist.c:48
#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:33
#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:193
void * palloc0(Size size)
Definition: mcxt.c:980
#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:66
Datum g_intbig_picksplit(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:303
#define ISALLTRUE(x)
Definition: hstore_gist.c:45
#define CALCGTSIZE(flag)
Definition: hstore_gist.c:48
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:187
#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:25
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:949
int errmsg(const char *fmt,...)
Definition: elog.c:822
Datum g_intbig_union(PG_FUNCTION_ARGS)
Definition: _intbig_gist.c:244
#define LOOPBYTE
Definition: hstore_gist.c:21
int i
#define SIGLEN
Definition: hstore_gist.c:15
static int hemdist(GISTTYPE *a, GISTTYPE *b)
Definition: _intbig_gist.c:209
#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:19
#define ARRPTR(x)
Definition: cube.c:24
#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:26
static int comparecost(const void *a, const void *b)
Definition: _intbig_gist.c:296
#define GETENTRY(vec, pos)
Definition: _intbig_gist.c:11
#define DatumGetArrayTypeP(X)
Definition: array.h:249