[176] | 1 | /* -*- C++ -*- */ |
---|
| 2 | |
---|
| 3 | #ifndef _FIRSTFITHEAP_H_ |
---|
| 4 | #define _FIRSTFITHEAP_H_ |
---|
| 5 | |
---|
| 6 | template <class Super> |
---|
| 7 | class FirstFitHeap : public Super { |
---|
| 8 | public: |
---|
| 9 | |
---|
| 10 | FirstFitHeap (void) |
---|
| 11 | : myFreeList (NULL) |
---|
| 12 | #ifndef NDEBUG |
---|
| 13 | ,nObjects (0) |
---|
| 14 | #endif |
---|
| 15 | { |
---|
| 16 | assert (classInvariant()); |
---|
| 17 | } |
---|
| 18 | |
---|
| 19 | ~FirstFitHeap (void) |
---|
| 20 | { |
---|
| 21 | #if 1 |
---|
| 22 | // Delete everything on the free list. |
---|
| 23 | void * ptr = myFreeList; |
---|
| 24 | while (ptr != NULL) { |
---|
| 25 | // assert (nObjects > 0); |
---|
| 26 | assert (ptr != NULL); |
---|
| 27 | void * oldptr = ptr; |
---|
| 28 | ptr = (void *) ((freeObject *) ptr)->next; |
---|
| 29 | Super::free (oldptr); |
---|
| 30 | #ifndef NDEBUG |
---|
| 31 | --nObjects; |
---|
| 32 | #endif |
---|
| 33 | } |
---|
| 34 | #endif |
---|
| 35 | } |
---|
| 36 | |
---|
| 37 | inline void * malloc (size_t sz) { |
---|
| 38 | // Check the free list first. |
---|
| 39 | assert (classInvariant()); |
---|
| 40 | void * ptr = myFreeList; |
---|
| 41 | if (ptr == NULL) { |
---|
| 42 | assert (nObjects == 0); |
---|
| 43 | ptr = Super::malloc (sz); |
---|
| 44 | } else { |
---|
| 45 | assert (nObjects > 0); |
---|
| 46 | freeObject * p = myFreeList; |
---|
| 47 | freeObject * prev = NULL; |
---|
| 48 | while ((p != NULL) && (getSize((void *) p) < sz)) { |
---|
| 49 | prev = p; |
---|
| 50 | p = p->next; |
---|
| 51 | } |
---|
| 52 | if (p == NULL) { |
---|
| 53 | ptr = Super::malloc (sz); |
---|
| 54 | } else { |
---|
| 55 | assert (getSize((void *) p) >= sz); |
---|
| 56 | if (prev == NULL) { |
---|
| 57 | myFreeList = p->next; |
---|
| 58 | } else { |
---|
| 59 | assert (prev->next == p); |
---|
| 60 | prev->next = p->next; |
---|
| 61 | } |
---|
| 62 | #ifndef NDEBUG |
---|
| 63 | nObjects--; |
---|
| 64 | #endif |
---|
| 65 | ptr = p; |
---|
| 66 | } |
---|
| 67 | } |
---|
| 68 | assert (classInvariant()); |
---|
| 69 | return ptr; |
---|
| 70 | } |
---|
| 71 | |
---|
| 72 | inline void free (void * ptr) { |
---|
| 73 | // Add this object to the free list. |
---|
| 74 | assert (ptr != NULL); |
---|
| 75 | assert (classInvariant()); |
---|
| 76 | #ifndef NDEBUG |
---|
| 77 | nObjects++; |
---|
| 78 | #endif |
---|
| 79 | freeObject * p = myFreeList; |
---|
| 80 | freeObject * prev = NULL; |
---|
| 81 | // Insert the object "in order". |
---|
| 82 | #if 1 |
---|
| 83 | while ((p != NULL) & (p <= ptr)) { |
---|
| 84 | prev = p; |
---|
| 85 | p = p->next; |
---|
| 86 | } |
---|
| 87 | #endif |
---|
| 88 | if (prev == NULL) { |
---|
| 89 | ((freeObject *) ptr)->next = myFreeList; |
---|
| 90 | myFreeList = (freeObject *) ptr; |
---|
| 91 | } else { |
---|
| 92 | ((freeObject *) ptr)->next = prev->next; |
---|
| 93 | prev->next = (freeObject *) ptr; |
---|
| 94 | } |
---|
| 95 | assert (classInvariant()); |
---|
| 96 | } |
---|
| 97 | |
---|
| 98 | private: |
---|
| 99 | |
---|
| 100 | int classInvariant (void) { |
---|
| 101 | return (((myFreeList == NULL) && (nObjects == 0)) |
---|
| 102 | || ((myFreeList != NULL) && (nObjects > 0))); |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | class freeObject { |
---|
| 106 | public: |
---|
| 107 | freeObject * next; |
---|
| 108 | }; |
---|
| 109 | |
---|
| 110 | freeObject * myFreeList; |
---|
| 111 | #ifndef NDEBUG |
---|
| 112 | int nObjects; |
---|
| 113 | #endif |
---|
| 114 | |
---|
| 115 | }; |
---|
| 116 | |
---|
| 117 | #endif |
---|