Import RTFL 0.1.1v0.1.1

1 files changed, 652 insertions, 0 deletions

diff --git a/lout/misc.hh b/lout/misc.hh
new file mode 100644
index 0000000..7edf83c
--- /dev/null
+++ b/lout/misc.hh
@@ -0,0 +1,652 @@
+#ifndef __LOUT_MISC_HH__
+#define __LOUT_MISC_HH__
+
+#include <stdio.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+namespace lout {
+
+/**
+ * \brief Miscellaneous stuff, which does not fit anywhere else.
+ *
+ * Actually, the other parts, beginning with ::object, depend on this.
+ */
+namespace misc {
+
+template <class T> inline T min (T a, T b) { return a < b ? a : b; }
+template <class T> inline T max (T a, T b) { return a > b ? a : b; }
+
+template <class T> inline T min (T a, T b, T c)
+{
+   return (min (a, min (b, c)));
+}
+template <class T> inline T max (T a, T b, T c)
+{
+   return (max (a, max (b, c)));
+}
+
+extern const char *prgName;
+
+void init (int argc, char *argv[]);
+
+inline void assertNotReached ()
+{
+   fprintf (stderr, "*** [%s] This should not happen! ***\n", prgName);
+   abort ();
+}
+
+inline int roundInt(double d)
+{
+   return (int) ((d > 0) ? (d + 0.5) : (d - 0.5));
+}
+
+inline int AsciiTolower(char c)
+{
+   return ((c >= 'A' && c <= 'Z') ? c + 0x20 : c);
+}
+
+inline int AsciiToupper(char c)
+{
+   return ((c >= 'a' && c <= 'z') ? c - 0x20 : c);
+}
+
+inline int AsciiStrcasecmp(const char *s1, const char *s2)
+{
+   int ret = 0;
+
+   while ((*s1 || *s2) && !(ret = AsciiTolower(*s1) - AsciiTolower(*s2))) {
+      s1++;
+      s2++;
+   }
+   return ret;
+}
+
+/**
+ * \brief Simple (simpler than container::untyped::Vector and
+ *    container::typed::Vector) template based vector.
+ */
+template <class T> class SimpleVector
+{
+private:
+   T *array;
+   int num, numAlloc;
+
+   inline void resize ()
+   {
+      /* This algorithm was tuned for memory&speed with this huge page:
+       *   http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
+       */
+      if (array == NULL) {
+         this->numAlloc = 1;
+         this->array = (T*) malloc (sizeof (T));
+      }
+      if (this->numAlloc < this->num) {
+         this->numAlloc = (this->num < 100) ?
+                          this->num : this->num + this->num/10;
+         this->array =
+            (T*) realloc(this->array, (this->numAlloc * sizeof (T)));
+      }
+   }
+
+public:
+   inline SimpleVector (int initAlloc = 1)
+   {
+      this->num = 0;
+      this->numAlloc = initAlloc;
+      this->array = NULL;
+   }
+
+   inline SimpleVector (const SimpleVector &o) {
+      this->array = NULL;
+      this->num = o.num;
+      this->numAlloc = o.numAlloc;
+      resize ();
+      memcpy (this->array, o.array, sizeof (T) * num);
+   }
+
+   inline ~SimpleVector ()
+   {
+      if (this->array)
+         free (this->array);
+   }
+
+   /**
+    * \brief Return the number of elements put into this vector.
+    */
+   inline int size() const { return this->num; }
+
+   inline T* getArray() const { return array; }
+
+   inline T* detachArray() {
+      T* arr = array;
+      array = NULL;
+      numAlloc = 0;
+      num = 0;
+      return arr;
+   }
+
+   /**
+    * \brief Increase the vector size by one.
+    *
+    * May be necessary before calling misc::SimpleVector::set.
+    */
+   inline void increase() { setSize(this->num + 1); }
+
+   /**
+    * \brief Set the size explicitly.
+    *
+    * May be necessary before calling misc::SimpleVector::set.
+    */
+   inline void setSize(int newSize) {
+      assert (newSize >= 0);
+      this->num = newSize;
+      this->resize ();
+   }
+
+   /**
+    * \brief Set the size explicitly and initialize new values.
+    *
+    * May be necessary before calling misc::SimpleVector::set.
+    */
+   inline void setSize (int newSize, T t) {
+      int oldSize = this->num;
+      setSize (newSize);
+      for (int i = oldSize; i < newSize; i++)
+         set (i, t);
+   }
+
+   /**
+    * \brief Return the reference of one element.
+    *
+    * \sa misc::SimpleVector::get
+    */
+   inline T* getRef (int i) const {
+      assert (i >= 0 && this->num - i > 0);
+      return array + i;
+   }
+
+   /**
+    * \brief Return the one element, explicitly.
+    *
+    * The element is copied, so for complex elements, you should rather used
+    * misc::SimpleVector::getRef.
+    */
+   inline T get (int i) const {
+      assert (i >= 0 && this->num - i > 0);
+      return this->array[i];
+   }
+
+   /**
+    * \brief Return the reference of the first element (convenience method).
+    */
+   inline T* getFirstRef () const {
+      assert (this->num > 0);
+      return this->array;
+   }
+
+   /**
+    * \brief Return the first element, explicitly.
+    */
+   inline T getFirst () const {
+      assert (this->num > 0);
+      return this->array[0];
+   }
+
+   /**
+    * \brief Return the reference of the last element (convenience method).
+    */
+   inline T* getLastRef () const {
+      assert (this->num > 0);
+      return this->array + this->num - 1;
+   }
+
+   /**
+    * \brief Return the last element, explicitly.
+    */
+   inline T getLast () const {
+      assert (this->num > 0);
+      return this->array[this->num - 1];
+   }
+
+   /**
+    * \brief Store an object in the vector.
+    *
+    * Unlike in container::untyped::Vector and container::typed::Vector,
+    * you have to care about the size, so a call to
+    * misc::SimpleVector::increase or misc::SimpleVector::setSize may
+    * be necessary before.
+    */
+   inline void set (int i, T t) {
+      assert (i >= 0 && this->num - i > 0);
+      this->array[i] = t;
+   }
+
+   /**
+    * \brief Store an object at the end of the vector.
+    */
+   inline void setLast (T t) {
+      assert (this->num > 0);
+      this->array[this->num - 1] = t;
+   }
+};
+
+/**
+ * \brief Container similar to lout::misc::SimpleVector, but some cases
+ *    of insertion optimized (used for hyphenation).
+ *
+ * For hyphenation, words are often split, so that some space must be
+ * inserted by the method NotSoSimpleVector::insert. Typically, some
+ * elements are inserted quite at the beginning (when the word at the
+ * end of the first or at the beginning of the second line is
+ * hyphenated), then, a bit further (end of second line/beginning of
+ * third line) and so on. In the first time, nearly all words must be
+ * moved; in the second time, a bit less, etc. After all, using a
+ * simple vector would result in O(n<sup>2</sup>) number of elements
+ * moved total. With this class, however, the number can be kept at
+ * O(n).
+ *
+ * The basic idea is to keep an extra array (actually two, of which
+ * the second one is used temporarily), which is inserted in a logical
+ * way. Since there is only one extra array at max, reading is rather
+ * simple and fast (see NotSoSimpleVector::getRef): check whether the
+ * position is before, within, or after the extra array. The first
+ * insertion is also rather simple, when the extra array has to be
+ * created. The following sketch illustrates the most complex case,
+ * when an extra array exists, and something is inserted after it (the
+ * case for which this class has been optimized):
+ *
+ * \image html not-so-simple-container.png
+ *
+ * Dotted lines are used to keep the boxes aligned.
+ *
+ * As you see, only a relatively small fraction of elements has to be
+ * moved.
+ *
+ * There are some other cases, which have to be documented.
+ */
+template <class T> class NotSoSimpleVector
+{
+private:
+   T *arrayMain, *arrayExtra1, *arrayExtra2;
+   int numMain, numExtra, numAllocMain, numAllocExtra, startExtra;
+
+   inline void resizeMain ()
+   {
+      /* This algorithm was tuned for memory&speed with this huge page:
+       *   http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
+       */
+      if (arrayMain == NULL) {
+         this->numAllocMain = 1;
+         this->arrayMain = (T*) malloc (sizeof (T));
+      }
+      if (this->numAllocMain < this->numMain) {
+         this->numAllocMain = (this->numMain < 100) ?
+                          this->numMain : this->numMain + this->numMain/10;
+         this->arrayMain =
+            (T*) realloc(this->arrayMain, (this->numAllocMain * sizeof (T)));
+      }
+   }
+
+   inline void resizeExtra ()
+   {
+      /* This algorithm was tuned for memory&speed with this huge page:
+       *   http://downloads.mysql.com/docs/refman-6.0-en.html.tar.gz
+       */
+      if (arrayExtra1 == NULL) {
+         this->numAllocExtra = 1;
+         this->arrayExtra1 = (T*) malloc (sizeof (T));
+         this->arrayExtra2 = (T*) malloc (sizeof (T));
+      }
+      if (this->numAllocExtra < this->numExtra) {
+         this->numAllocExtra = (this->numExtra < 100) ?
+                          this->numExtra : this->numExtra + this->numExtra/10;
+         this->arrayExtra1 =
+            (T*) realloc(this->arrayExtra1, (this->numAllocExtra * sizeof (T)));
+         this->arrayExtra2 =
+            (T*) realloc(this->arrayExtra2, (this->numAllocExtra * sizeof (T)));
+      }
+   }
+
+   void consolidate ()
+   {
+      if (startExtra != -1) {
+         numMain += numExtra;
+         resizeMain ();
+         memmove (arrayMain + startExtra + numExtra, arrayMain + startExtra,
+                  (numMain - (startExtra + numExtra)) * sizeof (T));
+         memmove (arrayMain + startExtra, arrayExtra1, numExtra * sizeof (T));
+         startExtra = -1;
+         numExtra = 0;
+      }
+   }
+
+public:
+   inline NotSoSimpleVector (int initAlloc)
+   {
+      this->numMain = this->numExtra = 0;
+      this->numAllocMain = initAlloc;
+      this->numAllocExtra = initAlloc;
+      this->arrayMain = this->arrayExtra1 = this->arrayExtra2 = NULL;
+      this->startExtra = -1;
+   }
+
+   inline NotSoSimpleVector (const NotSoSimpleVector &o)
+   {
+      this->arrayMain = NULL;
+      this->numMain = o.numMain;
+      this->numAllocMain = o.numAllocMain;
+      resizeMain ();
+      memcpy (this->arrayMain, o.arrayMain, sizeof (T) * numMain);
+
+      this->arrayExtra = NULL;
+      this->numExtra = o.numExtra;
+      this->numAllocExtra = o.numAllocExtra;
+      resizeExtra ();
+      memcpy (this->arrayExtra, o.arrayExtra, sizeof (T) * numExtra);
+
+      this->startExtra = o.startExtra;
+   }
+
+   inline ~NotSoSimpleVector ()
+   {
+      if (this->arrayMain)
+         free (this->arrayMain);
+      if (this->arrayExtra1)
+         free (this->arrayExtra1);
+      if (this->arrayExtra2)
+         free (this->arrayExtra2);
+   }
+
+   inline int size() const { return this->numMain + this->numExtra; }
+
+   inline void increase() { setSize(size() + 1); }
+
+   inline void setSize(int newSize)
+   {
+      assert (newSize >= 0);
+      this->numMain = newSize - numExtra;
+      this->resizeMain ();
+   }
+
+   void insert (int index, int numInsert)
+   {
+      assert (numInsert >= 0);
+
+      // The following lines are a simple (but inefficient) replacement.
+      //setSize (numMain + numInsert);
+      //memmove (arrayMain + index + numInsert, arrayMain + index,
+      //         (numMain - index - numInsert) * sizeof (T));
+      //return;
+
+      if (this->startExtra == -1) {
+         // simple case
+         this->numExtra = numInsert;
+         this->startExtra = index;
+         resizeExtra ();
+      } else {
+         if (index < startExtra)  {
+            consolidate ();
+            insert (index, numInsert);
+         } else if (index < startExtra + numExtra) {
+            int oldNumExtra = numExtra;
+            numExtra += numInsert;
+            resizeExtra ();
+
+            int toMove = startExtra + oldNumExtra - index;
+            memmove (arrayExtra1 + numExtra - toMove,
+                     arrayExtra1 + index - startExtra,
+                     toMove * sizeof (T));
+         } else {
+            int oldNumExtra = numExtra;
+            numExtra += numInsert;
+            resizeExtra ();
+
+            // Note: index refers to the *logical* adress, not to the
+            // *physical* one.
+            int diff = index - this->startExtra - oldNumExtra;
+            T *arrayMainI = arrayMain + this->startExtra;
+            for (int i = diff + oldNumExtra - 1; i >= 0; i--) {
+               T *src = i < oldNumExtra ?
+                  this->arrayExtra1 + i : arrayMainI + (i - oldNumExtra);
+               T *dest = i < diff ?
+                  arrayMainI + i : arrayExtra2 + (i - diff);
+               *dest = *src;
+            }
+
+            memcpy (arrayExtra1, arrayExtra2, sizeof (T) * oldNumExtra);
+            startExtra = index - oldNumExtra;
+         }
+      }
+   }
+
+   /**
+    * \brief Return the reference of one element.
+    *
+    * \sa misc::SimpleVector::get
+    */
+   inline T* getRef (int i) const
+   {
+      if (this->startExtra == -1) {
+         assert (i >= 0 && i < this->numMain);
+         return this->arrayMain + i;
+      } else {
+         if (i < this->startExtra) {
+            assert (i >= 0);
+            return this->arrayMain + i;
+         } else if (i >= this->startExtra + this->numExtra) {
+            // The original assertion
+            ///
+            //    "assert (i < this->numMain + this->numExtra)"
+            //
+            // causes this warnung in dw::Textblock::breakAdded:
+            //
+            //    "assuming signed overflow does not occur when assuming that
+            //     (X - c) > X is always false [-Wstrict-overflow]"
+            //
+            // Subtracting numExtra from both sides solves this,
+            // interrestingly.
+
+            assert (i - this->numExtra < this->numMain);
+            return this->arrayMain + i - this->numExtra;
+         } else
+            return this->arrayExtra1 + i - this->startExtra;
+      }
+   }
+
+   /**
+    * \brief Return the one element, explicitly.
+    *
+    * The element is copied, so for complex elements, you should rather used
+    * misc::SimpleVector::getRef.
+    */
+   inline T get (int i) const
+   {
+      return *(this->getRef(i));
+   }
+
+   /**
+    * \brief Return the reference of the first element (convenience method).
+    */
+   inline T* getFirstRef () const {
+      assert (size () > 0);
+      return this->getRef(0);
+   }
+
+   /**
+    * \brief Return the first element, explicitly.
+    */
+   inline T getFirst () const {
+      return *(this->getFirstRef());
+   }
+
+   /**
+    * \brief Return the reference of the last element (convenience method).
+    */
+   inline T* getLastRef () const {
+      assert (size () > 0);
+      return this->getRef(size () - 1);
+   }
+
+   /**
+    * \brief Return the last element, explicitly.
+    */
+   inline T getLast () const {
+      return *(this->getLastRef());
+   }
+
+   /**
+    * \brief Store an object in the vector.
+    *
+    * Unlike in container::untyped::Vector and container::typed::Vector,
+    * you have to care about the size, so a call to
+    * misc::SimpleVector::increase or misc::SimpleVector::setSize may
+    * be necessary before.
+    */
+   inline void set (int i, T t) {
+      *(this->getRef(i)) = t;
+   }
+
+   /**
+    * \brief Store an object at the end of the vector.
+    */
+   inline void setLast (T t) {
+      *(this->getLastRef()) = t;
+   }
+};
+
+/**
+ * \brief A class for fast concatenation of a large number of strings.
+ */
+class StringBuffer
+{
+private:
+   struct Node
+   {
+      char *data;
+      Node *next;
+   };
+
+   Node *firstNode, *lastNode;
+   int numChars;
+   char *str;
+   bool strValid;
+
+public:
+   StringBuffer();
+   ~StringBuffer();
+
+   /**
+    * \brief Append a NUL-terminated string to the buffer, with copying.
+    *
+    * A copy is kept in the buffer, so the caller does not have to care
+    * about memory management.
+    */
+   inline void append(const char *str) { appendNoCopy(strdup(str)); }
+   inline void appendInt(int n)
+   { char buf[32]; sprintf (buf, "%d", n); append (buf); }
+   inline void appendPointer(void *p)
+   { char buf[32]; sprintf (buf, "%p", p); append (buf); }
+   inline void appendBool(bool b) { append (b ? "true" : "false"); }
+   void appendNoCopy(char *str);
+   const char *getChars();
+   void clear ();
+};
+
+
+/**
+ * \brief A bit set, which automatically reallocates when needed.
+ */
+class BitSet
+{
+private:
+   unsigned char *bits;
+   int numBytes;
+
+   inline int bytesForBits(int bits) { return bits == 0 ? 1 : (bits + 7) / 8; }
+
+public:
+   BitSet(int initBits);
+   ~BitSet();
+   void intoStringBuffer(misc::StringBuffer *sb);
+   bool get(int i) const;
+   void set(int i, bool val);
+   void clear();
+};
+
+/**
+ * \brief A simple allocator optimized to handle many small chunks of memory.
+ * The chunks can not be free'd individually. Instead the whole zone must be
+ * free'd with zoneFree().
+ */
+class ZoneAllocator
+{
+private:
+   size_t poolSize, poolLimit, freeIdx;
+   SimpleVector <char*> *pools;
+   SimpleVector <char*> *bulk;
+
+public:
+   ZoneAllocator (size_t poolSize) {
+      this->poolSize = poolSize;
+      this->poolLimit = poolSize / 4;
+      this->freeIdx = poolSize;
+      this->pools = new SimpleVector <char*> (1);
+      this->bulk = new SimpleVector <char*> (1);
+   };
+
+   ~ZoneAllocator () {
+      zoneFree ();
+      delete pools;
+      delete bulk;
+   }
+
+   inline void * zoneAlloc (size_t t) {
+      void *ret;
+
+      if (t > poolLimit) {
+         bulk->increase ();
+         bulk->set (bulk->size () - 1, (char*) malloc (t));
+         return bulk->get (bulk->size () - 1);
+      }
+
+      if (t > poolSize - freeIdx) {
+         pools->increase ();
+         pools->set (pools->size () - 1, (char*) malloc (poolSize));
+         freeIdx = 0;
+      }
+
+      ret = pools->get (pools->size () - 1) + freeIdx;
+      freeIdx += t;
+      return ret;
+   }
+
+   inline void zoneFree () {
+      for (int i = 0; i < pools->size (); i++)
+         free (pools->get (i));
+      pools->setSize (0);
+      for (int i = 0; i < bulk->size (); i++)
+         free (bulk->get (i));
+      bulk->setSize (0);
+      freeIdx = poolSize;
+   }
+
+   inline const char *strndup (const char *str, size_t t) {
+      char *new_str = (char *) zoneAlloc (t + 1);
+      memcpy (new_str, str, t);
+      new_str[t] = '\0';
+      return new_str;
+   }
+
+   inline const char *strdup (const char *str) {
+      return strndup (str, strlen (str));
+   }
+};
+
+} // namespace misc
+
+} // namespace lout
+
+#endif // __LOUT_MISC_HH__