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)) 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 264 for (index = 0; index < btp->
hdr.
nused; ++index)
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;
619 Size start_of_second;
625 if (end_of_first + 1 == start_of_second)
629 if (end_of_first == root_page)
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;
1027 * (parent->
hdr.
nused - index - 1));
1037 * (parent->
hdr.
nused - index - 1));
1076 result->
page = NULL;
1077 result->
found =
false;
1088 found_exact = index < btp->
hdr.
nused &&
1096 if (!found_exact && index > 0)
1129 result->
index = index;
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)
1267 for (index = 0; index < btp->
hdr.
nused; ++index)
1282 for (index = 0; index < btp->
hdr.
nused; ++index)
1301 while (span != NULL)
1303 if (span->
npages != expected_pages)
1326 Size victim_page = 0;
1352 if (f < FPM_NUM_FREELISTS - 1)
1361 if (candidate->
npages >= npages && (victim == NULL ||
1365 if (victim->
npages == npages)
1369 }
while (candidate != NULL);
1391 if (f == FPM_NUM_FREELISTS - 1 &&
1440 if (victim->
npages == npages)
1452 if (result.
index == 0)
1457 victim->
npages - npages);
1534 elog(
FATAL,
"free page manager btree is corrupt");
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)
static Size FreePageManagerLargestContiguous(FreePageManager *fpm)
static void FreePageManagerUpdateLargest(FreePageManager *fpm)
#define relptr_copy(rp1, rp2)
static void FreePagePushSpanLeader(FreePageManager *fpm, Size first_page, Size npages)
#define relptr_store(base, rp, val)
static void FreePageBtreeSearch(FreePageManager *fpm, Size first_page, FreePageBtreeSearchResult *result)
#define fpm_pointer_is_page_aligned(base, ptr)
static Size FreePageBtreeSearchInternal(FreePageBtree *btp, Size first_page)
#define FREE_PAGE_LEAF_MAGIC
#define relptr_is_null(rp)
RelptrFreePageBtree btree_root
RelptrFreePageSpanLeader prev
static FreePageBtree * FreePageBtreeSplitPage(FreePageManager *fpm, FreePageBtree *btp)
static Size FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, bool soft)
RelptrFreePageSpanLeader btree_recycle
struct FreePageBtreeHeader FreePageBtreeHeader
static void FreePageBtreeAdjustAncestorKeys(FreePageManager *fpm, FreePageBtree *btp)
void FreePageManagerPut(FreePageManager *fpm, Size first_page, Size npages)
FreePageBtreeLeafKey leaf_key[FPM_ITEMS_PER_LEAF_PAGE]
static void FreePageBtreeRecycle(FreePageManager *fpm, Size pageno)
bool FreePageManagerGet(FreePageManager *fpm, Size npages, Size *first_page)
static FreePageBtree * FreePageBtreeFindRightSibling(char *base, FreePageBtree *btp)
Size singleton_first_page
void appendStringInfo(StringInfo str, const char *fmt,...)
static void FreePageBtreeRemovePage(FreePageManager *fpm, FreePageBtree *btp)
RelptrFreePageSpanLeader next
struct FreePageBtreeInternalKey FreePageBtreeInternalKey
#define FREE_PAGE_INTERNAL_MAGIC
#define relptr_access(base, rp)
#define fpm_page_to_pointer(base, page)
#define FPM_NUM_FREELISTS
static FreePageBtree * FreePageBtreeFindLeftSibling(char *base, FreePageBtree *btp)
void appendStringInfoString(StringInfo str, const char *s)
void check_stack_depth(void)
static void FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, FreePageBtree *parent, int level, StringInfo buf)
static void FreePageBtreeUpdateParentPointers(char *base, FreePageBtree *btp)
static void FreePageBtreeConsolidate(FreePageManager *fpm, FreePageBtree *btp)
#define FPM_ITEMS_PER_INTERNAL_PAGE
static Size FreePageBtreeCleanup(FreePageManager *fpm)
bool contiguous_pages_dirty
static bool FreePageManagerGetInternal(FreePageManager *fpm, Size npages, Size *first_page)
void appendStringInfoChar(StringInfo str, char ch)
void initStringInfo(StringInfo str)
static Size FreePageBtreeFirstKey(FreePageBtree *btp)
static FreePageBtree * FreePageBtreeGetRecycled(FreePageManager *fpm)
void FreePageManagerInitialize(FreePageManager *fpm, char *base)
struct FreePageBtreeSearchResult FreePageBtreeSearchResult
RelptrFreePageManager self
static void FreePageBtreeInsertInternal(char *base, FreePageBtree *btp, Size index, Size first_page, FreePageBtree *child)
union FreePageBtree::@34 u
#define Assert(condition)
#define fpm_pointer_to_page(base, ptr)
struct FreePageBtreeLeafKey FreePageBtreeLeafKey
RelptrFreePageSpanLeader freelist[FPM_NUM_FREELISTS]
static Size FreePageBtreeSearchLeaf(FreePageBtree *btp, Size first_page)
char * FreePageManagerDump(FreePageManager *fpm)
unsigned btree_recycle_count
static void FreePageManagerDumpSpans(FreePageManager *fpm, FreePageSpanLeader *span, Size expected_pages, StringInfo buf)
RelptrFreePageBtree child
#define FREE_PAGE_SPAN_LEADER_MAGIC
static void FreePagePopSpanLeader(FreePageManager *fpm, Size pageno)
#define FPM_ITEMS_PER_LEAF_PAGE
static void FreePageBtreeInsertLeaf(FreePageBtree *btp, Size index, Size first_page, Size npages)
static void FreePageBtreeRemove(FreePageManager *fpm, FreePageBtree *btp, Size index)
#define fpm_segment_base(fpm)
FreePageBtreeInternalKey internal_key[FPM_ITEMS_PER_INTERNAL_PAGE]