Subversion Repositories HelenOS

Rev

Rev 2106 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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