63#define FREE_PAGE_SPAN_LEADER_MAGIC 0xea4020f0
64#define FREE_PAGE_LEAF_MAGIC 0x98eae728
65#define FREE_PAGE_INTERNAL_MAGIC 0x19aa32c9
72 RelptrFreePageSpanLeader
prev;
73 RelptrFreePageSpanLeader
next;
100#define FPM_ITEMS_PER_INTERNAL_PAGE \
101 ((FPM_PAGE_SIZE - sizeof(FreePageBtreeHeader)) / \
102 sizeof(FreePageBtreeInternalKey))
103#define FPM_ITEMS_PER_LEAF_PAGE \
104 ((FPM_PAGE_SIZE - sizeof(FreePageBtreeHeader)) / \
105 sizeof(FreePageBtreeLeafKey))
160 Size npages,
bool soft);
167#ifdef FPM_EXTRA_ASSERTS
196#ifdef FPM_EXTRA_ASSERTS
213 Size contiguous_pages;
238#ifdef FPM_EXTRA_ASSERTS
241 Assert(fpm->free_pages >= npages);
242 fpm->free_pages -= npages;
244 Assert(fpm->free_pages == sum_free_pages(fpm));
250#ifdef FPM_EXTRA_ASSERTS
269 sum_free_pages_recurse(fpm, child, sum);
294 }
while (candidate != NULL);
303 sum_free_pages_recurse(fpm,
root, &sum);
338 if (candidate->
npages > largest)
339 largest = candidate->
npages;
341 }
while (candidate != NULL);
381 Size contiguous_pages;
393 if (contiguous_pages > npages)
395 Size cleanup_contiguous_pages;
398 if (cleanup_contiguous_pages > contiguous_pages)
399 contiguous_pages = cleanup_contiguous_pages;
413#ifdef FPM_EXTRA_ASSERTS
414 fpm->free_pages += npages;
415 Assert(fpm->free_pages == sum_free_pages(fpm));
429 bool dumped_any_freelist =
false;
469 if (!dumped_any_freelist)
472 dumped_any_freelist =
true;
551#ifdef USE_ASSERT_CHECKING
557 Assert(s < parent->hdr.nused);
583 Size max_contiguous_pages = 0;
591 if (
root->hdr.nused == 1)
615 else if (
root->hdr.nused == 2 &&
619 Size start_of_second;
621 end_of_first =
root->u.leaf_key[0].first_page +
622 root->u.leaf_key[0].npages;
623 start_of_second =
root->u.leaf_key[1].first_page;
625 if (end_of_first + 1 == start_of_second)
629 if (end_of_first == root_page)
635 root->u.leaf_key[1].npages + 1;
641 Assert(max_contiguous_pages == 0);
670 Size contiguous_pages;
675 if (contiguous_pages == 0)
682 if (contiguous_pages > max_contiguous_pages)
683 max_contiguous_pages = contiguous_pages;
687 return max_contiguous_pages;
1076 result->
page = NULL;
1077 result->
found =
false;
1096 if (!found_exact &&
index > 0)
1150 Size mid = (low + high) / 2;
1153 if (first_page ==
val)
1155 else if (first_page <
val)
1180 Size mid = (low + high) / 2;
1183 if (first_page ==
val)
1185 else if (first_page <
val)
1262 if (parent != check_parent)
1301 while (span != NULL)
1303 if (span->
npages != expected_pages)
1326 Size victim_page = 0;
1361 if (candidate->
npages >= npages && (victim == NULL ||
1365 if (victim->
npages == npages)
1369 }
while (candidate != NULL);
1440 if (victim->
npages == npages)
1450 key->first_page += npages;
1451 key->npages -= npages;
1452 if (result.
index == 0)
1457 victim->
npages - npages);
1534 elog(
FATAL,
"free page manager btree is corrupt");
1539 root->hdr.nused = 1;
1554 if (
root->u.leaf_key[0].npages == 0)
1556 root->u.leaf_key[0].first_page = first_page;
1557 root->u.leaf_key[0].npages = npages;
1569 if (result.
index > 0)
1574 nindex = result.
index;
1586 if (prevkey != NULL && prevkey->
first_page + prevkey->
npages >= first_page)
1588 bool remove_next =
false;
1595 if (nextkey != NULL &&
1609 result = prevkey->
npages;
1628 if (nextkey != NULL && first_page + npages >= nextkey->
first_page)
1642 nextkey->
npages = newpages;
1686 for (
i = 0;
i < pages_needed; ++
i)
1689 elog(
FATAL,
"free page manager btree is corrupt");
1746 split_target : newsibling;
1749 if (
index == 0 && insert_into == split_target)
1759 split_target : newsibling;
1764 if (
index == 0 && insert_into == split_target)
1811 split_target = parent;
1829 if (result.
index == 0)
#define Assert(condition)
static Size FreePageBtreeSearchInternal(FreePageBtree *btp, Size first_page)
#define FREE_PAGE_INTERNAL_MAGIC
struct FreePageBtreeHeader FreePageBtreeHeader
struct FreePageBtreeInternalKey FreePageBtreeInternalKey
static FreePageBtree * FreePageBtreeFindRightSibling(char *base, FreePageBtree *btp)
static Size FreePageBtreeFirstKey(FreePageBtree *btp)
static Size FreePageBtreeSearchLeaf(FreePageBtree *btp, Size first_page)
static void FreePagePopSpanLeader(FreePageManager *fpm, Size pageno)
static bool FreePageManagerGetInternal(FreePageManager *fpm, Size npages, Size *first_page)
char * FreePageManagerDump(FreePageManager *fpm)
static void FreePageBtreeRemove(FreePageManager *fpm, FreePageBtree *btp, Size index)
static void FreePagePushSpanLeader(FreePageManager *fpm, Size first_page, Size npages)
static void FreePageBtreeInsertInternal(char *base, FreePageBtree *btp, Size index, Size first_page, FreePageBtree *child)
static void FreePageBtreeAdjustAncestorKeys(FreePageManager *fpm, FreePageBtree *btp)
bool FreePageManagerGet(FreePageManager *fpm, Size npages, Size *first_page)
static Size FreePageManagerLargestContiguous(FreePageManager *fpm)
void FreePageManagerPut(FreePageManager *fpm, Size first_page, Size npages)
#define FPM_ITEMS_PER_LEAF_PAGE
static void FreePageManagerUpdateLargest(FreePageManager *fpm)
static FreePageBtree * FreePageBtreeFindLeftSibling(char *base, FreePageBtree *btp)
static FreePageBtree * FreePageBtreeGetRecycled(FreePageManager *fpm)
struct FreePageBtreeSearchResult FreePageBtreeSearchResult
static FreePageBtree * FreePageBtreeSplitPage(FreePageManager *fpm, FreePageBtree *btp)
static void FreePageBtreeRemovePage(FreePageManager *fpm, FreePageBtree *btp)
static void FreePageBtreeUpdateParentPointers(char *base, FreePageBtree *btp)
#define FREE_PAGE_SPAN_LEADER_MAGIC
struct FreePageBtreeLeafKey FreePageBtreeLeafKey
static Size FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, bool soft)
void FreePageManagerInitialize(FreePageManager *fpm, char *base)
static void FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, FreePageBtree *parent, int level, StringInfo buf)
static Size FreePageBtreeCleanup(FreePageManager *fpm)
static void FreePageBtreeInsertLeaf(FreePageBtree *btp, Size index, Size first_page, Size npages)
static void FreePageBtreeSearch(FreePageManager *fpm, Size first_page, FreePageBtreeSearchResult *result)
#define FPM_ITEMS_PER_INTERNAL_PAGE
static void FreePageBtreeConsolidate(FreePageManager *fpm, FreePageBtree *btp)
#define FREE_PAGE_LEAF_MAGIC
static void FreePageManagerDumpSpans(FreePageManager *fpm, FreePageSpanLeader *span, Size expected_pages, StringInfo buf)
static void FreePageBtreeRecycle(FreePageManager *fpm, Size pageno)
#define fpm_page_to_pointer(base, page)
#define FPM_NUM_FREELISTS
#define fpm_pointer_to_page(base, ptr)
#define fpm_segment_base(fpm)
#define fpm_pointer_is_page_aligned(base, ptr)
#define relptr_is_null(rp)
#define relptr_access(base, rp)
#define relptr_store(base, rp, val)
#define relptr_offset(rp)
#define relptr_copy(rp1, rp2)
void check_stack_depth(void)
void appendStringInfo(StringInfo str, const char *fmt,...)
void appendStringInfoString(StringInfo str, const char *s)
void appendStringInfoChar(StringInfo str, char ch)
void initStringInfo(StringInfo str)
RelptrFreePageBtree child
FreePageBtreeInternalKey internal_key[FPM_ITEMS_PER_INTERNAL_PAGE]
FreePageBtreeLeafKey leaf_key[FPM_ITEMS_PER_LEAF_PAGE]
union FreePageBtree::@33 u
unsigned btree_recycle_count
RelptrFreePageManager self
Size singleton_first_page
RelptrFreePageBtree btree_root
RelptrFreePageSpanLeader freelist[FPM_NUM_FREELISTS]
bool contiguous_pages_dirty
RelptrFreePageSpanLeader btree_recycle
RelptrFreePageSpanLeader prev
RelptrFreePageSpanLeader next