WebSVN – HelenOS-historic – Diff – /uspace/trunk/libc/include/libadt/fifo.h


/*
 * Copyright (C) 2006 Jakub Jermar
 * 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.
 */
 
/*
 * This implementation of FIFO stores values in an array
 * (static or dynamic). As such, these FIFOs have upper bound
 * on number of values they can store. Push and pop operations
 * are done via accessing the array through head and tail indices.
 * Because of better operation ordering in fifo_pop(), the access
 * policy for these two indices is to 'increment (mod size of FIFO)
 * and use'.
 */
 
#ifndef __FIFO_H__
#define __FIFO_H__
 
#include <malloc.h>
 
typedef unsigned long fifo_count_t;
typedef unsigned long fifo_index_t;
 
#define FIFO_CREATE_STATIC(name, t, itms)       \
    struct {                    \
        t fifo[(itms)];             \
        fifo_count_t items;         \
        fifo_index_t head;          \
        fifo_index_t tail;          \
    } name
 
/** Create and initialize static FIFO.
 *
 * FIFO is allocated statically.
 * This macro is suitable for creating smaller FIFOs.
 *
 * @param name Name of FIFO.
 * @param t Type of values stored in FIFO.
 * @param itms Number of items that can be stored in FIFO.
 */
#define FIFO_INITIALIZE_STATIC(name, t, itms)       \
 
 
    FIFO_CREATE_STATIC(name, t, itms) = {       \
 
 
 
        .items = (itms),            \
        .head = 0,              \
        .tail = 0               \
    }
 
/** Create and prepare dynamic FIFO.
 *
 * FIFO is allocated dynamically.
 * This macro is suitable for creating larger FIFOs.
 *
 * @param name Name of FIFO.
 * @param t Type of values stored in FIFO.
 * @param itms Number of items that can be stored in FIFO.
 */
#define FIFO_INITIALIZE_DYNAMIC(name, t, itms)      \
    struct {                    \
        t *fifo;                \
        fifo_count_t items;         \
        fifo_index_t head;          \
        fifo_index_t tail;          \
    } name = {                  \
        .fifo = NULL,               \
        .items = (itms),            \
        .head = 0,              \
        .tail = 0               \
    }
 
/** Pop value from head of FIFO.
 *
 * @param name FIFO name.
 *
 * @return Leading value in FIFO.
 */
#define fifo_pop(name) \
    name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
 
/** Push value to tail of FIFO.
 *
 * @param name FIFO name.
 * @param value Value to be appended to FIFO.
 *
 */
#define fifo_push(name, value) \
    name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value) 
 
/** Allocate memory for dynamic FIFO.
 *
 * @param name FIFO name.
 */
#define fifo_create(name) \
    name.fifo = malloc(sizeof(*name.fifo) * name.items)
 
#endif
 

Rev 1392	Rev 1481
1	/*	1	/*
2	* Copyright (C) 2006 Jakub Jermar	2	* Copyright (C) 2006 Jakub Jermar
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	/*	29	/*
30	* This implementation of FIFO stores values in an array	30	* This implementation of FIFO stores values in an array
31	* (static or dynamic). As such, these FIFOs have upper bound	31	* (static or dynamic). As such, these FIFOs have upper bound
32	* on number of values they can store. Push and pop operations	32	* on number of values they can store. Push and pop operations
33	* are done via accessing the array through head and tail indices.	33	* are done via accessing the array through head and tail indices.
34	* Because of better operation ordering in fifo_pop(), the access	34	* Because of better operation ordering in fifo_pop(), the access
35	* policy for these two indices is to 'increment (mod size of FIFO)	35	* policy for these two indices is to 'increment (mod size of FIFO)
36	* and use'.	36	* and use'.
37	*/	37	*/
38		38
39	#ifndef __FIFO_H__	39	#ifndef __FIFO_H__
40	#define __FIFO_H__	40	#define __FIFO_H__
41		41
42	#include <malloc.h>	42	#include <malloc.h>
43		43
44	typedef unsigned long fifo_count_t;	44	typedef unsigned long fifo_count_t;
45	typedef unsigned long fifo_index_t;	45	typedef unsigned long fifo_index_t;
46		46
-		47	#define FIFO_CREATE_STATIC(name, t, itms) \
-		48	struct { \
-		49	t fifo[(itms)]; \
-		50	fifo_count_t items; \
-		51	fifo_index_t head; \
-		52	fifo_index_t tail; \
-		53	} name
-		54
47	/** Create and initialize static FIFO.	55	/** Create and initialize static FIFO.
48	*	56	*
49	* FIFO is allocated statically.	57	* FIFO is allocated statically.
50	* This macro is suitable for creating smaller FIFOs.	58	* This macro is suitable for creating smaller FIFOs.
51	*	59	*
52	* @param name Name of FIFO.	60	* @param name Name of FIFO.
53	* @param t Type of values stored in FIFO.	61	* @param t Type of values stored in FIFO.
54	* @param itms Number of items that can be stored in FIFO.	62	* @param itms Number of items that can be stored in FIFO.
55	*/	63	*/
56	#define FIFO_INITIALIZE_STATIC(name, t, itms) \	64	#define FIFO_INITIALIZE_STATIC(name, t, itms) \
57	struct { \	-
58	t fifo[(itms)]; \	-
59	fifo_count_t items; \	65	FIFO_CREATE_STATIC(name, t, itms) = { \
60	fifo_index_t head; \	-
61	fifo_index_t tail; \	-
62	} name = { \	-
63	.items = (itms), \	66	.items = (itms), \
64	.head = 0, \	67	.head = 0, \
65	.tail = 0 \	68	.tail = 0 \
66	}	69	}
67		70
68	/** Create and prepare dynamic FIFO.	71	/** Create and prepare dynamic FIFO.
69	*	72	*
70	* FIFO is allocated dynamically.	73	* FIFO is allocated dynamically.
71	* This macro is suitable for creating larger FIFOs.	74	* This macro is suitable for creating larger FIFOs.
72	*	75	*
73	* @param name Name of FIFO.	76	* @param name Name of FIFO.
74	* @param t Type of values stored in FIFO.	77	* @param t Type of values stored in FIFO.
75	* @param itms Number of items that can be stored in FIFO.	78	* @param itms Number of items that can be stored in FIFO.
76	*/	79	*/
77	#define FIFO_INITIALIZE_DYNAMIC(name, t, itms) \	80	#define FIFO_INITIALIZE_DYNAMIC(name, t, itms) \
78	struct { \	81	struct { \
79	t *fifo; \	82	t *fifo; \
80	fifo_count_t items; \	83	fifo_count_t items; \
81	fifo_index_t head; \	84	fifo_index_t head; \
82	fifo_index_t tail; \	85	fifo_index_t tail; \
83	} name = { \	86	} name = { \
84	.fifo = NULL, \	87	.fifo = NULL, \
85	.items = (itms), \	88	.items = (itms), \
86	.head = 0, \	89	.head = 0, \
87	.tail = 0 \	90	.tail = 0 \
88	}	91	}
89		92
90	/** Pop value from head of FIFO.	93	/** Pop value from head of FIFO.
91	*	94	*
92	* @param name FIFO name.	95	* @param name FIFO name.
93	*	96	*
94	* @return Leading value in FIFO.	97	* @return Leading value in FIFO.
95	*/	98	*/
96	#define fifo_pop(name) \	99	#define fifo_pop(name) \
97	name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]	100	name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
98		101
99	/** Push value to tail of FIFO.	102	/** Push value to tail of FIFO.
100	*	103	*
101	* @param name FIFO name.	104	* @param name FIFO name.
102	* @param value Value to be appended to FIFO.	105	* @param value Value to be appended to FIFO.
103	*	106	*
104	*/	107	*/
105	#define fifo_push(name, value) \	108	#define fifo_push(name, value) \
106	name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)	109	name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)
107		110
108	/** Allocate memory for dynamic FIFO.	111	/** Allocate memory for dynamic FIFO.
109	*	112	*
110	* @param name FIFO name.	113	* @param name FIFO name.
111	*/	114	*/
112	#define fifo_create(name) \	115	#define fifo_create(name) \
113	name.fifo = malloc(sizeof(name.fifo) name.items)	116	name.fifo = malloc(sizeof(name.fifo) name.items)
114		117
115	#endif	118	#endif
116		119

Subversion Repositories HelenOS-historic

(root)/uspace/trunk/libc/include/libadt/fifo.h – Rev 1392 → 1481