From 3606cca91d57668528a18cef0415133a56039a83 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Wed, 12 Feb 2014 22:39:29 -0500
Subject: [PATCH] More hacking.

---
 src/backend/utils/mmgr/freepage.c | 77 ++++++++++++++++++++++++++++---
 src/include/utils/freepage.h      |  9 ++--
 2 files changed, 76 insertions(+), 10 deletions(-)

diff --git a/src/backend/utils/mmgr/freepage.c b/src/backend/utils/mmgr/freepage.c
index 7acb434d93..221025b4d6 100644
--- a/src/backend/utils/mmgr/freepage.c
+++ b/src/backend/utils/mmgr/freepage.c
@@ -47,8 +47,8 @@ typedef struct FreePageBtreeInternalKey
 /* Leaf key; no payload data. */
 typedef struct FreePageBtreeLeafKey
 {
-	Size	first_page;				/* low bound for keys on child page */
-	Size	last_page;				/* high bound for keys on child page */
+	Size	first_page;				/* first page in span */
+	Size	npages;					/* number of pages in span */
 } FreePageBtreeLeafKey;
 
 /* Work out how many keys will fit on a page. */
@@ -121,7 +121,7 @@ FreePageManagerInitialize(FreePageManager *fpm, char *base, LWLock *lock,
 	relptr_store(base, fpm->self, fpm);
 	relptr_store(base, fpm->lock, lock);
 	fpm->lock_address_is_fixed = lock_address_is_fixed;
-	relptr_store(base, fpm->root, (FreePageBtree *) NULL);
+	relptr_store(base, fpm->btree_root, (FreePageBtree *) NULL);
 
 	for (f = 0; f < FPM_NUM_FREELISTS; f++)
 		relptr_store(base, fpm->freelist[f], (FreePageSpanLeader *) NULL);
@@ -222,20 +222,85 @@ FreePageManagerGet(FreePageManager *fpm, Size npages, Size *first_page)
 	return true;
 }
 
+/*
+ * Insert an item into the btree in the given position on the given page.
+ */
+static void
+FreePageBtreeInsert(FreePageManager *fpm, FreePageBtree *btp, Size index,
+					Size first_page, Size npages)
+{
+	char *base = fpm_segment_base(fpm);
+	FreePageBtree *splitroot;
+	int		nsplits = 0;
+
+	Assert(btp->hdr.magic == FREE_PAGE_LEAF_MAGIC);
+	Assert(index < btp->hdr.nused);
+	Assert(btp->hdr.nused <= FPM_ITEMS_PER_LEAF_PAGE);
+
+	/* If the page is not full, this is easy as pie. */
+	if (btp->hdr.nused < FPM_ITEMS_PER_LEAF_PAGE)
+	{
+		memmove(&btp->u.leaf_key[index + 1], &btp->u.leaf_key[index],
+				sizeof(FreePageBtreeLeafKey) * (btp->hdr.nused - index));
+		btp->u.leaf_key[index].first_page = first_page;
+		btp->u.leaf_key[index].npages = npages;
+		++btp->hdr.nused;
+		return;
+	}
+
+	/*
+	 * Move upward until we find a page that isn't full.  We'll need to split
+	 * everything below that point.
+	 */
+	++nsplits;
+	splitroot = relptr_access(base, btp->parent);
+	for (;;)
+	{
+		++nsplits;
+		if (splitroot == NULL)
+			break;
+
+		Assert(splitroot->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
+		Assert(btp->hdr.nused <= FPM_ITEMS_PER_INTERNAL_PAGE);
+
+		if (splitroot->hdr.nused < FPM_ITEMS_PER_INTERNAL_PAGE)
+			break;
+		splitroot = relptr_access(base, splitroot->parent);
+	}
+
+	/*
+	 * XXX. Ensure that we have at least nsplit spages in fpm->btree_recycle.
+	 * How?
+	 */
+
+	/*
+	 * If everything up to and including the root was full, split the root.
+	 * The depth of the btree increases by one.
+	 */
+	if (splitroot == NULL)
+	{
+		/* XXX. Perform root split. */
+	}
+
+	/* Work our way down the tree, splitting as we go. */
+	while (splitroot->hdr.magic == FREE_PAGE_INTERNAL_MAGIC)
+}
+
 /*
  * Remove from the btree the item in the given position on the given page.
  */
 static void
 FreePageBtreeRemove(FreePageManager *fpm, FreePageBtree *btp, Size index)
 {
+	char *base = fpm_segment_base(fpm);
 	Assert(btp->hdr.magic == FREE_PAGE_LEAF_MAGIC);
 	Assert(index < btp->hdr.nused);
 
 	/* Shuffle remaining keys. */
 	--btp->hdr.nused;
 	if (index < btp->hdr.nused)
-		memmove(&btp->u.leaf_key[index], btp->u.leaf_key[index + 1],
-				sizeof(FreePageBtreeLeafKey) * btp->hdr.nused - index);
+		memmove(&btp->u.leaf_key[index], &btp->u.leaf_key[index + 1],
+				sizeof(FreePageBtreeLeafKey) * (btp->hdr.nused - index));
 
 	/*
 	 * XXX.  At this point, the key is gone, but the node may be empty or
@@ -277,7 +342,7 @@ FreePageBtreeSearch(FreePageManager *fpm, Size first_page,
 					FreePageBtreeSearchResult *result)
 {
 	char *base = fpm_segment_base(fpm);
-	FreePageBtree *btp = relptr_access(base, fpm->root);
+	FreePageBtree *btp = relptr_access(base, fpm->btree_root);
 	Size	index;
 
 	/* If the btree is empty, then this would be the only item. */
diff --git a/src/include/utils/freepage.h b/src/include/utils/freepage.h
index 84ee0d39ab..e33d35ae54 100644
--- a/src/include/utils/freepage.h
+++ b/src/include/utils/freepage.h
@@ -49,11 +49,12 @@ typedef struct FreePageManager FreePageManager;
 /* Everything we need in order to manage free pages (see freepage.c) */
 struct FreePageManager
 {
-    relptr(FreePageManager)  self;
-    relptr(LWLock)  lock;
+	relptr(FreePageManager)  self;
+	relptr(LWLock)  lock;
 	bool			lock_address_is_fixed;
-    relptr(FreePageBtree)   root;
-    relptr(FreePageSpanLeader)  freelist[FPM_NUM_FREELISTS];
+	relptr(FreePageBtree)   btree_root;
+	relptr(FreePageSpanLeader)	btree_recycle;
+	relptr(FreePageSpanLeader)  freelist[FPM_NUM_FREELISTS];
 };
 
 /* Macros to convert between page numbers (expressed as Size) and pointers. */
-- 
2.39.5