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  struct Node *escontext;
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  ereturn(state->escontext, ERR,
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  ereturn(state->escontext, ERR,
211  (errcode(ERRCODE_SYNTAX_ERROR),
212  errmsg("syntax error")));
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  struct Node *escontext = fcinfo->context;
487 
488 #ifdef BS_DEBUG
489  StringInfoData pbuf;
490 #endif
491 
492  state.buf = buf;
493  state.state = WAITOPERAND;
494  state.count = 0;
495  state.num = 0;
496  state.str = NULL;
497  state.escontext = escontext;
498 
499  /* make polish notation (postfix, but in reverse order) */
500  if (makepol(&state) == ERR)
501  PG_RETURN_NULL();
502  if (!state.num)
503  ereturn(escontext, (Datum) 0,
504  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
505  errmsg("empty query")));
506 
507  if (state.num > QUERYTYPEMAXITEMS)
508  ereturn(escontext, (Datum) 0,
509  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
510  errmsg("number of query items (%d) exceeds the maximum allowed (%d)",
511  state.num, (int) QUERYTYPEMAXITEMS)));
512  commonlen = COMPUTESIZE(state.num);
513 
514  query = (QUERYTYPE *) palloc(commonlen);
515  SET_VARSIZE(query, commonlen);
516  query->size = state.num;
517  ptr = GETQUERY(query);
518 
519  for (i = state.num - 1; i >= 0; i--)
520  {
521  ptr[i].type = state.str->type;
522  ptr[i].val = state.str->val;
523  tmp = state.str->next;
524  pfree(state.str);
525  state.str = tmp;
526  }
527 
528  pos = query->size - 1;
529  findoprnd(ptr, &pos);
530 #ifdef BS_DEBUG
531  initStringInfo(&pbuf);
532  for (i = 0; i < query->size; i++)
533  {
534  if (ptr[i].type == OPR)
535  appendStringInfo(&pbuf, "%c(%d) ", ptr[i].val, ptr[i].left);
536  else
537  appendStringInfo(&pbuf, "%d ", ptr[i].val);
538  }
539  elog(DEBUG3, "POR: %s", pbuf.data);
540  pfree(pbuf.data);
541 #endif
542 
543  PG_RETURN_POINTER(query);
544 }
545 
546 
547 /*
548  * out function
549  */
550 typedef struct
551 {
553  char *buf;
554  char *cur;
556 } INFIX;
557 
558 #define RESIZEBUF(inf,addsize) while( ( (inf)->cur - (inf)->buf ) + (addsize) + 1 >= (inf)->buflen ) { \
559  int32 len = inf->cur - inf->buf; \
560  inf->buflen *= 2; \
561  inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
562  inf->cur = inf->buf + len; \
563 }
564 
565 static void
566 infix(INFIX *in, bool first)
567 {
568  /* since this function recurses, it could be driven to stack overflow. */
570 
571  if (in->curpol->type == VAL)
572  {
573  RESIZEBUF(in, 11);
574  sprintf(in->cur, "%d", in->curpol->val);
575  in->cur = strchr(in->cur, '\0');
576  in->curpol--;
577  }
578  else if (in->curpol->val == (int32) '!')
579  {
580  bool isopr = false;
581 
582  RESIZEBUF(in, 1);
583  *(in->cur) = '!';
584  in->cur++;
585  *(in->cur) = '\0';
586  in->curpol--;
587  if (in->curpol->type == OPR)
588  {
589  isopr = true;
590  RESIZEBUF(in, 2);
591  sprintf(in->cur, "( ");
592  in->cur = strchr(in->cur, '\0');
593  }
594  infix(in, isopr);
595  if (isopr)
596  {
597  RESIZEBUF(in, 2);
598  sprintf(in->cur, " )");
599  in->cur = strchr(in->cur, '\0');
600  }
601  }
602  else
603  {
604  int32 op = in->curpol->val;
605  INFIX nrm;
606 
607  in->curpol--;
608  if (op == (int32) '|' && !first)
609  {
610  RESIZEBUF(in, 2);
611  sprintf(in->cur, "( ");
612  in->cur = strchr(in->cur, '\0');
613  }
614 
615  nrm.curpol = in->curpol;
616  nrm.buflen = 16;
617  nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
618 
619  /* get right operand */
620  infix(&nrm, false);
621 
622  /* get & print left operand */
623  in->curpol = nrm.curpol;
624  infix(in, false);
625 
626  /* print operator & right operand */
627  RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
628  sprintf(in->cur, " %c %s", op, nrm.buf);
629  in->cur = strchr(in->cur, '\0');
630  pfree(nrm.buf);
631 
632  if (op == (int32) '|' && !first)
633  {
634  RESIZEBUF(in, 2);
635  sprintf(in->cur, " )");
636  in->cur = strchr(in->cur, '\0');
637  }
638  }
639 }
640 
641 
642 Datum
644 {
645  QUERYTYPE *query = PG_GETARG_QUERYTYPE_P(0);
646  INFIX nrm;
647 
648  if (query->size == 0)
649  ereport(ERROR,
650  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
651  errmsg("empty query")));
652 
653  nrm.curpol = GETQUERY(query) + query->size - 1;
654  nrm.buflen = 32;
655  nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
656  *(nrm.cur) = '\0';
657  infix(&nrm, true);
658 
659  PG_FREE_IF_COPY(query, 0);
660  PG_RETURN_POINTER(nrm.buf);
661 }
662 
663 
664 /* Useless old "debugging" function for a fundamentally wrong algorithm */
665 Datum
667 {
668  elog(ERROR, "querytree is no longer implemented");
669  PG_RETURN_NULL();
670 }
#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:666
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:137
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:558
static void findoprnd(ITEM *ptr, int32 *pos)
Definition: _int_bool.c:439
static int32 makepol(WORKSTATE *state)
Definition: _int_bool.c:154
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:49
Datum bqarr_out(PG_FUNCTION_ARGS)
Definition: _int_bool.c:643
#define WAITENDOPERAND
Definition: _int_bool.c:19
static void infix(INFIX *in, bool first)
Definition: _int_bool.c:566
bool execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
Definition: _int_bool.c:308
#define STACKDEPTH
Definition: _int_bool.c:148
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:264
#define GETBIT(x, i)
Definition: blutils.c:33
signed int int32
Definition: c.h:494
#define ARRNELEMS(x)
Definition: cube.c:26
#define ARRPTR(x)
Definition: cube.c:25
int errcode(int sqlerrcode)
Definition: elog.c:855
int errmsg(const char *fmt,...)
Definition: elog.c:1068
#define ereturn(context, dummy_value,...)
Definition: elog.h:276
#define DEBUG3
Definition: elog.h:28
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
#define ereport(elevel,...)
Definition: elog.h:149
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:644
#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:45
char * BITVECP
Definition: hstore_gist.c:31
long val
Definition: informix.c:670
char sign
Definition: informix.c:674
int j
Definition: isn.c:74
int i
Definition: isn.c:73
void pfree(void *pointer)
Definition: mcxt.c:1521
void * palloc(Size size)
Definition: mcxt.c:1317
static char ** options
static char * buf
Definition: pg_test_fsync.c:73
#define sprintf
Definition: port.h:240
void check_stack_depth(void)
Definition: postgres.c:3531
uintptr_t Datum
Definition: postgres.h:64
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:97
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:553
char * cur
Definition: _int_bool.c:554
int32 buflen
Definition: _int_bool.c:555
ITEM * curpol
Definition: _int_bool.c:552
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
int32 type
Definition: _int_bool.c:28
Definition: nodes.h:129
int32 size
Definition: _int.h:150
char * buf
Definition: _int_bool.c:35
struct Node * escontext
Definition: _int_bool.c:38
int32 state
Definition: _int_bool.c:36
int32 num
Definition: _int_bool.c:42
NODE * str
Definition: _int_bool.c:40
int32 count
Definition: _int_bool.c:37
Definition: regguts.h:323
struct state * next
Definition: regguts.h:332
static ItemArray items
Definition: test_tidstore.c:49
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305
const char * type