1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2 // -*- Mode: C++ -*- 3 // 4 // Copyright (C) 2016-2020 Red Hat, Inc. 5 // 6 // Author: Dodji Seketeli 7 8 /// @file 9 /// 10 /// Declaration of types pertaining to the interned string pool used 11 /// throughout Libabigail, for performance reasons. 12 /// 13 /// For the record, the concept of the String Interning method is 14 /// explained at https://en.wikipedia.org/wiki/String_interning. 15 16 #ifndef __ABG_INTERNED_STR_H__ 17 #define __ABG_INTERNED_STR_H__ 18 19 #include <functional> 20 #include <memory> 21 #include <ostream> 22 #include <string> 23 #include <unordered_set> 24 25 26 namespace abigail 27 { 28 // Inject some std types into this namespace. 29 using std::unordered_set; 30 using std::string; 31 using std::ostream; 32 33 /// The abstraction of an interned string. 34 /// 35 /// It's a wrapper around a pointer to a std::string, along with a set 36 /// of method that helps make this string integrate with std::string 37 /// seamlessly. For instance, the type provides equality operators 38 /// that help compare it against std::string. 39 /// 40 /// Note that this @ref interned_string type is design to have the 41 /// same size as a pointer to a string. 42 class interned_string 43 { 44 std::string* raw_; 45 46 /// Constructor. 47 /// 48 /// @param raw the pointer to string that this interned_string 49 /// wraps. interned_string(string * raw)50 interned_string(string* raw) 51 : raw_(raw) 52 {} 53 54 public: 55 56 /// Default constructor. 57 /// 58 /// Constructs an empty pointer to string. interned_string()59 interned_string() 60 : raw_() 61 {} 62 63 /// Copy constructor. 64 /// 65 /// @param o the other instance to copy from. interned_string(const interned_string & o)66 interned_string(const interned_string& o) 67 {raw_ = o.raw_;} 68 69 /// Assignment operator. 70 /// 71 /// @param o the other instance to assign to the current one. 72 interned_string& 73 operator=(const interned_string& o) 74 { 75 raw_ = o.raw_; 76 return *this; 77 } 78 79 /// Clear the string. 80 void clear()81 clear() 82 {raw_ = 0;} 83 84 /// Test if the current instance of @ref interned_string is empty. 85 /// 86 /// @return true iff the currentisntance of @ref interned_string is 87 /// empty. 88 bool empty()89 empty() const 90 {return !raw_;} 91 92 /// Return the underlying pointer to std::string that this 93 /// interned_string wraps. 94 /// 95 /// @return a pointer to the underlying std::string, or 0 if this 96 /// interned_string is empty. 97 const string* raw()98 raw() const 99 {return raw_;} 100 101 /// Compare the current instance of @ref interned_string against 102 /// another instance of @ref interned_string. 103 /// 104 /// Note that this comparison is done in O(1), because it compares 105 /// the pointer values of the two underlying pointers to std::string 106 /// held by each instances of @ref interned_string. 107 /// 108 /// @param o the other @ref interned_string to compare against. 109 /// 110 /// @return true iff the current instance equals @p o. 111 bool 112 operator==(const interned_string& o) const 113 {return raw_ == o.raw_;} 114 115 /// Inequality operator. 116 /// 117 /// @param o the other @ref interned_string to compare the current 118 /// instance against. 119 /// 120 /// @return true iff the current instance is different from the @p 121 /// o. 122 bool 123 operator!=(const interned_string& o) const 124 {return !operator==(o);} 125 126 /// Compare the current instance of @ref interned_string against 127 /// an instance of std::string. 128 /// 129 /// Note that this comparison is done in O(N), N being the size (in 130 /// number of characters) of the strings being compared. 131 /// 132 /// @param o the instance of std::string to compare against. 133 /// 134 /// @return true iff the current instance equals @p o. 135 bool 136 operator==(const string& o) const 137 { 138 if (raw_) 139 return *raw_ == o; 140 return o.empty(); 141 } 142 143 /// Inequality operator. 144 /// 145 /// Takes the current instance of @ref interned_string and an 146 /// instance of std::string. 147 /// 148 /// @param o the instance of std::string to compare the current 149 /// instance of @ref interned_string against. 150 /// 151 /// @return true if the current instance of @ref interned_string is 152 /// different from @p o. 153 bool 154 operator!=(const string& o) const 155 {return ! operator==(o);} 156 157 /// "Less than" operator. 158 /// 159 /// Lexicographically compares the current instance of @ref 160 /// interned_string against another instance. 161 /// 162 /// @param o the other instance of @ref interned_string to compare 163 /// against. 164 /// 165 /// @return true iff the current instance of interned_string is 166 /// lexicographycally less than the string @p o. 167 bool 168 operator<(const interned_string& o) const 169 {return static_cast<string>(*this) < static_cast<std::string>(o);} 170 171 /// Conversion operator to string. 172 /// 173 /// @return the underlying string this instance refers too. string()174 operator string() const 175 { 176 if (!raw_) 177 return ""; 178 return *raw_; 179 } 180 181 friend class interned_string_pool; 182 }; // end class interned_string 183 184 bool 185 operator==(const string& l, const interned_string& r); 186 187 bool 188 operator!=(const string& l, const interned_string& r); 189 190 ostream& 191 operator<<(ostream& o, const interned_string& s); 192 193 string 194 operator+(const interned_string& s1,const string& s2); 195 196 string 197 operator+(const string& s1, const interned_string& s2); 198 199 /// A functor to hash instances of @ref interned_string. 200 struct hash_interned_string 201 { 202 /// The hash operator. 203 /// 204 /// It's super fast because hashing an interned string amounts to 205 /// hashing the pointer to it's underlying string. It's because 206 /// every distinct string is present only in one copy in the 207 /// environment. 208 /// 209 /// @param s the instance of @ref interned_string to hash. 210 /// 211 /// @return the returned hash value. 212 size_t operatorhash_interned_string213 operator()(const interned_string& s) const 214 { 215 std::hash<size_t> hash_size_t; 216 return hash_size_t(reinterpret_cast<size_t>(s.raw())); 217 } 218 }; // end struct hash_interned_string 219 220 221 /// The interned string pool. 222 /// 223 /// This is where all the distinct strings represented by the interned 224 /// strings leave. The pool is the actor responsible for creating 225 /// interned strings. 226 class interned_string_pool 227 { 228 struct priv; 229 std::unique_ptr<priv> priv_; 230 231 public: 232 233 interned_string_pool(); 234 235 interned_string 236 create_string(const std::string&); 237 238 bool 239 has_string(const char* s) const; 240 241 const char* 242 get_string(const char* s) const; 243 244 ~interned_string_pool(); 245 }; // end class interned_string_pool 246 247 /// Convenience typedef for a set of @ref interned_string 248 typedef unordered_set<interned_string, 249 hash_interned_string> interned_string_set_type; 250 251 } // end namespace abigail 252 253 #endif // __ABG_INTERNED_STR_H__ 254