Published STX B+ Tree C++ Template Classes Version 0.7
Posted on 2007-04-27 15:02 by Timo at Permlink with Comments. Tags: stx-btree c++
Released the first version 0.7 of the STX B+ Tree C++ Template Classes package. The template classes are licensed under the LGPL.
The STX B+ Tree package is a set of C++ template classes implementing a B+ tree key/data container in main memory. The classes are designed as drop-in replacements of the STL containers set, map, multiset and multimap and follow their interfaces very closely. By packing multiple value pairs into each node of the tree the B+ tree reduces heap fragmentation and utilizes cache-line effects better than the standard red-black binary tree. The tree algorithms are based on the implementation in Cormen, Leiserson and Rivest's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. The classes contain extensive assertion and verification mechanisms to ensure the implementation's correctness by testing the tree invariants.
The main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.
The source code package is available for download from this webpage.
The classes are documented extensively using doxygen. The generated HTML documentation can be browsed online or downloaded.
Special interest was put into performing a speed comparison test between the standard red-black tree and the new B+ tree implementation. The speed test results are interesting and show the B+ tree to be significantly faster for trees containing more than 16,000 items.
Lautsprecher-Odyssee und Duetta Selbstbau
Posted on 2007-04-18 19:00 by Timo at Permlink with Comments. Tags: hifi selbstbau
Zusammenfassung
In diesem Blog-Eintrag beschreibe ich meine drei-monatige, intensive Suche nach neuen Lautsprechern. Der Eintrag enthält viele persönliche Meinungen und soll insbesondere zu der Zeit angestellte Überlegungen und Vermutungen erfassen. Dieser Bericht soll sein, was ich in damals vergeblich im Internet gesucht habe: eine detaillierte Entwicklung von völlig unerfahrenen Musikhörer zum Boxen-Selbstbauer. Der ganze Bericht ist natürlich subjektiv, manch Suchender wird völlig anderer Meinung sein.
Die Suche startet im letzten Dezember bei den einschlägigen Elektronikmärkten. Mit den bekannten Test-Magazinen bewaffnet, hätte ich dort um Haaresbreite ein Paar Lautsprecher gekauft. Durch Zufall kamen wir dann zu Orbid-Sound und durften dort begeistert alles probe hören und sogar zwei Paar Lautsprecher ausleihen. Am Ende landete ich jedoch beim HiFi-Selbstbau. Nach langem Vergleich der verschiedenen im Internet verfügbaren Bausätze entschied ich mich zu Udo Wohlgemuth nach Bochum zu fahren und dort zwei Duetta-Bausätze zu kaufen.
Die zehntägige Bastelarbeit an dem Paar Duettas hat mir sehr viel Spaß gemacht. Hier werden die einzelnen Schritte nur kurz beschrieben aber durch viele Photos illustriert. Besonderes Augenmerk legte ich auf die Schwierigkeiten, welche ich damals als totaler Selbstbau-Neuling überwinden musste. Der Blog-Eintrag endet mit einer differenzierten Beschreibung des Klangs meiner Duettas.
HMTG Web Page Redesign
Posted on 2007-04-14 20:24 by Timo at Permlink with Comments. Tags: webdesign
Finished redesigning the web site and e-catalog of the Hartmetall-Gesellschaft. This is actually the fifth version of the homepage. It is now based on Template::Toolkit technology with the old PostgreSQL database back-end. The style was adapted to todays modern web designs.
On this occasion I have collected and organized versions of older home pages. They show a stream of development which the page has taken:
C++ Code Snippet - Compressing STL Strings with zlib
Posted on 2007-03-28 18:23 by Timo at Permlink with Comments. Tags: c++ code-snippet
The zlib library can be found on virtually every computer. It is THE general-purpose lossless patent-free compression library.
This small C++ code snippet features a pair of functions which use this ubiquitous library to compress ordinary STL strings. There are many uses for this code snippet, like compressing string data stored in a database or binary data transfered over a network. Keep in mind that the compressed string data is binary, so the string's c_str() representation must be avoided.
#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <zlib.h>
/** Compress a STL string using zlib with given compression level and return
* the binary data. */
std::string compress_string(const std::string& str,
int compressionlevel = Z_BEST_COMPRESSION)
{
z_stream zs; // z_stream is zlib's control structure
memset(&zs, 0, sizeof(zs));
if (deflateInit(&zs, compressionlevel) != Z_OK)
throw(std::runtime_error("deflateInit failed while compressing."));
zs.next_in = (Bytef*)str.data();
zs.avail_in = str.size(); // set the z_stream's input
int ret;
char outbuffer[32768];
std::string outstring;
// retrieve the compressed bytes blockwise
do {
zs.next_out = reinterpret_cast<Bytef*>(outbuffer);
zs.avail_out = sizeof(outbuffer);
ret = deflate(&zs, Z_FINISH);
if (outstring.size() < zs.total_out) {
// append the block to the output string
outstring.append(outbuffer,
zs.total_out - outstring.size());
}
} while (ret == Z_OK);
deflateEnd(&zs);
if (ret != Z_STREAM_END) { // an error occurred that was not EOF
std::ostringstream oss;
oss << "Exception during zlib compression: (" << ret << ") " << zs.msg;
throw(std::runtime_error(oss.str()));
}
return outstring;
}
/** Decompress an STL string using zlib and return the original data. */
std::string decompress_string(const std::string& str)
{
z_stream zs; // z_stream is zlib's control structure
memset(&zs, 0, sizeof(zs));
if (inflateInit(&zs) != Z_OK)
throw(std::runtime_error("inflateInit failed while decompressing."));
zs.next_in = (Bytef*)str.data();
zs.avail_in = str.size();
int ret;
char outbuffer[32768];
std::string outstring;
// get the decompressed bytes blockwise using repeated calls to inflate
do {
zs.next_out = reinterpret_cast<Bytef*>(outbuffer);
zs.avail_out = sizeof(outbuffer);
ret = inflate(&zs, 0);
if (outstring.size() < zs.total_out) {
outstring.append(outbuffer,
zs.total_out - outstring.size());
}
} while (ret == Z_OK);
inflateEnd(&zs);
if (ret != Z_STREAM_END) { // an error occurred that was not EOF
std::ostringstream oss;
oss << "Exception during zlib decompression: (" << ret << ") "
<< zs.msg;
throw(std::runtime_error(oss.str()));
}
return outstring;
}
/** Small dumb tool (de)compressing cin to cout. It holds all input in memory,
* so don't use it for huge files. */
int main(int argc, char* argv[])
{
std::string allinput;
while (std::cin.good()) // read all input from cin
{
char inbuffer[32768];
std::cin.read(inbuffer, sizeof(inbuffer));
allinput.append(inbuffer, std::cin.gcount());
}
if (argc >= 2 && strcmp(argv[1], "-d") == 0)
{
std::string cstr = decompress_string( allinput );
std::cerr << "Inflated data: "
<< allinput.size() << " -> " << cstr.size()
<< " (" << std::setprecision(1) << std::fixed
<< ( ((float)cstr.size() / (float)allinput.size() - 1.0) * 100.0 )
<< "% increase).\n";
std::cout << cstr;
}
else
{
std::string cstr = compress_string( allinput );
std::cerr << "Deflated data: "
<< allinput.size() << " -> " << cstr.size()
<< " (" << std::setprecision(1) << std::fixed
<< ( (1.0 - (float)cstr.size() / (float)allinput.size()) * 100.0)
<< "% saved).\n";
std::cout << cstr;
}
}
C++ Code Snippet - Using the Boost.Regex Library
Posted on 2007-03-14 14:43 by Timo at Permlink with Comments. Tags: c++ code-snippet
The Boost library is a collection of very useful C++ (template) libraries. However it's documentation is very complex and using the library straight-forward usually results in g++ scrolling endless pages of template instantiation errors.
This code snippet shows by example how to use the Boost.Regex library. It compiles and executes regular expressions on strings. Some test I ran showed that it is not as fast as pcre, however Boost.Regex it is easier and more elegant to use in C++ programs. The program must be linked with -lboost_regex.
#include <stdlib.h>
#include <boost/regex.hpp>
#include <boost/lexical_cast.hpp>
int main()
{
// This regex is compiled at start-up and matches YYYY-MM-DD dates. If it
// contains a syntax error, the program aborts at start-up with an
// exception.
static const boost::regex
date_regex("(199[0-9]|200[0-9])-([1-9]|0[1-9]|1[012])-([1-9]|[0-2][1-9]|3[01])");
// First example: char* c-style input strings use boost::cmatch results.
{
const char *input_cstr = "2007-03-14";
boost::cmatch char_matches;
if (boost::regex_match(input_cstr, char_matches, date_regex))
{
// Convert the parsed number using boost's lexical_cast library
int year = boost::lexical_cast<int>( char_matches[1] );
// Or use the old way: get the std::string object, then it's char*
int month = atoi( char_matches[2].str().c_str() );
std::cout << "First example:"
<< " year " << year
<< " month " << month
<< " day " << char_matches[3] << "\n";
}
else
{
std::cout << "First example should have matched the regex.\n";
}
}
// Second example: STL strings use boost::smatch results.
{
std::string input_stlstr = "2007-03-34";
boost::smatch str_matches;
if (boost::regex_match(input_stlstr, str_matches, date_regex))
{
std::cout << "Second example shouldn't have matched the regex.\n";
}
else
{
std::cout << "Second example didn't match the regex. This was intended.\n";
}
}
// Third example: Temporary regex object and no capture results needed.
{
if (boost::regex_match("2007", boost::regex("(199[0-9]|200[0-9])")))
{
std::cout << "Third example matched the temporary regex object.\n";
}
else
{
std::cout << "Third example should have matched the regex.\n";
}
}
// Fourth example: regex_match matches the whole string while regex_search
// matches substrings just like perl.
{
std::string input = "Today is 2007-03-14, how are you?";
if (boost::regex_match(input, date_regex))
{
std::cout << "Fourth example (regex_match) shouldn't match.\n";
}
else
{
std::cout << "As expected, the fourth example (regex_match) didn't match.\n";
}
if (boost::regex_search(input, date_regex))
{
std::cout << "While the fourth example using regex_search did matched.\n";
}
else
{
std::cout << "Fourth example using regex_search should have matched the regex.\n";
}
}
}
C++ Code Snippet - Making a Custom Class ostream Outputable
Posted on 2007-03-01 14:47 by Timo at Permlink with Comments. Tags: c++ code-snippet
How to get a custom class to work with std::cout << obj; ? I for my part always forget the exact prototype of the required operator<<. Here is an minimal working example to copy code from:
struct myclass
{
int a, b;
myclass(int _a, int _b)
: a(_a), b(_b)
{ }
};
// make myclass ostream outputtable
std::ostream& operator<< (std::ostream &stream, const myclass &obj)
{
return stream << "(" << obj.a << "," << obj.b << ")";
}
int main()
{
myclass obj(42, 46);
std::cout << obj << std::endl;
}
NetFundamentals Seminar - Presentation Today
Posted on 2007-01-29 19:00 by Timo at Permlink with Comments. Tags: netfundamentals university talk
Following up on the technical report, today Dimitar and myself gave a 70min presentation on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation. It finished my work for the NetFundamentals seminar, which was organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. The seminar was very profound and extensively dug into the mathematics of six fundamental networking papers. Besides that it was great fun and opened some new horizons.
Our presentation can be downloaded as PDF (553 KB), with two slides per page or even with four per page.
Furthermore our listeners were given an equation sheet (139 KB) to aid them in following the many formulas.
NetFundamentals Seminar - Technical Report Finished
Posted on 2006-12-19 18:19 by Timo at Permlink with Comments. Tags: netfundamentals university
Today the technical report on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation was finished. It is part of my work for the NetFundamentals seminar organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. In the seminar six of the computer science papers most worth reading are reviewed and presented. The technical report was written by Dimitar Yordanov and myself and a presentation will follow.
The technical report can be downloaded as PDF (470 KB)
Abstract
One of the computer science papers most worth reading is Gallager's algorithm for minimum delay routing. The merit of Gallager's paper is its rigorous mathematical approach to a problem, which is more often taken care of using heuristics. The approach is founded on a well designed mathematical network model, which is custom-tailored to describe the minimum total delay routing problem. Mathematical observations on the model lead to two conditions for achieving global optimization, which are based on the marginal delay of links and neighbors. From these observations and conditions an iterative, distributed routing algorithm is naturally derived. Gallager finishes his analysis by proving in detail that the algorithm achieves total minimum delay routing. Algorithm and model are reviewed and illustrated in detail in this technical report.
QtSqlView 0.8.0 Released
Posted on 2006-10-10 12:56 by Timo at Permlink with Comments. Tags: qtsqlview c++
Released the first version 0.8.0 of QtSqlView under the GPL.
QtSqlView is a simple and easy to use SQL database browser written in Qt 4.x using the excellent QtSql components. Using QtSql drivers it can natively connect to MySQL, PostgreSQL and SQLite databases. Furthermore other database systems may be accessed using their ODBC drivers. QtSqlView is released under the GNU General Public License: source code and win32 binary may be downloaded here.
This short program was initially written for a set of windows users, who need to access and edit a PostgreSQL database. All this is possible with M$ Access and ODBC, but the configuration of PostgreSQL's ODBC driver and the ODBC DSN is far too complicated for the average database editor. Thus problem-free access of open-source databases was top priority for QtSqlView.
QtSqlView boasts the following features:
- Problem-free connecting to MySQL, PostgreSQL and SQLite databases on Windows.
- Add, delete and modify a list of database connections.
- Browse, edit, save and revert SQL tables, system tables and views of registered connections
- Copy selected cells as tab-separated text to the clipboard.
- View table schema including primary key.
- Execute custom SQL queries on the database connect and view results.
- SQL syntax highlighting in query editor.
- Uses Qt4's greatly improved SQL components.
You may download the source code for Linux/OSX or a setup package for Windows.
More screenshots are available as well.
SDIOS06 - Source Code and Ready-To-Run Image
Posted on 2006-09-14 09:26 by Timo at Permlink with Comments. Tags: sdios06 university c++
As promised the source code to SDIOS06 was released under the GPL.
SDIOS06 is a toy operating system developed during the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. It was designed and written by Timo Bingmann, Matthias Braun, Torsten Geiger and Andreas Mähler. Two games were ported to a custom SDL implementation using the VMware "hard"-ware: SDLjump and SuperTux. For more information and screenshots see my blog entry 20060727-SDI-Demo.
The source code archive was published on the L4Ka.org page: http://www.l4ka.org/projects/SDIOS06/
A local copy of the source archive (7.4 MB) is available as well. The README file contains a great deal of information about SDIOS06's design and modules. The complete source code can be browsed on the web.
To make demonstration as easy as possible a ready-to-run binary vmware image (3.8 MB) can be downloaded. The image contains SDIOS06 installed on a virtual vmware disk image. The VMware image can be run using the free VMware Player.
