Annotation of src/usr.bin/find/operator.c, Revision 1.1.1.1
1.1 deraadt 1: /*-
2: * Copyright (c) 1990, 1993
3: * The Regents of the University of California. 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, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
16: * 3. All advertising materials mentioning features or use of this software
17: * must display the following acknowledgement:
18: * This product includes software developed by the University of
19: * California, Berkeley and its contributors.
20: * 4. Neither the name of the University nor the names of its contributors
21: * may be used to endorse or promote products derived from this software
22: * without specific prior written permission.
23: *
24: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34: * SUCH DAMAGE.
35: */
36:
37: #ifndef lint
38: /*static char sccsid[] = "from: @(#)operator.c 8.1 (Berkeley) 6/6/93";*/
39: static char rcsid[] = "$Id: operator.c,v 1.3 1993/12/30 21:15:31 jtc Exp $";
40: #endif /* not lint */
41:
42: #include <sys/types.h>
43:
44: #include <err.h>
45: #include <fts.h>
46: #include <stdio.h>
47:
48: #include "find.h"
49:
50: /*
51: * yanknode --
52: * destructively removes the top from the plan
53: */
54: static PLAN *
55: yanknode(planp)
56: PLAN **planp; /* pointer to top of plan (modified) */
57: {
58: PLAN *node; /* top node removed from the plan */
59:
60: if ((node = (*planp)) == NULL)
61: return (NULL);
62: (*planp) = (*planp)->next;
63: node->next = NULL;
64: return (node);
65: }
66:
67: /*
68: * yankexpr --
69: * Removes one expression from the plan. This is used mainly by
70: * paren_squish. In comments below, an expression is either a
71: * simple node or a N_EXPR node containing a list of simple nodes.
72: */
73: static PLAN *
74: yankexpr(planp)
75: PLAN **planp; /* pointer to top of plan (modified) */
76: {
77: register PLAN *next; /* temp node holding subexpression results */
78: PLAN *node; /* pointer to returned node or expression */
79: PLAN *tail; /* pointer to tail of subplan */
80: PLAN *subplan; /* pointer to head of ( ) expression */
81: int f_expr();
82:
83: /* first pull the top node from the plan */
84: if ((node = yanknode(planp)) == NULL)
85: return (NULL);
86:
87: /*
88: * If the node is an '(' then we recursively slurp up expressions
89: * until we find its associated ')'. If it's a closing paren we
90: * just return it and unwind our recursion; all other nodes are
91: * complete expressions, so just return them.
92: */
93: if (node->type == N_OPENPAREN)
94: for (tail = subplan = NULL;;) {
95: if ((next = yankexpr(planp)) == NULL)
96: err(1, "(: missing closing ')'");
97: /*
98: * If we find a closing ')' we store the collected
99: * subplan in our '(' node and convert the node to
100: * a N_EXPR. The ')' we found is ignored. Otherwise,
101: * we just continue to add whatever we get to our
102: * subplan.
103: */
104: if (next->type == N_CLOSEPAREN) {
105: if (subplan == NULL)
106: errx(1, "(): empty inner expression");
107: node->p_data[0] = subplan;
108: node->type = N_EXPR;
109: node->eval = f_expr;
110: break;
111: } else {
112: if (subplan == NULL)
113: tail = subplan = next;
114: else {
115: tail->next = next;
116: tail = next;
117: }
118: tail->next = NULL;
119: }
120: }
121: return (node);
122: }
123:
124: /*
125: * paren_squish --
126: * replaces "parentheisized" plans in our search plan with "expr" nodes.
127: */
128: PLAN *
129: paren_squish(plan)
130: PLAN *plan; /* plan with ( ) nodes */
131: {
132: register PLAN *expr; /* pointer to next expression */
133: register PLAN *tail; /* pointer to tail of result plan */
134: PLAN *result; /* pointer to head of result plan */
135:
136: result = tail = NULL;
137:
138: /*
139: * the basic idea is to have yankexpr do all our work and just
140: * collect it's results together.
141: */
142: while ((expr = yankexpr(&plan)) != NULL) {
143: /*
144: * if we find an unclaimed ')' it means there is a missing
145: * '(' someplace.
146: */
147: if (expr->type == N_CLOSEPAREN)
148: errx(1, "): no beginning '('");
149:
150: /* add the expression to our result plan */
151: if (result == NULL)
152: tail = result = expr;
153: else {
154: tail->next = expr;
155: tail = expr;
156: }
157: tail->next = NULL;
158: }
159: return (result);
160: }
161:
162: /*
163: * not_squish --
164: * compresses "!" expressions in our search plan.
165: */
166: PLAN *
167: not_squish(plan)
168: PLAN *plan; /* plan to process */
169: {
170: register PLAN *next; /* next node being processed */
171: register PLAN *node; /* temporary node used in N_NOT processing */
172: register PLAN *tail; /* pointer to tail of result plan */
173: PLAN *result; /* pointer to head of result plan */
174:
175: tail = result = next = NULL;
176:
177: while ((next = yanknode(&plan)) != NULL) {
178: /*
179: * if we encounter a ( expression ) then look for nots in
180: * the expr subplan.
181: */
182: if (next->type == N_EXPR)
183: next->p_data[0] = not_squish(next->p_data[0]);
184:
185: /*
186: * if we encounter a not, then snag the next node and place
187: * it in the not's subplan. As an optimization we compress
188: * several not's to zero or one not.
189: */
190: if (next->type == N_NOT) {
191: int notlevel = 1;
192:
193: node = yanknode(&plan);
194: while (node->type == N_NOT) {
195: ++notlevel;
196: node = yanknode(&plan);
197: }
198: if (node == NULL)
199: errx(1, "!: no following expression");
200: if (node->type == N_OR)
201: errx(1, "!: nothing between ! and -o");
202: if (notlevel % 2 != 1)
203: next = node;
204: else
205: next->p_data[0] = node;
206: }
207:
208: /* add the node to our result plan */
209: if (result == NULL)
210: tail = result = next;
211: else {
212: tail->next = next;
213: tail = next;
214: }
215: tail->next = NULL;
216: }
217: return (result);
218: }
219:
220: /*
221: * or_squish --
222: * compresses -o expressions in our search plan.
223: */
224: PLAN *
225: or_squish(plan)
226: PLAN *plan; /* plan with ors to be squished */
227: {
228: register PLAN *next; /* next node being processed */
229: register PLAN *tail; /* pointer to tail of result plan */
230: PLAN *result; /* pointer to head of result plan */
231:
232: tail = result = next = NULL;
233:
234: while ((next = yanknode(&plan)) != NULL) {
235: /*
236: * if we encounter a ( expression ) then look for or's in
237: * the expr subplan.
238: */
239: if (next->type == N_EXPR)
240: next->p_data[0] = or_squish(next->p_data[0]);
241:
242: /* if we encounter a not then look for not's in the subplan */
243: if (next->type == N_NOT)
244: next->p_data[0] = or_squish(next->p_data[0]);
245:
246: /*
247: * if we encounter an or, then place our collected plan in the
248: * or's first subplan and then recursively collect the
249: * remaining stuff into the second subplan and return the or.
250: */
251: if (next->type == N_OR) {
252: if (result == NULL)
253: errx(1, "-o: no expression before -o");
254: next->p_data[0] = result;
255: next->p_data[1] = or_squish(plan);
256: if (next->p_data[1] == NULL)
257: errx(1, "-o: no expression after -o");
258: return (next);
259: }
260:
261: /* add the node to our result plan */
262: if (result == NULL)
263: tail = result = next;
264: else {
265: tail->next = next;
266: tail = next;
267: }
268: tail->next = NULL;
269: }
270: return (result);
271: }
![[BACK]](/icons/back.gif){kind=icon}
Return to operator.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / find