[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: kdesupport/indexlib
From: Luís Pedro Coelho <luis () luispedro ! org>
Date: 2005-07-29 7:03:54
Message-ID: 1122620634.860217.28158.nullmailer () svn ! kde ! org
[Download RAW message or body]
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";
}}
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic