Return to operator.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / find

Annotation of 43BSDReno/usr.bin/find/operator.c, revision 1.1

1.1     ! root        1: /*-
        !             2:  * Copyright (c) 1990 The Regents of the University of California.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * This code is derived from software contributed to Berkeley by
        !             6:  * Cimarron D. Taylor of the University of California, Berkeley.
        !             7:  *
        !             8:  * Redistribution and use in source and binary forms are permitted provided
        !             9:  * that: (1) source distributions retain this entire copyright notice and
        !            10:  * comment, and (2) distributions including binaries display the following
        !            11:  * acknowledgement:  ``This product includes software developed by the
        !            12:  * University of California, Berkeley and its contributors'' in the
        !            13:  * documentation or other materials provided with the distribution and in
        !            14:  * all advertising materials mentioning features or use of this software.
        !            15:  * Neither the name of the University nor the names of its contributors may
        !            16:  * be used to endorse or promote products derived from this software without
        !            17:  * specific prior written permission.
        !            18:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
        !            19:  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
        !            20:  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            21:  */
        !            22: 
        !            23: #ifndef lint
        !            24: static char sccsid[] = "@(#)operator.c 5.1 (Berkeley) 4/16/90";
        !            25: #endif /* not lint */
        !            26: 
        !            27: #include <sys/types.h>
        !            28: #include <stdio.h>
        !            29: #include "find.h"
        !            30:     
        !            31: /*
        !            32:  * find_yanknode --
        !            33:  *     destructively removes the top from the plan
        !            34:  */
        !            35: PLAN *
        !            36: find_yanknode(planp)    
        !            37:        PLAN **planp;           /* pointer to top of plan (modified) */
        !            38: {
        !            39:        PLAN *node;             /* top node removed from the plan */
        !            40:     
        !            41:        if ((node = (*planp)) == NULL)
        !            42:                return(NULL);
        !            43:        (*planp) = (*planp)->next;
        !            44:        node->next = NULL;
        !            45:        return(node);
        !            46: }
        !            47:  
        !            48: /*
        !            49:  * find_yankexpr --
        !            50:  *     Removes one expression from the plan.  This is used mainly by
        !            51:  *     find_squish_paren.  In comments below, an expression is either
        !            52:  *     a simple node or a T_EXPR node containing a list of simple nodes.
        !            53:  */
        !            54: PLAN *
        !            55: find_yankexpr(planp)    
        !            56:        PLAN **planp;           /* pointer to top of plan (modified) */
        !            57: {
        !            58:        register PLAN *next;    /* temp node holding subexpression results */
        !            59:        PLAN *node;             /* pointer to returned node or expression */
        !            60:        PLAN *tail;             /* pointer to tail of subplan */
        !            61:        PLAN *subplan;          /* pointer to head of ( ) expression */
        !            62:        int f_expr();
        !            63:     
        !            64:        /* first pull the top node from the plan */
        !            65:        if ((node = find_yanknode(planp)) == NULL)
        !            66:                return(NULL);
        !            67:     
        !            68:        /*
        !            69:         * If the node is an '(' then we recursively slurp up expressions
        !            70:         * until we find its associated ')'.  If it's a closing paren we
        !            71:         * just return it and unwind our recursion; all other nodes are
        !            72:         * complete expressions, so just return them.
        !            73:         */
        !            74:        if (node->type == T_OPENPAREN)
        !            75:                for (tail = subplan = NULL;;) {
        !            76:                        if ((next = find_yankexpr(planp)) == NULL)
        !            77:                                bad_arg("(", "missing closing ')'");
        !            78:                        /*
        !            79:                         * If we find a closing ')' we store the collected
        !            80:                         * subplan in our '(' node and convert the node to
        !            81:                         * a T_EXPR.  The ')' we found is ignored.  Otherwise,
        !            82:                         * we just continue to add whatever we get to our
        !            83:                         * subplan.
        !            84:                         */
        !            85:                        if (next->type == T_CLOSEPAREN) {
        !            86:                                if (subplan == NULL)
        !            87:                                        bad_arg("()", "empty inner expression");
        !            88:                                node->p_data[0] = subplan;
        !            89:                                node->type = T_EXPR;
        !            90:                                node->eval = f_expr;
        !            91:                                break;
        !            92:                        } else {
        !            93:                                if (subplan == NULL)
        !            94:                                        tail = subplan = next;
        !            95:                                else {
        !            96:                                        tail->next = next;
        !            97:                                        tail = next;
        !            98:                                }
        !            99:                                tail->next = NULL;
        !           100:                        }
        !           101:                }
        !           102:        return(node);
        !           103: }
        !           104:  
        !           105: /*
        !           106:  * find_squish_paren --
        !           107:  *     replaces "parentheisized" plans in our search plan with "expr" nodes.
        !           108:  */
        !           109: PLAN *
        !           110: find_squish_paren(plan)
        !           111:        PLAN *plan;             /* plan with ( ) nodes */
        !           112: {
        !           113:        register PLAN *expr;    /* pointer to next expression */
        !           114:        register PLAN *tail;    /* pointer to tail of result plan */
        !           115:        PLAN *result;           /* pointer to head of result plan */
        !           116:     
        !           117:        result = tail = NULL;
        !           118: 
        !           119:        /*
        !           120:         * the basic idea is to have find_yankexpr do all our work and just
        !           121:         * collect it's results together.
        !           122:         */
        !           123:        while ((expr = find_yankexpr(&plan)) != NULL) {
        !           124:                /*
        !           125:                 * if we find an unclaimed ')' it means there is a missing
        !           126:                 * '(' someplace.
        !           127:                 */
        !           128:                if (expr->type == T_CLOSEPAREN)
        !           129:                        bad_arg(")", "no beginning '('");
        !           130: 
        !           131:                /* add the expression to our result plan */
        !           132:                if (result == NULL)
        !           133:                        tail = result = expr;
        !           134:                else {
        !           135:                        tail->next = expr;
        !           136:                        tail = expr;
        !           137:                }
        !           138:                tail->next = NULL;
        !           139:        }
        !           140:        return(result);
        !           141: }
        !           142:  
        !           143: /*
        !           144:  * find_squish_not --
        !           145:  *     compresses "!" expressions in our search plan.
        !           146:  */
        !           147: PLAN *
        !           148: find_squish_not(plan)
        !           149:        PLAN *plan;             /* plan to process */
        !           150: {
        !           151:        register PLAN *next;    /* next node being processed */
        !           152:        register PLAN *node;    /* temporary node used in T_NOT processing */
        !           153:        register PLAN *tail;    /* pointer to tail of result plan */
        !           154:        PLAN *result;           /* pointer to head of result plan */
        !           155:     
        !           156:        tail = result = next = NULL;
        !           157:     
        !           158:        while ((next = find_yanknode(&plan)) != NULL) {
        !           159:                /*
        !           160:                 * if we encounter a ( expression ) then look for nots in
        !           161:                 * the expr subplan.
        !           162:                 */
        !           163:                if (next->type == T_EXPR)
        !           164:                        next->p_data[0] = find_squish_not(next->p_data[0]);
        !           165: 
        !           166:                /*
        !           167:                 * if we encounter a not, then snag the next node and place
        !           168:                 * it in the not's subplan.  As an optimization we compress
        !           169:                 * several not's to zero or one not.
        !           170:                 */
        !           171:                if (next->type == T_NOT) {
        !           172:                        int notlevel = 1;
        !           173: 
        !           174:                        node = find_yanknode(&plan);
        !           175:                        while (node->type == T_NOT) {
        !           176:                                ++notlevel;
        !           177:                                node = find_yanknode(&plan);
        !           178:                        }
        !           179:                        if (node == NULL)
        !           180:                                bad_arg("!", "no following expression");
        !           181:                        if (node->type == T_OR)
        !           182:                                bad_arg("!", "nothing between ! and -o");
        !           183:                        if (notlevel % 2 != 1)
        !           184:                                next = node;
        !           185:                        else
        !           186:                                next->p_data[0] = node;
        !           187:                }
        !           188: 
        !           189:                /* add the node to our result plan */
        !           190:                if (result == NULL)
        !           191:                        tail = result = next;
        !           192:                else {
        !           193:                        tail->next = next;
        !           194:                        tail = next;
        !           195:                }
        !           196:                tail->next = NULL;
        !           197:        }
        !           198:        return(result);
        !           199: }
        !           200:  
        !           201: /*
        !           202:  * find_squish_or --
        !           203:  *     compresses -o expressions in our search plan.
        !           204:  */
        !           205: PLAN *
        !           206: find_squish_or(plan)
        !           207:        PLAN *plan;             /* plan with ors to be squished */
        !           208: {
        !           209:        register PLAN *next;    /* next node being processed */
        !           210:        register PLAN *tail;    /* pointer to tail of result plan */
        !           211:        PLAN *result;           /* pointer to head of result plan */
        !           212:     
        !           213:        tail = result = next = NULL;
        !           214:     
        !           215:        while ((next = find_yanknode(&plan)) != NULL) {
        !           216:                /*
        !           217:                 * if we encounter a ( expression ) then look for or's in
        !           218:                 * the expr subplan.
        !           219:                 */
        !           220:                if (next->type == T_EXPR)
        !           221:                        next->p_data[0] = find_squish_or(next->p_data[0]);
        !           222: 
        !           223:                /* if we encounter a not then look for not's in the subplan */
        !           224:                if (next->type == T_NOT)
        !           225:                        next->p_data[0] = find_squish_or(next->p_data[0]);
        !           226: 
        !           227:                /*
        !           228:                 * if we encounter an or, then place our collected plan in the
        !           229:                 * or's first subplan and then recursively collect the
        !           230:                 * remaining stuff into the second subplan and return the or.
        !           231:                 */
        !           232:                if (next->type == T_OR) {
        !           233:                        if (result == NULL)
        !           234:                                bad_arg("-o", "no expression before -o");
        !           235:                        next->p_data[0] = result;
        !           236:                        next->p_data[1] = find_squish_or(plan);
        !           237:                        if (next->p_data[1] == NULL)
        !           238:                                bad_arg("-o", "no expression after -o");
        !           239:                        return(next);
        !           240:                }
        !           241: 
        !           242:                /* add the node to our result plan */
        !           243:                if (result == NULL)
        !           244:                        tail = result = next;
        !           245:                else {
        !           246:                        tail->next = next;
        !           247:                        tail = next;
        !           248:                }
        !           249:                tail->next = NULL;
        !           250:        }
        !           251:        return(result);
        !           252: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.