Header And Logo

PostgreSQL
| The world's most advanced open source database.

_int_bool.c

Go to the documentation of this file.
00001 /*
00002  * contrib/intarray/_int_bool.c
00003  */
00004 #include "postgres.h"
00005 
00006 #include "miscadmin.h"
00007 #include "utils/builtins.h"
00008 
00009 #include "_int.h"
00010 
00011 PG_FUNCTION_INFO_V1(bqarr_in);
00012 PG_FUNCTION_INFO_V1(bqarr_out);
00013 Datum       bqarr_in(PG_FUNCTION_ARGS);
00014 Datum       bqarr_out(PG_FUNCTION_ARGS);
00015 
00016 PG_FUNCTION_INFO_V1(boolop);
00017 Datum       boolop(PG_FUNCTION_ARGS);
00018 
00019 PG_FUNCTION_INFO_V1(rboolop);
00020 Datum       rboolop(PG_FUNCTION_ARGS);
00021 
00022 PG_FUNCTION_INFO_V1(querytree);
00023 Datum       querytree(PG_FUNCTION_ARGS);
00024 
00025 
00026 /* parser's states */
00027 #define WAITOPERAND 1
00028 #define WAITENDOPERAND  2
00029 #define WAITOPERATOR    3
00030 
00031 /*
00032  * node of query tree, also used
00033  * for storing polish notation in parser
00034  */
00035 typedef struct NODE
00036 {
00037     int32       type;
00038     int32       val;
00039     struct NODE *next;
00040 } NODE;
00041 
00042 typedef struct
00043 {
00044     char       *buf;
00045     int32       state;
00046     int32       count;
00047     /* reverse polish notation in list (for temporary usage) */
00048     NODE       *str;
00049     /* number in str */
00050     int32       num;
00051 } WORKSTATE;
00052 
00053 /*
00054  * get token from query string
00055  */
00056 static int32
00057 gettoken(WORKSTATE *state, int32 *val)
00058 {
00059     char        nnn[16];
00060     int         innn;
00061 
00062     *val = 0;                   /* default result */
00063 
00064     innn = 0;
00065     while (1)
00066     {
00067         if (innn >= sizeof(nnn))
00068             return ERR;         /* buffer overrun => syntax error */
00069         switch (state->state)
00070         {
00071             case WAITOPERAND:
00072                 innn = 0;
00073                 if ((*(state->buf) >= '0' && *(state->buf) <= '9') ||
00074                     *(state->buf) == '-')
00075                 {
00076                     state->state = WAITENDOPERAND;
00077                     nnn[innn++] = *(state->buf);
00078                 }
00079                 else if (*(state->buf) == '!')
00080                 {
00081                     (state->buf)++;
00082                     *val = (int32) '!';
00083                     return OPR;
00084                 }
00085                 else if (*(state->buf) == '(')
00086                 {
00087                     state->count++;
00088                     (state->buf)++;
00089                     return OPEN;
00090                 }
00091                 else if (*(state->buf) != ' ')
00092                     return ERR;
00093                 break;
00094             case WAITENDOPERAND:
00095                 if (*(state->buf) >= '0' && *(state->buf) <= '9')
00096                 {
00097                     nnn[innn++] = *(state->buf);
00098                 }
00099                 else
00100                 {
00101                     long        lval;
00102 
00103                     nnn[innn] = '\0';
00104                     errno = 0;
00105                     lval = strtol(nnn, NULL, 0);
00106                     *val = (int32) lval;
00107                     if (errno != 0 || (long) *val != lval)
00108                         return ERR;
00109                     state->state = WAITOPERATOR;
00110                     return (state->count && *(state->buf) == '\0')
00111                         ? ERR : VAL;
00112                 }
00113                 break;
00114             case WAITOPERATOR:
00115                 if (*(state->buf) == '&' || *(state->buf) == '|')
00116                 {
00117                     state->state = WAITOPERAND;
00118                     *val = (int32) *(state->buf);
00119                     (state->buf)++;
00120                     return OPR;
00121                 }
00122                 else if (*(state->buf) == ')')
00123                 {
00124                     (state->buf)++;
00125                     state->count--;
00126                     return (state->count < 0) ? ERR : CLOSE;
00127                 }
00128                 else if (*(state->buf) == '\0')
00129                     return (state->count) ? ERR : END;
00130                 else if (*(state->buf) != ' ')
00131                     return ERR;
00132                 break;
00133             default:
00134                 return ERR;
00135                 break;
00136         }
00137         (state->buf)++;
00138     }
00139 }
00140 
00141 /*
00142  * push new one in polish notation reverse view
00143  */
00144 static void
00145 pushquery(WORKSTATE *state, int32 type, int32 val)
00146 {
00147     NODE       *tmp = (NODE *) palloc(sizeof(NODE));
00148 
00149     tmp->type = type;
00150     tmp->val = val;
00151     tmp->next = state->str;
00152     state->str = tmp;
00153     state->num++;
00154 }
00155 
00156 #define STACKDEPTH  16
00157 
00158 /*
00159  * make polish notation of query
00160  */
00161 static int32
00162 makepol(WORKSTATE *state)
00163 {
00164     int32       val,
00165                 type;
00166     int32       stack[STACKDEPTH];
00167     int32       lenstack = 0;
00168 
00169     /* since this function recurses, it could be driven to stack overflow */
00170     check_stack_depth();
00171 
00172     while ((type = gettoken(state, &val)) != END)
00173     {
00174         switch (type)
00175         {
00176             case VAL:
00177                 pushquery(state, type, val);
00178                 while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
00179                                     stack[lenstack - 1] == (int32) '!'))
00180                 {
00181                     lenstack--;
00182                     pushquery(state, OPR, stack[lenstack]);
00183                 }
00184                 break;
00185             case OPR:
00186                 if (lenstack && val == (int32) '|')
00187                     pushquery(state, OPR, val);
00188                 else
00189                 {
00190                     if (lenstack == STACKDEPTH)
00191                         ereport(ERROR,
00192                                 (errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
00193                                  errmsg("statement too complex")));
00194                     stack[lenstack] = val;
00195                     lenstack++;
00196                 }
00197                 break;
00198             case OPEN:
00199                 if (makepol(state) == ERR)
00200                     return ERR;
00201                 while (lenstack && (stack[lenstack - 1] == (int32) '&' ||
00202                                     stack[lenstack - 1] == (int32) '!'))
00203                 {
00204                     lenstack--;
00205                     pushquery(state, OPR, stack[lenstack]);
00206                 }
00207                 break;
00208             case CLOSE:
00209                 while (lenstack)
00210                 {
00211                     lenstack--;
00212                     pushquery(state, OPR, stack[lenstack]);
00213                 };
00214                 return END;
00215                 break;
00216             case ERR:
00217             default:
00218                 ereport(ERROR,
00219                         (errcode(ERRCODE_SYNTAX_ERROR),
00220                          errmsg("syntax error")));
00221                 return ERR;
00222 
00223         }
00224     }
00225 
00226     while (lenstack)
00227     {
00228         lenstack--;
00229         pushquery(state, OPR, stack[lenstack]);
00230     };
00231     return END;
00232 }
00233 
00234 typedef struct
00235 {
00236     int32      *arrb;
00237     int32      *arre;
00238 } CHKVAL;
00239 
00240 /*
00241  * is there value 'val' in (sorted) array or not ?
00242  */
00243 static bool
00244 checkcondition_arr(void *checkval, ITEM *item)
00245 {
00246     int32      *StopLow = ((CHKVAL *) checkval)->arrb;
00247     int32      *StopHigh = ((CHKVAL *) checkval)->arre;
00248     int32      *StopMiddle;
00249 
00250     /* Loop invariant: StopLow <= val < StopHigh */
00251 
00252     while (StopLow < StopHigh)
00253     {
00254         StopMiddle = StopLow + (StopHigh - StopLow) / 2;
00255         if (*StopMiddle == item->val)
00256             return (true);
00257         else if (*StopMiddle < item->val)
00258             StopLow = StopMiddle + 1;
00259         else
00260             StopHigh = StopMiddle;
00261     }
00262     return false;
00263 }
00264 
00265 static bool
00266 checkcondition_bit(void *checkval, ITEM *item)
00267 {
00268     return GETBIT(checkval, HASHVAL(item->val));
00269 }
00270 
00271 /*
00272  * evaluate boolean expression, using chkcond() to test the primitive cases
00273  */
00274 static bool
00275 execute(ITEM *curitem, void *checkval, bool calcnot,
00276         bool (*chkcond) (void *checkval, ITEM *item))
00277 {
00278     /* since this function recurses, it could be driven to stack overflow */
00279     check_stack_depth();
00280 
00281     if (curitem->type == VAL)
00282         return (*chkcond) (checkval, curitem);
00283     else if (curitem->val == (int32) '!')
00284     {
00285         return (calcnot) ?
00286             ((execute(curitem - 1, checkval, calcnot, chkcond)) ? false : true)
00287             : true;
00288     }
00289     else if (curitem->val == (int32) '&')
00290     {
00291         if (execute(curitem + curitem->left, checkval, calcnot, chkcond))
00292             return execute(curitem - 1, checkval, calcnot, chkcond);
00293         else
00294             return false;
00295     }
00296     else
00297     {                           /* |-operator */
00298         if (execute(curitem + curitem->left, checkval, calcnot, chkcond))
00299             return true;
00300         else
00301             return execute(curitem - 1, checkval, calcnot, chkcond);
00302     }
00303 }
00304 
00305 /*
00306  * signconsistent & execconsistent called by *_consistent
00307  */
00308 bool
00309 signconsistent(QUERYTYPE *query, BITVEC sign, bool calcnot)
00310 {
00311     return execute(GETQUERY(query) + query->size - 1,
00312                    (void *) sign, calcnot,
00313                    checkcondition_bit);
00314 }
00315 
00316 /* Array must be sorted! */
00317 bool
00318 execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot)
00319 {
00320     CHKVAL      chkval;
00321 
00322     CHECKARRVALID(array);
00323     chkval.arrb = ARRPTR(array);
00324     chkval.arre = chkval.arrb + ARRNELEMS(array);
00325     return execute(GETQUERY(query) + query->size - 1,
00326                    (void *) &chkval, calcnot,
00327                    checkcondition_arr);
00328 }
00329 
00330 typedef struct
00331 {
00332     ITEM       *first;
00333     bool       *mapped_check;
00334 } GinChkVal;
00335 
00336 static bool
00337 checkcondition_gin(void *checkval, ITEM *item)
00338 {
00339     GinChkVal  *gcv = (GinChkVal *) checkval;
00340 
00341     return gcv->mapped_check[item - gcv->first];
00342 }
00343 
00344 bool
00345 gin_bool_consistent(QUERYTYPE *query, bool *check)
00346 {
00347     GinChkVal   gcv;
00348     ITEM       *items = GETQUERY(query);
00349     int         i,
00350                 j = 0;
00351 
00352     if (query->size <= 0)
00353         return FALSE;
00354 
00355     /*
00356      * Set up data for checkcondition_gin.  This must agree with the query
00357      * extraction code in ginint4_queryextract.
00358      */
00359     gcv.first = items;
00360     gcv.mapped_check = (bool *) palloc(sizeof(bool) * query->size);
00361     for (i = 0; i < query->size; i++)
00362     {
00363         if (items[i].type == VAL)
00364             gcv.mapped_check[i] = check[j++];
00365     }
00366 
00367     return execute(GETQUERY(query) + query->size - 1,
00368                    (void *) &gcv, true,
00369                    checkcondition_gin);
00370 }
00371 
00372 static bool
00373 contains_required_value(ITEM *curitem)
00374 {
00375     /* since this function recurses, it could be driven to stack overflow */
00376     check_stack_depth();
00377 
00378     if (curitem->type == VAL)
00379         return true;
00380     else if (curitem->val == (int32) '!')
00381     {
00382         /*
00383          * Assume anything under a NOT is non-required.  For some cases with
00384          * nested NOTs, we could prove there's a required value, but it seems
00385          * unlikely to be worth the trouble.
00386          */
00387         return false;
00388     }
00389     else if (curitem->val == (int32) '&')
00390     {
00391         /* If either side has a required value, we're good */
00392         if (contains_required_value(curitem + curitem->left))
00393             return true;
00394         else
00395             return contains_required_value(curitem - 1);
00396     }
00397     else
00398     {                           /* |-operator */
00399         /* Both sides must have required values */
00400         if (contains_required_value(curitem + curitem->left))
00401             return contains_required_value(curitem - 1);
00402         else
00403             return false;
00404     }
00405 }
00406 
00407 bool
00408 query_has_required_values(QUERYTYPE *query)
00409 {
00410     if (query->size <= 0)
00411         return false;
00412     return contains_required_value(GETQUERY(query) + query->size - 1);
00413 }
00414 
00415 /*
00416  * boolean operations
00417  */
00418 Datum
00419 rboolop(PG_FUNCTION_ARGS)
00420 {
00421     /* just reverse the operands */
00422     return DirectFunctionCall2(boolop,
00423                                PG_GETARG_DATUM(1),
00424                                PG_GETARG_DATUM(0));
00425 }
00426 
00427 Datum
00428 boolop(PG_FUNCTION_ARGS)
00429 {
00430     ArrayType  *val = PG_GETARG_ARRAYTYPE_P_COPY(0);
00431     QUERYTYPE  *query = PG_GETARG_QUERYTYPE_P(1);
00432     CHKVAL      chkval;
00433     bool        result;
00434 
00435     CHECKARRVALID(val);
00436     PREPAREARR(val);
00437     chkval.arrb = ARRPTR(val);
00438     chkval.arre = chkval.arrb + ARRNELEMS(val);
00439     result = execute(GETQUERY(query) + query->size - 1,
00440                      &chkval, true,
00441                      checkcondition_arr);
00442     pfree(val);
00443 
00444     PG_FREE_IF_COPY(query, 1);
00445     PG_RETURN_BOOL(result);
00446 }
00447 
00448 static void
00449 findoprnd(ITEM *ptr, int32 *pos)
00450 {
00451 #ifdef BS_DEBUG
00452     elog(DEBUG3, (ptr[*pos].type == OPR) ?
00453          "%d  %c" : "%d  %d", *pos, ptr[*pos].val);
00454 #endif
00455     if (ptr[*pos].type == VAL)
00456     {
00457         ptr[*pos].left = 0;
00458         (*pos)--;
00459     }
00460     else if (ptr[*pos].val == (int32) '!')
00461     {
00462         ptr[*pos].left = -1;
00463         (*pos)--;
00464         findoprnd(ptr, pos);
00465     }
00466     else
00467     {
00468         ITEM       *curitem = &ptr[*pos];
00469         int32       tmp = *pos;
00470 
00471         (*pos)--;
00472         findoprnd(ptr, pos);
00473         curitem->left = *pos - tmp;
00474         findoprnd(ptr, pos);
00475     }
00476 }
00477 
00478 
00479 /*
00480  * input
00481  */
00482 Datum
00483 bqarr_in(PG_FUNCTION_ARGS)
00484 {
00485     char       *buf = (char *) PG_GETARG_POINTER(0);
00486     WORKSTATE   state;
00487     int32       i;
00488     QUERYTYPE  *query;
00489     int32       commonlen;
00490     ITEM       *ptr;
00491     NODE       *tmp;
00492     int32       pos = 0;
00493 
00494 #ifdef BS_DEBUG
00495     StringInfoData pbuf;
00496 #endif
00497 
00498     state.buf = buf;
00499     state.state = WAITOPERAND;
00500     state.count = 0;
00501     state.num = 0;
00502     state.str = NULL;
00503 
00504     /* make polish notation (postfix, but in reverse order) */
00505     makepol(&state);
00506     if (!state.num)
00507         ereport(ERROR,
00508                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
00509                  errmsg("empty query")));
00510 
00511     commonlen = COMPUTESIZE(state.num);
00512     query = (QUERYTYPE *) palloc(commonlen);
00513     SET_VARSIZE(query, commonlen);
00514     query->size = state.num;
00515     ptr = GETQUERY(query);
00516 
00517     for (i = state.num - 1; i >= 0; i--)
00518     {
00519         ptr[i].type = state.str->type;
00520         ptr[i].val = state.str->val;
00521         tmp = state.str->next;
00522         pfree(state.str);
00523         state.str = tmp;
00524     }
00525 
00526     pos = query->size - 1;
00527     findoprnd(ptr, &pos);
00528 #ifdef BS_DEBUG
00529     initStringInfo(&pbuf);
00530     for (i = 0; i < query->size; i++)
00531     {
00532         if (ptr[i].type == OPR)
00533             appendStringInfo(&pbuf, "%c(%d) ", ptr[i].val, ptr[i].left);
00534         else
00535             appendStringInfo(&pbuf, "%d ", ptr[i].val);
00536     }
00537     elog(DEBUG3, "POR: %s", pbuf.data);
00538     pfree(pbuf.data);
00539 #endif
00540 
00541     PG_RETURN_POINTER(query);
00542 }
00543 
00544 
00545 /*
00546  * out function
00547  */
00548 typedef struct
00549 {
00550     ITEM       *curpol;
00551     char       *buf;
00552     char       *cur;
00553     int32       buflen;
00554 } INFIX;
00555 
00556 #define RESIZEBUF(inf,addsize) while( ( (inf)->cur - (inf)->buf ) + (addsize) + 1 >= (inf)->buflen ) { \
00557     int32 len = inf->cur - inf->buf; \
00558     inf->buflen *= 2; \
00559     inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
00560     inf->cur = inf->buf + len; \
00561 }
00562 
00563 static void
00564 infix(INFIX *in, bool first)
00565 {
00566     if (in->curpol->type == VAL)
00567     {
00568         RESIZEBUF(in, 11);
00569         sprintf(in->cur, "%d", in->curpol->val);
00570         in->cur = strchr(in->cur, '\0');
00571         in->curpol--;
00572     }
00573     else if (in->curpol->val == (int32) '!')
00574     {
00575         bool        isopr = false;
00576 
00577         RESIZEBUF(in, 1);
00578         *(in->cur) = '!';
00579         in->cur++;
00580         *(in->cur) = '\0';
00581         in->curpol--;
00582         if (in->curpol->type == OPR)
00583         {
00584             isopr = true;
00585             RESIZEBUF(in, 2);
00586             sprintf(in->cur, "( ");
00587             in->cur = strchr(in->cur, '\0');
00588         }
00589         infix(in, isopr);
00590         if (isopr)
00591         {
00592             RESIZEBUF(in, 2);
00593             sprintf(in->cur, " )");
00594             in->cur = strchr(in->cur, '\0');
00595         }
00596     }
00597     else
00598     {
00599         int32       op = in->curpol->val;
00600         INFIX       nrm;
00601 
00602         in->curpol--;
00603         if (op == (int32) '|' && !first)
00604         {
00605             RESIZEBUF(in, 2);
00606             sprintf(in->cur, "( ");
00607             in->cur = strchr(in->cur, '\0');
00608         }
00609 
00610         nrm.curpol = in->curpol;
00611         nrm.buflen = 16;
00612         nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
00613 
00614         /* get right operand */
00615         infix(&nrm, false);
00616 
00617         /* get & print left operand */
00618         in->curpol = nrm.curpol;
00619         infix(in, false);
00620 
00621         /* print operator & right operand */
00622         RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
00623         sprintf(in->cur, " %c %s", op, nrm.buf);
00624         in->cur = strchr(in->cur, '\0');
00625         pfree(nrm.buf);
00626 
00627         if (op == (int32) '|' && !first)
00628         {
00629             RESIZEBUF(in, 2);
00630             sprintf(in->cur, " )");
00631             in->cur = strchr(in->cur, '\0');
00632         }
00633     }
00634 }
00635 
00636 
00637 Datum
00638 bqarr_out(PG_FUNCTION_ARGS)
00639 {
00640     QUERYTYPE  *query = PG_GETARG_QUERYTYPE_P(0);
00641     INFIX       nrm;
00642 
00643     if (query->size == 0)
00644         ereport(ERROR,
00645                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
00646                  errmsg("empty query")));
00647 
00648     nrm.curpol = GETQUERY(query) + query->size - 1;
00649     nrm.buflen = 32;
00650     nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
00651     *(nrm.cur) = '\0';
00652     infix(&nrm, true);
00653 
00654     PG_FREE_IF_COPY(query, 0);
00655     PG_RETURN_POINTER(nrm.buf);
00656 }
00657 
00658 
00659 /* Useless old "debugging" function for a fundamentally wrong algorithm */
00660 Datum
00661 querytree(PG_FUNCTION_ARGS)
00662 {
00663     elog(ERROR, "querytree is no longer implemented");
00664     PG_RETURN_NULL();
00665 }