summaryrefslogtreecommitdiffstats
path: root/lib/interfaces/hashedstring.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/interfaces/hashedstring.h')
-rw-r--r--lib/interfaces/hashedstring.h155
1 files changed, 155 insertions, 0 deletions
diff --git a/lib/interfaces/hashedstring.h b/lib/interfaces/hashedstring.h
new file mode 100644
index 00000000..e62ab2e3
--- /dev/null
+++ b/lib/interfaces/hashedstring.h
@@ -0,0 +1,155 @@
+/***************************************************************************
+ copyright : (C) 2006 by David Nolden
+***************************************************************************/
+
+/***************************************************************************
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU General Public License as published by *
+ * the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ ***************************************************************************/
+
+#ifndef HASHED_STRING_H
+#define HASHED_STRING_H
+
+#include<qstring.h>
+#include<qdatastream.h>
+#include<ksharedptr.h>
+#include<set>
+#include <ext/hash_map>
+#include <string>
+
+///A simple class that stores a string together with it's appropriate hash-key
+class HashedString {
+ public:
+ HashedString() : m_hash( 0 ) {}
+
+ HashedString( const QString& str ) : m_str( str ) {
+ initHash();
+ }
+
+ HashedString( const char* str ) : m_str( str ) {
+ initHash();
+ }
+
+ inline size_t hash() const {
+ return m_hash;
+ }
+
+ QString str() const {
+ return m_str;
+ }
+
+ bool operator == ( const HashedString& rhs ) const {
+ if ( m_hash != rhs.m_hash )
+ return false;
+ return m_str == rhs.m_str;
+ }
+
+ ///Does not compare alphabetically, uses the hash-key for ordering.
+ bool operator < ( const HashedString& rhs ) const {
+ if ( m_hash < rhs.m_hash )
+ return true;
+ if ( m_hash == rhs.m_hash )
+ return m_str < rhs.m_str;
+ return false;
+ }
+
+ static size_t hashString( const QString& str );
+
+ private:
+ void initHash();
+
+ QString m_str;
+ size_t m_hash;
+
+ friend QDataStream& operator << ( QDataStream& stream, const HashedString& str );
+ friend QDataStream& operator >> ( QDataStream& stream, HashedString& str );
+};
+
+QDataStream& operator << ( QDataStream& stream, const HashedString& str );
+
+QDataStream& operator >> ( QDataStream& stream, HashedString& str );
+
+class HashedStringSetData;
+class HashedStringSetGroup;
+
+///This is a reference-counting string-set optimized for fast lookup of hashed strings
+class HashedStringSet {
+ public:
+ HashedStringSet();
+
+ ~HashedStringSet();
+
+ ///Constructs a string-set from one single file
+ HashedStringSet( const HashedString& file );
+
+ HashedStringSet( const HashedStringSet& rhs );
+
+ int size() const;
+
+ HashedStringSet& operator = ( const HashedStringSet& rhs );
+ ///@return whether the given file-name was included
+ bool operator[] ( const HashedString& rhs ) const;
+
+ void insert( const HashedString& str );
+
+ HashedStringSet& operator +=( const HashedStringSet& );
+
+ HashedStringSet& operator -=( const HashedStringSet& );
+
+ ///intersection-test
+ ///Returns true if all files that are part of this set are also part of the given set
+ bool operator <= ( const HashedStringSet& rhs ) const;
+
+ bool operator == ( const HashedStringSet& rhs ) const;
+
+ void read( QDataStream& stream );
+ void write( QDataStream& stream ) const;
+
+ std::string print() const;
+
+ size_t hash() const;
+ private:
+ friend class HashedStringSetGroup;
+ void makeDataPrivate();
+ 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.
+ friend HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs );
+};
+
+HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs );
+
+namespace __gnu_cxx {
+template<>
+struct hash<HashedString> {
+ size_t operator () ( const HashedString& str ) const {
+ return str.hash();
+ }
+};
+}
+
+///Used to find all registered HashedStringSet's that contain all strings given to findGroups(..)
+class HashedStringSetGroup {
+ public:
+ typedef std::set<size_t> ItemSet;
+ void addSet( size_t id, const HashedStringSet& set );
+ void enableSet( size_t id );
+ bool isDisabled( size_t id ) const;
+ void disableSet( size_t id );
+ void removeSet( size_t id );
+
+ //Writes the ids of all registered and not disabled HashedStringSet's that are completely included in the given HashedStringSet efficiently)
+ void findGroups( HashedStringSet strings, ItemSet& target ) const;
+
+ private:
+ typedef __gnu_cxx::hash_map<HashedString, ItemSet> GroupMap;
+ typedef __gnu_cxx::hash_map<size_t, size_t> SizeMap;
+ GroupMap m_map;
+ SizeMap m_sizeMap;
+ ItemSet m_disabled;
+ ItemSet m_global;
+};
+#endif