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