boost/libs/container/test/alloc_full_test.cpp - nest-cam/4320010/boost - Git at Google

 //////////////////////////////////////////////////////////////////////////////
 //
 // (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 <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;
 }
	//////////////////////////////////////////////////////////////////////////////
	//
	// (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 <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(i2);
	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(isizeof_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;
	}