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 = wslen(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 = wslen(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) wsncpy(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) wscpy(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 }