1 /* 2 SPDX-FileCopyrightText: 2006 David Nolden <david.nolden.kdevelop@art-master.de> 3 SPDX-License-Identifier: GPL-2.0-or-later 4 */ 5 6 #ifndef HASHED_STRING_H 7 #define HASHED_STRING_H 8 9 #include "ast.h" 10 11 #include <QHash> 12 #include <QSet> 13 #include <QString> 14 #include <qdatastream.h> 15 #include <set> 16 #include <string> 17 18 ///A simple class that stores a string together with it's appropriate hash-key 19 class HashedString 20 { 21 public: HashedString()22 HashedString() : m_hash(0) {} 23 HashedString(const QString & str)24 HashedString(const QString& str) : m_str(str) // krazy:exclude=explicit 25 { 26 initHash(); 27 } 28 HashedString(const char * str)29 HashedString(const char* str) : m_str(QLatin1String(str)) // krazy:exclude=explicit 30 { 31 initHash(); 32 } 33 hash()34 inline size_t hash() const 35 { 36 return m_hash; 37 } 38 str()39 QString str() const 40 { 41 return m_str; 42 } 43 44 bool operator == (const HashedString& rhs) const 45 { 46 if (m_hash != rhs.m_hash) 47 return false; 48 return m_str == rhs.m_str; 49 } 50 51 ///Does not compare alphabetically, uses the hash-key for ordering. 52 bool operator < (const HashedString& rhs) const 53 { 54 if (m_hash < rhs.m_hash) 55 return true; 56 if (m_hash == rhs.m_hash) 57 return m_str < rhs.m_str; 58 return false; 59 } 60 61 static size_t hashString(const QString& str); 62 63 private: 64 void initHash(); 65 66 QString m_str; 67 size_t m_hash; 68 69 friend QDataStream& operator << (QDataStream& stream, const HashedString& str); 70 friend QDataStream& operator >> (QDataStream& stream, HashedString& str); 71 }; 72 73 QDataStream& operator << (QDataStream& stream, const HashedString& str); 74 75 QDataStream& operator >> (QDataStream& stream, HashedString& str); 76 77 class HashedStringSetData; 78 class HashedStringSetGroup; 79 80 ///This is a reference-counting string-set optimized for fast lookup of hashed strings 81 class HashedStringSet 82 { 83 public: 84 HashedStringSet(); 85 86 ~HashedStringSet(); 87 88 ///Constructs a string-set from one single file 89 explicit HashedStringSet(const HashedString& file); 90 91 HashedStringSet(const HashedStringSet& rhs); 92 93 int size() const; 94 95 HashedStringSet& operator = (const HashedStringSet& rhs); 96 ///@return whether the given file-name was included 97 bool operator[] (const HashedString& rhs) const; 98 99 void insert(const HashedString& str); 100 101 HashedStringSet& operator +=(const HashedStringSet&); 102 103 HashedStringSet& operator -=(const HashedStringSet&); 104 105 ///intersection-test 106 ///Returns true if all files that are part of this set are also part of the given set 107 bool operator <= (const HashedStringSet& rhs) const; 108 109 bool operator == (const HashedStringSet& rhs) const; 110 111 void read(QDataStream& stream); 112 void write(QDataStream& stream) const; 113 114 std::string print() const; 115 116 size_t hash() const; 117 private: 118 friend class HashedStringSetGroup; 119 void makeDataPrivate(); 120 KSharedPtr<HashedStringSetData> m_data; //this implies some additional cost because KShared's destructor is virtual. Maybe change that by copying KShared without the virtual destructor. 121 friend HashedStringSet operator + (const HashedStringSet& lhs, const HashedStringSet& rhs); 122 }; 123 124 HashedStringSet operator + (const HashedStringSet& lhs, const HashedStringSet& rhs); 125 126 ///Used to find all registered HashedStringSet's that contain all strings given to findGroups(..) 127 class HashedStringSetGroup 128 { 129 public: 130 typedef std::set<size_t> ItemSet; 131 void addSet(size_t id, const HashedStringSet& set); 132 void enableSet(size_t id); 133 bool isDisabled(size_t id) const; 134 void disableSet(size_t id); 135 void removeSet(size_t id); 136 137 //Writes the ids of all registered and not disabled HashedStringSet's that are completely included in the given HashedStringSet efficiently) 138 void findGroups(HashedStringSet strings, ItemSet& target) const; 139 140 private: 141 typedef QHash<HashedString, ItemSet> GroupMap; 142 typedef QHash<size_t, size_t> SizeMap; 143 GroupMap m_map; 144 SizeMap m_sizeMap; 145 ItemSet m_disabled; 146 ItemSet m_global; 147 }; 148 149 uint qHash(const HashedString &key); 150 151 #endif 152