15 #include "hashedstring.h" 16 #include <kdatastream.h> 20 #include<ext/hash_set> 27 size_t fastHashString(
const TQString& str );
29 size_t hashStringSafe(
const TQString& str ) {
31 int len = str.length();
32 for(
int a = 0; a < len; a++ ) {
33 hash = str[a].unicode() + (hash * 17);
38 size_t HashedString::hashString(
const TQString& str )
40 return fastHashString( str );
43 size_t fastHashString(
const TQString& str ) {
45 if( !str.isEmpty() ) {
46 const TQChar* curr = str.unicode();
47 const TQChar* end = curr + str.length();
51 hash = c.unicode() + ( hash * 17 );
58 void HashedString::initHash() {
59 m_hash = hashString( m_str );
63 class HashedStringSetData :
public TDEShared {
66 typedef __gnu_cxx::hash_set<HashedString> StringSet;
68 typedef std::set<HashedString> StringSet;
71 mutable bool m_hashValid;
72 mutable size_t m_hash;
73 HashedStringSetData() : m_hashValid( false ) {
75 inline void invalidateHash() {
79 void computeHash()
const;
82 void HashedStringSetData::computeHash()
const {
85 for( StringSet::const_iterator it = m_files.begin(); it != m_files.end(); ++it ) {
87 m_hash += num * (*it).hash();
92 HashedStringSet::HashedStringSet() {}
94 HashedStringSet::~HashedStringSet() {}
100 HashedStringSet::HashedStringSet(
const HashedStringSet& rhs ) : m_data( rhs.m_data ) {}
109 int HashedStringSet::size()
const {
110 if( !m_data )
return 0;
111 return m_data->m_files.size();
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() ) );
130 m_data->m_files.insert( rhs.m_data->m_files.begin(), rhs.m_data->m_files.end() );
142 if( !m_data )
return *
this;
143 if( !rhs.m_data )
return *
this;
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() ) );
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 ) {
162 void HashedStringSet::makeDataPrivate() {
164 m_data =
new HashedStringSetData();
167 if ( m_data->_TDEShared_count() != 1 )
168 m_data =
new HashedStringSetData( *m_data );
176 return m_data->m_files.find( rhs ) != m_data->m_files.end();
179 void HashedStringSet::insert(
const HashedString& str ) {
180 if( str.str().isEmpty() )
return;
182 m_data->m_files.insert( str );
183 m_data->invalidateHash();
189 if ( m_data->m_files.empty() )
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() );
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();
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;
208 bool HashedStringSet::operator == (
const HashedStringSet& rhs )
const {
209 if( hash() != rhs.hash() )
return false;
214 else if ( m_data->m_files.empty() )
219 else if ( rhs.m_data->m_files.empty() )
222 if ( empty1 && empty2 )
224 if ( empty1 || empty2 )
227 return m_data->m_files == rhs.m_data->m_files;
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;
236 void HashedStringSet::read( TQDataStream& stream ) {
240 m_data =
new HashedStringSetData();
244 for(
int a = 0; a < cnt; a++ ) {
246 m_data->m_files.insert( s );
253 void HashedStringSet::write( TQDataStream& stream )
const {
257 int cnt = m_data->m_files.size();
259 for( HashedStringSetData::StringSet::const_iterator it = m_data->m_files.begin(); it != m_data->m_files.end(); ++it ) {
265 std::string HashedStringSet::print()
const {
266 std::ostringstream s;
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";
275 TQDataStream& operator << ( TQDataStream& stream,
const HashedString& str ) {
277 stream << str.m_hash;
281 TQDataStream& operator >> ( TQDataStream& stream,
HashedString& str ) {
283 stream >> str.m_hash;
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;
295 itr->second.insert(
id );
298 m_global.insert(
id );
302 void HashedStringSetGroup::disableSet(
size_t id ) {
303 m_disabled.insert(
id );
306 void HashedStringSetGroup::enableSet(
size_t id ) {
307 m_disabled.erase(
id );
310 bool HashedStringSetGroup::isDisabled(
size_t id )
const {
311 return m_disabled.find(
id ) != m_disabled.end();
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 );
323 void HashedStringSetGroup::findGroups(
HashedStringSet strings, ItemSet& target )
const {
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() ) );
330 __gnu_cxx::hash_map<size_t, int> hitCounts;
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() ) {
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() ) {
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 );
357 std::set_union( found.begin(), found.end(), m_global.begin(), m_global.end(), std::insert_iterator<ItemSet>( target, target.end() ) );
359 target.swap( found );
361 std::set_difference( found.begin(), found.end(), m_disabled.begin(), m_disabled.end(), std::insert_iterator<ItemSet>( target, target.end() ) );
A simple class that stores a string together with it's appropriate hash-key.
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 ...
bool operator[](const HashedString &rhs) const
This is a reference-counting string-set optimized for fast lookup of hashed strings.