dmmlib/src/sll/best_fit_on_freelist.c

/*
 *   Copyright 2011 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 "sll/best_fit_on_freelist.h"
#include "block_header.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.
 */
void * best_fit_on_freelist(heap_t *heap, size_t requested_size) {
    void *current_block, *previous_block, *ptr;
    void *best_block, *best_previous_block;
    size_t best_size;

    ptr = NULL;
    best_block = NULL;
    best_size = (size_t) -1; /* SIZE_MAX */

    for(current_block = heap->free_list_head; current_block != NULL;
            current_block = get_next(current_block)) {
        if(get_size(current_block) >= requested_size) {
            if(get_size(current_block) < best_size) {
                best_block = current_block;
                best_size = get_size(current_block);
                best_previous_block = previous_block;
                if(best_size == requested_size) {
                    break;
                }
            }
        }
        previous_block = current_block;
    } 

    /* Remove the block from the list */
    if(best_block != NULL) {
        if(best_block == heap->free_list_head) {
            heap->free_list_head = get_next(best_block);
        } else {
            set_next(best_previous_block, get_next(best_block));
        }
        ptr = best_block;
    }

    return ptr;
}