diff DEPENDENCIES/generic/include/boost/pool/simple_segregated_storage.hpp @ 16:2665513ce2d3

Add boost headers

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/DEPENDENCIES/generic/include/boost/pool/simple_segregated_storage.hpp	Tue Aug 05 11:11:38 2014 +0100
@@ -0,0 +1,377 @@
+// Copyright (C) 2000, 2001 Stephen Cleary
+//
+// 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 for updates, documentation, and revision history.
+
+#ifndef BOOST_SIMPLE_SEGREGATED_STORAGE_HPP
+#define BOOST_SIMPLE_SEGREGATED_STORAGE_HPP
+
+/*!
+  \file
+  \brief Simple Segregated Storage.
+  \details A simple segregated storage implementation:
+  simple segregated storage is the basic idea behind the Boost Pool library.
+  Simple segregated storage is the simplest, and probably the fastest,
+  memory allocation/deallocation algorithm.
+  It begins by partitioning a memory block into fixed-size chunks.
+  Where the block comes from is not important until implementation time.
+  A Pool is some object that uses Simple Segregated Storage in this fashion.
+*/
+
+// std::greater
+#include <functional>
+
+#include <boost/pool/poolfwd.hpp>
+
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable:4127)  // Conditional expression is constant
+#endif
+
+#ifdef BOOST_POOL_VALIDATE
+#  define BOOST_POOL_VALIDATE_INTERNALS validate();
+#else
+#  define BOOST_POOL_VALIDATE_INTERNALS
+#endif
+
+namespace boost {
+
+/*! 
+
+\brief Simple Segregated Storage is the simplest, and probably the fastest,
+memory allocation/deallocation algorithm.  It is responsible for
+partitioning a memory block into fixed-size chunks: where the block comes from 
+is determined by the client of the class.
+
+\details Template class simple_segregated_storage controls access to a free list of memory chunks. 
+Please note that this is a very simple class, with preconditions on almost all its functions. It is intended to 
+be the fastest and smallest possible quick memory allocator - e.g., something to use in embedded systems. 
+This class delegates many difficult preconditions to the user (i.e., alignment issues).
+
+An object of type simple_segregated_storage<SizeType>  is empty  if its free list is empty. 
+If it is not empty, then it is ordered  if its free list is ordered. A free list is ordered if repeated calls 
+to <tt>malloc()</tt> will result in a constantly-increasing sequence of values, as determined by <tt>std::less<void *></tt>. 
+A member function is <i>order-preserving</i> if the free list maintains its order orientation (that is, an 
+ordered free list is still ordered after the member function call).
+
+*/
+template <typename SizeType>
+class simple_segregated_storage
+{
+  public:
+    typedef SizeType size_type;
+
+  private:
+    simple_segregated_storage(const simple_segregated_storage &);
+    void operator=(const simple_segregated_storage &);
+
+    static void * try_malloc_n(void * & start, size_type n,
+        size_type partition_size);
+
+  protected:
+    void * first; /*!< This data member is the free list.
+      It points to the first chunk in the free list,
+      or is equal to 0 if the free list is empty.
+    */
+
+    void * find_prev(void * ptr);
+
+    // for the sake of code readability :)
+    static void * & nextof(void * const ptr)
+    { //! The return value is just *ptr cast to the appropriate type. ptr must not be 0. (For the sake of code readability :)
+    //! As an example, let us assume that we want to truncate the free list after the first chunk.
+    //! That is, we want to set *first to 0; this will result in a free list with only one entry.
+    //! The normal way to do this is to first cast first to a pointer to a pointer to void,
+    //! and then dereference and assign (*static_cast<void **>(first) = 0;).
+    //! This can be done more easily through the use of this convenience function (nextof(first) = 0;).
+    //! \returns dereferenced pointer.
+      return *(static_cast<void **>(ptr));
+    }
+
+  public:
+    // Post: empty()
+    simple_segregated_storage()
+    :first(0)
+    { //! Construct empty storage area.
+      //! \post empty()
+    }
+
+    static void * segregate(void * block,
+        size_type nsz, size_type npartition_sz,
+        void * end = 0);
+
+    // Same preconditions as 'segregate'
+    // Post: !empty()
+    void add_block(void * const block,
+        const size_type nsz, const size_type npartition_sz)
+    { //! Add block
+      //! Segregate this block and merge its free list into the
+      //!  free list referred to by "first".
+      //! \pre Same as segregate.
+      //!  \post !empty()
+      BOOST_POOL_VALIDATE_INTERNALS
+      first = segregate(block, nsz, npartition_sz, first);
+      BOOST_POOL_VALIDATE_INTERNALS
+    }
+
+    // Same preconditions as 'segregate'
+    // Post: !empty()
+    void add_ordered_block(void * const block,
+        const size_type nsz, const size_type npartition_sz)
+    { //! add block (ordered into list)
+      //! This (slower) version of add_block segregates the
+      //!  block and merges its free list into our free list
+      //!  in the proper order.
+       BOOST_POOL_VALIDATE_INTERNALS
+      // Find where "block" would go in the free list
+      void * const loc = find_prev(block);
+
+      // Place either at beginning or in middle/end
+      if (loc == 0)
+        add_block(block, nsz, npartition_sz);
+      else
+        nextof(loc) = segregate(block, nsz, npartition_sz, nextof(loc));
+      BOOST_POOL_VALIDATE_INTERNALS
+    }
+
+    // default destructor.
+
+    bool empty() const
+    { //! \returns true only if simple_segregated_storage is empty.
+      return (first == 0);
+    }
+
+    void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
+    { //! Create a chunk.
+      //!  \pre !empty()
+      //! Increment the "first" pointer to point to the next chunk.
+       BOOST_POOL_VALIDATE_INTERNALS
+      void * const ret = first;
+
+      // Increment the "first" pointer to point to the next chunk.
+      first = nextof(first);
+      BOOST_POOL_VALIDATE_INTERNALS
+      return ret;
+    }
+
+    void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk)
+    { //! Free a chunk.
+      //! \pre chunk was previously returned from a malloc() referring to the same free list.
+      //! \post !empty()
+       BOOST_POOL_VALIDATE_INTERNALS
+      nextof(chunk) = first;
+      first = chunk;
+      BOOST_POOL_VALIDATE_INTERNALS
+    }
+
+    void ordered_free(void * const chunk)
+    { //! This (slower) implementation of 'free' places the memory
+      //!  back in the list in its proper order.
+      //! \pre chunk was previously returned from a malloc() referring to the same free list
+      //! \post !empty().
+
+      // Find where "chunk" goes in the free list
+       BOOST_POOL_VALIDATE_INTERNALS
+      void * const loc = find_prev(chunk);
+
+      // Place either at beginning or in middle/end.
+      if (loc == 0)
+        (free)(chunk);
+      else
+      {
+        nextof(chunk) = nextof(loc);
+        nextof(loc) = chunk;
+      }
+      BOOST_POOL_VALIDATE_INTERNALS
+    }
+
+   void * malloc_n(size_type n, size_type partition_size);
+    
+    //! \pre chunks was previously allocated from *this with the same
+    //!   values for n and partition_size.
+    //! \post !empty()
+    //! \note If you're allocating/deallocating n a lot, you should
+    //!  be using an ordered pool.
+    void free_n(void * const chunks, const size_type n,
+        const size_type partition_size)
+    { 
+       BOOST_POOL_VALIDATE_INTERNALS
+      if(n != 0)
+        add_block(chunks, n * partition_size, partition_size);
+       BOOST_POOL_VALIDATE_INTERNALS
+    }
+
+    // pre: chunks was previously allocated from *this with the same
+    //   values for n and partition_size.
+    // post: !empty()
+    void ordered_free_n(void * const chunks, const size_type n,
+        const size_type partition_size)
+    { //! Free n chunks from order list.
+      //! \pre chunks was previously allocated from *this with the same
+      //!   values for n and partition_size.
+
+      //! \pre n should not be zero (n == 0 has no effect).
+       BOOST_POOL_VALIDATE_INTERNALS
+      if(n != 0)
+        add_ordered_block(chunks, n * partition_size, partition_size);
+       BOOST_POOL_VALIDATE_INTERNALS
+    }
+#ifdef BOOST_POOL_VALIDATE
+    void validate()
+    {
+       int index = 0;
+       void* old = 0;
+       void* ptr = first;
+       while(ptr)
+       {
+          void* pt = nextof(ptr); // trigger possible segfault *before* we update variables
+          ++index;
+          old = ptr;
+          ptr = nextof(ptr);
+       }
+    }
+#endif
+};
+
+//! Traverses the free list referred to by "first",
+//!  and returns the iterator previous to where
+//!  "ptr" would go if it was in the free list.
+//!  Returns 0 if "ptr" would go at the beginning
+//!  of the free list (i.e., before "first").
+
+//! \note Note that this function finds the location previous to where ptr would go
+//! if it was in the free list.
+//! It does not find the entry in the free list before ptr
+//! (unless ptr is already in the free list).
+//! Specifically, find_prev(0) will return 0,
+//! not the last entry in the free list.
+//! \returns location previous to where ptr would go if it was in the free list.
+template <typename SizeType>
+void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)
+{ 
+  // Handle border case.
+  if (first == 0 || std::greater<void *>()(first, ptr))
+    return 0;
+
+  void * iter = first;
+  while (true)
+  {
+    // if we're about to hit the end, or if we've found where "ptr" goes.
+    if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr))
+      return iter;
+
+    iter = nextof(iter);
+  }
+}
+
+//! Segregate block into chunks.
+//! \pre npartition_sz >= sizeof(void *)
+//! \pre    npartition_sz = sizeof(void *) * i, for some integer i
+//! \pre    nsz >= npartition_sz
+//! \pre Block is properly aligned for an array of object of
+//!        size npartition_sz and array of void *.
+//! The requirements above guarantee that any pointer to a chunk
+//! (which is a pointer to an element in an array of npartition_sz)
+//! may be cast to void **.
+template <typename SizeType>
+void * simple_segregated_storage<SizeType>::segregate(
+    void * const block,
+    const size_type sz,
+    const size_type partition_sz,
+    void * const end)
+{
+  // Get pointer to last valid chunk, preventing overflow on size calculations
+  //  The division followed by the multiplication just makes sure that
+  //    old == block + partition_sz * i, for some integer i, even if the
+  //    block size (sz) is not a multiple of the partition size.
+  char * old = static_cast<char *>(block)
+      + ((sz - partition_sz) / partition_sz) * partition_sz;
+
+  // Set it to point to the end
+  nextof(old) = end;
+
+  // Handle border case where sz == partition_sz (i.e., we're handling an array
+  //  of 1 element)
+  if (old == block)
+    return block;
+
+  // Iterate backwards, building a singly-linked list of pointers
+  for (char * iter = old - partition_sz; iter != block;
+      old = iter, iter -= partition_sz)
+    nextof(iter) = old;
+
+  // Point the first pointer, too
+  nextof(block) = old;
+
+  return block;
+}
+
+//! \pre (n > 0), (start != 0), (nextof(start) != 0)
+//! \post (start != 0)
+//! The function attempts to find n contiguous chunks
+//!  of size partition_size in the free list, starting at start.
+//! If it succeds, it returns the last chunk in that contiguous
+//!  sequence, so that the sequence is known by [start, {retval}]
+//! If it fails, it does do either because it's at the end of the
+//!  free list or hits a non-contiguous chunk.  In either case,
+//!  it will return 0, and set start to the last considered
+//!  chunk.  You are at the end of the free list if
+//!  nextof(start) == 0.  Otherwise, start points to the last
+//!  chunk in the contiguous sequence, and nextof(start) points
+//!  to the first chunk in the next contiguous sequence (assuming
+//!  an ordered free list).
+template <typename SizeType>
+void * simple_segregated_storage<SizeType>::try_malloc_n(
+    void * & start, size_type n, const size_type partition_size)
+{
+  void * iter = nextof(start);
+  while (--n != 0)
+  {
+    void * next = nextof(iter);
+    if (next != static_cast<char *>(iter) + partition_size)
+    {
+      // next == 0 (end-of-list) or non-contiguous chunk found
+      start = iter;
+      return 0;
+    }
+    iter = next;
+  }
+  return iter;
+}
+
+//! Attempts to find a contiguous sequence of n partition_sz-sized chunks. If found, removes them 
+//! all from the free list and returns a pointer to the first. If not found, returns 0. It is strongly 
+//! recommended (but not required) that the free list be ordered, as this algorithm will fail to find 
+//! a contiguous sequence unless it is contiguous in the free list as well. Order-preserving. 
+//! O(N) with respect to the size of the free list.
+template <typename SizeType>
+void * simple_segregated_storage<SizeType>::malloc_n(const size_type n,
+    const size_type partition_size)
+{
+   BOOST_POOL_VALIDATE_INTERNALS
+  if(n == 0)
+    return 0;
+  void * start = &first;
+  void * iter;
+  do
+  {
+    if (nextof(start) == 0)
+      return 0;
+    iter = try_malloc_n(start, n, partition_size);
+  } while (iter == 0);
+  void * const ret = nextof(start);
+  nextof(start) = nextof(iter);
+  BOOST_POOL_VALIDATE_INTERNALS
+  return ret;
+}
+
+} // namespace boost
+
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+
+#endif