pool.h

clucene是c++版的全文检索引擎,完全移植于lucene,采用 stl 编写.

/*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
* 
* Distributable under the terms of either the Apache License (Version 2.0) or 
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#ifndef _lucene_debug_pool_
#define _lucene_debug_pool_
//this code is based on the boost memory pool library

#if defined(_LUCENE_PRAGMA_ONCE)
# pragma once
#endif
#ifdef LUCENE_ENABLE_MEMORY_POOL //no point including if not using mempool
CL_NS_DEF(debug)

void lucene_release_memory_pool();

//predefine some classes
template <typename UserAllocator=default_user_allocator_malloc_free>
class pool;
struct default_user_allocator_malloc_free;

///The LucenePoolBase
template <pool<>* mempool>
#ifdef LUCENE_ENABLE_REFCOUNT
   class LucenePoolBase:public LuceneBase{
#else
   class LucenePoolBase{
#endif
public:
   LucenePoolBase(){
   }
   static void* operator new (size_t size){
      return mempool->ordered_malloc();
   }
   static void operator delete (void *p){
      mempool->ordered_free(p);
   }
};


/////////////////////

//
// gcd is an algorithm that calculates the greatest common divisor of two
//  integers, using Euclid's algorithm.
//
// Pre: A > 0 && B > 0
// Recommended: A > B
template <typename Integer>
Integer gcd(Integer A, Integer B)
{
  do
  {
    const Integer tmp(B);
    B = A % B;
    A = tmp;
  } while (B != 0);

  return A;
}
//
// lcm is an algorithm that calculates the least common multiple of two
//  integers.
//
// Pre: A > 0 && B > 0
// Recommended: A > B
template <typename Integer>
Integer lcm(const Integer & A, const Integer & B)
{
  Integer ret = A;
  ret /= gcd(A, B);
  ret *= B;
  return ret;
}

struct default_user_allocator_malloc_free
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return reinterpret_cast<char *>(std::malloc(bytes)); }
  static void free(char * const block)
  { std::free(block); }
};

// PODptr is a class that pretends to be a "pointer" to different class types
//  that don't really exist.  It provides member functions to access the "data"
//  of the "object" it points to.  Since these "class" types are of variable
//  size, and contains some information at the *end* of its memory (for
//  alignment reasons), PODptr must contain the size of this "class" as well as
//  the pointer to this "object".
// PODptr is a class that pretends to be a "pointer" to different class types
//  that don't really exist.  It provides member functions to access the "data"
//  of the "object" it points to.  Since these "class" types are of variable
//  size, and contains some information at the *end* of its memory (for
//  alignment reasons), PODptr must contain the size of this "class" as well as
//  the pointer to this "object".
template <typename SizeType>
class PODptr
{
  public:
    typedef SizeType size_type;

  private:
    char * ptr;
    size_type sz;
    size_t lcm_size;

    char * ptr_next_size() const
    { return (ptr + sz - sizeof(size_type)); }
    char * ptr_next_ptr() const
    {
      return (ptr_next_size() - lcm_size);
    }

  public:
    PODptr(char * const nptr, const size_type nsize)
    :ptr(nptr), sz(nsize), lcm_size(lcm(sizeof(size_type), sizeof(void *))) { }
    PODptr()
    :ptr(0), sz(0), lcm_size(lcm(sizeof(size_type), sizeof(void *))) { }

    bool valid() const { return (begin() != 0); }
    void invalidate() { begin() = 0; }
    char * & begin() { return ptr; }
    char * begin() const { return ptr; }
    char * end() const { return ptr_next_ptr(); }
    size_type total_size() const { return sz; }
    size_type element_size() const
    {
      return (sz - sizeof(size_type) - lcm_size);
    }

    size_type & next_size() const
    { return *(reinterpret_cast<size_type *>(ptr_next_size())); }
    char * & next_ptr() const
    { return *(reinterpret_cast<char **>(ptr_next_ptr())); }

    PODptr next() const
    { return PODptr<size_type>(next_ptr(), next_size()); }
    void next(const PODptr & arg) const
    {
      next_ptr() = arg.begin();
      next_size() = arg.total_size();
    }
};

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 UserAllocator>
class pool: protected simple_segregated_storage<typename UserAllocator::size_type>
{
  public:
    typedef UserAllocator user_allocator;
    typedef typename UserAllocator::size_type size_type;
    typedef typename UserAllocator::difference_type difference_type;
  private:
    // Returns 0 if out-of-memory
    // Called if malloc/ordered_malloc needs to resize the free list
    void * malloc_need_resize();
    void * ordered_malloc_need_resize();

    const size_t min_alloc_size;
    const size_t min_alloc_size2;
  protected:
    PODptr<size_type> list;

    simple_segregated_storage<size_type> & store() { return *this; }
    const simple_segregated_storage<size_type> & store() const { return *this; }
    const size_type requested_size;
    size_type next_size;


    // is_from() tests a chunk to determine if it belongs in a block
    static bool is_from(void * const chunk, char * const i,
        const size_type sizeof_i)
    {
      std::less_equal<void *> lt_eq;
      std::less<void *> lt;
      return (lt_eq(i, chunk) && lt(chunk, i + sizeof_i));
    }

    size_type alloc_size() const
    {
      size_type min_size = min_alloc_size;
      return lcm<size_type>(requested_size, min_size);
    }

    // for the sake of code readability :)
    static void * & nextof(void * const ptr)
    { return *(static_cast<void **>(ptr)); }

  public:
    // The second parameter here is an extension!
    // pre: npartition_size != 0 && nnext_size != 0
    explicit pool(const size_type nrequested_size,
        const size_type nnext_size = 32)
    :requested_size(nrequested_size), next_size(nnext_size),
    min_alloc_size(lcm(sizeof(void *), sizeof(size_type))),
    min_alloc_size2(lcm(sizeof(size_type), sizeof(void *)))
    { }

    size_type total_size() const { return list.total_size(); }
    ~pool() { purge_memory(); }

    // Releases memory blocks that don't have chunks allocated
    // pre: lists are ordered
    //  Returns true if memory was actually deallocated
    bool release_memory();

    // Releases *all* memory blocks, even if chunks are still allocated
    //  Returns true if memory was actually deallocated
    bool purge_memory();

    // These functions are extensions!
    size_type get_next_size() const { return next_size; }
    void set_next_size(const size_type nnext_size) { next_size = nnext_size; }

    // Both malloc and ordered_malloc do a quick inlined check first for any
    //  free chunks.  Only if we need to get another memory block do we call
    //  the non-inlined *_need_resize() functions.
    // Returns 0 if out-of-memory
    void * malloc()
    {
      // Look for a non-empty storage
      if (!store().empty())
        return store().malloc();
      return malloc_need_resize();
    }

    void * ordered_malloc()
    {
      // Look for a non-empty storage
      if (!store().empty())
        return store().malloc();
      return ordered_malloc_need_resize();
    }

    // Returns 0 if out-of-memory
    // Allocate a contiguous section of n chunks
    void * ordered_malloc(size_type n);