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