2010 Apr 02 - Fri

Checked Iterators in Microsoft Visual C++

I've wondered why some of my C++ programs seem to run slower than I think they should be running. Then I came across an article regarding Checked Iterators, and it become clearer to me where some of my execution speed issues could be. By default, in debug mode, all standard iterators are bounds checked. This checking can cause a slow down in execution speed when using standard iterators extensively.

The solution is to set certain macros to selectively enable and disable the checking on proven code. A Microsoft MSDN article on Checked Iterators describes the two symbols used for controlling the checked iterators feature:

• _SECURE_SCL: If defined as 1, unsafe iterator use causes a runtime error. If defined as 0, checked iterators are disabled. The exact behavior of the runtime error depends on the value of _SECURE_SCL_THROWS. The default value for _SECURE_SCL is 1, meaning checked iterators are enabled by default.
• _SECURE_SCL_THROWS: If defined as 1, an out of range iterator use causes an exception at runtime. If defined as 0, the program is terminated by calling invalid_parameter. The default value for _SECURE_SCL_THROWS is 0, meaning the program will be terminated by default. Requires _SECURE_SCL to also be defined.

2009 Oct 17 - Sat

Memory Leak Detection in MSVC 2008 C++

In Visual Studio, when building debug releases, I seem to recall that memory leak detection was automatically enabled. In Visual Studio 2008, memory leak detection is not automatically enabled. Code will need to be added to the source files to make it available.

Memory Leak Detection Enabling is a document in MSDN describing how to enable the ability. Basically, to enable the debug heap functions, include the following statements:

#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>

Immediately before the program exits, include the following function call:

_CrtDumpMemoryLeaks();

One commenter indicates that this only works best with C code, ie, C code will get discriptive comments, but C++ code will get cryptic memory reports.

In order to get the file and line number to work you need to manually redefine new in your code. This is done by undefining new, and redefining it to point to the debug versions that take a file and line number.

During debugging, in Windows based applications, std::cout no longer sends text into the IDE's Output window. Instead, the function OutputDebugString( "..." ) needs to be used.

2009 Oct 01 - Thu

Building Boost 1.40.0 on Debian Linux

Boost builds well on Linux. To get a clean build, I needed two libraries. With Python already installed, I needed to 'apt-get install python-dev'. The iostreams library needed the bzip2 libraries which can be installed through 'apt-get install libbz2-dev'.

After downloading bjam from sourcforge, my build then used:

bjam install --toolset=gcc --prefix=/usr/local --layout=tagged variant=debug threading=multi link=static

Instead of 'debug', 'release' can be used.

2009 Aug 19 - Wed

Boost Bind/Lambda replaced by Boost Spirit/Phoenix

Regular users of the C++ library known as Boost will already know about functors, lambda functions, and the like. These abilities mostly originate in the Boost.Bind and Boost.Lambda libraries.

As I'll soon be using the functor capability within my C++ programs, I wanted to make a 'note-to-self' regarding the fact that Boost.Bind and Boost.Lambda have basically been superceded by Boost.Spirit.Phoenix.

The Phoenix library has been accepted into Boost based upon Hartmut's summary of the Phoenix review.

The current incarnation of the Boost libraries is 1.39. Here is the Spirit User's Guide which includes a link to the Phoenix Documentation and a link to the Phoenix Users Guide.

It is noted that FC++ influenced Phoenix, and when looking at the FC++ web site, there is a reference to LC++, which is a Logic Programming language built atop of FC++. I wonder if something similar has been done atop of Phoenix.

An example from the Boost Mailing List of using Phoenix:

#include <vector>
#include <algorithm>
#include <boost/shared_ptr.hpp>
#include <boost/spirit/home/phoenix/core.hpp>

#include <boost/spirit/home/phoenix/operator.hpp>
#include <boost/spirit/home/phoenix/bind/bind_function.hpp>

struct A {};

void foo( const A& ) {}

int main()
{
   using namespace boost::phoenix;
   using namespace boost::phoenix::arg_names;

   std::vector< boost::shared_ptr< A > > vec;

   vec.push_back( boost::shared_ptr< A >( new A ) );

   std::for_each( vec.begin(), vec.end(),

                  bind( &foo, *arg1 ) );
   return 0;

}

Colorized with CodeColorizer.

2009 Aug 02 - Sun

Building HDF5 in Microsoft Visual Studio 2008

A while ago, I wrote an article about HDF Group's Hierarchical Data Format (HDF5) Library . In the article, there were some brief installation instructions. This article adds some refinements to the installation instructions.

You need to start by downloading the compression libraries:

• SZip 2.1 for VS2005
• ZLib 1.2 for VS2005

Create a sub-directory called 'compress' somewhere. In that sub-directory, create two additional sub-directories: 'include' and 'lib'.

Unzip the two downloads. From each of the two uncompressed libraries, put all the .lib and .dll files into the sub-directory .\compress\lib, and put all the .h files into the .\compress\include sub-directory.

In Windows, create two environment variables by going: Start->ControlPanel->System->Advanced->EnvironmentVariables, and then create two new user variables:

• HDF5_EXT_SZIP = szlibdll.lib
• HDF5_EXT_ZLIB = zlib1.lib

The remaining build instructions focus on building the useful HDF5 C++ libraries for HDF5 v1.9, with v1.9.43 being the latest as of this writing. Download /hdf5-1.9.43.tar.gz and expand it with 7-Zip into a working sub-directory called hdf5-1.9.43. Run .\hdf5-1.9.43\windows\copy_hdf.bat. Double click on .\hdf5-1.9.43\windows\proj\all\all.sln to open the Visual Studio Solution. The file is in version 2005. VS 2008 will ask to convert it for you. You'll need to do so.

After the conversion, go into Tools->Options->ProjectsAndSolutions->VC++Directories. Set 'Include Files' to the full path of your .\compress\include sub-directory, and set 'Library Files' to the full path of your .\compress\lib sub-directory.

For the project properties, choose whether you are doing a debug build or a release build. Do the build.

For v1.9.43, I found that there was one debug executable that wouldn't build, which, since I'm only interested in some key libraries, has no effect on my required outcome.

After the build process is complete, open a command prompt in .\hdf5-1.9.43, and run 'installhdf5lib.bat'. The various .dll, .lib, and .h files will be in \dll, \lib, and \include off of .\hdf5-1.9.43\hdf5lib.

From Sysinternals, download junction.exe. This allows you to create symbolic links between directories. Put the program somewhere in your path. Then use it to create a symbolic link from your existing project to the hdf5lib directory. This will allow you to change library versions with a simple symbolic link change. For example, something like the following will set a link to the include files where ever you installed and built the hdf5 libraries.

• junction hdf5 .\hdf5-1.9.43\hdf5lib

2009 Jul 29 - Wed

A Singleton Per Thread

A while ago, I had written about singletons, and how there isn't something straight-forward in Boost. Recently, I've seen references to a couple of interesting messages regarding not only singletons, but how to get a singleton per thread.

One starts by considering Boost Thread Local Storage and how to use it.

Then one can consider the concept of a thread-safe lazy singleton template class from the Boost Cookbook, which a singleton implementation not referenced in my other article.

Rutger ter Borg suggested the following untested possible code snippet:

template< typename Singleton >
Singleton& get_singleton() {
  static boost::thread_specific_ptr< Singleton > m_singleton;
  if ( !m_singleton.get() ) {
    m_singleton.reset( new Singleton() );
  }
  return *m_singleton;
}

2009 Apr 26 - Sun

Boost Preprocessor: Arrays

Typically, in some form of C++ best practice summaries, it is recommended to stay away from using the C++ Macro Preprocessor. For the most part, except when I needed to Microsoft MFC message maps, where use preprocessor macros, I have followed this maxim. Until now.

I came across a situation where one section of code is dependent upon the order of declarations in another section of code. With manual code preparation, and even if things are documented appropriately, it is easy to forget to update the inter-related sections of code properly.

An example is when initializing the column definitions of an MFC CListView. I'd like to construct an enumeration of column indexes and ensure those remain in-sync with any changes I may make to the CListView column defintions themselves.

I hadn't realized the power of the C++ macro preprocessor until I started reading Appendix A: An Introduction to Preprocessor Metaprogramming in the book "C++ Template Metaprogramming" by David Abrahams and Aleksey Gurtovoy.

By using the Boost Preprocessor Library, the power of the C++ Macro Preprocessor is realized.

I can now define my column structures and associated variables in a single header file. I also define various extraction macros.

#include "boost/preprocessor/tuple/elem.hpp"
#include "boost/preprocessor/array/elem.hpp"
#include "boost/preprocessor/array/size.hpp"
#include "boost/preprocessor/punctuation/comma_if.hpp"
#include "boost/preprocessor/repetition/repeat.hpp"


#define COLHDR_DELTAS_ARRAY_ELEMENT_SIZE 6
#define COLHDR_DELTAS_ARRAY \
  (15, \
    ( \
      (COLHDR_DELTAS_COL_UndSym, "UndSym", LVCFMT_LEFT,  50, std::string, m_sSymbolUnderlying), \
      (COLHDR_DELTAS_COL_Sym   , "Sym",    LVCFMT_RIGHT, 50, std::string, m_sSymbol), \
      (COLHDR_DELTAS_COL_Strk  , "Strk",   LVCFMT_RIGHT, 50, double,      m_dblStrike), \
      (COLHDR_DELTAS_COL_Expiry, "Expiry", LVCFMT_RIGHT, 50, ptime,       m_dtExpiry), \
      (COLHDR_DELTAS_COL_Bid   , "Bid",    LVCFMT_RIGHT, 50, double,      m_dblBid), \
      (COLHDR_DELTAS_COL_BidSz , "BidSz",  LVCFMT_RIGHT, 50, int,         m_nBidSize), \
      (COLHDR_DELTAS_COL_Sprd  , "Sprd",   LVCFMT_RIGHT, 50, double,      m_dblSpread), \
      (COLHDR_DELTAS_COL_Ask   , "Ask",    LVCFMT_RIGHT, 50, double,      m_dblAsk), \
      (COLHDR_DELTAS_COL_AskSz , "AskSz",  LVCFMT_RIGHT, 50, int,         m_nAskSize), \
      (COLHDR_DELTAS_COL_Pos   , "Pos",    LVCFMT_RIGHT, 50, int,         m_nPosition), \
      (COLHDR_DELTAS_COL_AvgCst, "AvgCst", LVCFMT_RIGHT, 50, double,      m_dblAverageCost), \
      (COLHDR_DELTAS_COL_Delta , "Delta",  LVCFMT_RIGHT, 50, double,      m_dblDelta), \
      (COLHDR_DELTAS_COL_Gamma , "Gamma",  LVCFMT_RIGHT, 50, double,      m_dblGamma), \
      (COLHDR_DELTAS_COL_UnRlPL, "UnRlPL", LVCFMT_RIGHT, 50, double,      m_dblUnrealizedPL), \
      (COLHDR_DELTAS_COL_RlPL  , "RlPL",   LVCFMT_RIGHT, 50, double,      m_dblRealizedPL) \
      ) \
    ) \
  /**/

#define COLHDR_DELTAS_EXTRACT_COL_DETAILS(z, n, m, text) \
  BOOST_PP_TUPLE_ELEM( \
    COLHDR_DELTAS_ARRAY_ELEMENT_SIZE, m, \
      BOOST_PP_ARRAY_ELEM( n, COLHDR_DELTAS_ARRAY ) \
    )

#define COLHDR_DELTAS_EXTRACT_ENUM_LIST(z, n, text) \
  BOOST_PP_COMMA_IF(n) \
  COLHDR_DELTAS_EXTRACT_COL_DETAILS( z, n, 0, text )

#define COLHDR_DELTAS_EMIT_InsertColumn( z, n, VAR ) \
  m_vuDeltas.InsertColumn( VAR++, \
    _T(COLHDR_DELTAS_EXTRACT_COL_DETAILS(z, n, 1, ~)), \
    COLHDR_DELTAS_EXTRACT_COL_DETAILS(z, n, 2, ~), \
    COLHDR_DELTAS_EXTRACT_COL_DETAILS(z, n, 3, ~) \
    );

#define COLHDR_DELTAS_EMIT_DefineVars( z, n, text ) \
  COLHDR_DELTAS_EXTRACT_COL_DETAILS(z, n, 4, ~) \
  COLHDR_DELTAS_EXTRACT_COL_DETAILS(z, n, 5, ~)\
  ;

Then in my class declaration, I can extract the enumerations in the correct 0-based order:

  enum enumColHdrDeltasCol {
    BOOST_PP_REPEAT( BOOST_PP_ARRAY_SIZE( COLHDR_DELTAS_ARRAY ), COLHDR_DELTAS_EXTRACT_ENUM_LIST, ~ )
  };

The repetitive code of creating the columns in the CListView is handled through repetition and extraction macros:

  int ix = 0;
  BOOST_PP_REPEAT( BOOST_PP_ARRAY_SIZE( COLHDR_DELTAS_ARRAY ), COLHDR_DELTAS_EMIT_InsertColumn, ix )
  // m_vuDeltas.InsertColumn( ix++, "UndSym", LVCFMT_LEFT, 50 );

I'll be able to further use the initial structure to create the row factory for keeping the CListView and row-structures synchronized. If I happen to change my mind on column ordering, all related code sections are automatically updated.

2009 Jan 02 - Fri

Wanted: A Single C++ Singleton

The Singleton Concept is a reasonably simple concept. For writing software, the concept of a singleton stipulates that only one instance of a class will be instantiated during run time. All references to an object of a particular class will be to only one instance. The instance is usually created at program startup, often times before 'main', and destroyed at programs end, often after 'main' exits.

I wish to use the concept of a Singleton in my C++ based trading software for Manager classes which keep track of Providers, Instruments, and Portfolios.

Thinking that the Singleton Design Pattern was simple, I figured I could implement my own flavour. But I decided to do some research first. It turns out there are simple ways, complicated ways, and controversial ways.

From the controversial side, some consider using Singletons as less than desirable, as the concept introduces global state, which in turn reduces modularity, compartmentalization, and as a consequence increases the complexity of testing. These are valid reasons, and I see it being applicable to situations where a programmer uses Singletons for small objects or built-in data types.

In my situation, I wish to form Singletons of larger self-contained classes. It doesn't make logical sense to have multiple managers, and as such, the Singleton concept enforces/implmements my need for singleton managers.

With the Boost Libraries being as comprehensive and well written as they are, I figured they should offer up a good singleton of a Singleton implementation. Nope. In doing a search through the library, I find about four or six or more different flavours of singleton.hpp, and nothing in the 'common areas' of the library:

• boost/serialization/singleton.hpp: uses boost::noncopyable, has medium multi-threading capability, and contains some .dll dependencies
• boost/log/detail/singleton.hpp: uses boost::noncopyable, is a simpler class, not sure if it is thread safe, and makes use of #defines like BOOST_ONCE_INIT
• boost/pool/detail/singleton.hpp: a simple, self-contained class designed for instantiation before main, basically a type of Meyer's Singleton but using a template mechanism
• boost/thread/detail/singleton.hpp: a very minimalistic singleton

There are notes in some locations indicating that these shouldn't be used as they are essentially 'library internal' routines and are subject to non-documented changes.

hmmm, maybe Singletons are complicated. Alex Ott's Blog mentioned that there was actually a Singleton submission (documentation) to Boost back in the beginning of 2008. The submission promised to handle single threaded and multi-threaded implementations of the Singleton Pattern. It was rejected. Reviewers wanted to see a more modularized approach. The submitter indicated that he has/had run out of time to do so. In reading the review thread, a number of writers didn't like the complexity of the Loki library, and thus the Boost submission took a different tact. I'm of an impression that the library submission would have a good change of succeeding if it followed the 'programming by policy' method used in Loki. Under the hood there is some complexity, but to the user, the interface is clean and modular. For those interested in the submission code, It resides mouldering in the sandbox.

Loki, which was started by Andrei Alexandrescu in his book on "Modern C++ Design", has a Singleton implementation, but no on-line documentation. I went into his book and I see that he goes into some detail on the design ideas and usage notes regarding his Loki SingletonHolder class. Indeed, he says that there is no single size-fits-all singleton. And when looking at the doxygen class notes, there is a variety of construction, lifetime, and threading template traits available. Perhaps this file could be spruced up and submitted to Boost.

Andrei and Scott Meyers wrote a paper back in September 2004 called C++ and the Perils of Double-Checked Locking. It goes into the gory details of why multi-threaded Singletons are so hard to implement. Much of it has to do with compiler optimizations, and the fact that C++ machine states are defined for single threaded models only. It is interesting to note that implication that C++ is really multi-threaded, from a philosophical and design perspecitve. It has been forced into that world with assemlby code and operating system api work arounds. C++ has been so malleable when it comes to metaprogramming, object oriented programming, and any of a number of other programming paradigms. To fall down on the job of multi-threading may be an indication of the difficulties inherent in moving from single-threading to multi-threading and multi-core processing.

In addition to the library submitted to Boost, another author offers up his version of a Thread-Safe C++ Singleton. His writing indicates he uses the concept of a Phoenix Singleton, a Singleton which can recreate itself. The book Modern C++ Design goes into a description of this.

For a simple, single-threaded, self contained Singleton which manages itself, a C++ Singleton Pattern is available. It uses the Curiously Recurring Template Pattern (CRTP). It uses an override of new and delete but does not use reference counting to keep things straight, which may cause problems in some use cases. It is like a Phoenix Singleton but doesn't really do LIFO type creation/destruction properly.

Scott Meyer's "Effective C++ Third Edition" has a description of what has been termed Meyer's Singleton. It does all the constructor, destructor, and assignment hiding and provides a built-in static method for returning a reference to the object instance. Here is a specific version of The Meyers Singleton.

class InstrumentManager {
public:
  static InstrumentManager &Instance() {
    static InstrumentManager _InstrumentManager;  // local static object initialization
    return _InstrumentManager;
  }
  void BasicMethod( void );
private:
  InstrumentManager();  // constructor (ctor) is hidden
  InstrumentManager( InstrumentManager const & );  // copy ctor is hidden
  InstrumentManager &operator=( InstrumentManager const & );  // assignment operator is hidden
  ~InstrumentManager()  // destructor (dtor) is hidden
};

A Generic Meyers Singleton:

// singleton.h
#ifndef __SINGLETON_H
#define __SINGLETON_H

template class CSingleton {
public:
  static T& Instance() {
    static T _instance;
    return _instance;
  }
protected:
private:
  CSingleton();          // ctor hidden
  ~CSingleton();          // dtor hidden
  CSingleton(CSingleton const&);    // copy ctor hidden
  CSingleton& operator=(CSingleton const&);  // assign op hidden
};

#endif

In summary, I think I'll end up using the boost::detail::pool as it can be used to wrap general classes without resorting to writing classes as specific Meyers Singletons, which may or may not be a good thing. If, at some point in the future, I get some free time, tackling the Loki Singleton to Boost Singleton conversion might be an interesting learning experience.

See also Singleton Per Thread.

2008 May 29 - Thu

Evaluating Inter-Process Communication Frameworks

I'm reposting some comments regarding IPC frameworks that I made to the Boost-Users listserve today. It is in response to someone making unsubstantiated remarks regarding the relative merits of ACE and Boost, and another looking for some substatiated remarks. What follows are some substantiated remarks, based upon my personal experience with it and several other libraries.

I've started working on a number of distributed system projects. As a consequence, I started looking for distributed system libraries. References to ACE were most pervasive. I implemented a number of trial applications with the library. That was after plowing through relevant sections in the three primary ACE reference books. That was a good learning experience, if only to find out the various patterns in distributed architecture definition. I had the inter-process/inter-server communications (which only sent simple stuff) working well within ACE's Acceptor/Connector framework. ACE has a number of other patterns one can use. I was really impressed with the fact that the examples I used from the books worked as advertised, and I was able to bend them to my will.

ACE is based upon an interaction of classes, macros, and templates. One has to spend some time with the environment in order to become proficient with it. It has a large API. A number of lower level API's upon which higher level API's are based. For example the Acceptor/Connector uses constructs described earlier in the books.

Once I had my basic communications going, I realized I needed to get some form concrete messaging infrastructure in place. I had an impression that TAO, which is a layer above ACE, would be quite extravagant to implement, with it being an implementation of the CORBA specification. I wanted something a little lighter (a whole lot lighter actually).

As I worked through that project, I started hearing about ASIO, indirectly through some other libraries I was using. ASIO is now a member of Boost. I read a review somewhere that ASIO is a 'modern' replacement for ACE. If you want to get into real template structures and Boost oriented philosophy, I'd say that is a valid statement. I'd also say that ASIO is 'more to the point' and straight forward than is ACE, at least for the things I want to accomplish. But like ACE, ASIO is the basic communications infrastructure, no real messaging capability, which is what distributed computing is all about. ASIO turned out to be a little harder to get my head wrapped around as it uses a number of advanced C++ and Boost related idioms. For a run-of-the-mill C++ programmer, ACE would be better. For someone steeped in the power and obscurity of advanced C++, and is looking to advance their skill set, ASIO would be better.

I came across RCF - Interprocess communication for C++, which is a messaging framework riding atop of ASIO. Flexible, lightweight, and to the point. I worked through the examples and things worked as advertised. It has the encryption, publisher/subscriber, oneway/twoway idioms, and a few other nifty features.

At the same time I was doing that, seemingly coincidently, I learned a few more interesting facts. Going into this, I realized that I need a message dispatcher/proxy, some decent failover techniques, and some additional event handling for non-IPC related activities.

Someone suggested ICE from www.zeroc.com for an RCF-like solution, but working to a larger scale. I've heard that the library's originator is someone who spent much time on CORBA standards and redid the concept without the 'benefit' of committee involvement. I think the library has all the bases covered in terms of lightweight message handling, dispatching, resiliency, and higher level distributed processing philosophies. The drawback is that it will have a steeper learning curve than would an implementation using RCF. I like RCF, but I think I.m going to have to tilt towards ICE (itself, like RCF, developed and focused towards C++ in a multiple license environment).

On the non-IPC front, Qt's QCoreApplication looks to be a good substrate on which to build event driven daemons.

In the end, I think my solutions are going to involve:

• ZeroC's ICE for primary inter-process communications
• Qt QCoreApplication as a base for daemon development (which has built-in stuff for threads/locks, slots/signals)
• Wt, a C++ based web toolkit for distributed GUI development
• Boost Libraries to fill in all the holes
• a little legacy layer 3/4 ACE in one library I'm using, but with some work, I think I can convert the ACE stuff to ASIO

2008 May 25 - Sun

A Keyword Matching Algorithm

There are a number of well known algorithms out there for taking in a set of keywords and matching them against test. Aho and Corasick comes to mind, as does the Wu Manber algorithm (the latter I've implemented, and the code resides elsewhere on this site).

For another project, I didn't need something quite so fancy. Actually two projects come to mind. One is that I have a input comma separated value file which includes stock symbols, a description, and the associated exchange. I wanted to keep statitics on what is read in on an exchange basis. My first kick at the can on this was to implement a string look up table using

In another part of the file, to do some special computing, and in a fit of late night programming, I went so far as to implementing a multi-stage strcmp on each exchange to do something special for each.

I knew from the outset, that would be horribly inefficient, but I didn't have a nice algorithm at hand to do it with.

After being reminded of Aho Corasick in another context, I decided to take another stab at improving efficiency. I ended up implementing half of Aho Corasick's algorithm, the 'go' function. Since I'm always matching from the beginning of the string, and am not stepping through text, the exclusion of the 'fail' function works quite well, and keeps the code smaller.

At some point in time the code can be coverted to something using templates in order to accept various string types, various element matches, and return codes.

Since the 'fail' function isn't implemented, the lookup table can be updated dynamically without being rebuilt from scratch.

The library is quite easy to use. With AddPattern, add new keywords along with some sort of index or object. When using FindMatch with the target keyword, the appropriate object will be returned on a successful match. If no match is found NULL will be returned. A modification to the class would add a default object for use when no matches are found.

Here is the header file.

#pragma once

// Copyright (2008) Ray Burkholder
// Matching against multiple keywords

#include <vector>
#include <string>

class CKeyWordMatch {
public:
  CKeyWordMatch(void);
  virtual ~CKeyWordMatch(void);
  void ClearPatterns( void );
  void AddPattern( const std::string 
&sPattern, void *object );
  void *FindMatch( const std::string 
&sMatch );
protected:
  struct structNode {
    size_t ixLinkToNextLevel;  // next letter of same word
    size_t ixLinkAtSameLevel;  // look for other letters at same location
    void *object;  // upon match, (returned when 
keyword found)
    char chLetter;  // the letter at this node
    structNode() : ixLinkToNextLevel( 0 ), ixLinkAtSameLevel( 0 ), 
      object( NULL ), chLetter( 0 ) {};
  };
  std::vector<structNode> m_vNodes;
private:
};

Here is the code file:

#include "StdAfx.h"
#include "KeyWordMatch.h"

// Copyright (2008) Ray Burkholder
// Matching against multiple keywords

#include <stdexcept>

CKeyWordMatch::CKeyWordMatch(void) {
  ClearPatterns();
}

CKeyWordMatch::CKeyWordMatch(size_t size) {
  m_vNodes.reserve( size );
  ClearPatterns();
}

CKeyWordMatch::~CKeyWordMatch(void) {
  m_vNodes.clear();
}

void CKeyWordMatch::ClearPatterns() {
  m_vNodes.clear();
  structNode node;
  m_vNodes.push_back( node ); // root node with nothing
}

void CKeyWordMatch::AddPattern( 
              const std::string &sPattern, void *object ) {
  std::string::const_iterator iter = sPattern.begin(); 
  if ( sPattern.end() == iter ) {
    throw std::runtime_error( "zero length pattern" );
  }
  size_t ixNode = 0;
  size_t ix;
  bool bDone = false;
  while ( !bDone ) {
    char ch = *iter;
    ix = m_vNodes[ ixNode ].ixLinkToNextLevel;
    if ( 0 == ix ) { // end of chain, so add letter
      structNode node;
      node.chLetter = ch;
      m_vNodes.push_back( node );
      ix = m_vNodes.size() - 1;
      m_vNodes[ ixNode ].ixLinkToNextLevel = ix;
      ixNode = ix;
    }
    else { // find letter at this level
      //ix = m_vNodes[ ixNode ].ixLinkToNextLetter;  // already set
      bool bLevelDone = false;
      size_t ixLevel = ix;  // set from above
      while ( !bLevelDone ) {
        if ( ch == m_vNodes[ ixLevel ].chLetter ) { 
          // found matching character
          ixNode = ixLevel;
          bLevelDone = true;
        }
        else {
          // move onto next node at this level to find character
          size_t ixLinkAtNextSameLevel 
            = m_vNodes[ ixLevel ].ixLinkAtSameLevel;
          if ( 0 == ixLinkAtNextSameLevel ) {
            // add a new node at this level
            structNode node;
            node.chLetter = ch;
            m_vNodes.push_back( node );
            ix = m_vNodes.size() - 1;
            m_vNodes[ ixLevel ].ixLinkAtSameLevel = ix;
            ixNode = ix;
            bLevelDone = true;
          }
          else {
            // check the new node, nothing to do here
            // check next in sequence
            ixLevel = ixLinkAtNextSameLevel;
          }
        }
      }
    }
    ++iter;
    if ( sPattern.end() == iter ) {
      if ( NULL != m_vNodes[ ixNode ].object ) {
        std::runtime_error( "Pattern already present" );
      }
      m_vNodes[ ixNode ].object = object;  // 
assign and finish
      bDone = true;
    }
  }
}

void *CKeyWordMatch::FindMatch( const std::string &sPattern ) {
  // traverse structure looking for matches
  std::string::const_iterator iter = sPattern.begin(); 
  if ( sPattern.end() == iter ) {
    throw std::runtime_error( "zero length pattern" );
  }
  void *object = NULL;
  size_t ixNode = 0;
  size_t ix;
  bool bOpFound = true;
  bool bDone = false;
  while ( !bDone ) {
    char ch = *iter;
    ix = m_vNodes[ ixNode ].ixLinkToNextLevel;
    if ( 0 == ix ) {
      bDone = true;  // no more matches to be found so exit
    }
    else {
      // compare characters at this level
      bool bLevelDone = false;
      size_t ixLevel = ix;  // set from above
      while ( !bLevelDone ) {
        if ( ch == m_vNodes[ ixLevel ].chLetter ) {
          ixNode = ixLevel;
          bLevelDone = true;
        }
        else {
          ixLevel = m_vNodes[ ixLevel ].ixLinkAtSameLevel;
          if ( 0 == ixLevel ) {  // no match so end 
            bLevelDone = true;
            bDone = true;
          }
        }
      }
    }
    ++iter;
    if ( sPattern.end() == iter ) {
      object = m_vNodes[ ixNode ].object;
      bDone = true;
    }
  }
  return object;
}

2008 May 23 - Fri

RCF - Interprocess Communications for C++

For a couple of distributed computing projects, I've been trying to come up with a feasible and easy to use method for making applications talk to each other, whether they be on the same machine or across a network.

I started off doing some work with Douglas C. Schmidt's ACE: The ADAPTIVE Communication Environment. I plowed through ACE's three primary programming books to see what would be the best bit of the environment I would need. I ended up implementing a demo with the Acceptor - Connector framework, just to see how things worked.

I then started on thinking on the messaging structure and the event handling structures. ACE's mixture of macros and classes turned out to be a little overwhelming for what I wanted to accomplish.

During my stint with ACE, I started to use ASIO, from the Boost libraries. I was first introduced to ASIO through working with WT: WebToolKit. I used Wt as a frontend to a voip call sign in server.

The next step in the evolution is to present a real time call summary report to authorized management as the calls are authenticated, authorized, and accounted for from a Radius server. This means sending call detail messages from the Radius server to a central dispatch server, and then publish to active web clients (with the clients written with Wt).

As Wt uses ASIO for its underlying network communications, and I had read a remark somewhere that ASIO is the new improved ACE, I started to look into it as the mechanism for my inter-process communications. I even got a good chunk of messaging infrastructure written as was about to get it testing when I found it was all for nought.

I came across RCF - Interprocess Communications for C++. It is a library that has been in development for the last few years by a talented fellow by the name of Jarl Lindrud. The library has implemented all the stuff that I only dreamed about doing: publish/subscribing, stream encryption, payload filtering, and any number of other nifty features.

I had a few painful moments in getting the library built. After a couple of messages back and forth to the author, I realized I was trying to build the whole thing into a static library rather than using an 'include' technique to get the platform specific files built.

The client and server examples built and ran without a hitch. I must admit that I was impressed by the examples in the ACE books as well: they compiled and ran with little or no messing about.

The RCF library is better because it deals with serializing native values back and forth, something that ACE only accomplishes when you get into the TAO and CORBA levels of the environment.

So now with Boost (which includes ASIO), RCF (which uses ASIO), and Wt (which also uses ASIO), I think I have all the interprocess tools I need to make my modules talk to each other. Now I can get on with the meat of my projects.

2008 Mar 26 - Wed

C++ Custom Containers and Iterators

I'm using the HDF5 File System for holding time series information. Rather than writing my own binary search implementation to find particular elements within a particular saved time series, I thought it would be clever if I designed the interface so I could use the Standard Template Library's 'find' iterator. If I can make the STL's 'find' work, then all the other iterators should work just as well, and thus I'll have an easy mechanism to access time series with very little programming involved.

I can find any number of web sites containing information on how to work with C++'s standard containers and iterators. When it comes to finding information on custom containers and iterators, the information is not quite so plentiful.

The first article I came across was one from TechRepublic called Extending the C++ STL with custom containers. It didn't quite have the meat I was expecting.

Bjarne Stroustrup's book, The C++ Programming Language, does have a section on iterators and a section on containers. In retrospect, they are quite good introductions to the concept, but I didn't feel the examples were as informative as I would have liked.

Microsoft's MSDN has an article called C++ and STL: Take Advantage of STL Algorithms by Implementing a Custom Iterator, but this article only covers the custom iterator side of things, it doesn't discuss how it would interact with a custom container.

Dr. Dobbs inherited an article entitled Custom Containers & Iterators for STL-Friendly Code: A pair of approaches for creating custom containers from the March 2005 issue of C++ Users Journal. Some code extracts are included but there are some pieces missing, such as the begin() and end() methods and how they are put together. The link in the article to the original code no longer works. However, I did find that I have the Dr. Dobbs Developer Library DVD Release 4. On it resides the full example code. That was much more informative.

Now that I have a better understanding for what I'm looking, I see that the STL compliant container example has some useful information. In the same vein, CodeProject has another example: An STL compliant sorted vector.

Finally, I came across Ulrich Breymann's book called Desiging Components with the C++ STL. It provided all the necessary background to pull it all together. I always thought there was more to it, but custom containers and iterators may not be so hard after all. Once I have the code finished, I'll try to have it posted one way or another.