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 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 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 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 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 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