These are the windows fixes that I previously alluded to, combined with
[dyninst.git] / common / src / String.C
1 /*
2  * Copyright (c) 1996-2007 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
30  */
31
32
33 // $Id: String.C,v 1.37 2008/05/09 00:25:38 jaw Exp $
34
35 #include <assert.h>
36 #include "common/h/headers.h"
37
38 #if !defined(os_windows)
39 #include <regex.h>
40 #endif
41
42 #include "common/h/String.h"
43
44 // Declare static member vrbles:
45 pdstring *pdstring::nilptr = NULL;
46 long pdstring::nilptr_initialized = 0;
47 int string_counter::count = 0;
48 string_counter sc;
49
50 /* This doesn't actually belong here. */
51 void dedemangle( const char * demangled, char * result ) {
52    /* Lifted from Jeffrey Odom.  Code reformatted so
53       I could figure out how to eliminate compiler warnings.
54       Adjusted to handle spaces inside templates intelligently.
55       We cut off everything after the first l-paren, so we don't
56       need to worry about the space after the parameters but
57       before the 'const'. */
58    const char * resultBegins = NULL;
59    char * resultEnds = NULL;
60    
61    if ( demangled[0] == '(' &&
62         strstr( demangled, "::" ) != NULL) {
63       /* Local variable.  Strip off the opening ( :: ). */
64       resultBegins = strrchr( demangled, ')' ) + 3;
65       
66       /* End it at the right-most space, if any. */
67       resultEnds = strrchr( resultBegins, ' ' );
68       if( resultEnds != NULL ) { * resultEnds = '\0'; }
69    }
70    else if ( strrchr( demangled, '(' ) != NULL ) {
71       /* Strip off return types, if any.  Be careful not to
72          pull off [template?/]class/namespace information.
73          
74          The only space that matters is the one that's _not_
75          inside a template, so skip the templates and cut at the
76          first space.  We can ignore 'operator[<[<]|>[>]]' because
77          we'll stop before we reach it.
78          
79          Caveat: conversion operators (e.g., "operator bool") have
80          spaces in the function name.  Right now we deal with this
81          specifically (is the function "operator *"?).  Could be
82          altered to after the last template but before the last
83          left parenthesis.  (Instead of next, for "operator ()".)
84       */
85
86       resultBegins = demangled;
87       int stack = 0; bool inTemplate = false;
88       unsigned int offset, start_template_offset=0, stop_template_offset=0;
89       int lastColon = 0;
90       for( offset = 0; offset < strlen( resultBegins ); offset++ ) {
91          if( resultBegins[offset] == '<' ) {
92             stack++;
93             inTemplate = true;
94             if(stack == 1)
95                start_template_offset = offset;
96          }
97          else if( resultBegins[offset] == '>' ) {
98             stack--;
99             if( stack == 0 ) { 
100                inTemplate = false;
101                stop_template_offset = offset;
102             }
103          }
104          else if( !inTemplate && resultBegins[offset] == '(' ) {
105             /* We've stumbled on something without a return value. */
106
107 #ifdef os_solaris
108             /* ptr return types for native compiler don't seem to have a space
109                before the start of the func name (e.g. void*func_name(void*) ).
110
111                need to find last asterick before '(' and see if it's within
112                a template area. if not, then set resultBegins to next offset.
113             */
114             char *prefix = (char*)malloc(strlen(demangled));
115             if(prefix != NULL) {
116                strncpy(prefix, demangled, offset+1); 
117                prefix[offset+1] = '\0';
118                char *last_ast = strrchr(prefix, '*');            
119                if( last_ast != NULL ) {
120                   unsigned last_ast_off = last_ast - prefix;
121                   if( stop_template_offset ) {
122                      if( last_ast_off > start_template_offset &&
123                          last_ast_off < stop_template_offset ) {
124                         // last '*' is in template, no return type
125                         offset = 0;
126                         resultBegins = demangled;
127                         free(prefix);
128                         break;
129                      }
130                   }
131                   // not in template, so last '*' must be end of return type
132                   resultBegins = demangled + last_ast_off + 1;
133                   offset = last_ast_off + 1;
134                   free(prefix);
135                   break;
136                }
137             }
138             // no '*', is actually no return type function
139             offset = 0;
140             resultBegins = demangled;
141 #else
142             offset = 0;
143             resultBegins = demangled;
144 #endif
145             break;
146          }
147          else if( !inTemplate && resultBegins[offset] == ' ' ) {
148             /* FIXME: verify that the space isn't in the function name,
149                e.g., 'operator bool'.  If the first space we meet _is_
150                a function name, it doesn't have a(n explicit) return type. */
151             if( strstr( &(resultBegins[ lastColon + 1 ]), "operator " ) == resultBegins + lastColon + 1 ) {
152                resultBegins = demangled;
153                offset = 0;
154             }
155             else {
156                resultBegins = &(resultBegins[offset + 1]);
157                offset++;
158             }
159             
160             break;
161          }
162          else if( !inTemplate && resultBegins[offset] == ':' ) {
163             lastColon = offset;
164          }
165       } /* end template elimination loop */
166
167       /* Scan past the function name; the first left parenthesis
168          not in in a template declaration starts the function arguments. */
169       stack = 0; inTemplate = false;
170       for( ; offset < strlen( resultBegins ); offset++ ) {
171          if( resultBegins[offset] == '<' ) {
172             stack++;
173             inTemplate = true;
174          }
175          if( resultBegins[offset] == '>' ) {
176             stack--;
177             if( stack == 0 ) { inTemplate = false; }
178          }
179          if( !inTemplate && resultBegins[offset] == '(' ) {
180             resultEnds = const_cast<char *>(&(resultBegins[offset]));
181             * resultEnds = '\0';
182             break;
183          } 
184       } /* end template elimination loop */
185    } /* end if a function prototype */
186    else {
187       /* Assume demangle OK. */
188       resultBegins = demangled;
189    }
190    
191    strcpy( result, resultBegins );
192 } /* end dedemangle */
193
194
195 string_ll::string_ll()
196     : str_(0), len_(0), key_(0) {
197 }
198
199 string_ll::string_ll(const char* str)
200 {
201    str_ = str ? STRDUP(str) : NULL;
202    len_ = str ? STRLEN(str) : 0;
203    key_ = 0; // lazy key define
204 }
205
206 string_ll::string_ll(const char *str, unsigned len) {
207    // same as above constructor, but copies less than the entire string.
208    // You specifiy the # of chars to copy.
209    if (len > strlen(str))
210       // just copy the whole string
211       len = strlen(str);
212
213    len_ = len;
214    str_ = (char *) malloc(sizeof(char) * (len+1));
215    (void) P_memcpy(str_, str, len);
216    str_[len] = '\0';
217
218    key_ = 0; // lazy key define
219 }
220
221 string_ll::string_ll(const string_ll& s)
222     : str_(STRDUP(s.str_)), len_(s.len_), key_(s.key_) {
223    // lazy key define iff "s" lazy key define (as it should be)
224 }
225
226 string_ll::string_ll(const char c) {
227   char tempBuffer[2]; //only need space for one character and '\0'
228   sprintf(tempBuffer, "%c", c);
229
230   str_ = STRDUP(tempBuffer);
231   len_ = STRLEN(tempBuffer);
232
233   key_ = 0; // lazy key define
234 }
235
236 string_ll::string_ll(int i) {
237    char tempBuffer[40];
238    sprintf(tempBuffer, "%d", i);
239
240    str_ = STRDUP(tempBuffer);
241    len_ = STRLEN(tempBuffer);
242
243    key_ = 0; // lazy key define
244 }
245
246 string_ll::string_ll(long l) {
247    char tempBuffer[40];
248    sprintf(tempBuffer, "%ld", l);
249
250    str_ = STRDUP(tempBuffer);
251    len_ = STRLEN(tempBuffer);
252
253    key_ = 0; // lazy key define
254 }
255
256 string_ll::string_ll(unsigned u) {
257    char tempBuffer[40];
258    sprintf(tempBuffer, "%u", u);
259
260    str_ = STRDUP(tempBuffer);
261    len_ = STRLEN(tempBuffer);
262
263    key_ = 0; // lazy key define
264 }
265
266 string_ll::string_ll(unsigned long ul) {
267    char tempBuffer[40];
268    sprintf(tempBuffer, "%lu", ul);
269
270    str_ = STRDUP(tempBuffer);
271    len_ = STRLEN(tempBuffer);
272
273    key_ = 0; // lazy key define
274 }
275
276 string_ll::string_ll(float f) {
277    char tempBuffer[40];
278    sprintf(tempBuffer, "%f", f);
279
280    str_ = STRDUP(tempBuffer);
281    len_ = STRLEN(tempBuffer);
282
283    key_ = 0; // lazy key define
284 }
285
286 string_ll::string_ll(double d) {
287    char tempBuffer[40];
288    sprintf(tempBuffer, "%g", d);
289
290    str_ = STRDUP(tempBuffer);
291    len_ = STRLEN(tempBuffer);
292
293    key_ = 0; // lazy key define
294 }
295
296 string_ll::~string_ll() { 
297    assert(this);
298    if (str_)
299    {
300       free(str_);
301       str_ = 0;
302    }
303 }
304
305 string_ll&
306 string_ll::operator=(const char* str) {
307     if (str_ == str) {
308         return *this;
309     }
310
311     free(str_); str_ = 0;
312
313     str_ = STRDUP(str);
314     len_ = STRLEN(str);
315
316     key_ = 0; // lazy key define
317
318     return *this;
319 }
320
321 string_ll&
322 string_ll::operator=(const string_ll& s) {
323     if (this == &s) {
324         return *this;
325     }
326
327     free(str_); str_ = 0;
328
329     str_ = STRDUP(s.str_);
330     len_ = s.len_;
331     key_ = s.key_; // lazy key define iff "s" lazy key define, which is correct
332
333     return *this;
334 }
335
336 string_ll&
337 string_ll::operator+=(const string_ll& s) {
338     unsigned nlen = len_ + s.len_;
339     char*    ptr  = (char *) malloc(sizeof(char) * (nlen+1));
340     assert(ptr);
341
342     memcpy(ptr, str_, len_);
343     memcpy(&ptr[len_], s.str_, s.len_);
344     ptr[nlen] = '\0';
345
346     free(str_); str_ = 0;
347     str_ = ptr;
348     len_ = nlen;
349
350     key_ = 0;
351
352     return *this;
353 }
354
355 string_ll&
356 string_ll::operator+=(const char *ptr) {
357    // this routine exists as an optimization, sometimes avoiding the need to create
358    // a temporary string, which can be expensive.
359
360    const int ptr_len = P_strlen(ptr);
361    const unsigned nlen = len_ + ptr_len;
362    char *new_ptr = (char *) malloc(sizeof(char) * (nlen+1));
363    assert(new_ptr);
364
365    memcpy(new_ptr, str_, len_);
366    memcpy(&new_ptr[len_], ptr, ptr_len);
367    new_ptr[nlen] = '\0';
368   
369    if (str_)
370       free(str_);
371    str_ = new_ptr;
372    len_ = nlen;
373
374    key_ = 0; // lazy key define
375
376    return *this;
377 }
378
379 string_ll
380 string_ll::operator+(const string_ll& s) const {
381     string_ll ret = *this;
382     return (ret += s);
383 }
384
385 string_ll
386 string_ll::operator+(const char *ptr) const {
387    string_ll ret = *this;
388    return (ret += ptr);
389 }
390
391 bool
392 string_ll::operator==(const string_ll& s) const {
393    if (&s == this) return true;
394
395    updateKeyIfNeeded(); s.updateKeyIfNeeded();
396    if (key_ != s.key_) return false;
397    if (len_ != s.len_) return false;
398    return STREQ(str_, s.str_);
399 }
400
401 bool
402 string_ll::operator!=(const string_ll& s) const {
403    if (&s == this) return false;
404    if (len_ != s.len_) return true;
405    return STRNE(str_, s.str_);
406 }
407
408 bool
409 string_ll::operator<=(const string_ll& s) const {
410     return ((&s == this) || STRLE(str_, s.str_));
411 }
412
413 bool
414 string_ll::operator>=(const string_ll& s) const {
415     return ((&s == this) || STRGE(str_, s.str_));
416 }
417
418 bool
419 string_ll::prefix_of(const char* s, unsigned sl) const {
420     return ((len_ > sl) ? false : STREQN(str_, s, len_));
421 }
422
423 bool
424 string_ll::prefix_of(const string_ll& s) const {
425     return ((&s == this) || prefix_of(s.str_, s.len_));
426 }
427
428 bool
429 string_ll::prefixed_by(const char* s, unsigned sl) const {
430     return ((sl > len_) ? false : STREQN(str_, s, sl));
431 }
432
433 bool
434 string_ll::prefixed_by(const string_ll& s) const {
435     return ((&s == this) || prefixed_by(s.str_, s.len_));
436 }
437
438 bool
439 string_ll::suffix_of(const char* s, unsigned sl) const {
440     return ((len_ > sl) ? false : STREQN(str_, s + strlen( s ) - len_, len_));
441 }
442
443 bool
444 string_ll::suffix_of(const string_ll& s) const {
445     return ((&s == this) || suffix_of(s.str_, s.len_));
446 }
447
448 bool
449 string_ll::suffixed_by(const char* s, unsigned sl) const {
450     return ((sl > len_) ? false : STREQN(str_ + len_ - sl, s, sl));
451 }
452
453 bool
454 string_ll::suffixed_by(const string_ll& s) const {
455     return ((&s == this) || suffixed_by(s.str_, s.len_));
456 }
457
458
459 unsigned
460 string_ll::find (const char *s, unsigned sl) const {
461    if (!len_) return 0;
462   for(unsigned int i=0; i<=(len_-sl); i++) {
463     if( STREQN(str_ + i, s, sl) ) return i;
464   }
465   return len_;
466 }
467
468 unsigned 
469 string_ll::find (const string_ll &s) const{
470   return ((&s == this) ? 0 : find(s.str_, s.len_)); 
471 }
472
473 unsigned
474 string_ll::hashs(const char* str) {
475     if (!str)
476        return 1; // 0 is reserved for unhashed key
477
478     unsigned h = 5381;
479     while (*str) {
480         h = (h << 5) + h + (unsigned) (*str);
481         str++;
482     }
483     return h==0 ? 1 : h; // 0 is reserved for unhashed key
484 }
485
486 unsigned
487 string_ll::STRLEN(const char* str) {
488     return ((str)?(P_strlen(str)):(0));
489 }
490
491 char*
492 string_ll::STRDUP(const char* str) {
493     if (!str) {
494         return 0;
495     }
496
497     unsigned size = P_strlen(str)+1;
498     char*    p    = (char *)malloc(sizeof(char) * size);
499     assert(p);
500
501     (void) P_memcpy(p, str, size);
502     return p;
503 }
504
505 bool
506 string_ll::STREQ(const char* s1, const char* s2) {
507     return ((s1&&s2)?(P_strcmp(s1,s2)==0):(!(s1||s2)));
508 }
509
510 bool
511 string_ll::STREQN(const char* s1, const char* s2, unsigned len) {
512     return ((s1&&s2)?(P_strncmp(s1,s2,len)==0):(!(s1||s2)));
513 }
514
515 bool
516 string_ll::STRNE(const char* s1, const char* s2) {
517     return ((s1&&s2)?(P_strcmp(s1,s2)!=0):(false));
518 }
519
520 bool
521 string_ll::STRLT(const char* s1, const char* s2) {
522     return ((s1&&s2)?(P_strcmp(s1,s2)<0):(false));
523 }
524
525 bool
526 string_ll::STRLE(const char* s1, const char* s2) {
527     return ((s1&&s2)?(P_strcmp(s1,s2)<=0):(!(s1||s2)));
528 }
529
530 bool
531 string_ll::STRGT(const char* s1, const char* s2) {
532     return ((s1&&s2)?(P_strcmp(s1,s2)>0):(false));
533 }
534
535 bool
536 string_ll::STRGE(const char* s1, const char* s2) {
537     return ((s1&&s2)?(P_strcmp(s1,s2)>=0):(!(s1||s2)));
538 }
539
540 const char *
541 string_ll::STRCHR(const char* s, char c) {
542     return (s?(P_strchr(s,c)):(NULL));
543 }
544
545 string_ll
546 string_ll::substr(unsigned pos, unsigned len) const {
547         if( pos >= len_ )
548                 return string_ll( "" );
549         else
550                 return string_ll( str_ + pos, len );
551 }
552
553 bool
554 string_ll::wildcardEquiv( const string_ll &them, bool checkCase ) const {
555         if( *this == them )
556                 return true;
557         else
558                 return pattern_match( str_, them.str_, checkCase );
559 }
560
561
562 // This function will match string s against pattern p.
563 // Asterisks match 0 or more wild characters, and a question
564 // mark matches exactly one wild character.  In other words,
565 // the asterisk is the equivalent of the regex ".*" and the
566 // question mark is the equivalent of "."
567
568 bool
569 string_ll::pattern_match( const char *p, const char *s, bool checkCase ) {
570         //const char *p = ptrn;
571         //char *s = str;
572
573         while ( true ) {
574                 // If at the end of the pattern, it matches if also at the end of the string
575                 if( *p == '\0' )
576                         return ( *s == '\0' );
577
578                 // Process a '*'
579                 if( *p == MULTIPLE_WILDCARD_CHAR ) {
580                         ++p;
581                         
582                         // If at the end of the pattern, it matches
583                         if( *p == '\0' )
584                                 return true;
585
586                         // Try to match the remaining pattern for each remaining substring of s
587                         for(; *s != '\0'; ++s )
588                                 if( pattern_match( p, s, checkCase ) )
589                                         return true;
590                         // Failed
591                         return false;
592                 }
593
594                 // If at the end of the string (and at this point, not of the pattern), it fails
595                 if( *s == '\0' )
596                         return false;
597
598                 // Check if this character matches
599                 bool matchChar = false;
600                 if( *p == WILDCARD_CHAR || *p == *s )
601                         matchChar = true;
602                 else if( !checkCase ) {
603                         if( *p >= 'A' && *p <= 'Z' && *s == ( *p + ( 'a' - 'A' ) ) )
604                                 matchChar = true;
605                         else if( *p >= 'a' && *p <= 'z' && *s == ( *p - ( 'a' - 'A' ) ) )
606                                 matchChar = true;
607                 }
608
609                 if( matchChar ) {
610                         ++p;
611                         ++s;
612                         continue;
613                 }
614
615                 // Did not match
616                 return false;
617         }
618 }
619
620
621 // Use POSIX regular expression pattern matching to check if string s matches
622 // the pattern in this string
623 bool
624 string_ll::regexEquiv( const char *s, bool checkCase ) const {
625 // Would this work under NT?  I don't know.
626 #if !defined(os_windows)
627         regex_t r;
628         int err;
629         bool match = false;
630         int cflags = REG_NOSUB;
631         if( !checkCase )
632                 cflags |= REG_ICASE;
633
634         // Regular expressions must be compiled first, see 'man regexec'
635         err = regcomp( &r, str_, cflags );
636
637         if( err == 0 ) {
638                 // Now we can check for a match
639                 err = regexec( &r, s, 0, NULL, 0 );
640                 if( err == 0 )
641                         match = true;
642         }
643
644         // Deal with errors
645         if( err != 0 && err != REG_NOMATCH ) {
646                 char errbuf[80];
647                 regerror( err, &r, errbuf, 80 );
648                 //cerr << "string_ll::regexEquiv -- " << errbuf << endl;
649         }
650
651         // Free the pattern buffer
652         regfree( &r );
653         return match;
654 #else
655         return false;
656 #endif
657 }
658
659
660 #if 0
661 ostream& operator<< (ostream &os, const string_ll &s) {
662    if(s.str_ != NULL)
663       os << s.str_;
664    return os;
665 }
666 #endif
667
668 //debug_ostream& operator<< (debug_ostream &os, const string_ll &s) {
669 //   if(s.str_ != NULL)
670 //      os << s.str_;
671 //   return os;
672 //}
673
674 pdstring operator+(const char *ptr, const pdstring &str) {
675    // a syntactical convenience.
676    // This fn could probably be optimized quite a bit (pre-allocate exactly
677    // the # of bytes that are needed)
678    pdstring result(ptr);
679    result += str;
680    return result;
681 }
682
683 void pdstring::initialize_static_stuff() {
684    // should only get called once:
685    // VG(06/15/02): this assertion doesn't hold w/VC.NET because nilptr is never initialized!
686    //assert(nilptr == NULL);
687
688    nilptr = new pdstring((char*)NULL);
689       // the typecast is essential, lest NULL be interpreted
690       // as the integer 0 instead of the pointer 0!
691
692    nilptr_initialized = MAGIC_NILPTR_FLAG;
693       // magic value: see getNilptr() for explanation
694 }
695
696 void pdstring::free_static_stuff() {
697    delete nilptr;
698    nilptr = NULL;
699 }
700
701
702