Fast formatter

From: vonosan (5045-2h8p_at_[hidden])
Date: 2001-12-30 17:52:15

Hello,
I created very fast experimental implementation of formatter.
(http://groups.yahoo.com/group/boost/files/formatter/formatter.tar.gz)
For gcc-3.0 it is 1.1-1.3 slower compared with ostringstream
and as fast as ofstream. Only positional parameters in the
form %N are supported. Example:
  formatter fmt("%2, %1, %0");
  string s1 = fmt('0')(1)("two").str(); // 1
  cout << s1 << endl;
  string s2 = fmt('0')(1)("two");       // 2
  cout << s1 << endl;
  fmt('0')(1)("two").write(cout);       // 3
  cout << endl;
  cout << fmt('0')(1)("two") << endl;   // 4
   
Output:
  two, 1, 0
  two, 1, 0
  two, 1, 0
  two, 1, 0

All parameters are outputed using abstract_fmt_param class:
  class abstract_fmt_param
  {
  public:
    virtual write_spec(ostream &) const = 0;
    // ...
  };

There is one implementation of abstract_fmt_param for every type T:
  template<typename T> 
  class fmt_param : abstract_fmt_param 
  {
    const T & val_;
    virtual void write_spec(ostream_type & output) const 
    { 
      output << val_; 
    } 
    // ...
  }

Class formatter encapsulates simple hash table of fixed size
allocated in stack that hold pointers to abstract_fmt_param:
  class formatter
  {
    std::string str_; // format string
    mutable fmt_driver driver_;
    // ...
  };

  class fmt_driver // hash table and more
  { 
    enum { table_size = 32 };
    abstract_fmt_param * table_ [ table_size ];
    inline static size_t hash(size_t val) 
    { 
      return val % table_size; 
    } 
    // ...
  };
  
Don't be confused by this discourage name fmt_driver. This class
do two different things. I'm going to split it in the next release.
Now look at this generalized function call ended with write function:
  fmt('0')(1)("two").write(cout);
  
First operator() do this:
  template<typename T> 
  inline fmt_param<T>
  formatter::operator()(const T & val) const 
  { 
    driver_.init(str_.c_str()); 
    return fmt_param<T>(driver_, val); 
  } 
 
Quite simple. It clears hash table in init function and then
returns fmt_param object. Pointer to the beginning of the
format string is also passed to init function. This is second
responsibility of fmt_driver.

Following operators () are:
  template<typename T> 
  template<typename U>
  inline fmt_param<U>
  fmt_param<T>::operator()(const U & param) 
  { 
    driver_.insert(this); 
    return fmt_param<U>(driver_, param); 
  } 

This code is simple too.  It started with inserting _this_
pointer (implicitly casted to abstrct_fmt_param *)
to hash table and then returns fmt_param object for
the param.

At the end of operators () chain we have one temporary
fmt_param object for every parameter and all of them inserted
into hash map except the last one. Now all is prepared to
format:
  template<typename T>
  inline void fmt_param<T>::write(ostream_type & output) 
  { 
    driver_.insert(this); 
    fmt_parser parser(output, driver_); 
    parser.parse(); 
  } 
  
Last fmt_param inserted into hash table and parser parses:
 void fmt_parser::parse() 
 { 
   while(!is_end_())
   {
     // put normal text to the output_
     size_t param = get_param_(); // N returned for %N
     // let's find in hash table:
     if(const abstract_fmt_param * fp = driver_.find(param))
       fp->write_spec(output_); 
     // ...
   }
 } 
That all. Class fmt_param has also function str, operator std::string
and operator<<. All these operations use write function as a base.
Note that you should pass all parameters in one expression. I think
it's reasonable limitation for generalized function call concept.
-----------------
Alexander Nasonov