1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21/*
22 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26
27/*
28 *	misc.cc
29 *
30 *	This file contains various unclassified routines. Some main groups:
31 *		getname
32 *		Memory allocation
33 *		String handling
34 *		Property handling
35 *		Error message handling
36 *		Make internal state dumping
37 *		main routine support
38 */
39
40/*
41 * Included files
42 */
43#include <bsd/bsd.h>		/* bsd_signal() */
44#include <mksh/i18n.h>		/* get_char_semantics_value() */
45#include <mksh/misc.h>
46#include <stdarg.h>		/* va_list, va_start(), va_end() */
47#include <stdlib.h>		/* mbstowcs() */
48#include <sys/signal.h>		/* SIG_DFL */
49#include <sys/wait.h>		/* wait() */
50
51#include <string.h>		/* strerror() */
52#include <libintl.h>
53
54
55/*
56 * Defined macros
57 */
58
59/*
60 * typedefs & structs
61 */
62
63/*
64 * Static variables
65 */
66extern "C" {
67	void		(*sigivalue)(int) = SIG_DFL;
68	void		(*sigqvalue)(int) = SIG_DFL;
69	void		(*sigtvalue)(int) = SIG_DFL;
70	void		(*sighvalue)(int) = SIG_DFL;
71}
72
73long	getname_bytes_count = 0;
74long	getname_names_count = 0;
75long	getname_struct_count = 0;
76
77long	freename_bytes_count = 0;
78long	freename_names_count = 0;
79long	freename_struct_count = 0;
80
81long	expandstring_count = 0;
82long	getwstring_count = 0;
83
84/*
85 * File table of contents
86 */
87static void	expand_string(register String string, register int length);
88
89#define	FATAL_ERROR_MSG_SIZE 200
90
91/*
92 *	getmem(size)
93 *
94 *	malloc() version that checks the returned value.
95 *
96 *	Return value:
97 *				The memory chunk we allocated
98 *
99 *	Parameters:
100 *		size		The size of the chunk we need
101 *
102 *	Global variables used:
103 */
104char *
105getmem(size_t size)
106{
107	char *result = (char *)malloc(size);
108	if (result == NULL) {
109		(void) fprintf(stderr, "*** Error: malloc(%d) failed: %s\n%s",
110		    size, strerror(errno),
111		    gettext("mksh: Fatal error: Out of memory\n"));
112		exit(1);
113	}
114	return (result);
115}
116
117/*
118 *	retmem(p)
119 *
120 *	Cover funtion for free() to make it possible to insert advises.
121 *
122 *	Parameters:
123 *		p		The memory block to free
124 *
125 *	Global variables used:
126 */
127void
128retmem(wchar_t *p)
129{
130	(void) free((char *) p);
131}
132
133void
134retmem_mb(caddr_t p)
135{
136	(void) free(p);
137}
138
139/*
140 *	getname_fn(name, len, dont_enter)
141 *
142 *	Hash a name string to the corresponding nameblock.
143 *
144 *	Return value:
145 *				The Name block for the string
146 *
147 *	Parameters:
148 *		name		The string we want to internalize
149 *		len		The length of that string
150 *		dont_enter	Don't enter the name if it does not exist
151 *
152 *	Global variables used:
153 *		funny		The vector of semantic tags for characters
154 *		hashtab		The hashtable used for the nametable
155 */
156Name
157getname_fn(wchar_t *name, register int len, register Boolean dont_enter, register Boolean * foundp)
158{
159	register int		length;
160	register wchar_t	*cap = name;
161	register Name		np;
162	static Name_rec		empty_Name;
163	char			*tmp_mbs_buffer = NULL;
164	char			*mbs_name = mbs_buffer;
165
166	/*
167	 * First figure out how long the string is.
168	 * If the len argument is -1 we count the chars here.
169	 */
170	if (len == FIND_LENGTH) {
171		length = wcslen(name);
172	} else {
173		length = len;
174	}
175
176	Wstring ws;
177	ws.init(name, length);
178	if (length >= MAXPATHLEN) {
179		mbs_name = tmp_mbs_buffer = getmem((length * MB_LEN_MAX) + 1);
180	}
181	(void) wcstombs(mbs_name, ws.get_string(), (length * MB_LEN_MAX) + 1);
182
183	/* Look for the string */
184	if (dont_enter || (foundp != 0)) {
185		np = hashtab.lookup(mbs_name);
186		if (foundp != 0) {
187			*foundp = (np != 0) ? true : false;
188		}
189		if ((np != 0) || dont_enter) {
190			if(tmp_mbs_buffer != NULL) {
191				retmem_mb(tmp_mbs_buffer);
192			}
193			return np;
194		} else {
195			np = ALLOC(Name);
196		}
197	} else {
198		Boolean found;
199		np = hashtab.insert(mbs_name, found);
200		if (found) {
201			if(tmp_mbs_buffer != NULL) {
202				retmem_mb(tmp_mbs_buffer);
203			}
204			return np;
205		}
206	}
207	getname_struct_count += sizeof(struct _Name);
208	*np = empty_Name;
209
210	np->string_mb = strdup(mbs_name);
211	if(tmp_mbs_buffer != NULL) {
212		retmem_mb(tmp_mbs_buffer);
213		mbs_name = tmp_mbs_buffer = NULL;
214	}
215	getname_bytes_count += strlen(np->string_mb) + 1;
216	/* Fill in the new Name */
217	np->stat.time = file_no_time;
218	np->hash.length = length;
219	/* Scan the namestring to classify it */
220	for (cap = name, len = 0; --length >= 0;) {
221		len |= get_char_semantics_value(*cap++);
222	}
223	np->dollar = BOOLEAN((len & (int) dollar_sem) != 0);
224	np->meta = BOOLEAN((len & (int) meta_sem) != 0);
225	np->percent = BOOLEAN((len & (int) percent_sem) != 0);
226	np->wildcard = BOOLEAN((len & (int) wildcard_sem) != 0);
227	np->colon = BOOLEAN((len & (int) colon_sem) != 0);
228	np->parenleft = BOOLEAN((len & (int) parenleft_sem) != 0);
229	getname_names_count++;
230	return np;
231}
232
233void
234store_name(Name name)
235{
236	hashtab.insert(name);
237}
238
239void
240free_name(Name name)
241{
242	freename_names_count++;
243	freename_struct_count += sizeof(struct _Name);
244	freename_bytes_count += strlen(name->string_mb) + 1;
245	retmem_mb(name->string_mb);
246	for (Property next, p = name->prop; p != NULL; p = next) {
247		next = p->next;
248		free(p);
249	}
250	free(name);
251}
252
253/*
254 *	enable_interrupt(handler)
255 *
256 *	This routine sets a new interrupt handler for the signals make
257 *	wants to deal with.
258 *
259 *	Parameters:
260 *		handler		The function installed as interrupt handler
261 *
262 *	Static variables used:
263 *		sigivalue	The original signal handler
264 *		sigqvalue	The original signal handler
265 *		sigtvalue	The original signal handler
266 *		sighvalue	The original signal handler
267 */
268void
269enable_interrupt(register void (*handler) (int))
270{
271	if (sigivalue != SIG_IGN) {
272		(void) bsd_signal(SIGINT, (SIG_PF) handler);
273	}
274	if (sigqvalue != SIG_IGN) {
275		(void) bsd_signal(SIGQUIT, (SIG_PF) handler);
276	}
277	if (sigtvalue != SIG_IGN) {
278		(void) bsd_signal(SIGTERM, (SIG_PF) handler);
279	}
280	if (sighvalue != SIG_IGN) {
281		(void) bsd_signal(SIGHUP, (SIG_PF) handler);
282	}
283}
284
285/*
286 *	setup_char_semantics()
287 *
288 *	Load the vector char_semantics[] with lexical markers
289 *
290 *	Parameters:
291 *
292 *	Global variables used:
293 *		char_semantics	The vector of character semantics that we set
294 */
295void
296setup_char_semantics(void)
297{
298	const char	*s;
299	wchar_t		wc_buffer[1];
300	int		entry;
301
302	if (svr4) {
303		s = "@-";
304	} else {
305		s = "=@-?!+";
306	}
307	for (s; MBTOWC(wc_buffer, s); s++) {
308		entry = get_char_semantics_entry(*wc_buffer);
309		char_semantics[entry] |= (int) command_prefix_sem;
310	}
311	char_semantics[dollar_char_entry] |= (int) dollar_sem;
312	for (s = "#|=^();&<>*?[]:$`'\"\\\n"; MBTOWC(wc_buffer, s); s++) {
313		entry = get_char_semantics_entry(*wc_buffer);
314		char_semantics[entry] |= (int) meta_sem;
315	}
316	char_semantics[percent_char_entry] |= (int) percent_sem;
317	for (s = "@*<%?^"; MBTOWC(wc_buffer, s); s++) {
318		entry = get_char_semantics_entry(*wc_buffer);
319		char_semantics[entry] |= (int) special_macro_sem;
320	}
321	for (s = "?[*"; MBTOWC(wc_buffer, s); s++) {
322		entry = get_char_semantics_entry(*wc_buffer);
323		char_semantics[entry] |= (int) wildcard_sem;
324	}
325	char_semantics[colon_char_entry] |= (int) colon_sem;
326	char_semantics[parenleft_char_entry] |= (int) parenleft_sem;
327}
328
329/*
330 *	errmsg(errnum)
331 *
332 *	Return the error message for a system call error
333 *
334 *	Return value:
335 *				An error message string
336 *
337 *	Parameters:
338 *		errnum		The number of the error we want to describe
339 */
340char *
341errmsg(int errnum)
342{
343	char *msg;
344	char *errbuf;
345
346	errno = 0;
347	msg = strerror(errnum);
348	if (errno == EINVAL) {
349		size_t size = 6 + 1 + 11 + 1;
350		errbuf = getmem(size);
351		(void) snprintf(errbuf, size, gettext("Error %d"), errnum);
352		return (errbuf);
353	}
354	return (msg);
355}
356
357static char static_buf[MAXPATHLEN*3];
358
359/*
360 *	fatal_mksh(format, args...)
361 *
362 *	Print a message and die
363 *
364 *	Parameters:
365 *		format		printf type format string
366 *		args		Arguments to match the format
367 */
368/*VARARGS*/
369void
370fatal_mksh(const char *message, ...)
371{
372	va_list args;
373	char    *buf = static_buf;
374	char	*mksh_fat_err = gettext("mksh: Fatal error: ");
375	char	*cur_wrk_dir = gettext("Current working directory: ");
376	int	mksh_fat_err_len = strlen(mksh_fat_err);
377
378	va_start(args, message);
379	(void) fflush(stdout);
380	(void) strcpy(buf, mksh_fat_err);
381	size_t buf_len = vsnprintf(static_buf + mksh_fat_err_len,
382				   sizeof(static_buf) - mksh_fat_err_len,
383				   message, args)
384			+ mksh_fat_err_len
385			+ strlen(cur_wrk_dir)
386			+ strlen(get_current_path_mksh())
387			+ 3; // "\n\n"
388	va_end(args);
389	if (buf_len >= sizeof(static_buf)) {
390		buf = getmem(buf_len);
391		(void) strcpy(buf, mksh_fat_err);
392		va_start(args, message);
393		(void) vsprintf(buf + mksh_fat_err_len, message, args);
394		va_end(args);
395	}
396	(void) strcat(buf, "\n");
397/*
398	if (report_pwd) {
399 */
400	if (1) {
401		(void) strcat(buf, cur_wrk_dir);
402		(void) strcat(buf, get_current_path_mksh());
403		(void) strcat(buf, "\n");
404	}
405	(void) fputs(buf, stderr);
406	(void) fflush(stderr);
407	if (buf != static_buf) {
408		retmem_mb(buf);
409	}
410	exit_status = 1;
411	exit(1);
412}
413
414/*
415 *	fatal_reader_mksh(format, args...)
416 *
417 *	Parameters:
418 *		format		printf style format string
419 *		args		arguments to match the format
420 */
421/*VARARGS*/
422void
423fatal_reader_mksh(const char * pattern, ...)
424{
425	va_list args;
426	char	message[1000];
427
428	va_start(args, pattern);
429/*
430	if (file_being_read != NULL) {
431		WCSTOMBS(mbs_buffer, file_being_read);
432		if (line_number != 0) {
433			(void) sprintf(message,
434				       gettext("%s, line %d: %s"),
435				       mbs_buffer,
436				       line_number,
437				       pattern);
438		} else {
439			(void) sprintf(message,
440				       "%s: %s",
441				       mbs_buffer,
442				       pattern);
443		}
444		pattern = message;
445	}
446 */
447
448	(void) fflush(stdout);
449	(void) fprintf(stderr, gettext("mksh: Fatal error in reader: "));
450	(void) vfprintf(stderr, pattern, args);
451	(void) fprintf(stderr, "\n");
452	va_end(args);
453
454/*
455	if (temp_file_name != NULL) {
456		(void) fprintf(stderr,
457			       gettext("mksh: Temp-file %s not removed\n"),
458			       temp_file_name->string_mb);
459		temp_file_name = NULL;
460	}
461 */
462
463/*
464	if (report_pwd) {
465 */
466	if (1) {
467		(void) fprintf(stderr,
468			       gettext("Current working directory %s\n"),
469			       get_current_path_mksh());
470	}
471	(void) fflush(stderr);
472	exit_status = 1;
473	exit(1);
474}
475
476/*
477 *	warning_mksh(format, args...)
478 *
479 *	Print a message and continue.
480 *
481 *	Parameters:
482 *		format		printf type format string
483 *		args		Arguments to match the format
484 */
485/*VARARGS*/
486void
487warning_mksh(char * message, ...)
488{
489	va_list args;
490
491	va_start(args, message);
492	(void) fflush(stdout);
493	(void) fprintf(stderr, gettext("mksh: Warning: "));
494	(void) vfprintf(stderr, message, args);
495	(void) fprintf(stderr, "\n");
496	va_end(args);
497/*
498	if (report_pwd) {
499 */
500	if (1) {
501		(void) fprintf(stderr,
502			       gettext("Current working directory %s\n"),
503			       get_current_path_mksh());
504	}
505	(void) fflush(stderr);
506}
507
508/*
509 *	get_current_path_mksh()
510 *
511 *	Stuff current_path with the current path if it isnt there already.
512 *
513 *	Parameters:
514 *
515 *	Global variables used:
516 */
517char *
518get_current_path_mksh(void)
519{
520	char			pwd[(MAXPATHLEN * MB_LEN_MAX)];
521	static char		*current_path;
522
523	if (current_path == NULL) {
524		getcwd(pwd, sizeof(pwd));
525		if (pwd[0] == (int) nul_char) {
526			pwd[0] = (int) slash_char;
527			pwd[1] = (int) nul_char;
528		}
529		current_path = strdup(pwd);
530	}
531	return current_path;
532}
533
534/*
535 *	append_prop(target, type)
536 *
537 *	Create a new property and append it to the property list of a Name.
538 *
539 *	Return value:
540 *				A new property block for the target
541 *
542 *	Parameters:
543 *		target		The target that wants a new property
544 *		type		The type of property being requested
545 *
546 *	Global variables used:
547 */
548Property
549append_prop(register Name target, register Property_id type)
550{
551	register Property	*insert = &target->prop;
552	register Property	prop = *insert;
553	register int		size;
554
555	switch (type) {
556	case conditional_prop:
557		size = sizeof (struct Conditional);
558		break;
559	case line_prop:
560		size = sizeof (struct Line);
561		break;
562	case macro_prop:
563		size = sizeof (struct _Macro);
564		break;
565	case makefile_prop:
566		size = sizeof (struct Makefile);
567		break;
568	case member_prop:
569		size = sizeof (struct Member);
570		break;
571	case recursive_prop:
572		size = sizeof (struct Recursive);
573		break;
574	case sccs_prop:
575		size = sizeof (struct Sccs);
576		break;
577	case suffix_prop:
578		size = sizeof (struct Suffix);
579		break;
580	case target_prop:
581		size = sizeof (struct Target);
582		break;
583	case time_prop:
584		size = sizeof (struct STime);
585		break;
586	case vpath_alias_prop:
587		size = sizeof (struct Vpath_alias);
588		break;
589	case long_member_name_prop:
590		size = sizeof (struct Long_member_name);
591		break;
592	case macro_append_prop:
593		size = sizeof (struct _Macro_appendix);
594		break;
595	case env_mem_prop:
596		size = sizeof (struct _Env_mem);
597		break;
598	default:
599		fatal_mksh(gettext("Internal error. Unknown prop type %d"), type);
600	}
601	for (; prop != NULL; insert = &prop->next, prop = *insert);
602	size += PROPERTY_HEAD_SIZE;
603	*insert = prop = (Property) getmem(size);
604	memset((char *) prop, 0, size);
605	prop->type = type;
606	prop->next = NULL;
607	return prop;
608}
609
610/*
611 *	maybe_append_prop(target, type)
612 *
613 *	Append a property to the Name if none of this type exists
614 *	else return the one already there
615 *
616 *	Return value:
617 *				A property of the requested type for the target
618 *
619 *	Parameters:
620 *		target		The target that wants a new property
621 *		type		The type of property being requested
622 *
623 *	Global variables used:
624 */
625Property
626maybe_append_prop(register Name target, register Property_id type)
627{
628	register Property	prop;
629
630	if ((prop = get_prop(target->prop, type)) != NULL) {
631		return prop;
632	}
633	return append_prop(target, type);
634}
635
636/*
637 *	get_prop(start, type)
638 *
639 *	Scan the property list of a Name to find the next property
640 *	of a given type.
641 *
642 *	Return value:
643 *				The first property of the type, if any left
644 *
645 *	Parameters:
646 *		start		The first property block to check for type
647 *		type		The type of property block we need
648 *
649 *	Global variables used:
650 */
651Property
652get_prop(register Property start, register Property_id type)
653{
654	for (; start != NULL; start = start->next) {
655		if (start->type == type) {
656			return start;
657		}
658	}
659	return NULL;
660}
661
662/*
663 *	append_string(from, to, length)
664 *
665 *	Append a C string to a make string expanding it if nessecary
666 *
667 *	Parameters:
668 *		from		The source (C style) string
669 *		to		The destination (make style) string
670 *		length		The length of the from string
671 *
672 *	Global variables used:
673 */
674void
675append_string(register wchar_t *from, register String to, register int length)
676{
677	if (length == FIND_LENGTH) {
678		length = wcslen(from);
679	}
680	if (to->buffer.start == NULL) {
681		expand_string(to, 32 + length);
682	}
683	if (to->buffer.end - to->text.p <= length) {
684		expand_string(to,
685			      (to->buffer.end - to->buffer.start) * 2 +
686			      length);
687	}
688	if (length > 0) {
689		(void) wcsncpy(to->text.p, from, length);
690		to->text.p += length;
691	}
692	*(to->text.p) = (int) nul_char;
693}
694
695wchar_t * get_wstring(char *from) {
696	if(from == NULL) {
697		return NULL;
698	}
699	getwstring_count++;
700	wchar_t * wcbuf = ALLOC_WC(strlen(from) + 1);
701	mbstowcs(wcbuf, from, strlen(from)+1);
702	return wcbuf;
703}
704
705void
706append_string(register char *from, register String to, register int length)
707{
708	if (length == FIND_LENGTH) {
709		length = strlen(from);
710	}
711	if (to->buffer.start == NULL) {
712		expand_string(to, 32 + length);
713	}
714	if (to->buffer.end - to->text.p <= length) {
715		expand_string(to,
716			      (to->buffer.end - to->buffer.start) * 2 +
717			      length);
718	}
719	if (length > 0) {
720		(void) mbstowcs(to->text.p, from, length);
721		to->text.p += length;
722	}
723	*(to->text.p) = (int) nul_char;
724}
725
726/*
727 *	expand_string(string, length)
728 *
729 *	Allocate more memory for strings that run out of space.
730 *
731 *	Parameters:
732 *		string		The make style string we want to expand
733 *		length		The new length we need
734 *
735 *	Global variables used:
736 */
737static void
738expand_string(register String string, register int length)
739{
740	register wchar_t	*p;
741
742	if (string->buffer.start == NULL) {
743		/* For strings that have no memory allocated */
744		string->buffer.start =
745		  string->text.p =
746		    string->text.end =
747		      ALLOC_WC(length);
748		string->buffer.end = string->buffer.start + length;
749		string->text.p[0] = (int) nul_char;
750		string->free_after_use = true;
751		expandstring_count++;
752		return;
753	}
754	if (string->buffer.end - string->buffer.start >= length) {
755		/* If we really don't need more memory. */
756		return;
757	}
758	/*
759	 * Get more memory, copy the string and free the old buffer if
760	 * it is was malloc()'ed.
761	 */
762	expandstring_count++;
763	p = ALLOC_WC(length);
764	(void) wcscpy(p, string->buffer.start);
765	string->text.p = p + (string->text.p - string->buffer.start);
766	string->text.end = p + (string->text.end - string->buffer.start);
767	string->buffer.end = p + length;
768	if (string->free_after_use) {
769		retmem(string->buffer.start);
770	}
771	string->buffer.start = p;
772	string->free_after_use = true;
773}
774
775/*
776 *	append_char(from, to)
777 *
778 *	Append one char to a make string expanding it if nessecary
779 *
780 *	Parameters:
781 *		from		Single character to append to string
782 *		to		The destination (make style) string
783 *
784 *	Global variables used:
785 */
786void
787append_char(wchar_t from, register String to)
788{
789	if (to->buffer.start == NULL) {
790		expand_string(to, 32);
791	}
792	if (to->buffer.end - to->text.p <= 2) {
793		expand_string(to, to->buffer.end - to->buffer.start + 32);
794	}
795	*(to->text.p)++ = from;
796	*(to->text.p) = (int) nul_char;
797}
798
799/*
800 *	handle_interrupt_mksh()
801 *
802 *	This is where C-C traps are caught.
803 */
804void
805handle_interrupt_mksh(int)
806{
807	(void) fflush(stdout);
808	/* Make sure the processes running under us terminate first. */
809	if (childPid > 0) {
810		kill(childPid, SIGTERM);
811		childPid = -1;
812	}
813	while (wait((int *) NULL) != -1);
814	exit_status = 2;
815	exit(2);
816}
817
818/*
819 *	setup_interrupt()
820 *
821 *	This routine saves the original interrupt handler pointers
822 *
823 *	Parameters:
824 *
825 *	Static variables used:
826 *		sigivalue	The original signal handler
827 *		sigqvalue	The original signal handler
828 *		sigtvalue	The original signal handler
829 *		sighvalue	The original signal handler
830 */
831void
832setup_interrupt(register void (*handler) (int))
833{
834	sigivalue = bsd_signal(SIGINT, SIG_IGN);
835	sigqvalue = bsd_signal(SIGQUIT, SIG_IGN);
836	sigtvalue = bsd_signal(SIGTERM, SIG_IGN);
837	sighvalue = bsd_signal(SIGHUP, SIG_IGN);
838	enable_interrupt(handler);
839}
840
841
842void
843mbstowcs_with_check(wchar_t *pwcs, const char *s, size_t n)
844{
845	if(mbstowcs(pwcs, s, n) == -1) {
846		fatal_mksh(gettext("The string `%s' is not valid in current locale"), s);
847	}
848}
849
850
851
852Wstring::Wstring()
853{
854	INIT_STRING_FROM_STACK(string, string_buf);
855}
856
857Wstring::Wstring(struct _Name * name)
858{
859	INIT_STRING_FROM_STACK(string, string_buf);
860	append_string(name->string_mb, &string, name->hash.length);
861}
862
863Wstring::~Wstring()
864{
865	if(string.free_after_use) {
866		retmem(string.buffer.start);
867	}
868}
869
870void
871Wstring::init(struct _Name * name)
872{
873	if(string.free_after_use) {
874		retmem(string.buffer.start);
875	}
876	INIT_STRING_FROM_STACK(string, string_buf);
877	append_string(name->string_mb, &string, name->hash.length);
878}
879
880void
881Wstring::init(wchar_t * name, unsigned length)
882{
883	INIT_STRING_FROM_STACK(string, string_buf);
884	append_string(name, &string, length);
885	string.buffer.start[length] = 0;
886}
887
888Boolean
889Wstring::equaln(wchar_t * str, unsigned length)
890{
891	return (Boolean)IS_WEQUALN(string.buffer.start, str, length);
892}
893
894Boolean
895Wstring::equaln(Wstring * str, unsigned length)
896{
897	return (Boolean)IS_WEQUALN(string.buffer.start, str->string.buffer.start, length);
898}
899
900Boolean
901Wstring::equal(wchar_t * str, unsigned off, unsigned length)
902{
903	return (Boolean)IS_WEQUALN(string.buffer.start + off, str, length);
904}
905
906Boolean
907Wstring::equal(wchar_t * str, unsigned off)
908{
909	return (Boolean)IS_WEQUAL(string.buffer.start + off, str);
910}
911
912Boolean
913Wstring::equal(wchar_t * str)
914{
915	return equal(str, 0);
916}
917
918Boolean
919Wstring::equal(Wstring * str, unsigned off, unsigned length)
920{
921	return (Boolean)IS_WEQUALN(string.buffer.start + off, str->string.buffer.start, length);
922}
923
924Boolean
925Wstring::equal(Wstring * str)
926{
927	return equal(str, 0);
928}
929
930Boolean
931Wstring::equal(Wstring * str, unsigned off)
932{
933	return (Boolean)IS_WEQUAL(string.buffer.start + off, str->string.buffer.start);
934}
935
936void
937Wstring::append_to_str(struct _String * str, unsigned off, unsigned length)
938{
939	append_string(string.buffer.start + off, str, length);
940}
941
942Name
943Name_set::lookup(const char *key)
944{
945	for (entry *node = root; node != 0;) {
946		int res = strcmp(key, node->name->string_mb);
947		if (res < 0) {
948			node = node->left;
949		} else if (res > 0) {
950			node = node->right;
951		} else {
952			return node->name;
953		}
954	}
955	return 0;
956}
957
958Name
959Name_set::insert(const char *key, Boolean &found)
960{
961	Name	name = 0;
962
963	if (root != 0) {
964		for (entry *node = root; name == 0;) {
965			int res = strcmp(key, node->name->string_mb);
966			if (res < 0) {
967				if (node->left != 0) {
968					node = node->left;
969				} else {
970					found = false;
971					name = ALLOC(Name);
972
973					node->left = new entry(name, node);
974					rebalance(node);
975				}
976			} else if (res > 0) {
977				if (node->right != 0) {
978					node = node->right;
979				} else {
980					found = false;
981					name = ALLOC(Name);
982
983					node->right = new entry(name, node);
984					rebalance(node);
985				}
986			} else {
987				found = true;
988				name = node->name;
989			}
990		}
991	} else {
992		found = false;
993		name = ALLOC(Name);
994
995		root = new entry(name, 0);
996	}
997	return name;
998}
999
1000void
1001Name_set::insert(Name name) {
1002	if (root != 0) {
1003		for (entry *node = root;;) {
1004			int res = strcmp(name->string_mb, node->name->string_mb);
1005			if (res < 0) {
1006				if (node->left != 0) {
1007					node = node->left;
1008				} else {
1009					node->left = new entry(name, node);
1010					rebalance(node);
1011					break;
1012				}
1013			} else if (res > 0) {
1014				if (node->right != 0) {
1015					node = node->right;
1016				} else {
1017					node->right = new entry(name, node);
1018					rebalance(node);
1019					break;
1020				}
1021			} else {
1022				// should be an error: inserting already existing name
1023				break;
1024			}
1025		}
1026	} else {
1027		root = new entry(name, 0);
1028	}
1029}
1030
1031void
1032Name_set::rebalance(Name_set::entry *node) {
1033	for (; node != 0; node = node->parent) {
1034		entry *right = node->right;
1035		entry *left = node->left;
1036
1037		unsigned rdepth = (right != 0) ? right->depth : 0;
1038		unsigned ldepth = (left != 0) ? left->depth : 0;
1039
1040		if (ldepth > rdepth + 1) {
1041			if ((node->left = left->right) != 0) {
1042				left->right->parent = node;
1043			}
1044			if ((left->parent = node->parent) != 0) {
1045				if (node == node->parent->right) {
1046					node->parent->right = left;
1047				} else {
1048					node->parent->left = left;
1049				}
1050			} else {
1051				root = left;
1052			}
1053			left->right = node;
1054			node->parent = left;
1055
1056			node->setup_depth();
1057			node = left;
1058		} else if (rdepth > ldepth + 1) {
1059			if ((node->right = right->left) != 0) {
1060				right->left->parent = node;
1061			}
1062			if ((right->parent = node->parent) != 0) {
1063				if (node == node->parent->right) {
1064					node->parent->right = right;
1065				} else {
1066					node->parent->left = right;
1067				}
1068			} else {
1069				root = right;
1070			}
1071			right->left = node;
1072			node->parent = right;
1073
1074			node->setup_depth();
1075			node = right;
1076		}
1077		node->setup_depth();
1078	}
1079}
1080
1081Name_set::iterator
1082Name_set::begin() const {
1083	for (entry *node = root; node != 0; node = node->left) {
1084		if (node->left == 0) {
1085			return iterator(node);
1086		}
1087	}
1088	return iterator();
1089}
1090
1091Name_set::iterator&
1092Name_set::iterator::operator++() {
1093	if (node != 0) {
1094		if (node->right != 0) {
1095			node = node->right;
1096			while (node->left != 0) {
1097				node = node->left;
1098			}
1099		} else {
1100			while ((node->parent != 0) && (node->parent->right == node)) {
1101				node = node->parent;
1102			}
1103			node = node->parent;
1104		}
1105	}
1106	return *this;
1107}
1108