From kde-commits  Fri Jul 29 07:03:54 2005
From: =?utf-8?q?Lu=C3=ADs=20Pedro=20Coelho?= <luis () luispedro ! org>
Date: Fri, 29 Jul 2005 07:03:54 +0000
To: kde-commits
Subject: kdesupport/indexlib
Message-Id: <1122620634.860217.28158.nullmailer () svn ! kde ! org>
X-MARC-Message: https://marc.info/?l=kde-commits&m=112262069432386

SVN commit 439875 by luis_pedro:

Add a one-level trie
(an indexing array, basically)

Pump the version number


 M  +3 -3      create.cpp  
 M  +1 -1      indexlib-config.in  
 M  +12 -0     memreference.h  
 M  +22 -3     stringset.cpp  
 M  +1 -1      stringset.h  
 M  +1 -1      version.h  


--- trunk/kdesupport/indexlib/create.cpp #439874:439875
@@ -33,7 +33,6 @@
 #include "quotes.h"
 #include "path.h"
 #include "version.h"
-#include "version.h"
 #include <fstream>
 #include <unistd.h>
 
@@ -44,9 +43,10 @@
 	if ( !info ) return indexlib::index_type::none;
 	std::string type;
 	std::string marker;
-	std::string version;
+	int major, minor;
+	char sep;
 	std::getline( info, marker );
-	std::getline( info, version );
+	info >> major >> sep >> minor;
 	info >> type;
 	if ( !info ) return indexlib::index_type::none;
 	if ( type == "quotes" ) return indexlib::index_type::quotes;
--- trunk/kdesupport/indexlib/indexlib-config.in #439874:439875
@@ -35,7 +35,7 @@
 	  flags="$flags -I$includedir/index"
 	  ;;
     --version)
-	  echo 0.93
+	  echo 0.94
 	  ;;
     --prefix)
 	  echo $prefix
--- trunk/kdesupport/indexlib/memreference.h #439874:439875
@@ -69,6 +69,18 @@
 	return ref = ref + v;
 }
 
+template <typename T>
+memory_reference<T> operator ++( memory_reference<T> ref ) {
+	return ref = ref + 1;
+}
+
+template <typename T>
+T operator ++( memory_reference<T> ref, int ) {
+	T v = ref;
+	ref = ref + 1;
+	return v;
+}
+
 template <typename T, typename U>
 memory_reference<T> operator -= ( memory_reference<T> ref, U v ) {
 	return ref = ref - v;
--- trunk/kdesupport/indexlib/stringset.cpp #439874:439875
@@ -36,13 +36,29 @@
 
 stringset::stringset( std::string name ):
 	strings_( path_concat( name, "strings-set" ) ),
-	ordered_( path_concat( name, "ordered-set" ) )
+	ordered_( path_concat( name, "ordered-set" ) ),
+	trie_( path_concat( name, "trie" ) )
 {
+	if ( trie_.empty() ) {
+		trie_.resize( 256 );
+		if ( !ordered_.empty() ) {
+			unsigned char last = 0;
+			for ( unsigned i = 0; i != ordered_.size(); ++i ) {
+				unsigned char cur = static_cast<unsigned char>( strings_.get_cstr( ordered_[ i ] )[ 0 ] );
+				if ( cur != last ) {
+					trie_[ cur ] = i;
+					last = cur;
+				}
+			}
+			if ( last < 255 ) trie_[ last + 1 ] = ordered_.size();
+		}
+	}
 }
 
 void stringset::remove( std::string name ) {
 	stringarray::remove( path_concat( name, "strings-set" ) );
 	memvector<stringarray::index_type>::remove( path_concat( name, "ordered-set" ) );
+	memvector<stringarray::index_type>::remove( path_concat( name, "trie" ) );
 }
 
 std::pair<stringset::const_iterator, stringset::const_iterator> stringset::upper_lower( const char* str ) const {
@@ -52,8 +68,8 @@
 }
 
 stringset::const_iterator stringset::lower_bound( const char* str ) const {
-	const_iterator top = begin();
-	const_iterator bottom = end();
+	const_iterator top = begin() + trie_[ ( unsigned )str[ 0 ] ];
+	const_iterator bottom = begin() + trie_[ ( unsigned )str[ 0 ] + 1 ];
 	while ( top < bottom ) {
 		const_iterator middle = top + ( bottom - top ) / 2;
 		int c = strcmp( *middle, str );
@@ -76,6 +92,9 @@
 	stringarray::index_type res = strings_.add( str );
 	ordered_.insert( ordered_.begin() + where.order(), res );
 	assert( ordered_.size() == strings_.size() );
+	for ( unsigned next = ( unsigned )str[ 0 ] + 1; next != 256; ++next ) {
+		++trie_[ next ];
+	}
 	return res;
 }
 
--- trunk/kdesupport/indexlib/stringset.h #439874:439875
@@ -140,7 +140,7 @@
 	private:
 		stringarray strings_;
 		memvector<stringarray::index_type> ordered_;
-		
+		memvector<stringarray::index_type> trie_;
 };
 
 inline
--- trunk/kdesupport/indexlib/version.h #439874:439875
@@ -5,7 +5,7 @@
 namespace version {
 
 const unsigned major = 0;
-const unsigned minor = 92;
+const unsigned minor = 94;
 const char* const marker = "indexlib directory, see http://luispedro.org/software/index";
 
 }}