All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
fifo.c
Go to the documentation of this file.
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;
34 
35  void *data[1];
36 };
37 
38 
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 
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 
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 
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 
109 {
110  if (!fi || (fi->num == 0)) return NULL;
111 
112  return fi->data[fi->first];
113 }
114 
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
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
unsigned int num
Definition: fifo.c:30
void fr_fifo_free(fr_fifo_t *fi)
Definition: fifo.c:55
unsigned int last
Definition: fifo.c:31
void * fr_fifo_peek(fr_fifo_t *fi)
Definition: fifo.c:108
unsigned int fr_fifo_num_elements(fr_fifo_t *fi)
Definition: fifo.c:115
unsigned int first
Definition: fifo.c:31
Definition: fifo.c:29
uint8_t data[]
Definition: eap_pwd.h:625
int fr_fifo_push(fr_fifo_t *fi, void *data)
Definition: fifo.c:79
unsigned int max
Definition: fifo.c:32
fr_fifo_t * fr_fifo_create(TALLOC_CTX *ctx, int max, fr_fifo_free_t freeNode)
Definition: fifo.c:39
void(* fr_fifo_free_t)(void *)
Definition: libradius.h:566
int main(int argc, char *argv[])
Definition: radattr.c:959
void * fr_fifo_pop(fr_fifo_t *fi)
Definition: fifo.c:92
fr_fifo_free_t freeNode
Definition: fifo.c:33
void * data[1]
Definition: fifo.c:35
#define RCSID(id)
Definition: build.h:135
#define fr_exit(_x)
Definition: libradius.h:508