misc.hh

Go to the documentation of this file.

#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 {

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;
}

class Comparable
{
public:
    virtual ~Comparable();

   virtual int compareTo(Comparable *other) = 0;

   static int compareFun(const void *p1, const void *p2);
};

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)
   {
      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);
   }

   inline int size() { return this->num; }

   inline T* getArray() { return array; }

   inline T* detachArray() {
      T* arr = array;
      array = NULL;
      numAlloc = 0;
      num = 0;
      return arr;
   }

   inline void increase() { setSize(this->num + 1); }

   inline void setSize(int newSize) {
      assert (newSize >= 0);
      this->num = newSize;
      this->resize ();
   }

   inline void setSize (int newSize, T t) {
      int oldSize = this->num;
      setSize (newSize);
      for (int i = oldSize; i < newSize; i++)
         set (i, t);
   }

   inline T* getRef (int i) {
      assert (i >= 0 && this->num - i > 0);
      return array + i;
   }

   inline T get (int i) {
      assert (i >= 0 && this->num - i > 0);
      return this->array[i];
   }

   inline T* getFirstRef () {
      assert (this->num > 0);
      return this->array;
   }

   inline T getFirst () {
      assert (this->num > 0);
      return this->array[0];
   }

   inline T* getLastRef () {
      assert (this->num > 0);
      return this->array + this->num - 1;
   }

   inline T getLast () {
      assert (this->num > 0);
      return this->array[this->num - 1];
   }

   inline void set (int i, T t) {
      assert (i >= 0 && this->num - i > 0);
      this->array[i] = t;
   }
};

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() { 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;
         }
      }
   }

   inline T* getRef (int i)
   {
      if (this->startExtra == -1)
         return this->arrayMain + i;
      else {
         if (i < this->startExtra)
            return this->arrayMain + i;
         else if (i >= this->startExtra + this->numExtra)
            return this->arrayMain + i - this->numExtra;
         else
            return this->arrayExtra1 + i - this->startExtra;
      }
   }

   inline T get (int i)
   {
      return *(this->getRef(i));
   }

   inline T* getFirstRef () {
      assert (size () > 0);
      return this->getRef(0);
   }

   inline T getFirst () {
      return *(this->getFirstRef());
   }

   inline T* getLastRef () {
      assert (size () > 0);
      return this->getRef(size () - 1);
   }

   inline T getLast () {
      return *(this->getLastRef());
   }

   inline void set (int i, T t) {
      *(this->getRef(i)) = t;
   }
};

class StringBuffer
{
private:
   struct Node
   {
      char *data;
      Node *next;
   };

   Node *firstNode, *lastNode;
   int numChars;
   char *str;
   bool strValid;

public:
   StringBuffer();
   ~StringBuffer();

   inline void append(const char *str) { appendNoCopy(strdup(str)); }
   void appendNoCopy(char *str);
   const char *getChars();
   void clear ();
};


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);
   void set(int i, bool val);
   void clear();
};

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__