dmmlib/src/freelist/fitting/best.c

/*
 *   Copyright Institute of Communication and Computer Systems (ICCS) 
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 */

#include <dmmlib/config.h>

#include "freelist/fitting/best.h"
#include "freelist/ordering_policy.h"
#include "freelist/block_header_funcs.h"

/**
 * \details In order to remove a block from a singly linked list, we need to
 * keep track of the previous block as well: The previous block must point to
 * the current block's next block once the current one is removed.
 * Normally the best fit search alogrithm would have to traverse the whole list
 * in order to find the best block. However, a check is being performed each
 * time a new best candidate is found, so that we stop once a perfect block is
 * found.
 */
block_header_t * fl_best_fit(freelist_rb_t *raw_block, size_t requested_size) {
    block_header_t *current_block, *previous_block;
    block_header_t *best_block, *best_previous_block;
    size_t best_size, block_size;

    previous_block = NULL;
    best_previous_block = NULL;
    best_block = NULL;
    best_size = (size_t) -1; /* SIZE_MAX */
    
    SLIST_FOREACH(current_block, &raw_block->fl_head, pointers) {
        block_size = get_size(current_block);
        if(block_size >= requested_size) {
            if(block_size < best_size) {
                best_block = current_block;
                best_size = block_size;
                best_previous_block = previous_block;
                /* If the requested size is found, there is no need to keep
                 * searching for a better sized block */
                if(best_size == requested_size) {
                    break;
                }
            }
        }
        previous_block = current_block;
    } 

    /* Remove the block from the list
     * Note: no need to iterate through the list as the block is already found
     */
    if(best_block != NULL) {
        if((raw_block->fl_head).slh_first == best_block) {
            REMOVE_FSLLIST_HEAD(raw_block);
        } else {
#ifdef FIFO_ORDERED
            if(raw_block->fl_tail == best_block) {
                raw_block->fl_tail = best_previous_block;
            }
#endif /* FIFO_ORDERED */
            best_previous_block->pointers.sle_next =
                best_block->pointers.sle_next;
        }
    }

    return best_block;
}