![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to operator.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / find|
Return to operator.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / find |
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.