dmmlib/src/freelist/linked_lists/search_algorithms.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 <stdio.h>
#include "freelist/linked_lists/search_algorithms.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 * best_fit_on_freelist(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;

    current_block = NULL;
    previous_block = NULL;
    best_previous_block = NULL;
    best_block = NULL;
    best_size = (size_t) -1; /* SIZE_MAX */
    block_size = 0;

    for(current_block = raw_block->free_list_head; current_block != NULL;
            current_block = current_block->next) {
        block_size = get_size(current_block);
        if(block_size >= requested_size) {
            if(block_size < best_size) {
                best_block = current_block;
                best_size = get_size(current_block);
                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: remove_block() is not used because the block is already found */
    if(best_block != NULL) {
        if(best_block == raw_block->free_list_head) {
            raw_block->free_list_head = best_block->next;
#ifdef BLOCKS_IN_DLL
            if(heap->free_list_head != NULL) {
                set_previous(heap->free_list_head, NULL);
            }
#endif /* BLOCKS_IN_DLL */
        } else {
            best_previous_block->next = best_block->next;
#ifdef BLOCKS_IN_DLL
            if(get_next(best_block) != NULL) {
                set_previous(get_next(best_block), best_previous_block);
            }
#endif /* BLOCKS_IN_DLL */
        }
    }

    return best_block;
}

#ifdef GOOD_FIT

void * good_fit_on_freelist(raw_block_header_t *raw_block, size_t requested_size) {
    void *current_block, *previous_block;
    void *best_block, *best_previous_block;
    size_t best_size, block_size;

    current_block = NULL;
    previous_block = NULL;
    best_previous_block = NULL;
    best_block = NULL;
    best_size = (size_t) -1; /* SIZE_MAX */
    block_size = 0;

    for(current_block = heap->free_list_head; current_block != NULL;
            current_block = get_next(current_block)) {
#ifdef COUNT_HOPS
        heap->dmm_stats.total_hops++;
#endif /* COUNT_HOPS */
        block_size = get_size(current_block);
        if(block_size >= requested_size) {
            if(block_size < best_size) {
                best_block = current_block;
                best_size = get_size(current_block);
                best_previous_block = previous_block;
		/* If the block size fits the relaxed requirements, then there
		 * is no need to keep searching for a better sized block */
                if(heap->dmm_knobs.fit_percentage * best_size <= requested_size) {
                    break;
                }
            }
        }
        previous_block = current_block;
    } 

    /* Remove the block from the list */
    /* Note: remove_block() is not used because the block is already found */
    if(best_block != NULL) {
        if(best_block == heap->free_list_head) {
            heap->free_list_head = get_next(best_block);
#ifdef BLOCKS_IN_DLL
            if(heap->free_list_head != NULL) {
                set_previous(heap->free_list_head, NULL);
            }
#endif /* BLOCKS_IN_DLL */
        } else {
            set_next(best_previous_block, get_next(best_block));
#ifdef BLOCKS_IN_DLL
            if(get_next(best_block) != NULL) {
                set_previous(get_next(best_block), best_previous_block);
            }
#endif /* BLOCKS_IN_DLL */
        }
    }

    return best_block;
}

#endif /* GOOD_FIT */


/**
 * \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.
 */
block_header_t * exact_fit_on_freelist(freelist_rb_t *raw_block, size_t requested_size) {
    block_header_t *current_block, *previous_block, *ptr;

    previous_block = NULL;
    ptr = NULL;

    for(current_block = raw_block->free_list_head; current_block != NULL;
            current_block = current_block->next) {
        if(get_size(current_block) == requested_size) {
            if(current_block == raw_block->free_list_head) {
                raw_block->free_list_head = current_block->next;
#ifdef BLOCKS_IN_DLL
                set_previous(heap->free_list_head, NULL);
#endif /* BLOCKS_IN_DLL */
            } else {
                previous_block->next = current_block->next;
#ifdef BLOCKS_IN_DLL
                set_previous(get_next(current_block), previous_block);
#endif /* BLOCKS_IN_DLL */
            }
            ptr = current_block;
            break;
        }
        previous_block = current_block;
    } 

    return ptr;
}

/**
 * \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.
 */
block_header_t * first_fit_on_freelist(freelist_rb_t *raw_block, size_t requested_size) {
    block_header_t *current_block, *previous_block, *ptr;

    previous_block = NULL;
    ptr = NULL;

    for(current_block = raw_block->free_list_head; current_block != NULL;
            current_block = current_block->next) {
        if(get_size(current_block) >= requested_size) {
            if(current_block == raw_block->free_list_head) {
                raw_block->free_list_head = current_block->next;
#ifdef BLOCKS_IN_DLL
                set_previous(heap->free_list_head, NULL);
#endif /* BLOCKS_IN_DLL */
            } else {
                previous_block->next = current_block->next;
#ifdef BLOCKS_IN_DLL
                set_previous(get_next(current_block), previous_block);
#endif /* BLOCKS_IN_DLL */
            }
            ptr = current_block;
            break;
        }
        previous_block = current_block;
    } 

    return ptr;
}