1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
15  * 3. Neither the name of the University nor the names of its contributors
35  * name or inode number. They also provide for creation, deletion,
62  * HASHFACTOR. The variable "entry" points to the hash table;
66 static struct entry **entry;  variable
69 static void		 addino(ino_t, struct entry *);
70 static struct entry	*lookupparent(char *);
71 static void		 removeentry(struct entry *);
74  * Look up an entry by inode number
76 struct entry *
79 	struct entry *ep;  in lookupino()
83 	for (ep = entry[inum % entrytblsize]; ep != NULL; ep = ep->e_next)  in lookupino()
84 		if (ep->e_ino == inum)  in lookupino()
90  * Add an entry into the entry table
93 addino(ino_t inum, struct entry *np)  in addino()
95 	struct entry **epp;  in addino()
99 	epp = &entry[inum % entrytblsize];  in addino()
100 	np->e_ino = inum;  in addino()
101 	np->e_next = *epp;  in addino()
104 		for (np = np->e_next; np != NULL; np = np->e_next)  in addino()
105 			if (np->e_ino == inum)  in addino()
110  * Delete an entry from the entry table
115 	struct entry *next;  in deleteino()
116 	struct entry **prev;  in deleteino()
120 	prev = &entry[inum % entrytblsize];  in deleteino()
121 	for (next = *prev; next != NULL; next = next->e_next) {  in deleteino()
122 		if (next->e_ino == inum) {  in deleteino()
123 			next->e_ino = 0;  in deleteino()
124 			*prev = next->e_next;  in deleteino()
127 		prev = &next->e_next;  in deleteino()
133  * Look up an entry by name
135 struct entry *
136 lookupname(char *name)  in lookupname()  argument
138 	struct entry *ep;  in lookupname()
142 	cp = name;  in lookupname()
143 	for (ep = lookupino(UFS_ROOTINO); ep != NULL; ep = ep->e_entries) {  in lookupname()
150 		for ( ; ep != NULL; ep = ep->e_sibling)  in lookupname()
151 			if (strcmp(ep->e_name, buf) == 0)  in lookupname()
164 static struct entry *
165 lookupparent(char *name)  in lookupparent()  argument
167 	struct entry *ep;  in lookupparent()
170 	tailindex = strrchr(name, '/');  in lookupparent()
174 	ep = lookupname(name);  in lookupparent()
178 	if (ep->e_type != NODE)  in lookupparent()
179 		panic("%s is not a directory\n", name);  in lookupparent()
187 myname(struct entry *ep)  in myname()
192 	for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {  in myname()
193 		cp -= ep->e_namlen;  in myname()
194 		memmove(cp, ep->e_name, (long)ep->e_namlen);  in myname()
197 		*(--cp) = '/';  in myname()
198 		ep = ep->e_parent;  in myname()
208 static struct entry *freelist = NULL;
211  * add an entry to the symbol table
213 struct entry *
214 addentry(char *name, ino_t inum, int type)  in addentry()  argument
216 	struct entry *np, *ep;  in addentry()
220 		freelist = np->e_next;  in addentry()
221 		memset(np, 0, (long)sizeof(struct entry));  in addentry()
223 		np = (struct entry *)calloc(1, sizeof(struct entry));  in addentry()
227 	np->e_type = type & ~LINK;  in addentry()
228 	ep = lookupparent(name);  in addentry()
231 			panic("bad name to addentry %s\n", name);  in addentry()
232 		np->e_name = savename(name);  in addentry()
233 		np->e_namlen = strlen(name);  in addentry()
234 		np->e_parent = np;  in addentry()
238 	np->e_name = savename(strrchr(name, '/') + 1);  in addentry()
239 	np->e_namlen = strlen(np->e_name);  in addentry()
240 	np->e_parent = ep;  in addentry()
241 	np->e_sibling = ep->e_entries;  in addentry()
242 	ep->e_entries = np;  in addentry()
246 			panic("link to non-existent name\n");  in addentry()
247 		np->e_ino = inum;  in addentry()
248 		np->e_links = ep->e_links;  in addentry()
249 		ep->e_links = np;  in addentry()
252 			panic("duplicate entry\n");  in addentry()
259  * delete an entry from the symbol table
262 freeentry(struct entry *ep)  in freeentry()
264 	struct entry *np;  in freeentry()
267 	if (ep->e_flags != REMOVED)  in freeentry()
269 	if (ep->e_type == NODE) {  in freeentry()
270 		if (ep->e_links != NULL)  in freeentry()
272 		if (ep->e_entries != NULL)  in freeentry()
273 			badentry(ep, "freeing non-empty directory");  in freeentry()
275 	if (ep->e_ino != 0) {  in freeentry()
276 		np = lookupino(ep->e_ino);  in freeentry()
280 			inum = ep->e_ino;  in freeentry()
282 			if (ep->e_links != NULL)  in freeentry()
283 				addino(inum, ep->e_links);  in freeentry()
285 			for (; np != NULL; np = np->e_links) {  in freeentry()
286 				if (np->e_links == ep) {  in freeentry()
287 					np->e_links = ep->e_links;  in freeentry()
296 	freename(ep->e_name);  in freeentry()
297 	ep->e_next = freelist;  in freeentry()
302  * Relocate an entry in the tree structure
305 moveentry(struct entry *ep, char *newname)  in moveentry()
307 	struct entry *np;  in moveentry()
313 	if (np != ep->e_parent) {  in moveentry()
315 		ep->e_parent = np;  in moveentry()
316 		ep->e_sibling = np->e_entries;  in moveentry()
317 		np->e_entries = ep;  in moveentry()
320 	freename(ep->e_name);  in moveentry()
321 	ep->e_name = savename(cp);  in moveentry()
322 	ep->e_namlen = strlen(cp);  in moveentry()
323 	if (strcmp(gentempname(ep), ep->e_name) == 0)  in moveentry()
324 		ep->e_flags |= TMPNAME;  in moveentry()
326 		ep->e_flags &= ~TMPNAME;  in moveentry()
330  * Remove an entry in the tree structure
333 removeentry(struct entry *ep)  in removeentry()
335 	struct entry *np;  in removeentry()
337 	np = ep->e_parent;  in removeentry()
338 	if (np->e_entries == ep) {  in removeentry()
339 		np->e_entries = ep->e_sibling;  in removeentry()
341 		for (np = np->e_entries; np != NULL; np = np->e_sibling) {  in removeentry()
342 			if (np->e_sibling == ep) {  in removeentry()
343 				np->e_sibling = ep->e_sibling;  in removeentry()
348 			badentry(ep, "cannot find entry in parent list");  in removeentry()
356  * of similar lengths can use the same entry. The value of STRTBLINCR
357  * is chosen so that every entry has at least enough space to hold
358  * a "struct strtbl" header. Thus every entry can be linked onto an
374  * Allocate space for a name. It first looks to see if it already
375  * has an appropriate sized entry, and if not allocates a new one.
378 savename(char *name)  in savename()  argument
384 	if (name == NULL)  in savename()
385 		panic("bad name\n");  in savename()
386 	len = strlen(name);  in savename()
389 		strtblhdr[len / STRTBLINCR].next = np->next;  in savename()
396 	(void) strcpy(cp, name);  in savename()
401  * Free space for a name. The resulting entry is linked onto the
405 freename(char *name)  in freename()  argument
409 	tp = &strtblhdr[strlen(name) / STRTBLINCR];  in freename()
410 	np = (struct strhdr *)name;  in freename()
411 	np->next = tp->next;  in freename()
412 	tp->next = np;  in freename()
434 	struct entry *ep, *tep;  in dumpsymtable()
436 	struct entry temp, *tentry;  in dumpsymtable()
452 	 * Assign indices to each entry  in dumpsymtable()
456 		for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {  in dumpsymtable()
457 			ep->e_index = mynum++;  in dumpsymtable()
458 			(void) fwrite(ep->e_name, sizeof(char),  in dumpsymtable()
459 			       (int)allocsize(ep->e_namlen), fd);  in dumpsymtable()
468 		for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {  in dumpsymtable()
469 			memmove(tep, ep, (long)sizeof(struct entry));  in dumpsymtable()
470 			tep->e_name = (char *)stroff;  in dumpsymtable()
471 			stroff += allocsize(ep->e_namlen);  in dumpsymtable()
472 			tep->e_parent = (struct entry *)ep->e_parent->e_index;  in dumpsymtable()
473 			if (ep->e_links != NULL)  in dumpsymtable()
474 				tep->e_links =  in dumpsymtable()
475 					(struct entry *)ep->e_links->e_index;  in dumpsymtable()
476 			if (ep->e_sibling != NULL)  in dumpsymtable()
477 				tep->e_sibling =  in dumpsymtable()
478 					(struct entry *)ep->e_sibling->e_index;  in dumpsymtable()
479 			if (ep->e_entries != NULL)  in dumpsymtable()
480 				tep->e_entries =  in dumpsymtable()
481 					(struct entry *)ep->e_entries->e_index;  in dumpsymtable()
482 			if (ep->e_next != NULL)  in dumpsymtable()
483 				tep->e_next =  in dumpsymtable()
484 					(struct entry *)ep->e_next->e_index;  in dumpsymtable()
485 			(void) fwrite((char *)tep, sizeof(struct entry), 1, fd);  in dumpsymtable()
489 	 * Convert entry pointers to indexes, and output  in dumpsymtable()
492 		if (entry[i] == NULL)  in dumpsymtable()
495 			tentry = (struct entry *)entry[i]->e_index;  in dumpsymtable()
496 		(void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);  in dumpsymtable()
522 	struct entry *ep;  in initsymtable()
523 	struct entry *baseep, *lep;  in initsymtable()
532 		entry = calloc((unsigned)entrytblsize, sizeof(struct entry *));  in initsymtable()
533 		if (entry == NULL)  in initsymtable()
534 			panic("no memory for entry table\n");  in initsymtable()
536 		ep->e_flags |= NEW;  in initsymtable()
547 	tblsize = stbuf.st_size - sizeof(struct symtableheader);  in initsymtable()
588 	entry = (struct entry **)  in initsymtable()
589 		(base + tblsize - (entrytblsize * sizeof(struct entry *)));  in initsymtable()
590 	baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));  in initsymtable()
591 	lep = (struct entry *)entry;  in initsymtable()
593 		if (entry[i] == NULL)  in initsymtable()
595 		entry[i] = &baseep[(long)entry[i]];  in initsymtable()
598 		ep->e_name = base + (long)ep->e_name;  in initsymtable()
599 		ep->e_parent = &baseep[(long)ep->e_parent];  in initsymtable()
600 		if (ep->e_sibling != NULL)  in initsymtable()
601 			ep->e_sibling = &baseep[(long)ep->e_sibling];  in initsymtable()
602 		if (ep->e_links != NULL)  in initsymtable()
603 			ep->e_links = &baseep[(long)ep->e_links];  in initsymtable()
604 		if (ep->e_entries != NULL)  in initsymtable()
605 			ep->e_entries = &baseep[(long)ep->e_entries];  in initsymtable()
606 		if (ep->e_next != NULL)  in initsymtable()
607 			ep->e_next = &baseep[(long)ep->e_next];  in initsymtable()