X-Git-Url: https://git.saurik.com/apple/libutil.git/blobdiff_plain/3f2457aa214f9ca3e3a7f86c702bfbf3df4d485e..1bd2040a698ab5d6035aaf13c3544e5ab3c8af2c:/ExtentManager.cpp

diff --git a/ExtentManager.cpp b/ExtentManager.cpp
new file mode 100644
index 0000000..74d54c6
--- /dev/null
+++ b/ExtentManager.cpp
@@ -0,0 +1,171 @@
+/*
+ * Copyright (c) 2008 Apple Inc. All rights reserved.
+ *
+ * @APPLE_LICENSE_HEADER_START@
+ * 
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
+ * file.
+ * 
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ * 
+ * @APPLE_LICENSE_HEADER_END@
+ */
+//
+//	ExtentManager.cpp
+//
+
+#include "ExtentManager.h"
+
+void
+ExtentManager::Init(uint32_t theBlockSize, uint32_t theNativeBlockSize, off_t theTotalBytes)
+{
+	blockSize = theBlockSize;
+	nativeBlockSize = theNativeBlockSize;
+	totalBytes = theTotalBytes;
+	totalBlocks = howmany(totalBytes, blockSize);
+
+	// add sentry empty extents at both sides so empty partition doesn't need to be handled specially
+	AddBlockRangeExtent(0, 0);
+	AddBlockRangeExtent(totalBlocks, 0);
+}
+
+void
+ExtentManager::MergeExtent(const ExtentInfo &a, const ExtentInfo &b, ExtentInfo *c)
+{
+	// merge ext into *curIt
+	c->blockAddr = min(a.blockAddr, b.blockAddr);
+	c->numBlocks = max(a.blockAddr + a.numBlocks, b.blockAddr + b.numBlocks) - c->blockAddr;
+}
+
+void
+ExtentManager::AddBlockRangeExtent(off_t blockAddr, off_t numBlocks)
+{
+	struct ExtentInfo ext, newExt;
+	ListExtIt curIt, newIt;
+	bool merged = false;
+
+	// make the range a valid range
+	if ((blockAddr > totalBlocks) || (blockAddr + numBlocks < 0)) { // totally out of range, do nothing
+		return;
+	}
+	if (blockAddr < 0) {
+		numBlocks = blockAddr + numBlocks;
+		blockAddr = 0;
+	}
+	if (blockAddr + numBlocks > totalBlocks) {
+		numBlocks = totalBlocks - blockAddr;
+	}
+
+	ext.blockAddr = blockAddr;
+	ext.numBlocks = numBlocks;
+
+	for (curIt = extentList.begin(); curIt != extentList.end(); curIt++) {
+		if (BeforeExtent(ext, *curIt))
+			break;
+		if (!BeforeExtent(*curIt, ext)) { // overlapped extents
+			MergeExtent(ext, *curIt, &newExt);
+			*curIt = newExt;
+			merged = true;
+			break;
+		}
+	}
+
+	// insert ext before curIt
+	if (!merged) {
+		curIt = extentList.insert(curIt, ext); // throws bad_alloc when out of memory
+	}
+
+	// merge the extents
+	newIt = curIt;
+	curIt = extentList.begin();
+	while (curIt != extentList.end()) {
+		if (curIt == newIt || BeforeExtent(*curIt, *newIt)) { // curIt is before newIt
+			curIt++;
+			continue;
+		}
+		if (BeforeExtent(*newIt, *curIt)) { // curIt is after newIt now, we are done
+			break;
+		}
+		// merge the two extents
+		MergeExtent(*curIt, *newIt, &newExt);
+		*newIt = newExt;
+		curIt = extentList.erase(curIt);
+	}
+	// printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks);	 DebugPrint();
+} // ExtentManager::AddBlockRangeExtent
+
+void
+ExtentManager::RemoveBlockRangeExtent(off_t blockAddr, off_t numBlocks)
+{
+	struct ExtentInfo ext, newExt;
+	ListExtIt curIt;
+
+	ext.blockAddr = blockAddr;
+	ext.numBlocks = numBlocks;
+
+	curIt = extentList.begin();
+	while (curIt != extentList.end()) {
+		if (BeforeExtent(*curIt, ext)) {
+			curIt++;
+			continue;
+		}
+		if (BeforeExtent(ext, *curIt)) // we are done
+			break;
+		// overlapped extents
+		if (curIt->blockAddr >= ext.blockAddr &&
+			curIt->blockAddr + curIt->numBlocks <= ext.blockAddr + ext.numBlocks) {
+			// *curIt is totally within ext, remove curIt
+			curIt = extentList.erase(curIt);
+		} else if (curIt->blockAddr < ext.blockAddr &&
+			curIt->blockAddr + curIt->numBlocks > ext.blockAddr + ext.numBlocks) {
+			// ext is totally within *curIt, split ext into two
+			newExt.blockAddr = ext.blockAddr + ext.numBlocks;
+			newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr;
+			curIt->numBlocks = ext.blockAddr - curIt->blockAddr;
+			curIt++;
+			extentList.insert(curIt, newExt); // throws bad_alloc when out of memory
+			curIt++;	
+		} else { // remove part of ext
+			if (curIt->blockAddr >= ext.blockAddr) { // remove the former part of *curIt
+				assert(curIt->blockAddr + curIt->numBlocks > newExt.blockAddr);
+				newExt.blockAddr = ext.blockAddr + ext.numBlocks;
+				newExt.numBlocks = curIt->blockAddr + curIt->numBlocks - newExt.blockAddr;
+				*curIt = newExt;
+			} else { // remove the latter part of *curIt
+				curIt->numBlocks = ext.blockAddr - curIt->blockAddr;
+			}
+			curIt++;
+		}
+	}
+	//printf("After %s(%lld, %lld)\n", __func__, blockAddr, numBlocks);	 DebugPrint();
+}
+
+void
+ExtentManager::AddByteRangeExtent(off_t byteAddr, off_t numBytes)
+{
+	off_t blockAddr = byteAddr / blockSize;
+	off_t blockAddrOfLastByte = (byteAddr + numBytes - 1) / blockSize;
+	off_t numBlocks = blockAddrOfLastByte - blockAddr + 1;
+	AddBlockRangeExtent(blockAddr, numBlocks);
+}
+
+void
+ExtentManager::DebugPrint()
+{
+	ListExtIt it;
+
+	for (it = extentList.begin(); it != extentList.end(); it++) {
+		printf("[%lld, %lld] ", it->blockAddr, it->numBlocks);
+	}
+	printf("\n");
+}