dmmlib/src/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 "linked_lists/search_algorithms.h"
#include "block_header.h"

#ifdef WITH_FIXED_LISTS
/**
 * \details The maptable of the heap is being traversed sequentially while
 * searching for a size equal of the requested size. If one is found, then we
 * return the head of this list (provided that it is not null) and set the next
 * block as the new head.
 */
void * search_on_fixed(heap_t * heap, size_t requested_size) {
    maptable_node_t *node;
    void *ptr;

    node = heap->maptable_head;
    ptr = NULL;

    while(node) {
#ifdef COUNT_HOPS
        heap->dmm_stats.total_hops++;
#endif /* COUNT_HOPS */
        if(node->size == requested_size) {
            if(node->fixed_list_head != NULL) {
                ptr = node->fixed_list_head;
                node->fixed_list_head = get_next(ptr);
#ifdef BLOCKS_IN_DLL
                set_previous(node->fixed_list_head, NULL);
#endif /* BLOCKS_IN_DLL */
            }
            break;
        }
        node = node->next;
    }

    return ptr;
}
#endif /* WITH_FIXED_LISTS */

/**
 * \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;
    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 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 == 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;
}

#ifdef GOOD_FIT

void * good_fit_on_freelist(heap_t *heap, 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.
 */
void * exact_fit_on_freelist(heap_t *heap, size_t requested_size) {
    void *current_block, *previous_block, *ptr;

    previous_block = NULL;
    ptr = NULL;

    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 */
        if(get_size(current_block) == requested_size) {
            if(current_block == heap->free_list_head) {
                heap->free_list_head = get_next(current_block);
#ifdef BLOCKS_IN_DLL
                set_previous(heap->free_list_head, NULL);
#endif /* BLOCKS_IN_DLL */
            } else {
                set_next(previous_block, get_next(current_block));
#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.
 */
void * first_fit_on_freelist(heap_t *heap, size_t requested_size) {
    void *current_block, *previous_block, *ptr;

    previous_block = NULL;
    ptr = NULL;

    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 */
        if(get_size(current_block) >= requested_size) {
            if(current_block == heap->free_list_head) {
                heap->free_list_head = get_next(current_block);
#ifdef BLOCKS_IN_DLL
                set_previous(heap->free_list_head, NULL);
#endif /* BLOCKS_IN_DLL */
            } else {
                set_next(previous_block, get_next(current_block));
#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;
}