1 /*
2 * fifo.c Non-thread-safe fifo (FIFO) implementation, based
3 * on hash tables.
4 *
5 * Version: $Id: 7a9ecfac6d839c13bdce115bb842ae39c2996267 $
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
20 *
21 * Copyright 2005,2006 The FreeRADIUS server project
22 * Copyright 2005 Alan DeKok <aland@ox.org>
23 */
24
25 RCSID("$Id: 7a9ecfac6d839c13bdce115bb842ae39c2996267 $")
26
27 #include <freeradius-devel/libradius.h>
28
29 struct fr_fifo_t {
30 unsigned int num;
31 unsigned int first, last;
32 unsigned int max;
33 fr_fifo_free_t freeNode;
34
35 void *data[1];
36 };
37
38
fr_fifo_create(TALLOC_CTX * ctx,int max,fr_fifo_free_t freeNode)39 fr_fifo_t *fr_fifo_create(TALLOC_CTX *ctx, int max, fr_fifo_free_t freeNode)
40 {
41 fr_fifo_t *fi;
42
43 if ((max < 2) || (max > (1024 * 1024))) return NULL;
44
45 fi = talloc_zero_size(ctx, (sizeof(*fi) + (sizeof(fi->data[0])*max)));
46 if (!fi) return NULL;
47 talloc_set_type(fi, fr_fifo_t);
48
49 fi->max = max;
50 fi->freeNode = freeNode;
51
52 return fi;
53 }
54
fr_fifo_free(fr_fifo_t * fi)55 void fr_fifo_free(fr_fifo_t *fi)
56 {
57 unsigned int i;
58
59 if (!fi) return;
60
61 if (fi->freeNode) {
62 for (i = 0 ; i < fi->num; i++) {
63 unsigned int element;
64
65 element = i + fi->first;
66 if (element > fi->max) {
67 element -= fi->max;
68 }
69
70 fi->freeNode(fi->data[element]);
71 fi->data[element] = NULL;
72 }
73 }
74
75 memset(fi, 0, sizeof(*fi));
76 talloc_free(fi);
77 }
78
fr_fifo_push(fr_fifo_t * fi,void * data)79 int fr_fifo_push(fr_fifo_t *fi, void *data)
80 {
81 if (!fi || !data) return 0;
82
83 if (fi->num >= fi->max) return 0;
84
85 fi->data[fi->last++] = data;
86 if (fi->last >= fi->max) fi->last = 0;
87 fi->num++;
88
89 return 1;
90 }
91
fr_fifo_pop(fr_fifo_t * fi)92 void *fr_fifo_pop(fr_fifo_t *fi)
93 {
94 void *data;
95
96 if (!fi || (fi->num == 0)) return NULL;
97
98 data = fi->data[fi->first++];
99
100 if (fi->first >= fi->max) {
101 fi->first = 0;
102 }
103 fi->num--;
104
105 return data;
106 }
107
fr_fifo_peek(fr_fifo_t * fi)108 void *fr_fifo_peek(fr_fifo_t *fi)
109 {
110 if (!fi || (fi->num == 0)) return NULL;
111
112 return fi->data[fi->first];
113 }
114
fr_fifo_num_elements(fr_fifo_t * fi)115 unsigned int fr_fifo_num_elements(fr_fifo_t *fi)
116 {
117 if (!fi) return 0;
118
119 return fi->num;
120 }
121
122 #ifdef TESTING
123
124 /*
125 * cc -DTESTING -I .. fifo.c -o fifo
126 *
127 * ./fifo
128 */
129
130 #define MAX 1024
main(int argc,char ** argv)131 int main(int argc, char **argv)
132 {
133 int i, j, array[MAX];
134 fr_fifo_t *fi;
135
136 fi = fr_fifo_create(NULL, MAX, NULL);
137 if (!fi) fr_exit(1);
138
139 for (j = 0; j < 5; j++) {
140 #define SPLIT (MAX/3)
141 #define COUNT ((j * SPLIT) + i)
142 for (i = 0; i < SPLIT; i++) {
143 array[COUNT % MAX] = COUNT;
144
145 if (!fr_fifo_push(fi, &array[COUNT % MAX])) {
146 fprintf(stderr, "%d %d\tfailed pushing %d\n",
147 j, i, COUNT);
148 fr_exit(2);
149 }
150
151 if (fr_fifo_num_elements(fi) != (i + 1)) {
152 fprintf(stderr, "%d %d\tgot size %d expected %d\n",
153 j, i, i + 1, fr_fifo_num_elements(fi));
154 fr_exit(1);
155 }
156 }
157
158 if (fr_fifo_num_elements(fi) != SPLIT) {
159 fprintf(stderr, "HALF %d %d\n",
160 fr_fifo_num_elements(fi), SPLIT);
161 fr_exit(1);
162 }
163
164 for (i = 0; i < SPLIT; i++) {
165 int *p;
166
167 p = fr_fifo_pop(fi);
168 if (!p) {
169 fprintf(stderr, "No pop at %d\n", i);
170 fr_exit(3);
171 }
172
173 if (*p != COUNT) {
174 fprintf(stderr, "%d %d\tgot %d expected %d\n",
175 j, i, *p, COUNT);
176 fr_exit(4);
177 }
178
179 if (fr_fifo_num_elements(fi) != SPLIT - (i + 1)) {
180 fprintf(stderr, "%d %d\tgot size %d expected %d\n",
181 j, i, SPLIT - (i + 1), fr_fifo_num_elements(fi));
182 fr_exit(1);
183 }
184 }
185
186 if (fr_fifo_num_elements(fi) != 0) {
187 fprintf(stderr, "ZERO %d %d\n",
188 fr_fifo_num_elements(fi), 0);
189 fr_exit(1);
190 }
191 }
192
193 fr_fifo_free(fi);
194
195 fr_exit(0);
196 }
197 #endif
198