datablock.h

Go to the documentation of this file.

/* 
 * Scythe Statistical Library Copyright (C) 2000-2002 Andrew D. Martin
 * and Kevin M. Quinn; 2002-present Andrew D. Martin, Kevin M. Quinn,
 * and Daniel Pemstein.  All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify under the terms of the GNU General Public License as
 * published by Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.  See the text files
 * COPYING and LICENSE, distributed with this source code, for further
 * information.
 * --------------------------------------------------------------------
 *  scythestat/datablock.h
 */

#ifndef SCYTHE_DATABLOCK_H
#define SCYTHE_DATABLOCK_H

#ifdef SCYTHE_COMPILE_DIRECT
#include "error.h"
#else
#include "scythestat/error.h"
#endif

#ifdef SCYTHE_PTHREAD
#include <pthread.h>
#endif

namespace scythe {
  /* Convenience typedefs */
  namespace { // local to this file
    typedef unsigned int uint;
  }

  template <typename T_type>
  class DataBlock { 
    public:
      /**** CONSTRUCTORS ****/
      
      /*
       * Create an empty data block.
       */
      
      DataBlock ()
        : data_ (0),
          size_ (0),
          refs_ (0)
      {}

      /* 
       * Create a block of a given size.
       */
      explicit
      DataBlock (uint size)
        : data_ (0),
          size_ (0),
          refs_ (0)
      {
        resize(size);
        SCYTHE_DEBUG_MSG("Constructed new " << size << "(" << size_
            << ") DataBlock at address " << data_);
      }

      /*
       * Create an exact copy of another data block.
       */
      DataBlock (const DataBlock<T_type>& b)
        : data_ (b.data_),
          size_ (b.size_),
          refs_ (b.refs_)
      {}

      /**** DESTRUCTOR ****/

      ~DataBlock ()
      {
        SCYTHE_DEBUG_MSG("Destructing block at " << data_);
        deallocate();
      }

      /**** REFERENCE COUNTING ****/

      inline uint addReference ()
      {
        SCYTHE_DEBUG_MSG("Added reference to DataBlock at address "
            << data_);
        return ++refs_;
      }

      inline uint removeReference ()
      {
        SCYTHE_DEBUG_MSG("Removed reference to DataBlock at address "
           << data_);
        return --refs_ ;
      }

      inline uint references ()
      {
        return refs_;
      }

      /**** ACCESSORS ****/

      inline T_type* data()
      {
        return data_;
      }

      inline const T_type* data() const
      {
        return data_;
      }

      inline uint size () const
      {
        return size_;
      }

    protected:
      /**** (DE)ALLOCATION AND RESIZING ****/
      
      /* Allocate data given the current block size. */
      inline void allocate (uint size)
      {
        /* TODO Think about cache boundary allocations for big blocks
         * see blitz++ */

        if (data_ != 0) // Get rid of previous allocation if it exists
          deallocate();

        data_ = new (std::nothrow) T_type[size];
        
        SCYTHE_CHECK_10(data_ == 0, scythe_alloc_error,
            "Failure allocating DataBlock of size " << size);
      }

      /* Deallocate a block's data */
      inline void deallocate ()
      {
        SCYTHE_DEBUG_MSG("  Deallocating DataBlock of size " << size_
            << " at address " << data_);
        delete[] data_;
        data_ = 0;
      }

    public:
      /* TODO At the moment, references call this method directly.  Not
       * sure if this is the best interface choice. */
      /* Resize a block. */
      void resize (uint newsize)
      {
        if (newsize > size_)
          grow(newsize);
        else if (newsize < size_ / 4)
          shrink();
      }

    protected:
      /* Make a block larger. Expects to be called by resize and does
       * not reset the size_ variable. */
      inline void grow (uint newsize)
      {
        size_ = size_ ? size_ : 1; // make sure not zero

        /* TODO Can we speed this up?  In 20 iters we're at
         * 1048576 elems doing the math might be more costly...
         */
        while (size_ < newsize)
          size_ <<= 1;

        allocate(size_);
      }

      /* Make a block smaller. Expects to be called by resize */
      inline void shrink ()
      {
        size_ >>= 1;
        allocate(size_);
      }

    private:
      /**** INSTANCE VARIABLES ****/
      T_type *data_;   // The data array
      uint size_;  // The number of elements in the block
      uint refs_;  // The number of views looking at this block
  }; // end class DataBlock

  template <class T_type>
  class NullDataBlock : public DataBlock<T_type>
  {
    typedef DataBlock<T_type> T_base;
    public:
      
      NullDataBlock ()
        : DataBlock<T_type> ()
      {
        // never want to deallocate (or resize) this one
        T_base::addReference(); 
        SCYTHE_DEBUG_MSG("Constructed NULL datablock");
      }

      ~NullDataBlock ()
      {}

  }; // end class NullDataBlock


  template <class T_type>
  class DataBlockReference {
    public:
      /**** CONSTRUCTORS ****/

      /* Default constructor: points the object at a static null block
       */
      DataBlockReference ()
        : data_ (0),
          block_ (&nullBlock_)
      {
#ifdef SCYTHE_PTHREAD
        pthread_mutex_lock (&ndbMutex_);
#endif
        block_->addReference();
#ifdef SCYTHE_PTHREAD
        pthread_mutex_unlock (&ndbMutex_);
#endif
      }

      /* New block constructor: creates a new underlying block of a
       * given size and points at it. */
      explicit
      DataBlockReference (uint size)
        : data_ (0),
          block_ (0)
      {
        block_ = new (std::nothrow) DataBlock<T_type> (size);
        SCYTHE_CHECK_10 (block_ == 0, scythe_alloc_error,
            "Could not allocate DataBlock object");
        
        data_ = block_->data();
        block_->addReference();
      }

      /* Refrence to an existing block constructor: points to an
       * offset within an existing block. */
      DataBlockReference (const DataBlockReference<T_type>& reference,
          uint offset = 0)
        : data_ (reference.data_ + offset),
          block_ (reference.block_)
      {
#ifdef SCYTHE_PTHREAD
        bool lock = false;
        if (block_ == &nullBlock_) {
          pthread_mutex_lock (&ndbMutex_);
          lock = true;
        }
#endif
        block_->addReference();
#ifdef SCYTHE_PTHREAD
        if (lock)
          pthread_mutex_unlock (&ndbMutex_);
#endif
      }
      
      /**** DESTRUCTOR ****/
      /* Automates removal of underlying block objects when refcount
       * hits nil.
       */
      virtual ~DataBlockReference ()
      {
#ifdef SCYTHE_PTHREAD
        bool lock = false;
        if (block_ == &nullBlock_) {
          pthread_mutex_lock (&ndbMutex_);
          lock = true;
        }
#endif
        withdrawReference();
#ifdef SCYTHE_PTHREAD
        if (lock)
          pthread_mutex_unlock (&ndbMutex_);
#endif
      }

    protected:

      /**** MEMBERS CALLED BY DERIVED CLASS ****/
      void referenceOther (const DataBlockReference<T_type>& ref,
          uint offset = 0)
      {
#ifdef SCYTHE_PTHREAD
        bool lock = false;
        if (block_ == &nullBlock_ || ref.block_ == &nullBlock_) {
          pthread_mutex_lock (&ndbMutex_);
          lock = true;
        }
#endif
        withdrawReference ();
        block_ = ref.block_;
        block_->addReference();
        data_ = ref.data_ + offset;
#ifdef SCYTHE_PTHREAD
        if (lock)
          pthread_mutex_lock (&ndbMutex_);
#endif
      }

      void referenceNew (uint size)
      {
#ifdef SCYTHE_PTHREAD
        bool lock = false;
        if (block_ == &nullBlock_) {
          pthread_mutex_lock (&ndbMutex_);
          lock = true;
        }
#endif
        /* If we are the only referent to this data block, resize it. 
         * Otherwise, shift the reference to point to a newly
         * constructed block.
         */
        if (block_->references() == 1) {
          block_->resize(size);
          data_ = block_->data(); // This is a pretty good indication
          // that the interface and implementation are too tightly
          // coupled for resizing.
        } else {
          withdrawReference();
          block_ = 0;
          block_ = new (std::nothrow) DataBlock<T_type> (size);
          SCYTHE_CHECK_10(block_ == 0, scythe_alloc_error,
              "Could not allocate new data block");
          data_ = block_->data();
          block_->addReference();
        }
#ifdef SCYTHE_PTHREAD
        if (lock)
          pthread_mutex_unlock (&ndbMutex_);
#endif
      }

    private:
      /**** INTERNAL MEMBERS ****/
      void withdrawReference ()
      {
        // All calls to withdrawReference are mutex protected and protecting
        // this too can create a race condition.

        if (block_->removeReference() == 0
            && block_ != &nullBlock_)
          delete block_;
      }

      void referenceNull ()
      {
#ifdef SCYTHE_PTHREAD
        pthread_mutex_lock (&ndbMutex_);
#endif
        withdrawReference();
        block_ = &nullBlock_;
        block_->addReference();
        data_ = 0;

#ifdef SCYTHE_PTHREAD
        pthread_mutex_unlock (&ndbMutex_);
#endif
      }


    /**** INSTANCE VARIABLES ****/
    protected:
      T_type* data_;  // Pointer to the underlying data (offset)
    
    private:
      DataBlock<T_type>* block_;
      static NullDataBlock<T_type> nullBlock_;
#ifdef SCYTHE_PTHREAD
      static pthread_mutex_t ndbMutex_;
#endif

  }; // end class DataBlockReference

  /* Instantiation of the static null memory block */
  template <typename T>
  NullDataBlock<T> DataBlockReference<T>::nullBlock_;

#ifdef SCYTHE_PTHREAD
  // mutex initialization
  template <typename T>
  pthread_mutex_t 
  DataBlockReference<T>::ndbMutex_ = PTHREAD_MUTEX_INITIALIZER;
#endif

} // end namespace scythe

#endif /* SCYTHE_DATABLOCK_H */