• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • TDevelop Interfaces Library
 

TDevelop Interfaces Library

  • lib
  • interfaces
hashedstring.cpp
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 #include "hashedstring.h"
16 #include <kdatastream.h>
17 #include <sstream>
18 #include <algorithm>
19 #include <iterator>
20 #include<ext/hash_set>
21 #include<set>
22 #include<algorithm>
23 
24 //It needs to be measured whether this flag should be turned on or off. It seems just to move the complexity from one position to the other, without any variant being really better.
25 #define USE_HASHMAP
26 
27 size_t fastHashString( const TQString& str );
28 
29 size_t hashStringSafe( const TQString& str ) {
30  size_t hash = 0;
31  int len = str.length();
32  for( int a = 0; a < len; a++ ) {
33  hash = str[a].unicode() + (hash * 17);
34  }
35  return hash;
36 }
37 
38 size_t HashedString::hashString( const TQString& str )
39 {
40  return fastHashString( str );
41 }
42 
43 size_t fastHashString( const TQString& str ) {
44  size_t hash = 0;
45  if( !str.isEmpty() ) {
46  const TQChar* curr = str.unicode();
47  const TQChar* end = curr + str.length();
48  TQChar c;
49  for(; curr < end ;) {
50  c = *curr;
51  hash = c.unicode() + ( hash * 17 );
52  ++curr;
53  }
54  }
55  return hash;
56 }
57 
58 void HashedString::initHash() {
59  m_hash = hashString( m_str );
60 }
61 
62 
63 class HashedStringSetData : public TDEShared {
64  public:
65 #ifdef USE_HASHMAP
66  typedef __gnu_cxx::hash_set<HashedString> StringSet;
67 #else
68  typedef std::set<HashedString> StringSet; //must be a set, so the set-algorithms work
69 #endif
70  StringSet m_files;
71  mutable bool m_hashValid;
72  mutable size_t m_hash;
73  HashedStringSetData() : m_hashValid( false ) {
74  }
75  inline void invalidateHash() {
76  m_hashValid = false;
77  }
78 
79  void computeHash() const;
80 };
81 
82 void HashedStringSetData::computeHash() const {
83  int num = 1;
84  m_hash = 0;
85  for( StringSet::const_iterator it = m_files.begin(); it != m_files.end(); ++it ) {
86  num *= 7;
87  m_hash += num * (*it).hash();
88  }
89  m_hashValid = true;
90 }
91 
92 HashedStringSet::HashedStringSet() {}
93 
94 HashedStringSet::~HashedStringSet() {}
95 
96 HashedStringSet::HashedStringSet( const HashedString& file ) {
97  insert( file );
98 }
99 
100 HashedStringSet::HashedStringSet( const HashedStringSet& rhs ) : m_data( rhs.m_data ) {}
101 
102 HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs ) {
103  HashedStringSet ret = lhs;
104  ret += rhs;
105 
106  return ret;
107 }
108 
109 int HashedStringSet::size() const {
110  if( !m_data ) return 0;
111  return m_data->m_files.size();
112 }
113 
114 HashedStringSet& HashedStringSet::operator = ( const HashedStringSet& rhs ) {
115  m_data = rhs.m_data;
116  return *this;
117 }
118 
119 HashedStringSet& HashedStringSet::operator +=( const HashedStringSet& rhs ) {
120  if ( !rhs.m_data )
121  return * this;
122 
123 #ifndef USE_HASHMAP
124  TDESharedPtr<HashedStringSetData> oldData = m_data;
125  if( !oldData ) oldData = new HashedStringSetData();
126  m_data = new HashedStringSetData();
127  std::set_union( oldData->m_files.begin(), oldData->m_files.end(), rhs.m_data->m_files.begin(), rhs.m_data->m_files.end(), std::insert_iterator<HashedStringSetData::StringSet>( m_data->m_files, m_data->m_files.end() ) );
128 #else
129  makeDataPrivate();
130  m_data->m_files.insert( rhs.m_data->m_files.begin(), rhs.m_data->m_files.end() );
131  /*HashedStringSetData::StringSet::const_iterator end = rhs.m_data->m_files.end();
132  HashedStringSetData::StringSet& mySet( m_data->m_files );
133  for( HashedStringSetData::StringSet::const_iterator it = rhs.m_data->m_files.begin(); it != end; ++it ) {
134  mySet.insert( *it );
135  }*/
136 
137 #endif
138  return *this;
139 }
140 
141 HashedStringSet& HashedStringSet::operator -=( const HashedStringSet& rhs ) {
142  if( !m_data ) return *this;
143  if( !rhs.m_data ) return *this;
144 #ifndef USE_HASHMAP
145  TDESharedPtr<HashedStringSetData> oldData = m_data;
146  m_data = new HashedStringSetData();
147  std::set_difference( oldData->m_files.begin(), oldData->m_files.end(), rhs.m_data->m_files.begin(), rhs.m_data->m_files.end(), std::insert_iterator<HashedStringSetData::StringSet>( m_data->m_files, m_data->m_files.end() ) );
148 #else
149  makeDataPrivate();
150  HashedStringSetData::StringSet::const_iterator end = rhs.m_data->m_files.end();
151  HashedStringSetData::StringSet::const_iterator myEnd = m_data->m_files.end();
152  HashedStringSetData::StringSet& mySet( m_data->m_files );
153  for( HashedStringSetData::StringSet::const_iterator it = rhs.m_data->m_files.begin(); it != end; ++it ) {
154  mySet.erase( *it );
155  }
156 
157 #endif
158  return *this;
159 }
160 
161 
162 void HashedStringSet::makeDataPrivate() {
163  if ( !m_data ) {
164  m_data = new HashedStringSetData();
165  return ;
166  }
167  if ( m_data->_TDEShared_count() != 1 )
168  m_data = new HashedStringSetData( *m_data );
169 }
170 
171 bool HashedStringSet::operator[] ( const HashedString& rhs ) const {
172  //if ( rhs.str() == "*" )
173  //return true; /// * stands for "any file"
174  if ( !m_data )
175  return false;
176  return m_data->m_files.find( rhs ) != m_data->m_files.end();
177 }
178 
179 void HashedStringSet::insert( const HashedString& str ) {
180  if( str.str().isEmpty() ) return;
181  makeDataPrivate();
182  m_data->m_files.insert( str );
183  m_data->invalidateHash();
184 }
185 
186 bool HashedStringSet::operator <= ( const HashedStringSet& rhs ) const {
187  if ( !m_data )
188  return true;
189  if ( m_data->m_files.empty() )
190  return true;
191  if ( !rhs.m_data )
192  return false;
193 #ifndef USE_HASHMAP
194  return std::includes( rhs.m_data->m_files.begin(), rhs.m_data->m_files.end(), m_data->m_files.begin(), m_data->m_files.end() );
195 #else
196  const HashedStringSetData::StringSet& otherSet( rhs.m_data->m_files );
197  HashedStringSetData::StringSet::const_iterator end = rhs.m_data->m_files.end();
198  HashedStringSetData::StringSet::const_iterator myEnd = m_data->m_files.end();
199 
200  for( HashedStringSetData::StringSet::const_iterator it = m_data->m_files.begin(); it != myEnd; ++it ) {
201  HashedStringSetData::StringSet::const_iterator i = otherSet.find( *it );
202  if( i == end ) return false;
203  }
204  return true;
205 #endif
206 }
207 
208 bool HashedStringSet::operator == ( const HashedStringSet& rhs ) const {
209  if( hash() != rhs.hash() ) return false;
210 
211  bool empty1 = false;
212  if ( !m_data )
213  empty1 = true;
214  else if ( m_data->m_files.empty() )
215  empty1 = true;
216  bool empty2 = false;
217  if ( !rhs.m_data )
218  empty2 = true;
219  else if ( rhs.m_data->m_files.empty() )
220  empty2 = true;
221 
222  if ( empty1 && empty2 )
223  return true;
224  if ( empty1 || empty2 )
225  return false;
226 
227  return m_data->m_files == rhs.m_data->m_files;
228 }
229 
230 size_t HashedStringSet::hash() const {
231  if( !m_data ) return 0;
232  if( !m_data->m_hashValid ) m_data->computeHash();
233  return m_data->m_hash;
234 }
235 
236 void HashedStringSet::read( TQDataStream& stream ) {
237  bool b;
238  stream >> b;
239  if( b ) {
240  m_data = new HashedStringSetData();
241  int cnt;
242  stream >> cnt;
243  HashedString s;
244  for( int a = 0; a < cnt; a++ ) {
245  stream >> s;
246  m_data->m_files.insert( s );
247  }
248  } else {
249  m_data = 0;
250  }
251 }
252 
253 void HashedStringSet::write( TQDataStream& stream ) const {
254  bool b = m_data;
255  stream << b;
256  if( b ) {
257  int cnt = m_data->m_files.size();
258  stream << cnt;
259  for( HashedStringSetData::StringSet::const_iterator it = m_data->m_files.begin(); it != m_data->m_files.end(); ++it ) {
260  stream << *it;
261  }
262  }
263 }
264 
265 std::string HashedStringSet::print() const {
266  std::ostringstream s;
267  if( m_data ) {
268  for( HashedStringSetData::StringSet::const_iterator it = m_data->m_files.begin(); it != m_data->m_files.end(); ++it ) {
269  s << (*it).str().ascii() << "\n";
270  }
271  }
272  return s.str();
273 }
274 
275 TQDataStream& operator << ( TQDataStream& stream, const HashedString& str ) {
276  stream << str.m_str;
277  stream << str.m_hash;
278  return stream;
279 }
280 
281 TQDataStream& operator >> ( TQDataStream& stream, HashedString& str ) {
282  stream >> str.m_str;
283  stream >> str.m_hash;
284  return stream;
285 }
286 
287 void HashedStringSetGroup::addSet( size_t id, const HashedStringSet& set ) {
288  if( set.m_data && !set.m_data->m_files.empty() ) {
289  m_sizeMap[ id ] = set.size();
290  for( HashedStringSetData::StringSet::const_iterator it = set.m_data->m_files.begin(); it != set.m_data->m_files.end(); ++it ) {
291  GroupMap::iterator itr = m_map.find( *it );
292  if( itr == m_map.end() ) {
293  itr = m_map.insert( std::make_pair( *it, ItemSet() ) ).first;
294  }
295  itr->second.insert( id );
296  }
297  } else {
298  m_global.insert( id );
299  }
300 }
301 
302 void HashedStringSetGroup::disableSet( size_t id ) {
303  m_disabled.insert( id );
304 }
305 
306 void HashedStringSetGroup::enableSet( size_t id ) {
307  m_disabled.erase( id );
308 }
309 
310 bool HashedStringSetGroup::isDisabled( size_t id ) const {
311  return m_disabled.find( id ) != m_disabled.end();
312 }
313 
314 void HashedStringSetGroup::removeSet( size_t id ) {
315  m_disabled.erase( id );
316  m_global.erase( id );
317  m_sizeMap.erase( id );
318  for( GroupMap::iterator it = m_map.begin(); it != m_map.end(); ++it ) {
319  it->second.erase( id );
320  }
321 }
322 
323 void HashedStringSetGroup::findGroups( HashedStringSet strings, ItemSet& target ) const {
324  target.clear();
325  if( !strings.m_data ) {
326  std::set_difference( m_global.begin(), m_global.end(), m_disabled.begin(), m_disabled.end(), std::insert_iterator<ItemSet>( target, target.end() ) );
327  return;
328  }
329  //This might yet be optimized by sorting the sets according to their size, and starting the intersectioning with the smallest ones.
330  __gnu_cxx::hash_map<size_t, int> hitCounts;
331 
332  for( HashedStringSetData::StringSet::const_iterator it = strings.m_data->m_files.begin(); it != strings.m_data->m_files.end(); ++it ) {
333  GroupMap::const_iterator itr = m_map.find( *it );
334  if( itr == m_map.end() ) {
335  //There are no string-sets that include the currently searched for string
336  continue;
337  }
338 
339  for( ItemSet::const_iterator it2 = itr->second.begin(); it2 != itr->second.end(); ++it2 ) {
340  __gnu_cxx::hash_map<size_t, int>::iterator v = hitCounts.find( *it2 );
341  if( v != hitCounts.end() ) {
342  ++(*v).second;
343  } else {
344  hitCounts[*it2] = 1;
345  }
346  }
347  }
348 
349  //Now count together all groups that are completely within the given string-set(their hitCount equals their size)
350  ItemSet found;
351  for( __gnu_cxx::hash_map<size_t, int>::const_iterator it = hitCounts.begin(); it != hitCounts.end(); ++it ) {
352  if( (*it).second == (*m_sizeMap.find( (*it).first )).second )
353  found.insert( (*it).first );
354  }
355 
356 
357  std::set_union( found.begin(), found.end(), m_global.begin(), m_global.end(), std::insert_iterator<ItemSet>( target, target.end() ) );
358 
359  target.swap( found );
360  target.clear();
361  std::set_difference( found.begin(), found.end(), m_disabled.begin(), m_disabled.end(), std::insert_iterator<ItemSet>( target, target.end() ) );
362 }
HashedString
A simple class that stores a string together with it&#39;s appropriate hash-key.
Definition: hashedstring.h:26
HashedStringSet::operator<=
bool operator<=(const HashedStringSet &rhs) const
intersection-test Returns true if all files that are part of this set are also part of the given set ...
Definition: hashedstring.cpp:186
HashedStringSet::operator[]
bool operator[](const HashedString &rhs) const
Definition: hashedstring.cpp:171
HashedStringSet
This is a reference-counting string-set optimized for fast lookup of hashed strings.
Definition: hashedstring.h:81

TDevelop Interfaces Library

Skip menu "TDevelop Interfaces Library"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

TDevelop Interfaces Library

Skip menu "TDevelop Interfaces Library"
  • buildtools
  •   lib
  •     base
  •     parsers
  •       autotools
  •       qmake
  •     widgets
  •   api
  • languages
  •   lib
  •     debugger
  •     designer_integration
  •     interfaces
  • lib
  •   catalog
  •   interfaces
  •     extensions
  •     external
  •     extras
  •   util
  •   widgets
  •     propeditor
  • parts
  •   documentation
  •     interfaces
  • src
  •   profileengine
  •     lib
Generated for TDevelop Interfaces Library by doxygen 1.8.13
This website is maintained by Timothy Pearson.