source: mainline/uspace/srv/net/structures/dynamic_fifo.c@ f1848d6

/*
 * Copyright (c) 2009 Lukas Mejdrech
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup net
 *  @{
 */

/** @file
 *  Dynamic first in first out positive integer queue implementation.
 */

#include <errno.h>
#include <malloc.h>
#include <mem.h>

#include "dynamic_fifo.h"

/** Internal magic value for a&nbsp;consistency check.
 */
#define DYN_FIFO_MAGIC_VALUE    0x58627659

/** Returns the next queue index.
 *  The queue field is circular.
 *  @param[in] fifo The dynamic queue.
 *  @param[in] index The actual index to be shifted.
 */
#define NEXT_INDEX( fifo, index )       ((( index ) + 1 ) % (( fifo )->size + 1 ))

/** Checks if the queue is valid.
 *  @param[in] fifo The dynamic queue.
 *  @returns TRUE if the queue is valid.
 *  @returns FALSE otherwise.
 */
int     dyn_fifo_is_valid( dyn_fifo_ref fifo );

int dyn_fifo_is_valid( dyn_fifo_ref fifo ){
        return fifo && ( fifo->magic_value == DYN_FIFO_MAGIC_VALUE );
}

int dyn_fifo_initialize( dyn_fifo_ref fifo, int size ){
        if( ! fifo ) return EBADMEM;
        if( size <= 0 ) return EINVAL;
        fifo->items = ( int * ) malloc( sizeof( int ) * size + 1 );
        if( ! fifo->items ) return ENOMEM;
        fifo->size = size;
        fifo->head = 0;
        fifo->tail = 0;
        fifo->magic_value = DYN_FIFO_MAGIC_VALUE;
        return EOK;
}

int     dyn_fifo_push( dyn_fifo_ref fifo, int value, int max_size ){
        int *   new_items;

        if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
        if( NEXT_INDEX( fifo, fifo->tail ) == fifo->head ){
                if(( max_size > 0 ) && (( fifo->size * 2 ) > max_size )){
                        if( fifo->size >= max_size ) return ENOMEM;
                }else{
                        max_size = fifo->size * 2;
                }
                new_items = realloc( fifo->items, sizeof( int ) * max_size + 1 );
                if( ! new_items ) return ENOMEM;
                fifo->items = new_items;
                if( fifo->tail < fifo->head ){
                        if( fifo->tail < max_size - fifo->size ){
                                memcpy( fifo->items + fifo->size + 1, fifo->items, fifo->tail * sizeof( int ));
                                fifo->tail += fifo->size + 1;
                        }else{
                                memcpy( fifo->items + fifo->size + 1, fifo->items, ( max_size - fifo->size ) * sizeof( int ));
                                memcpy( fifo->items, fifo->items + max_size - fifo->size, fifo->tail - max_size + fifo->size );
                                fifo->tail -= max_size - fifo->size;
                        }
                }
                fifo->size = max_size;
        }
        fifo->items[ fifo->tail ] = value;
        fifo->tail = NEXT_INDEX( fifo, fifo->tail );
        return EOK;
}

int dyn_fifo_pop( dyn_fifo_ref fifo ){
        int     value;

        if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
        if( fifo->head == fifo->tail ) return ENOENT;
        value = fifo->items[ fifo->head ];
        fifo->head = NEXT_INDEX( fifo, fifo->head );
        return value;
}

int dyn_fifo_value( dyn_fifo_ref fifo ){
        if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
        if( fifo->head == fifo->tail ) return ENOENT;
        return fifo->items[ fifo->head ];
}

int dyn_fifo_destroy( dyn_fifo_ref fifo ){
        if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
        free( fifo->items );
        fifo->magic_value = 0;
        return EOK;
}

/** @}
 */