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