Changeset 7093a32 in mainline


Ignore:
Timestamp:
2010-09-26T15:20:55Z (14 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
4edd39fc
Parents:
2544442
Message:

Cleanup of dynamic FIFO.

Location:
uspace/lib/c
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/generic/adt/dynamic_fifo.c

    r2544442 r7093a32  
    3232
    3333/** @file
    34  *  Dynamic first in first out positive integer queue implementation.
     34 * Dynamic first in first out positive integer queue implementation.
    3535 */
    3636
    … …  
    4141#include <adt/dynamic_fifo.h>
    4242
    43 /** Internal magic value for a&nbsp;consistency check.
    44  */
     43/** Internal magic value for a consistency check. */
    4544#define DYN_FIFO_MAGIC_VALUE    0x58627659
    4645
    4746/** Returns the next queue index.
    48  *  The queue field is circular.
    49  *  @param[in] fifo The dynamic queue.
    50  *  @param[in] index The actual index to be shifted.
     47 *
     48 * The queue field is circular.
     49 *
     50 * @param[in] fifo      The dynamic queue.
     51 * @param[in] index     The actual index to be shifted.
    5152 */
    5253#define NEXT_INDEX(fifo, index) (((index) + 1) % ((fifo)->size + 1))
    5354
    5455/** Checks if the queue is valid.
    55  *  @param[in] fifo The dynamic queue.
    56  *  @returns TRUE if the queue is valid.
    57  *  @returns FALSE otherwise.
    58  */
    59 static int dyn_fifo_is_valid(dyn_fifo_ref fifo){
     56 *
     57 * @param[in] fifo      The dynamic queue.
     58 * @returns             TRUE if the queue is valid.
     59 * @returns             FALSE otherwise.
     60 */
     61static int dyn_fifo_is_valid(dyn_fifo_ref fifo)
     62{
    6063        return fifo && (fifo->magic_value == DYN_FIFO_MAGIC_VALUE);
    6164}
    6265
    63 int dyn_fifo_initialize(dyn_fifo_ref fifo, int size){
    64         if(! fifo){
     66/** Initializes the dynamic queue.
     67 *
     68 * @param[in,out] fifo  The dynamic queue.
     69 * @param[in] size      The initial queue size.
     70 * @returns             EOK on success.
     71 * @returns             EINVAL if the queue is not valid.
     72 * @returns             EBADMEM if the fifo parameter is NULL.
     73 * @returns             ENOMEM if there is not enough memory left.
     74 */
     75int dyn_fifo_initialize(dyn_fifo_ref fifo, int size)
     76{
     77        if (!fifo)
    6578                return EBADMEM;
    66         }
    67         if(size <= 0){
    68                 return EINVAL;
    69         }
     79
     80        if (size <= 0)
     81                return EINVAL;
     82
    7083        fifo->items = (int *) malloc(sizeof(int) * size + 1);
    71         if(! fifo->items){
     84        if (!fifo->items)
    7285                return ENOMEM;
    73         }
     86
    7487        fifo->size = size;
    7588        fifo->head = 0;
    7689        fifo->tail = 0;
    7790        fifo->magic_value = DYN_FIFO_MAGIC_VALUE;
     91
    7892        return EOK;
    7993}
    8094
    81 int dyn_fifo_push(dyn_fifo_ref fifo, int value, int max_size){
     95/** Appends a new item to the queue end.
     96 *
     97 * @param[in,out] fifo  The dynamic queue.
     98 * @param[in] value     The new item value. Should be positive.
     99 * @param[in] max_size  The maximum queue size. The queue is not resized beyound
     100 *                      this limit. May be zero or negative to indicate no
     101 *                      limit.
     102 * @returns             EOK on success.
     103 * @returns             EINVAL if the queue is not valid.
     104 * @returns             ENOMEM if there is not enough memory left.
     105 */
     106int dyn_fifo_push(dyn_fifo_ref fifo, int value, int max_size)
     107{
    82108        int * new_items;
    83109
    84         if(! dyn_fifo_is_valid(fifo)){
    85                 return EINVAL;
    86         }
    87         if(NEXT_INDEX(fifo, fifo->tail) == fifo->head){
    88                 if((max_size > 0) && ((fifo->size * 2) > max_size)){
    89                         if(fifo->size >= max_size){
     110        if (!dyn_fifo_is_valid(fifo))
     111                return EINVAL;
     112
     113        if (NEXT_INDEX(fifo, fifo->tail) == fifo->head) {
     114                if ((max_size > 0) && ((fifo->size * 2) > max_size)) {
     115                        if(fifo->size >= max_size)
    90116                                return ENOMEM;
    91                         }
    92                 }else{
     117                } else {
    93118                        max_size = fifo->size * 2;
    94119                }
     120
    95121                new_items = realloc(fifo->items, sizeof(int) * max_size + 1);
    96                 if(! new_items){
     122                if (!new_items)
    97123                        return ENOMEM;
    98                 }
     124
    99125                fifo->items = new_items;
    100                 if(fifo->tail < fifo->head){
    101                         if(fifo->tail < max_size - fifo->size){
    102                                 memcpy(fifo->items + fifo->size + 1, fifo->items, fifo->tail * sizeof(int));
     126                if (fifo->tail < fifo->head) {
     127                        if (fifo->tail < max_size - fifo->size) {
     128                                memcpy(fifo->items + fifo->size + 1,
     129                                    fifo->items, fifo->tail * sizeof(int));
    103130                                fifo->tail += fifo->size + 1;
    104                         }else{
    105                                 memcpy(fifo->items + fifo->size + 1, fifo->items, (max_size - fifo->size) * sizeof(int));
    106                                 memcpy(fifo->items, fifo->items + max_size - fifo->size, fifo->tail - max_size + fifo->size);
     131                        } else {
     132                                memcpy(fifo->items + fifo->size + 1,
     133                                    fifo->items,
     134                                    (max_size - fifo->size) * sizeof(int));
     135                                memcpy(fifo->items,
     136                                    fifo->items + max_size - fifo->size,
     137                                    fifo->tail - max_size + fifo->size);
    107138                                fifo->tail -= max_size - fifo->size;
    108139                        }
    … …  
    110141                fifo->size = max_size;
    111142        }
     143
    112144        fifo->items[fifo->tail] = value;
    113145        fifo->tail = NEXT_INDEX(fifo, fifo->tail);
    … …  
    115147}
    116148
    117 int dyn_fifo_pop(dyn_fifo_ref fifo){
     149/** Returns and excludes the first item in the queue.
     150 *
     151 * @param[in,out] fifoi The dynamic queue.
     152 * @returns             Value of the first item in the queue.
     153 * @returns             EINVAL if the queue is not valid.
     154 * @returns             ENOENT if the queue is empty.
     155 */
     156int dyn_fifo_pop(dyn_fifo_ref fifo)
     157{
    118158        int value;
    119159
    120         if(! dyn_fifo_is_valid(fifo)){
    121                 return EINVAL;
    122         }
    123         if(fifo->head == fifo->tail){
     160        if (!dyn_fifo_is_valid(fifo))
     161                return EINVAL;
     162
     163        if (fifo->head == fifo->tail)
    124164                return ENOENT;
    125         }
     165
    126166        value = fifo->items[fifo->head];
    127167        fifo->head = NEXT_INDEX(fifo, fifo->head);
    … …  
    129169}
    130170
    131 int dyn_fifo_value(dyn_fifo_ref fifo){
    132         if(! dyn_fifo_is_valid(fifo)){
    133                 return EINVAL;
    134         }
    135         if(fifo->head == fifo->tail){
     171/** Returns and keeps the first item in the queue.
     172 *
     173 * @param[in,out] fifo  The dynamic queue.
     174 * @returnsi            Value of the first item in the queue.
     175 * @returns             EINVAL if the queue is not valid.
     176 * @returns             ENOENT if the queue is empty.
     177 */
     178int dyn_fifo_value(dyn_fifo_ref fifo)
     179{
     180        if (!dyn_fifo_is_valid(fifo))
     181                return EINVAL;
     182
     183        if (fifo->head == fifo->tail)
    136184                return ENOENT;
    137         }
     185
    138186        return fifo->items[fifo->head];
    139187}
    140188
    141 int dyn_fifo_destroy(dyn_fifo_ref fifo){
    142         if(! dyn_fifo_is_valid(fifo)){
    143                 return EINVAL;
    144         }
     189/** Clears and destroys the queue.
     190 *
     191 *  @param[in,out] fifo         The dynamic queue.
     192 *  @returns                    EOK on success.
     193 *  @returns                    EINVAL if the queue is not valid.
     194 */
     195int dyn_fifo_destroy(dyn_fifo_ref fifo)
     196{
     197        if (!dyn_fifo_is_valid(fifo))
     198                return EINVAL;
     199
    145200        free(fifo->items);
    146201        fifo->magic_value = 0;

  • uspace/lib/c/include/adt/dynamic_fifo.h

    r2544442 r7093a32  
    3232
    3333/** @file
    34  *  Dynamic first in first out positive integer queue.
    35  *  Possitive integer values only.
     34 * Dynamic first in first out positive integer queue.
     35 * Possitive integer values only.
    3636 */
    3737
    … …  
    4040
    4141/** Type definition of the dynamic fifo queue.
    42  *  @see dyn_fifo
     42 * @see dyn_fifo
    4343 */
    4444typedef struct dyn_fifo dyn_fifo_t;
    … …  
    4747 *  @see dyn_fifo
    4848 */
    49 typedef dyn_fifo_t *    dyn_fifo_ref;
     49typedef dyn_fifo_t *dyn_fifo_ref;
    5050
    5151/** Dynamic first in first out positive integer queue.
    52  *  Possitive integer values only.
    53  *  The queue automatically resizes if needed.
     52 * Possitive integer values only.
     53 * The queue automatically resizes if needed.
    5454 */
    55 struct dyn_fifo{
    56         /** Stored item field.
    57          */
    58         int *   items;
    59         /** Actual field size.
    60          */
     55struct dyn_fifo {
     56        /** Stored item field. */
     57        int *items;
     58        /** Actual field size. */
    6159        int size;
    62         /** First item in the queue index.
    63          */
     60        /** First item in the queue index. */
    6461        int head;
    65         /** Last item in the queue index.
    66          */
     62        /** Last item in the queue index. */
    6763        int tail;
    68         /** Consistency check magic value.
    69          */
     64        /** Consistency check magic value. */
    7065        int magic_value;
    7166};
    7267
    73 /** Initializes the dynamic queue.
    74  *  @param[in,out] fifo The dynamic queue.
    75  *  @param[in] size The initial queue size.
    76  *  @returns EOK on success.
    77  *  @returns EINVAL if the queue is not valid.
    78  *  @returns EBADMEM if the fifo parameter is NULL.
    79  *  @returns ENOMEM if there is not enough memory left.
    80  */
    81 extern int dyn_fifo_initialize(dyn_fifo_ref fifo, int size);
    82 
    83 /** Appends a new item to the queue end.
    84  *  @param[in,out] fifo The dynamic queue.
    85  *  @param[in] value The new item value. Should be positive.
    86  *  @param[in] max_size The maximum queue size. The queue is not resized beyound this limit. May be zero or negative (<=0) to indicate no limit.
    87  *  @returns EOK on success.
    88  *  @returns EINVAL if the queue is not valid.
    89  *  @returns ENOMEM if there is not enough memory left.
    90  */
    91 extern int dyn_fifo_push(dyn_fifo_ref fifo, int value, int max_size);
    92 
    93 /** Returns and excludes the first item in the queue.
    94  *  @param[in,out] fifo The dynamic queue.
    95  *  @returns Value of the first item in the queue.
    96  *  @returns EINVAL if the queue is not valid.
    97  *  @returns ENOENT if the queue is empty.
    98  */
    99 extern int dyn_fifo_pop(dyn_fifo_ref fifo);
    100 
    101 /** Returns and keeps the first item in the queue.
    102  *  @param[in,out] fifo The dynamic queue.
    103  *  @returns Value of the first item in the queue.
    104  *  @returns EINVAL if the queue is not valid.
    105  *  @returns ENOENT if the queue is empty.
    106  */
    107 extern int dyn_fifo_value(dyn_fifo_ref fifo);
    108 
    109 /** Clears and destroys the queue.
    110  *  @param[in,out] fifo The dynamic queue.
    111  *  @returns EOK on success.
    112  *  @returns EINVAL if the queue is not valid.
    113  */
    114 extern int dyn_fifo_destroy(dyn_fifo_ref fifo);
     68extern int dyn_fifo_initialize(dyn_fifo_ref, int);
     69extern int dyn_fifo_destroy(dyn_fifo_ref);
     70extern int dyn_fifo_push(dyn_fifo_ref, int, int);
     71extern int dyn_fifo_pop(dyn_fifo_ref);
     72extern int dyn_fifo_value(dyn_fifo_ref);
    11573
    11674#endif
Note: See TracChangeset for help on using the changeset viewer.