PostgreSQL Source Code  git master
_int_bool.c
Go to the documentation of this file.
1 /*
2  * contrib/intarray/_int_bool.c
3  */
4 #include "postgres.h"
5 
6 #include "_int.h"
7 #include "miscadmin.h"
8 #include "utils/builtins.h"
9 
15 
16 
17 /* parser's states */
18 #define WAITOPERAND 1
19 #define WAITENDOPERAND 2
20 #define WAITOPERATOR 3
21 
22 /*
23  * node of query tree, also used
24  * for storing polish notation in parser
25  */
26 typedef struct NODE
27 {
30  struct NODE *next;
31 } NODE;
32 
33 typedef struct
34 {
35  char *buf;
38  /* reverse polish notation in list (for temporary usage) */
40  /* number in str */
42 } WORKSTATE;
43 
44 /*
45  * get token from query string
46  */
47 static int32
49 {
50  char nnn[16];
51  int innn;
52 
53  *val = 0; /* default result */
54 
55  innn = 0;
56  while (1)
57  {
58  if (innn >= sizeof(nnn))
59  return ERR; /* buffer overrun => syntax error */
60  switch (state->state)
61  {
62  case WAITOPERAND:
63  innn = 0;
64  if ((*(state->buf) >= '0' && *(state->buf) <= '9') ||
65  *(state->buf) == '-')
66  {
67  state->state = WAITENDOPERAND;
68  nnn[innn++] = *(state->buf);
69  }
70  else if (*(state->buf) == '!')
71  {
72  (state->buf)++;
73  *val = (int32) '!';
74  return OPR;
75  }
76  else if (*(state->buf) == '(')
77  {
78  state->count++;
79  (state->buf)++;
80  return OPEN;
81  }
82  else if (*(state->buf) != ' ')
83  return ERR;
84  break;
85  case WAITENDOPERAND:
86  if (*(state->buf) >= '0' && *(state->buf) <= '9')
87  {
88  nnn[innn++] = *(state->buf);
89  }
90  else
91  {
92  long lval;
93 
94  nnn[innn] = '\0';
95  errno = 0;
96  lval = strtol(nnn, NULL, 0);
97  *val = (int32) lval;
98  if (errno != 0 || (long) *val != lval)
99  return ERR;
100  state->state = WAITOPERATOR;
101  return (state->count && *(state->buf) == '\0')
102  ? ERR : VAL;
103  }
104  break;
105  case WAITOPERATOR:
106  if (*(state->buf) == '&' || *(state->buf) == '|')
107  {
108  state->state = WAITOPERAND;
109  *val = (int32) *(state->buf);
110  (state->buf)++;
111  return OPR;
112  }
113  else if (*(state->buf) == ')')
114  {
115  (state->buf)++;
116  state->count--;
117  return (state->count < 0) ? ERR : CLOSE;
118  }
119  else if (*(state->buf) == '\0')
120  return (state->count) ? ERR : END;
121  else if (*(state->buf) != ' ')
122  return ERR;
123  break;
124  default:
125  return ERR;
126  break;
127  }
128  (state->buf)++;
129  }
130 }
131 
132 /*
133  * push new one in polish notation reverse view
134  */
135 static void
137 {
138  NODE *tmp = (NODE *) palloc(sizeof(NODE));
139 
140  tmp->type = type;
141  tmp->val = val;
142  tmp->next = state->str;
143  state->str = tmp;
144  state->num++;
145 }
146 
147 #define STACKDEPTH 16
148 
149 /*
150  * make polish notation of query
151  */
152 static int32
154 {
155  int32 val,
156  type;
157  int32 stack[STACKDEPTH];
158  int32 lenstack = 0;
159 
160  /* since this function recurses, it could be driven to stack overflow */
162 
163  while ((type = gettoken(state, &val)) != END)
164  {
165  switch (type)
166  {
167  case VAL:
168  pushquery(state, type, val);
169  while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
170  stack[lenstack - 1] == (int32) '!'))
171  {
172  lenstack--;
173  pushquery(state, OPR, stack[lenstack]);
174  }
175  break;
176  case OPR:
177  if (lenstack && val == (int32) '|')
178  pushquery(state, OPR, val);
179  else
180  {
181  if (lenstack == STACKDEPTH)
182  ereport(ERROR,
183  (errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
184  errmsg("statement too complex")));
185  stack[lenstack] = val;
186  lenstack++;
187  }
188  break;
189  case OPEN:
190  if (makepol(state) == ERR)
191  return ERR;
192  while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
193  stack[lenstack - 1] == (int32) '!'))
194  {
195  lenstack--;
196  pushquery(state, OPR, stack[lenstack]);
197  }
198  break;
199  case CLOSE:
200  while (lenstack)
201  {
202  lenstack--;
203  pushquery(state, OPR, stack[lenstack]);
204  };
205  return END;
206  break;
207  case ERR:
208  default:
209  ereport(ERROR,
210  (errcode(ERRCODE_SYNTAX_ERROR),
211  errmsg("syntax error")));
212  return ERR;
213  }
214  }
215 
216  while (lenstack)
217  {
218  lenstack--;
219  pushquery(state, OPR, stack[lenstack]);
220  };
221  return END;
222 }
223 
224 typedef struct
225 {
228 } CHKVAL;
229 
230 /*
231  * is there value 'val' in (sorted) array or not ?
232  */
233 static bool
234 checkcondition_arr(void *checkval, ITEM *item, void *options)
235 {
236  int32 *StopLow = ((CHKVAL *) checkval)->arrb;
237  int32 *StopHigh = ((CHKVAL *) checkval)->arre;
238  int32 *StopMiddle;
239 
240  /* Loop invariant: StopLow <= val < StopHigh */
241 
242  while (StopLow < StopHigh)
243  {
244  StopMiddle = StopLow + (StopHigh - StopLow) / 2;
245  if (*StopMiddle == item->val)
246  return true;
247  else if (*StopMiddle < item->val)
248  StopLow = StopMiddle + 1;
249  else
250  StopHigh = StopMiddle;
251  }
252  return false;
253 }
254 
255 static bool
256 checkcondition_bit(void *checkval, ITEM *item, void *siglen)
257 {
258  return GETBIT(checkval, HASHVAL(item->val, (int) (intptr_t) siglen));
259 }
260 
261 /*
262  * evaluate boolean expression, using chkcond() to test the primitive cases
263  */
264 static bool
265 execute(ITEM *curitem, void *checkval, void *options, bool calcnot,
266  bool (*chkcond) (void *checkval, ITEM *item, void *options))
267 {
268  /* since this function recurses, it could be driven to stack overflow */
270 
271  if (curitem->type == VAL)
272  return (*chkcond) (checkval, curitem, options);
273  else if (curitem->val == (int32) '!')
274  {
275  return calcnot ?
276  ((execute(curitem - 1, checkval, options, calcnot, chkcond)) ? false : true)
277  : true;
278  }
279  else if (curitem->val == (int32) '&')
280  {
281  if (execute(curitem + curitem->left, checkval, options, calcnot, chkcond))
282  return execute(curitem - 1, checkval, options, calcnot, chkcond);
283  else
284  return false;
285  }
286  else
287  { /* |-operator */
288  if (execute(curitem + curitem->left, checkval, options, calcnot, chkcond))
289  return true;
290  else
291  return execute(curitem - 1, checkval, options, calcnot, chkcond);
292  }
293 }
294 
295 /*
296  * signconsistent & execconsistent called by *_consistent
297  */
298 bool
299 signconsistent(QUERYTYPE *query, BITVECP sign, int siglen, bool calcnot)
300 {
301  return execute(GETQUERY(query) + query->size - 1,
302  (void *) sign, (void *) (intptr_t) siglen, calcnot,
304 }
305 
306 /* Array must be sorted! */
307 bool
308 execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
309 {
310  CHKVAL chkval;
311 
312  CHECKARRVALID(array);
313  chkval.arrb = ARRPTR(array);
314  chkval.arre = chkval.arrb + ARRNELEMS(array);
315  return execute(GETQUERY(query) + query->size - 1,
316  (void *) &chkval, NULL, calcnot,
318 }
319 
320 typedef struct
321 {
324 } GinChkVal;
325 
326 static bool
327 checkcondition_gin(void *checkval, ITEM *item, void *options)
328 {
329  GinChkVal *gcv = (GinChkVal *) checkval;
330 
331  return gcv->mapped_check[item - gcv->first];
332 }
333 
334 bool
335 gin_bool_consistent(QUERYTYPE *query, bool *check)
336 {
337  GinChkVal gcv;
338  ITEM *items = GETQUERY(query);
339  int i,
340  j = 0;
341 
342  if (query->size <= 0)
343  return false;
344 
345  /*
346  * Set up data for checkcondition_gin. This must agree with the query
347  * extraction code in ginint4_queryextract.
348  */
349  gcv.first = items;
350  gcv.mapped_check = (bool *) palloc(sizeof(bool) * query->size);
351  for (i = 0; i < query->size; i++)
352  {
353  if (items[i].type == VAL)
354  gcv.mapped_check[i] = check[j++];
355  }
356 
357  return execute(GETQUERY(query) + query->size - 1,
358  (void *) &gcv, NULL, true,
360 }
361 
362 static bool
364 {
365  /* since this function recurses, it could be driven to stack overflow */
367 
368  if (curitem->type == VAL)
369  return true;
370  else if (curitem->val == (int32) '!')
371  {
372  /*
373  * Assume anything under a NOT is non-required. For some cases with
374  * nested NOTs, we could prove there's a required value, but it seems
375  * unlikely to be worth the trouble.
376  */
377  return false;
378  }
379  else if (curitem->val == (int32) '&')
380  {
381  /* If either side has a required value, we're good */
382  if (contains_required_value(curitem + curitem->left))
383  return true;
384  else
385  return contains_required_value(curitem - 1);
386  }
387  else
388  { /* |-operator */
389  /* Both sides must have required values */
390  if (contains_required_value(curitem + curitem->left))
391  return contains_required_value(curitem - 1);
392  else
393  return false;
394  }
395 }
396 
397 bool
399 {
400  if (query->size <= 0)
401  return false;
402  return contains_required_value(GETQUERY(query) + query->size - 1);
403 }
404 
405 /*
406  * boolean operations
407  */
408 Datum
410 {
411  /* just reverse the operands */
413  PG_GETARG_DATUM(1),
414  PG_GETARG_DATUM(0));
415 }
416 
417 Datum
419 {
421  QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(1);
422  CHKVAL chkval;
423  bool result;
424 
426  PREPAREARR(val);
427  chkval.arrb = ARRPTR(val);
428  chkval.arre = chkval.arrb + ARRNELEMS(val);
429  result = execute(GETQUERY(query) + query->size - 1,
430  &chkval, NULL, true,
432  pfree(val);
433 
434  PG_FREE_IF_COPY(query, 1);
435  PG_RETURN_BOOL(result);
436 }
437 
438 static void
439 findoprnd(ITEM *ptr, int32 *pos)
440 {
441  /* since this function recurses, it could be driven to stack overflow. */
443 
444 #ifdef BS_DEBUG
445  elog(DEBUG3, (ptr[*pos].type == OPR) ?
446  "%d %c" : "%d %d", *pos, ptr[*pos].val);
447 #endif
448  if (ptr[*pos].type == VAL)
449  {
450  ptr[*pos].left = 0;
451  (*pos)--;
452  }
453  else if (ptr[*pos].val == (int32) '!')
454  {
455  ptr[*pos].left = -1;
456  (*pos)--;
457  findoprnd(ptr, pos);
458  }
459  else
460  {
461  ITEM *curitem = &ptr[*pos];
462  int32 tmp = *pos;
463 
464  (*pos)--;
465  findoprnd(ptr, pos);
466  curitem->left = *pos - tmp;
467  findoprnd(ptr, pos);
468  }
469 }
470 
471 
472 /*
473  * input
474  */
475 Datum
477 {
478  char *buf = (char *) PG_GETARG_POINTER(0);
480  int32 i;
481  QUERYTYPE *query;
482  int32 commonlen;
483  ITEM *ptr;
484  NODE *tmp;
485  int32 pos = 0;
486 
487 #ifdef BS_DEBUG
488  StringInfoData pbuf;
489 #endif
490 
491  state.buf = buf;
492  state.state = WAITOPERAND;
493  state.count = 0;
494  state.num = 0;
495  state.str = NULL;
496 
497  /* make polish notation (postfix, but in reverse order) */
498  makepol(&state);
499  if (!state.num)
500  ereport(ERROR,
501  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
502  errmsg("empty query")));
503 
504  if (state.num > QUERYTYPEMAXITEMS)
505  ereport(ERROR,
506  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
507  errmsg("number of query items (%d) exceeds the maximum allowed (%d)",
508  state.num, (int) QUERYTYPEMAXITEMS)));
509  commonlen = COMPUTESIZE(state.num);
510 
511  query = (QUERYTYPE *) palloc(commonlen);
512  SET_VARSIZE(query, commonlen);
513  query->size = state.num;
514  ptr = GETQUERY(query);
515 
516  for (i = state.num - 1; i >= 0; i--)
517  {
518  ptr[i].type = state.str->type;
519  ptr[i].val = state.str->val;
520  tmp = state.str->next;
521  pfree(state.str);
522  state.str = tmp;
523  }
524 
525  pos = query->size - 1;
526  findoprnd(ptr, &pos);
527 #ifdef BS_DEBUG
528  initStringInfo(&pbuf);
529  for (i = 0; i < query->size; i++)
530  {
531  if (ptr[i].type == OPR)
532  appendStringInfo(&pbuf, "%c(%d) ", ptr[i].val, ptr[i].left);
533  else
534  appendStringInfo(&pbuf, "%d ", ptr[i].val);
535  }
536  elog(DEBUG3, "POR: %s", pbuf.data);
537  pfree(pbuf.data);
538 #endif
539 
540  PG_RETURN_POINTER(query);
541 }
542 
543 
544 /*
545  * out function
546  */
547 typedef struct
548 {
550  char *buf;
551  char *cur;
553 } INFIX;
554 
555 #define RESIZEBUF(inf,addsize) while( ( (inf)->cur - (inf)->buf ) + (addsize) + 1 >= (inf)->buflen ) { \
556  int32 len = inf->cur - inf->buf; \
557  inf->buflen *= 2; \
558  inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
559  inf->cur = inf->buf + len; \
560 }
561 
562 static void
563 infix(INFIX *in, bool first)
564 {
565  /* since this function recurses, it could be driven to stack overflow. */
567 
568  if (in->curpol->type == VAL)
569  {
570  RESIZEBUF(in, 11);
571  sprintf(in->cur, "%d", in->curpol->val);
572  in->cur = strchr(in->cur, '\0');
573  in->curpol--;
574  }
575  else if (in->curpol->val == (int32) '!')
576  {
577  bool isopr = false;
578 
579  RESIZEBUF(in, 1);
580  *(in->cur) = '!';
581  in->cur++;
582  *(in->cur) = '\0';
583  in->curpol--;
584  if (in->curpol->type == OPR)
585  {
586  isopr = true;
587  RESIZEBUF(in, 2);
588  sprintf(in->cur, "( ");
589  in->cur = strchr(in->cur, '\0');
590  }
591  infix(in, isopr);
592  if (isopr)
593  {
594  RESIZEBUF(in, 2);
595  sprintf(in->cur, " )");
596  in->cur = strchr(in->cur, '\0');
597  }
598  }
599  else
600  {
601  int32 op = in->curpol->val;
602  INFIX nrm;
603 
604  in->curpol--;
605  if (op == (int32) '|' && !first)
606  {
607  RESIZEBUF(in, 2);
608  sprintf(in->cur, "( ");
609  in->cur = strchr(in->cur, '\0');
610  }
611 
612  nrm.curpol = in->curpol;
613  nrm.buflen = 16;
614  nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
615 
616  /* get right operand */
617  infix(&nrm, false);
618 
619  /* get & print left operand */
620  in->curpol = nrm.curpol;
621  infix(in, false);
622 
623  /* print operator & right operand */
624  RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
625  sprintf(in->cur, " %c %s", op, nrm.buf);
626  in->cur = strchr(in->cur, '\0');
627  pfree(nrm.buf);
628 
629  if (op == (int32) '|' && !first)
630  {
631  RESIZEBUF(in, 2);
632  sprintf(in->cur, " )");
633  in->cur = strchr(in->cur, '\0');
634  }
635  }
636 }
637 
638 
639 Datum
641 {
642  QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(0);
643  INFIX nrm;
644 
645  if (query->size == 0)
646  ereport(ERROR,
647  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
648  errmsg("empty query")));
649 
650  nrm.curpol = GETQUERY(query) + query->size - 1;
651  nrm.buflen = 32;
652  nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
653  *(nrm.cur) = '\0';
654  infix(&nrm, true);
655 
656  PG_FREE_IF_COPY(query, 0);
657  PG_RETURN_POINTER(nrm.buf);
658 }
659 
660 
661 /* Useless old "debugging" function for a fundamentally wrong algorithm */
662 Datum
664 {
665  elog(ERROR, "querytree is no longer implemented");
666  PG_RETURN_NULL();
667 }
#define CLOSE
Definition: _int.h:165
#define OPEN
Definition: _int.h:164
#define END
Definition: _int.h:160
#define PREPAREARR(x)
Definition: _int.h:49
#define COMPUTESIZE(size)
Definition: _int.h:155
#define CHECKARRVALID(x)
Definition: _int.h:30
#define OPR
Definition: _int.h:163
#define VAL
Definition: _int.h:162
#define ERR
Definition: _int.h:161
#define GETQUERY(x)
Definition: _int.h:157
#define QUERYTYPEMAXITEMS
Definition: _int.h:156
#define PG_GETARG_QUERYTYPE_P(n)
Definition: _int.h:170
PG_FUNCTION_INFO_V1(bqarr_in)
Datum querytree(PG_FUNCTION_ARGS)
Definition: _int_bool.c:663
Datum rboolop(PG_FUNCTION_ARGS)
Definition: _int_bool.c:409
static bool checkcondition_arr(void *checkval, ITEM *item, void *options)
Definition: _int_bool.c:234
bool signconsistent(QUERYTYPE *query, BITVECP sign, int siglen, bool calcnot)
Definition: _int_bool.c:299
static void pushquery(WORKSTATE *state, int32 type, int32 val)
Definition: _int_bool.c:136
static bool contains_required_value(ITEM *curitem)
Definition: _int_bool.c:363
static bool checkcondition_bit(void *checkval, ITEM *item, void *siglen)
Definition: _int_bool.c:256
#define RESIZEBUF(inf, addsize)
Definition: _int_bool.c:555
static void findoprnd(ITEM *ptr, int32 *pos)
Definition: _int_bool.c:439
static int32 makepol(WORKSTATE *state)
Definition: _int_bool.c:153
bool query_has_required_values(QUERYTYPE *query)
Definition: _int_bool.c:398
#define WAITOPERAND
Definition: _int_bool.c:18
static int32 gettoken(WORKSTATE *state, int32 *val)
Definition: _int_bool.c:48
Datum bqarr_out(PG_FUNCTION_ARGS)
Definition: _int_bool.c:640
#define WAITENDOPERAND
Definition: _int_bool.c:19
static void infix(INFIX *in, bool first)
Definition: _int_bool.c:563
bool execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
Definition: _int_bool.c:308
#define STACKDEPTH
Definition: _int_bool.c:147
Datum boolop(PG_FUNCTION_ARGS)
Definition: _int_bool.c:418
Datum bqarr_in(PG_FUNCTION_ARGS)
Definition: _int_bool.c:476
static bool checkcondition_gin(void *checkval, ITEM *item, void *options)
Definition: _int_bool.c:327
#define WAITOPERATOR
Definition: _int_bool.c:20
static bool execute(ITEM *curitem, void *checkval, void *options, bool calcnot, bool(*chkcond)(void *checkval, ITEM *item, void *options))
Definition: _int_bool.c:265
struct NODE NODE
bool gin_bool_consistent(QUERYTYPE *query, bool *check)
Definition: _int_bool.c:335
#define PG_GETARG_ARRAYTYPE_P_COPY(n)
Definition: array.h:257
#define GETBIT(x, i)
Definition: blutils.c:33
signed int int32
Definition: c.h:429
#define ARRNELEMS(x)
Definition: cube.c:26
#define ARRPTR(x)
Definition: cube.c:25
int errcode(int sqlerrcode)
Definition: elog.c:693
int errmsg(const char *fmt,...)
Definition: elog.c:904
#define DEBUG3
Definition: elog.h:22
#define ERROR
Definition: elog.h:33
#define elog(elevel,...)
Definition: elog.h:218
#define ereport(elevel,...)
Definition: elog.h:143
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:633
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_RETURN_NULL()
Definition: fmgr.h:345
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
#define HASHVAL(val, siglen)
Definition: hstore_gist.c:44
char * BITVECP
Definition: hstore_gist.c:30
long val
Definition: informix.c:664
char sign
Definition: informix.c:668
int j
Definition: isn.c:74
int i
Definition: isn.c:73
void pfree(void *pointer)
Definition: mcxt.c:1175
void * palloc(Size size)
Definition: mcxt.c:1068
static char ** options
static char * buf
Definition: pg_test_fsync.c:67
#define sprintf
Definition: port.h:227
void check_stack_depth(void)
Definition: postgres.c:3500
uintptr_t Datum
Definition: postgres.h:411
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:342
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:91
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
int32 * arrb
Definition: _int_bool.c:226
int32 * arre
Definition: _int_bool.c:227
ITEM * first
Definition: _int_bool.c:322
bool * mapped_check
Definition: _int_bool.c:323
char * buf
Definition: _int_bool.c:550
char * cur
Definition: _int_bool.c:551
int32 buflen
Definition: _int_bool.c:552
ITEM * curpol
Definition: _int_bool.c:549
Definition: _int.h:141
int16 left
Definition: _int.h:143
int32 val
Definition: _int.h:144
int16 type
Definition: _int.h:142
Definition: _int_bool.c:27
struct NODE * next
Definition: _int_bool.c:30
int32 val
Definition: _int_bool.c:29
struct NODE * left
int32 type
Definition: _int_bool.c:28
int32 size
Definition: _int.h:150
char * buf
Definition: _int_bool.c:35
int32 state
Definition: _int_bool.c:36
int32 num
Definition: _int_bool.c:41
NODE * str
Definition: _int_bool.c:39
int32 count
Definition: _int_bool.c:37
Definition: regguts.h:318
struct state * next
Definition: regguts.h:327