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