source: NonGTP/Boost/boost/pool/simple_segregated_storage.hpp @ 857

Revision 857, 8.0 KB checked in by igarcia, 19 years ago (diff)
Line 
1// Copyright (C) 2000, 2001 Stephen Cleary
2//
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6//
7// See http://www.boost.org for updates, documentation, and revision history.
8
9#ifndef BOOST_SIMPLE_SEGREGATED_STORAGE_HPP
10#define BOOST_SIMPLE_SEGREGATED_STORAGE_HPP
11
12// std::greater
13#include <functional>
14
15#include <boost/pool/poolfwd.hpp>
16
17namespace boost {
18
19template <typename SizeType>
20class simple_segregated_storage
21{
22  public:
23    typedef SizeType size_type;
24
25  private:
26    simple_segregated_storage(const simple_segregated_storage &);
27    void operator=(const simple_segregated_storage &);
28
29    // pre: (n > 0), (start != 0), (nextof(start) != 0)
30    // post: (start != 0)
31    static void * try_malloc_n(void * & start, size_type n,
32        size_type partition_size);
33
34  protected:
35    void * first;
36
37    // Traverses the free list referred to by "first",
38    //  and returns the iterator previous to where
39    //  "ptr" would go if it was in the free list.
40    // Returns 0 if "ptr" would go at the beginning
41    //  of the free list (i.e., before "first")
42    void * find_prev(void * ptr);
43
44    // for the sake of code readability :)
45    static void * & nextof(void * const ptr)
46    { return *(static_cast<void **>(ptr)); }
47
48  public:
49    // Post: empty()
50    simple_segregated_storage()
51    :first(0) { }
52
53    // pre: npartition_sz >= sizeof(void *)
54    //      npartition_sz = sizeof(void *) * i, for some integer i
55    //      nsz >= npartition_sz
56    //      block is properly aligned for an array of object of
57    //        size npartition_sz and array of void *
58    // The requirements above guarantee that any pointer to a chunk
59    //  (which is a pointer to an element in an array of npartition_sz)
60    //  may be cast to void **.
61    static void * segregate(void * block,
62        size_type nsz, size_type npartition_sz,
63        void * end = 0);
64
65    // Same preconditions as 'segregate'
66    // Post: !empty()
67    void add_block(void * const block,
68        const size_type nsz, const size_type npartition_sz)
69    {
70      // Segregate this block and merge its free list into the
71      //  free list referred to by "first"
72      first = segregate(block, nsz, npartition_sz, first);
73    }
74
75    // Same preconditions as 'segregate'
76    // Post: !empty()
77    void add_ordered_block(void * const block,
78        const size_type nsz, const size_type npartition_sz)
79    {
80      // This (slower) version of add_block segregates the
81      //  block and merges its free list into our free list
82      //  in the proper order
83
84      // Find where "block" would go in the free list
85      void * const loc = find_prev(block);
86
87      // Place either at beginning or in middle/end
88      if (loc == 0)
89        add_block(block, nsz, npartition_sz);
90      else
91        nextof(loc) = segregate(block, nsz, npartition_sz, nextof(loc));
92    }
93
94    // default destructor
95
96    bool empty() const { return (first == 0); }
97
98    // pre: !empty()
99    void * malloc()
100    {
101      void * const ret = first;
102
103      // Increment the "first" pointer to point to the next chunk
104      first = nextof(first);
105      return ret;
106    }
107
108    // pre: chunk was previously returned from a malloc() referring to the
109    //  same free list
110    // post: !empty()
111    void free(void * const chunk)
112    {
113      nextof(chunk) = first;
114      first = chunk;
115    }
116
117    // pre: chunk was previously returned from a malloc() referring to the
118    //  same free list
119    // post: !empty()
120    void ordered_free(void * const chunk)
121    {
122      // This (slower) implementation of 'free' places the memory
123      //  back in the list in its proper order.
124
125      // Find where "chunk" goes in the free list
126      void * const loc = find_prev(chunk);
127
128      // Place either at beginning or in middle/end
129      if (loc == 0)
130        free(chunk);
131      else
132      {
133        nextof(chunk) = nextof(loc);
134        nextof(loc) = chunk;
135      }
136    }
137
138    // Note: if you're allocating/deallocating n a lot, you should
139    //  be using an ordered pool.
140    void * malloc_n(size_type n, size_type partition_size);
141
142    // pre: chunks was previously allocated from *this with the same
143    //   values for n and partition_size
144    // post: !empty()
145    // Note: if you're allocating/deallocating n a lot, you should
146    //  be using an ordered pool.
147    void free_n(void * const chunks, const size_type n,
148        const size_type partition_size)
149    {
150      add_block(chunks, n * partition_size, partition_size);
151    }
152
153    // pre: chunks was previously allocated from *this with the same
154    //   values for n and partition_size
155    // post: !empty()
156    void ordered_free_n(void * const chunks, const size_type n,
157        const size_type partition_size)
158    {
159      add_ordered_block(chunks, n * partition_size, partition_size);
160    }
161};
162
163template <typename SizeType>
164void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)
165{
166  // Handle border case
167  if (first == 0 || std::greater<void *>()(first, ptr))
168    return 0;
169
170  void * iter = first;
171  while (true)
172  {
173    // if we're about to hit the end or
174    //  if we've found where "ptr" goes
175    if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr))
176      return iter;
177
178    iter = nextof(iter);
179  }
180}
181
182template <typename SizeType>
183void * simple_segregated_storage<SizeType>::segregate(
184    void * const block,
185    const size_type sz,
186    const size_type partition_sz,
187    void * const end)
188{
189  // Get pointer to last valid chunk, preventing overflow on size calculations
190  //  The division followed by the multiplication just makes sure that
191  //    old == block + partition_sz * i, for some integer i, even if the
192  //    block size (sz) is not a multiple of the partition size.
193  char * old = static_cast<char *>(block)
194      + ((sz - partition_sz) / partition_sz) * partition_sz;
195
196  // Set it to point to the end
197  nextof(old) = end;
198
199  // Handle border case where sz == partition_sz (i.e., we're handling an array
200  //  of 1 element)
201  if (old == block)
202    return block;
203
204  // Iterate backwards, building a singly-linked list of pointers
205  for (char * iter = old - partition_sz; iter != block;
206      old = iter, iter -= partition_sz)
207    nextof(iter) = old;
208
209  // Point the first pointer, too
210  nextof(block) = old;
211
212  return block;
213}
214
215// The following function attempts to find n contiguous chunks
216//  of size partition_size in the free list, starting at start.
217// If it succeds, it returns the last chunk in that contiguous
218//  sequence, so that the sequence is known by [start, {retval}]
219// If it fails, it does do either because it's at the end of the
220//  free list or hits a non-contiguous chunk.  In either case,
221//  it will return 0, and set start to the last considered
222//  chunk.  You are at the end of the free list if
223//  nextof(start) == 0.  Otherwise, start points to the last
224//  chunk in the contiguous sequence, and nextof(start) points
225//  to the first chunk in the next contiguous sequence (assuming
226//  an ordered free list)
227template <typename SizeType>
228void * simple_segregated_storage<SizeType>::try_malloc_n(
229    void * & start, size_type n, const size_type partition_size)
230{
231  void * iter = nextof(start);
232  while (--n != 0)
233  {
234    void * next = nextof(iter);
235    if (next != static_cast<char *>(iter) + partition_size)
236    {
237      // next == 0 (end-of-list) or non-contiguous chunk found
238      start = iter;
239      return 0;
240    }
241    iter = next;
242  }
243  return iter;
244}
245
246template <typename SizeType>
247void * simple_segregated_storage<SizeType>::malloc_n(const size_type n,
248    const size_type partition_size)
249{
250  void * start = &first;
251  void * iter;
252  do
253  {
254    if (nextof(start) == 0)
255      return 0;
256    iter = try_malloc_n(start, n, partition_size);
257  } while (iter == 0);
258  void * const ret = nextof(start);
259  nextof(start) = nextof(iter);
260  return ret;
261}
262
263} // namespace boost
264
265#endif
Note: See TracBrowser for help on using the repository browser.