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