source: proiecte/swift/trunk/lib/hoard-371/src/heaplayers/firstfitheap.h @ 176

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

#ifndef _FIRSTFITHEAP_H_
#define _FIRSTFITHEAP_H_

template <class Super>
class FirstFitHeap : public Super {
public:
  
  FirstFitHeap (void)
    : myFreeList (NULL)
#ifndef NDEBUG
    ,nObjects (0)
#endif
    {
      assert (classInvariant());
    }

  ~FirstFitHeap (void)
    {
#if 1
      // Delete everything on the free list.
      void * ptr = myFreeList;
      while (ptr != NULL) {
        // assert (nObjects > 0);
        assert (ptr != NULL);
        void * oldptr = ptr;
        ptr = (void *) ((freeObject *) ptr)->next;
        Super::free (oldptr);
#ifndef NDEBUG
        --nObjects;
#endif
      }
#endif
    }

  inline void * malloc (size_t sz) {
    // Check the free list first.
    assert (classInvariant());
    void * ptr = myFreeList;
    if (ptr == NULL) {
      assert (nObjects == 0);
      ptr = Super::malloc (sz);
    } else {
      assert (nObjects > 0);
      freeObject * p = myFreeList;
      freeObject * prev = NULL;
      while ((p != NULL) && (getSize((void *) p) < sz)) {
        prev = p;
        p = p->next;
      }
      if (p == NULL) {
        ptr = Super::malloc (sz);
      } else {
        assert (getSize((void *) p) >= sz);
        if (prev == NULL) {
          myFreeList = p->next;
        } else {
          assert (prev->next == p);
          prev->next = p->next;
        }
#ifndef NDEBUG
        nObjects--;
#endif
        ptr = p;
      }
    }
    assert (classInvariant());
    return ptr;
  }
  
  inline void free (void * ptr) {
    // Add this object to the free list.
    assert (ptr != NULL);
    assert (classInvariant());
#ifndef NDEBUG
    nObjects++;
#endif
    freeObject * p = myFreeList;
    freeObject * prev = NULL;
    // Insert the object "in order".
#if 1
    while ((p != NULL) & (p <= ptr)) {
      prev = p;
      p = p->next;
    }
#endif
    if (prev == NULL) {
      ((freeObject *) ptr)->next = myFreeList;
      myFreeList = (freeObject *) ptr;
    } else {
      ((freeObject *) ptr)->next = prev->next;
      prev->next = (freeObject *) ptr;
    }
    assert (classInvariant());
  }

private:

  int classInvariant (void) {
    return (((myFreeList == NULL) && (nObjects == 0))
            || ((myFreeList != NULL) && (nObjects > 0)));
  }

  class freeObject {
  public:
    freeObject * next;
  };

  freeObject * myFreeList;
#ifndef NDEBUG
  int nObjects;
#endif

};

#endif