/*
 * Copyright (c) 2020 Red Hat, Inc.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA. 
 *
 * $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/forest.h#2 $
 */

#ifndef FOREST_H
#define FOREST_H

#include "blockMapTree.h"
#include "types.h"

/**
 * A function to be called for each allocated PBN when traversing the forest.
 *
 * @param pbn         A PBN of a tree node
 * @param completion  The parent completion of the traversal
 *
 * @return VDO_SUCCESS or an error
 **/
typedef int EntryCallback(PhysicalBlockNumber pbn, VDOCompletion *completion);

/**
 * Get the tree page for a given height and page index.
 *
 * @param forest     The forest which holds the page
 * @param rootIndex  The index of the tree that holds the page
 * @param height     The height of the desired page
 * @param pageIndex  The index of the desired page
 *
 * @return The requested page
 **/
TreePage *getTreePageByIndex(Forest       *forest,
                             RootCount     rootIndex,
                             Height        height,
                             PageNumber    pageIndex)
  __attribute__((warn_unused_result));

/**
 * Make a collection of trees for a BlockMap, expanding the existing forest if
 * there is one.
 *
 * @param map      The block map
 * @param entries  The number of entries the block map will hold
 *
 * @return VDO_SUCCESS or an error
 **/
int makeForest(BlockMap *map, BlockCount entries)
  __attribute__((warn_unused_result));

/**
 * Free a forest and all of the segments it contains and NULL out the reference
 * to it.
 *
 * @param forestPtr  A pointer to the forest to free
 **/
void freeForest(Forest **forestPtr);

/**
 * Abandon the unused next forest from a BlockMap.
 *
 * @param map  The block map
 **/
void abandonForest(BlockMap *map);

/**
 * Replace a BlockMap's Forest with the already-prepared larger forest.
 *
 * @param map  The block map
 **/
void replaceForest(BlockMap *map);

/**
 * Walk the entire forest of a block map.
 *
 * @param map            The block map to traverse
 * @param entryCallback  A function to call with the pbn of each allocated node
 *                       in the forest
 * @param parent         The completion to notify on each traversed PBN, and
 *                       when the traversal is complete
 **/
void traverseForest(BlockMap      *map,
                    EntryCallback *entryCallback,
                    VDOCompletion *parent);

/**
 * Compute the approximate number of pages which the forest will allocate in
 * order to map the specified number of logical blocks. This method assumes
 * that the block map is entirely arboreal.
 *
 * @param logicalBlocks  The number of blocks to map
 * @param rootCount      The number of trees in the forest
 *
 * @return A (slight) over-estimate of the total number of possible forest
 *         pages including the leaves
 **/
BlockCount computeForestSize(BlockCount logicalBlocks, RootCount rootCount)
  __attribute__((warn_unused_result));
#endif // FOREST_H