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 fifo The dynamic queue. Input parameter.
 *  @param index The actual index to be shifted. Input parameter.
 */
#define NEXT_INDEX( fifo, index )   ((( index ) + 1 ) % (( fifo )->size + 1 ))
 
/** Checks if the queue is valid.
 *  @param fifo The dynamic queue. Input parameter.
 *  @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 4588 → 4704

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