FCL/sf/os/ossrv: comparison ossrv_pub/boost_apis/boost/pool/simple_segregated

equal deleted inserted replaced

--1:000000000000
+:e4d67989cc36
+// 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
+// std::greater
+#include <functional>
+#include <boost/pool/poolfwd.hpp>
+namespace boost {
+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 &);
+// pre: (n > 0), (start != 0), (nextof(start) != 0)
+// post: (start != 0)
+static void * try_malloc_n(void * & start, size_type n,
+size_type partition_size);
+protected:
+void * first;
+// 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")
+void * find_prev(void * ptr);
+// for the sake of code readability :)
+static void * & nextof(void * const ptr)
+{ return *(static_cast<void **>(ptr)); }
+public:
+// Post: empty()
+simple_segregated_storage()
+:first(0) { }
+// pre: npartition_sz >= sizeof(void *)
+//      npartition_sz = sizeof(void *) * i, for some integer i
+//      nsz >= npartition_sz
+//      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 **.
+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)
+{
+// Segregate this block and merge its free list into the
+//  free list referred to by "first"
+first = segregate(block, nsz, npartition_sz, first);
+}
+// Same preconditions as 'segregate'
+// Post: !empty()
+void add_ordered_block(void * const block,
+const size_type nsz, const size_type npartition_sz)
+{
+// This (slower) version of add_block segregates the
+//  block and merges its free list into our free list
+//  in the proper order
+// 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));
+}
+// default destructor
+bool empty() const { return (first == 0); }
+// pre: !empty()
+void * malloc()
+{
+void * const ret = first;
+// Increment the "first" pointer to point to the next chunk
+first = nextof(first);
+return ret;
+}
+// pre: chunk was previously returned from a malloc() referring to the
+//  same free list
+// post: !empty()
+void free(void * const chunk)
+{
+nextof(chunk) = first;
+first = chunk;
+}
+// pre: chunk was previously returned from a malloc() referring to the
+//  same free list
+// post: !empty()
+void ordered_free(void * const chunk)
+{
+// This (slower) implementation of 'free' places the memory
+//  back in the list in its proper order.
+// Find where "chunk" goes in the free list
+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;
+}
+}
+// Note: if you're allocating/deallocating n a lot, you should
+//  be using an ordered pool.
+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)
+{
+add_block(chunks, n * partition_size, partition_size);
+}
+// 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)
+{
+add_ordered_block(chunks, n * partition_size, partition_size);
+}
+};
+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);
+}
+}
+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;
+}
+// The following 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;
+}
+template <typename SizeType>
+void * simple_segregated_storage<SizeType>::malloc_n(const size_type n,
+const size_type partition_size)
+{
+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);
+return ret;
+}
+} // namespace boost
+#endif