text: ///-*-C++-*-//////////////////////////////////////////////////////////////////
  //
  // Hoard: A Fast, Scalable, and Memory-Efficient Allocator
  //        for Shared-Memory Multiprocessors
  // Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
  //
  // Copyright (c) 1998-2000, The University of Texas at Austin.
  //
  // This library is free software; you can redistribute it and/or modify
  // it under the terms of the GNU Library General Public License as
  // published by the Free Software Foundation, http://www.fsf.org.
  //
  // This library is distributed in the hope that it will be useful, but
  // WITHOUT ANY WARRANTY; without even the implied warranty of
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  // Library General Public License for more details.
  //
  //////////////////////////////////////////////////////////////////////////////
  
  /*
    superblock.h
    ------------------------------------------------------------------------
    The superblock class controls a number of blocks (which are
    allocatable units of memory).
    ------------------------------------------------------------------------
    Emery Berger                    | <http://www.cs.utexas.edu/users/emery>
    Department of Computer Sciences |             <http://www.cs.utexas.edu>
    University of Texas at Austin   |                <http://www.utexas.edu>
    ========================================================================
  */
  
  #ifndef _SUPERBLOCK_H_
  #define _SUPERBLOCK_H_
  
  #include "config.h"
  #include "arch-specific.h"
  #include "block.h"
  
  
  namespace BPrivate {
  
  class hoardHeap;				// forward declaration
  class processHeap;				// forward declaration
  
  class superblock {
  	public:
  		// Construct a superblock for a given size class and set the heap
  		// owner.
  		superblock(int numblocks, int sizeclass, hoardHeap *owner);
  		~superblock(void) {}
  
  		// Make (allocate or re-use) a superblock for a given size class.
  		static superblock *makeSuperblock(int sizeclass, processHeap *pHeap);
  
  		// Find out who allocated this superblock.
  		inline hoardHeap *getOwner(void);
  
  		// Set the superblock's owner.
  		inline void setOwner(hoardHeap *o);
  
  		// Get a block from the superblock.
  		inline block *getBlock(void);
  
  		// Put a block back in the superblock.
  		inline void putBlock(block *b);
  
  		// How many blocks are available?
  		inline int getNumAvailable(void);
  
  		// How many blocks are there, in total?
  		inline int getNumBlocks(void);
  
  		// What size class are blocks in this superblock?
  		inline int getBlockSizeClass(void);
  
  		// Insert this superblock before the next one.
  		inline void insertBefore(superblock *nextSb);
  
  		// Return the next pointer (to the next superblock in the list).
  		inline superblock *const getNext(void);
  
  		// Return the prev pointer (to the previous superblock in the list).
  		inline superblock *const getPrev(void);
  
  		// Compute the 'fullness' of this superblock.
  		inline void computeFullness(void);
  
  		// Return the 'fullness' of this superblock.
  		inline int getFullness(void);
  
  #if HEAP_FRAG_STATS
  		// Return the amount of waste in every allocated block.
  		int getMaxInternalFragmentation(void);
  #endif
  
  		// Remove this superblock from its linked list.
  		inline void remove(void);
  
  		// Is this superblock valid? (i.e.,
  		// does it have the right magic number?)
  		inline int isValid(void);
  
  		void
  		upLock(void)
  		{
  			hoardLock(_upLock);
  		}
  
  		void
  		upUnlock(void)
  		{
  			hoardUnlock(_upLock);
  		}
  
  	private:
  		// Disable copying and assignment.
  
  		superblock(const superblock &);
  		const superblock & operator=(const superblock &);
  
  		// Used for sanity checking.
  		enum { SUPERBLOCK_MAGIC = 0xCAFEBABE };
  
  #if HEAP_DEBUG
  		unsigned long _magic;
  #endif
  
  		const int _sizeClass;		// The size class of blocks in the superblock.
  		const int _numBlocks;		// The number of blocks in the superblock.
  		int _numAvailable;			// The number of blocks available.
  		int _fullness;				// How full is this superblock?
  		// (which SUPERBLOCK_FULLNESS group is it in)
  		block *_freeList;			// A pointer to the first free block.
  		hoardHeap *_owner;			// The heap who owns this superblock.
  		superblock *_next;			// The next superblock in the list.
  		superblock *_prev;			// The previous superblock in the list.
  
  		hoardLockType _upLock;		// Lock this when moving a superblock to the global (process) heap.
  
  		// We insert a cache pad here to prevent false sharing with the
  		// first block (which immediately follows the superblock).
  		double _pad[CACHE_LINE / sizeof(double)];
  };
  
  
  hoardHeap *
  superblock::getOwner(void)
  {
  	assert(isValid());
  	hoardHeap *o = _owner;
  	return o;
  }
  
  
  void
  superblock::setOwner(hoardHeap *o)
  {
  	assert(isValid());
  	_owner = o;
  }
  
  
  block *
  superblock::getBlock(void)
  {
  	assert(isValid());
  	// Pop off a block from this superblock's freelist,
  	// if there is one available.
  	if (_freeList == NULL) {
  		// The freelist is empty.
  		assert(getNumAvailable() == 0);
  		return NULL;
  	}
  
  	assert(getNumAvailable() > 0);
  	block *b = _freeList;
  	_freeList = _freeList->getNext();
  	_numAvailable--;
  
  	b->setNext(NULL);
  
  	computeFullness();
  	return b;
  }
  
  
  void
  superblock::putBlock(block *b)
  {
  	assert(isValid());
  	// Push a block onto the superblock's freelist.
  	assert(b->isValid());
  	assert(b->getSuperblock() == this);
  	assert(getNumAvailable() < getNumBlocks());
  	b->setNext(_freeList);
  	_freeList = b;
  	_numAvailable++;
  	computeFullness();
  }
  
  
  int
  superblock::getNumAvailable(void)
  {
  	assert(isValid());
  	return _numAvailable;
  }
  
  
  int
  superblock::getNumBlocks(void)
  {
  	assert(isValid());
  	return _numBlocks;
  }
  
  
  int
  superblock::getBlockSizeClass(void)
  {
  	assert(isValid());
  	return _sizeClass;
  }
  
  
  superblock * const
  superblock::getNext(void)
  {
  	assert(isValid());
  	return _next;
  }
  
  superblock * const
  superblock::getPrev(void)
  {
  	assert(isValid());
  	return _prev;
  }
  
  
  void
  superblock::insertBefore(superblock * nextSb)
  {
  	assert(isValid());
  	// Insert this superblock before the next one (nextSb).
  	assert(nextSb != this);
  	_next = nextSb;
  	if (nextSb) {
  		_prev = nextSb->_prev;
  		nextSb->_prev = this;
  	}
  }
  
  
  void
  superblock::remove(void)
  {
  	// Remove this superblock from a doubly-linked list.
  	if (_next)
  		_next->_prev = _prev;
  	if (_prev)
  		_prev->_next = _next;
  
  	_prev = NULL;
  	_next = NULL;
  }
  
  
  int
  superblock::isValid(void)
  {
  	assert(_numBlocks > 0);
  	assert(_numAvailable <= _numBlocks);
  	assert(_sizeClass >= 0);
  	return 1;
  }
  
  
  void
  superblock::computeFullness(void)
  {
  	assert(isValid());
  	_fullness = (((SUPERBLOCK_FULLNESS_GROUP - 1)
  		* (getNumBlocks() - getNumAvailable())) / getNumBlocks());
  }
  
  
  int
  superblock::getFullness(void)
  {
  	assert(isValid());
  	return _fullness;
  }
  
  }	// namespace BPrivate
  
  #endif // _SUPERBLOCK_H_
  