WebSVN – HelenOS – Diff – /branches/network/uspace/srv/net/structures/dynamic_fifo.c


/*
 * Copyright (c) 2009 Lukas Mejdrech
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/** @addtogroup net
 *  @{
 */
 
/** @file
 *  Dynamic first in first out positive integer queue implementation.
 */
 
#include <errno.h>
#include <malloc.h>
#include <mem.h>
 
#include "dynamic_fifo.h"
 
/** Internal magic value for a&nbsp;consistency check.
 */
#define DYN_FIFO_MAGIC_VALUE    0x58627659
 
/** Returns the next queue index.
 *  The queue field is circular.
 *  @param[in] fifo The dynamic queue.
 *  @param[in] index The actual index to be shifted.
 */
#define NEXT_INDEX( fifo, index )   ((( index ) + 1 ) % (( fifo )->size + 1 ))
 
/** Checks if the queue is valid.
 *  @param[in] fifo The dynamic queue.
 *  @returns TRUE if the queue is valid.
 *  @returns FALSE otherwise.
 */
int dyn_fifo_is_valid( dyn_fifo_ref fifo );
 
int dyn_fifo_is_valid( dyn_fifo_ref fifo ){
    return fifo && ( fifo->magic_value == DYN_FIFO_MAGIC_VALUE );
}
 
int dyn_fifo_initialize( dyn_fifo_ref fifo, int size ){
    if( ! fifo ) return EBADMEM;
    if( size <= 0 ) return EINVAL;
    fifo->items = ( int * ) malloc( sizeof( int ) * size + 1 );
    if( ! fifo->items ) return ENOMEM;
    fifo->size = size;
    fifo->head = 0;
    fifo->tail = 0;
    fifo->magic_value = DYN_FIFO_MAGIC_VALUE;
    return EOK;
}
 
int dyn_fifo_push( dyn_fifo_ref fifo, int value, int max_size ){
    int *   new_items;
 
    if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
    if( NEXT_INDEX( fifo, fifo->tail ) == fifo->head ){
        if(( max_size > 0 ) && (( fifo->size * 2 ) > max_size )){
            if( fifo->size >= max_size ) return ENOMEM;
        }else{
            max_size = fifo->size * 2;
        }
        new_items = realloc( fifo->items, sizeof( int ) * max_size + 1 );
        if( ! new_items ) return ENOMEM;
        fifo->items = new_items;
        if( fifo->tail < fifo->head ){
            if( fifo->tail < max_size - fifo->size ){
                memcpy( fifo->items + fifo->size + 1, fifo->items, fifo->tail * sizeof( int ));
                fifo->tail += fifo->size + 1;
            }else{
                memcpy( fifo->items + fifo->size + 1, fifo->items, ( max_size - fifo->size ) * sizeof( int ));
                memcpy( fifo->items, fifo->items + max_size - fifo->size, fifo->tail - max_size + fifo->size );
                fifo->tail -= max_size - fifo->size;
            }
        }
        fifo->size = max_size;
    }
    fifo->items[ fifo->tail ] = value;
    fifo->tail = NEXT_INDEX( fifo, fifo->tail );
    return EOK;
}
 
int dyn_fifo_pop( dyn_fifo_ref fifo ){
    int value;
 
    if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
    if( fifo->head == fifo->tail ) return ENOENT;
    value = fifo->items[ fifo->head ];
    fifo->head = NEXT_INDEX( fifo, fifo->head );
    return value;
}
 
int dyn_fifo_value( dyn_fifo_ref fifo ){
    if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
    if( fifo->head == fifo->tail ) return ENOENT;
    return fifo->items[ fifo->head ];
}
 
int dyn_fifo_destroy( dyn_fifo_ref fifo ){
    if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
    free( fifo->items );
    fifo->magic_value = 0;
    return EOK;
}
 
/** @}
 */
 

Subversion Repositories HelenOS

(root)/branches/network/uspace/srv/net/structures/dynamic_fifo.c – Rev 4704 → 4756

Rev 4704		Rev 4756
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	* Dynamic first in first out positive integer queue implementation.
35	*/	35	*/
36		36
37	#include <errno.h>	37	#include <errno.h>
38	#include <malloc.h>	38	#include <malloc.h>
39	#include <mem.h>	39	#include <mem.h>
40		40
41	#include "dynamic_fifo.h"	41	#include "dynamic_fifo.h"
42		42
43	/** Internal magic value for a consistency check.	43	/** Internal magic value for a consistency check.
44	*/	44	*/
45	#define DYN_FIFO_MAGIC_VALUE 0x58627659	45	#define DYN_FIFO_MAGIC_VALUE 0x58627659
46		46
47	/** Returns the next queue index.	47	/** Returns the next queue index.
48	* The queue field is circular.	48	* The queue field is circular.
49	* @param fifo The dynamic queue. Input parameter.	49	* @param[in] fifo The dynamic queue.
50	* @param index The actual index to be shifted. Input parameter.	50	* @param[in] index The actual index to be shifted.
51	*/	51	*/
52	#define NEXT_INDEX( fifo, index ) ((( index ) + 1 ) % (( fifo )->size + 1 ))	52	#define NEXT_INDEX( fifo, index ) ((( index ) + 1 ) % (( fifo )->size + 1 ))
53		53
54	/** Checks if the queue is valid.	54	/** Checks if the queue is valid.
55	* @param fifo The dynamic queue. Input parameter.	55	* @param[in] fifo The dynamic queue.
56	* @returns TRUE if the queue is valid.	56	* @returns TRUE if the queue is valid.
57	* @returns FALSE otherwise.	57	* @returns FALSE otherwise.
58	*/	58	*/
59	int dyn_fifo_is_valid( dyn_fifo_ref fifo );	59	int dyn_fifo_is_valid( dyn_fifo_ref fifo );
60		60
61	int dyn_fifo_is_valid( dyn_fifo_ref fifo ){	61	int dyn_fifo_is_valid( dyn_fifo_ref fifo ){
62	return fifo && ( fifo->magic_value == DYN_FIFO_MAGIC_VALUE );	62	return fifo && ( fifo->magic_value == DYN_FIFO_MAGIC_VALUE );
63	}	63	}
64		64
65	int dyn_fifo_initialize( dyn_fifo_ref fifo, int size ){	65	int dyn_fifo_initialize( dyn_fifo_ref fifo, int size ){
66	if( ! fifo ) return EBADMEM;	66	if( ! fifo ) return EBADMEM;
67	if( size <= 0 ) return EINVAL;	67	if( size <= 0 ) return EINVAL;
68	fifo->items = ( int * ) malloc( sizeof( int ) * size + 1 );	68	fifo->items = ( int * ) malloc( sizeof( int ) * size + 1 );
69	if( ! fifo->items ) return ENOMEM;	69	if( ! fifo->items ) return ENOMEM;
70	fifo->size = size;	70	fifo->size = size;
71	fifo->head = 0;	71	fifo->head = 0;
72	fifo->tail = 0;	72	fifo->tail = 0;
73	fifo->magic_value = DYN_FIFO_MAGIC_VALUE;	73	fifo->magic_value = DYN_FIFO_MAGIC_VALUE;
74	return EOK;	74	return EOK;
75	}	75	}
76		76
77	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 ){
78	int * new_items;	78	int * new_items;
79		79
80	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;	80	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
81	if( NEXT_INDEX( fifo, fifo->tail ) == fifo->head ){	81	if( NEXT_INDEX( fifo, fifo->tail ) == fifo->head ){
82	if(( max_size > 0 ) && (( fifo->size * 2 ) > max_size )){	82	if(( max_size > 0 ) && (( fifo->size * 2 ) > max_size )){
83	if( fifo->size >= max_size ) return ENOMEM;	83	if( fifo->size >= max_size ) return ENOMEM;
84	}else{	84	}else{
85	max_size = fifo->size * 2;	85	max_size = fifo->size * 2;
86	}	86	}
87	new_items = realloc( fifo->items, sizeof( int ) * max_size + 1 );	87	new_items = realloc( fifo->items, sizeof( int ) * max_size + 1 );
88	if( ! new_items ) return ENOMEM;	88	if( ! new_items ) return ENOMEM;
89	fifo->items = new_items;	89	fifo->items = new_items;
90	if( fifo->tail < fifo->head ){	90	if( fifo->tail < fifo->head ){
91	if( fifo->tail < max_size - fifo->size ){	91	if( fifo->tail < max_size - fifo->size ){
92	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 ));
93	fifo->tail += fifo->size + 1;	93	fifo->tail += fifo->size + 1;
94	}else{	94	}else{
95	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 ));
96	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 );
97	fifo->tail -= max_size - fifo->size;	97	fifo->tail -= max_size - fifo->size;
98	}	98	}
99	}	99	}
100	fifo->size = max_size;	100	fifo->size = max_size;
101	}	101	}
102	fifo->items[ fifo->tail ] = value;	102	fifo->items[ fifo->tail ] = value;
103	fifo->tail = NEXT_INDEX( fifo, fifo->tail );	103	fifo->tail = NEXT_INDEX( fifo, fifo->tail );
104	return EOK;	104	return EOK;
105	}	105	}
106		106
107	int dyn_fifo_pop( dyn_fifo_ref fifo ){	107	int dyn_fifo_pop( dyn_fifo_ref fifo ){
108	int value;	108	int value;
109		109
110	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;	110	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
111	if( fifo->head == fifo->tail ) return ENOENT;	111	if( fifo->head == fifo->tail ) return ENOENT;
112	value = fifo->items[ fifo->head ];	112	value = fifo->items[ fifo->head ];
113	fifo->head = NEXT_INDEX( fifo, fifo->head );	113	fifo->head = NEXT_INDEX( fifo, fifo->head );
114	return value;	114	return value;
115	}	115	}
116		116
117	int dyn_fifo_value( dyn_fifo_ref fifo ){	117	int dyn_fifo_value( dyn_fifo_ref fifo ){
118	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;	118	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
119	if( fifo->head == fifo->tail ) return ENOENT;	119	if( fifo->head == fifo->tail ) return ENOENT;
120	return fifo->items[ fifo->head ];	120	return fifo->items[ fifo->head ];
121	}	121	}
122		122
123	int dyn_fifo_destroy( dyn_fifo_ref fifo ){	123	int dyn_fifo_destroy( dyn_fifo_ref fifo ){
124	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;	124	if( ! dyn_fifo_is_valid( fifo )) return EINVAL;
125	free( fifo->items );	125	free( fifo->items );
126	fifo->magic_value = 0;	126	fifo->magic_value = 0;
127	return EOK;	127	return EOK;
128	}	128	}
129		129
130	/** @}	130	/** @}
131	*/	131	*/
132		132