/*
* This file is part of UBIFS.
*
* Copyright (C) 2006-2008 Nokia Corporation.
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as published by
* the Free Software Foundation.
*
* 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 St, Fifth Floor, Boston, MA 02110-1301 USA
*
* Authors: Adrian Hunter
* Artem Bityutskiy (Битюцкий Артём)
*/
/*
* This file implements the functions that access LEB properties and their
* categories. LEBs are categorized based on the needs of UBIFS, and the
* categories are stored as either heaps or lists to provide a fast way of
* finding a LEB in a particular category. For example, UBIFS may need to find
* an empty LEB for the journal, or a very dirty LEB for garbage collection.
*/
#include "ubifs.h"
/**
* get_heap_comp_val - get the LEB properties value for heap comparisons.
* @lprops: LEB properties
* @cat: LEB category
*/
static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)
{
switch (cat) {
case LPROPS_FREE:
return lprops->free;
case LPROPS_DIRTY_IDX:
return lprops->free + lprops->dirty;
default:
return lprops->dirty;
}
}
/**
* move_up_lpt_heap - move a new heap entry up as far as possible.
* @c: UBIFS file-system description object
* @heap: LEB category heap
* @lprops: LEB properties to move
* @cat: LEB category
*
* New entries to a heap are added at the bottom and then moved up until the
* parent's value is greater. In the case of LPT's category heaps, the value
* is either the amount of free space or the amount of dirty space, depending
* on the category.
*/
static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
struct ubifs_lprops *lprops, int cat)
{
int val1, val2, hpos;
hpos = lprops->hpos;
if (!hpos)
return; /* Already top of the heap */
val1 = get_heap_comp_val(lprops, cat);
/* Compare to parent and, if greater, move up the heap */
do {
int ppos = (hpos - 1) / 2;
val2 = get_heap_comp_val(heap->arr[ppos], cat);
if (val2 >= val1)
return;
/* Greater than parent so move up */
heap->arr[ppos]->hpos = hpos;
heap->arr[hpos] = heap->arr[ppos];
heap->arr[ppos] = lprops;
lprops->hpos = ppos;
hpos = ppos;
} while (hpos);
}
/**
* adjust_lpt_heap - move a changed heap entry up or down the heap.
* @c: UBIFS file-system description object
* @heap: LEB category heap
* @lprops: LEB properties to move
* @hpos: heap position of @lprops
* @cat: LEB category
*
* Changed entries in a heap are moved up or down until the parent's value is
* greater. In the case of LPT's category heaps, the value is either the amount