//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2007-2013. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/container for documentation.
//
//////////////////////////////////////////////////////////////////////////////


#ifdef _MSC_VER
#pragma warning (disable:4702)
#endif

#include <vector>
#include <iostream>
#include <utility>
#include <cstring>
#include <algorithm>    //std::remove
#include <boost/container/detail/alloc_lib_auto_link.hpp>

namespace boost { namespace container { namespace test {

static const int NumIt = 2000;

enum deallocation_type { DirectDeallocation, InverseDeallocation, MixedDeallocation, EndDeallocationType };

//This test allocates until there is no more memory
//and after that deallocates all in the inverse order

bool test_allocation()
{
   if(!boost_cont_all_deallocated())
      return false;
   boost_cont_malloc_check();
   for( deallocation_type t = DirectDeallocation
      ; t != EndDeallocationType
      ; t = (deallocation_type)((int)t + 1)){
      std::vector<void*> buffers;
      //std::size_t free_memory = a.get_free_memory();

      for(int i = 0; i != NumIt; ++i){
         void *ptr = boost_cont_malloc(i);
         if(!ptr)
            break;
         buffers.push_back(ptr);
      }

      switch(t){
         case DirectDeallocation:
         {
            for(int j = 0, max = (int)buffers.size()
               ;j < max
               ;++j){
               boost_cont_free(buffers[j]);
            }
         }
         break;
         case InverseDeallocation:
         {
            for(int j = (int)buffers.size()
               ;j--
               ;){
               boost_cont_free(buffers[j]);
            }
         }
         break;
         case MixedDeallocation:
         {
            for(int j = 0, max = (int)buffers.size()
               ;j < max
               ;++j){
               int pos = (j%4)*((int)buffers.size())/4;
               boost_cont_free(buffers[pos]);
               buffers.erase(buffers.begin()+pos);
            }
         }
         break;
         default:
         break;
      }
      if(!boost_cont_all_deallocated())
         return false;
      //bool ok = free_memory == a.get_free_memory() &&
               //a.all_memory_deallocated() && a.check_sanity();
      //if(!ok)  return ok;
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();
}

//This test allocates until there is no more memory
//and after that tries to shrink all the buffers to the
//half of the original size

bool test_allocation_shrink()
{
   boost_cont_malloc_check();
   std::vector<void*> buffers;

   //Allocate buffers with extra memory
   for(int i = 0; i != NumIt; ++i){
      void *ptr = boost_cont_malloc(i*2);
      if(!ptr)
         break;
      buffers.push_back(ptr);
   }

   //Now shrink to half
   for(int i = 0, max = (int)buffers.size()
      ;i < max
      ; ++i){
      std::size_t try_received_size;
      void* try_result = boost_cont_allocation_command
               ( BOOST_CONTAINER_TRY_SHRINK_IN_PLACE, 1, i*2
               , i, &try_received_size, (char*)buffers[i]).first;

      std::size_t received_size;
      void* result = boost_cont_allocation_command
         ( BOOST_CONTAINER_SHRINK_IN_PLACE, 1, i*2
         , i, &received_size, (char*)buffers[i]).first;

      if(result != try_result)
         return false;

      if(received_size != try_received_size)
         return false;

      if(result){
         if(received_size > std::size_t(i*2)){
            return false;
         }
         if(received_size < std::size_t(i)){
            return false;
         }
      }
   }

   //Deallocate it in non sequential order
   for(int j = 0, max = (int)buffers.size()
      ;j < max
      ;++j){
      int pos = (j%4)*((int)buffers.size())/4;
      boost_cont_free(buffers[pos]);
      buffers.erase(buffers.begin()+pos);
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
}

//This test allocates until there is no more memory
//and after that tries to expand all the buffers to
//avoid the wasted internal fragmentation

bool test_allocation_expand()
{
   boost_cont_malloc_check();
   std::vector<void*> buffers;

   //Allocate buffers with extra memory
   for(int i = 0; i != NumIt; ++i){
      void *ptr = boost_cont_malloc(i);
      if(!ptr)
         break;
      buffers.push_back(ptr);
   }

   //Now try to expand to the double of the size
   for(int i = 0, max = (int)buffers.size()
      ;i < max
      ;++i){
      std::size_t received_size;
      std::size_t min_size = i+1;
      std::size_t preferred_size = i*2;
      preferred_size = min_size > preferred_size ? min_size : preferred_size;
      while(boost_cont_allocation_command
         ( BOOST_CONTAINER_EXPAND_FWD, 1, min_size
         , preferred_size, &received_size, (char*)buffers[i]).first){
         //Check received size is bigger than minimum
         if(received_size < min_size){
            return false;
         }
         //Now, try to expand further
         min_size       = received_size+1;
         preferred_size = min_size*2;
      }
   }

   //Deallocate it in non sequential order
   for(int j = 0, max = (int)buffers.size()
      ;j < max
      ;++j){
      int pos = (j%4)*((int)buffers.size())/4;
      boost_cont_free(buffers[pos]);
      buffers.erase(buffers.begin()+pos);
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
}

//This test allocates until there is no more memory
//and after that tries to expand all the buffers to
//avoid the wasted internal fragmentation
bool test_allocation_shrink_and_expand()
{
   std::vector<void*> buffers;
   std::vector<std::size_t> received_sizes;
   std::vector<bool>        size_reduced;

   //Allocate buffers wand store received sizes
   for(int i = 0; i != NumIt; ++i){
      std::size_t received_size;
      void *ptr = boost_cont_allocation_command
         (BOOST_CONTAINER_ALLOCATE_NEW, 1, i, i*2, &received_size, 0).first;
      if(!ptr){
         ptr = boost_cont_allocation_command
            ( BOOST_CONTAINER_ALLOCATE_NEW, 1, 1, i*2, &received_size, 0).first;
         if(!ptr)
            break;
      }
      buffers.push_back(ptr);
      received_sizes.push_back(received_size);
   }

   //Now shrink to half
   for(int i = 0, max = (int)buffers.size()
      ; i < max
      ; ++i){
      std::size_t received_size;
      bool size_reduced_flag;
      if(true == (size_reduced_flag = !!
         boost_cont_allocation_command
         ( BOOST_CONTAINER_SHRINK_IN_PLACE, 1, received_sizes[i]
         , i, &received_size, (char*)buffers[i]).first)){
         if(received_size > std::size_t(received_sizes[i])){
            return false;
         }
         if(received_size < std::size_t(i)){
            return false;
         }
      }
      size_reduced.push_back(size_reduced_flag);
   }

   //Now try to expand to the original size
   for(int i = 0, max = (int)buffers.size()
      ;i < max
      ;++i){
      if(!size_reduced[i])  continue;
      std::size_t received_size;
      std::size_t request_size =  received_sizes[i];
      if(boost_cont_allocation_command
         ( BOOST_CONTAINER_EXPAND_FWD, 1, request_size
         , request_size, &received_size, (char*)buffers[i]).first){
         if(received_size != request_size){
            return false;
         }
      }
      else{
         return false;
      }
   }

   //Deallocate it in non sequential order
   for(int j = 0, max = (int)buffers.size()
      ;j < max
      ;++j){
      int pos = (j%4)*((int)buffers.size())/4;
      boost_cont_free(buffers[pos]);
      buffers.erase(buffers.begin()+pos);
   }

   return 0 != boost_cont_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
}

//This test allocates until there is no more memory
//and after that deallocates the odd buffers to
//make room for expansions. The expansion will probably
//success since the deallocation left room for that.

bool test_allocation_deallocation_expand()
{
   boost_cont_malloc_check();
   std::vector<void*> buffers;

   //Allocate buffers with extra memory
   for(int i = 0; i != NumIt; ++i){
      void *ptr = boost_cont_malloc(i);
      if(!ptr)
         break;
      buffers.push_back(ptr);
   }

   //Now deallocate the half of the blocks
   //so expand maybe can merge new free blocks
   for(int i = 0, max = (int)buffers.size()
      ;i < max
      ;++i){
      if(i%2){
         boost_cont_free(buffers[i]);
         buffers[i] = 0;
      }
   }

   //Now try to expand to the double of the size
   for(int i = 0, max = (int)buffers.size()
      ;i < max
      ;++i){
      //
      if(buffers[i]){
         std::size_t received_size;
         std::size_t min_size = i+1;
         std::size_t preferred_size = i*2;
         preferred_size = min_size > preferred_size ? min_size : preferred_size;

         while(boost_cont_allocation_command
            ( BOOST_CONTAINER_EXPAND_FWD, 1, min_size
            , preferred_size, &received_size, (char*)buffers[i]).first){
            //Check received size is bigger than minimum
            if(received_size < min_size){
               return false;
            }
            //Now, try to expand further
            min_size       = received_size+1;
            preferred_size = min_size*2;
         }
      }
   }

   //Now erase null values from the vector
   buffers.erase(std::remove(buffers.begin(), buffers.end(), (void*)0)
                ,buffers.end());

   //Deallocate it in non sequential order
   for(int j = 0, max = (int)buffers.size()
      ;j < max
      ;++j){
      int pos = (j%4)*((int)buffers.size())/4;
      boost_cont_free(buffers[pos]);
      buffers.erase(buffers.begin()+pos);
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
}

//This test allocates until there is no more memory
//and after that deallocates all except the last.
//If the allocation algorithm is a bottom-up algorithm
//the last buffer will be in the end of the segment.
//Then the test will start expanding backwards, until
//the buffer fills all the memory

bool test_allocation_with_reuse()
{
   boost_cont_malloc_check();
   //We will repeat this test for different sized elements
   for(int sizeof_object = 1; sizeof_object < 20; ++sizeof_object){
      std::vector<void*> buffers;

      //Allocate buffers with extra memory
      for(int i = 0; i != NumIt; ++i){
         void *ptr = boost_cont_malloc(i*sizeof_object);
         if(!ptr)
            break;
         buffers.push_back(ptr);
      }

      //Now deallocate all except the latest
      //Now try to expand to the double of the size
      for(int i = 0, max = (int)buffers.size() - 1
         ;i < max
         ;++i){
         boost_cont_free(buffers[i]);
      }

      //Save the unique buffer and clear vector
      void *ptr = buffers.back();
      buffers.clear();

      //Now allocate with reuse
      std::size_t received_size = 0;
      for(int i = 0; i != NumIt; ++i){
         std::size_t min_size = (received_size/sizeof_object + 1)*sizeof_object;
         std::size_t prf_size = (received_size/sizeof_object + (i+1)*2)*sizeof_object;
         boost_cont_command_ret_t ret = boost_cont_allocation_command
            ( BOOST_CONTAINER_EXPAND_BWD, sizeof_object, min_size
            , prf_size, &received_size, (char*)ptr);
         //If we have memory, this must be a buffer reuse
         if(!ret.first)
            break;
         //If we have memory, this must be a buffer reuse
         if(!ret.second)
            return false;
         if(received_size < min_size)
            return false;
         ptr = ret.first;
      }
      //There should be only a single block so deallocate it
      boost_cont_free(ptr);
      boost_cont_malloc_check();
      if(!boost_cont_all_deallocated())
         return false;
   }
   return true;
}


//This test allocates memory with different alignments
//and checks returned memory is aligned.

bool test_aligned_allocation()
{
   boost_cont_malloc_check();
   //Allocate aligned buffers in a loop
   //and then deallocate it
   for(unsigned int i = 1; i != (1 << (sizeof(int)/2)); i <<= 1){
      for(unsigned int j = 1; j != 512; j <<= 1){
         void *ptr = boost_cont_memalign(i-1, j);
         if(!ptr){
            return false;
         }

         if(((std::size_t)ptr & (j - 1)) != 0)
            return false;
         boost_cont_free(ptr);
         //if(!a.all_memory_deallocated() || !a.check_sanity()){
         //   return false;
         //}
      }
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
}

//This test allocates memory with different alignments
//and checks returned memory is aligned.

bool test_continuous_aligned_allocation()
{
   boost_cont_malloc_check();
   std::vector<void*> buffers;
   //Allocate aligned buffers in a loop
   //and then deallocate it
   bool continue_loop = true;
   unsigned int MaxAlign = 4096;
   unsigned int MaxSize  = 4096;
   for(unsigned i = 1; i < MaxSize; i <<= 1){
      for(unsigned int j = 1; j < MaxAlign; j <<= 1){
         for(int k = 0; k != NumIt; ++k){
            void *ptr = boost_cont_memalign(i-1, j);
            buffers.push_back(ptr);
            if(!ptr){
               continue_loop = false;
               break;
            }

            if(((std::size_t)ptr & (j - 1)) != 0)
               return false;
         }
         //Deallocate all
         for(int k = (int)buffers.size(); k--;){
            boost_cont_free(buffers[k]);
         }
         buffers.clear();
         //if(!a.all_memory_deallocated() && a.check_sanity())
         //   return false;
         if(!continue_loop)
            break;
      }
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
}

//This test allocates multiple values until there is no more memory
//and after that deallocates all in the inverse order
bool test_many_equal_allocation()
{
   boost_cont_malloc_check();
   for( deallocation_type t = DirectDeallocation
      ; t != EndDeallocationType
      ; t = (deallocation_type)((int)t + 1)){
      //std::size_t free_memory = a.get_free_memory();

      std::vector<void*> buffers2;

      //Allocate buffers with extra memory
      for(int i = 0; i != NumIt; ++i){
         void *ptr = boost_cont_malloc(i);
         if(!ptr)
            break;
         //if(!a.check_sanity())
            //return false;
         buffers2.push_back(ptr);
      }

      //Now deallocate the half of the blocks
      //so expand maybe can merge new free blocks
      for(int i = 0, max = (int)buffers2.size()
         ;i < max
         ;++i){
         if(i%2){
            boost_cont_free(buffers2[i]);
            buffers2[i] = 0;
         }
      }

      //if(!a.check_sanity())
         //return false;

      std::vector<void*> buffers;
      for(int i = 0; i != NumIt/10; ++i){
         boost_cont_memchain chain;
         BOOST_CONTAINER_MEMCHAIN_INIT(&chain);
         boost_cont_multialloc_nodes((i+1)*2, i+1, DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &chain);
         boost_cont_memchain_it it = BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain);
         if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain, it))
            break;

         std::size_t n = 0;
         for(; !BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain, it); ++n){
            buffers.push_back(BOOST_CONTAINER_MEMIT_ADDR(it));
            BOOST_CONTAINER_MEMIT_NEXT(it);
         }
         if(n != std::size_t((i+1)*2))
            return false;
      }

      //if(!a.check_sanity())
         //return false;

      switch(t){
         case DirectDeallocation:
         {
            for(int j = 0, max = (int)buffers.size()
               ;j < max
               ;++j){
               boost_cont_free(buffers[j]);
            }
         }
         break;
         case InverseDeallocation:
         {
            for(int j = (int)buffers.size()
               ;j--
               ;){
               boost_cont_free(buffers[j]);
            }
         }
         break;
         case MixedDeallocation:
         {
            for(int j = 0, max = (int)buffers.size()
               ;j < max
               ;++j){
               int pos = (j%4)*((int)buffers.size())/4;
               boost_cont_free(buffers[pos]);
               buffers.erase(buffers.begin()+pos);
            }
         }
         break;
         default:
         break;
      }

      //Deallocate the rest of the blocks

      //Deallocate it in non sequential order
      for(int j = 0, max = (int)buffers2.size()
         ;j < max
         ;++j){
         int pos = (j%4)*((int)buffers2.size())/4;
         boost_cont_free(buffers2[pos]);
         buffers2.erase(buffers2.begin()+pos);
      }

      //bool ok = free_memory == a.get_free_memory() &&
               //a.all_memory_deallocated() && a.check_sanity();
      //if(!ok)  return ok;
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();
}

//This test allocates multiple values until there is no more memory
//and after that deallocates all in the inverse order

bool test_many_different_allocation()
{
   boost_cont_malloc_check();
   const std::size_t ArraySize = 11;
   std::size_t requested_sizes[ArraySize];
   for(std::size_t i = 0; i < ArraySize; ++i){
      requested_sizes[i] = 4*i;
   }

   for( deallocation_type t = DirectDeallocation
      ; t != EndDeallocationType
      ; t = (deallocation_type)((int)t + 1)){
      //std::size_t free_memory = a.get_free_memory();

      std::vector<void*> buffers2;

      //Allocate buffers with extra memory
      for(int i = 0; i != NumIt; ++i){
         void *ptr = boost_cont_malloc(i);
         if(!ptr)
            break;
         buffers2.push_back(ptr);
      }

      //Now deallocate the half of the blocks
      //so expand maybe can merge new free blocks
      for(int i = 0, max = (int)buffers2.size()
         ;i < max
         ;++i){
         if(i%2){
            boost_cont_free(buffers2[i]);
            buffers2[i] = 0;
         }
      }

      std::vector<void*> buffers;
      for(int i = 0; i != NumIt; ++i){
         boost_cont_memchain chain;
         BOOST_CONTAINER_MEMCHAIN_INIT(&chain);
         boost_cont_multialloc_arrays(ArraySize, requested_sizes, 1, DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &chain);
         boost_cont_memchain_it it = BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain);
         if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain, it))
            break;
         std::size_t n = 0;
         for(; !BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain, it); ++n){
            buffers.push_back(BOOST_CONTAINER_MEMIT_ADDR(it));
            BOOST_CONTAINER_MEMIT_NEXT(it);
         }
         if(n != ArraySize)
            return false;
      }

      switch(t){
         case DirectDeallocation:
         {
            for(int j = 0, max = (int)buffers.size()
               ;j < max
               ;++j){
               boost_cont_free(buffers[j]);
            }
         }
         break;
         case InverseDeallocation:
         {
            for(int j = (int)buffers.size()
               ;j--
               ;){
               boost_cont_free(buffers[j]);
            }
         }
         break;
         case MixedDeallocation:
         {
            for(int j = 0, max = (int)buffers.size()
               ;j < max
               ;++j){
               int pos = (j%4)*((int)buffers.size())/4;
               boost_cont_free(buffers[pos]);
               buffers.erase(buffers.begin()+pos);
            }
         }
         break;
         default:
         break;
      }

      //Deallocate the rest of the blocks

      //Deallocate it in non sequential order
      for(int j = 0, max = (int)buffers2.size()
         ;j < max
         ;++j){
         int pos = (j%4)*((int)buffers2.size())/4;
         boost_cont_free(buffers2[pos]);
         buffers2.erase(buffers2.begin()+pos);
      }

      //bool ok = free_memory == a.get_free_memory() &&
               //a.all_memory_deallocated() && a.check_sanity();
      //if(!ok)  return ok;
   }
   boost_cont_malloc_check();
   return 0 != boost_cont_all_deallocated();
}

bool test_many_deallocation()
{
   const std::size_t ArraySize = 11;
   std::vector<boost_cont_memchain> buffers;
   std::size_t requested_sizes[ArraySize];
   for(std::size_t i = 0; i < ArraySize; ++i){
      requested_sizes[i] = 4*i;
   }

   for(int i = 0; i != NumIt; ++i){
      boost_cont_memchain chain;
      BOOST_CONTAINER_MEMCHAIN_INIT(&chain);
      boost_cont_multialloc_arrays(ArraySize, requested_sizes, 1, DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &chain);
      boost_cont_memchain_it it = BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain);
      if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain, it))
         return false;
      buffers.push_back(chain);
   }
   for(int i = 0; i != NumIt; ++i){
      boost_cont_multidealloc(&buffers[i]);
   }
   buffers.clear();

   boost_cont_malloc_check();
   if(!boost_cont_all_deallocated())
      return false;

   for(int i = 0; i != NumIt; ++i){
      boost_cont_memchain chain;
      BOOST_CONTAINER_MEMCHAIN_INIT(&chain);
      boost_cont_multialloc_nodes(ArraySize, i*4+1, DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &chain);
      boost_cont_memchain_it it = BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain);
      if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain, it))
         return false;
      buffers.push_back(chain);
   }
   for(int i = 0; i != NumIt; ++i){
      boost_cont_multidealloc(&buffers[i]);
   }
   buffers.clear();

   boost_cont_malloc_check();
   if(!boost_cont_all_deallocated())
      return false;

   return true;
}

//This function calls all tests

bool test_all_allocation()
{
   std::cout << "Starting test_allocation"
             << std::endl;

   if(!test_allocation()){
      std::cout << "test_allocation_direct_deallocation failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_many_equal_allocation"
             << std::endl;

   if(!test_many_equal_allocation()){
      std::cout << "test_many_equal_allocation failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_many_different_allocation"
             << std::endl;

   if(!test_many_different_allocation()){
      std::cout << "test_many_different_allocation failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_allocation_shrink"
             << std::endl;

   if(!test_allocation_shrink()){
      std::cout << "test_allocation_shrink failed"
                << std::endl;
      return false;
   }

   if(!test_allocation_shrink_and_expand()){
      std::cout << "test_allocation_shrink_and_expand failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_allocation_expand"
             << std::endl;

   if(!test_allocation_expand()){
      std::cout << "test_allocation_expand failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_allocation_deallocation_expand"
             << std::endl;

   if(!test_allocation_deallocation_expand()){
      std::cout << "test_allocation_deallocation_expand failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_allocation_with_reuse"
             << std::endl;

   if(!test_allocation_with_reuse()){
      std::cout << "test_allocation_with_reuse failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_aligned_allocation"
             << std::endl;

   if(!test_aligned_allocation()){
      std::cout << "test_aligned_allocation failed"
                << std::endl;
      return false;
   }

   std::cout << "Starting test_continuous_aligned_allocation"
             << std::endl;

   if(!test_continuous_aligned_allocation()){
      std::cout << "test_continuous_aligned_allocation failed"
                << std::endl;
      return false;
   }

   if(!test_many_deallocation()){
      std::cout << "test_many_deallocation failed"
                << std::endl;
      return false;
   }

   return 0 != boost_cont_all_deallocated();
}

}}}   //namespace boost { namespace container { namespace test {


int main()
{
   if(!boost::container::test::test_all_allocation())
      return 1;
   return 0;
}