/*

 * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1997

 * Moscow Center for SPARC Technology

 *

 * Copyright (c) 1999

 * Boris Fomitchev

 *

 * This material is provided "as is", with absolutely no warranty expressed

 * or implied. Any use is at your own risk.

 *

 * Permission to use or copy this software for any purpose is hereby granted

 * without fee, provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

#include "stlport_prefix.h"

#include <memory>

#if defined (__GNUC__) && (defined (__CYGWIN__) || defined (__MINGW32__)) && (!defined (__SYMBIAN32__))

#  include <malloc.h>

//#  define _STLP_MALLOC_USABLE_SIZE(__buf) malloc_usable_size(__buf)

#endif

#if defined (_STLP_PTHREADS) && !defined (_STLP_NO_THREADS)

#  include <pthread_alloc>

#  include <cerrno>

#endif

#include <stl/_threads.h>

#include "lock_free_slist.h"

#if defined(__SYMBIAN32__WSD__)

#include "libstdcppwsd.h"

#define __oom_handler 	get_oom_handler()

#define _S_lock 		get_allocator_S_lock()

#define _S_heap_size 	get_S_heap_size()

#define _S_start_free 	get_S_start_free()

#define _S_end_free		get_S_end_free()

#define _S_free_list 	get_S_free_list()

#define _S_chunk_allocator_lock 	get_S_chunk_allocator_lock()

#define _S_free_per_thread_states	get_S_free_per_thread_states()

#define _S_key						get_S_key()

#define _S_key_initialized			get_S_key_initialized()

#endif

#ifdef __SYMBIAN32__

extern "C"

{

IMPORT_C void* BackendAlloc(size_t );

IMPORT_C void BackendFree(void* );

}

EXPORT_C void* backend_allocate(size_t __n)

    {

    for (;;)

        {

        void* p = BackendAlloc(__n);

        if (p)

            {

            return p; 

            }

        // set_new_handler uses Dll::Tls. So only this threads new handler will be changed

        // for the time it is set back. No problems for other threads.

        std::new_handler nh_func  = std::set_new_handler(NULL);

        std::set_new_handler(nh_func);

        if (nh_func)

            {

            nh_func();

            }

        else

            {

            __THROW(std::bad_alloc());

            }

        }

    }

EXPORT_C void  backend_free(void* __p)

    {

    BackendFree(__p);

    }

#endif

#if defined (__WATCOMC__)

#  pragma warning 13 9

#  pragma warning 367 9

#  pragma warning 368 9

#endif

#if defined (_STLP_SGI_THREADS)

  // We test whether threads are in use before locking.

  // Perhaps this should be moved into stl_threads.h, but that

  // probably makes it harder to avoid the procedure call when

  // it isn't needed.

extern "C" {

  extern int __us_rsthread_malloc;

}

#endif

// Specialised debug form of malloc which does not provide "false"

// memory leaks when run with debug CRT libraries.

#if defined (_STLP_MSVC) && (_STLP_MSVC >= 1020 && defined (_STLP_DEBUG_ALLOC)) && !defined (_STLP_WCE)

#  include <crtdbg.h>

inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_malloc_dbg(__bytes, _CRT_BLOCK, __FILE__, __LINE__)); }

inline void __stlp_chunck_free(void* __p) { _free_dbg(__p, _CRT_BLOCK); }

#else  // !_DEBUG

#  ifdef _STLP_NODE_ALLOC_USE_MALLOC

#    include <cstdlib>

inline void* __stlp_chunk_malloc(size_t __bytes) { _STLP_CHECK_NULL_ALLOC(_STLP_VENDOR_CSTD::malloc(__bytes)); }

inline void __stlp_chunck_free(void* __p) { _STLP_VENDOR_CSTD::free(__p); }

#  else

inline void* __stlp_chunk_malloc(size_t __bytes) {

    return _STLP_STD::__stl_new(__bytes);

}

inline void __stlp_chunck_free(void* __p) {

    _STLP_STD::__stl_delete(__p);     

}

#  endif

#endif  // !_DEBUG

#define _S_FREELIST_INDEX(__bytes) ((__bytes - size_t(1)) >> (int)_ALIGN_SHIFT)

_STLP_BEGIN_NAMESPACE

class __malloc_alloc_impl {

private:

  static void* _S_oom_malloc(size_t __n) {

    __oom_handler_type __my_malloc_handler;

    void * __result;

    for (;;) {

      __my_malloc_handler = __oom_handler;

      if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }

      (*__my_malloc_handler)();

      __result = malloc(__n);

      if (__result) return(__result);

    }

#if defined (_STLP_NEED_UNREACHABLE_RETURN)

    return 0;

#endif

  }

#if defined(__SYMBIAN32__WSD__)  

  static _STLP_STATIC_MEMBER_DECLSPEC __oom_handler_type& get_oom_handler();

#else

  static __oom_handler_type __oom_handler;

#endif

public:

  // this one is needed for proper simple_alloc wrapping

  typedef char value_type;

  static void* allocate(size_t& __n) {

    void* __result = malloc(__n);

    if (0 == __result) {

      __result = _S_oom_malloc(__n);

    }

#if defined (_STLP_MALLOC_USABLE_SIZE)

    else {

      size_t __new_n = _STLP_MALLOC_USABLE_SIZE(__result);

      /*

      if (__n != __new_n) {

        printf("requested size %d, usable %d\n", __n, __new_n);

      }

      */

      __n = __new_n;

    }

#endif

    return __result;

  }

  static void deallocate(void* __p, size_t /* __n */) { free((char*)__p); }

  static __oom_handler_type set_malloc_handler(__oom_handler_type __f) {

    __oom_handler_type __old = __oom_handler;

    __oom_handler = __f;

    return __old;

  }

#if defined(__SYMBIAN32__WSD__)  

  friend void ::stdcpp_allocators_init();

#endif

};

#if !defined(__SYMBIAN32__WSD__)

// malloc_alloc out-of-memory handling

__oom_handler_type __malloc_alloc_impl::__oom_handler = __STATIC_CAST(__oom_handler_type, 0);

#endif

void* _STLP_CALL __malloc_alloc::allocate(size_t& __n)

{ return __malloc_alloc_impl::allocate(__n); }

__oom_handler_type _STLP_CALL __malloc_alloc::set_malloc_handler(__oom_handler_type __f)

{ return __malloc_alloc_impl::set_malloc_handler(__f); }

// *******************************************************

// Default node allocator.

// With a reasonable compiler, this should be roughly as fast as the

// original STL class-specific allocators, but with less fragmentation.

//

// Important implementation properties:

// 1. If the client request an object of size > _MAX_BYTES, the resulting

//    object will be obtained directly from malloc.

// 2. In all other cases, we allocate an object of size exactly

//    _S_round_up(requested_size).  Thus the client has enough size

//    information that we can return the object to the proper free list

//    without permanently losing part of the object.

//

#define _STLP_NFREELISTS 16

/*

 * On Symbian, the stlport is built as a dll and also dynamically linked against 

 * by the applications. The _STLP_USE_DYNAMIC_LIB should always be defined.

 * _STLP_LEAKS_PEDANTIC is defined to prevent the memory leaks in __node_alloc 

 * when the library is dynamically loaded and unloaded.

 */

#if defined (_STLP_LEAKS_PEDANTIC) && ( defined (_STLP_USE_DYNAMIC_LIB) || defined (__SYMBIAN32__) )

/*

 * We can only do cleanup of the node allocator memory pool if we are

 * sure that the STLport library is used as a shared one as it guaranties

 * the unicity of the node allocator instance. Without that guaranty node

 * allocator instances might exchange memory blocks making the implementation

 * of a cleaning process much more complicated.

 */

#  define _STLP_DO_CLEAN_NODE_ALLOC

#endif

/* When STLport is used without multi threaded safety we use the node allocator

 * implementation with locks as locks becomes no-op. The lock free implementation

 * always use system specific atomic operations which are slower than 'normal'

 * ones.

 */

#if defined (_STLP_THREADS) && \

    defined (_STLP_HAS_ATOMIC_FREELIST) && defined (_STLP_ATOMIC_ADD)

/*

 * We have an implementation of the atomic freelist (_STLP_atomic_freelist)

 * for this architecture and compiler.  That means we can use the non-blocking

 * implementation of the node-allocation engine.*/

#  define _STLP_USE_LOCK_FREE_IMPLEMENTATION

#endif

#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

#  if defined (_STLP_THREADS)

class _Node_Alloc_Lock {

public:

  _Node_Alloc_Lock() {

#  if defined (_STLP_SGI_THREADS)

    if (__us_rsthread_malloc)

#  endif

      _S_lock._M_acquire_lock();

  }

  ~_Node_Alloc_Lock() {

#  if defined (_STLP_SGI_THREADS)

    if (__us_rsthread_malloc)

#  endif

        _S_lock._M_release_lock();

  }

#if defined (__SYMBIAN32__WSD__)

  static _STLP_STATIC_MUTEX& get_allocator_S_lock();

#else

  static _STLP_STATIC_MUTEX _S_lock;

#endif

};

#if !defined(__SYMBIAN32__WSD__)

_STLP_STATIC_MUTEX _Node_Alloc_Lock::_S_lock _STLP_MUTEX_INITIALIZER;

#endif

#  else

class _Node_Alloc_Lock {

public:

  _Node_Alloc_Lock() { }

  ~_Node_Alloc_Lock() { }

};

#  endif

struct _Node_alloc_obj {

  _Node_alloc_obj * _M_next;

};

#endif

class __node_alloc_impl {

_STLP_PRIVATE:

  static inline size_t _STLP_CALL _S_round_up(size_t __bytes)

  { return (((__bytes) + (size_t)_ALIGN-1) & ~((size_t)_ALIGN - 1)); }

#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

  typedef _STLP_atomic_freelist::item   _Obj;

  typedef _STLP_atomic_freelist         _Freelist;

  typedef _STLP_atomic_freelist         _ChunkList;

  // Header of blocks of memory that have been allocated as part of

  // a larger chunk but have not yet been chopped up into nodes.

  struct _FreeBlockHeader : public _STLP_atomic_freelist::item {

    char* _M_end;     // pointer to end of free memory

  };

#else

  typedef _Node_alloc_obj       _Obj;

  typedef _Obj* _STLP_VOLATILE  _Freelist;

  typedef _Obj*                 _ChunkList;

#endif

private:

  // Returns an object of size __n, and optionally adds to size __n free list.

  static _Obj* _S_refill(size_t __n);

  // Allocates a chunk for nobjs of size __p_size.  nobjs may be reduced

  // if it is inconvenient to allocate the requested number.

  static char* _S_chunk_alloc(size_t __p_size, int& __nobjs);

  // Chunk allocation state.

#if defined(__SYMBIAN32__WSD__)  

  static _Freelist* get_S_free_list();

#else

  static _Freelist _S_free_list[_STLP_NFREELISTS];

#endif

  // Amount of total allocated memory

#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

  static _STLP_VOLATILE __stl_atomic_t _S_heap_size;

#else

#if defined(__SYMBIAN32__WSD__)

  static size_t& get_S_heap_size();

#else

  static size_t _S_heap_size;

#endif

#endif

#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

  // List of blocks of free memory

  static _STLP_atomic_freelist  _S_free_mem_blocks;

#else

#if defined(__SYMBIAN32__WSD__)

  // Start of the current free memory buffer

  static char*& get_S_start_free();

  // End of the current free memory buffer

  static char*& get_S_end_free();

#else

  // Start of the current free memory buffer

  static char* _S_start_free;

  // End of the current free memory buffer

  static char* _S_end_free;

#endif

#endif

#if defined (_STLP_DO_CLEAN_NODE_ALLOC)

public:

  // Methods to report alloc/dealloc calls to the counter system.

#  if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

  typedef _STLP_VOLATILE __stl_atomic_t _AllocCounter;

#  else

  typedef __stl_atomic_t _AllocCounter;

#  endif

  static _AllocCounter& _STLP_CALL _S_alloc_counter();

  static void _S_alloc_call();

  static void _S_dealloc_call();

private:

  // Free all the allocated chuncks of memory

  static void _S_chunk_dealloc();

  // Beginning of the linked list of allocated chunks of memory

  static _ChunkList _S_chunks;

#endif /* _STLP_DO_CLEAN_NODE_ALLOC */

public:

  /* __n must be > 0      */

  static void* _M_allocate(size_t& __n);

  /* __p may not be 0 */

  static void _M_deallocate(void *__p, size_t __n);

#if defined(__SYMBIAN32__WSD__)

	friend void ::stdcpp_allocators_init();

#endif

};

#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

void* __node_alloc_impl::_M_allocate(size_t& __n) {

  __n = _S_round_up(__n);

  _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);

  _Obj *__r;

  // Acquire the lock here with a constructor call.

  // This ensures that it is released in exit or during stack

  // unwinding.

  _Node_Alloc_Lock __lock_instance;

  if ( (__r  = *__my_free_list) != 0 ) {

    *__my_free_list = __r->_M_next;

  } else {

    __r = _S_refill(__n);

  }

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  _S_alloc_call();

#  endif

  // lock is released here

  return __r;

}

void __node_alloc_impl::_M_deallocate(void *__p, size_t __n) {

  _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);

  _Obj * __pobj = __STATIC_CAST(_Obj*, __p);

  // acquire lock

  _Node_Alloc_Lock __lock_instance;

  __pobj->_M_next = *__my_free_list;

  *__my_free_list = __pobj;

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  _S_dealloc_call();

#  endif

  // lock is released here

}

/* We allocate memory in large chunks in order to avoid fragmenting     */

/* the malloc heap too much.                                            */

/* We assume that size is properly aligned.                             */

/* We hold the allocation lock.                                         */

char* __node_alloc_impl::_S_chunk_alloc(size_t _p_size, int& __nobjs) {

  char* __result;

  size_t __total_bytes = _p_size * __nobjs;

  size_t __bytes_left = _S_end_free - _S_start_free;

  if (__bytes_left > 0) {

    if (__bytes_left >= __total_bytes) {

      __result = _S_start_free;

      _S_start_free += __total_bytes;

      return __result;

    }

    if (__bytes_left >= _p_size) {

      __nobjs = (int)(__bytes_left / _p_size);

      __total_bytes = _p_size * __nobjs;

      __result = _S_start_free;

      _S_start_free += __total_bytes;

      return __result;

    }

    // Try to make use of the left-over piece.

    _Obj* _STLP_VOLATILE* __my_free_list = _S_free_list + _S_FREELIST_INDEX(__bytes_left);

    __REINTERPRET_CAST(_Obj*, _S_start_free)->_M_next = *__my_free_list;

    *__my_free_list = __REINTERPRET_CAST(_Obj*, _S_start_free);

  }

  size_t __bytes_to_get =

    2 * __total_bytes + _S_round_up(_S_heap_size >> 4)

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

    + sizeof(_Obj)

#  endif

    ;

  _S_start_free = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));

  if (0 == _S_start_free) {

    _Obj* _STLP_VOLATILE* __my_free_list;

    _Obj* __p;

    // Try to do with what we have.  That can't hurt.

    // We do not try smaller requests, since that tends

    // to result in disaster on multi-process machines.

    for (size_t __i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {

      __my_free_list = _S_free_list + _S_FREELIST_INDEX(__i);

      __p = *__my_free_list;

      if (0 != __p) {

        *__my_free_list = __p -> _M_next;

        _S_start_free = __REINTERPRET_CAST(char*, __p);

        _S_end_free = _S_start_free + __i;

        return _S_chunk_alloc(_p_size, __nobjs);

        // Any leftover piece will eventually make it to the

        // right free list.

      }

    }

    _S_end_free = 0;    // In case of exception.

    _S_start_free = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));

    /*

    (char*)malloc_alloc::allocate(__bytes_to_get);

    */

    // This should either throw an

    // exception or remedy the situation.  Thus we assume it

    // succeeded.

  }

  _S_heap_size += __bytes_to_get;

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  __REINTERPRET_CAST(_Obj*, _S_start_free)->_M_next = _S_chunks;

  _S_chunks = __REINTERPRET_CAST(_Obj*, _S_start_free);

#  endif

  _S_end_free = _S_start_free + __bytes_to_get;

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  _S_start_free += sizeof(_Obj);

#  endif

  return _S_chunk_alloc(_p_size, __nobjs);

}

/* Returns an object of size __n, and optionally adds to size __n free list.*/

/* We assume that __n is properly aligned.                                  */

/* We hold the allocation lock.                                             */

_Node_alloc_obj* __node_alloc_impl::_S_refill(size_t __n) {

  int __nobjs = 20;

  char* __chunk = _S_chunk_alloc(__n, __nobjs);

  if (1 == __nobjs) return __REINTERPRET_CAST(_Obj*, __chunk);

  _Obj* _STLP_VOLATILE* __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);

  _Obj* __result;

  _Obj* __current_obj;

  _Obj* __next_obj;

  /* Build free list in chunk */

  __result = __REINTERPRET_CAST(_Obj*, __chunk);

  *__my_free_list = __next_obj = __REINTERPRET_CAST(_Obj*, __chunk + __n);

  for (--__nobjs; --__nobjs; ) {

    __current_obj = __next_obj;

    __next_obj = __REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __next_obj) + __n);

    __current_obj->_M_next = __next_obj;

  }

  __next_obj->_M_next = 0;

  return __result;

}

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

void __node_alloc_impl::_S_alloc_call()

{ ++_S_alloc_counter(); }

void __node_alloc_impl::_S_dealloc_call() {

  __stl_atomic_t &counter = _S_alloc_counter();

  if (--counter == 0)

  { _S_chunk_dealloc(); }

}

/* We deallocate all the memory chunks      */

void __node_alloc_impl::_S_chunk_dealloc() {

  _Obj *__pcur = _S_chunks, *__pnext;

  while (__pcur != 0) {

    __pnext = __pcur->_M_next;

    __stlp_chunck_free(__pcur);

    __pcur = __pnext;

  }

  _S_chunks = 0;

  _S_start_free = _S_end_free = 0;

  _S_heap_size = 0;

  // Reinterprest cast cant remove volatileness. So using C style cast

  memset((char*)(&_S_free_list[0]), 0, _STLP_NFREELISTS * sizeof(_Obj*));

}

#  endif /* _STLP_DO_CLEAN_NODE_ALLOC */

#else /* !defined(_STLP_USE_LOCK_FREE_IMPLEMENTATION) */

void* __node_alloc_impl::_M_allocate(size_t& __n) {

  __n = _S_round_up(__n);

  _Obj* __r = _S_free_list[_S_FREELIST_INDEX(__n)].pop();

  if (__r  == 0)

  { __r = _S_refill(__n); }

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  _S_alloc_call();

#  endif

  return __r;

}

void __node_alloc_impl::_M_deallocate(void *__p, size_t __n) {

  _S_free_list[_S_FREELIST_INDEX(__n)].push(__STATIC_CAST(_Obj*, __p));

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  _S_dealloc_call();

#  endif

}

/* Returns an object of size __n, and optionally adds additional ones to    */

/* freelist of objects of size __n.                                         */

/* We assume that __n is properly aligned.                                  */

__node_alloc_impl::_Obj* __node_alloc_impl::_S_refill(size_t __n) {

  int __nobjs = 20;

  char* __chunk = _S_chunk_alloc(__n, __nobjs);

  if (__nobjs <= 1)

    return __REINTERPRET_CAST(_Obj*, __chunk);

  // Push all new nodes (minus first one) onto freelist

  _Obj* __result   = __REINTERPRET_CAST(_Obj*, __chunk);

  _Obj* __cur_item = __result;

  _Freelist* __my_freelist = _S_free_list + _S_FREELIST_INDEX(__n);

  for (--__nobjs; __nobjs != 0; --__nobjs) {

    __cur_item  = __REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __cur_item) + __n);

    __my_freelist->push(__cur_item);

  }

  return __result;

}

/* We allocate memory in large chunks in order to avoid fragmenting     */

/* the malloc heap too much.                                            */

/* We assume that size is properly aligned.                             */

char* __node_alloc_impl::_S_chunk_alloc(size_t _p_size, int& __nobjs) {

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  //We are going to add a small memory block to keep all the allocated blocks

  //address, we need to do so respecting the memory alignment. The following

  //static assert checks that the reserved block is big enough to store a pointer.

  _STLP_STATIC_ASSERT(sizeof(_Obj) <= _ALIGN)

#  endif

  char*  __result       = 0;

  __stl_atomic_t __total_bytes  = __STATIC_CAST(__stl_atomic_t, _p_size) * __nobjs;

  _FreeBlockHeader* __block = __STATIC_CAST(_FreeBlockHeader*, _S_free_mem_blocks.pop());

  if (__block != 0) {

    // We checked a block out and can now mess with it with impugnity.

    // We'll put the remainder back into the list if we're done with it below.

    char*  __buf_start  = __REINTERPRET_CAST(char*, __block);

    __stl_atomic_t __bytes_left = __block->_M_end - __buf_start;

    if ((__bytes_left < __total_bytes) && (__bytes_left >= __STATIC_CAST(__stl_atomic_t, _p_size))) {

      // There's enough left for at least one object, but not as much as we wanted

      __result      = __buf_start;

      __nobjs       = (int)(__bytes_left/_p_size);

      __total_bytes = __STATIC_CAST(__stl_atomic_t, _p_size) * __nobjs;

      __bytes_left -= __total_bytes;

      __buf_start  += __total_bytes;

    }

    else if (__bytes_left >= __total_bytes) {

      // The block has enough left to satisfy all that was asked for

      __result      = __buf_start;

      __bytes_left -= __total_bytes;

      __buf_start  += __total_bytes;

    }

    if (__bytes_left != 0) {

      // There is still some memory left over in block after we satisfied our request.

      if ((__result != 0) && (__bytes_left >= sizeof(_FreeBlockHeader))) {

        // We were able to allocate at least one object and there is still enough

        // left to put remainder back into list.

        _FreeBlockHeader* __newblock = __REINTERPRET_CAST(_FreeBlockHeader*, __buf_start);

        __newblock->_M_end  = __block->_M_end;

        _S_free_mem_blocks.push(__newblock);

      }

      else {

        // We were not able to allocate enough for at least one object.

        // Shove into freelist of nearest (rounded-down!) size.

        size_t __rounded_down = _S_round_up(__bytes_left + 1) - (size_t)_ALIGN;

        if (__rounded_down > 0)

          _S_free_list[_S_FREELIST_INDEX(__rounded_down)].push((_Obj*)__buf_start);

      }

    }

    if (__result != 0)

      return __result;

  }

  // We couldn't satisfy it from the list of free blocks, get new memory.

  __stl_atomic_t __bytes_to_get = 2 * __total_bytes + __STATIC_CAST(__stl_atomic_t, _S_round_up(_S_heap_size >> 4))

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

    + _ALIGN

#  endif

    ;

  __result = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));

  // Alignment check

  _STLP_VERBOSE_ASSERT(((__REINTERPRET_CAST(size_t, __result) & __STATIC_CAST(size_t, _ALIGN - 1)) == 0), _StlMsg_DBA_DELETED_TWICE)

  if (0 == __result) {

    // Allocation failed; try to canibalize from freelist of a larger object size.

    for (size_t __i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {

      _Obj* __p  = _S_free_list[_S_FREELIST_INDEX(__i)].pop();

      if (0 != __p) {

        if (__i < sizeof(_FreeBlockHeader)) {

          // Not enough to put into list of free blocks, divvy it up here.

          // Use as much as possible for this request and shove remainder into freelist.

          __nobjs = (int)(__i/_p_size);

          __total_bytes = __nobjs * __STATIC_CAST(__stl_atomic_t, _p_size);

          size_t __bytes_left = __i - __total_bytes;

          size_t __rounded_down = _S_round_up(__bytes_left+1) - (size_t)_ALIGN;

          if (__rounded_down > 0) {

            _S_free_list[_S_FREELIST_INDEX(__rounded_down)].push(__REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __p) + __total_bytes));

          }

          return __REINTERPRET_CAST(char*, __p);

        }

        else {

          // Add node to list of available blocks and recursively allocate from it.

          _FreeBlockHeader* __newblock = (_FreeBlockHeader*)__p;

          __newblock->_M_end  = __REINTERPRET_CAST(char*, __p) + __i;

          _S_free_mem_blocks.push(__newblock);

          return _S_chunk_alloc(_p_size, __nobjs);

        }

      }

    }

    // We were not able to find something in a freelist, try to allocate a smaller amount.

    __bytes_to_get  = __total_bytes

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

      + _ALIGN

#  endif

      ;

    __result = __STATIC_CAST(char*, __stlp_chunk_malloc(__bytes_to_get));

    // Alignment check

    _STLP_VERBOSE_ASSERT(((__REINTERPRET_CAST(size_t, __result) & __STATIC_CAST(size_t, _ALIGN - 1)) == 0), _StlMsg_DBA_DELETED_TWICE)

    // This should either throw an exception or remedy the situation.

    // Thus we assume it succeeded.

  }

  _STLP_ATOMIC_ADD(&_S_heap_size, __bytes_to_get);

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

  // We have to track the allocated memory chunks for release on exit.

  _S_chunks.push(__REINTERPRET_CAST(_Obj*, __result));

  __result       += _ALIGN;

  __bytes_to_get -= _ALIGN;

#  endif

  if (__bytes_to_get > __total_bytes) {

    // Push excess memory allocated in this chunk into list of free memory blocks

    _FreeBlockHeader* __freeblock = __REINTERPRET_CAST(_FreeBlockHeader*, __result + __total_bytes);

    __freeblock->_M_end  = __result + __bytes_to_get;

    _S_free_mem_blocks.push(__freeblock);

  }

  return __result;

}

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)

void __node_alloc_impl::_S_alloc_call()

{ _STLP_ATOMIC_INCREMENT(&_S_alloc_counter()); }

void __node_alloc_impl::_S_dealloc_call() {

  _STLP_VOLATILE __stl_atomic_t *pcounter = &_S_alloc_counter();

  if (_STLP_ATOMIC_DECREMENT(pcounter) == 0)

    _S_chunk_dealloc();

}

/* We deallocate all the memory chunks      */

void __node_alloc_impl::_S_chunk_dealloc() {

  // Note: The _Node_alloc_helper class ensures that this function

  // will only be called when the (shared) library is unloaded or the

  // process is shutdown.  It's thus not possible that another thread

  // is currently trying to allocate a node (we're not thread-safe here).

  //

  // Clear the free blocks and all freelistst.  This makes sure that if

  // for some reason more memory is allocated again during shutdown

  // (it'd also be really nasty to leave references to deallocated memory).

  _S_free_mem_blocks.clear();

  _S_heap_size      = 0;

  for (size_t __i = 0; __i < _STLP_NFREELISTS; ++__i) {

    _S_free_list[__i].clear();

  }

  // Detach list of chunks and free them all

  _Obj* __chunk = _S_chunks.clear();

  while (__chunk != 0) {

    _Obj* __next = __chunk->_M_next;

    __stlp_chunck_free(__chunk);

    __chunk  = __next;

  }

}

#  endif /* _STLP_DO_CLEAN_NODE_ALLOC */

#endif /* !defined(_STLP_USE_LOCK_FREE_IMPLEMENTATION) */

#if defined (_STLP_DO_CLEAN_NODE_ALLOC)

struct __node_alloc_cleaner {

  ~__node_alloc_cleaner()

      {

      __node_alloc_impl::_S_dealloc_call(); 

      }

};

#  if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

_STLP_VOLATILE __stl_atomic_t& _STLP_CALL

#  else

__stl_atomic_t& _STLP_CALL

#  endif

__node_alloc_impl::_S_alloc_counter() {

  static _AllocCounter _S_counter = 1;

  static __node_alloc_cleaner _S_node_alloc_cleaner;

  return _S_counter;

}

#endif

#if !defined(__SYMBIAN32__WSD__)

#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

_Node_alloc_obj * _STLP_VOLATILE

__node_alloc_impl::_S_free_list[_STLP_NFREELISTS]

= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

// The 16 zeros are necessary to make version 4.1 of the SunPro

// compiler happy.  Otherwise it appears to allocate too little

// space for the array.

#else

_STLP_atomic_freelist __node_alloc_impl::_S_free_list[_STLP_NFREELISTS];

_STLP_atomic_freelist __node_alloc_impl::_S_free_mem_blocks;

#endif

#if !defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

char *__node_alloc_impl::_S_start_free = 0;

char *__node_alloc_impl::_S_end_free = 0;

#endif

#if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

_STLP_VOLATILE __stl_atomic_t

#else

size_t

#endif

__node_alloc_impl::_S_heap_size = 0;

#endif //__SYMBIAN32__WSD__

#if defined (_STLP_DO_CLEAN_NODE_ALLOC)

#  if defined (_STLP_USE_LOCK_FREE_IMPLEMENTATION)

_STLP_atomic_freelist __node_alloc_impl::_S_chunks;

#  else

_Node_alloc_obj* __node_alloc_impl::_S_chunks  = 0;

#  endif

#endif

_STLP_DECLSPEC void * _STLP_CALL __node_alloc::_M_allocate(size_t& __n)

{ return __node_alloc_impl::_M_allocate(__n); }

_STLP_DECLSPEC void _STLP_CALL __node_alloc::_M_deallocate(void *__p, size_t __n)

{ __node_alloc_impl::_M_deallocate(__p, __n); }

#if defined (_STLP_PTHREADS) && !defined (_STLP_NO_THREADS)

#  define _STLP_DATA_ALIGNMENT 8

_STLP_MOVE_TO_PRIV_NAMESPACE

// *******************************************************

// __perthread_alloc implementation

union _Pthread_alloc_obj {

  union _Pthread_alloc_obj * __free_list_link;

  char __client_data[_STLP_DATA_ALIGNMENT];    /* The client sees this.    */

};

// Pthread allocators don't appear to the client to have meaningful

// instances.  We do in fact need to associate some state with each

// thread.  That state is represented by _Pthread_alloc_per_thread_state.

struct _Pthread_alloc_per_thread_state {

  typedef _Pthread_alloc_obj __obj;

  enum { _S_NFREELISTS = _MAX_BYTES / _STLP_DATA_ALIGNMENT };

  // Free list link for list of available per thread structures.

  // When one of these becomes available for reuse due to thread

  // termination, any objects in its free list remain associated

  // with it.  The whole structure may then be used by a newly

  // created thread.

  _Pthread_alloc_per_thread_state() : __next(0)

  { memset((void *)__CONST_CAST(_Pthread_alloc_obj**, __free_list), 0, (size_t)_S_NFREELISTS * sizeof(__obj *)); }

  // Returns an object of size __n, and possibly adds to size n free list.

  void *_M_refill(size_t __n);

  _Pthread_alloc_obj* volatile __free_list[_S_NFREELISTS];

  _Pthread_alloc_per_thread_state *__next;

  // this data member is only to be used by per_thread_allocator, which returns memory to the originating thread.

  _STLP_mutex _M_lock;

};

// Pthread-specific allocator.

class _Pthread_alloc_impl {

public: // but only for internal use:

  typedef _Pthread_alloc_per_thread_state __state_type;

  typedef char value_type;

  // Allocates a chunk for nobjs of size size.  nobjs may be reduced

  // if it is inconvenient to allocate the requested number.

  static char *_S_chunk_alloc(size_t __size, size_t &__nobjs, __state_type*);

  enum {_S_ALIGN = _STLP_DATA_ALIGNMENT};

  static size_t _S_round_up(size_t __bytes)

  { return (((__bytes) + (int)_S_ALIGN - 1) & ~((int)_S_ALIGN - 1)); }

  static size_t _S_freelist_index(size_t __bytes)

  { return (((__bytes) + (int)_S_ALIGN - 1) / (int)_S_ALIGN - 1); }

private:

  // Chunk allocation state. And other shared state.

  // Protected by _S_chunk_allocator_lock.

#if defined(__SYMBIAN32__WSD__)

public:	

	static void pt_wsd_init() {

		get_S_free_per_thread_states() = 0;

		get_S_key() = 0;

		get_S_chunk_allocator_lock()._M_lock.iState   = _ENeedsNormalInit;

		get_S_chunk_allocator_lock()._M_lock.iPtr     = 0;

		get_S_chunk_allocator_lock()._M_lock.iReentry = 0;

		get_S_key_initialized() = false;

		get_S_start_free() = 0;

		get_S_end_free() = 0;

		get_S_heap_size() = 0;

	}

private:

  static _STLP_STATIC_MUTEX& get_S_chunk_allocator_lock()

	{ return get_libcpp_wsd().wsd_pt_S_chunk_allocator_lock; }

  static char*& get_S_start_free()

  	{ return get_libcpp_wsd().wsd_pt_S_start_free; }

  static char*& get_S_end_free()

  	{ return get_libcpp_wsd().wsd_pt_S_end_free; }

  static size_t& get_S_heap_size()

  	{ return get_libcpp_wsd().wsd_pt_S_heap_size; }

  static __state_type*& get_S_free_per_thread_states()

	{ return get_libcpp_wsd().wsd_pt_S_free_per_thread_states; }

  static pthread_key_t& get_S_key()

  	{ return get_libcpp_wsd().wsd_pt_S_key; }

  static bool& get_S_key_initialized()

  	{ return get_libcpp_wsd().wsd_pt_S_key_initialized; }

#else

  static _STLP_STATIC_MUTEX _S_chunk_allocator_lock;

  static char *_S_start_free;

  static char *_S_end_free;

  static size_t _S_heap_size;

  static __state_type *_S_free_per_thread_states;

  static pthread_key_t _S_key;

  static bool _S_key_initialized;

#endif

  // Pthread key under which per thread state is stored.

  // Allocator instances that are currently unclaimed by any thread.

  static void _S_destructor(void *instance);

  // Function to be called on thread exit to reclaim per thread

  // state.

  static __state_type *_S_new_per_thread_state();

public:

  // Return a recycled or new per thread state.

  static __state_type *_S_get_per_thread_state();

private:

        // ensure that the current thread has an associated

        // per thread state.

  class _M_lock;

  friend class _M_lock;

  class _M_lock {

  public:

    _M_lock () { _S_chunk_allocator_lock._M_acquire_lock(); }

    ~_M_lock () { _S_chunk_allocator_lock._M_release_lock(); }

  };

public:

  /* n must be > 0      */

  static void * allocate(size_t& __n);

  /* p may not be 0 */

  static void deallocate(void *__p, size_t __n);

  // boris : versions for per_thread_allocator

  /* n must be > 0      */

  static void * allocate(size_t& __n, __state_type* __a);

  /* p may not be 0 */

  static void deallocate(void *__p, size_t __n, __state_type* __a);

  static void * reallocate(void *__p, size_t __old_sz, size_t& __new_sz);

};

/* Returns an object of size n, and optionally adds to size n free list.*/

/* We assume that n is properly aligned.                                */

/* We hold the allocation lock.                                         */

void *_Pthread_alloc_per_thread_state::_M_refill(size_t __n) {

  typedef _Pthread_alloc_obj __obj;

  size_t __nobjs = 128;

  char * __chunk = _Pthread_alloc_impl::_S_chunk_alloc(__n, __nobjs, this);

  __obj * volatile * __my_free_list;

  __obj * __result;

  __obj * __current_obj, * __next_obj;

  size_t __i;

  if (1 == __nobjs)  {

    return __chunk;

  }

  __my_free_list = __free_list + _Pthread_alloc_impl::_S_freelist_index(__n);

  /* Build free list in chunk */

  __result = (__obj *)__chunk;

  *__my_free_list = __next_obj = (__obj *)(__chunk + __n);

  for (__i = 1; ; ++__i) {

    __current_obj = __next_obj;

    __next_obj = (__obj *)((char *)__next_obj + __n);

    if (__nobjs - 1 == __i) {

      __current_obj -> __free_list_link = 0;

      break;

    } else {

      __current_obj -> __free_list_link = __next_obj;

    }

  }

  return __result;

}

void _Pthread_alloc_impl::_S_destructor(void *__instance) {

  _M_lock __lock_instance;  // Need to acquire lock here.

  _Pthread_alloc_per_thread_state* __s = (_Pthread_alloc_per_thread_state*)__instance;

  __s -> __next = _S_free_per_thread_states;