Subversion Repositories HelenOS

Rev

Rev 4588 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2009 Lukas Mejdrech
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup net
  30.  *  @{
  31.  */
  32.  
  33. /** @file
  34.  *  Dynamic first in first out positive integer queue implementation.
  35.  */
  36.  
  37. #include <errno.h>
  38. #include <malloc.h>
  39. #include <mem.h>
  40.  
  41. #include "dynamic_fifo.h"
  42.  
  43. /** Internal magic value for a&nbsp;consistency check.
  44.  */
  45. #define DYN_FIFO_MAGIC_VALUE    0x58627659
  46.  
  47. /** Returns the next queue index.
  48.  *  The queue field is circular.
  49.  *  @param fifo The dynamic queue. Input parameter.
  50.  *  @param index The actual index to be shifted. Input parameter.
  51.  */
  52. #define NEXT_INDEX( fifo, index )   ((( index ) + 1 ) % (( fifo )->size + 1 ))
  53.  
  54. /** Checks if the queue is valid.
  55.  *  @param fifo The dynamic queue. Input parameter.
  56.  *  @returns TRUE if the queue is valid.
  57.  *  @returns FALSE otherwise.
  58.  */
  59. int dyn_fifo_is_valid( dyn_fifo_ref fifo );
  60.  
  61. int dyn_fifo_is_valid( dyn_fifo_ref fifo ){
  62.     return fifo && ( fifo->magic_value == DYN_FIFO_MAGIC_VALUE );
  63. }
  64.  
  65. int dyn_fifo_initialize( dyn_fifo_ref fifo, int size ){
  66.     if( ! fifo ) return EBADMEM;
  67.     if( size <= 0 ) return EINVAL;
  68.     fifo->items = ( int * ) malloc( sizeof( int ) * size + 1 );
  69.     if( ! fifo->items ) return ENOMEM;
  70.     fifo->size = size;
  71.     fifo->head = 0;
  72.     fifo->tail = 0;
  73.     fifo->magic_value = DYN_FIFO_MAGIC_VALUE;
  74.     return EOK;
  75. }
  76.  
  77. int dyn_fifo_push( dyn_fifo_ref fifo, int value, int max_size ){
  78.     int *   new_items;
  79.  
  80.     if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
  81.     if( NEXT_INDEX( fifo, fifo->tail ) == fifo->head ){
  82.         if(( max_size > 0 ) && (( fifo->size * 2 ) > max_size )){
  83.             if( fifo->size >= max_size ) return ENOMEM;
  84.         }else{
  85.             max_size = fifo->size * 2;
  86.         }
  87.         new_items = realloc( fifo->items, sizeof( int ) * max_size + 1 );
  88.         if( ! new_items ) return ENOMEM;
  89.         fifo->items = new_items;
  90.         if( fifo->tail < fifo->head ){
  91.             if( fifo->tail < max_size - fifo->size ){
  92.                 memcpy( fifo->items + fifo->size + 1, fifo->items, fifo->tail * sizeof( int ));
  93.                 fifo->tail += fifo->size + 1;
  94.             }else{
  95.                 memcpy( fifo->items + fifo->size + 1, fifo->items, ( max_size - fifo->size ) * sizeof( int ));
  96.                 memcpy( fifo->items, fifo->items + max_size - fifo->size, fifo->tail - max_size + fifo->size );
  97.                 fifo->tail -= max_size - fifo->size;
  98.             }
  99.         }
  100.         fifo->size = max_size;
  101.     }
  102.     fifo->items[ fifo->tail ] = value;
  103.     fifo->tail = NEXT_INDEX( fifo, fifo->tail );
  104.     return EOK;
  105. }
  106.  
  107. int dyn_fifo_pop( dyn_fifo_ref fifo ){
  108.     int value;
  109.  
  110.     if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
  111.     if( fifo->head == fifo->tail ) return ENOENT;
  112.     value = fifo->items[ fifo->head ];
  113.     fifo->head = NEXT_INDEX( fifo, fifo->head );
  114.     return value;
  115. }
  116.  
  117. int dyn_fifo_value( dyn_fifo_ref fifo ){
  118.     if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
  119.     if( fifo->head == fifo->tail ) return ENOENT;
  120.     return fifo->items[ fifo->head ];
  121. }
  122.  
  123. int dyn_fifo_destroy( dyn_fifo_ref fifo ){
  124.     if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
  125.     free( fifo->items );
  126.     fifo->magic_value = 0;
  127.     return EOK;
  128. }
  129.  
  130. /** @}
  131.  */
  132.