// xheap.h -- exogenous heap manager -- manages a heap in some other medium // // Most commonly used to manage a heap in a stream on disk, // without itself requiring disk I/O. #ifndef __XHEAP_INCLUDED__ #define __XHEAP_INCLUDED__ #ifndef __ARRAY_INCLUDED__ #include "array.h" #endif class XHeap { struct Regn { OFF off; unsigned size; Regn() { off = 0; size = 0; } Regn(OFF off_, unsigned size_) { off = off_; size = size_; } OFF end() { return off + size; } static BOOL hasSize(Regn* pregn, void* pvSize) { return pregn->size >= *(unsigned*)pvSize; } static BOOL isOffLE(Regn* pregn, void* pvRegn) { return ((Regn*)pvRegn)->off <= pregn->off; } }; Array rgregnFree; unsigned iregnRover; OFF offMac; public: XHeap() { iregnRover = 0; offMac = 0; } void reset() { rgregnFree.reset(); iregnRover = 0; offMac = 0; } OFF alloc(unsigned size) { precondition(invariants()); precondition(size > 0); OFF off; #ifdef _MIPS_ size = cbAlign(size); #endif if (rgregnFree.findFirstEltSuchThat_Rover(&Regn::hasSize, &size, &iregnRover)) { Regn* pregn = &rgregnFree[iregnRover]; assert(pregn->size >= size); off = pregn->off; pregn->off += size; if ((pregn->size -= size) == 0) rgregnFree.deleteAt(iregnRover); } else { // No suitable free block found. Return storage at the end of the stream. off = offMac; offMac += size; } postcondition(invariants()); return off; } BOOL free(OFF off, unsigned size) { precondition(invariants()); precondition(off >= 0 && size > 0); #ifdef _MIPS_ size = cbAlign(size); #endif Regn regn(off, size); unsigned iregn = rgregnFree.binarySearch(&Regn::isOffLE, ®n); Regn* pregnPrev = (iregn > 0) ? &rgregnFree[iregn-1] : 0; Regn* pregnNext = (iregn < rgregnFree.size()) ? &rgregnFree[iregn] : 0; BOOL fAdjPrev = (pregnPrev && pregnPrev->end() == regn.off); BOOL fAdjNext = (pregnNext && regn.end() == pregnNext->off); if (fAdjPrev) { if (fAdjNext) { // merge all three blocks into previous block pregnPrev->size += regn.size + pregnNext->size; rgregnFree.deleteAt(iregn); } else { // merge this block into previous pregnPrev->size += regn.size; } } else { if (fAdjNext) { // merge this block into next pregnNext->off = regn.off; pregnNext->size += regn.size; } else { // insert a new block here if (!rgregnFree.insertAt(iregn, regn)) return FALSE; } } // Restart the rover index prior to this free block. if (iregn < iregnRover) iregnRover = (iregn > 0) ? iregn - 1 : 0; postcondition(invariants()); return TRUE; } BOOL save(Buffer* pbuf) { precondition(invariants()); return pbuf->Append((PB)&iregnRover, sizeof(iregnRover)) && pbuf->Append((PB)&offMac, sizeof(offMac)) && rgregnFree.save(pbuf); } BOOL reload(PB* ppb) { iregnRover = *((unsigned*&)*ppb)++; offMac = *((OFF*&)*ppb)++; BOOL OK = rgregnFree.reload(ppb); postcondition(invariants()); return OK; } BOOL invariants() { unsigned size = rgregnFree.size(); #ifdef _MIPS_ // all free regions should be in aligned-sized chunks for (unsigned i = 0; i < size; i++) if (rgregnFree[i].size != (ulong)cbAlign(rgregnFree[i].size)) return FALSE; // regions should be in sorted order for (i = 1; i < size; i++) #else for (unsigned i = 1; i < size; i++) #endif if (rgregnFree[i-1].off >= rgregnFree[i].off || rgregnFree[i-1].end() >= rgregnFree[i].off) return FALSE; // the last region should preceed offMac if (size > 0 && rgregnFree[size-1].end() > offMac) return FALSE; return TRUE; } #ifdef _DEBUG friend class EnumXHeap; #endif }; #ifdef _DEBUG class EnumXHeap : public Enum { // Enumerates the used regions of an XHeap private: unsigned current, size, rgnSize; OFF rgnOff, nextOff; XHeap *xheap; public: EnumXHeap( XHeap *xheap_ ) { current = (unsigned)-1; rgnOff = 0; nextOff = 0; rgnSize = 0; xheap = xheap_; size = xheap->rgregnFree.size(); } void release() { delete this; } void reset() { current = (unsigned)-1; rgnOff = 0; nextOff = 0; } BOOL next() { ++current; if(current>size) return FALSE; if(current == 0 && size>0 && xheap->rgregnFree[0].off == 0) // First block is free { nextOff = xheap->rgregnFree[0].size; current++; } rgnOff = nextOff; // Advance our pointer if(currentrgregnFree[current].off + xheap->rgregnFree[current].size; rgnSize = xheap->rgregnFree[current].off - rgnOff; assert(rgnOff + rgnSize == (unsigned)xheap->rgregnFree[current].off ); } else // last blob of data (can be empty) rgnSize = xheap->offMac - rgnOff; assert( !current || (current && rgnSize >= 0) ); return (rgnSize > 0 ); // Returns false when the region is empty } void get( OUT OFF *poff, OUT unsigned *psize ) { if(poff) *poff = rgnOff; if(psize) *psize = rgnSize; } }; #endif #endif // !__XHEAP_INCLUDED__