← Back to branch summary

~ubuntu-branches/debian/sid/kdevelop/sid

« back to all changes in this revision

Viewing changes to lib/interfaces/hashedstring.h

  • Committer: Bazaar Package Importer
  • Author(s): Jeremy Lainé
  • Date: 2010-05-05 07:21:55 UTC
  • mfrom: (1.2.3 upstream) (5.1.2 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100505072155-h78lx19pu04sbhtn
Tags: 4:4.0.0-2
http://bugs.debian.org/579947
http://bugs.debian.org/481832
http://bugs.debian.org/562410
http://bugs.debian.org/546961
* Upload to unstable (Closes: #579947, #481832).
* Acknowledge obsolete NMU fixes (Closes: #562410, #546961).

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/interfaces/hashedstring.h
1
 
/***************************************************************************
2
 
   copyright            : (C) 2006 by David Nolden
3
 
   email                : david.nolden.kdevelop@art-master.de
4
 
***************************************************************************/
5
 
 
6
 
/***************************************************************************
7
 
 *                                                                         *
8
 
 *   This program is free software; you can redistribute it and/or modify  *
9
 
 *   it under the terms of the GNU General Public License as published by  *
10
 
 *   the Free Software Foundation; either version 2 of the License, or     *
11
 
 *   (at your option) any later version.                                   *
12
 
 *                                                                         *
13
 
 ***************************************************************************/
14
 
 
15
 
#ifndef HASHED_STRING_H
16
 
#define HASHED_STRING_H
17
 
 
18
 
#include<qstring.h>
19
 
#include<qdatastream.h>
20
 
#include<ksharedptr.h>
21
 
#include<set>
22
 
#include <ext/hash_map>
23
 
#include <string>
24
 
 
25
 
///A simple class that stores a string together with it's appropriate hash-key
26
 
class HashedString {
27
 
  public:
28
 
    HashedString() : m_hash( 0 ) {}
29
 
 
30
 
    HashedString( const QString& str ) : m_str( str ) {
31
 
      initHash();
32
 
    }
33
 
    
34
 
    HashedString( const char* str ) : m_str( str ) {
35
 
      initHash();
36
 
    }
37
 
 
38
 
    inline size_t hash() const {
39
 
      return m_hash;
40
 
    }
41
 
 
42
 
    QString str() const {
43
 
      return m_str;
44
 
    }
45
 
 
46
 
    bool operator == ( const HashedString& rhs ) const {
47
 
      if ( m_hash != rhs.m_hash )
48
 
        return false;
49
 
      return m_str == rhs.m_str;
50
 
    }
51
 
 
52
 
    ///Does not compare alphabetically, uses the hash-key for ordering.
53
 
    bool operator < ( const HashedString& rhs ) const {
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
 
  public:
83
 
    HashedStringSet();
84
 
 
85
 
    ~HashedStringSet();
86
 
 
87
 
    ///Constructs a string-set from one single file
88
 
    HashedStringSet( const HashedString& file );
89
 
 
90
 
    HashedStringSet( const HashedStringSet& rhs );
91
 
 
92
 
    int size() const;
93
 
 
94
 
    HashedStringSet& operator = ( const HashedStringSet& rhs );
95
 
    ///@return whether the given file-name was included
96
 
    bool operator[] ( const HashedString& rhs ) const;
97
 
 
98
 
    void insert( const HashedString& str );
99
 
 
100
 
    HashedStringSet& operator +=( const HashedStringSet& );
101
 
    
102
 
    HashedStringSet& operator -=( const HashedStringSet& );
103
 
 
104
 
    ///intersection-test
105
 
    ///Returns true if all files that are part of this set are also part of the given set
106
 
    bool operator <= ( const HashedStringSet& rhs ) const;
107
 
 
108
 
    bool operator == ( const HashedStringSet& rhs ) const;
109
 
 
110
 
    void read( QDataStream& stream );
111
 
    void write( QDataStream& stream ) const;
112
 
 
113
 
    std::string print() const;
114
 
 
115
 
  size_t hash() const;
116
 
  private:
117
 
    friend class HashedStringSetGroup;
118
 
    void makeDataPrivate();
119
 
    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.
120
 
    friend HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs );
121
 
};
122
 
 
123
 
HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs );
124
 
 
125
 
namespace __gnu_cxx {
126
 
template<>
127
 
struct hash<HashedString> {
128
 
  size_t operator () ( const HashedString& str ) const {
129
 
    return str.hash();
130
 
  }
131
 
};
132
 
}
133
 
 
134
 
///Used to find all registered HashedStringSet's that contain all strings given to findGroups(..)
135
 
class HashedStringSetGroup {
136
 
  public:
137
 
    typedef std::set<size_t> ItemSet;
138
 
    void addSet( size_t id, const HashedStringSet& set );
139
 
    void enableSet( size_t id );
140
 
    bool isDisabled( size_t id ) const;
141
 
    void disableSet( size_t id );
142
 
    void removeSet( size_t id );
143
 
 
144
 
    //Writes the ids of all registered and not disabled HashedStringSet's that are completely included in the given HashedStringSet efficiently)
145
 
    void findGroups( HashedStringSet strings, ItemSet& target ) const;
146
 
 
147
 
  private:
148
 
    typedef __gnu_cxx::hash_map<HashedString, ItemSet> GroupMap;
149
 
    typedef __gnu_cxx::hash_map<size_t, size_t> SizeMap;
150
 
    GroupMap m_map;
151
 
    SizeMap m_sizeMap;
152
 
    ItemSet m_disabled;
153
 
    ItemSet m_global;
154
 
};
155
 
#endif