looseslotheap.h

Go to the documentation of this file.

/* -*- C++ -*- */

#ifndef _LOOSESLOTHEAP_H_
#define _LOOSESLOTHEAP_H_

#include <assert.h>

#include "bigchunk.h"

/*
  LooseSlotHeap: A "Loose" slot heap.

  malloc returns objects of size slotSize, allocated from the super heap
  in chunkSize units.

  free returns objects of size slotSize.

  When the slot heap is at least 1/emptyFraction empty, a
  chunk that is at least that empty is freed to the super heap.
  Note that the chunk's memory MAY NOT SAFELY be recycled in toto --
  it must be parceled out using the chunk interface.

  The intent of this heap is to allow mostly-empty chunks to move up
  to a staging area (the super heap) where they may be reused by other
  "loose" slot heaps.

*/

template <int chunkSize, int slotSize, int emptyFraction, class Super>
class LooseSlotHeap {
public:

        inline LooseSlotHeap (void);
        inline ~LooseSlotHeap (void);

  // Get a slotSize object.
  inline void * malloc (size_t sz);

  // Free a slotSize object.
  static inline void free (void * ptr);

private:

        Super theHeap;

        typedef BigChunk<chunkSize, slotSize, LooseSlotHeap> chunkType;

        inline void localFree (void * ptr);

        void checkClassInvariant (void) {
#ifndef NDEBUG
                assert (inUse >= 0);
                assert (inUse <= space);
                assert (lastIndex >= 0);
                assert (lastIndex <= emptyFraction);
                // Now check to make sure that inUse & space are correct.
                int localInUse = 0;
                int localSpace = 0;
                for (int i = 0; i < emptyFraction + 1; i++) {
                        chunkType * ch = myChunks[i];
                        while (ch != NULL) {
                                assert (ch->getHeap() == this);
                                localInUse += ch->getNumSlotsInUse();
                                localSpace += ch->getNumSlots();
                                ch = ch->getNext();
                        }
                }
                assert (localSpace == space);
                assert (localInUse == inUse);
#endif
        }

  // How full is this block?
        //   0 == empty to no more than 1/emptyFraction full.
        //   emptyFraction == completely full.
  static inline int getFullness (chunkType * ch);
    
        // Move a chunk, if necessary, into the right list
  // based on its emptiness.
        // Returns the index of which list it is put or left in.
        inline int update (chunkType * ch, int prevIndex);

  // The array of chunks, "radix sorted" by emptiness.
  // completely empty chunks are in index 0.
  // completely full chunks are in index emptyFraction.
  chunkType * myChunks[emptyFraction + 1];

  // The last index (from 0) in the above array that has a chunk.
  int lastIndex;

  // How much space is in use in all of the chunks.
  int inUse;

  // How much space there is (free or not) in all of the chunks.
  int space;
};


template <int chunkSize, int slotSize, int emptyFraction, class Super>
LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::LooseSlotHeap (void)
  : space (0),
    inUse (0),
    lastIndex (emptyFraction - 1)
{
        // Initialize the chunk pointers (all initially empty).
        for (int i = 0; i < emptyFraction + 1; i++) {
                myChunks[i] = NULL;
        }
}


template <int chunkSize, int slotSize, int emptyFraction, class Super>
LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::~LooseSlotHeap (void)
{
        // Free every chunk.
        chunkType * ch, * tmp;
        for (int i = 0; i < emptyFraction + 1; i++) {
                ch = myChunks[i];
                while (ch != NULL) {
                        tmp = ch;
                        ch = ch->getNext();
                        theHeap.free (tmp);
                }
        }
}


template <int chunkSize, int slotSize, int emptyFraction, class Super>
int LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::getFullness (chunkType * ch)
{
  int fullness = (emptyFraction * ch->getNumSlotsInUse())/ch->getNumSlots();
        //printf ("numslots avail = %d, num slots total = %d, fullness = %d\n", ch->getNumSlotsFree(), ch->getNumSlots(), fullness);
        return fullness;
}

        
template <int chunkSize, int slotSize, int emptyFraction, class Super>
void * LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::malloc (size_t sz)
{
        checkClassInvariant();
        //printf ("Loose malloc %d (slot size = %d)\n", sz, slotSize);
  assert (sz <= slotSize);
  void * ptr = NULL;
        chunkType * ch = NULL;
  // Always try to allocate from the most-full chunk (resetting
  // lastIndex as we go).
        lastIndex = emptyFraction - 1; // FIX ME!
  while (lastIndex >= 0) {
                ch = myChunks[lastIndex];
    if (ch == NULL) {
      lastIndex--;
    } else {
      // Got one.
      break;
    }
  }
  if (lastIndex < 0) {
                assert (ch == NULL);
    // There were no chunks available.
    assert ((space - inUse) == 0);
    // Make one with memory from the "super" heap.
                printf ("!!!\n");
                ch = (chunkType*) theHeap.malloc (chunkSize);
                ch->setHeap (this);
                assert (ch->getNumSlotsFree() > 0);
                printf ("Super malloc %d\n", chunkSize);
                lastIndex = getFullness(ch);
                register chunkType*& head = myChunks[lastIndex];
                assert (head == NULL);
                ch->setPrev (NULL);
                ch->setNext (NULL);
    head = ch;
    inUse += ch->getNumSlotsInUse();
    space += ch->getNumSlots();
                assert (ch->getNumSlotsFree() <= ch->getNumSlots());
                // FOR NOW!! FIX ME!!!
                assert (ch->getNumSlotsFree() == ch->getNumSlots());
                printf ("Space, in use was %d, %d\n", space, inUse);
                printf ("Space, in use NOW %d, %d\n", space, inUse);
  }
        assert (ch != NULL);
        assert (ch->getNumSlotsFree() > 0);
        int prevFullness = getFullness (ch);
        int prevInUse = ch->getNumSlotsInUse();
        assert (ch->getHeap() == this);
  ptr = ch->getSlot();
  inUse++;
        assert (prevInUse + 1 == ch->getNumSlotsInUse());
        int newFullness = getFullness (ch);
        if (prevFullness != newFullness) {
                int n = update (ch, prevFullness);
                assert (n == newFullness);
        }
  chunkType * bch = (chunkType *) chunkType::getChunk(ptr);
  assert (bch == ch);
  assert (ptr != NULL);
        checkClassInvariant();
  return ptr;
}


template <int chunkSize, int slotSize, int emptyFraction, class Super>
void LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::free (void * ptr) {
  chunkType * ch
    = (chunkType *) chunkType::getChunk (ptr);
        assert (ch != NULL);
        (ch->getHeap())->localFree (ptr);
}


template <int chunkSize, int slotSize, int emptyFraction, class Super>
void LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::localFree (void * ptr) {
        checkClassInvariant();
        printf ("free! (in use = %d, space = %d)\n", inUse, space);
  // Mark the slot in the chunk as free.
  chunkType * ch
    = (chunkType *) chunkType::getChunk (ptr);
        assert (ch != NULL);
        assert (ch->getHeap() == this);
        int prevFullness = getFullness (ch);
        int prevInUse = ch->getNumSlotsInUse();
  ch->putSlot (ptr);
        inUse--;
        assert (prevInUse - 1 == ch->getNumSlotsInUse());
        checkClassInvariant();
        int newIndex = getFullness (ch);
        if (prevFullness != newIndex) {
                int n = update (ch, prevFullness);
                assert (n == newIndex);
        }
  // If we are more than 1/emptyFraction empty,
  // return a mostly-empty chunk to the super heap.
  if ((space - inUse > 2 * chunkSize/slotSize)
                && (emptyFraction * (space - inUse) > space)) {
                printf ("RETURNING A CHUNK!\n");
                // Find an empty chunk.
                int emptyIndex = 0;
                ch = NULL;
                while (emptyIndex < emptyFraction) {
                        ch = myChunks[emptyIndex];
                        if (ch != NULL)
                                break;
                        emptyIndex++;
                }
                assert (ch != NULL);
                checkClassInvariant();
                ch->setHeap (NULL);
    // Remove a chunk and give it to the super heap.
                myChunks[emptyIndex] = myChunks[emptyIndex]->getNext();
                if (myChunks[emptyIndex] != NULL) {
                        myChunks[emptyIndex]->setPrev (NULL);
                }
                ch->setPrev (NULL);
                ch->setNext (NULL);
                // A sanity check on the chunk we're about to return.
                assert (ch->getNumSlotsFree() >= 0);
                assert (ch->getNumSlots() >= ch->getNumSlotsFree());
                printf ("Updating space & in use: was %d, %d (slots in use = %d)\n",
                        space, inUse, ch->getNumSlotsInUse());
                space -= ch->getNumSlots();
                inUse -= ch->getNumSlotsInUse();
                printf ("Updating space & in use: NOW %d, %d\n", space, inUse);
                theHeap.free (ch);
                checkClassInvariant();
  }
        checkClassInvariant();
}


// Move a chunk, if necessary, into the right list
// based on its emptiness.
template <int chunkSize, int slotSize, int emptyFraction, class Super>
int LooseSlotHeap<chunkSize, slotSize, emptyFraction, Super>::update (chunkType * ch, int prevIndex)
{
  // Move this chunk if necessary.
#ifndef NDEBUG
        chunkType * bch = myChunks[prevIndex];
        while (bch != NULL) {
                if (bch == ch)
                        break;
                bch = bch->getNext();
        }
        assert (bch == ch);
#endif
  int newIndex = getFullness(ch);
  // printf ("newIndex = %d\n", newIndex);
        // Reset last index (for simplicity). // FIX ME??
  // Remove the chunk from its current list.
        if (ch == myChunks[prevIndex]) {
                myChunks[prevIndex] = myChunks[prevIndex]->getNext();
        }
  if (ch->getPrev() != NULL) {
                ch->getPrev()->setNext(ch->getNext());
  }
        if (ch->getNext() != NULL) {
          ch->getNext()->setPrev(ch->getPrev());
  }
  // Add it to the newIndex list.
  chunkType*& head = myChunks[newIndex];
  ch->setPrev (NULL);
  ch->setNext (head);
  if (head != NULL) {
    head->setPrev(ch);
  }
        head = ch;
        // Verify that the chunk is in the right list.
#ifndef NDEBUG
        bch = myChunks[newIndex];
        while (bch != NULL) {
                if (bch == ch)
                        break;
                bch = bch->getNext();
        }
        assert (bch == ch);
#endif
        return newIndex;
}



#endif

---