xfs/libxfs/xfs_btree.c

630  * The leaf record start with a header then followed by records containing
655  * overlapping intervals.  In such a tree, records are still sorted lowest to
660  * available in the block(s) below.  Because records are /not/ sorted by the
672  * that particular node.  If a leaf node is reached, return the records that
681  * reverse mapping records on a reflink filesystem:
692  * query would return records 1 and 2 because they both overlap (B+D-1), and
1460  * Copy records from one btree block to another.
1507  * Shift records one index left/right inside a single btree block.
2261  * keys because the highest key can be in any of the records or keys
2544 		/* It's a leaf.  Move records.  */
2585 		/* It's a leaf. operate on records */
2740 		/* It's a leaf. make a hole in the records */
2945 		/* It's a leaf.  Move records.  */
2952 		/* Copy records to the new block. */
3344 		 * Get the keys for the left block's records and put them
3463 	int			numrecs;/* number of records */
3582 		/* It's a leaf. make a hole in the records */
3601 	/* Log the new number of records in the btree header. */
3609 	 * some records into the new tree block), so use the regular key
3971 		/* It's a leaf. operate on records */
4049 	 * If the number of records remaining in the block is at least
4060 	 * Otherwise, we have to move some records around to keep the
4163 		 * Otherwise, grab the number of records in right for
4247 		 * Otherwise, grab the number of records in right for
4334 		/* It's a leaf.  Move records.  */
4348 	 * Fix up the number of records and right block pointer in the
4808  * @max_recs: maximum records allowed in this btree node
4837  * For the given limits on leaf and keyptr records per block, calculate the
4838  * height of the tree needed to index the number of leaf records.
4843 	unsigned long long	records)
4845 	unsigned long long	level_blocks = howmany_64(records, limits[0]);
4857  * For the given limits on leaf and keyptr records per block, calculate the
4858  * number of blocks needed to index the given number of leaf records.
4863 	unsigned long long	records)
4865 	unsigned long long	level_blocks = howmany_64(records, limits[0]);
4877  * Given a number of available blocks for the btree to consume with records and
4878  * pointers, calculate the height of the tree needed to index all the records
4915  * Query a regular btree for all records overlapping a given interval.
4916  * Start with a LE lookup of the key of low_rec and return all records
4988  * Query an overlapped interval btree for all records overlapping a given
4993  * First, generate keys for the low and high records passed in.
5065 			 * are no more interesting records in this block.  Pop
5092 		 * to continue looking for records.
5156  * Query a btree for all records overlapping a given interval of keys.  The
5187 /* Query a btree for all records. */
5308  * map to any records; is fully mapped to records; or is partially mapped to
5309  * records.  This is the btree record equivalent to determining if a file is
5367 /* Are there more records in this btree? */
5377 	/* There are still records in this block. */