← Back to branch summary

~martin-decky/helenos/rcu

« back to all changes in this revision

Viewing changes to uspace/srv/net/structures/dynamic_fifo.c

  • Committer: Pavel Rimsky
  • Date: 2010-02-20 20:54:53 UTC
  • mfrom: (292 head)
  • mto: This revision was merged to the branch mainline in revision 296.
  • Revision ID: pavel@pavel-laptop-20100220205453-70sim280j709dgp3
Synchronize with head.

Show diffs side-by-side

added added

removed removed

Lines of Context:
uspace/srv/net/structures/dynamic_fifo.c
 
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[in] fifo The dynamic queue.
 
50
 *  @param[in] index The actual index to be shifted.
 
51
 */
 
52
#define NEXT_INDEX( fifo, index )       ((( index ) + 1 ) % (( fifo )->size + 1 ))
 
53
 
 
54
/** 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
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
 */