Update copyright to LGPL on all files
[dyninst.git] / common / src / util.C
1 /*
2  * Copyright (c) 1996-2009 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 #if defined(os_windows)
32 #include "common/h/ntHeaders.h"
33 #endif
34 #include <stdio.h>
35 #include <string>
36 #include "dynutil/h/util.h"
37
38
39 namespace Dyninst {
40 COMMON_EXPORT unsigned addrHashCommon(const Address &addr)
41 {
42    // inspired by hashs of string class
43
44    register unsigned result = 5381;
45
46    register Address accumulator = addr;
47    while (accumulator > 0) {
48       // We use 3 bits at a time from the address
49       result = (result << 4) + result + (accumulator & 0x07);
50       accumulator >>= 3;
51    }
52
53    return result;
54 }
55
56 COMMON_EXPORT unsigned addrHash(const Address & iaddr)
57 {
58    return Dyninst::addrHashCommon(iaddr);
59 }
60
61 COMMON_EXPORT unsigned ptrHash(const void * iaddr)
62 {
63    return Dyninst::addrHashCommon((Address)iaddr);
64 }
65
66 COMMON_EXPORT unsigned ptrHash(void * iaddr)
67 {
68    return Dyninst::addrHashCommon((Address)iaddr);
69 }
70
71 COMMON_EXPORT unsigned addrHash4(const Address &iaddr)
72 {
73    // call when you know that the low 2 bits are 0 (meaning they contribute
74    // nothing to an even hash distribution)
75    return Dyninst::addrHashCommon(iaddr >> 2);
76 }
77
78 COMMON_EXPORT unsigned addrHash16(const Address &iaddr)
79 {
80    // call when you know that the low 4 bits are 0 (meaning they contribute
81    // nothing to an even hash distribution)
82    return Dyninst::addrHashCommon(iaddr >> 4);
83 }
84
85 // string hash grabbed from pdstring
86 unsigned stringhash(const std::string &s)
87 {
88    const char *str = s.c_str();
89    if (!str)
90       return 1; // 0 is reserved for unhashed key
91
92    unsigned h = 5381;
93    while (*str) {
94       h = (h << 5) + h + (unsigned) (*str);
95       str++;
96    }
97    return h==0 ? 1 : h; // 0 is reserved for unhashed key
98 }
99
100 std::string itos(int in)
101 {
102   char buf[16];
103   snprintf(buf, 16, "%d", in);
104   return std::string(buf);
105 }
106
107 std::string utos(unsigned in)
108 {
109   char buf[16];
110   snprintf(buf, 16, "%u", in);
111   return std::string(buf);
112 }
113
114
115 // This function will match string s against pattern p.
116 // Asterisks match 0 or more wild characters, and a question
117 // mark matches exactly one wild character.  In other words,
118 // the asterisk is the equivalent of the regex ".*" and the
119 // question mark is the equivalent of "."
120
121 bool pattern_match( const char *p, const char *s, bool checkCase ) 
122 {
123    //const char *p = ptrn;
124    //char *s = str;
125
126    while ( true ) {
127
128       // If at the end of the pattern, it matches if also at the end of the string
129
130       if ( *p == '\0' )
131          return ( *s == '\0' );
132
133       // Process a '*'
134
135       if ( *p == MULTIPLE_WILDCARD_CHAR ) {
136          ++p;
137
138          // If at the end of the pattern, it matches
139          if ( *p == '\0' )
140             return true;
141
142          // Try to match the remaining pattern for each remaining substring of s
143          for (; *s != '\0'; ++s )
144             if ( pattern_match( p, s, checkCase ) )
145                return true;
146          // Failed
147          return false;
148       }
149
150       // If at the end of the string (and at this point, not of the pattern), it fails
151       if( *s == '\0' )
152          return false;
153
154       // Check if this character matches
155       bool matchChar = false;
156       if ( *p == WILDCARD_CHAR || *p == *s )
157          matchChar = true;
158       else if ( !checkCase ) {
159          if ( *p >= 'A' && *p <= 'Z' && *s == ( *p + ( 'a' - 'A' ) ) )
160             matchChar = true;
161          else if ( *p >= 'a' && *p <= 'z' && *s == ( *p - ( 'a' - 'A' ) ) )
162             matchChar = true;
163       }
164
165       if ( matchChar ) {
166          ++p;
167          ++s;
168          continue;
169       }
170
171       // Did not match
172       return false;
173    }
174 }
175
176 bool wildcardEquiv(const std::string &us, const std::string &them, bool checkCase ) 
177 {
178    if ( us == them )
179       return true;
180    else
181       return pattern_match( us.c_str(), them.c_str(), checkCase );
182 }
183
184
185 } // namespace Dyninst