root/trunk/whisperlib/common/base/free_list.h

// Copyright (c) 2009, Whispersoft s.r.l.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
// * Neither the name of Whispersoft s.r.l. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Author: Catalin Popescu

#ifndef __COMMON_BASE_FREE_LIST_H__
#define __COMMON_BASE_FREE_LIST_H__

#define _XOPEN_SOURCE 600
#include <stdlib.h>

#include <vector>
#include <whisperlib/common/base/types.h>
#include <whisperlib/common/sync/mutex.h>
#include <whisperlib/common/base/errno.h>

namespace util {

template <typename T>
class FreeList {
 public:
  explicit FreeList(size_t max_size)
    : max_size_(max_size) {
  }
  virtual ~FreeList() {
    while ( !free_list_.empty() ) {
      T* const p = free_list_.back();
      free_list_.pop_back();
      delete p;
    }
  }
  virtual T* New() {
    if ( !free_list_.empty() ) {
      T* const p = free_list_.back();
      free_list_.pop_back();
      return p;
    } else {
      return new T;
    }
  }
  virtual bool Dispose(T* p) {
    if ( free_list_.size() < max_size_ ) {
      free_list_.push_back(p);
      return false;
    }
    delete p;
    return true;
  }
  size_t max_size() const {
    return max_size_;
  }
 private:
  const size_t max_size_;
  vector<T*> free_list_;
};

template <typename T>
class ThreadSafeFreeList : public FreeList<T> {
 public:
  explicit ThreadSafeFreeList(size_t max_size)
    : FreeList<T>(max_size) {
  }
  virtual T* New() {
    synch::MutexLocker ml(&mutex_);
    return FreeList<T>::New();
  }
  virtual bool Dispose(T* p) {
    synch::MutexLocker ml(&mutex_);
    return FreeList<T>::Dispose(p);
  }
 private:
  synch::Mutex mutex_;
};

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

template <typename T>
class FreeArrayList {
 public:
  FreeArrayList(size_t size, size_t max_size)
    : size_(size),
      max_size_(max_size) {
  }
  virtual ~FreeArrayList() {
    while ( !free_list_.empty() ) {
      T* const p = free_list_.back();
      free_list_.pop_back();
      delete [] p;
    }
  }
  virtual T* New() {
    if ( !free_list_.empty() ) {
      T* const p = free_list_.back();
      free_list_.pop_back();
      return p;
    } else {
      return new T[size_];
    }
  }
  virtual bool Dispose(T* p) {
    if ( free_list_.size() < max_size_ ) {
      free_list_.push_back(p);
      return false;
    }
    delete [] p;
    return true;
  }
  size_t size() const {
    return size_;
  }
 protected:
  const size_t size_;
  const size_t max_size_;
  vector<T*> free_list_;
};

template <typename T>
class ThreadSafeFreeArrayList : public FreeArrayList<T> {
 public:
  ThreadSafeFreeArrayList(size_t size, size_t max_size)
    : FreeArrayList<T>(size, max_size) {
  }
  virtual T* New() {
    synch::MutexLocker ml(&mutex_);
    return FreeArrayList<T>::New();
  }
  virtual bool Dispose(T* p) {
    synch::MutexLocker ml(&mutex_);
    return FreeArrayList<T>::Dispose(p);
  }
 private:
  synch::Mutex mutex_;
};

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


// ATTENTION : here the size is in blocks !!
class MemAlignedFreeArrayList : public FreeArrayList<char> {
 public:
  MemAlignedFreeArrayList(size_t size_in_blocks,
                          size_t alignment,
                          size_t max_size,
                          bool alloc_initially = false)
    : FreeArrayList<char>(size_in_blocks, max_size),
      alignment_(alignment),
      alloc_initially_(false) {
    if ( alloc_initially ) {
      vector<char*> p;
      for ( size_t i = 0; i < max_size; ++i ) {
        p.push_back(NewInternal());
        CHECK(p.back() != NULL);
      }
      for ( size_t i = 0; i < p.size(); ++i ) {
        DisposeInternal(p[i]);
      }
      alloc_initially_ = true;
    }
  }
  virtual ~MemAlignedFreeArrayList() {
    while ( !free_list_.empty() ) {
      char* const p = free_list_.back();
      free_list_.pop_back();
      free(p);
    }
  }
  virtual char* New() {
    return NewInternal();
  }
  virtual bool Dispose(char* p) {
    return DisposeInternal(p);
  }
  size_t alignment() const {
    return alignment_;
  }
 private:
  char* NewInternal() {
    if ( !free_list_.empty() ) {
      char* const p = free_list_.back();
      free_list_.pop_back();
      return p;
    } else if ( alloc_initially_ ) {
      LOG_ERROR << " Freepool exhausted";
      return NULL;
    } else {
      void* ret = NULL;
      const int err = posix_memalign(&ret,
                                     alignment_,
                                     size_ * alignment_);
      if ( err ) {
        LOG_ERROR << " Error in posix_memalign: " << errno
                  << " : " << GetSystemErrorDescription(errno);
        return NULL;
      }
      return reinterpret_cast<char*>(ret);
    }
  }
  bool DisposeInternal(char* p) {
    if ( free_list_.size() < max_size_ ) {
      free_list_.push_back(p);
      return false;
    }
    CHECK(!alloc_initially_);
    free(p);
    return true;
  }
 private:
  const size_t alignment_;
  bool alloc_initially_;
};

class ThreadSafeMemAlignedFreeArrayList : public MemAlignedFreeArrayList {
 public:
  ThreadSafeMemAlignedFreeArrayList(size_t size,
                                    size_t alignment,
                                    size_t max_size)
    : MemAlignedFreeArrayList(size, alignment, max_size) {
  }
  virtual char* New() {
    synch::MutexLocker ml(&mutex_);
    return MemAlignedFreeArrayList::New();
  }
  virtual bool Dispose(char* p) {
    synch::MutexLocker ml(&mutex_);
    return MemAlignedFreeArrayList::Dispose(p);
  }
 private:
  synch::Mutex mutex_;
};
}

#endif  // __COMMON_BASE_FREE_LIST_H__