1 /*
2
3 * Copyright (c) 1984, 1985, 1986 AT&T
4 * All Rights Reserved
5
6 * THIS IS UNPUBLISHED PROPRIETARY SOURCE
7 * CODE OF AT&T.
8 * The copyright notice above does not
9 * evidence any actual or intended
10 * publication of such source code.
11
12 */
13 /* @(#)findnod.c 1.1 */
14
15 /*
16 * FINDNOD.C
17 *
18 * Programmer: D. G. Korn
19 *
20 * Owner: D. A. Lambeth
21 *
22 * Date: April 17, 1980
23 *
24 *
25 *
26 * FINDNOD (NAME, ROOT, TYPE)
27 *
28 * Return a pointer to the Namnod in the tree given by
29 * ROOT whose namid is NAME. If TYPE has non-zero last bit, create
30 * a new node with namid NAME, if one does not exist, and
31 * insert it into ROOT.
32 *
33 * _NAMP (NAME, ROOT, TYPE)
34 *
35 * Return a pointer to the Namnod in the linked list
36 * of Namnods given by ROOT whose namid is NAME. If
37 * TYPE is non-zero, create a new node with namid
38 * NAME, if one does not exist, and link it into the list.
39 *
40 * MAK_NOD (NAME)
41 *
42 * Allocate a Namnod, setting its namid to NAME and its
43 * value to VALUE to NULL.
44 *
45 * COPY_NOD(NODE, TYPE)
46 *
47 * Return a pointer to a Namnod in the last Shell tree
48 * whose name is the same as that in NODE.
49 * If TYPE is non-zero the attributes of NODE
50 * are also copied.
51 *
52 *
53 * See Also: lookup(III), linknod(III), chkid(III)
54 */
55
56 #include "name.h"
57 #include "flags.h"
58
59 #define round(a,b) (a+b-1)&~(b-1)
60
61 struct Namnod *mak_nod();
62 char *bracket_match();
63 struct Namnod *findnod();
64
65 extern char *malloc(), *valup();
66 extern char *strcpy();
67 extern unsigned chkid();
68 extern void failed();
69 extern void assign();
70 extern void free();
71 extern struct Namaray *growaray();
72 extern long aeval();
73 #ifdef NAME_SCOPE
74 extern char *index();
75 struct Namnod *copy_nod();
76 #endif
77 static struct Namnod *_namp();
78
79 static int save_i;
80
81 /*
82 * FINDNOD (NAME, ROOT, TYPE)
83 *
84 * char *NAME;
85 *
86 * struct Amemory *ROOT;
87 *
88 * int TYPE;
89 *
90 * Return a pointer to the Namnod in tree ROOT whose namid is
91 * NAME. If TYPE is non-zero, a Namnod of the given id will
92 * be created, if necessary. If the RE_USE bit is set then
93 * the hash code will not be recomputed. This is set in
94 * lookup(III) when looking up the name in several trees.
95 *
96 * If TYPE is zero, and NAME is not found, NULL is returned.
97 *
98 * NAME should be of a form acceptable to chkid(III).
99 *
100 * Algorithm: Memory (ROOT) is an array of linked lists of
101 * Namnods. Hashing on NAME selects one list; a
102 * scan of this locates the node of interest.
103 */
104
findnod(name,root,type)105 struct Namnod *findnod(name,root,type)
106 char *name;
107 struct Amemory *root;
108 {
109 register char *cp = name;
110 register int c;
111 struct Namnod *np = NULL;
112 {
113 register int i;
114 while((c = *((unsigned char*)cp++)) && c!= '[');
115 if(c)
116 *--cp = 0;
117 if((type&RE_USE)==0)
118 save_i = chkid(name);
119 if((i=save_i)==0)
120 {
121 if(type&CHK_FOR)
122 goto skip;
123 failed (name, notid);
124 }
125 i &= root->memsize-1;
126 np = _namp(name,&root->memhead[i],type&ADD_NOD);
127 skip:
128 if(c)
129 *cp = c;
130 if(np == NULL)
131 return(np);
132 if ((c == 0) && !(attest (np, ARRAY)))
133 return(np);
134 if(c == 0)
135 {
136 setdot (np, 0);
137 return(np);
138 }
139 }
140 {
141 register struct Namaray *ap;
142 register int dot;
143 char *sp;
144 struct Namnod *nq;
145 if (attest (np, ARRAY))
146 ap = arayp (np);
147 else
148 {
149 #ifdef NAME_SCOPE
150 if(attest(np, C_WRITE))
151 {
152 np = copy_nod(np,2);
153 }
154 #endif
155 ap = growaray((struct Namaray *)NULL,0);
156 }
157 cp = bracket_match(sp=cp);
158 c = *cp;
159 *cp = 0;
160 dot = (int)aeval((char*)sp+1);
161 *cp = c;
162 if ((dot >= ARRMAX) || (dot < 0))
163 failed(name,subscript);
164 else
165 ap->adot = dot;
166 if (!attest (np, ARRAY))
167 if (dot == 0)
168 {
169 free((char *)ap);
170 return(np);
171 }
172 else if ((cp = valup (np)) != NULL)
173 {
174 nq = mak_nod (np->namid);
175 nq->value.namflg = np->value.namflg;
176 assign (nq, cp);
177 ap->val[0] = &nq->value;
178 }
179 if (dot > ap->maxi)
180 ap = growaray (ap, dot);
181 np->value.namval.aray = ap;
182 np->value.namflg |= ARRAY;
183 setdot (np, dot);
184 return(np);
185 }
186 }
187
188
189 /*
190 * skip to a matching ']' and return pointer to matched character
191 * routine assumes that you are sitting on the '['
192 */
193
bracket_match(string)194 char *bracket_match(string)
195 register char *string;
196 {
197 register int count = 1;
198 register int c;
199 while(count>0 && (c= *++string))
200 {
201 if(c=='[')
202 count++;
203 else if(c==']')
204 count--;
205 }
206 return(string);
207 }
208
209 /*
210 * _NAMP (NAME, ROOT, TYPE)
211 *
212 * char *NAME;
213 *
214 * struct Amemory *ROOT;
215 *
216 * int TYPE;
217 *
218 * Return a pointer to the Namnod in a linked list of
219 * Namnods (given by ROOT) whose namid is NAME. If TYPE
220 * is non-zero, a new Namnod with the given NAME will
221 * be inserted, if none is found.
222 *
223 * NAME should be of a form acceptable to chkid(III).
224 */
225
_namp(name,root,type)226 static struct Namnod *_namp(name,root,type)
227 char *name;
228 struct Namnod **root;
229 {
230 register char *cp,*sp;
231 register struct Namnod *np;
232 register struct Namnod *nq = NULL;
233 struct Namnod *rp = *root;
234
235 for(np=rp;np;nq=np,np=np->namnxt)
236 {
237 if((np->value.namflg&N_AVAIL)==0)
238 {
239 /* match even if np->name has an = in it */
240 cp = np->namid;
241 sp = name;
242 do
243 {
244 if(*sp==0)
245 {
246 if(*cp && *cp != '=')
247 break;
248 if(nq==NULL)
249 return(np);
250 nq->namnxt = np->namnxt;
251 np->namnxt = rp;
252 return(*root=np);
253 }
254 }
255 while(*sp++ == *cp++);
256 }
257 }
258 if(type==0)
259 return((struct Namnod*)NULL);
260 np = mak_nod(name);
261 np->namnxt = rp;
262 return(*root=np);
263 }
264
265 /*
266 * MAKNOD (NAME)
267 *
268 * char *NAME;
269 *
270 * Allocate a Namnod, setting its namid to NAME and its value
271 * to VALUE to NULL. A pointer to the allocated node is returned.
272 * NULL is returned if there is no space to be allocated
273 * for the Namnod.
274 *
275 * NAME should be of a form acceptable to chkid(III).
276 */
277
mak_nod(name)278 struct Namnod *mak_nod(name)
279 char *name;
280 {
281 register struct Namnod *np;
282 if((np=(struct Namnod *)malloc((unsigned)sizeof(struct Namnod)+strlen(name)+1)) == (struct Namnod*)NULL)
283 return(np);
284 np->namid = (char *)(np+1);
285 strcpy (np->namid, name);
286 np->value.namflg = N_DEFAULT;
287 np->value.namval.cp = NULL;
288 np->namnxt = NULL;
289 np->namsz = 0;
290 return(np);
291 }
292
293 #ifdef NAME_SCOPE
copy_nod(node,type)294 struct Namnod *copy_nod(node, type)
295 struct Namnod *node;
296 int type;
297 {
298 register struct Namnod *oldnp = node;
299 register struct Namnod *newnp;
300 register struct Amemory *rootp=namep;
301 char *cp;
302 while(rootp->nexttree)
303 rootp = rootp->nexttree; /* skip to last tree */
304 if(cp = index(node->namid,'='))
305 *cp = 0;
306 newnp = findnod(oldnp->namid,rootp,1);
307 if(cp)
308 *cp = '=';
309 if(type==0)
310 return(newnp);
311 oldnp->value.namflg &= ~C_WRITE;
312 newnp->value.namflg = oldnp->value.namflg&~(IN_DIR|N_FREE|N_ALLOC);
313 newnp->namid = oldnp->namid;
314 oldnp->value.namflg |= N_AVAIL;
315 if(attest(oldnp, ARRAY))
316 {
317 register struct Namaray *ap1,*ap2;
318 int dot;
319 char *val;
320 ap1 = arayp(oldnp);
321 dot = ap1->adot;
322 ap2 = growaray((struct Namaray*)0,ap1->maxi);
323 newnp->value.namval.aray = ap2;
324 for(ap1->adot=0;ap1->adot <= ap1->maxi;ap1->adot++)
325 if(val=valup(oldnp))
326 {
327 ap2->adot = ap1->adot;
328 assign(newnp,val);
329 }
330 ap2->adot = dot;
331 }
332 else if(type==2 )
333 assign(newnp,valup(oldnp));
334 return(newnp);
335 }
336 #endif /* NAME_SCOPE */
337