sid/include/sidmiscutil.h

   1 // sidmiscutil.h - Useful utility classes.  -*- C++ -*-
   2
   3 // Copyright (C) 1999-2003, 2006, 2007 Red Hat.
   4 // This file is part of SID and is licensed under the GPL.
   5 // See the file COPYING.SID for conditions for redistribution.
   6
   7 #ifndef SIDMISCUTIL_H
   8 #define SIDMISCUTIL_H
   9
  10 #include <sidconfig.h>
  11 #include <sidpinutil.h>
  12
  13 #include <string>
  14 #include <iostream>
  15 #include <fstream>
  16 #include <vector>
  17 #include <map>
  18 #include <cassert>
  19 #include <cctype>
  20 #include <cerrno>
  21 #include <cstring>
  22 #ifdef __CYGWIN__
  23 #include <sys/cygwin.h>
  24 #endif
  25 // XXX: kludge for compatibility both with old & new libstdc++
  26 #if STD_CCTYPE
  27 #define STDCTYPE(func) std::func
  28 #else
  29 #define STDCTYPE(func) func
  30 #endif
  31
  32 #include <limits.h>
  33 #include <stdio.h>
  34 #include <stdarg.h>
  35
  36 using std::string;
  37 using std::vector;
  38
  39 namespace sidutil
  40 {
  41   // Instances of this class template function as bidirectional lookup
  42   // tables (bijections) for mapping objects to each other by value.
  43   template <class Obj1, class Obj2>
  44   class bijection
  45   {
  46     typedef std::map<Obj1,Obj2> forward_t;
  47     typedef std::map<Obj2,Obj1> backward_t;
  48     mutable forward_t forward;
  49     mutable backward_t backward;
  50
  51   public:
  52
  53     // Find Obj2 by Obj1.
  54     bool
  55     find(const Obj1& one, Obj2& two) const
  56       {
  57         typename forward_t::const_iterator it = this->forward.find(one);
  58         if (it != this->forward.end())
  59           {
  60             typename backward_t::const_iterator ti = this->backward.find(it->second);
  61             assert (ti != this->backward.end());
  62             two = it->second;
  63             return true;
  64           }
  65         else
  66           return false;
  67       }
  68
  69     // Find Obj1 by Obj2.
  70     bool
  71     find(const Obj2& two, Obj1& one) const
  72       {
  73         typename backward_t::iterator ti = this->backward.find(two);
  74         if (ti != this->backward.end())
  75           {
  76             typename forward_t::const_iterator it = this->forward.find(ti->second);
  77             assert (it != this->forward.end());
  78             one = ti->second;
  79             return true;
  80           }
  81         else
  82           return false;
  83       }
  84
  85     // Register Obj1<->Obj2 pair.  Both must be unique.
  86     void
  87     add (const Obj1& one, const Obj2& two)
  88       {
  89         assert (this->forward.find(one) == this->forward.end());
  90         this->forward[one] = two;
  91         assert (this->backward.find(two) == this->backward.end());
  92         this->backward[two] = one;
  93       }
  94
  95     // Register Obj1<->Obj2 pair.  Both must be unique.
  96     void
  97     add (const Obj2& two, const Obj1& one)
  98       {
  99         this->add (one, two);
 100       }
 101
 102     void
 103     erase_all ()
 104       {
 105         this->forward.erase(this->forward.begin(), this->forward.end());
 106         this->backward.erase(this->backward.begin(), this->backward.end());
 107       }
 108   };
 109
 110
 111   // This class, a possible mix-in, may be used to limit the number of
 112   // levels of recursion of functions.  It functions as a counter that
 113   // trips an assert() failure if it is made to exceed a configured
 114   // limit.  A limit of 0 is nonsensical and disallowed by assertion.
 115   class recursion_limited
 116   {
 117     friend class recursion_record;
 118
 119     // XXX: might be nice to be signal-safe.
 120     int count;
 121     int max;
 122     std::string label;
 123
 124   protected:
 125     // These functions are for use by recursion_record instances
 126
 127     void recursion_enter ()
 128       {
 129         if (this->count <= this->max)
 130           this->count ++;
 131         if (! ok())
 132           std::cerr << label << ": recursion limit exceeded (" << this->count << ")" << std::endl;
 133       }
 134
 135     void recursion_exit ()
 136       {
 137         if (this->count > 0)
 138           this->count --;
 139         else
 140           std::cerr << label << ": recursion limit underflow (" << this->count << ")" << std::endl;
 141       }
 142
 143     bool ok () const
 144       {
 145         return (this->count >= 0 && this->count <= this->max);
 146       }
 147
 148   public:
 149     static const unsigned default_recursion_limit = 1000;
 150
 151     recursion_limited (const std::string& l,
 152                        int m = default_recursion_limit): count(0), max(m), label(l)
 153       {
 154         assert (this->max > 0);
 155       }
 156   };
 157
 158
 159   // Each instance of the recursion_record class, during its lifetime,
 160   // occupies one spot in a designated recursion_limited object's
 161   // slot.  Merely instantiate an instance of this type in any block
 162   // that may suffer from indefinite recursion.
 163   class recursion_record
 164   {
 165     recursion_limited* limiter;
 166
 167   public:
 168     recursion_record (recursion_limited* l): limiter(l)
 169       {
 170         this->limiter->recursion_enter ();
 171       }
 172
 173      bool ok () const
 174       {
 175         return (this->limiter->ok());
 176       }
 177
 178     ~recursion_record ()
 179       {
 180         this->limiter->recursion_exit ();
 181       }
 182   };
 183
 184
 185
 186   // The string2stream and stream2string classes may be used as
 187   // wrappers around string values to transmit them to/from streams.
 188   // Normal string stream-in operators break on word boundaries.
 189   // These wrappers encode arbitrary strings safely.
 190   // Use as follows:
 191   //
 192   // ostream o;
 193   // string s = "anything at all";
 194   // o << string2stream(s);
 195   //
 196   // istream i;
 197   // string s;
 198   // i >> stream2string(s);
 199
 200   struct string2stream
 201   {
 202     const std::string& sendme;
 203     friend std::ostream& operator << (std::ostream& o, const string2stream& it);
 204   public:
 205     string2stream (const std::string& s): sendme(s) {}
 206   };
 207
 208
 209   inline std::ostream&
 210   operator << (std::ostream& o, const string2stream& it)
 211     {
 212       o << '"';
 213       for (unsigned i=0; i<it.sendme.length(); i++)
 214         {
 215           char c = it.sendme[i];
 216           char hex[] = "0123456789ABCDEF";
 217           if ((isprint(c)) && (! isspace(c)) && (c != '%'))
 218             // NB: character class must not include '%' itself, and must
 219             // include only chars that iostream>>std::string would consider
 220             // parts of a single string.
 221             o << c;
 222           else
 223             // print URL-encoded char
 224             o << "%" << hex[(c >> 4) & 0x0f] << hex[c & 0x0f];
 225         }
 226       o << '"';
 227       return o;
 228     }
 229
 230   struct stream2string
 231   {
 232     std::string& parseme;
 233     friend std::istream& operator >> (std::istream& i, const stream2string& it);
 234   public:
 235     stream2string (std::string& s): parseme(s) {}
 236   };
 237
 238
 239   inline std::istream&
 240   operator >> (std::istream& i, const stream2string& it)
 241     {
 242       std::string encoded;
 243       i >> encoded;
 244       it.parseme = "";
 245
 246       unsigned j;
 247       for (j=1; j<encoded.length()-1; j++)  // ignore double-quote delimiters
 248         {
 249           char c = encoded[j];
 250           if (c != '%')
 251             it.parseme += c;
 252           else if (j < encoded.length() - 3) // limiting case:  "......%DD"
 253             {
 254               char c1 = toupper (encoded[++j]);
 255               char c2 = toupper (encoded[++j]);
 256
 257               // hex decoding
 258               unsigned d1 =
 259                 (c1 >= '0' && c1 <= '9') ? (c1 - '0') :
 260                 (c1 >= 'A' && c1 <= 'F') ? (c1 - 'A' + 10) :
 261                 (j = encoded.length(), 0); // error: detected just before exit
 262               unsigned d2 =
 263                 (c2 >= '0' && c2 <= '9') ? (c2 - '0') :
 264                 (c2 >= 'A' && c2 <= 'F') ? (c2 - 'A' + 10) :
 265                 (j = encoded.length(), 0); // error: detected just before exit
 266
 267               char cc = (d1 << 4) | d2;
 268               it.parseme += cc;
 269             }
 270           else
 271             break;
 272         }
 273
 274       // set flag on parse error
 275       if (j != encoded.length() - 1)
 276         i.setstate(std::ios::badbit);
 277
 278       return i;
 279     }
 280
 281
 282   // Tokenize a string.  Use given set of separator characters.
 283   inline std::vector<std::string>
 284   tokenize (const std::string& str, const std::string& sep)
 285     {
 286       std::vector<std::string> tokens;
 287       std::string remainder = str;
 288
 289       while (remainder.size() > 0)
 290         {
 291           std::string::size_type sep_pos = remainder.find_first_of (sep);
 292           if (sep_pos == std::string::npos) // no more tokens
 293             {
 294               tokens.push_back (remainder);
 295               break;
 296             }
 297           else
 298             {
 299               tokens.push_back (remainder.substr (0, sep_pos));
 300               // trim token
 301               remainder = remainder.substr (sep_pos);
 302               // trim to next non-separator
 303               sep_pos = remainder.find_first_not_of (sep);
 304               if (sep_pos == std::string::npos) // none?
 305                 {
 306                   tokens.push_back ("");
 307                   break;
 308                 }
 309               remainder = remainder.substr (sep_pos);
 310             }
 311         }
 312       return tokens;
 313     }
 314
 315
 316   inline std::string
 317   std_error_string ()
 318     {
 319       const char* error_message = "(unknown error)";
 320 #ifdef HAVE_STRERROR
 321       error_message = strerror (errno);
 322 #endif
 323       return std::string(error_message);
 324     }
 325
 326
 327   // Return a vector of directory names, where the SID_LIBRARY_PATH
 328   // and SID_EXEC_PREFIX environment variables are pointing.  Convert
 329   // all paths to POSIX form on Cygwin.
 330   inline std::vector<std::string>
 331   sid_file_search_path ()
 332   {
 333     std::vector<std::string> search_directories;
 334
 335     char* slp = getenv ("SID_LIBRARY_PATH"); // run-time configuration
 336     if (slp)
 337       {
 338         search_directories = tokenize (slp, ":");
 339       }
 340
 341     char* sep = getenv ("SID_EXEC_PREFIX"); // install-time configuration
 342 #ifdef __CYGWIN__
 343     char conv_fn[PATH_MAX*2];
 344     if (sep)
 345       {
 346         int rc = cygwin_conv_to_full_posix_path (sep, conv_fn);
 347         if (rc != 0)
 348           std::cerr << "sid_file_search_path: cygwin_conv_to_full_posix_path failed: "
 349                     << std_error_string () << std::endl;
 350         else
 351           sep = conv_fn;
 352       }
 353 #endif
 354     if (!sep) sep = SID_EXEC_PREFIX; // build-time configuration
 355     // We really just want to get to pkgdatadir, which is $prefix/share
 356     // Guess exec-prefix == prefix
 357     std::string pkglibdir1 = std::string(sep) + std::string("/share");
 358     search_directories.push_back (pkglibdir1);
 359     // Guess exec-prefix == prefix/H-HOST
 360     std::string pkglibdir2 = std::string(sep) + std::string("/../share");
 361     search_directories.push_back (pkglibdir2);
 362
 363     return search_directories;
 364   }
 365
 366
 367   // Look around cwd, the standard search dirs (.../sid)
 368   // At worst, return the given name.
 369   inline std::string
 370   find_sid_data_file (const std::string& file)
 371   {
 372     std::vector<std::string> file_path = sid_file_search_path ();
 373     std::vector<std::string> path;
 374
 375     path.push_back (std::string("")); // no prefix
 376     for (unsigned i=0; i<file_path.size(); i++)
 377       path.push_back (file_path[i] + std::string("/sid/"));
 378
 379     for (unsigned i=0; i<path.size(); i++)
 380       {
 381         const std::string& dir = path[i];
 382         std::string full_path = dir + file;
 383
 384         // Try to open it.
 385         std::ifstream f (full_path.c_str());
 386         if (f.good())
 387           return full_path;
 388       }
 389
 390     return file;
 391   }
 392
 393   class logger
 394   {
 395 #define SID_LOG_PERSISTENT_BUFFER (HAVE_VSNPRINTF || ! HAVE_VASPRINTF)
 396 #define SID_LOG_TRANSIENT_MALLOC_BUFFER (! SID_LOG_PERSISTENT_BUFFER)
 397   public:
 398     logger (sidutil::output_pin *p_ulog_out_pin,
 399             bool p_buffer_output,
 400             sid::host_int_4 p_ulog_level,
 401             std::string p_ulog_mode) :
 402       ulog_level (p_ulog_level),
 403       ulog_mode (p_ulog_mode),
 404       buffer_output (p_buffer_output),
 405       buffer_size (4096), // big enough for now
 406       saved_messages (),
 407       saved_levels ()
 408       {
 409         ulog_out_pin = p_ulog_out_pin;
 410 #if SID_LOG_PERSISTENT_BUFFER
 411         buffer = new char[buffer_size];
 412 #endif
 413       }
 414     ~logger ()
 415       {
 416         // Output any saved messages.
 417         output_saved_messages ();
 418 #if SID_LOG_PERSISTENT_BUFFER
 419         delete [] buffer;
 420 #endif
 421       }
 422
 423     void set_attributes (bool p_buffer_output,
 424                          sid::host_int_4 p_ulog_level,
 425                          std::string p_ulog_mode)
 426     {
 427       buffer_output = p_buffer_output;
 428       ulog_level  = p_ulog_level;
 429       ulog_mode = p_ulog_mode;
 430     }
 431
 432     virtual void log (sid::host_int_4 level, const char *fmt, va_list ap)
 433       {
 434         if (! buffer_output)
 435           {
 436             // Output any saved messages first
 437             output_saved_messages ();
 438
 439             // Check the logging level and mode.
 440             if (! check_level (level))
 441               return;
 442           }
 443
 444         // Write the message into a buffer.
 445         int length;
 446         for (;;)
 447           {
 448 #if HAVE_VSNPRINTF
 449             length = vsnprintf (buffer, buffer_size, fmt, ap);
 450             if (length < buffer_size)
 451               break;
 452             delete [] buffer;
 453             buffer_size = length + 256;
 454             buffer = new char[buffer_size];
 455 #elif HAVE_VASPRINTF
 456             length = vasprintf (&buffer, fmt, ap);
 457             break;
 458 #else
 459             length = STDCTYPE(vsprintf) (buffer, fmt, ap);
 460             if (length >= buffer_size)
 461               std::cerr << "Error: ulog buffer overflow!!!" << std::endl;
 462             break;
 463 #endif
 464           }
 465
 466         // If the output pin is not connected yet, Save the message for
 467         // later. This happens when the log message is issued from the
 468         // component's constructor.
 469         if (buffer_output)
 470           {
 471             saved_messages.push_back (std::string (buffer));
 472             saved_levels.push_back (level);
 473           }
 474         else
 475           {
 476             // Otherwise, output the new message.
 477             for (int i = 0; i < length; ++i)
 478               ulog_out_pin->drive (buffer[i]);
 479           }
 480
 481 #if SID_LOG_TRANSIENT_MALLOC_BUFFER
 482         free (buffer);
 483 #endif
 484       }
 485
 486   public:
 487     bool check_level (sid::host_int_4 level)
 488       {
 489         if (level > ulog_level)
 490           return false;
 491
 492         if (level != ulog_level
 493             && (ulog_mode == "match" || ulog_mode == "equal"))
 494           return false;
 495
 496         return true;
 497       }
 498
 499   public:
 500     void output_saved_messages ()
 501       {
 502         while (saved_messages.size () > 0)
 503           {
 504             if (check_level (saved_levels[0]))
 505               {
 506                 std::string s = saved_messages[0];
 507                 for (int i = 0; i < s.size (); ++i)
 508                   ulog_out_pin->drive (s[i]);
 509               }
 510             saved_messages.erase (saved_messages.begin ());
 511             saved_levels.erase (saved_levels.begin ());
 512           }
 513       }
 514
 515   private:
 516     sid::host_int_4 ulog_level;
 517     std::string ulog_mode;
 518     sidutil::output_pin *ulog_out_pin;
 519     bool buffer_output;
 520     char *buffer;
 521     long buffer_size;
 522     std::vector<std::string> saved_messages;
 523     std::vector<sid::host_int_4> saved_levels;
 524 #undef SID_LOG_PERSISTENT_BUFFER
 525 #undef SID_LOG_TRANSIENT_MALLOC_BUFFER
 526   public:
 527     void delete_saved_messages ()
 528     {
 529       saved_messages.clear ();
 530       saved_levels.clear ();
 531     }
 532   };
 533
 534   // This class is intended for the implementation of change logging and
 535   // change reversing. It is optimized for a potentially large number of
 536   // elements and for growth, shrinkage and access as a LIFO stack. It is
 537   // also optimized for growing again after shrinking.
 538   class change_log
 539   {
 540   public:
 541     change_log (sid::host_int_4 g = 0x100000) :
 542       growth_rate (g),
 543       buffer (0),
 544       buf_index (0),
 545       buf_size (0),
 546       current_length (0)
 547     {}
 548    ~change_log ()
 549     {
 550       if (buffer)
 551         delete buffer;
 552     }
 553
 554     // Begin a new record and add the given data.
 555     void push (const void *data, sid::host_int_4 length)
 556     {
 557       current_length = 0;
 558       add (data, length);
 559     }
 560
 561     // Add the given data to the current record.
 562     void add (const void *data, sid::host_int_4 length)
 563     {
 564       if (buf_index + length > buf_size)
 565         {
 566           buf_size += growth_rate * length;
 567           unsigned char* new_buf = new unsigned char[buf_size];
 568           if (buffer)
 569             {
 570               memcpy (new_buf, buffer, buf_index);
 571               delete buffer;
 572             }
 573           buffer = new_buf;
 574         }
 575
 576       memcpy (buffer + buf_index, data, length);
 577       buf_index += length;
 578       current_length += length;
 579     }
 580
 581     // Complete the current record by writing its length.
 582     void finish ()
 583     {
 584       unsigned char l = current_length;
 585       add (& l, 1);
 586     }
 587
 588     // Remove the last record.
 589     void pop ()
 590     {
 591       unsigned len = buffer[--buf_index];
 592       buf_index -= len;
 593     }
 594
 595     // Return a pointer to the last record.
 596     const void *top (sid::host_int_4 &length) const
 597     {
 598       length = buffer[buf_index - 1];
 599       return buffer + buf_index - length - 1;
 600     }
 601
 602     // Is the change log emtpy?
 603     bool empty () const { return buf_index <= 0; }
 604
 605   private:
 606     sid::host_int_4 growth_rate;
 607     unsigned char* buffer;
 608     sid::host_int_4 buf_index;
 609     sid::host_int_4 buf_size;
 610     unsigned char current_length;
 611   };
 612 }
 613
 614 #endif // SIDMISCUTIL_H