kernel/generic/include/adt/fifo.h

   1 /*
   2  * Copyright (c) 2006 Jakub Jermar
   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 genericadt
  30  * @{
  31  */
  32 /** @file
  33  */
  34
  35 /*
  36  * This implementation of FIFO stores values in an array
  37  * (static or dynamic). As such, these FIFOs have upper bound
  38  * on number of values they can store. Push and pop operations
  39  * are done via accessing the array through head and tail indices.
  40  * Because of better operation ordering in fifo_pop(), the access
  41  * policy for these two indices is to 'increment (mod size of FIFO)
  42  * and use'.
  43  */
  44
  45 #ifndef KERN_FIFO_H_
  46 #define KERN_FIFO_H_
  47
  48 #include <mm/slab.h>
  49
  50 /** Create and initialize static FIFO.
  51  *
  52  * FIFO is allocated statically.
  53  * This macro is suitable for creating smaller FIFOs.
  54  *
  55  * @param name Name of FIFO.
  56  * @param t Type of values stored in FIFO.
  57  * @param itms Number of items that can be stored in FIFO.
  58  */
  59 #define FIFO_INITIALIZE_STATIC(name, t, itms)           \
  60         struct {                                        \
  61                 t fifo[(itms)];                         \
  62                 count_t items;                          \
  63                 index_t head;                           \
  64                 index_t tail;                           \
  65         } name = {                                      \
  66                 .items = (itms),                        \
  67                 .head = 0,                              \
  68                 .tail = 0                               \
  69         }
  70
  71 /** Create and prepare dynamic FIFO.
  72  *
  73  * FIFO is allocated dynamically.
  74  * This macro is suitable for creating larger FIFOs.
  75  *
  76  * @param name Name of FIFO.
  77  * @param t Type of values stored in FIFO.
  78  * @param itms Number of items that can be stored in FIFO.
  79  */
  80 #define FIFO_INITIALIZE_DYNAMIC(name, t, itms)          \
  81         struct {                                        \
  82                 t *fifo;                                \
  83                 count_t items;                          \
  84                 index_t head;                           \
  85                 index_t tail;                           \
  86         } name = {                                      \
  87                 .fifo = NULL,                           \
  88                 .items = (itms),                        \
  89                 .head = 0,                              \
  90                 .tail = 0                               \
  91         }
  92
  93 /** Pop value from head of FIFO.
  94  *
  95  * @param name FIFO name.
  96  *
  97  * @return Leading value in FIFO.
  98  */
  99 #define fifo_pop(name) \
 100         name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
 101
 102 /** Push value to tail of FIFO.
 103  *
 104  * @param name FIFO name.
 105  * @param value Value to be appended to FIFO.
 106  *
 107  */
 108 #define fifo_push(name, value) \
 109         name.fifo[name.tail = \
 110             (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)
 111
 112 /** Allocate memory for dynamic FIFO.
 113  *
 114  * @param name FIFO name.
 115  */
 116 #define fifo_create(name) \
 117         name.fifo = malloc(sizeof(*name.fifo) * name.items, 0)
 118
 119 #endif
 120
 121 /** @}
 122  */