1 | /* a fifo queue that never fills. |
---|
2 | * Copyright (C) 2005 Elwood C. Downey ecdowney@clearskyinstitute.com |
---|
3 | * includes standalone commandline test program, see below. |
---|
4 | |
---|
5 | This library is free software; you can redistribute it and/or |
---|
6 | modify it under the terms of the GNU Lesser General Public |
---|
7 | License as published by the Free Software Foundation; either |
---|
8 | version 2.1 of the License, or (at your option) any later version. |
---|
9 | |
---|
10 | This library is distributed in the hope that it will be useful, |
---|
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
13 | Lesser General Public License for more details. |
---|
14 | |
---|
15 | You should have received a copy of the GNU Lesser General Public |
---|
16 | License along with this library; if not, write to the Free Software |
---|
17 | Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
---|
18 | |
---|
19 | */ |
---|
20 | |
---|
21 | /** \file fq.c |
---|
22 | \brief a fifo queue that never fills. |
---|
23 | |
---|
24 | Generic FIFO Queue. |
---|
25 | |
---|
26 | an FQ is a FIFO list of pointers to void, each called an "element". |
---|
27 | elements are added at q[head]. there are (nq) elements in the list. the |
---|
28 | element to be removed next is q[head-nq]. there are (head-nq) empty slots |
---|
29 | at the front of the q array. there are (nmem-head) elements available at |
---|
30 | the end. if the head reaches the end, existing enties are slid to the front |
---|
31 | of the array and total memory is adjusted up or down as required. |
---|
32 | |
---|
33 | example: |
---|
34 | |
---|
35 | <-------------------- nmem = 17 ---------------------------------> |
---|
36 | <-- head - nq = 6 ---> <-- nq = 4 --> <---- nmem - head = 7 --> |
---|
37 | --------------------------------------------------------------------- |
---|
38 | | | | | | | | x | x | x | x | | | | | | | | |
---|
39 | --------------------------------------------------------------------- |
---|
40 | 0 1 2 3 4 5 6 7 8 9 ^ |
---|
41 | head = 10 |
---|
42 | |
---|
43 | \author Elwood Downey |
---|
44 | */ |
---|
45 | |
---|
46 | #include <stdlib.h> |
---|
47 | #include <string.h> |
---|
48 | |
---|
49 | #include "fq.h" |
---|
50 | |
---|
51 | struct _FQ { |
---|
52 | void **q; /* malloced array of (void *) */ |
---|
53 | int nq; /* number of elements on queue */ |
---|
54 | int head; /* index into q[] of next empty spot */ |
---|
55 | int nmem; /* number of total slots in q[] */ |
---|
56 | int grow; /* n elements to grow when out of room*/ |
---|
57 | }; |
---|
58 | |
---|
59 | /* default memory managers, override with setMemFuncsFQ() */ |
---|
60 | static void *(*mymalloc)(size_t size) = malloc; |
---|
61 | static void *(*myrealloc)(void *ptr, size_t size) = realloc; |
---|
62 | static void (*myfree)(void *ptr) = free; |
---|
63 | |
---|
64 | static void chkFQ (FQ *q); |
---|
65 | |
---|
66 | /* return pointer to a new FQ, or NULL if no more memory. |
---|
67 | * grow is an efficiency hint of the number of elements to grow when out of |
---|
68 | * room, nothing terrible happens if it is wrong. |
---|
69 | */ |
---|
70 | FQ * |
---|
71 | newFQ (int grow) |
---|
72 | { |
---|
73 | FQ *q = (FQ *)(*mymalloc)(sizeof(FQ)); |
---|
74 | memset (q, 0, sizeof(FQ)); |
---|
75 | q->q = (*mymalloc) (1); /* seed for realloc */ |
---|
76 | q->grow = grow > 0 ? grow : 1; |
---|
77 | return (q); |
---|
78 | } |
---|
79 | |
---|
80 | /* delete a FQ no longer needed */ |
---|
81 | void |
---|
82 | delFQ (FQ *q) |
---|
83 | { |
---|
84 | (*myfree) (q->q); /* guaranteed set in newFQ() */ |
---|
85 | (*myfree) ((void *)q); |
---|
86 | } |
---|
87 | |
---|
88 | /* push an element onto the given FQ */ |
---|
89 | void |
---|
90 | pushFQ (FQ *q, void *e) |
---|
91 | { |
---|
92 | chkFQ (q); |
---|
93 | q->q[q->head++] = e; |
---|
94 | q->nq++; |
---|
95 | } |
---|
96 | |
---|
97 | /* pop and return the next element in the given FQ, or NULL if empty */ |
---|
98 | void * |
---|
99 | popFQ (FQ *q) |
---|
100 | { |
---|
101 | return (q->nq > 0 ? q->q[q->head - q->nq--] : NULL); |
---|
102 | } |
---|
103 | |
---|
104 | /* return next element in the given FQ leaving it on the q, or NULL if empty */ |
---|
105 | void * |
---|
106 | peekFQ (FQ *q) |
---|
107 | { |
---|
108 | return (peekiFQ(q,0)); |
---|
109 | } |
---|
110 | |
---|
111 | /* return ith element from head of the given FQ. |
---|
112 | * this can be used for iteration as: |
---|
113 | * for (i = 0; i < nFQ(q); i++) |
---|
114 | * void *e = peekiFQ(q,i); |
---|
115 | */ |
---|
116 | void * |
---|
117 | peekiFQ (FQ *q, int i) |
---|
118 | { |
---|
119 | return (q->nq > 0 ? q->q[q->head - q->nq + i] : NULL); |
---|
120 | } |
---|
121 | |
---|
122 | /* return the number of elements in the given FQ */ |
---|
123 | int |
---|
124 | nFQ (FQ *q) |
---|
125 | { |
---|
126 | return (q->nq); |
---|
127 | } |
---|
128 | |
---|
129 | /* install new version of malloc/realloc/free. |
---|
130 | * N.B. don't call after first use of any other FQ function |
---|
131 | */ |
---|
132 | void |
---|
133 | setMemFuncsFQ (void *(*newmalloc)(size_t size), |
---|
134 | void *(*newrealloc)(void *ptr, size_t size), |
---|
135 | void (*newfree)(void *ptr)) |
---|
136 | { |
---|
137 | mymalloc = newmalloc; |
---|
138 | myrealloc = newrealloc; |
---|
139 | myfree = newfree; |
---|
140 | } |
---|
141 | |
---|
142 | /* insure q can hold one more element */ |
---|
143 | static void |
---|
144 | chkFQ (FQ *q) |
---|
145 | { |
---|
146 | int infront; |
---|
147 | |
---|
148 | /* done if still room at end */ |
---|
149 | if (q->nmem > q->head) |
---|
150 | return; |
---|
151 | |
---|
152 | /* move list to front */ |
---|
153 | infront = q->head - q->nq; |
---|
154 | memmove (q->q, &q->q[infront], q->nq * sizeof(void*)); |
---|
155 | q->head -= infront; |
---|
156 | |
---|
157 | /* realloc to minimum number of grow-sized chunks required */ |
---|
158 | q->nmem = q->grow*(q->head/q->grow+1); |
---|
159 | q->q = (*myrealloc) (q->q, q->nmem * sizeof(void*)); |
---|
160 | } |
---|
161 | |
---|
162 | #if defined(TEST_FQ) |
---|
163 | |
---|
164 | /* to build a stand-alone commandline test program: |
---|
165 | * cc -DTEST_FQ -o fq fq.c |
---|
166 | * run ./fq to test push/pop/peek and watch the queue after each operation. |
---|
167 | * the queue test elements are char, please excuse the ugly casts. |
---|
168 | */ |
---|
169 | |
---|
170 | #include <stdio.h> |
---|
171 | |
---|
172 | /* draw a simple graphical representation of the given FQ */ |
---|
173 | static void |
---|
174 | prFQ (FQ *q) |
---|
175 | { |
---|
176 | int i; |
---|
177 | |
---|
178 | /* print the q, empty slots print as '.' */ |
---|
179 | for (i = 0; i < q->nmem; i++) { |
---|
180 | if (i >= q->head - q->nq && i < q->head) |
---|
181 | printf ("%c", (char)(int)q->q[i]); |
---|
182 | else |
---|
183 | printf ("."); |
---|
184 | } |
---|
185 | |
---|
186 | /* add right-justified stats */ |
---|
187 | printf ("%*s nmem = %2d head = %2d nq = %2d\n", 50-i, "", q->nmem, |
---|
188 | q->head, q->nq); |
---|
189 | } |
---|
190 | |
---|
191 | int |
---|
192 | main (int ac, char *av[]) |
---|
193 | { |
---|
194 | FQ *q = newFQ(8); |
---|
195 | int c, e = -1; |
---|
196 | void *p; |
---|
197 | |
---|
198 | printf ("Commands:\n"); |
---|
199 | printf (" P = push a letter a-z\n"); |
---|
200 | printf (" p = pop a letter\n"); |
---|
201 | printf (" k = peek into queue\n"); |
---|
202 | |
---|
203 | while ((c = fgetc(stdin)) != EOF) { |
---|
204 | switch (c) { |
---|
205 | case 'P': |
---|
206 | pushFQ (q, (void*)('a'+(e=(e+1)%26))); |
---|
207 | prFQ(q); |
---|
208 | break; |
---|
209 | case 'p': |
---|
210 | p = popFQ (q); |
---|
211 | if (p) |
---|
212 | printf ("popped %c\n", (char)(int)p); |
---|
213 | else |
---|
214 | printf ("popped empty q\n"); |
---|
215 | prFQ(q); |
---|
216 | break; |
---|
217 | case 'k': |
---|
218 | p = peekFQ (q); |
---|
219 | if (p) |
---|
220 | printf ("peeked %c\n", (char)(int)p); |
---|
221 | else |
---|
222 | printf ("peeked empty q\n"); |
---|
223 | prFQ(q); |
---|
224 | break; |
---|
225 | default: |
---|
226 | break; |
---|
227 | } |
---|
228 | } |
---|
229 | |
---|
230 | return (0); |
---|
231 | } |
---|
232 | #endif /* TEST_FQ */ |
---|
233 | |
---|