dynamic_fifo.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2009 Lukas Mejdrech
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00037 #include <adt/dynamic_fifo.h>
00038 
00039 #include <errno.h>
00040 #include <malloc.h>
00041 #include <mem.h>
00042 
00044 #define DYN_FIFO_MAGIC_VALUE    0x58627659
00045 
00053 #define NEXT_INDEX(fifo, index) (((index) + 1) % ((fifo)->size + 1))
00054 
00061 static int dyn_fifo_is_valid(dyn_fifo_t *fifo)
00062 {
00063         return fifo && (fifo->magic_value == DYN_FIFO_MAGIC_VALUE);
00064 }
00065 
00075 int dyn_fifo_initialize(dyn_fifo_t *fifo, int size)
00076 {
00077         if (!fifo)
00078                 return EBADMEM;
00079 
00080         if (size <= 0)
00081                 return EINVAL;
00082 
00083         fifo->items = (int *) malloc(sizeof(int) * size + 1);
00084         if (!fifo->items)
00085                 return ENOMEM;
00086 
00087         fifo->size = size;
00088         fifo->head = 0;
00089         fifo->tail = 0;
00090         fifo->magic_value = DYN_FIFO_MAGIC_VALUE;
00091 
00092         return EOK;
00093 }
00094 
00106 int dyn_fifo_push(dyn_fifo_t *fifo, int value, int max_size)
00107 {
00108         int *new_items;
00109 
00110         if (!dyn_fifo_is_valid(fifo))
00111                 return EINVAL;
00112 
00113         if (NEXT_INDEX(fifo, fifo->tail) == fifo->head) {
00114                 if ((max_size > 0) && ((fifo->size * 2) > max_size)) {
00115                         if(fifo->size >= max_size)
00116                                 return ENOMEM;
00117                 } else {
00118                         max_size = fifo->size * 2;
00119                 }
00120 
00121                 new_items = realloc(fifo->items, sizeof(int) * max_size + 1);
00122                 if (!new_items)
00123                         return ENOMEM;
00124 
00125                 fifo->items = new_items;
00126                 if (fifo->tail < fifo->head) {
00127                         if (fifo->tail < max_size - fifo->size) {
00128                                 memcpy(fifo->items + fifo->size + 1,
00129                                     fifo->items, fifo->tail * sizeof(int));
00130                                 fifo->tail += fifo->size + 1;
00131                         } else {
00132                                 memcpy(fifo->items + fifo->size + 1,
00133                                     fifo->items,
00134                                     (max_size - fifo->size) * sizeof(int));
00135                                 memcpy(fifo->items,
00136                                     fifo->items + max_size - fifo->size,
00137                                     fifo->tail - max_size + fifo->size);
00138                                 fifo->tail -= max_size - fifo->size;
00139                         }
00140                 }
00141                 fifo->size = max_size;
00142         }
00143 
00144         fifo->items[fifo->tail] = value;
00145         fifo->tail = NEXT_INDEX(fifo, fifo->tail);
00146         return EOK;
00147 }
00148 
00156 int dyn_fifo_pop(dyn_fifo_t *fifo)
00157 {
00158         int value;
00159 
00160         if (!dyn_fifo_is_valid(fifo))
00161                 return EINVAL;
00162 
00163         if (fifo->head == fifo->tail)
00164                 return ENOENT;
00165 
00166         value = fifo->items[fifo->head];
00167         fifo->head = NEXT_INDEX(fifo, fifo->head);
00168         return value;
00169 }
00170 
00178 int dyn_fifo_value(dyn_fifo_t *fifo)
00179 {
00180         if (!dyn_fifo_is_valid(fifo))
00181                 return EINVAL;
00182 
00183         if (fifo->head == fifo->tail)
00184                 return ENOENT;
00185 
00186         return fifo->items[fifo->head];
00187 }
00188 
00195 int dyn_fifo_destroy(dyn_fifo_t *fifo)
00196 {
00197         if (!dyn_fifo_is_valid(fifo))
00198                 return EINVAL;
00199 
00200         free(fifo->items);
00201         fifo->magic_value = 0;
00202         return EOK;
00203 }
00204 

Generated on Thu Jun 2 07:45:45 2011 for HelenOS/USB by  doxygen 1.4.7