//==========================================================================
// PRODUCT: RusRoute - MaaSoftware routing firewall software driver
// (C) Copyright Moiseenko A.A., MaaSoftware, 2003-2008. All Rights Reserved.
// http://www.maasoftware.ru       http://www.maasoftware.com
// http://www.rusroute.ru          http://www.rusroute.com
// support@maasoftware.ru
//==========================================================================
// FILE:       MaaTL.h
//
// AUTHOR:     Andrey A. Moiseenko
//
// OVERVIEW    MaaSoftware template library.
// ~~~~~~~~
// DATE:       16.10.2003
//==========================================================================

#ifndef __MAARF_MAATL_H
#define __MAARF_MAATL_H

#ifndef _MaaRF_INTERNAL_BUILD
//#define Malloc(x) malloc(x)
//#define Free(x,y) free(x)
#define Memcpy(x,y,z) memcpy(x,y,z)
#define Memcmp(x,y,z) memcmp(x,y,z)
#define Memzero(x,y) memset(x,0,y)

#define Strlen(x) strlen(x)
#define Strcmp(x,y) strcmp(x,y)
#endif

//---------------------------------------------------------------------------
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
//---------------------------------------------------------------------------
template < class T > void CMaaSwap ( T & a, T & b )
{
     T tmp ( a );
     a = b;
     b = tmp;
}
//---------------------------------------------------------------------------
struct CMaaDLink
{
     CMaaDLink * Next, * Prev; // list

     // it is not need to initialize links before caling AddAtXxxx ()
     void Init ()
     {
          Next = Prev = NULL;
     }
     void InsertAfter ( CMaaDLink * That )  // .... That, this, ....
     {
          Next = That -> Next;
          Prev = That;
          Next -> Prev = this;
          That -> Next = this;
     }
     void InsertBefore ( CMaaDLink * That )  // .... this, That, ....
     {
          Prev = That -> Prev;
          Next = That;
          Prev -> Next = this;
          That -> Prev = this;
     }
} GCC_PACKED;
//---------------------------------------------------------------------------
template < class T > struct CMaaDLink_Item : public CMaaDLink
{
     T m_Item;
     operator T & ()
     {
          return m_Item;
     }
};
//---------------------------------------------------------------------------
template < class T > struct CMaaDLink_pItem : public CMaaDLink
{
     T * m_pItem;
     operator T *& ()
     {
          return m_pItem;
     }
     T * operator -> ()
     {
          return m_pItem;
     }
     T * operator = ( T * ptr )
     {
          return m_pItem = ptr;
     }
};
//---------------------------------------------------------------------------
template < class T > struct CMaaDLink_pItemAD : public CMaaDLink_pItem < T >
{
     CMaaDLink_pItemAD ()
     {
          m_pItem = NULL;
     }
     ~CMaaDLink_pItemAD ()
     {
          delete m_pItem;
     }
     T * operator = ( T * ptr )
     {
          return CMaaDLink_pItem < T >::operator = ( ptr );
     }
};
//---------------------------------------------------------------------------
// Modification. Clear(), New(), Delete(), etc.
//---------------------------------------------------------------------------
template < class T > class CMaaDList
{
     CMaaDLink Head;
public:
     BOOL m_AutoDeleteItems;
     //----------------------------------------------------------------------
     CMaaDList ( BOOL AutoDeleteItems = FALSE )
     :    m_AutoDeleteItems ( AutoDeleteItems )
     {
          Init();
     }
     //----------------------------------------------------------------------
     virtual ~CMaaDList ()
     {
          if   ( m_AutoDeleteItems )
          {
               Clear ();
          }
     }
     //----------------------------------------------------------------------
     void Init()
     {
          Head.Next = Head.Prev = &Head;
     }
     /*
     void LoseAll()
     {
          Init();
     }
     */
     bool IsEmpty () const
     {
          return Head.Next == &Head;
     }
     //----------------------------------------------------------------------
#ifndef __unix__
     #define CMaaDLink__ CMaaDLink::
#else
     #define CMaaDLink__
#endif
     //----------------------------------------------------------------------
     virtual void Delete ( T * p )
     {
          delete p;
     }
     //----------------------------------------------------------------------
     /*virtual T * New ()
     {
          T * p = new T;
          p -> CMaaDLink__ Init ();  // but it is not nessesary to perform initializations
          return p;
     }*/
     //----------------------------------------------------------------------
     void Clear ()
     {
          for  ( T * p; p = GetFromFront (); )
          {
               Delete ( p );
          }
     }
     //----------------------------------------------------------------------
     void AddAtBack ( T * That )
     {
          That -> CMaaDLink__ Prev = Head.Prev;
          That -> CMaaDLink__ Next = & Head;
          Head.Prev = That;
          That -> CMaaDLink__ Prev -> CMaaDLink__ Next = That;
     }
     //----------------------------------------------------------------------
     void AddAtFront ( T * That )
     {
          That -> CMaaDLink__ Next = Head.Next;
          That -> CMaaDLink__ Prev = & Head;
          Head.Next = That;
          That -> CMaaDLink__ Next -> Prev = That;
     }
     //----------------------------------------------------------------------
     T * GetFromFront ()
     {
          CMaaDLink * That;
          if   ( ( That = Head.Next ) == & Head )
          {
               That = NULL;
          }
          else
          {
               That -> CMaaDLink__ Next -> Prev =  & Head;
               Head.Next = That -> CMaaDLink__ Next;
               That -> CMaaDLink__ Prev = That -> CMaaDLink__ Next = NULL;
          }
          return ( T * ) That;
     }
     //----------------------------------------------------------------------
     T * GetFromBack ()
     {
          CMaaDLink * That;
          if   ( ( That = Head.Prev ) == & Head )
          {
               That = NULL;
          }
          else
          {
               That -> CMaaDLink__ Prev -> Next =  & Head;
               Head.Prev = That -> CMaaDLink__ Prev;
               That -> CMaaDLink__ Next = That -> CMaaDLink__ Prev = NULL;
          }
          return ( T * ) That;
     }
     //----------------------------------------------------------------------
     T * LookAtFront ()
     {
          //CMaaDLink * That;
          //if   ( ( That = Head.Next ) == & Head )
          //{
          //     That = NULL;
          //}
          //return ( T * ) That;
          return ( Head.Next == &Head ) ? NULL : ( T* ) Head.Next;
     }
     //----------------------------------------------------------------------
     T * LookAtBack ()
     {
          //CMaaDLink * That;
          //if   ( ( That = Head.Prev ) == & Head )
          //{
          //     That = NULL;
          //}
          //return ( T * ) That;
          return ( Head.Prev == &Head ) ? NULL : ( T* ) Head.Prev;
     }
     //----------------------------------------------------------------------
     T * Next ( T * That )
     {
          return That -> Next == & Head ? NULL : ( T * ) That -> Next;
     }
     //----------------------------------------------------------------------
     T * Prev ( T * That )
     {
          return That -> Prev == & Head ? NULL : ( T * ) That -> Prev;
     }
     //----------------------------------------------------------------------
     int CopyChainToBack ( T * pFirst, T * pSkip = NULL )
     {
          int Ret = 0;
          for  ( ; pFirst; )
          {
               CMaaDLink * pThis = pFirst;
               pFirst = ( T * ) pFirst -> CMaaDLink__ Next;
               if   ( pThis != pSkip )
               {
                    AddAtBack ( ( T * ) pThis );
               }
               else
               {
                    Ret++;
               }
          }
          return Ret;
     }
     //----------------------------------------------------------------------
     static void Release ( T * That )
     {
          if   ( That -> CMaaDLink__ Prev )
          {
               That -> CMaaDLink__ Prev -> Next = That -> CMaaDLink__ Next;
          }
          else
          {
               INT3 // I never pass here free item
          }
          if   ( That -> CMaaDLink__ Next )
          {
               That -> CMaaDLink__ Next -> Prev = That -> CMaaDLink__ Prev;
          }
          else
          {
               INT3 // I never pass here free item
          }
          That -> CMaaDLink__ Next = That -> CMaaDLink__ Prev = NULL; // but it is not nessesary to perform initializations
     }
     //----------------------------------------------------------------------
     void Remove ( T * That )
     {
          Release ( That );
     }
     //----------------------------------------------------------------------
     //static void InsertAfrer ( T * That, T * After )
     //{
     //     That -> CMaaDLink__ Next = After -> CMaaDLink__ Next;
     //     That -> CMaaDLink__ Prev = After;
     //     That -> CMaaDLink__ Next -> Prev = That;
     //}
     //----------------------------------------------------------------------
     int GetCount ()
     {
          int c = 0;
          T * p;
          for  ( p = LookAtFront (); p; p = this->Next ( p ) )
          {
               c++;
          }
          return c;
     }
     void MoveThatToTheEnd ( CMaaDList < T > & That )
     {
          if   ( !That.IsEmpty () )
          {
               T * F = ( T * ) That.Head.Next;
               T * L = ( T * ) That.Head.Prev;
               T * m = ( T * ) Head.Prev;
               m -> Next = F;
               F -> Prev = m;
               L -> Next = &Head;
               Head.Prev = L;
               That.LoseAll ();
          }
     }
     void MoveThatToTheFront ( CMaaDList < T > & That )
     {
          if   ( !That.IsEmpty () )
          {
               T * F = ( T * ) That.Head.Next;
               T * L = ( T * ) That.Head.Prev;
               T * m = ( T * ) Head.Next;
               m -> Prev = L;
               L -> Next = m;
               F -> Prev = &Head;
               Head.Next = F;
               That.LoseAll ();
          }
     }
     BOOL MoveUp ( T * That )
     {
          T * Neighbor = Prev ( That );
          if   ( !Neighbor )
          {
               return FALSE;
          }
          Release ( That );
          That -> InsertBefore ( Neighbor );
          return TRUE;
     }
     BOOL MoveDown ( T * That )
     {
          T * Neighbor = Next ( That );
          if   ( !Neighbor )
          {
               return FALSE;
          }
          Release ( That );
          That -> InsertAfter ( Neighbor );
          return TRUE;
     }
#undef CMaaDLink__
};
//---------------------------------------------------------------------------
template < class T > class CMaaDListAD : public CMaaDList < T >
{
public:
     CMaaDListAD ()
     :    CMaaDList < T > ( TRUE ) // Auto deleting list items from destructor by default
     {
     }
};

//---------------------------------------------------------------------------
template < class T > class CMaaPtr
{
protected:
     T    * m_Ptr;
     size_t m_MaxIndex;

public:

     void Swap ( CMaaPtr & That )
     {
          CMaaSwap ( m_Ptr, That.m_Ptr );
          CMaaSwap ( m_MaxIndex, That.m_MaxIndex );
     }
     // This constructor creates MaxIndex numbers of elements of class T.
     // Under Windows makes exeption if no free memory available.
     CMaaPtr ( size_t MaxIndex )
     :    m_Ptr ( NULL ),
          m_MaxIndex ( MaxIndex )
     {
          if    ( ( size_t ) sizeof ( T ) * MaxIndex >= MaxIndex )
          {
               m_Ptr = new T [ MaxIndex ];
               if   ( ! m_Ptr && MaxIndex )
               {
                    INT3;
#ifndef __unix__
                    OUT_DEBUG_STRING ( "MAARF:Memory allocation failed\r\n" );
#endif
                    m_MaxIndex = 0;
               }
          }
     }

     virtual ~CMaaPtr ()
     {
          delete [] m_Ptr;
     }

     virtual BOOL IsValid () const
     {
          return m_Ptr != NULL || m_MaxIndex == 0;
     }

     operator T * ()
     {
          return m_Ptr;
     }

     T & operator * () const
     {
          return * m_Ptr;
     }

     T & operator [] ( int Index )
     {
          return m_Ptr [ Index ];
     }
     size_t MaxIndex ()
     {
          return m_MaxIndex;
     }
     void Zero ()
     {
          if   ( m_Ptr )
          {
               Memzero ( m_Ptr, ( size_t ) sizeof ( T ) * m_MaxIndex );
          }
     }
     virtual BOOL Resize ( int n )
     {
          CMaaPtr < T > tmp ( n );
          if   ( !tmp.IsValid () )
          {
               return FALSE;
          }
          Swap ( tmp );
          return TRUE;
     }
};
//---------------------------------------------------------------------------
inline unsigned long CMaaStandardHashFunction ( const void * ptr, int len )
{
     unsigned char * p = ( unsigned char * ) ptr;
     unsigned long x = 0;
     for  ( int i = len; i--; )
     {
          x = ( ( x >> 25 ) | ( x << 7 ) ) ^ *p++;
     }
     return x;
}
//---------------------------------------------------------------------------
template < class Key, class Data > class CMaaUnivHash
{
     struct Record
     {
          Record * pNext;
          Key  K;
          Data D;
     };
     int  m_TableSize;   // size of item table
     int  m_HashSize;    // size of hash table

     Record * m_FreeList,   // list of free items
            * m_Table,      // table of items
            ** m_Hash;      // hash table
     BOOL fOK;

protected:
     // hash function of key
     virtual unsigned long HashFunction ( const Key & K ) const
     {
          if   ( sizeof ( Key ) == sizeof ( unsigned long ) )
          {
               return * ( unsigned long * ) &K;
          }
          else
          {
               unsigned char * p = ( unsigned char * ) &K;
               unsigned long x = 0;
               for  ( int i = sizeof ( Key ); i--; )
               {
                    x = ( ( x >> 25 ) | ( x << 7 ) ) ^ *p++;
               }
               return x;
          }
     }

public:

     virtual void Swap ( CMaaUnivHash < Key, Data > & That )
     {
          CMaaSwap ( m_TableSize, That.m_TableSize );
          CMaaSwap ( m_HashSize,  That.m_HashSize );
          CMaaSwap ( m_FreeList,  That.m_FreeList );
          CMaaSwap ( m_Table,     That.m_Table );
          CMaaSwap ( m_Hash,      That.m_Hash );
          CMaaSwap ( fOK,         That.fOK );
     }

     virtual CMaaUnivHash < Key, Data > * MakeNewTable ( int Size )
     {
          return new CMaaUnivHash < Key, Data > ( Size );
     }

     CMaaUnivHash ( int Size = 16 )
     {
          if   ( Size < 2 )
          {
               Size = 2;
          }
          m_HashSize     = Size + Size / 10;
          m_TableSize    = Size;
          m_Table        = new Record [ m_TableSize ];
          m_Hash         = new Record * [ m_HashSize ];
          if   ( m_Table && m_Hash )
          {
               fOK = TRUE;
               // Initializing free list
               Record * p =  m_Table + m_TableSize - 1;
               p->pNext = NULL;
               for  ( int i = m_TableSize - 1; i; i--, p-- )
               {
                    ( p - 1 ) -> pNext = p; // m_Table [ i - 1 ].Next = & m_Table [ i ];
               }
               m_FreeList = m_Table;
               Memzero ( m_Hash, m_HashSize * sizeof ( * m_Hash ) );
          }
          else
          {
               delete [] m_Hash;  m_Hash  = NULL;
               delete [] m_Table; m_Table = NULL;
               fOK = FALSE;
          }
     }

     BOOL IsOK ()
     {
          return fOK;
     }

     virtual ~CMaaUnivHash ()
     {
          delete [] m_Hash;  m_Hash  = NULL;
          delete [] m_Table; m_Table = NULL;
     }

     void Cleanup ( int NewTableSize = 0 )
     {
          CMaaUnivHash < Key, Data > * NewTable = MakeNewTable ( NewTableSize ? NewTableSize : m_TableSize );
          if   ( NewTable )
          {
               Swap ( *NewTable );
               delete NewTable;
          }
     }

     int GetMaxIndex () const
     {
          return m_HashSize;
     }

     // returns 0 for success
     int FindByIndex ( int Index, Key * K = NULL, Data * D = NULL ) const
     {
          if   ( Index >= 0 && Index < m_HashSize )
          {
               if   ( m_Hash [ Index ] )
               {
                    if   ( K )
                    {
                         *K = m_Hash [ Index ] -> K;
                    }
                    if   ( D )
                    {
                         *D = m_Hash [ Index ] -> D;
                    }
                    return 0;
               }
          }
          return 1;
     }

     // Adds  element. ( Copy element to table )
     // Returns 0 if success. 1 - Key alredy exists. 2 - Not enought free memory
     int Add    ( const Key & K, const Data & D, int fOverwrite = 0 )
     {
          int Ret = 0; // 0: IsOk, 1,2: IsFail
          Record * Free = m_FreeList;
          Record * This;
          if   ( ! Free )
          {
               CMaaUnivHash < Key, Data > * NewTable = MakeNewTable ( 2 * m_TableSize );
               if   ( !NewTable || !NewTable->IsOK () )
               {
                    Ret = 2; // No free elements
               }
               else
               {
                    This = m_Table;
                    for  ( int i = m_TableSize; i ; i-- )
                    {
                         NewTable->Add ( This -> K, This -> D );
                         This++;
                    }
                    Ret = NewTable->Add ( K, D, fOverwrite );
                    Swap ( *NewTable );
                    delete NewTable;
               }
          }
          else
          {
               Record ** Hash = m_Hash + HashFunction ( K ) % ( unsigned long ) m_HashSize;
               This = * Hash;
               if   ( ! This )
               {
                    // Creating new node
                    * Hash = Free;
                    m_FreeList = Free -> pNext;
                    Free -> pNext = NULL;
                    Free -> K = K;
                    Free -> D = D;
               }
               else
               {
                    // searching if Key alredy exists
                    for  ( ; This; This = This -> pNext )
                    {
                         if   ( This -> K == K )
                         {
                              if   ( ! fOverwrite )
                              {
                                   Ret = 1; // Key alredy exists
                                   break;
                              }
                              This -> D = D;
                              return 0;
                         }
                    }
                    if   ( ! Ret )
                    {
                         m_FreeList = Free -> pNext;
                         Free -> pNext = *Hash;
                         * Hash = Free;
                         Free -> K = K;
                         Free -> D = D;
                    }
               }
          }
          return Ret;

     }

     // Adds  element. ( Owerwrites it if exists )
     // Returns 0 if success. 2 - Not enought free memory
     int AddOver ( const Key & K, const Data & D )
     {
          return Add ( K, D, 1 );
     }

     // Finds element.
     // If ok: returns 0 and copy Data ( if Data != NULL )
     int Find   ( const Key & K, Data * D = NULL ) const
     {
          int Ret = 1; // 0: IsOk, 1: Key was not found

          Record ** Hash = m_Hash + HashFunction ( K ) % ( unsigned long ) m_HashSize;
          Record  * This = * Hash;
          if   ( This )
          {
               // searching for Key
               for  ( ; This; This = This -> pNext )
               {
                    if   ( This -> K == K )
                    {
                         if   ( D )
                         {
                              *D = This -> D;
                         }
                         Ret = 0; // Key was found
                         break;
                    }
               }
          }
          return Ret;
     }

     // Removes element.
     // Returns 0 if ok.
     // it is sutable to add param void * Data ( witch is NULL by default ) where to rerurn deleted context of Data
     int Remove ( const Key & K, Data * D = NULL )
     {
          int Ret = 1; // 0: IsOk, 1: Key was not found

          Record ** Hash = m_Hash + HashFunction ( K ) % ( unsigned long ) m_HashSize;
          Record  * This = * Hash, * Prev = NULL;
          if   ( This )
          {
               // searching for Key
               for  ( ; This; This = This -> pNext )
               {
                    if   ( This -> K == K )
                    {
                         if   ( D )
                         {
                              *D = This -> D;
                         }
                         if   ( Prev )
                         {
                              Prev -> pNext = This -> pNext;
                         }
                         else
                         {
                              * Hash = This -> pNext;
                         }
                         This -> pNext = m_FreeList;
                         m_FreeList = This;
                         Ret = 0; // Key was found
                         break;
                    }
                    Prev = This;
               }
          }
          return Ret;
     }

     Data * operator [] ( const Key & K )
     {
          Record ** Hash = m_Hash + HashFunction ( K ) % ( unsigned long ) m_HashSize;
          Record  * This = * Hash;
          if   ( This )
          {
               // searching for Key
               for  ( ; This; This = This -> pNext )
               {
                    if   ( This -> K == Key )
                    {
                         return & This -> D;
                    }
               }
          }
          return NULL;
     }

     // returns -1: invalid parameter Size, -2: Size is too small (too small arrays Keys/Datas )
     int EnumeratePtrs ( int Size, Key ** Keys, Data ** Datas ) const
     {
          if   ( Size >= 0 )
          {
               int j = 0;
               for  ( int i = 0; i < m_HashSize; i++ )
               {
                    Record * This = m_Hash [ i ];
                    if   ( This )
                    {
                         // scaning all Keys
                         for  ( ; This; This = This -> pNext )
                         {
                              if   ( j >= Size )
                              {
                                   return -2;
                              }
                              if   ( Keys )
                              {
                                   Keys  [ j ] = & This -> K;
                              }
                              if   ( Datas )
                              {
                                   Datas [ j ] = & This -> D;
                              }
                              j++;
                         }
                    }
               }
               return j;
          }
          return -1;
     }

     // returns -1: invalid parameter Size, -2: Size is too small (too small arrays Keys/Datas )
     int EnumerateItems ( int Size, Key * Keys, Data * Datas ) const
     {
          if   ( Size >= 0 )
          {
               int j = 0;
               for  ( int i = 0; i < m_HashSize; i++ )
               {
                    Record * This = m_Hash [ i ];
                    if   ( This )
                    {
                         // scaning all Keys
                         for  ( ; This; This = This -> pNext )
                         {
                              if   ( Keys )
                              {
                                   if   ( j >= Size )
                                   {
                                        return -2;
                                   }
                                   * Keys = This -> K;
                                   Keys++;
                              }
                              if   ( Datas )
                              {
                                   if   ( j >= Size )
                                   {
                                        return -2;
                                   }
                                   * Datas = This -> D;
                                   Datas++;
                              }
                              j++;
                         }
                    }
               }
               return j;
          }
          return -1;
     }

     int GetItemCount () const
     {
          return EnumerateItems ( 0x7fffffff, NULL, NULL );
     }

     typedef void ( *EnumerateProc )( Key & K, Data & D, void * Param );
     typedef void ( *EnumerateProcEx )( Key & K, Data & D, CMaaUnivHash < Key, Data > & ht, void * Param );

     void EnumerateByProc ( EnumerateProc Proc, void * Param = NULL )
     {
          for  ( int i = 0; i < m_HashSize; i++ )
          {
               Record * This = m_Hash [ i ];
               if   ( This )
               {
                    // scaning all Keys
                    Record * Next;
                    for  ( ; This; This = Next )
                    {
                         Next = This -> pNext;
                         Proc ( This -> K, This -> D, Param );
                    }
               }
          }
     }

     void EnumerateByProc ( EnumerateProcEx Proc, void * Param = NULL )
     {
          for  ( int i = 0; i < m_HashSize; i++ )
          {
               Record * This = m_Hash [ i ];
               if   ( This )
               {
                    // scaning all Keys
                    Record * Next;
                    for  ( ; This; This = Next )
                    {
                         Next = This -> pNext;
                         Proc ( This -> K, This -> D, *this, Param );
                    }
               }
          }
     }
};
//---------------------------------------------------------------------------
template < class Key, class Data > class CMaaUnivHash_KeyIsClass : public CMaaUnivHash < Key, Data >
{
     unsigned long HashFunction ( const Key & K ) const
     {
          return K.Hash ();
     }
public:
     CMaaUnivHash_KeyIsClass ( int Size = 16 )
     :    CMaaUnivHash < Key, Data > ( Size )
     {
     }
     virtual CMaaUnivHash < Key, Data > * MakeNewTable ( int Size )
     {
          return new CMaaUnivHash_KeyIsClass < Key, Data > ( Size );
     }
};
//---------------------------------------------------------------------------
template < class Key, class Data > class CMaaUnivHashClassPtr : public CMaaUnivHash < Key, Data >
{
public:
     CMaaUnivHashClassPtr ( int Size = 16 )
     :    CMaaUnivHash < Key, Data > ( Size )
     {
     }

     static void ObjectDeleter ( Key & K, Data & D, CMaaUnivHash < Key, Data > & ht, void * Param )
     {
          delete D;
     }

     ~CMaaUnivHashClassPtr ()
     {
          EnumerateByProc ( ObjectDeleter );
     }
};
//---------------------------------------------------------------------------

#endif // __MAARF_MAATL_H